Mercurial > almixer_isolated

comparison CircularQueue.h @ 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
21 #ifndef C_CIRCULAR_QUEUE_H
22 #define C_CIRCULAR_QUEUE_H
23
24 /* Set up for C function definitions, even when using C++ */
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28
29 /**
30 * @file
31 * This is a C-based Circular queue class.
32 * This class provides very simple circular queue functionality,
33 * with an API similar to the C++ STL queue class.
34 * Currently, a queue cannot be resized.
35 * Because C doesn't do templates and I really don't want
36 * to write my own polymorphism, you must select the proper queue
37 * for your data types.
38 * I currently provide an unisigned int version
39 * and a void* version. The void* version will let you use any type,
40 * but remember that you are responsible for casting and maintaining
41 * your own type safety. I have found the unsigned int version to be
42 * very useful because if you have a map somewhere that associates
43 * unique identifier numbers to data (e.g. OpenGL displaylists/textures),
44 * then you can just deal with the id numbers and don't have to deal with
45 * the casting and typesafety issues. I recommend you don't overlook the
46 * usefulness of this version.
47 *
48 * @warning Do not mix the CircularQueues created from the different versions.
49 * They are incompatible. Use only CircularQueueUnsignedInt objects with
50 * CircularQueueUnsignedInt_* functions, etc.
51 *
52 * Example Usage:
53 * @code
54 * CircularQueueUnsignedInt* myqueue;
55 * unsigned int ret_val;
56 *
57 * myqueue = CircularQueueUnsignedInt_CreateQueue(3);
58 * if(NULL == myqueue)
59 * {
60 * fprintf(stderr, "Error, could not create queue\n");
61 * return 0;
62 * }
63 *
64 *
65 * ret_val = CircularQueueUnsignedInt_PushBack(myqueue, 1);
66 * ret_val = CircularQueueUnsignedInt_PushBack(myqueue, 2);
67 * ret_val = CircularQueueUnsignedInt_PushBack(myqueue, 3);
68 * if(0 == ret_val)
69 * {
70 * fprintf(stderr, "Error, Could not pushback\n");
71 * exit(1);
72 * }
73 *
74 * ret_val = CircularQueueUnsignedInt_PopBack(myqueue);
75 * if(0 == ret_val)
76 * {
77 * fprintf(stderr, "Error, Could not popback\n");
78 * exit(2);
79 * }
80 *
81 * fprintf(stderr, "Testing queue, should have 1,2\n");
82 * CircularQueueUnsignedInt_Print(myqueue);
83 *
84 * ret_val = CircularQueueUnsignedInt_PushFront(myqueue, 4);
85 * if(0 == ret_val)
86 * {
87 * fprintf(stderr, "Error, Could not pushfront\n");
88 * exit(1);
89 * }
90 * fprintf(stderr, "Testing queue, should have 4,1,2\n");
91 * CircularQueueUnsignedInt_Print(myqueue);
92 *
93 * @endcode
94 */
95
96 /**
97 * This is the essentially the CircularQueue object.
98 * This contains all the data associated with a CircularQueue instance.
99 * This version is for unsigned int data types. In the future, I suppose
100 * I could add a void* data type at the very least and maybe some
101 * other data types.
102 * This should be considered an opaque data type.
103 */
104 typedef struct
105 {
106 unsigned int maxSize; /**< Max size of the queue. */
107 unsigned int currentSize; /**< Current number of entries in the queue. */
108 unsigned int headIndex; /**< The index of where the current head is. */
109 unsigned int tailIndex; /**< The index of where the current tail is. */
110 unsigned int* internalQueue; /**< The array representing the queue. */
111 } CircularQueueUnsignedInt;
112
113 /**
114 * This creates a new CircularQueue (for unsigned int) instance.
115 * This will create a new circular queue instance which holds
116 * unsigned int's in its queue.
117 *
118 * @note This implementation does not allow a circular queue to be resized.
119 *
120 * @param max_size This specifies the maximum number of elements the circular
121 * can hold.
122 *
123 * @return Returns a pointer to a CircularQueue which is the
124 * instance variable (if successful) or NULL on failure.
125 *
126 * @see CircularQueueUnsignedInt_FreeQueue
127 */
128 CircularQueueUnsignedInt* CircularQueueUnsignedInt_CreateQueue(unsigned int max_size);
129
130 /**
131 * This destroys a CircularQueue instance.
132 * This will destroy the memory associated with the circular queue instance.
133 * Whenever you create a CircularQueue instance, you should always to
134 * remember to balance it with a FreeQueue.
135 *
136 * @param queue The pointer to the CircularQueue instance.
137 *
138 * @see CircularQueueUnsignedInt_CreateQueue
139 */
140 void CircularQueueUnsignedInt_FreeQueue(CircularQueueUnsignedInt* queue);
141
142 /**
143 * This pushes a new value into the back of the queue.
144 * If the queue is full, the function will fail and return 0.
145 *
146 * @param queue The pointer to the CircularQueue instance.
147 * @param value The value you want to push into the queue.
148 *
149 * @return Returns 1 on success, or 0 on failure.
150 */
151 unsigned int CircularQueueUnsignedInt_PushBack(CircularQueueUnsignedInt* queue, unsigned int value);
152
153 /**
154 * This pushes a new value into the front of the queue.
155 * If the queue is full, the function will fail and return 0.
156 *
157 * @param queue The pointer to the CircularQueue instance.
158 * @param value The value you want to push into the queue.
159 *
160 * @return Returns 1 on success, or 0 on failure.
161 */
162 unsigned int CircularQueueUnsignedInt_PushFront(CircularQueueUnsignedInt* queue, unsigned int value);
163
164 /**
165 * This removes the value at the front of the queue.
166 * If the queue is empty, the function will return 0.
167 * Note that this function does not return the value popped, but
168 * an error flag. If you need the value, you must call Front()
169 * to retrieve the value before popping it.
170 *
171 * @param queue The pointer to the CircularQueue instance.
172 *
173 * @return Returns 1 on success, or 0 on failure.
174 * @see CircularQueueUnsignedInt_Front
175 */
176 unsigned int CircularQueueUnsignedInt_PopFront(CircularQueueUnsignedInt* queue);
177
178 /**
179 * This removes the value at the back of the queue.
180 * If the queue is empty, the function will return 0.
181 * Note that this function does not return the value popped, but
182 * an error flag. If you need the value, you must call Back()
183 * to retrieve the value before popping it.
184 *
185 * @param queue The pointer to the CircularQueue instance.
186 *
187 * @return Returns 1 on success, or 0 on failure.
188 * @see CircularQueueUnsignedInt_Back
189 */
190 unsigned int CircularQueueUnsignedInt_PopBack(CircularQueueUnsignedInt* queue);
191
192 /**
193 * This gets the value at the front of the queue.
194 * If the queue is empty, the value returned will be 0.
195 * Because this 0 return value is ambiguous because it could also could
196 * be a legitimate value in the queue, if you need more robust error
197 * checking for if the queue is empty, you should get the size of the
198 * queue using the Size() function.
199 *
200 * @param queue The pointer to the CircularQueue instance.
201 *
202 * @return Returns the value stored at the queue or 0 if the queue is empty
203 * (or if there is an error).
204 *
205 * @see CircularQueueUnsignedInt_Size
206 */
207 unsigned int CircularQueueUnsignedInt_Front(CircularQueueUnsignedInt* queue);
208
209 /**
210 * This gets the value at the back of the queue.
211 * If the queue is empty, the value returned will be 0.
212 * Because this 0 return value is ambiguous because it could also could
213 * be a legitimate value in the queue, if you need more robust error
214 * checking for if the queue is empty, you should get the size of the
215 * queue using the Size() function.
216 *
217 * @param queue The pointer to the CircularQueue instance.
218 *
219 * @return Returns the value stored at the queue or 0 if the queue is empty
220 * (or 0 if there is an error).
221 *
222 * @see CircularQueueUnsignedInt_Size
223 */
224 unsigned int CircularQueueUnsignedInt_Back(CircularQueueUnsignedInt* queue);
225
226 /**
227 * This gets the current number of entries that are in the queue.
228 * This is number is not to be confused with the MaxSize.
229 *
230 * @param queue The pointer to the CircularQueue instance.
231 *
232 * @return Returns the number of entries currently in queue, or 0 if
233 * there is an error.
234 *
235 */
236 unsigned int CircularQueueUnsignedInt_Size(CircularQueueUnsignedInt* queue);
237
238 /**
239 * This gets the maximum number of entries that are allowed in the queue at
240 * a given time.
241 * This is the number that you used in the CreateQueue function.
242 *
243 * @param queue The pointer to the CircularQueue instance.
244 *
245 * @return Returns the maximum number of entries allowed in the queue.
246 */
247 unsigned int CircularQueueUnsignedInt_MaxSize(CircularQueueUnsignedInt* queue);
248 /**
249 * This empties the entire queue.
250 * This will remove all entries that are in the queue.
251 * This does not destroy any memory. Use FreeQueue() to actually destroy
252 * the queue.
253 *
254 * @param queue The pointer to the CircularQueue instance.
255 */
256 void CircularQueueUnsignedInt_Clear(CircularQueueUnsignedInt* queue);
257
258 /**
259 * This is a debugging function that will print all the elements in the
260 * queue to stderr.
261 * This function is provided as convenience, but should not be considered
262 * as part of the standard API. Treat this function as deprecated
263 * as it's implementation may change or be removed entirely.
264 *
265 * @param queue The pointer to the CircularQueue instance.
266 */
267 void CircularQueueUnsignedInt_Print(CircularQueueUnsignedInt* queue);
268
269
270 /**
271 * This is the essentially the CircularQueue object.
272 * This contains all the data associated with a CircularQueue instance.
273 * This version is for unsigned int data types. In the future, I suppose
274 * I could add a void* data type at the very least and maybe some
275 * other data types.
276 * This should be considered an opaque data type.
277 */
278 typedef struct
279 {
280 unsigned int maxSize; /**< Max size of the queue. */
281 unsigned int currentSize; /**< Current number of entries in the queue. */
282 unsigned int headIndex; /**< The index of where the current head is. */
283 unsigned int tailIndex; /**< The index of where the current tail is. */
284 void** internalQueue; /**< The array representing the queue. */
285 } CircularQueueVoid;
286
287 /**
288 * This creates a new CircularQueue (for void* ) instance.
289 * This will create a new circular queue instance which holds
290 * unsigned int's in its queue.
291 *
292 * @note This implementation does not allow a circular queue to be resized.
293 *
294 * @param max_size This specifies the maximum number of elements the circular
295 * can hold.
296 *
297 * @return Returns a pointer to a CircularQueue which is the
298 * instance variable (if successful) or NULL on failure.
299 *
300 * @see CircularQueueVoid_FreeQueue
301 */
302 CircularQueueVoid* CircularQueueVoid_CreateQueue(unsigned int max_size);
303
304 /**
305 * This destroys a CircularQueue instance.
306 * This will destroy the memory associated with the circular queue instance.
307 * Whenever you create a CircularQueue instance, you should always to
308 * remember to balance it with a FreeQueue.
309 *
310 * @param queue The pointer to the CircularQueue instance.
311 *
312 * @see CircularQueueVoid_CreateQueue
313 */
314 void CircularQueueVoid_FreeQueue(CircularQueueVoid* queue);
315
316 /**
317 * This pushes a new value into the back of the queue.
318 * If the queue is full, the function will fail and return 0.
319 *
320 * @param queue The pointer to the CircularQueue instance.
321 * @param value The value you want to push into the queue.
322 *
323 * @return Returns 1 on success, or 0 on failure.
324 */
325 unsigned int CircularQueueVoid_PushBack(CircularQueueVoid* queue, void* value);
326
327 /**
328 * This pushes a new value into the front of the queue.
329 * If the queue is full, the function will fail and return 0.
330 *
331 * @param queue The pointer to the CircularQueue instance.
332 * @param value The value you want to push into the queue.
333 *
334 * @return Returns 1 on success, or 0 on failure.
335 */
336 unsigned int CircularQueueVoid_PushFront(CircularQueueVoid* queue, void* value);
337
338 /**
339 * This removes the value at the front of the queue.
340 * If the queue is empty, the function will return 0.
341 * Note that this function does not return the value popped, but
342 * an error flag. If you need the value, you must call Front()
343 * to retrieve the value before popping it.
344 *
345 * @param queue The pointer to the CircularQueue instance.
346 *
347 * @return Returns 1 on success, or 0 on failure.
348 * @see CircularQueueVoid_Front
349 */
350 unsigned int CircularQueueVoid_PopFront(CircularQueueVoid* queue);
351
352 /**
353 * This removes the value at the back of the queue.
354 * If the queue is empty, the function will return 0.
355 * Note that this function does not return the value popped, but
356 * an error flag. If you need the value, you must call Back()
357 * to retrieve the value before popping it.
358 *
359 * @param queue The pointer to the CircularQueue instance.
360 *
361 * @return Returns 1 on success, or 0 on failure.
362 * @see CircularQueueVoid_Back
363 */
364 unsigned int CircularQueueVoid_PopBack(CircularQueueVoid* queue);
365
366 /**
367 * This gets the value at the front of the queue.
368 * If the queue is empty, the value returned will be 0.
369 * Because this 0 return value is ambiguous because it could also could
370 * be a legitimate value in the queue, if you need more robust error
371 * checking for if the queue is empty, you should get the size of the
372 * queue using the Size() function.
373 *
374 * @param queue The pointer to the CircularQueue instance.
375 *
376 * @return Returns the value stored at the queue or 0 if the queue is empty
377 * (or if there is an error).
378 *
379 * @see CircularQueueVoid_Size
380 */
381 void* CircularQueueVoid_Front(CircularQueueVoid* queue);
382
383 /**
384 * This gets the value at the back of the queue.
385 * If the queue is empty, the value returned will be 0.
386 * Because this 0 return value is ambiguous because it could also could
387 * be a legitimate value in the queue, if you need more robust error
388 * checking for if the queue is empty, you should get the size of the
389 * queue using the Size() function.
390 *
391 * @param queue The pointer to the CircularQueue instance.
392 *
393 * @return Returns the value stored at the queue or 0 if the queue is empty
394 * (or 0 if there is an error).
395 *
396 * @see CircularQueueVoid_Size
397 */
398 void* CircularQueueVoid_Back(CircularQueueVoid* queue);
399
400 /**
401 * This gets the current number of entries that are in the queue.
402 * This is number is not to be confused with the MaxSize.
403 *
404 * @param queue The pointer to the CircularQueue instance.
405 *
406 * @return Returns the number of entries currently in queue, or 0 if
407 * there is an error.
408 *
409 */
410 unsigned int CircularQueueVoid_Size(CircularQueueVoid* queue);
411
412 /**
413 * This gets the maximum number of entries that are allowed in the queue at
414 * a given time.
415 * This is the number that you used in the CreateQueue function.
416 *
417 * @param queue The pointer to the CircularQueue instance.
418 *
419 * @return Returns the maximum number of entries allowed in the queue.
420 */
421 unsigned int CircularQueueVoid_MaxSize(CircularQueueVoid* queue);
422 /**
423 * This empties the entire queue.
424 * This will remove all entries that are in the queue.
425 * This does not destroy any memory. Use FreeQueue() to actually destroy
426 * the queue.
427 *
428 * @param queue The pointer to the CircularQueue instance.
429 */
430 void CircularQueueVoid_Clear(CircularQueueVoid* queue);
431
432 /* Not implemented for void* */
433 /*
434 void CircularQueueVoid_Print(CircularQueueVoid* queue);
435 */
436
437
438
439
440 /* Ends C function definitions when using C++ */
441 #ifdef __cplusplus
442 }
443 #endif
444
445
446
447 #endif /* C_CIRCULAR_QUEUE_H */
448