]> wirehaze git hosting - ppos.git/blob - ppos/lib/queue.c

wirehaze git hosting

projects / ppos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
tasks implementation (ongoing)
[ppos.git] / ppos / lib / queue.c
1 // PingPongOS - PingPong Operating System
2 // Prof. Carlos A. Maziero, DINF UFPR
3 // Versão 2.0 -- Junho de 2025
4
5 // Implementação do TAD fila genérica
6
7 /* PEDRO HENRIQUE FRIEDRICH RAMOS : GRR20243133 */
8
9 #include "queue.h"
10 #include <stdio.h>
11 #include <stdlib.h>
12
13 /* ------------------------------------------------------------------------- */
14 /* Data types ------------------------------------------------------------- */
15
16 /* Queue element. */
17 struct node_t
18 {
19 void *item; /* User provided opaque pointer. */
20 struct node_t *next; /* Pointer to the next node in the queue. */
21 };
22
23 /* ------------------------------------------------------------------------- */
24
25 /* Queue. */
26 struct queue_t
27 {
28 struct node_t *head; /* Pointer to the first node in the queue. */
29 struct node_t *tail; /* Pointer to the last node in the queue. */
30 struct node_t *iterator; /* Pointer to the current node. */
31 int size; /* Number of nodes in the queue. */
32 };
33
34 /* ------------------------------------------------------------------------- */
35 /* Internal functions ----------------------------------------------------- */
36
37 static inline struct node_t *
38 node_create (void)
39 {
40 return calloc (1, sizeof (struct node_t));
41 }
42
43 /* ------------------------------------------------------------------------- */
44
45 static inline void
46 node_destroy (struct node_t *node)
47 {
48 free (node);
49 }
50
51 /* ------------------------------------------------------------------------- */
52 /* Exported functions ----------------------------------------------------- */
53
54 struct queue_t *
55 queue_create (void)
56 {
57 return calloc (1, sizeof (struct queue_t));
58 }
59
60 /* ------------------------------------------------------------------------- */
61
62 int
63 queue_destroy (struct queue_t *queue)
64 {
65 struct node_t *n, *next;
66
67 if (!queue)
68 return ERROR;
69
70 n = queue->head;
71
72 while (n)
73 {
74 /* Save the next node pointer before destroying the current node. */
75 next = n->next;
76 node_destroy (n);
77 n = next;
78 }
79
80 free (queue);
81 return NOERROR;
82 }
83
84 /* ------------------------------------------------------------------------- */
85
86 int
87 queue_add (struct queue_t *queue, void *item)
88 {
89 struct node_t *n;
90
91 if (!queue || !item)
92 return ERROR;
93
94 if (!(n = node_create ()))
95 return ERROR;
96
97 n->item = item;
98 ++queue->size;
99
100 /* Empty queue, this is the first element. */
101 if (!queue->head)
102 {
103 queue->head = queue->tail = queue->iterator = n;
104 return NOERROR;
105 }
106
107 /* Append to queue. */
108 queue->tail = queue->tail->next = n;
109 return NOERROR;
110 }
111
112 /* ------------------------------------------------------------------------- */
113
114 int
115 queue_del (struct queue_t *queue, void *item)
116 {
117 struct node_t *n, *prev;
118
119 if (!queue || !item)
120 return ERROR;
121
122 if (!(n = queue->head)) /* Queue is empty. */
123 return ERROR;
124
125 prev = NULL;
126
127 while (n && n->item != item)
128 {
129 prev = n;
130 n = n->next;
131 }
132
133 if (!n) /* Not found. */
134 return ERROR;
135
136 if (prev)
137 prev->next = n->next;
138
139 /* Update boundaries accordingly. */
140 if (queue->head == n)
141 queue->head = n->next;
142
143 if (queue->tail == n)
144 queue->tail = prev;
145
146 /* Advance the iterator if it points to the removed node. */
147 if (queue->iterator == n)
148 queue->iterator = n->next;
149
150 --queue->size;
151 node_destroy (n);
152 return NOERROR;
153 }
154
155 /* ------------------------------------------------------------------------- */
156
157 bool
158 queue_has (struct queue_t *queue, void *item)
159 {
160 struct node_t *n;
161
162 if (!queue || !item)
163 return false;
164
165 if (!(n = queue->head))
166 return false;
167
168 /* Traverse until the item is found or the end is reached. */
169 while (n->item != item && (n = n->next))
170 ;
171
172 return n != NULL;
173 }
174
175 /* ------------------------------------------------------------------------- */
176
177 int
178 queue_size (struct queue_t *queue)
179 {
180 if (!queue)
181 return ERROR;
182
183 return queue->size;
184 }
185
186 /* ------------------------------------------------------------------------- */
187
188 void *
189 queue_head (struct queue_t *queue)
190 {
191 if (!queue || !queue->head)
192 return NULL;
193
194 queue->iterator = queue->head;
195
196 return queue->head->item;
197 }
198
199 /* ------------------------------------------------------------------------- */
200
201 void *
202 queue_next (struct queue_t *queue)
203 {
204 if (!queue || !queue->iterator)
205 return NULL;
206
207 queue->iterator = queue->iterator->next;
208
209 if (!queue->iterator)
210 return NULL;
211
212 return queue->iterator->item;
213 }
214
215 /* ------------------------------------------------------------------------- */
216
217 void *
218 queue_item (struct queue_t *queue)
219 {
220 if (!queue || !queue->iterator)
221 return NULL;
222
223 return queue->iterator->item;
224 }
225
226 /* ------------------------------------------------------------------------- */
227
228 void
229 queue_print (char *name, struct queue_t *queue, void (func) (void *))
230 {
231 struct node_t *n;
232
233 if (!name)
234 return;
235
236 printf ("%s: ", name);
237
238 if (!queue)
239 {
240 puts ("undef");
241 return;
242 }
243
244 fputs ("[ ", stdout);
245
246 for (n = queue->head; n; n = n->next)
247 {
248 if (func)
249 func (n->item);
250
251 else
252 fputs ("undef", stdout);
253
254 putchar (' ');
255 }
256
257 printf ("] (%d items)\n", queue->size);
258 }
259
260 /* ------------------------------------------------------------------------- */