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