src/system/kernel/util/queue.cpp

   1 /* Standard queue */
   2
   3 /*
   4 ** Copyright 2001, Travis Geiselbrecht. All rights reserved.
   5 ** Distributed under the terms of the NewOS License.
   6 */
   7
   8 #include <kernel.h>
   9 #include <queue.h>
  10 #include <malloc.h>
  11 #include <errno.h>
  12
  13 typedef struct queue_element {
  14         void *next;
  15 } queue_element;
  16
  17 typedef struct queue_typed {
  18         queue_element *head;
  19         queue_element *tail;
  20         int count;
  21 } queue_typed;
  22
  23
  24 int
  25 queue_init(queue *q)
  26 {
  27         q->head = q->tail = NULL;
  28         q->count = 0;
  29         return 0;
  30 }
  31
  32
  33 int
  34 queue_remove_item(queue *_q, void *e)
  35 {
  36         queue_typed *q = (queue_typed *)_q;
  37         queue_element *elem = (queue_element *)e;
  38         queue_element *temp, *last = NULL;
  39
  40         temp = (queue_element *)q->head;
  41         while (temp) {
  42                 if (temp == elem) {
  43                         if (last)
  44                                 last->next = temp->next;
  45                         else
  46                                 q->head = (queue_element*)temp->next;
  47
  48                         if (q->tail == temp)
  49                                 q->tail = last;
  50                         q->count--;
  51                         return 0;
  52                 }
  53                 last = temp;
  54                 temp = (queue_element*)temp->next;
  55         }
  56
  57         return -1;
  58 }
  59
  60
  61 int
  62 queue_enqueue(queue *_q, void *e)
  63 {
  64         queue_typed *q = (queue_typed *)_q;
  65         queue_element *elem = (queue_element *)e;
  66
  67         if (q->tail == NULL) {
  68                 q->tail = elem;
  69                 q->head = elem;
  70         } else {
  71                 q->tail->next = elem;
  72                 q->tail = elem;
  73         }
  74         elem->next = NULL;
  75         q->count++;
  76         return 0;
  77 }
  78
  79
  80 void *
  81 queue_dequeue(queue *_q)
  82 {
  83         queue_typed *q = (queue_typed *)_q;
  84         queue_element *elem;
  85
  86         elem = q->head;
  87         if (q->head != NULL)
  88                 q->head = (queue_element*)q->head->next;
  89         if (q->tail == elem)
  90                 q->tail = NULL;
  91
  92         if (elem != NULL)
  93                 q->count--;
  94
  95         return elem;
  96 }
  97
  98
  99 void *
 100 queue_peek(queue *q)
 101 {
 102         return q->head;
 103 }
 104
 105
 106 //      #pragma mark -
 107 /* fixed queue stuff */
 108
 109
 110 int
 111 fixed_queue_init(fixed_queue *q, int size)
 112 {
 113         if (size <= 0)
 114                 return EINVAL;
 115
 116         q->table = (void**)malloc(size * sizeof(void *));
 117         if (!q->table)
 118                 return ENOMEM;
 119         q->head = 0;
 120         q->tail = 0;
 121         q->count = 0;
 122         q->size = size;
 123
 124         return 0;
 125 }
 126
 127
 128 void
 129 fixed_queue_destroy(fixed_queue *q)
 130 {
 131         free(q->table);
 132 }
 133
 134
 135 int
 136 fixed_queue_enqueue(fixed_queue *q, void *e)
 137 {
 138         if (q->count == q->size)
 139                 return ENOMEM;
 140
 141         q->table[q->head++] = e;
 142         if (q->head >= q->size)
 143                 q->head = 0;
 144         q->count++;
 145
 146         return 0;
 147 }
 148
 149
 150 void *
 151 fixed_queue_dequeue(fixed_queue *q)
 152 {
 153         void *e;
 154
 155         if (q->count <= 0)
 156                 return NULL;
 157
 158         e = q->table[q->tail++];
 159         if (q->tail >= q->size)
 160                 q->tail = 0;
 161         q->count--;
 162
 163         return e;
 164 }
 165
 166
 167 void *
 168 fixed_queue_peek(fixed_queue *q)
 169 {
 170         if (q->count <= 0)
 171                 return NULL;
 172
 173         return q->table[q->tail];
 174 }
 175
 176