qLibc

qlist.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 qlist.c Doubly Linked-list implementation.
31 *
32 * qlist container is a doubly Linked-List implementation.
33 * qlist provides uniformly named methods to add, get, pop and remove an
34 * element at the beginning and end of the list. These operations allow qlist
35 * to be used as a stack, queue, or double-ended queue.
36 *
37 * @code
38 * [Conceptional Data Structure Diagram]
39 *
40 * last~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+
41 * |
42 * +-----------+ doubly +-----------+ doubly +-|---------+
43 * first~~~|~> 0 <~|~~~~~~~~~~|~> 1 <~|~~~~~~~~~~|~> N |
44 * +-----|-----+ linked +-----|-----+ linked +-----|-----+
45 * | | |
46 * +-----v---------------+ | +-----v-----+
47 * | DATA A | | | DATA N |
48 * +---------------------+ | +-----------+
49 * +---------------------v------------------+
50 * | DATA B |
51 * +----------------------------------------+
52 * @endcode
53 *
54 * @code
55 * // create a list.
56 * qlist_t *list = qlist(QLIST_THREADSAFE);
57 *
58 * // insert elements
59 * list->addlast(list, "e1", sizeof("e1"));
60 * list->addlast(list, "e2", sizeof("e2"));
61 * list->addlast(list, "e3", sizeof("e3"));
62 *
63 * // get
64 * char *e1 = (char*)list->getfirst(list, NULL, true)); // malloced
65 * char *e3 = (char*)list->getat(list, -1, NULL, false)); // no malloc
66 * (...omit...)
67 * free(e1);
68 *
69 * // pop (get and remove)
70 * char *e2 = (char*)list->popat(list, 1, NULL)); // get malloced copy
71 * (...omit...)
72 * free(e2);
73 *
74 * // debug output
75 * list->debug(list, stdout, true);
76 *
77 * // traversal
78 * qlist_obj_t obj;
79 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
80 * list->lock(list);
81 * while (list->getnext(list, &obj, false) == true) {
82 * printf("DATA=%s, SIZE=%zu\n", (char*)obj.data, obj.size);
83 * }
84 * list->unlock(list);
85 *
86 * // free object
87 * list->free(list);
88 * @endcode
89 */
90
91#include <stdio.h>
92#include <stdlib.h>
93#include <stdbool.h>
94#include <string.h>
95#include <errno.h>
96#include "qinternal.h"
97#include "containers/qlist.h"
98
99#ifndef _DOXYGEN_SKIP
100
101 static void *get_at(qlist_t *list, int index, size_t *size, bool newmem, bool remove);
102 static qlist_obj_t *get_obj(qlist_t *list, int index);
103 static bool remove_obj(qlist_t *list, qlist_obj_t *obj);
104
105#endif
106
107/**
108 * Create new qlist_t linked-list container
109 *
110 * @param options combination of initialization options.
111 *
112 * @return a pointer of malloced qlist_t container, otherwise returns NULL.
113 * @retval errno will be set in error condition.
114 * -ENOMEM : Memory allocation failure.
115 *
116 * @code
117 * qlist_t *list = qlist(0);
118 * @endcode
119 *
120 * @note
121 * Available options:
122 * - QLIST_THREADSAFE - make it thread-safe.
123 */
124qlist_t *qlist(int options) {
125 qlist_t *list = (qlist_t *) calloc(1, sizeof(qlist_t));
126 if (list == NULL) {
127 errno = ENOMEM;
128 return NULL;
129 }
130
131 // handle options.
132 if (options & QLIST_THREADSAFE) {
133 Q_MUTEX_NEW(list->qmutex, true);
134 if (list->qmutex == NULL) {
135 errno = ENOMEM;
136 free(list);
137 return NULL;
138 }
139 }
140
141 // member methods
142 list->setsize = qlist_setsize;
143
144 list->addfirst = qlist_addfirst;
145 list->addlast = qlist_addlast;
146 list->addat = qlist_addat;
147
148 list->getfirst = qlist_getfirst;
149 list->getlast = qlist_getlast;
150 list->getat = qlist_getat;
151 list->getnext = qlist_getnext;
152
153 list->popfirst = qlist_popfirst;
154 list->poplast = qlist_poplast;
155 list->popat = qlist_popat;
156
157 list->removefirst = qlist_removefirst;
158 list->removelast = qlist_removelast;
159 list->removeat = qlist_removeat;
160
161 list->reverse = qlist_reverse;
162 list->clear = qlist_clear;
163
164 list->size = qlist_size;
165 list->datasize = qlist_datasize;
166
167 list->toarray = qlist_toarray;
168 list->tostring = qlist_tostring;
169 list->debug = qlist_debug;
170
171 list->lock = qlist_lock;
172 list->unlock = qlist_unlock;
173
174 list->free = qlist_free;
175
176 return list;
177}
178
179/**
180 * qlist->setsize(): Limit maximum number of elements allowed in this list.
181 *
182 * @param list qlist_t container pointer.
183 * @param max maximum number of elements. 0 means no limit.
184 *
185 * @return previous maximum number.
186 *
187 * @note
188 * The default maximum number of elements is unlimited.
189 */
190 size_t qlist_setsize(qlist_t *list, size_t max) {
191 qlist_lock(list);
192 size_t old = list->max;
193 list->max = max;
194 qlist_unlock(list);
195 return old;
196}
197
198/**
199 * qlist->addfirst(): Inserts a element at the beginning of this list.
200 *
201 * @param list qlist_t container pointer.
202 * @param data a pointer which points data memory.
203 * @param size size of the data.
204 *
205 * @return true if successful, otherwise returns false.
206 * @retval errno will be set in error condition.
207 * - ENOBUFS : List full. Only happens when this list has set to have limited
208 * number of elements.
209 * - EINVAL : Invalid argument.
210 * - ENOMEM : Memory allocation failure.
211 *
212 * @code
213 * // create a sample object.
214 * struct my_obj obj;
215 *
216 * // create a list and add the sample object.
217 * qlist_t *list = qlist();
218 * list->addfirst(list, &obj, sizeof(struct my_obj));
219 * @endcode
220 */
221 bool qlist_addfirst(qlist_t *list, const void *data, size_t size) {
222 return qlist_addat(list, 0, data, size);
223}
224
225/**
226 * qlist->addlast(): Appends a element to the end of this list.
227 *
228 * @param list qlist_t container pointer.
229 * @param data a pointer which points data memory.
230 * @param size size of the data.
231 *
232 * @return true if successful, otherwise returns false.
233 * @retval errno will be set in error condition.
234 * - ENOBUFS : List full. Only happens when this list has set to have limited
235 * number of elements.
236 * - EINVAL : Invalid argument.
237 * - ENOMEM : Memory allocation failure.
238 */
239 bool qlist_addlast(qlist_t *list, const void *data, size_t size) {
240 return qlist_addat(list, -1, data, size);
241}
242
243/**
244 * qlist->addat(): Inserts a element at the specified position in this
245 * list.
246 *
247 * @param list qlist_t container pointer.
248 * @param index index at which the specified element is to be inserted.
249 * @param data a pointer which points data memory.
250 * @param size size of the data.
251 *
252 * @return true if successful, otherwise returns false.
253 * @retval errno will be set in error condition.
254 * - ENOBUFS : List full. Only happens when this list has set to have limited
255 * number of elements.
256 * - ERANGE : Index out of range.
257 * - EINVAL : Invalid argument.
258 * - ENOMEM : Memory allocation failure.
259 *
260 * @code
261 * first last new
262 * Linked-list [ A ]<=>[ B ]<=>[ C ]?==?[ ]
263 * (positive index) 0 1 2 3
264 * (negative index) -3 -2 -1
265 * @endcode
266 *
267 * @code
268 * qlist_t *list = qlist();
269 * list->addat(list, 0, &obj, sizeof(obj)); // same as addfirst().
270 * list->addat(list, -1, &obj, sizeof(obj)); // same as addlast().
271 * @endcode
272 *
273 * @note
274 * Index starts from 0.
275 */
276 bool qlist_addat(qlist_t *list, int index, const void *data, size_t size) {
277 // check arguments
278 if (data == NULL || size <= 0) {
279 errno = EINVAL;
280 return false;
281 }
282
283 qlist_lock(list);
284
285 // check maximum number of allowed elements if set
286 if (list->max > 0 && list->num >= list->max) {
287 errno = ENOBUFS;
288 qlist_unlock(list);
289 return false;
290 }
291
292 // adjust index
293 if (index < 0)
294 index = (list->num + index) + 1; // -1 is same as addlast()
295 if (index < 0 || index > list->num) {
296 // out of bound
297 qlist_unlock(list);
298 errno = ERANGE;
299 return false;
300 }
301
302 // duplicate object
303 void *dup_data = malloc(size);
304 if (dup_data == NULL) {
305 qlist_unlock(list);
306 errno = ENOMEM;
307 return false;
308 }
309 memcpy(dup_data, data, size);
310
311 // make new object list
312 qlist_obj_t *obj = (qlist_obj_t *) malloc(sizeof(qlist_obj_t));
313 if (obj == NULL) {
314 free(dup_data);
315 qlist_unlock(list);
316 errno = ENOMEM;
317 return false;
318 }
319 obj->data = dup_data;
320 obj->size = size;
321 obj->prev = NULL;
322 obj->next = NULL;
323
324 // make link
325 if (index == 0) {
326 // add at first
327 obj->next = list->first;
328 if (obj->next != NULL)
329 obj->next->prev = obj;
330 list->first = obj;
331 if (list->last == NULL)
332 list->last = obj;
333 } else if (index == list->num) {
334 // add after last
335 obj->prev = list->last;
336 if (obj->prev != NULL)
337 obj->prev->next = obj;
338 list->last = obj;
339 if (list->first == NULL)
340 list->first = obj;
341 } else {
342 // add at the middle of list
343 qlist_obj_t *tgt = get_obj(list, index);
344 if (tgt == NULL) {
345 // should not be happened.
346 free(dup_data);
347 free(obj);
348 qlist_unlock(list);
349 errno = EAGAIN;
350 return false;
351 }
352
353 // insert obj
354 tgt->prev->next = obj;
355 obj->prev = tgt->prev;
356 obj->next = tgt;
357 tgt->prev = obj;
358 }
359
360 list->datasum += size;
361 list->num++;
362
363 qlist_unlock(list);
364
365 return true;
366}
367
368/**
369 * qlist->getfirst(): Returns the first element in this list.
370 *
371 * @param list qlist_t container pointer.
372 * @param size if size is not NULL, element size will be stored.
373 * @param newmem whether or not to allocate memory for the element.
374 *
375 * @return a pointer of element, otherwise returns NULL.
376 * @retval errno will be set in error condition.
377 * - ENOENT : List is empty.
378 * - ENOMEM : Memory allocation failure.
379 *
380 * @code
381 * size_t size;
382 * void *data = list->getfirst(list, &size, true);
383 * if (data != NULL) {
384 * (...omit...)
385 * free(data);
386 * }
387 * @endcode
388 */
389 void *qlist_getfirst(qlist_t *list, size_t *size, bool newmem) {
390 return qlist_getat(list, 0, size, newmem);
391}
392
393/**
394 * qlist->getlast(): Returns the last element in this list.
395 *
396 * @param list qlist_t container pointer.
397 * @param size if size is not NULL, element size will be stored.
398 * @param newmem whether or not to allocate memory for the element.
399 *
400 * @return a pointer of element, otherwise returns NULL.
401 * @retval errno will be set in error condition.
402 * ENOENT : List is empty.
403 * ENOMEM : Memory allocation failure.
404 */
405 void *qlist_getlast(qlist_t *list, size_t *size, bool newmem) {
406 return qlist_getat(list, -1, size, newmem);
407}
408
409/**
410 * qlist->getat(): Returns the element at the specified position in this
411 * list.
412 *
413 * @param list qlist_t container pointer.
414 * @param index index at which the specified element is to be inserted
415 * @param size if size is not NULL, element size will be stored.
416 * @param newmem whether or not to allocate memory for the element.
417 *
418 * @return a pointer of element, otherwise returns NULL.
419 * @retval errno
420 * @retval errno will be set in error condition.
421 * -ERANGE : Index out of range.
422 * -ENOMEM : Memory allocation failure.
423 *
424 * @code
425 * first last
426 * Linked-list [ A ]<=>[ B ]<=>[ C ]
427 * (positive index) 0 1 2
428 * (negative index) -3 -2 -1
429 * @endcode
430 *
431 * @note
432 * Negative index can be used for addressing a element from the end in this
433 * stack. For example, index -1 is same as getlast() and index 0 is same as
434 * getfirst();
435 */
436 void *qlist_getat(qlist_t *list, int index, size_t *size, bool newmem) {
437 return get_at(list, index, size, newmem, false);
438}
439
440/**
441 * qlist->popfirst(): Returns and remove the first element in this list.
442 *
443 * @param list qlist_t container pointer.
444 * @param size if size is not NULL, element size will be stored.
445 *
446 * @return a pointer of malloced element, otherwise returns NULL.
447 * @retval errno will be set in error condition.
448 * -ENOENT : List is empty.
449 * -ENOMEM : Memory allocation failure.
450 */
451 void *qlist_popfirst(qlist_t *list, size_t *size) {
452 return qlist_popat(list, 0, size);
453}
454
455/**
456 * qlist->getlast(): Returns and remove the last element in this list.
457 *
458 * @param list qlist_t container pointer.
459 * @param size if size is not NULL, element size will be stored.
460 *
461 * @return a pointer of malloced element, otherwise returns NULL.
462 * @retval errno will be set in error condition.
463 * -ENOENT : List is empty.
464 * -ENOMEM : Memory allocation failure.
465 */
466 void *qlist_poplast(qlist_t *list, size_t *size) {
467 return qlist_popat(list, -1, size);
468}
469
470/**
471 * qlist->popat(): Returns and remove the element at the specified
472 * position in this list.
473 *
474 * @param list qlist_t container pointer.
475 * @param index index at which the specified element is to be inserted
476 * @param size if size is not NULL, element size will be stored.
477 *
478 * @return a pointer of malloced element, otherwise returns NULL.
479 * @retval errno will be set in error condition.
480 * -ERANGE : Index out of range.
481 * -ENOMEM : Memory allocation failure.
482 *
483 * @code
484 * first last
485 * Linked-list [ A ]<=>[ B ]<=>[ C ]
486 * (positive index) 0 1 2
487 * (negative index) -3 -2 -1
488 * @endcode
489 *
490 * @note
491 * Negative index can be used for addressing a element from the end in this
492 * stack. For example, index -1 is same as poplast() and index 0 is same as
493 * popfirst();
494 */
495 void *qlist_popat(qlist_t *list, int index, size_t *size) {
496 return get_at(list, index, size, true, true);
497}
498
499/**
500 * qlist->removefirst(): Removes the first element in this list.
501 *
502 * @param list qlist_t container pointer.
503 *
504 * @return a number of removed objects.
505 * @retval errno will be set in error condition.
506 * -ENOENT : List is empty.
507 */
508 bool qlist_removefirst(qlist_t *list) {
509 return qlist_removeat(list, 0);
510}
511
512/**
513 * qlist->removelast(): Removes the last element in this list.
514 *
515 * @param list qlist_t container pointer.
516 *
517 * @return a number of removed objects.
518 * @retval errno will be set in error condition.
519 * -ENOENT : List is empty.
520 */
521 bool qlist_removelast(qlist_t *list) {
522 return qlist_removeat(list, -1);
523}
524
525/**
526 * qlist->removeat(): Removes the element at the specified position in
527 * this list.
528 *
529 * @param list qlist_t container pointer.
530 * @param index index at which the specified element is to be removed.
531 *
532 * @return a number of removed objects.
533 * @retval errno will be set in error condition.
534 * -ERANGE : Index out of range.
535 */
536 bool qlist_removeat(qlist_t *list, int index) {
537 qlist_lock(list);
538
539 // get object pointer
540 qlist_obj_t *obj = get_obj(list, index);
541 if (obj == NULL) {
542 qlist_unlock(list);
543 return false;
544 }
545
546 bool ret = remove_obj(list, obj);
547
548 qlist_unlock(list);
549
550 return ret;
551}
552
553/**
554 * qlist->getnext(): Get next element in this list.
555 *
556 * @param list qlist_t container pointer.
557 * @param obj found data will be stored in this structure
558 * @param newmem whether or not to allocate memory for the element.
559 *
560 * @return true if found otherwise returns false
561 * @retval errno will be set in error condition.
562 * -ENOENT : No next element.
563 * -ENOMEM : Memory allocation failure.
564 *
565 * @note
566 * obj should be initialized with 0 by using memset() before first call.
567 * If newmem flag is true, user should de-allocate obj.name and obj.data
568 * resources.
569 *
570 * @code
571 * qlist_t *list = qlist();
572 * (...add data into list...)
573 *
574 * qlist_obj_t obj;
575 * memset((void*)&obj, 0, sizeof(obj)); // must be cleared before call
576 * list->lock(list); // can be omitted in single thread model.
577 * while (list->getnext(list, &obj, false) == true) {
578 * printf("DATA=%s, SIZE=%zu\n", (char*)obj.data, obj.size);
579 * }
580 * list->unlock(list); // release lock.
581 * @endcode
582 */
583 bool qlist_getnext(qlist_t *list, qlist_obj_t *obj, bool newmem) {
584 if (obj == NULL)
585 return false;
586
587 qlist_lock(list);
588
589 qlist_obj_t *cont = NULL;
590 if (obj->size == 0)
591 cont = list->first;
592 else
593 cont = obj->next;
594
595 if (cont == NULL) {
596 errno = ENOENT;
597 qlist_unlock(list);
598 return false;
599 }
600
601 bool ret = false;
602 while (cont != NULL) {
603 if (newmem == true) {
604 obj->data = malloc(cont->size);
605 if (obj->data == NULL)
606 break;
607
608 memcpy(obj->data, cont->data, cont->size);
609 } else {
610 obj->data = cont->data;
611 }
612 obj->size = cont->size;
613 obj->prev = cont->prev;
614 obj->next = cont->next;
615
616 ret = true;
617 break;
618 }
619
620 qlist_unlock(list);
621 return ret;
622}
623
624/**
625 * qlist->size(): Returns the number of elements in this list.
626 *
627 * @param list qlist_t container pointer.
628 *
629 * @return the number of elements in this list.
630 */
631 size_t qlist_size(qlist_t *list) {
632 return list->num;
633}
634
635/**
636 * qlist->size(): Returns the sum of total element size.
637 *
638 * @param list qlist_t container pointer.
639 *
640 * @return the sum of total element size.
641 */
642 size_t qlist_datasize(qlist_t *list) {
643 return list->datasum;
644}
645
646/**
647 * qlist->reverse(): Reverse the order of elements.
648 *
649 * @param list qlist_t container pointer.
650 */
651 void qlist_reverse(qlist_t *list) {
652 qlist_lock(list);
653 qlist_obj_t *obj;
654 for (obj = list->first; obj;) {
655 qlist_obj_t *next = obj->next;
656 obj->next = obj->prev;
657 obj->prev = next;
658 obj = next;
659 }
660
661 obj = list->first;
662 list->first = list->last;
663 list->last = obj;
664
665 qlist_unlock(list);
666}
667
668/**
669 * qlist->clear(): Removes all of the elements from this list.
670 *
671 * @param list qlist_t container pointer.
672 */
673 void qlist_clear(qlist_t *list) {
674 qlist_lock(list);
675 qlist_obj_t *obj;
676 for (obj = list->first; obj;) {
677 qlist_obj_t *next = obj->next;
678 free(obj->data);
679 free(obj);
680 obj = next;
681 }
682
683 list->num = 0;
684 list->datasum = 0;
685 list->first = NULL;
686 list->last = NULL;
687 qlist_unlock(list);
688}
689
690/**
691 * qlist->toarray(): Returns the serialized chunk containing all the
692 * elements in this list.
693 *
694 * @param list qlist_t container pointer.
695 * @param size if size is not NULL, chunk size will be stored.
696 *
697 * @return a malloced pointer,
698 * otherwise(if there is no data to merge) returns NULL.
699 * @retval errno will be set in error condition.
700 * -ENOENT : List is empty.
701 * -ENOMEM : Memory allocation failure.
702 */
703 void *qlist_toarray(qlist_t *list, size_t *size) {
704 if (list->num <= 0) {
705 if (size != NULL)
706 *size = 0;
707 errno = ENOENT;
708 return NULL;
709 }
710
711 qlist_lock(list);
712
713 void *chunk = malloc(list->datasum);
714 if (chunk == NULL) {
715 qlist_unlock(list);
716 errno = ENOMEM;
717 return NULL;
718 }
719 void *dp = chunk;
720
721 qlist_obj_t *obj;
722 for (obj = list->first; obj; obj = obj->next) {
723 memcpy(dp, obj->data, obj->size);
724 dp += obj->size;
725 }
726 qlist_unlock(list);
727
728 if (size != NULL)
729 *size = list->datasum;
730 return chunk;
731}
732
733/**
734 * qlist->tostring(): Returns a string representation of this list,
735 * containing string representation of each element.
736 *
737 * @param list qlist_t container pointer.
738 *
739 * @return a malloced pointer,
740 * otherwise(if there is no data to merge) returns NULL.
741 * @retval errno will be set in error condition.
742 * -ENOENT : List is empty.
743 * -ENOMEM : Memory allocation failure.
744 *
745 * @note
746 * Return string is always terminated by '\0'.
747 */
748 char *qlist_tostring(qlist_t *list) {
749 if (list->num <= 0) {
750 errno = ENOENT;
751 return NULL;
752 }
753
754 qlist_lock(list);
755
756 void *chunk = malloc(list->datasum + 1);
757 if (chunk == NULL) {
758 qlist_unlock(list);
759 errno = ENOMEM;
760 return NULL;
761 }
762 void *dp = chunk;
763
764 qlist_obj_t *obj;
765 for (obj = list->first; obj; obj = obj->next) {
766 size_t size = obj->size;
767 // do not copy tailing '\0'
768 if (*(char *) (obj->data + (size - 1)) == '\0')
769 size -= 1;
770 memcpy(dp, obj->data, size);
771 dp += size;
772 }
773 *((char *) dp) = '\0';
774 qlist_unlock(list);
775
776 return (char *) chunk;
777}
778
779/**
780 * qlist->debug(): Prints out stored elements for debugging purpose.
781 *
782 * @param list qlist_t container pointer.
783 * @param out output stream FILE descriptor such like stdout, stderr.
784 *
785 * @return true if successful, otherwise returns false.
786 * @retval errno will be set in error condition.
787 * -EIO : Invalid output stream.
788 */
789 bool qlist_debug(qlist_t *list, FILE *out) {
790 if (out == NULL) {
791 errno = EIO;
792 return false;
793 }
794
795 qlist_lock(list);
796 qlist_obj_t *obj;
797 int i;
798 for (i = 0, obj = list->first; obj; obj = obj->next, i++) {
799 fprintf(out, "%d=", i);
800 _q_textout(out, obj->data, obj->size, MAX_HUMANOUT);
801 fprintf(out, " (%zu)\n", obj->size);
802 }
803 qlist_unlock(list);
804
805 return true;
806}
807
808/**
809 * qlist->lock(): Enters critical section.
810 *
811 * @param list qlist_t container pointer.
812 *
813 * @note
814 * From user side, normally locking operation is only needed when traverse all
815 * elements using qlist->getnext().
816 */
817 void qlist_lock(qlist_t *list) {
818 Q_MUTEX_ENTER(list->qmutex);
819}
820
821/**
822 * qlist->unlock(): Leaves critical section.
823 *
824 * @param list qlist_t container pointer.
825 */
826 void qlist_unlock(qlist_t *list) {
827 Q_MUTEX_LEAVE(list->qmutex);
828}
829
830/**
831 * qlist->free(): Free qlist_t.
832 *
833 * @param list qlist_t container pointer.
834 */
835 void qlist_free(qlist_t *list) {
836 qlist_clear(list);
837 Q_MUTEX_DESTROY(list->qmutex);
838
839 free(list);
840}
841
842#ifndef _DOXYGEN_SKIP
843
844 static void *get_at(qlist_t *list, int index, size_t *size, bool newmem,
845 bool remove) {
846 qlist_lock(list);
847
848 // get object pointer
849 qlist_obj_t *obj = get_obj(list, index);
850 if (obj == NULL) {
851 qlist_unlock(list);
852 return false;
853 }
854
855 // copy data
856 void *data;
857 if (newmem == true) {
858 data = malloc(obj->size);
859 if (data == NULL) {
860 qlist_unlock(list);
861 errno = ENOMEM;
862 return false;
863 }
864 memcpy(data, obj->data, obj->size);
865 } else {
866 data = obj->data;
867 }
868 if (size != NULL)
869 *size = obj->size;
870
871 // remove if necessary
872 if (remove == true) {
873 if (remove_obj(list, obj) == false) {
874 if (newmem == true)
875 free(data);
876 data = NULL;
877 }
878 }
879
880 qlist_unlock(list);
881
882 return data;
883}
884
885 static qlist_obj_t *get_obj(qlist_t *list, int index) {
886 // index adjustment
887 if (index < 0)
888 index = list->num + index;
889 if (index >= list->num) {
890 errno = ERANGE;
891 return NULL;
892 }
893
894 // detect faster scan direction
895 bool backward;
896 qlist_obj_t *obj;
897 int listidx;
898 if (index < list->num / 2) {
899 backward = false;
900 obj = list->first;
901 listidx = 0;
902 } else {
903 backward = true;
904 obj = list->last;
905 listidx = list->num - 1;
906 }
907
908 // find object
909 while (obj != NULL) {
910 if (listidx == index)
911 return obj;
912
913 if (backward == false) {
914 obj = obj->next;
915 listidx++;
916 } else {
917 obj = obj->prev;
918 listidx--;
919 }
920 }
921
922 // never reach here
923 errno = ENOENT;
924 return NULL;
925}
926
927 static bool remove_obj(qlist_t *list, qlist_obj_t *obj) {
928 if (obj == NULL)
929 return false;
930
931 // chain prev and next elements
932 if (obj->prev == NULL)
933 list->first = obj->next;
934 else
935 obj->prev->next = obj->next;
936 if (obj->next == NULL)
937 list->last = obj->prev;
938 else
939 obj->next->prev = obj->prev;
940
941 // adjust counter
942 list->datasum -= obj->size;
943 list->num--;
944
945 // release obj
946 free(obj->data);
947 free(obj);
948
949 return true;
950}
951
952#endif /* _DOXYGEN_SKIP */
qlist_getlast
void * qlist_getlast(qlist_t *list, size_t *size, bool newmem)
qlist->getlast(): Returns the last element in this list.
Definition qlist.c:405
qlist_getnext
bool qlist_getnext(qlist_t *list, qlist_obj_t *obj, bool newmem)
qlist->getnext(): Get next element in this list.
Definition qlist.c:583
qlist_unlock
void qlist_unlock(qlist_t *list)
qlist->unlock(): Leaves critical section.
Definition qlist.c:826
qlist_tostring
char * qlist_tostring(qlist_t *list)
qlist->tostring(): Returns a string representation of this list, containing string representation of ...
Definition qlist.c:748
qlist_reverse
void qlist_reverse(qlist_t *list)
qlist->reverse(): Reverse the order of elements.
Definition qlist.c:651
qlist_removelast
bool qlist_removelast(qlist_t *list)
qlist->removelast(): Removes the last element in this list.
Definition qlist.c:521
qlist_addat
bool qlist_addat(qlist_t *list, int index, const void *data, size_t size)
qlist->addat(): Inserts a element at the specified position in this list.
Definition qlist.c:276
qlist_poplast
void * qlist_poplast(qlist_t *list, size_t *size)
qlist->getlast(): Returns and remove the last element in this list.
Definition qlist.c:466
qlist_addfirst
bool qlist_addfirst(qlist_t *list, const void *data, size_t size)
qlist->addfirst(): Inserts a element at the beginning of this list.
Definition qlist.c:221
qlist_free
void qlist_free(qlist_t *list)
qlist->free(): Free qlist_t.
Definition qlist.c:835
qlist_debug
bool qlist_debug(qlist_t *list, FILE *out)
qlist->debug(): Prints out stored elements for debugging purpose.
Definition qlist.c:789
qlist_getat
void * qlist_getat(qlist_t *list, int index, size_t *size, bool newmem)
qlist->getat(): Returns the element at the specified position in this list.
Definition qlist.c:436
qlist_addlast
bool qlist_addlast(qlist_t *list, const void *data, size_t size)
qlist->addlast(): Appends a element to the end of this list.
Definition qlist.c:239
qlist_datasize
size_t qlist_datasize(qlist_t *list)
qlist->size(): Returns the sum of total element size.
Definition qlist.c:642
qlist_removefirst
bool qlist_removefirst(qlist_t *list)
qlist->removefirst(): Removes the first element in this list.
Definition qlist.c:508
qlist_size
size_t qlist_size(qlist_t *list)
qlist->size(): Returns the number of elements in this list.
Definition qlist.c:631
qlist_popat
void * qlist_popat(qlist_t *list, int index, size_t *size)
qlist->popat(): Returns and remove the element at the specified position in this list.
Definition qlist.c:495
qlist_getfirst
void * qlist_getfirst(qlist_t *list, size_t *size, bool newmem)
qlist->getfirst(): Returns the first element in this list.
Definition qlist.c:389
qlist_clear
void qlist_clear(qlist_t *list)
qlist->clear(): Removes all of the elements from this list.
Definition qlist.c:673
qlist_lock
void qlist_lock(qlist_t *list)
qlist->lock(): Enters critical section.
Definition qlist.c:817
qlist_popfirst
void * qlist_popfirst(qlist_t *list, size_t *size)
qlist->popfirst(): Returns and remove the first element in this list.
Definition qlist.c:451
qlist_setsize
size_t qlist_setsize(qlist_t *list, size_t max)
qlist->setsize(): Limit maximum number of elements allowed in this list.
Definition qlist.c:190
qlist
qlist_t * qlist(int options)
Create new qlist_t linked-list container.
Definition qlist.c:124
qlist_toarray
void * qlist_toarray(qlist_t *list, size_t *size)
qlist->toarray(): Returns the serialized chunk containing all the elements in this list.
Definition qlist.c:703
qlist_removeat
bool qlist_removeat(qlist_t *list, int index)
qlist->removeat(): Removes the element at the specified position in this list.
Definition qlist.c:536