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 177