Mercurial > almixer_isolated

comparison CircularQueue.c @ 0:01e39f9f58d5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Bitkeeper era.
author Eric Wing <ewing . public |-at-| gmail . com>
date Wed, 27 Oct 2010 16:50:19 -0700
parents
children a8a8fe374984
comparison
equal deleted inserted replaced
-1:000000000000 0:01e39f9f58d5
1 /*
2 CircularQueue
3 Copyright (C) 2002 Eric Wing
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Library General Public
7 License as published by the Free Software Foundation; either
8 version 2 of the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Library General Public License for more details.
14
15 You should have received a copy of the GNU Library General Public
16 License along with this library; if not, write to the Free
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 */
19
20 #include "CircularQueue.h"
21 #include <stddef.h> /* for NULL */
22 #include <stdlib.h> /* for malloc/free */
23 #include <stdio.h> /* for debugging */
24
25 CircularQueueUnsignedInt* CircularQueueUnsignedInt_CreateQueue(unsigned int max_size)
26 {
27 CircularQueueUnsignedInt* ret_ptr;
28 if(max_size < 1)
29 {
30 return NULL;
31 }
32 ret_ptr = (CircularQueueUnsignedInt*)malloc(sizeof(CircularQueueUnsignedInt));
33 if(NULL == ret_ptr)
34 {
35 /* Out of memory */
36 return NULL;
37 }
38 ret_ptr->internalQueue = (unsigned int*)malloc(sizeof(unsigned int) * max_size);
39 if(NULL == ret_ptr->internalQueue)
40 {
41 /* Out of memory */
42 free(ret_ptr);
43 return NULL;
44 }
45 ret_ptr->maxSize = max_size;
46 ret_ptr->currentSize = 0;
47 ret_ptr->headIndex = 0;
48 ret_ptr->tailIndex = 0;
49
50 return ret_ptr;
51 }
52
53 void CircularQueueUnsignedInt_FreeQueue(CircularQueueUnsignedInt* queue)
54 {
55 if(NULL == queue)
56 {
57 return;
58 }
59
60 free(queue->internalQueue);
61 free(queue);
62 }
63
64 /**
65 * Returns 1 if successful, 0 if failure.
66 */
67 unsigned int CircularQueueUnsignedInt_PushBack(CircularQueueUnsignedInt* queue, unsigned int value)
68 {
69 unsigned int temp_index;
70 if(NULL == queue)
71 {
72 return 0;
73 }
74 if(queue->currentSize >= queue->maxSize)
75 {
76 return 0;
77 }
78 temp_index = queue->tailIndex + 1;
79 if(temp_index >= queue->maxSize)
80 {
81 /* need to wrap tail index around */
82 temp_index = 0;
83 }
84 /* So with my implementation, the tail index actually points
85 * to the slot right after the last value.
86 * So we will enter the value in the current tail, and then increment
87 * the tail.
88 * Note that in a full queue, the head and tail will be the same (I think).
89 */
90 queue->internalQueue[queue->tailIndex] = value;
91 queue->tailIndex = temp_index;
92 queue->currentSize++;
93
94 return 1;
95 }
96
97 /**
98 * Returns 1 if successful, 0 if failure.
99 */
100 unsigned int CircularQueueUnsignedInt_PushFront(CircularQueueUnsignedInt* queue, unsigned int value)
101 {
102 unsigned int temp_index;
103 if(NULL == queue)
104 {
105 return 0;
106 }
107 if(queue->currentSize >= queue->maxSize)
108 {
109 return 0;
110 }
111
112 /* This check is needed to prevent the unsigned int from overflowing. */
113 if(0 == queue->headIndex)
114 {
115 /* Need to wrap head index around */
116 temp_index = queue->maxSize - 1;
117 }
118 else
119 {
120 temp_index = queue->headIndex - 1;
121 }
122 /* So unlike the tail, the head index actually points to the element
123 * at the head, and not an element before (or after) the head.
124 */
125 queue->internalQueue[temp_index] = value;
126 queue->headIndex = temp_index;
127 queue->currentSize++;
128 return 1;
129 }
130
131 unsigned int CircularQueueUnsignedInt_PopFront(CircularQueueUnsignedInt* queue)
132 {
133 unsigned int temp_index;
134 if(NULL == queue)
135 {
136 return 0;
137 }
138 if(queue->currentSize == 0)
139 {
140 return 0;
141 }
142 temp_index = queue->headIndex + 1;
143 if(temp_index >= queue->maxSize)
144 {
145 /* need to wrap tail index around */
146 temp_index = 0;
147 }
148 queue->headIndex = temp_index;
149 queue->currentSize--;
150 return 1;
151 }
152
153
154 unsigned int CircularQueueUnsignedInt_PopBack(CircularQueueUnsignedInt* queue)
155 {
156 unsigned int temp_index;
157 if(NULL == queue)
158 {
159 return 0;
160 }
161 if(queue->currentSize == 0)
162 {
163 return 0;
164 }
165
166 /* This check is needed to prevent the unsigned int from overflowing. */
167 if(0 == queue->tailIndex)
168 {
169 temp_index = queue->maxSize - 1;
170 }
171 else
172 {
173 temp_index = queue->tailIndex - 1;
174 }
175
176 queue->tailIndex = temp_index;
177 queue->currentSize--;
178 return 1;
179 }
180
181 unsigned int CircularQueueUnsignedInt_Front(CircularQueueUnsignedInt* queue)
182 {
183 if(NULL == queue)
184 {
185 return 0;
186 }
187 if(0 == queue->currentSize)
188 {
189 return 0;
190 }
191 return queue->internalQueue[queue->headIndex];
192 }
193
194
195 unsigned int CircularQueueUnsignedInt_Back(CircularQueueUnsignedInt* queue)
196 {
197 unsigned int temp_index;
198 if(NULL == queue)
199 {
200 return 0;
201 }
202 if(0 == queue->currentSize)
203 {
204 return 0;
205 }
206 if(0 == queue->tailIndex)
207 {
208 /* need to wrap tail index around */
209 temp_index = queue->maxSize-1;
210 }
211 else
212 {
213 temp_index = queue->tailIndex-1;
214 }
215
216 return queue->internalQueue[temp_index];
217 }
218
219 unsigned int CircularQueueUnsignedInt_Size(CircularQueueUnsignedInt* queue)
220 {
221 if(NULL == queue)
222 {
223 return 0;
224 }
225 return queue->currentSize;
226 }
227
228 unsigned int CircularQueueUnsignedInt_MaxSize(CircularQueueUnsignedInt* queue)
229 {
230 if(NULL == queue)
231 {
232 return 0;
233 }
234 return queue->maxSize;
235 }
236
237 void CircularQueueUnsignedInt_Clear(CircularQueueUnsignedInt* queue)
238 {
239 if(NULL == queue)
240 {
241 return;
242 }
243
244 queue->currentSize = 0;
245 queue->headIndex = 0;
246 queue->tailIndex = 0;
247 }
248
249 void CircularQueueUnsignedInt_Print(CircularQueueUnsignedInt* queue)
250 {
251 unsigned int i;
252 unsigned int count;
253 if(NULL == queue)
254 {
255 return;
256 }
257 fprintf(stderr, "Queue: ");
258 for(count=0, i=queue->headIndex; count<queue->currentSize; count++, i++)
259 {
260 if(i >= queue->maxSize)
261 {
262 i=0;
263 }
264 fprintf(stderr, "%d ", queue->internalQueue[i]);
265 }
266 fprintf(stderr, "\n");
267 }
268
269 /*
270 * Implementation for void* version starts here.
271 */
272
273 CircularQueueVoid* CircularQueueVoid_CreateQueue(unsigned int max_size)
274 {
275 CircularQueueVoid* ret_ptr;
276 if(max_size < 1)
277 {
278 return NULL;
279 }
280 ret_ptr = (CircularQueueVoid*)malloc(sizeof(CircularQueueVoid));
281 if(NULL == ret_ptr)
282 {
283 /* Out of memory */
284 return NULL;
285 }
286 ret_ptr->internalQueue = (void**)malloc(sizeof(void*) * max_size);
287 if(NULL == ret_ptr->internalQueue)
288 {
289 /* Out of memory */
290 free(ret_ptr);
291 return NULL;
292 }
293 ret_ptr->maxSize = max_size;
294 ret_ptr->currentSize = 0;
295 ret_ptr->headIndex = 0;
296 ret_ptr->tailIndex = 0;
297
298 return ret_ptr;
299 }
300
301 void CircularQueueVoid_FreeQueue(CircularQueueVoid* queue)
302 {
303 if(NULL == queue)
304 {
305 return;
306 }
307
308 free(queue->internalQueue);
309 free(queue);
310 }
311
312 /**
313 * Returns 1 if successful, 0 if failure.
314 */
315 unsigned int CircularQueueVoid_PushBack(CircularQueueVoid* queue, void* value)
316 {
317 unsigned int temp_index;
318 if(NULL == queue)
319 {
320 return 0;
321 }
322 if(queue->currentSize >= queue->maxSize)
323 {
324 return 0;
325 }
326 temp_index = queue->tailIndex + 1;
327 if(temp_index >= queue->maxSize)
328 {
329 /* need to wrap tail index around */
330 temp_index = 0;
331 }
332 queue->internalQueue[queue->tailIndex] = value;
333 queue->tailIndex = temp_index;
334 queue->currentSize++;
335
336 return 1;
337 }
338
339 /**
340 * Returns 1 if successful, 0 if failure.
341 */
342 unsigned int CircularQueueVoid_PushFront(CircularQueueVoid* queue, void* value)
343 {
344 unsigned int temp_index;
345 if(NULL == queue)
346 {
347 return 0;
348 }
349 if(queue->currentSize >= queue->maxSize)
350 {
351 return 0;
352 }
353
354 /* This check is needed to prevent the unsigned int from overflowing. */
355 if(0 == queue->headIndex)
356 {
357 /* Need to wrap head index around */
358 temp_index = queue->maxSize - 1;
359 }
360 else
361 {
362 temp_index = queue->headIndex - 1;
363 }
364 queue->internalQueue[temp_index] = value;
365 queue->headIndex = temp_index;
366 queue->currentSize++;
367 return 1;
368 }
369
370 unsigned int CircularQueueVoid_PopFront(CircularQueueVoid* queue)
371 {
372 unsigned int temp_index;
373 if(NULL == queue)
374 {
375 return 0;
376 }
377 if(queue->currentSize == 0)
378 {
379 return 0;
380 }
381 temp_index = queue->headIndex + 1;
382 if(temp_index >= queue->maxSize)
383 {
384 /* need to wrap tail index around */
385 temp_index = 0;
386 }
387 queue->headIndex = temp_index;
388 queue->currentSize--;
389 return 1;
390 }
391
392
393 unsigned int CircularQueueVoid_PopBack(CircularQueueVoid* queue)
394 {
395 unsigned int temp_index;
396 if(NULL == queue)
397 {
398 return 0;
399 }
400 if(queue->currentSize == 0)
401 {
402 return 0;
403 }
404
405 /* This check is needed to prevent the unsigned int from overflowing. */
406 if(0 == queue->tailIndex)
407 {
408 temp_index = queue->maxSize - 1;
409 }
410 else
411 {
412 temp_index = queue->tailIndex - 1;
413 }
414
415 queue->tailIndex = temp_index;
416 queue->currentSize--;
417 return 1;
418 }
419
420 void* CircularQueueVoid_Front(CircularQueueVoid* queue)
421 {
422 if(NULL == queue)
423 {
424 return 0;
425 }
426 if(0 == queue->currentSize)
427 {
428 return 0;
429 }
430 return queue->internalQueue[queue->headIndex];
431 }
432
433
434 void* CircularQueueVoid_Back(CircularQueueVoid* queue)
435 {
436 unsigned int temp_index;
437 if(NULL == queue)
438 {
439 return 0;
440 }
441 if(0 == queue->currentSize)
442 {
443 return 0;
444 }
445 if(0 == queue->tailIndex)
446 {
447 /* need to wrap tail index around */
448 temp_index = queue->maxSize-1;
449 }
450 else
451 {
452 temp_index = queue->tailIndex-1;
453 }
454
455 return queue->internalQueue[temp_index];
456 }
457
458 unsigned int CircularQueueVoid_Size(CircularQueueVoid* queue)
459 {
460 if(NULL == queue)
461 {
462 return 0;
463 }
464 return queue->currentSize;
465 }
466
467 unsigned int CircularQueueVoid_MaxSize(CircularQueueVoid* queue)
468 {
469 if(NULL == queue)
470 {
471 return 0;
472 }
473 return queue->maxSize;
474 }
475
476 void CircularQueueVoid_Clear(CircularQueueVoid* queue)
477 {
478 if(NULL == queue)
479 {
480 return;
481 }
482
483 queue->currentSize = 0;
484 queue->headIndex = 0;
485 queue->tailIndex = 0;
486 }
487
488 /* Not implemented for void* */
489 /*
490 void CircularQueueVoid_Print(CircularQueueVoid* queue)
491 {
492 unsigned int i;
493 unsigned int count;
494 if(NULL == queue)
495 {
496 return;
497 }
498 fprintf(stderr, "Queue: ");
499 for(count=0, i=queue->headIndex; count<queue->currentSize; count++, i++)
500 {
501 if(i >= queue->maxSize)
502 {
503 i=0;
504 }
505 fprintf(stderr, "%d ", queue->internalQueue[i]);
506 }
507 fprintf(stderr, "\n");
508 }
509 */
510
511
512