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
queue_init(queue * q)25 queue_init(queue *q)
26 {
27 q->head = q->tail = NULL;
28 q->count = 0;
29 return 0;
30 }
31
32
33 int
queue_remove_item(queue * _q,void * e)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
queue_enqueue(queue * _q,void * e)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 *
queue_dequeue(queue * _q)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 *
queue_peek(queue * q)100 queue_peek(queue *q)
101 {
102 return q->head;
103 }
104
105
106 // #pragma mark -
107 /* fixed queue stuff */
108
109
110 int
fixed_queue_init(fixed_queue * q,int size)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
fixed_queue_destroy(fixed_queue * q)129 fixed_queue_destroy(fixed_queue *q)
130 {
131 free(q->table);
132 }
133
134
135 int
fixed_queue_enqueue(fixed_queue * q,void * e)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 *
fixed_queue_dequeue(fixed_queue * q)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 *
fixed_queue_peek(fixed_queue * q)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