1 /*
2 * linked list routines
3 *
4 * $Id: mjl_list.c,v 1.78 2020/03/17 07:32:15 mjl Exp $
5 *
6 * Matthew Luckie
7 * mjl@luckie.org.nz
8 *
9 * Copyright (C) 2004-2020 Matthew Luckie. All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY Matthew Luckie ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL Matthew Luckie BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 */
33
34 #include <stdlib.h>
35 #include <assert.h>
36
37 #if defined(DMALLOC)
38 #include <dmalloc.h>
39 #endif
40
41 #if defined(HAVE_CONFIG_H)
42 #include "config.h"
43 #endif
44
45 #include "mjl_list.h"
46
47 struct slist_node
48 {
49 void *item;
50 struct slist_node *next;
51 };
52
53 struct dlist_node
54 {
55 void *item;
56 struct dlist_node *prev;
57 struct dlist_node *next;
58 struct dlist *list;
59 };
60
61 struct clist_node
62 {
63 void *item;
64 struct clist_node *prev;
65 struct clist_node *next;
66 };
67
68 struct slist
69 {
70 slist_node_t *head;
71 slist_node_t *tail;
72 int length;
73 unsigned int lock;
74 slist_onremove_t onremove;
75 };
76
77 struct dlist
78 {
79 dlist_node_t *head;
80 dlist_node_t *tail;
81 int length;
82 unsigned int lock;
83 dlist_onremove_t onremove;
84 };
85
86 struct clist
87 {
88 clist_node_t *head;
89 int length;
90 unsigned int lock;
91 clist_onremove_t onremove;
92 };
93
random_u32(unsigned int * r)94 static int random_u32(unsigned int *r)
95 {
96 #ifdef _WIN32
97 unsigned int ui;
98 if(rand_s(&ui) != 0)
99 return -1;
100 *r = ui;
101 #elif HAVE_ARC4RANDOM
102 *r = arc4random();
103 #else
104 *r = random();
105 #endif
106 return 0;
107 }
108
shuffle_array(void ** array,int len)109 static int shuffle_array(void **array, int len)
110 {
111 int n = len;
112 unsigned int k;
113 void *tmp;
114
115 while(n > 1)
116 {
117 n--;
118 if(random_u32(&k) != 0)
119 return -1;
120 k %= n+1;
121
122 tmp = array[k];
123 array[k] = array[n];
124 array[n] = tmp;
125 }
126
127 return 0;
128 }
129
130 #if !defined(NDEBUG) && defined(MJLLIST_DEBUG)
slist_assert_sort(const slist_t * list,slist_cmp_t cmp)131 static void slist_assert_sort(const slist_t *list, slist_cmp_t cmp)
132 {
133 slist_node_t *n;
134 for(n=list->head; n->next != NULL; n = n->next)
135 assert(cmp(n->item, n->next->item) <= 0);
136 return;
137 }
138
slist_assert(const slist_t * list)139 static void slist_assert(const slist_t *list)
140 {
141 slist_node_t *node;
142 int i;
143
144 if(list == NULL)
145 return;
146
147 assert(list->length >= 0);
148
149 if(list->length == 0)
150 {
151 assert(list->head == NULL);
152 assert(list->tail == NULL);
153 }
154 else if(list->length == 1)
155 {
156 assert(list->head != NULL);
157 assert(list->tail != NULL);
158 assert(list->head == list->tail);
159 assert(list->head->next == NULL);
160 }
161 else
162 {
163 i = 1; node = list->head;
164 while(i<list->length)
165 {
166 assert(node != NULL);
167 node = node->next;
168 i++;
169 }
170 assert(node == list->tail);
171 }
172 return;
173 }
174 #else
175 #define slist_assert(list)((void)0)
176 #define slist_assert_sort(list,cmp)((void)0)
177 #endif
178
slist_lock(slist_t * list)179 void slist_lock(slist_t *list)
180 {
181 assert(list != NULL);
182 list->lock++;
183 return;
184 }
185
slist_unlock(slist_t * list)186 void slist_unlock(slist_t *list)
187 {
188 assert(list != NULL);
189 assert(list->lock > 0);
190 list->lock--;
191 return;
192 }
193
slist_islocked(slist_t * list)194 int slist_islocked(slist_t *list)
195 {
196 assert(list != NULL);
197 return list->lock == 0 ? 0 : 1;
198 }
199
200 #ifndef DMALLOC
slist_alloc(void)201 slist_t *slist_alloc(void)
202 #else
203 slist_t *slist_alloc_dm(const char *file, const int line)
204 #endif
205 {
206 slist_t *list;
207 size_t len = sizeof(slist_t);
208
209 #ifndef DMALLOC
210 list = (slist_t *)malloc(len);
211 #else
212 list = (slist_t *)dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
213 #endif
214
215 if(list != NULL)
216 {
217 slist_init(list);
218 }
219
220 return list;
221 }
222
slist_init(slist_t * list)223 void slist_init(slist_t *list)
224 {
225 assert(list != NULL);
226 list->head = NULL;
227 list->tail = NULL;
228 list->length = 0;
229 list->lock = 0;
230 list->onremove = NULL;
231 return;
232 }
233
slist_onremove(slist_t * list,slist_onremove_t onremove)234 void slist_onremove(slist_t *list, slist_onremove_t onremove)
235 {
236 assert(list != NULL);
237 list->onremove = onremove;
238 return;
239 }
240
241 #ifndef DMALLOC
slist_node(void * item,slist_node_t * next)242 static slist_node_t *slist_node(void *item, slist_node_t *next)
243 #else
244 static slist_node_t *slist_node(void *item, slist_node_t *next,
245 const char *file, const int line)
246 #endif
247 {
248 slist_node_t *node;
249 size_t len = sizeof(slist_node_t);
250
251 #ifndef DMALLOC
252 node = malloc(len);
253 #else
254 node = dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
255 #endif
256
257 if(node != NULL)
258 {
259 node->item = item;
260 node->next = next;
261 }
262
263 return node;
264 }
265
266 /*
267 * slist_dup
268 *
269 * make a copy of the list that points to the same items.
270 * if the foreach function is not null, call that on each item too.
271 */
272 #ifndef DMALLOC
slist_dup(slist_t * oldlist,const slist_foreach_t func,void * param)273 slist_t *slist_dup(slist_t *oldlist, const slist_foreach_t func, void *param)
274 #else
275 slist_t *slist_dup_dm(slist_t *oldlist,const slist_foreach_t func,void *param,
276 const char *file, const int line)
277 #endif
278 {
279 slist_t *list;
280 slist_node_t *oldnode, *node;
281
282 /* first, allocate a replacement slist_t structure */
283 #ifndef DMALLOC
284 list = slist_alloc();
285 #else
286 list = slist_alloc_dm(file, line);
287 #endif
288
289 if(list == NULL)
290 return NULL;
291
292 if(oldlist->head != NULL)
293 {
294 #ifndef DMALLOC
295 if((node = slist_node(oldlist->head->item, NULL)) == NULL)
296 #else
297 if((node = slist_node(oldlist->head->item, NULL, file, line)) == NULL)
298 #endif
299 {
300 goto err;
301 }
302
303 if(func != NULL) func(oldlist->head->item, param);
304
305 list->length = oldlist->length;
306 list->head = node;
307 oldnode = oldlist->head->next;
308 }
309 else return list;
310
311 while(oldnode != NULL)
312 {
313 #ifndef DMALLOC
314 if((node->next = slist_node(oldnode->item, NULL)) == NULL)
315 #else
316 if((node->next = slist_node(oldnode->item, NULL, file, line)) == NULL)
317 #endif
318 {
319 goto err;
320 }
321
322 if(func != NULL) func(oldnode->item, param);
323
324 oldnode = oldnode->next;
325 node = node->next;
326 }
327
328 list->tail = node;
329
330 return list;
331
332 err:
333 slist_free(list);
334 return NULL;
335 }
336
slist_concat(slist_t * first,slist_t * second)337 void slist_concat(slist_t *first, slist_t *second)
338 {
339 assert(first != NULL);
340 assert(second != NULL);
341 assert(first->lock == 0);
342 assert(second->lock == 0);
343 slist_assert(first);
344 slist_assert(second);
345
346 /* if there is nothing to concatenate, then return now */
347 if(second->length == 0)
348 {
349 return;
350 }
351
352 /* shift the second list's nodes into the first */
353 if(first->tail != NULL)
354 {
355 first->tail->next = second->head;
356 first->length += second->length;
357 first->tail = second->tail;
358 }
359 else
360 {
361 first->head = second->head;
362 first->tail = second->tail;
363 first->length = second->length;
364 }
365
366 /* reset the second list */
367 second->length = 0;
368 second->head = NULL;
369 second->tail = NULL;
370
371 slist_assert(first);
372 slist_assert(second);
373 return;
374 }
375
slist_flush(slist_t * list,slist_free_t free_func)376 static void slist_flush(slist_t *list, slist_free_t free_func)
377 {
378 slist_node_t *node;
379 slist_node_t *next;
380
381 assert(list != NULL);
382 slist_assert(list);
383 assert(list->lock == 0);
384
385 node = list->head;
386 while(node != NULL)
387 {
388 next = node->next;
389 if(list->onremove != NULL)
390 list->onremove(node->item);
391 if(free_func != NULL)
392 free_func(node->item);
393 free(node);
394 node = next;
395 }
396 return;
397 }
398
slist_empty(slist_t * list)399 void slist_empty(slist_t *list)
400 {
401 slist_flush(list, NULL);
402 slist_init(list);
403 return;
404 }
405
slist_empty_cb(slist_t * list,slist_free_t func)406 void slist_empty_cb(slist_t *list, slist_free_t func)
407 {
408 slist_flush(list, func);
409 slist_init(list);
410 return;
411 }
412
slist_free(slist_t * list)413 void slist_free(slist_t *list)
414 {
415 slist_flush(list, NULL);
416 free(list);
417 return;
418 }
419
slist_free_cb(slist_t * list,slist_free_t func)420 void slist_free_cb(slist_t *list, slist_free_t func)
421 {
422 slist_flush(list, func);
423 free(list);
424 return;
425 }
426
427 #ifndef DMALLOC
slist_head_push(slist_t * list,void * item)428 slist_node_t *slist_head_push(slist_t *list, void *item)
429 #else
430 slist_node_t *slist_head_push_dm(slist_t *list, void *item,
431 const char *file, const int line)
432 #endif
433 {
434 slist_node_t *node;
435
436 assert(list != NULL);
437 slist_assert(list);
438 assert(list->lock == 0);
439
440 #ifndef DMALLOC
441 if((node = slist_node(item, list->head)) != NULL)
442 #else
443 if((node = slist_node(item, list->head, file, line)) != NULL)
444 #endif
445 {
446 list->head = node;
447
448 if(list->tail == NULL)
449 {
450 list->tail = node;
451 }
452
453 list->length++;
454 }
455
456 slist_assert(list);
457
458 return node;
459 }
460
461 #ifndef DMALLOC
slist_tail_push(slist_t * list,void * item)462 slist_node_t *slist_tail_push(slist_t *list, void *item)
463 #else
464 slist_node_t *slist_tail_push_dm(slist_t *list, void *item,
465 const char *file, const int line)
466 #endif
467 {
468 slist_node_t *node;
469
470 assert(list != NULL);
471 slist_assert(list);
472 assert(list->lock == 0);
473
474 #ifndef DMALLOC
475 if((node = slist_node(item, NULL)) != NULL)
476 #else
477 if((node = slist_node(item, NULL, file, line)) != NULL)
478 #endif
479 {
480 if(list->tail != NULL)
481 {
482 list->tail->next = node;
483 list->tail = node;
484 }
485 else
486 {
487 list->head = list->tail = node;
488 }
489
490 list->length++;
491 }
492
493 slist_assert(list);
494
495 return node;
496 }
497
slist_head_pop(slist_t * list)498 void *slist_head_pop(slist_t *list)
499 {
500 slist_node_t *node;
501 void *item = NULL;
502
503 assert(list != NULL);
504 slist_assert(list);
505 assert(list->lock == 0);
506
507 if(list->head == NULL)
508 return NULL;
509
510 node = list->head;
511 item = node->item;
512
513 /* if there are no nodes left ... */
514 if((list->head = node->next) == NULL)
515 list->tail = NULL;
516
517 free(node);
518 list->length--;
519
520 if(list->onremove != NULL)
521 list->onremove(item);
522
523 slist_assert(list);
524
525 return item;
526 }
527
slist_head_item(const slist_t * list)528 void *slist_head_item(const slist_t *list)
529 {
530 assert(list != NULL);
531 if(list->head == NULL) return NULL;
532 return list->head->item;
533 }
534
slist_tail_item(const slist_t * list)535 void *slist_tail_item(const slist_t *list)
536 {
537 assert(list != NULL);
538 if(list->tail == NULL) return NULL;
539 return list->tail->item;
540 }
541
slist_head_node(const slist_t * list)542 slist_node_t *slist_head_node(const slist_t *list)
543 {
544 assert(list != NULL);
545 return list->head;
546 }
547
slist_tail_node(const slist_t * list)548 slist_node_t *slist_tail_node(const slist_t *list)
549 {
550 assert(list != NULL);
551 return list->tail;
552 }
553
slist_node_item(const slist_node_t * node)554 void *slist_node_item(const slist_node_t *node)
555 {
556 assert(node != NULL);
557 return node->item;
558 }
559
slist_node_next(const slist_node_t * node)560 slist_node_t *slist_node_next(const slist_node_t *node)
561 {
562 assert(node != NULL);
563 return node->next;
564 }
565
slist_foreach(slist_t * list,const slist_foreach_t func,void * param)566 int slist_foreach(slist_t *list, const slist_foreach_t func, void *param)
567 {
568 slist_node_t *node;
569 slist_node_t *next;
570
571 assert(list != NULL);
572 slist_lock(list);
573 slist_assert(list);
574
575 node = list->head;
576 while(node != NULL)
577 {
578 next = node->next;
579 if(func(node->item, param) != 0)
580 {
581 slist_unlock(list);
582 return -1;
583 }
584 node = next;
585 }
586
587 slist_assert(list);
588 slist_unlock(list);
589
590 return 0;
591 }
592
slist_count(const slist_t * list)593 int slist_count(const slist_t *list)
594 {
595 assert(list != NULL);
596 slist_assert(list);
597 return list->length;
598 }
599
slist_swap(slist_node_t ** a,int i,int j)600 static void slist_swap(slist_node_t **a, int i, int j)
601 {
602 slist_node_t *item = a[i];
603 a[i] = a[j];
604 a[j] = item;
605 return;
606 }
607
slist_node_array(const slist_t * list)608 static slist_node_t **slist_node_array(const slist_t *list)
609 {
610 slist_node_t **v = NULL, *n;
611 int i = 0;
612 assert(list->length >= 2);
613 if((v = malloc(sizeof(slist_node_t *) * list->length)) == NULL)
614 return NULL;
615 for(n = list->head; n != NULL; n = n->next)
616 v[i++] = n;
617 assert(i == list->length);
618 return v;
619 }
620
slist_rebuild(slist_t * list,slist_node_t ** v)621 static void slist_rebuild(slist_t *list, slist_node_t **v)
622 {
623 int i;
624 list->head = v[0];
625 list->tail = v[list->length-1];
626 list->tail->next = NULL;
627 for(i=0; i<list->length-1; i++)
628 v[i]->next = v[i+1];
629 slist_assert(list);
630 return;
631 }
632
633 /*
634 * slist_qsort_3:
635 *
636 * recursive function that implements quicksort with a three-way partition
637 * on an array of slist_node_t structures.
638 */
slist_qsort_3(slist_node_t ** a,slist_cmp_t cmp,int l,int r)639 static void slist_qsort_3(slist_node_t **a, slist_cmp_t cmp, int l, int r)
640 {
641 slist_node_t *c;
642 int i, lt, gt, rc;
643
644 if(l >= r)
645 return;
646
647 c = a[l];
648 lt = l;
649 gt = r;
650 i = l;
651
652 while(i <= gt)
653 {
654 rc = a[i]->item != c->item ? cmp(a[i]->item, c->item) : 0;
655 if(rc < 0)
656 slist_swap(a, lt++, i++);
657 else if(rc > 0)
658 slist_swap(a, i, gt--);
659 else
660 i++;
661 }
662
663 slist_qsort_3(a, cmp, l, lt-1);
664 slist_qsort_3(a, cmp, gt+1, r);
665 return;
666 }
667
slist_qsort(slist_t * list,slist_cmp_t cmp)668 int slist_qsort(slist_t *list, slist_cmp_t cmp)
669 {
670 slist_node_t **v;
671
672 slist_assert(list);
673 assert(list->lock == 0);
674
675 /* don't have to order the list if there less than two items in it */
676 if(list->length < 2)
677 return 0;
678
679 if((v = slist_node_array(list)) == NULL)
680 return -1;
681 slist_qsort_3(v, cmp, 0, list->length-1);
682 slist_rebuild(list, v);
683 free(v);
684
685 slist_assert_sort(list, cmp);
686 return 0;
687 }
688
slist_shuffle(slist_t * list)689 int slist_shuffle(slist_t *list)
690 {
691 slist_node_t **v;
692 slist_assert(list);
693 assert(list->lock == 0);
694 if(list->length < 2)
695 return 0;
696 if((v = slist_node_array(list)) == NULL)
697 return -1;
698 shuffle_array((void **)v, list->length);
699 slist_rebuild(list, v);
700 free(v);
701 return 0;
702 }
703
704 #if !defined(NDEBUG) && defined(MJLLIST_DEBUG)
dlist_assert_sort(const dlist_t * list,dlist_cmp_t cmp)705 static void dlist_assert_sort(const dlist_t *list, dlist_cmp_t cmp)
706 {
707 dlist_node_t *n;
708 for(n=list->head; n->next != NULL; n = n->next)
709 assert(cmp(n->item, n->next->item) <= 0);
710 return;
711 }
712
dlist_assert(const dlist_t * list)713 static void dlist_assert(const dlist_t *list)
714 {
715 dlist_node_t *node;
716 int i;
717
718 if(list == NULL)
719 return;
720
721 assert(list->length >= 0);
722
723 if(list->length == 0)
724 {
725 assert(list->head == NULL);
726 assert(list->tail == NULL);
727 }
728 else if(list->length == 1)
729 {
730 assert(list->head != NULL);
731 assert(list->tail != NULL);
732 assert(list->head == list->tail);
733 assert(list->head->next == NULL);
734 assert(list->head->prev == NULL);
735 assert(list->head->list == list);
736 }
737 else
738 {
739 assert(list->head->prev == NULL);
740 assert(list->tail->next == NULL);
741
742 i = 1; node = list->head;
743 while(i < list->length-1)
744 {
745 assert(node != NULL);
746 assert(node->next != NULL);
747 assert(node->next->prev == node);
748 assert(node->list == list);
749 node = node->next;
750 i++;
751 }
752 assert(node->next == list->tail);
753 assert(node->list == list);
754 }
755 return;
756 }
757 #else
758 #define dlist_assert(list)((void)0)
759 #define dlist_assert_sort(list,cmp)((void)0)
760 #endif
761
dlist_lock(dlist_t * list)762 void dlist_lock(dlist_t *list)
763 {
764 assert(list != NULL);
765 list->lock++;
766 return;
767 }
768
dlist_unlock(dlist_t * list)769 void dlist_unlock(dlist_t *list)
770 {
771 assert(list != NULL);
772 assert(list->lock > 0);
773 list->lock--;
774 return;
775 }
776
dlist_islocked(dlist_t * list)777 int dlist_islocked(dlist_t *list)
778 {
779 assert(list != NULL);
780 return list->lock == 0 ? 0 : 1;
781 }
782
783 #ifndef DMALLOC
dlist_alloc(void)784 dlist_t *dlist_alloc(void)
785 #else
786 dlist_t *dlist_alloc_dm(const char *file, const int line)
787 #endif
788 {
789 dlist_t *list;
790 size_t len = sizeof(dlist_t);
791
792 #ifndef DMALLOC
793 list = malloc(len);
794 #else
795 list = dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
796 #endif
797
798 if(list != NULL)
799 {
800 dlist_init(list);
801 }
802
803 return list;
804 }
805
dlist_init(dlist_t * list)806 void dlist_init(dlist_t *list)
807 {
808 assert(list != NULL);
809 list->head = NULL;
810 list->tail = NULL;
811 list->length = 0;
812 list->lock = 0;
813 list->onremove = NULL;
814 return;
815 }
816
dlist_onremove(dlist_t * list,dlist_onremove_t onremove)817 void dlist_onremove(dlist_t *list, dlist_onremove_t onremove)
818 {
819 assert(list != NULL);
820 list->onremove = onremove;
821 return;
822 }
823
824 #ifndef DMALLOC
dlist_node(void * i,dlist_node_t * p,dlist_node_t * n)825 static dlist_node_t *dlist_node(void *i, dlist_node_t *p, dlist_node_t *n)
826 #else
827 static dlist_node_t *dlist_node(void *i, dlist_node_t *p, dlist_node_t *n,
828 const char *file, const int line)
829 #endif
830 {
831 dlist_node_t *node;
832 size_t len = sizeof(dlist_node_t);
833
834 #ifndef DMALLOC
835 node = malloc(len);
836 #else
837 node = dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
838 #endif
839
840 if(node != NULL)
841 {
842 node->item = i;
843 node->prev = p;
844 node->next = n;
845 node->list = NULL;
846 }
847
848 return node;
849 }
850
851 /*
852 * dlist_dup
853 *
854 * make a copy of the list that points to the same items.
855 * if the foreach function is not null, call that on each item too.
856 */
857 #ifndef DMALLOC
dlist_dup(dlist_t * oldlist,const dlist_foreach_t func,void * param)858 dlist_t *dlist_dup(dlist_t *oldlist, const dlist_foreach_t func, void *param)
859 #else
860 dlist_t *dlist_dup_dm(dlist_t *oldlist,const dlist_foreach_t func,void *param,
861 const char *file, const int line)
862 #endif
863 {
864 dlist_t *list;
865 dlist_node_t *oldnode, *node;
866
867 /* first, allocate a replacement slist_t structure */
868 #ifndef DMALLOC
869 list = dlist_alloc();
870 #else
871 list = dlist_alloc_dm(file, line);
872 #endif
873
874 if(list == NULL)
875 return NULL;
876
877 if(oldlist->head != NULL)
878 {
879 #ifndef DMALLOC
880 if((node = dlist_node(oldlist->head->item, NULL, NULL)) == NULL)
881 #else
882 if((node = dlist_node(oldlist->head->item, NULL, NULL, file, line)) == NULL)
883 #endif
884 {
885 goto err;
886 }
887
888 if(func != NULL) func(oldlist->head->item, param);
889
890 list->length = oldlist->length;
891 list->head = node;
892 oldnode = oldlist->head->next;
893 }
894 else return list;
895
896 while(oldnode != NULL)
897 {
898 #ifndef DMALLOC
899 if((node->next = dlist_node(oldnode->item, node, NULL)) == NULL)
900 #else
901 if((node->next = dlist_node(oldnode->item, node, NULL, file, line)) == NULL)
902 #endif
903 {
904 goto err;
905 }
906
907 if(func != NULL) func(oldnode->item, param);
908
909 oldnode = oldnode->next;
910 node->next->prev = node;
911 node = node->next;
912 }
913
914 list->tail = node;
915 dlist_assert(list);
916
917 return list;
918
919 err:
920 dlist_free(list);
921 return NULL;
922 }
923
924 #ifndef DMALLOC
dlist_node_alloc(void * item)925 dlist_node_t *dlist_node_alloc(void *item)
926 {
927 return dlist_node(item, NULL, NULL);
928 }
929 #else
dlist_node_alloc_dm(void * item,const char * file,const int line)930 dlist_node_t *dlist_node_alloc_dm(void *item, const char *file, const int line)
931 {
932 return dlist_node(item, NULL, NULL, file, line);
933 }
934 #endif
935
dlist_flush(dlist_t * list,dlist_free_t free_func)936 static void dlist_flush(dlist_t *list, dlist_free_t free_func)
937 {
938 dlist_node_t *node;
939 dlist_node_t *next;
940
941 assert(list != NULL);
942 dlist_assert(list);
943 assert(list->lock == 0);
944
945 node = list->head;
946 while(node != NULL)
947 {
948 next = node->next;
949 if(list->onremove != NULL)
950 list->onremove(node->item);
951 if(free_func != NULL)
952 free_func(node->item);
953 free(node);
954 node = next;
955 }
956 return;
957 }
958
dlist_empty(dlist_t * list)959 void dlist_empty(dlist_t *list)
960 {
961 dlist_flush(list, NULL);
962 dlist_init(list);
963 return;
964 }
965
dlist_empty_cb(dlist_t * list,dlist_free_t func)966 void dlist_empty_cb(dlist_t *list, dlist_free_t func)
967 {
968 dlist_flush(list, func);
969 dlist_init(list);
970 return;
971 }
972
dlist_free(dlist_t * list)973 void dlist_free(dlist_t *list)
974 {
975 dlist_flush(list, NULL);
976 free(list);
977 return;
978 }
979
dlist_free_cb(dlist_t * list,dlist_free_t func)980 void dlist_free_cb(dlist_t *list, dlist_free_t func)
981 {
982 dlist_flush(list, func);
983 free(list);
984 return;
985 }
986
dlist_concat(dlist_t * first,dlist_t * second)987 void dlist_concat(dlist_t *first, dlist_t *second)
988 {
989 dlist_node_t *p;
990
991 assert(first != NULL);
992 assert(first->lock == 0);
993 assert(second != NULL);
994 assert(second->lock == 0);
995 dlist_assert(first);
996 dlist_assert(second);
997
998 /* if there's nothing to concatenate, then stop now */
999 if(second->head == NULL)
1000 return;
1001
1002 /* update the nodes in the second list to say they are now in the first */
1003 for(p = second->head; p != NULL; p = p->next)
1004 p->list = first;
1005
1006 /* shift the second list's nodes into the first */
1007 if(first->tail != NULL)
1008 {
1009 first->tail->next = second->head;
1010 second->head->prev = first->tail;
1011 first->tail = second->tail;
1012 first->length += second->length;
1013 }
1014 else
1015 {
1016 first->head = second->head;
1017 first->tail = second->tail;
1018 first->length = second->length;
1019 }
1020
1021 /* reset the second list */
1022 second->length = 0;
1023 second->head = NULL;
1024 second->tail = NULL;
1025
1026 return;
1027 }
1028
dlist_node_head_push(dlist_t * list,dlist_node_t * node)1029 void dlist_node_head_push(dlist_t *list, dlist_node_t *node)
1030 {
1031 dlist_onremove_t onremove = NULL;
1032
1033 assert(list != NULL);
1034 assert(list->lock == 0);
1035 assert(node != NULL);
1036 dlist_assert(list);
1037
1038 if(node->list != NULL)
1039 onremove = node->list->onremove;
1040
1041 /* eject the node from whatever list it is currently on */
1042 dlist_node_eject(node->list, node);
1043
1044 if(onremove != NULL)
1045 onremove(node->item);
1046
1047 /* if we don't have a head node, we don't have a tail node set either */
1048 if(list->head == NULL)
1049 list->tail = node;
1050 else
1051 list->head->prev = node;
1052
1053 /* the current head node will be second on the list */
1054 node->next = list->head;
1055 node->list = list;
1056
1057 list->head = node;
1058 list->length++;
1059
1060 dlist_assert(list);
1061
1062 return;
1063 }
1064
dlist_node_tail_push(dlist_t * list,dlist_node_t * node)1065 void dlist_node_tail_push(dlist_t *list, dlist_node_t *node)
1066 {
1067 dlist_onremove_t onremove = NULL;
1068
1069 assert(list != NULL);
1070 assert(list->lock == 0);
1071 assert(node != NULL);
1072 dlist_assert(list);
1073
1074 if(node->list != NULL)
1075 onremove = node->list->onremove;
1076
1077 /* eject the node from whatever list it is currently on */
1078 dlist_node_eject(node->list, node);
1079
1080 if(onremove != NULL)
1081 onremove(node->item);
1082
1083 /* if we don't have a tail node, we don't have a head node set either */
1084 if(list->tail == NULL)
1085 list->head = node;
1086 else
1087 list->tail->next = node;
1088
1089 /* the current tail node will be second to last on the list */
1090 node->prev = list->tail;
1091 node->list = list;
1092
1093 list->tail = node;
1094 list->length++;
1095
1096 dlist_assert(list);
1097
1098 return;
1099 }
1100
1101 #ifndef DMALLOC
dlist_head_push(dlist_t * list,void * item)1102 dlist_node_t *dlist_head_push(dlist_t *list, void *item)
1103 #else
1104 dlist_node_t *dlist_head_push_dm(dlist_t *list, void *item,
1105 const char *file, const int line)
1106 #endif
1107 {
1108 dlist_node_t *node;
1109
1110 assert(list != NULL);
1111 assert(list->lock == 0);
1112 dlist_assert(list);
1113
1114 #ifndef DMALLOC
1115 node = dlist_node(item, NULL, NULL);
1116 #else
1117 node = dlist_node(item, NULL, NULL, file, line);
1118 #endif
1119
1120 if(node == NULL)
1121 return NULL;
1122
1123 /* if we don't have a head node, we don't have a tail node set either */
1124 if(list->head == NULL)
1125 list->tail = node;
1126 else
1127 list->head->prev = node;
1128
1129 /* the current head node will be second on the list */
1130 node->next = list->head;
1131 node->list = list;
1132
1133 list->head = node;
1134 list->length++;
1135
1136 dlist_assert(list);
1137
1138 return node;
1139 }
1140
1141 #ifndef DMALLOC
dlist_tail_push(dlist_t * list,void * item)1142 dlist_node_t *dlist_tail_push(dlist_t *list, void *item)
1143 #else
1144 dlist_node_t *dlist_tail_push_dm(dlist_t *list, void *item,
1145 const char *file, const int line)
1146 #endif
1147 {
1148 dlist_node_t *node;
1149
1150 assert(list != NULL);
1151 assert(list->lock == 0);
1152 dlist_assert(list);
1153
1154 #ifndef DMALLOC
1155 node = dlist_node(item, NULL, NULL);
1156 #else
1157 node = dlist_node(item, NULL, NULL, file, line);
1158 #endif
1159
1160 if(node == NULL)
1161 return NULL;
1162
1163 /* if we don't have a tail node, we don't have a head node set either */
1164 if(list->tail == NULL)
1165 list->head = node;
1166 else
1167 list->tail->next = node;
1168
1169 /* the current tail node will be second to last on the list */
1170 node->prev = list->tail;
1171 node->list = list;
1172
1173 list->tail = node;
1174 list->length++;
1175
1176 dlist_assert(list);
1177
1178 return node;
1179 }
1180
dlist_head_pop(dlist_t * list)1181 void *dlist_head_pop(dlist_t *list)
1182 {
1183 dlist_node_t *node;
1184 void *item;
1185
1186 assert(list != NULL);
1187 assert(list->lock == 0);
1188 dlist_assert(list);
1189
1190 if(list->head == NULL)
1191 {
1192 return NULL;
1193 }
1194
1195 node = list->head;
1196 item = node->item;
1197
1198 /*
1199 * if we have a non-null node to replace the head with, null its prev
1200 * pointer as the node is now at the head of the list
1201 */
1202 if((list->head = node->next) != NULL)
1203 {
1204 list->head->prev = NULL;
1205 }
1206 else
1207 {
1208 /* no nodes left in list */
1209 list->tail = NULL;
1210 }
1211
1212 free(node);
1213 list->length--;
1214
1215 if(list->onremove != NULL)
1216 list->onremove(item);
1217
1218 dlist_assert(list);
1219
1220 return item;
1221 }
1222
dlist_tail_pop(dlist_t * list)1223 void *dlist_tail_pop(dlist_t *list)
1224 {
1225 dlist_node_t *node;
1226 void *item;
1227
1228 assert(list != NULL);
1229 assert(list->lock == 0);
1230 dlist_assert(list);
1231
1232 if(list->head == NULL)
1233 {
1234 return NULL;
1235 }
1236
1237 node = list->tail;
1238 item = node->item;
1239
1240 list->tail = node->prev;
1241
1242 if(list->tail != NULL)
1243 {
1244 list->tail->next = NULL;
1245 }
1246
1247 if(list->head == node)
1248 {
1249 list->head = NULL;
1250 }
1251
1252 free(node);
1253 list->length--;
1254
1255 if(list->onremove != NULL)
1256 list->onremove(item);
1257
1258 dlist_assert(list);
1259
1260 return item;
1261 }
1262
1263 /*
1264 * dlist_node_detach
1265 *
1266 * a node is on a list. detach it from the list, but do not free the
1267 * node.
1268 */
dlist_node_detach(dlist_t * list,dlist_node_t * node)1269 static void dlist_node_detach(dlist_t *list, dlist_node_t *node)
1270 {
1271 assert(node != NULL);
1272 assert(list == NULL || list->lock == 0);
1273 assert(node->list == list);
1274
1275 /* if the node is in the list, then we have to detach it */
1276 if(node->prev != NULL || node->next != NULL ||
1277 (list != NULL && list->head == node))
1278 {
1279 if(list != NULL)
1280 {
1281 if(list->head == node)
1282 list->head = node->next;
1283 if(list->tail == node)
1284 list->tail = node->prev;
1285 list->length--;
1286 }
1287
1288 if(node->prev != NULL) node->prev->next = node->next;
1289 if(node->next != NULL) node->next->prev = node->prev;
1290
1291 /* node has been detached, reset its pointers */
1292 node->next = NULL;
1293 node->prev = NULL;
1294 node->list = NULL;
1295 }
1296
1297 return;
1298 }
1299
1300 /*
1301 * dlist_node_pop
1302 *
1303 */
dlist_node_pop(dlist_t * list,dlist_node_t * node)1304 void *dlist_node_pop(dlist_t *list, dlist_node_t *node)
1305 {
1306 void *item;
1307
1308 assert(node != NULL);
1309 assert(node->list == list);
1310 assert(list == NULL || list->lock == 0);
1311 dlist_assert(list);
1312
1313 dlist_node_detach(list, node);
1314 item = node->item;
1315 free(node);
1316
1317 if(list != NULL && list->onremove != NULL)
1318 list->onremove(item);
1319
1320 dlist_assert(list);
1321
1322 return item;
1323 }
1324
dlist_node_item(const dlist_node_t * node)1325 void *dlist_node_item(const dlist_node_t *node)
1326 {
1327 assert(node != NULL);
1328 return node->item;
1329 }
1330
dlist_node_next(const dlist_node_t * node)1331 dlist_node_t *dlist_node_next(const dlist_node_t *node)
1332 {
1333 assert(node != NULL);
1334 return node->next;
1335 }
1336
dlist_node_prev(const dlist_node_t * node)1337 dlist_node_t *dlist_node_prev(const dlist_node_t *node)
1338 {
1339 assert(node != NULL);
1340 return node->prev;
1341 }
1342
1343 /*
1344 * dlist_node_eject
1345 *
1346 * remove a specified dlist_node from the list. do not actually free the
1347 * node structure itself, though.
1348 */
dlist_node_eject(dlist_t * list,dlist_node_t * node)1349 void dlist_node_eject(dlist_t *list, dlist_node_t *node)
1350 {
1351 assert(node != NULL);
1352 assert(list == NULL || list->lock == 0);
1353 assert(list == node->list);
1354 dlist_assert(list);
1355 dlist_node_detach(list, node);
1356 dlist_assert(list);
1357 return;
1358 }
1359
dlist_head_item(const dlist_t * list)1360 void *dlist_head_item(const dlist_t *list)
1361 {
1362 assert(list != NULL);
1363 if(list->head == NULL) return NULL;
1364 return list->head->item;
1365 }
1366
dlist_head_node(const dlist_t * list)1367 dlist_node_t *dlist_head_node(const dlist_t *list)
1368 {
1369 assert(list != NULL);
1370 return list->head;
1371 }
1372
dlist_tail_node(const dlist_t * list)1373 dlist_node_t *dlist_tail_node(const dlist_t *list)
1374 {
1375 assert(list != NULL);
1376 return list->tail;
1377 }
1378
dlist_tail_item(const dlist_t * list)1379 void *dlist_tail_item(const dlist_t *list)
1380 {
1381 assert(list != NULL);
1382 if(list->tail == NULL) return NULL;
1383 return list->tail->item;
1384 }
1385
dlist_foreach(dlist_t * list,const dlist_foreach_t func,void * param)1386 int dlist_foreach(dlist_t *list, const dlist_foreach_t func, void *param)
1387 {
1388 dlist_node_t *node, *next;
1389
1390 assert(list != NULL);
1391 assert(func != NULL);
1392
1393 dlist_lock(list);
1394 dlist_assert(list);
1395
1396 node = list->head;
1397 while(node != NULL)
1398 {
1399 next = node->next;
1400 if(func(node->item, param) != 0)
1401 {
1402 dlist_unlock(list);
1403 return -1;
1404 }
1405 node = next;
1406 }
1407
1408 dlist_assert(list);
1409 dlist_unlock(list);
1410
1411 return 0;
1412 }
1413
dlist_count(const dlist_t * list)1414 int dlist_count(const dlist_t *list)
1415 {
1416 assert(list != NULL);
1417 dlist_assert(list);
1418 return list->length;
1419 }
1420
dlist_swap(dlist_node_t ** a,int i,int j)1421 static void dlist_swap(dlist_node_t **a, int i, int j)
1422 {
1423 dlist_node_t *item = a[i];
1424 a[i] = a[j];
1425 a[j] = item;
1426 return;
1427 }
1428
dlist_node_array(const dlist_t * list)1429 static dlist_node_t **dlist_node_array(const dlist_t *list)
1430 {
1431 dlist_node_t **v = NULL, *n;
1432 int i = 0;
1433 assert(list->length >= 2);
1434 if((v = malloc(sizeof(dlist_node_t *) * list->length)) == NULL)
1435 return NULL;
1436 for(n = list->head; n != NULL; n = n->next)
1437 v[i++] = n;
1438 assert(i == list->length);
1439 return v;
1440 }
1441
dlist_rebuild(dlist_t * list,dlist_node_t ** v)1442 static void dlist_rebuild(dlist_t *list, dlist_node_t **v)
1443 {
1444 int i;
1445 list->head = v[0];
1446 list->tail = v[list->length-1];
1447 list->tail->next = NULL;
1448 list->head->prev = NULL;
1449 for(i=0; i<list->length; i++)
1450 {
1451 if(i > 0)
1452 v[i]->prev = v[i-1];
1453 if(i < list->length-1)
1454 v[i]->next = v[i+1];
1455 }
1456 dlist_assert(list);
1457 return;
1458 }
1459
1460 /*
1461 * dlist_qsort_3:
1462 *
1463 * recursive function that implements quicksort with a three-way partition
1464 * on an array of slist_node_t structures.
1465 */
dlist_qsort_3(dlist_node_t ** a,dlist_cmp_t cmp,int l,int r)1466 static void dlist_qsort_3(dlist_node_t **a, dlist_cmp_t cmp, int l, int r)
1467 {
1468 dlist_node_t *c;
1469 int i, lt, gt, rc;
1470
1471 if(l >= r)
1472 return;
1473
1474 c = a[l];
1475 lt = l;
1476 gt = r;
1477 i = l;
1478
1479 while(i <= gt)
1480 {
1481 rc = a[i]->item != c->item ? cmp(a[i]->item, c->item) : 0;
1482 if(rc < 0)
1483 dlist_swap(a, lt++, i++);
1484 else if(rc > 0)
1485 dlist_swap(a, i, gt--);
1486 else
1487 i++;
1488 }
1489
1490 dlist_qsort_3(a, cmp, l, lt-1);
1491 dlist_qsort_3(a, cmp, gt+1, r);
1492 return;
1493 }
1494
dlist_qsort(dlist_t * list,dlist_cmp_t cmp)1495 int dlist_qsort(dlist_t *list, dlist_cmp_t cmp)
1496 {
1497 dlist_node_t **v;
1498
1499 dlist_assert(list);
1500 assert(list->lock == 0);
1501
1502 /* don't have to order the list if there less than two items in it */
1503 if(list->length < 2)
1504 return 0;
1505
1506 if((v = dlist_node_array(list)) == NULL)
1507 return -1;
1508 dlist_qsort_3(v, cmp, 0, list->length-1);
1509 dlist_rebuild(list, v);
1510 free(v);
1511
1512 dlist_assert_sort(list, cmp);
1513 return 0;
1514 }
1515
dlist_shuffle(dlist_t * list)1516 int dlist_shuffle(dlist_t *list)
1517 {
1518 dlist_node_t **v;
1519 dlist_assert(list);
1520 assert(list->lock == 0);
1521 if(list->length < 2)
1522 return 0;
1523 if((v = dlist_node_array(list)) == NULL)
1524 return -1;
1525 shuffle_array((void **)v, list->length);
1526 dlist_rebuild(list, v);
1527 free(v);
1528 return 0;
1529 }
1530
1531 #if !defined(NDEBUG) && defined(MJLLIST_DEBUG)
clist_assert(const clist_t * list)1532 static void clist_assert(const clist_t *list)
1533 {
1534 clist_node_t *node;
1535 int i;
1536
1537 if(list == NULL)
1538 return;
1539
1540 assert(list->length >= 0);
1541
1542 if(list->length == 0)
1543 {
1544 assert(list->head == NULL);
1545 }
1546 else if(list->length == 1)
1547 {
1548 assert(list->head != NULL);
1549 assert(list->head->next == list->head);
1550 assert(list->head->prev == list->head);
1551 }
1552 else
1553 {
1554 i = 1; node = list->head;
1555 while(i < list->length)
1556 {
1557 assert(node != NULL);
1558 assert(node->next != NULL);
1559 assert(node->next->prev == node);
1560
1561 node = node->next;
1562 i++;
1563 }
1564
1565 assert(node->next == list->head);
1566 }
1567 return;
1568 }
1569 #else
1570 #define clist_assert(list)((void)0)
1571 #endif
1572
1573 #ifndef DMALLOC
clist_alloc(void)1574 clist_t *clist_alloc(void)
1575 #else
1576 clist_t *clist_alloc_dm(const char *file, const int line)
1577 #endif
1578 {
1579 clist_t *list;
1580 size_t len = sizeof(clist_t);
1581
1582 #ifndef DMALLOC
1583 list = malloc(len);
1584 #else
1585 list = dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
1586 #endif
1587
1588 if(list != NULL)
1589 {
1590 clist_init(list);
1591 }
1592
1593 return list;
1594 }
1595
clist_init(clist_t * list)1596 void clist_init(clist_t *list)
1597 {
1598 assert(list != NULL);
1599 list->head = NULL;
1600 list->length = 0;
1601 list->lock = 0;
1602 list->onremove = NULL;
1603 return;
1604 }
1605
clist_onremove(clist_t * list,clist_onremove_t onremove)1606 void clist_onremove(clist_t *list, clist_onremove_t onremove)
1607 {
1608 assert(list != NULL);
1609 list->onremove = onremove;
1610 return;
1611 }
1612
clist_lock(clist_t * list)1613 void clist_lock(clist_t *list)
1614 {
1615 assert(list != NULL);
1616 list->lock++;
1617 return;
1618 }
1619
clist_unlock(clist_t * list)1620 void clist_unlock(clist_t *list)
1621 {
1622 assert(list != NULL);
1623 assert(list->lock > 0);
1624 list->lock--;
1625 return;
1626 }
1627
clist_islocked(clist_t * list)1628 int clist_islocked(clist_t *list)
1629 {
1630 assert(list != NULL);
1631 return list->lock == 0 ? 0 : 1;
1632 }
1633
clist_flush(clist_t * list,clist_free_t free_func)1634 static void clist_flush(clist_t *list, clist_free_t free_func)
1635 {
1636 clist_node_t *node;
1637 clist_node_t *next;
1638
1639 assert(list != NULL);
1640 clist_assert(list);
1641
1642 if((node = list->head) == NULL)
1643 return;
1644
1645 /* break the circle */
1646 list->head->prev->next = NULL;
1647
1648 /* delete all the nodes */
1649 while(node != NULL)
1650 {
1651 next = node->next;
1652 if(list->onremove)
1653 list->onremove(node->item);
1654 if(free_func != NULL)
1655 free_func(node->item);
1656 free(node);
1657 node = next;
1658 }
1659
1660 return;
1661 }
1662
clist_free(clist_t * list)1663 void clist_free(clist_t *list)
1664 {
1665 clist_flush(list, NULL);
1666 free(list);
1667 return;
1668 }
1669
clist_free_cb(clist_t * list,clist_free_t func)1670 void clist_free_cb(clist_t *list, clist_free_t func)
1671 {
1672 clist_flush(list, func);
1673 free(list);
1674 return;
1675 }
1676
1677 #ifndef DMALLOC
clist_tail_push(clist_t * list,void * item)1678 clist_node_t *clist_tail_push(clist_t *list, void *item)
1679 #else
1680 clist_node_t *clist_tail_push_dm(clist_t *list, void *item,
1681 const char *file, const int line)
1682 #endif
1683 {
1684 clist_node_t *node, *tail;
1685 size_t len = sizeof(clist_node_t);
1686
1687 assert(list != NULL);
1688 clist_assert(list);
1689
1690 #ifndef DMALLOC
1691 node = malloc(len);
1692 #else
1693 node = dmalloc_malloc(file, line, len, DMALLOC_FUNC_MALLOC, 0, 0);
1694 #endif
1695
1696 if(node == NULL)
1697 {
1698 return NULL;
1699 }
1700 node->item = item;
1701
1702 if(list->head != NULL)
1703 {
1704 tail = list->head->prev;
1705
1706 node->prev = tail;
1707 node->next = list->head;
1708
1709 tail->next = node;
1710 list->head->prev = node;
1711 }
1712 else
1713 {
1714 list->head = node;
1715 node->prev = node->next = node;
1716 }
1717
1718 list->length++;
1719
1720 clist_assert(list);
1721
1722 return node;
1723 }
1724
clist_head_push(clist_t * list,void * item)1725 clist_node_t *clist_head_push(clist_t *list, void *item)
1726 {
1727 clist_node_t *node;
1728
1729 assert(list != NULL);
1730 if((node = clist_tail_push(list, item)) != NULL)
1731 {
1732 list->head = node;
1733 }
1734
1735 return node;
1736 }
1737
clist_head_item(const clist_t * list)1738 void *clist_head_item(const clist_t *list)
1739 {
1740 assert(list != NULL);
1741 if(list->head == NULL) return NULL;
1742 return list->head->item;
1743 }
1744
clist_head_node(const clist_t * list)1745 clist_node_t *clist_head_node(const clist_t *list)
1746 {
1747 assert(list != NULL);
1748 return list->head;
1749 }
1750
clist_tail_item(const clist_t * list)1751 void *clist_tail_item(const clist_t *list)
1752 {
1753 assert(list != NULL);
1754 if(list->head == NULL) return NULL;
1755 return list->head->prev->item;
1756 }
1757
clist_node_pop(clist_t * list,clist_node_t * node)1758 void *clist_node_pop(clist_t *list, clist_node_t *node)
1759 {
1760 void *item;
1761
1762 assert(list != NULL);
1763 assert(list->lock == 0);
1764 clist_assert(list);
1765
1766 item = node->item;
1767
1768 if(node == node->prev)
1769 {
1770 list->head = NULL;
1771 }
1772 else
1773 {
1774 if(list->head == node)
1775 {
1776 list->head = node->next;
1777 }
1778 node->prev->next = node->next;
1779 node->next->prev = node->prev;
1780 }
1781
1782 free(node);
1783 list->length--;
1784
1785 if(list->onremove != NULL)
1786 list->onremove(item);
1787
1788 clist_assert(list);
1789
1790 return item;
1791 }
1792
clist_tail_pop(clist_t * list)1793 void *clist_tail_pop(clist_t *list)
1794 {
1795 assert(list != NULL);
1796 if(list->head == NULL)
1797 {
1798 return NULL;
1799 }
1800
1801 return clist_node_pop(list, list->head->prev);
1802 }
1803
clist_head_pop(clist_t * list)1804 void *clist_head_pop(clist_t *list)
1805 {
1806 assert(list != NULL);
1807 if(list->head == NULL)
1808 {
1809 return NULL;
1810 }
1811
1812 return clist_node_pop(list, list->head);
1813 }
1814
clist_node_item(const clist_node_t * node)1815 void *clist_node_item(const clist_node_t *node)
1816 {
1817 assert(node != NULL);
1818 return node->item;
1819 }
1820
clist_node_next(const clist_node_t * node)1821 clist_node_t *clist_node_next(const clist_node_t *node)
1822 {
1823 assert(node != NULL);
1824 return node->next;
1825 }
1826
clist_head_left(clist_t * list)1827 clist_node_t *clist_head_left(clist_t *list)
1828 {
1829 assert(list != NULL);
1830 if(list->head == NULL)
1831 {
1832 return NULL;
1833 }
1834
1835 list->head = list->head->prev;
1836 return list->head;
1837 }
1838
clist_head_right(clist_t * list)1839 clist_node_t *clist_head_right(clist_t *list)
1840 {
1841 assert(list != NULL);
1842 if(list->head == NULL)
1843 {
1844 return NULL;
1845 }
1846
1847 list->head = list->head->next;
1848 return list->head;
1849 }
1850
clist_foreach(clist_t * list,const clist_foreach_t func,void * param)1851 int clist_foreach(clist_t *list, const clist_foreach_t func, void *param)
1852 {
1853 clist_node_t *node;
1854 clist_node_t *next;
1855
1856 assert(list != NULL);
1857 clist_lock(list);
1858 clist_assert(list);
1859
1860 node = list->head;
1861 if(node == NULL)
1862 {
1863 clist_unlock(list);
1864 return 0;
1865 }
1866
1867 for(;;)
1868 {
1869 next = node->next;
1870 if(func(node->item, param) != 0)
1871 {
1872 clist_unlock(list);
1873 return -1;
1874 }
1875
1876 if(next != list->head)
1877 {
1878 node = next;
1879 }
1880 else break;
1881 }
1882
1883 clist_assert(list);
1884 clist_unlock(list);
1885
1886 return 0;
1887 }
1888
clist_count(const clist_t * list)1889 int clist_count(const clist_t *list)
1890 {
1891 assert(list != NULL);
1892 clist_assert(list);
1893 return list->length;
1894 }
1895