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 13typedef struct queue_element { 14 void *next; 15} queue_element; 16 17typedef struct queue_typed { 18 queue_element *head; 19 queue_element *tail; 20 int count; 21} queue_typed; 22 23 24int 25queue_init(queue *q) 26{ 27 q->head = q->tail = NULL; 28 q->count = 0; 29 return 0; 30} 31 32 33int 34queue_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 61int 62queue_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 80void * 81queue_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 99void * 100queue_peek(queue *q) 101{ 102 return q->head; 103} 104 105 106// #pragma mark - 107/* fixed queue stuff */ 108 109 110int 111fixed_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 128void 129fixed_queue_destroy(fixed_queue *q) 130{ 131 free(q->table); 132} 133 134 135int 136fixed_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 150void * 151fixed_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 167void * 168fixed_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