qLibc

qqueue.c
Go to the documentation of this file.
1/******************************************************************************
2 * qLibc
3 *
4 * Copyright (c) 2010-2015 Seungyoung Kim.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 *****************************************************************************/
28
29/**
30 * @file qqueue.c Queue implementation.
31 *
32 * qqueue container is a queue implementation. It represents a
33 * first-in-first-out(FIFO). It extends qlist container that allow a
34 * linked-list to be treated as a queue.
35 *
36 * @code
37 * [Conceptional Data Structure Diagram]
38 *
39 * top bottom
40 * DATA POP <== [ A ][ B ][ C ] <== DATA PUSH
41 * (positive index) 0 1 2
42 * (negative index) -3 -2 -1
43 * @endcode
44 *
45 * @code
46 * // create queue
47 * qqueue_t *queue = qQueue();
48 *
49 * // example: integer queue
50 * queue->pushint(queue, 1);
51 * queue->pushint(queue, 2);
52 * queue->pushint(queue, 3);
53 *
54 * printf("popint(): %d\n", queue->popint(queue));
55 * printf("popint(): %d\n", queue->popint(queue));
56 * printf("popint(): %d\n", queue->popint(queue));
57 *
58 * // example: string queue
59 * queue->pushstr(queue, "A string");
60 * queue->pushstr(queue, "B string");
61 * queue->pushstr(queue, "C string");
62 *
63 * char *str = queue->popstr(queue);
64 * printf("popstr(): %s\n", str);
65 * free(str);
66 * str = queue->popstr(queue);
67 * printf("popstr(): %s\n", str);
68 * free(str);
69 * str = queue->popstr(queue);
70 * printf("popstr(): %s\n", str);
71 * free(str);
72 *
73 * // example: object queue
74 * queue->push(queue, "A object", sizeof("A object"));
75 * queue->push(queue, "B object", sizeof("B object"));
76 * queue->push(queue, "C object", sizeof("C object"));
77 *
78 * void *obj = queue->pop(queue, NULL);
79 * printf("pop(): %s\n", (char*)obj);
80 * free(obj);
81 * obj = queue->pop(queue, NULL);
82 * printf("pop(): %s\n", (char*)obj);
83 * free(obj);
84 * obj = queue->pop(queue, NULL);
85 * printf("pop(): %s\n", (char*)obj);
86 * free(obj);
87 *
88 * // release
89 * queue->free(queue);
90 *
91 * [Output]
92 * popint(): 3
93 * popint(): 2
94 * popint(): 1
95 * popstr(): C string
96 * popstr(): B string
97 * popstr(): A string
98 * pop(): C object
99 * pop(): B object
100 * pop(): A object
101 * @endcode
102 */
103
104#include <stdio.h>
105#include <stdlib.h>
106#include <stdbool.h>
107#include <string.h>
108#include <errno.h>
109#include "qinternal.h"
110#include "containers/qqueue.h"
111
112/**
113 * Create new queue container
114 *
115 * @param options combination of initialization options.
116 *
117 * @return a pointer of malloced qqueue container, otherwise returns NULL.
118 * @retval errno will be set in error condition.
119 * - ENOMEM : Memory allocation failure.
120 *
121 * @code
122 * qqueue_t *queue = qQueue(QQUEUE_THREADSAFE);
123 * @endcode
124 *
125 * @note
126 * Available options:
127 * - QQUEUE_THREADSAFE - make it thread-safe.
128 */
129qqueue_t *qqueue(int options) {
130 qqueue_t *queue = (qqueue_t *) malloc(sizeof(qqueue_t));
131 if (queue == NULL) {
132 errno = ENOMEM;
133 return NULL;
134 }
135
136 memset((void *) queue, 0, sizeof(qqueue_t));
137 queue->list = qlist(options);
138 if (queue->list == NULL) {
139 free(queue);
140 return NULL;
141 }
142
143 // methods
144 queue->setsize = qqueue_setsize;
145
146 queue->push = qqueue_push;
147 queue->pushstr = qqueue_pushstr;
148 queue->pushint = qqueue_pushint;
149
150 queue->pop = qqueue_pop;
151 queue->popstr = qqueue_popstr;
152 queue->popint = qqueue_popint;
153 queue->popat = qqueue_popat;
154
155 queue->get = qqueue_get;
156 queue->getstr = qqueue_getstr;
157 queue->getint = qqueue_getint;
158 queue->getat = qqueue_getat;
159
160 queue->size = qqueue_size;
161 queue->clear = qqueue_clear;
162 queue->debug = qqueue_debug;
163 queue->free = qqueue_free;
164
165 return queue;
166}
167
168/**
169 * qqueue->setsize(): Sets maximum number of elements allowed in this
170 * queue.
171 *
172 * @param queue qqueue container pointer.
173 * @param max maximum number of elements. 0 means no limit.
174 *
175 * @return previous maximum number.
176 */
177 size_t qqueue_setsize(qqueue_t *queue, size_t max) {
178 return queue->list->setsize(queue->list, max);
179}
180
181/**
182 * qqueue->push(): Pushes an element onto the top of this queue.
183 *
184 * @param queue qqueue container pointer.
185 * @param data a pointer which points data memory.
186 * @param size size of the data.
187 *
188 * @return true if successful, otherwise returns false.
189 * @retval errno will be set in error condition.
190 * - EINVAL : Invalid argument.
191 * - ENOBUFS : Queue full. Only happens when this queue has set to have
192 * limited number of elements)
193 * - ENOMEM : Memory allocation failure.
194 */
195 bool qqueue_push(qqueue_t *queue, const void *data, size_t size) {
196 return queue->list->addlast(queue->list, data, size);
197}
198
199/**
200 * qqueue->pushstr(): Pushes a string onto the top of this queue.
201 *
202 * @param queue qqueue container pointer.
203 * @param data a pointer which points data memory.
204 * @param size size of the data.
205 *
206 * @return true if successful, otherwise returns false.
207 * @retval errno will be set in error condition.
208 * - EINVAL : Invalid argument.
209 * - ENOBUFS : Queue full. Only happens when this queue has set to have
210 * limited number of elements.
211 * - ENOMEM : Memory allocation failure.
212 */
213 bool qqueue_pushstr(qqueue_t *queue, const char *str) {
214 if (str == NULL) {
215 errno = EINVAL;
216 return false;
217 }
218 return queue->list->addlast(queue->list, str, strlen(str) + 1);
219}
220
221/**
222 * qqueue->pushint(): Pushes a integer onto the top of this queue.
223 *
224 * @param queue qqueue container pointer.
225 * @param num integer data.
226 *
227 * @return true if successful, otherwise returns false.
228 * @retval errno will be set in error condition.
229 * - ENOBUFS : Queue full. Only happens when this queue has set to have
230 * limited number of elements.
231 * - ENOMEM : Memory allocation failure.
232 */
233 bool qqueue_pushint(qqueue_t *queue, int64_t num) {
234 return queue->list->addlast(queue->list, &num, sizeof(num));
235}
236
237/**
238 * qqueue->pop(): Removes a element at the top of this queue and returns
239 * that element.
240 *
241 * @param queue qqueue container pointer.
242 * @param size if size is not NULL, element size will be stored.
243 *
244 * @return a pointer of malloced element, otherwise returns NULL.
245 * @retval errno will be set in error condition.
246 * - ENOENT : Queue is empty.
247 * - ENOMEM : Memory allocation failure.
248 */
249 void *qqueue_pop(qqueue_t *queue, size_t *size) {
250 return queue->list->popfirst(queue->list, size);
251}
252
253/**
254 * qqueue->popstr(): Removes a element at the top of this queue and
255 * returns that element.
256 *
257 * @param queue qqueue container pointer.
258 *
259 * @return a pointer of malloced string element, otherwise returns NULL.
260 * @retval errno will be set in error condition.
261 * - ENOENT : Queue is empty.
262 * - ENOMEM : Memory allocation failure.
263 *
264 * @note
265 * The string element should be pushed through pushstr().
266 */
267 char *qqueue_popstr(qqueue_t *queue) {
268 size_t strsize;
269 char *str = queue->list->popfirst(queue->list, &strsize);
270 if (str != NULL) {
271 str[strsize - 1] = '\0'; // just to make sure
272 }
273
274 return str;
275}
276
277/**
278 * qqueue->popint(): Removes a integer at the top of this queue and
279 * returns that element.
280 *
281 * @param queue qqueue container pointer.
282 *
283 * @return an integer value, otherwise returns 0.
284 * @retval errno will be set in error condition.
285 * - ENOENT : Queue is empty.
286 * - ENOMEM : Memory allocation failure.
287 *
288 * @note
289 * The integer element should be pushed through pushint().
290 */
291int64_t qqueue_popint(qqueue_t *queue) {
292 int64_t num = 0;
293 int64_t *pnum = queue->list->popfirst(queue->list, NULL);
294 if (pnum != NULL) {
295 num = *pnum;
296 free(pnum);
297 }
298
299 return num;
300}
301
302/**
303 * qqueue->popat(): Returns and remove the element at the specified
304 * position in this queue.
305 *
306 * @param queue qqueue container pointer.
307 * @param index index at which the specified element is to be inserted
308 * @param size if size is not NULL, element size will be stored.
309 *
310 * @return a pointer of malloced element, otherwise returns NULL.
311 * @retval errno will be set in error condition.
312 * - ERANGE : Index out of range.
313 * - ENOMEM : Memory allocation failure.
314 *
315 * @note
316 * Negative index can be used for addressing a element from the bottom in this
317 * queue. For example, index -1 will always pop a element which is pushed at
318 * very last time.
319 */
320 void *qqueue_popat(qqueue_t *queue, int index, size_t *size) {
321 return queue->list->popat(queue->list, index, size);
322}
323
324/**
325 * qqueue->get(): Returns an element at the top of this queue without
326 * removing it.
327 *
328 * @param queue qqueue container pointer.
329 * @param size if size is not NULL, element size will be stored.
330 * @param newmem whether or not to allocate memory for the element.
331 *
332 * @return a pointer of malloced element, otherwise returns NULL.
333 * @retval errno will be set in error condition.
334 * - ENOENT : Queue is empty.
335 * - ENOMEM : Memory allocation failure.
336 */
337 void *qqueue_get(qqueue_t *queue, size_t *size, bool newmem) {
338 return queue->list->getfirst(queue->list, size, newmem);
339}
340
341/**
342 * qqueue->getstr(): Returns an string at the top of this queue without
343 * removing it.
344 *
345 * @param queue qqueue container pointer.
346 *
347 * @return a pointer of malloced string element, otherwise returns NULL.
348 * @retval errno will be set in error condition.
349 * - ENOENT : Queue is empty.
350 * - ENOMEM : Memory allocation failure.
351 *
352 * @note
353 * The string element should be pushed through pushstr().
354 */
355 char *qqueue_getstr(qqueue_t *queue) {
356 size_t strsize;
357 char *str = queue->list->getfirst(queue->list, &strsize, true);
358 if (str != NULL) {
359 str[strsize - 1] = '\0'; // just to make sure
360 }
361
362 return str;
363}
364
365/**
366 * qqueue->getint(): Returns an integer at the top of this queue without
367 * removing it.
368 *
369 * @param queue qqueue container pointer.
370 *
371 * @return an integer value, otherwise returns 0.
372 * @retval errno will be set in error condition.
373 * - ENOENT : Queue is empty.
374 * - ENOMEM : Memory allocation failure.
375 *
376 * @note
377 * The integer element should be pushed through pushint().
378 */
379int64_t qqueue_getint(qqueue_t *queue) {
380 int64_t num = 0;
381 int64_t *pnum = queue->list->getfirst(queue->list, NULL, true);
382 if (pnum != NULL) {
383 num = *pnum;
384 free(pnum);
385 }
386
387 return num;
388}
389
390/**
391 * qqueue->getat(): Returns an element at the specified position in this
392 * queue without removing it.
393 *
394 * @param queue qqueue container pointer.
395 * @param index index at which the specified element is to be inserted
396 * @param size if size is not NULL, element size will be stored.
397 * @param newmem whether or not to allocate memory for the element.
398 *
399 * @return a pointer of element, otherwise returns NULL.
400 * @retval errno will be set in error condition.
401 * - ERANGE : Index out of range.
402 * - ENOMEM : Memory allocation failure.
403 *
404 * @note
405 * Negative index can be used for addressing a element from the bottom in this
406 * queue. For example, index -1 will always get a element which is pushed at
407 * very last time.
408 */
409 void *qqueue_getat(qqueue_t *queue, int index, size_t *size, bool newmem) {
410 return queue->list->getat(queue->list, index, size, newmem);
411}
412
413/**
414 * qqueue->size(): Returns the number of elements in this queue.
415 *
416 * @param queue qqueue container pointer.
417 *
418 * @return the number of elements in this queue.
419 */
420 size_t qqueue_size(qqueue_t *queue) {
421 return queue->list->size(queue->list);
422}
423
424/**
425 * qqueue->clear(): Removes all of the elements from this queue.
426 *
427 * @param queue qqueue container pointer.
428 */
429 void qqueue_clear(qqueue_t *queue) {
430 queue->list->clear(queue->list);
431}
432
433/**
434 * qqueue->debug(): Print out stored elements for debugging purpose.
435 *
436 * @param queue qqueue container pointer.
437 * @param out output stream FILE descriptor such like stdout, stderr.
438 *
439 * @return true if successful, otherwise returns false.
440 */
441 bool qqueue_debug(qqueue_t *queue, FILE *out) {
442 return queue->list->debug(queue->list, out);
443}
444
445/**
446 * qqueue->free(): Free qqueue_t
447 *
448 * @param queue qqueue container pointer.
449 *
450 * @return always returns true.
451 */
452 void qqueue_free(qqueue_t *queue) {
453 queue->list->free(queue->list);
454 free(queue);
455}
qlist
qlist_t * qlist(int options)
Create new qlist_t linked-list container.
Definition qlist.c:124
qqueue_getint
int64_t qqueue_getint(qqueue_t *queue)
qqueue->getint(): Returns an integer at the top of this queue without removing it.
Definition qqueue.c:379
qqueue_get
void * qqueue_get(qqueue_t *queue, size_t *size, bool newmem)
qqueue->get(): Returns an element at the top of this queue without removing it.
Definition qqueue.c:337
qqueue_push
bool qqueue_push(qqueue_t *queue, const void *data, size_t size)
qqueue->push(): Pushes an element onto the top of this queue.
Definition qqueue.c:195
qqueue_pushstr
bool qqueue_pushstr(qqueue_t *queue, const char *str)
qqueue->pushstr(): Pushes a string onto the top of this queue.
Definition qqueue.c:213
qqueue_debug
bool qqueue_debug(qqueue_t *queue, FILE *out)
qqueue->debug(): Print out stored elements for debugging purpose.
Definition qqueue.c:441
qqueue_clear
void qqueue_clear(qqueue_t *queue)
qqueue->clear(): Removes all of the elements from this queue.
Definition qqueue.c:429
qqueue_pop
void * qqueue_pop(qqueue_t *queue, size_t *size)
qqueue->pop(): Removes a element at the top of this queue and returns that element.
Definition qqueue.c:249
qqueue_popstr
char * qqueue_popstr(qqueue_t *queue)
qqueue->popstr(): Removes a element at the top of this queue and returns that element.
Definition qqueue.c:267
qqueue_size
size_t qqueue_size(qqueue_t *queue)
qqueue->size(): Returns the number of elements in this queue.
Definition qqueue.c:420
qqueue_free
void qqueue_free(qqueue_t *queue)
qqueue->free(): Free qqueue_t
Definition qqueue.c:452
qqueue_getstr
char * qqueue_getstr(qqueue_t *queue)
qqueue->getstr(): Returns an string at the top of this queue without removing it.
Definition qqueue.c:355
qqueue_popat
void * qqueue_popat(qqueue_t *queue, int index, size_t *size)
qqueue->popat(): Returns and remove the element at the specified position in this queue.
Definition qqueue.c:320
qqueue
qqueue_t * qqueue(int options)
Create new queue container.
Definition qqueue.c:129
qqueue_pushint
bool qqueue_pushint(qqueue_t *queue, int64_t num)
qqueue->pushint(): Pushes a integer onto the top of this queue.
Definition qqueue.c:233
qqueue_setsize
size_t qqueue_setsize(qqueue_t *queue, size_t max)
qqueue->setsize(): Sets maximum number of elements allowed in this queue.
Definition qqueue.c:177
qqueue_popint
int64_t qqueue_popint(qqueue_t *queue)
qqueue->popint(): Removes a integer at the top of this queue and returns that element.
Definition qqueue.c:291
qqueue_getat
void * qqueue_getat(qqueue_t *queue, int index, size_t *size, bool newmem)
qqueue->getat(): Returns an element at the specified position in this queue without removing it.
Definition qqueue.c:409