This source file includes following definitions.
- gl_linked_nx_create_empty
- gl_linked_nx_create
- gl_linked_size
- gl_linked_node_value
- gl_linked_node_nx_set_value
- gl_linked_next_node
- gl_linked_previous_node
- gl_linked_first_node
- gl_linked_last_node
- gl_linked_get_at
- gl_linked_nx_set_at
- gl_linked_search_from_to
- gl_linked_indexof_from_to
- gl_linked_nx_add_first
- gl_linked_nx_add_last
- gl_linked_nx_add_before
- gl_linked_nx_add_after
- gl_linked_nx_add_at
- gl_linked_remove_node
- gl_linked_remove_at
- gl_linked_remove
- gl_linked_list_free
- gl_linked_iterator
- gl_linked_iterator_from_to
- gl_linked_iterator_next
- gl_linked_iterator_free
- gl_linked_sortedlist_search
- gl_linked_sortedlist_search_from_to
- gl_linked_sortedlist_indexof
- gl_linked_sortedlist_indexof_from_to
- gl_linked_sortedlist_nx_add
- gl_linked_sortedlist_remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 #ifdef SIGNAL_SAFE_LIST
32 # define ASYNCSAFE(type) *(type volatile *)&
33 #else
34 # define ASYNCSAFE(type)
35 #endif
36
37
38
39 static gl_list_t
40 gl_linked_nx_create_empty (gl_list_implementation_t implementation,
41 gl_listelement_equals_fn equals_fn,
42 gl_listelement_hashcode_fn hashcode_fn,
43 gl_listelement_dispose_fn dispose_fn,
44 bool allow_duplicates)
45 {
46 struct gl_list_impl *list =
47 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
48
49 if (list == NULL)
50 return NULL;
51
52 list->base.vtable = implementation;
53 list->base.equals_fn = equals_fn;
54 list->base.hashcode_fn = hashcode_fn;
55 list->base.dispose_fn = dispose_fn;
56 list->base.allow_duplicates = allow_duplicates;
57 #if WITH_HASHTABLE
58 list->table_size = 11;
59 list->table =
60 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
61 if (list->table == NULL)
62 goto fail;
63 #endif
64 list->root.next = &list->root;
65 list->root.prev = &list->root;
66 list->count = 0;
67
68 return list;
69
70 #if WITH_HASHTABLE
71 fail:
72 free (list);
73 return NULL;
74 #endif
75 }
76
77 static gl_list_t
78 gl_linked_nx_create (gl_list_implementation_t implementation,
79 gl_listelement_equals_fn equals_fn,
80 gl_listelement_hashcode_fn hashcode_fn,
81 gl_listelement_dispose_fn dispose_fn,
82 bool allow_duplicates,
83 size_t count, const void **contents)
84 {
85 struct gl_list_impl *list =
86 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
87 gl_list_node_t tail;
88
89 if (list == NULL)
90 return NULL;
91
92 list->base.vtable = implementation;
93 list->base.equals_fn = equals_fn;
94 list->base.hashcode_fn = hashcode_fn;
95 list->base.dispose_fn = dispose_fn;
96 list->base.allow_duplicates = allow_duplicates;
97 #if WITH_HASHTABLE
98 {
99 size_t estimate = xsum (count, count / 2);
100 if (estimate < 10)
101 estimate = 10;
102 list->table_size = next_prime (estimate);
103 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
104 goto fail1;
105 list->table =
106 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
107 if (list->table == NULL)
108 goto fail1;
109 }
110 #endif
111 list->count = count;
112 tail = &list->root;
113 for (; count > 0; contents++, count--)
114 {
115 gl_list_node_t node =
116 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
117
118 if (node == NULL)
119 goto fail2;
120
121 node->value = *contents;
122 #if WITH_HASHTABLE
123 node->h.hashcode =
124 (list->base.hashcode_fn != NULL
125 ? list->base.hashcode_fn (node->value)
126 : (size_t)(uintptr_t) node->value);
127
128
129 if (add_to_bucket (list, node) < 0)
130 {
131 free (node);
132 goto fail2;
133 }
134 #endif
135
136
137 node->prev = tail;
138 tail->next = node;
139 tail = node;
140 }
141 tail->next = &list->root;
142 list->root.prev = tail;
143
144 return list;
145
146 fail2:
147 {
148 gl_list_node_t node;
149
150 for (node = tail; node != &list->root; )
151 {
152 gl_list_node_t prev = node->prev;
153
154 free (node);
155 node = prev;
156 }
157 }
158 #if WITH_HASHTABLE
159 free (list->table);
160 fail1:
161 #endif
162 free (list);
163 return NULL;
164 }
165
166 static size_t _GL_ATTRIBUTE_PURE
167 gl_linked_size (gl_list_t list)
168 {
169 return list->count;
170 }
171
172 static const void * _GL_ATTRIBUTE_PURE
173 gl_linked_node_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
174 gl_list_node_t node)
175 {
176 return node->value;
177 }
178
179 static int
180 gl_linked_node_nx_set_value (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_t list,
181 gl_list_node_t node,
182 const void *elt)
183 {
184 #if WITH_HASHTABLE
185 if (elt != node->value)
186 {
187 size_t new_hashcode =
188 (list->base.hashcode_fn != NULL
189 ? list->base.hashcode_fn (elt)
190 : (size_t)(uintptr_t) elt);
191
192 if (new_hashcode != node->h.hashcode)
193 {
194 remove_from_bucket (list, node);
195 node->value = elt;
196 node->h.hashcode = new_hashcode;
197 if (add_to_bucket (list, node) < 0)
198 {
199
200
201
202 gl_list_node_t before_removed = node->prev;
203 gl_list_node_t after_removed = node->next;
204 ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
205 after_removed->prev = before_removed;
206 list->count--;
207 free (node);
208 return -1;
209 }
210 }
211 else
212 node->value = elt;
213 }
214 #else
215 node->value = elt;
216 #endif
217 return 0;
218 }
219
220 static gl_list_node_t _GL_ATTRIBUTE_PURE
221 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
222 {
223 return (node->next != &list->root ? node->next : NULL);
224 }
225
226 static gl_list_node_t _GL_ATTRIBUTE_PURE
227 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
228 {
229 return (node->prev != &list->root ? node->prev : NULL);
230 }
231
232 static gl_list_node_t _GL_ATTRIBUTE_PURE
233 gl_linked_first_node (gl_list_t list)
234 {
235 if (list->count > 0)
236 return list->root.next;
237 else
238 return NULL;
239 }
240
241 static gl_list_node_t _GL_ATTRIBUTE_PURE
242 gl_linked_last_node (gl_list_t list)
243 {
244 if (list->count > 0)
245 return list->root.prev;
246 else
247 return NULL;
248 }
249
250 static const void * _GL_ATTRIBUTE_PURE
251 gl_linked_get_at (gl_list_t list, size_t position)
252 {
253 size_t count = list->count;
254 gl_list_node_t node;
255
256 if (!(position < count))
257
258 abort ();
259
260 if (position <= ((count - 1) / 2))
261 {
262 node = list->root.next;
263 for (; position > 0; position--)
264 node = node->next;
265 }
266 else
267 {
268 position = count - 1 - position;
269 node = list->root.prev;
270 for (; position > 0; position--)
271 node = node->prev;
272 }
273 return node->value;
274 }
275
276 static gl_list_node_t
277 gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt)
278 {
279 size_t count = list->count;
280 gl_list_node_t node;
281
282 if (!(position < count))
283
284 abort ();
285
286 if (position <= ((count - 1) / 2))
287 {
288 node = list->root.next;
289 for (; position > 0; position--)
290 node = node->next;
291 }
292 else
293 {
294 position = count - 1 - position;
295 node = list->root.prev;
296 for (; position > 0; position--)
297 node = node->prev;
298 }
299 #if WITH_HASHTABLE
300 if (elt != node->value)
301 {
302 size_t new_hashcode =
303 (list->base.hashcode_fn != NULL
304 ? list->base.hashcode_fn (elt)
305 : (size_t)(uintptr_t) elt);
306
307 if (new_hashcode != node->h.hashcode)
308 {
309 remove_from_bucket (list, node);
310 node->value = elt;
311 node->h.hashcode = new_hashcode;
312 if (add_to_bucket (list, node) < 0)
313 {
314
315
316
317 gl_list_node_t before_removed = node->prev;
318 gl_list_node_t after_removed = node->next;
319 ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed;
320 after_removed->prev = before_removed;
321 list->count--;
322 free (node);
323 return NULL;
324 }
325 }
326 else
327 node->value = elt;
328 }
329 #else
330 node->value = elt;
331 #endif
332 return node;
333 }
334
335 static gl_list_node_t _GL_ATTRIBUTE_PURE
336 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
337 const void *elt)
338 {
339 size_t count = list->count;
340
341 if (!(start_index <= end_index && end_index <= count))
342
343 abort ();
344 {
345 #if WITH_HASHTABLE
346 size_t hashcode =
347 (list->base.hashcode_fn != NULL
348 ? list->base.hashcode_fn (elt)
349 : (size_t)(uintptr_t) elt);
350 size_t bucket = hashcode % list->table_size;
351 gl_listelement_equals_fn equals = list->base.equals_fn;
352
353 if (!list->base.allow_duplicates)
354 {
355
356 gl_list_node_t found = NULL;
357 gl_list_node_t node;
358
359 for (node = (gl_list_node_t) list->table[bucket];
360 node != NULL;
361 node = (gl_list_node_t) node->h.hash_next)
362 if (node->h.hashcode == hashcode
363 && (equals != NULL
364 ? equals (elt, node->value)
365 : elt == node->value))
366 {
367 found = node;
368 break;
369 }
370 if (start_index > 0)
371
372 for (node = list->root.next; ; node = node->next)
373 {
374 if (node == found)
375 return NULL;
376 if (--start_index == 0)
377 break;
378 }
379 if (end_index < count)
380
381 {
382 end_index = count - end_index;
383 for (node = list->root.prev; ; node = node->prev)
384 {
385 if (node == found)
386 return NULL;
387 if (--end_index == 0)
388 break;
389 }
390 }
391 return found;
392 }
393 else
394 {
395
396 bool multiple_matches = false;
397 gl_list_node_t first_match = NULL;
398 gl_list_node_t node;
399
400 for (node = (gl_list_node_t) list->table[bucket];
401 node != NULL;
402 node = (gl_list_node_t) node->h.hash_next)
403 if (node->h.hashcode == hashcode
404 && (equals != NULL
405 ? equals (elt, node->value)
406 : elt == node->value))
407 {
408 if (first_match == NULL)
409 first_match = node;
410 else
411 {
412 multiple_matches = true;
413 break;
414 }
415 }
416 if (multiple_matches)
417 {
418
419
420 end_index -= start_index;
421 node = list->root.next;
422 for (; start_index > 0; start_index--)
423 node = node->next;
424
425 for (;
426 end_index > 0;
427 node = node->next, end_index--)
428 if (node->h.hashcode == hashcode
429 && (equals != NULL
430 ? equals (elt, node->value)
431 : elt == node->value))
432 return node;
433
434
435 return NULL;
436 }
437 else
438 {
439 if (start_index > 0)
440
441 for (node = list->root.next; node != &list->root; node = node->next)
442 {
443 if (node == first_match)
444 return NULL;
445 if (--start_index == 0)
446 break;
447 }
448 if (end_index < list->count)
449
450 {
451 end_index = list->count - end_index;
452 for (node = list->root.prev; ; node = node->prev)
453 {
454 if (node == first_match)
455 return NULL;
456 if (--end_index == 0)
457 break;
458 }
459 }
460 return first_match;
461 }
462 }
463 #else
464 gl_listelement_equals_fn equals = list->base.equals_fn;
465 gl_list_node_t node = list->root.next;
466
467 end_index -= start_index;
468 for (; start_index > 0; start_index--)
469 node = node->next;
470
471 if (equals != NULL)
472 {
473 for (; end_index > 0; node = node->next, end_index--)
474 if (equals (elt, node->value))
475 return node;
476 }
477 else
478 {
479 for (; end_index > 0; node = node->next, end_index--)
480 if (elt == node->value)
481 return node;
482 }
483 return NULL;
484 #endif
485 }
486 }
487
488 static size_t _GL_ATTRIBUTE_PURE
489 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
490 const void *elt)
491 {
492 size_t count = list->count;
493
494 if (!(start_index <= end_index && end_index <= count))
495
496 abort ();
497 {
498 #if WITH_HASHTABLE
499
500
501
502 size_t hashcode =
503 (list->base.hashcode_fn != NULL
504 ? list->base.hashcode_fn (elt)
505 : (size_t)(uintptr_t) elt);
506 size_t bucket = hashcode % list->table_size;
507 gl_listelement_equals_fn equals = list->base.equals_fn;
508 gl_list_node_t node;
509
510
511 if (!list->base.allow_duplicates)
512 {
513
514 for (node = (gl_list_node_t) list->table[bucket];
515 node != NULL;
516 node = (gl_list_node_t) node->h.hash_next)
517 if (node->h.hashcode == hashcode
518 && (equals != NULL
519 ? equals (elt, node->value)
520 : elt == node->value))
521 break;
522 }
523 else
524 {
525
526 bool multiple_matches = false;
527 gl_list_node_t first_match = NULL;
528
529 for (node = (gl_list_node_t) list->table[bucket];
530 node != NULL;
531 node = (gl_list_node_t) node->h.hash_next)
532 if (node->h.hashcode == hashcode
533 && (equals != NULL
534 ? equals (elt, node->value)
535 : elt == node->value))
536 {
537 if (first_match == NULL)
538 first_match = node;
539 else
540 {
541 multiple_matches = true;
542 break;
543 }
544 }
545 if (multiple_matches)
546 {
547
548
549 size_t index;
550
551 index = start_index;
552 node = list->root.next;
553 for (; start_index > 0; start_index--)
554 node = node->next;
555
556 for (;
557 index < end_index;
558 node = node->next, index++)
559 if (node->h.hashcode == hashcode
560 && (equals != NULL
561 ? equals (elt, node->value)
562 : elt == node->value))
563 return index;
564
565
566 return (size_t)(-1);
567 }
568 node = first_match;
569 }
570
571
572 if (node == NULL)
573 return (size_t)(-1);
574 else
575 {
576 size_t index = 0;
577
578 for (; node->prev != &list->root; node = node->prev)
579 index++;
580
581 if (index >= start_index && index < end_index)
582 return index;
583 else
584 return (size_t)(-1);
585 }
586 #else
587 gl_listelement_equals_fn equals = list->base.equals_fn;
588 size_t index = start_index;
589 gl_list_node_t node = list->root.next;
590
591 for (; start_index > 0; start_index--)
592 node = node->next;
593
594 if (equals != NULL)
595 {
596 for (;
597 index < end_index;
598 node = node->next, index++)
599 if (equals (elt, node->value))
600 return index;
601 }
602 else
603 {
604 for (;
605 index < end_index;
606 node = node->next, index++)
607 if (elt == node->value)
608 return index;
609 }
610 return (size_t)(-1);
611 #endif
612 }
613 }
614
615 static gl_list_node_t
616 gl_linked_nx_add_first (gl_list_t list, const void *elt)
617 {
618 gl_list_node_t node =
619 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
620
621 if (node == NULL)
622 return NULL;
623
624 ASYNCSAFE(const void *) node->value = elt;
625 #if WITH_HASHTABLE
626 node->h.hashcode =
627 (list->base.hashcode_fn != NULL
628 ? list->base.hashcode_fn (node->value)
629 : (size_t)(uintptr_t) node->value);
630
631
632 if (add_to_bucket (list, node) < 0)
633 {
634 free (node);
635 return NULL;
636 }
637 #endif
638
639
640 node->prev = &list->root;
641 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
642 node->next->prev = node;
643 ASYNCSAFE(gl_list_node_t) list->root.next = node;
644 list->count++;
645
646 #if WITH_HASHTABLE
647 hash_resize_after_add (list);
648 #endif
649
650 return node;
651 }
652
653 static gl_list_node_t
654 gl_linked_nx_add_last (gl_list_t list, const void *elt)
655 {
656 gl_list_node_t node =
657 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
658
659 if (node == NULL)
660 return NULL;
661
662 ASYNCSAFE(const void *) node->value = elt;
663 #if WITH_HASHTABLE
664 node->h.hashcode =
665 (list->base.hashcode_fn != NULL
666 ? list->base.hashcode_fn (node->value)
667 : (size_t)(uintptr_t) node->value);
668
669
670 if (add_to_bucket (list, node) < 0)
671 {
672 free (node);
673 return NULL;
674 }
675 #endif
676
677
678 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
679 node->prev = list->root.prev;
680 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
681 list->root.prev = node;
682 list->count++;
683
684 #if WITH_HASHTABLE
685 hash_resize_after_add (list);
686 #endif
687
688 return node;
689 }
690
691 static gl_list_node_t
692 gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
693 {
694 gl_list_node_t new_node =
695 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
696
697 if (new_node == NULL)
698 return NULL;
699
700 ASYNCSAFE(const void *) new_node->value = elt;
701 #if WITH_HASHTABLE
702 new_node->h.hashcode =
703 (list->base.hashcode_fn != NULL
704 ? list->base.hashcode_fn (new_node->value)
705 : (size_t)(uintptr_t) new_node->value);
706
707
708 if (add_to_bucket (list, new_node) < 0)
709 {
710 free (new_node);
711 return NULL;
712 }
713 #endif
714
715
716 ASYNCSAFE(gl_list_node_t) new_node->next = node;
717 new_node->prev = node->prev;
718 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
719 node->prev = new_node;
720 list->count++;
721
722 #if WITH_HASHTABLE
723 hash_resize_after_add (list);
724 #endif
725
726 return new_node;
727 }
728
729 static gl_list_node_t
730 gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
731 {
732 gl_list_node_t new_node =
733 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
734
735 if (new_node == NULL)
736 return NULL;
737
738 ASYNCSAFE(const void *) new_node->value = elt;
739 #if WITH_HASHTABLE
740 new_node->h.hashcode =
741 (list->base.hashcode_fn != NULL
742 ? list->base.hashcode_fn (new_node->value)
743 : (size_t)(uintptr_t) new_node->value);
744
745
746 if (add_to_bucket (list, new_node) < 0)
747 {
748 free (new_node);
749 return NULL;
750 }
751 #endif
752
753
754 new_node->prev = node;
755 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
756 new_node->next->prev = new_node;
757 ASYNCSAFE(gl_list_node_t) node->next = new_node;
758 list->count++;
759
760 #if WITH_HASHTABLE
761 hash_resize_after_add (list);
762 #endif
763
764 return new_node;
765 }
766
767 static gl_list_node_t
768 gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt)
769 {
770 size_t count = list->count;
771 gl_list_node_t new_node;
772
773 if (!(position <= count))
774
775 abort ();
776
777 new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
778 if (new_node == NULL)
779 return NULL;
780
781 ASYNCSAFE(const void *) new_node->value = elt;
782 #if WITH_HASHTABLE
783 new_node->h.hashcode =
784 (list->base.hashcode_fn != NULL
785 ? list->base.hashcode_fn (new_node->value)
786 : (size_t)(uintptr_t) new_node->value);
787
788
789 if (add_to_bucket (list, new_node) < 0)
790 {
791 free (new_node);
792 return NULL;
793 }
794 #endif
795
796
797 if (position <= (count / 2))
798 {
799 gl_list_node_t node;
800
801 node = &list->root;
802 for (; position > 0; position--)
803 node = node->next;
804 new_node->prev = node;
805 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
806 new_node->next->prev = new_node;
807 ASYNCSAFE(gl_list_node_t) node->next = new_node;
808 }
809 else
810 {
811 gl_list_node_t node;
812
813 position = count - position;
814 node = &list->root;
815 for (; position > 0; position--)
816 node = node->prev;
817 ASYNCSAFE(gl_list_node_t) new_node->next = node;
818 new_node->prev = node->prev;
819 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
820 node->prev = new_node;
821 }
822 list->count++;
823
824 #if WITH_HASHTABLE
825 hash_resize_after_add (list);
826 #endif
827
828 return new_node;
829 }
830
831 static bool
832 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
833 {
834 gl_list_node_t prev;
835 gl_list_node_t next;
836
837 #if WITH_HASHTABLE
838
839 remove_from_bucket (list, node);
840 #endif
841
842
843 prev = node->prev;
844 next = node->next;
845
846 ASYNCSAFE(gl_list_node_t) prev->next = next;
847 next->prev = prev;
848 list->count--;
849
850 if (list->base.dispose_fn != NULL)
851 list->base.dispose_fn (node->value);
852 free (node);
853 return true;
854 }
855
856 static bool
857 gl_linked_remove_at (gl_list_t list, size_t position)
858 {
859 size_t count = list->count;
860 gl_list_node_t removed_node;
861
862 if (!(position < count))
863
864 abort ();
865
866 if (position <= ((count - 1) / 2))
867 {
868 gl_list_node_t node;
869 gl_list_node_t after_removed;
870
871 node = &list->root;
872 for (; position > 0; position--)
873 node = node->next;
874 removed_node = node->next;
875 after_removed = node->next->next;
876 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
877 after_removed->prev = node;
878 }
879 else
880 {
881 gl_list_node_t node;
882 gl_list_node_t before_removed;
883
884 position = count - 1 - position;
885 node = &list->root;
886 for (; position > 0; position--)
887 node = node->prev;
888 removed_node = node->prev;
889 before_removed = node->prev->prev;
890 node->prev = before_removed;
891 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
892 }
893 #if WITH_HASHTABLE
894 remove_from_bucket (list, removed_node);
895 #endif
896 list->count--;
897
898 if (list->base.dispose_fn != NULL)
899 list->base.dispose_fn (removed_node->value);
900 free (removed_node);
901 return true;
902 }
903
904 static bool
905 gl_linked_remove (gl_list_t list, const void *elt)
906 {
907 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
908
909 if (node != NULL)
910 return gl_linked_remove_node (list, node);
911 else
912 return false;
913 }
914
915 static void
916 gl_linked_list_free (gl_list_t list)
917 {
918 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
919 gl_list_node_t node;
920
921 for (node = list->root.next; node != &list->root; )
922 {
923 gl_list_node_t next = node->next;
924 if (dispose != NULL)
925 dispose (node->value);
926 free (node);
927 node = next;
928 }
929 #if WITH_HASHTABLE
930 free (list->table);
931 #endif
932 free (list);
933 }
934
935
936
937 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
938 gl_linked_iterator (gl_list_t list)
939 {
940 gl_list_iterator_t result;
941
942 result.vtable = list->base.vtable;
943 result.list = list;
944 result.p = list->root.next;
945 result.q = &list->root;
946 #if defined GCC_LINT || defined lint
947 result.i = 0;
948 result.j = 0;
949 result.count = 0;
950 #endif
951
952 return result;
953 }
954
955 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
956 gl_linked_iterator_from_to (gl_list_t list,
957 size_t start_index, size_t end_index)
958 {
959 gl_list_iterator_t result;
960 size_t n1, n2, n3;
961
962 if (!(start_index <= end_index && end_index <= list->count))
963
964 abort ();
965 result.vtable = list->base.vtable;
966 result.list = list;
967 n1 = start_index;
968 n2 = end_index - start_index;
969 n3 = list->count - end_index;
970
971
972 if (n1 > n2 && n1 > n3)
973 {
974
975 gl_list_node_t node;
976 size_t i;
977
978 node = &list->root;
979 for (i = n3; i > 0; i--)
980 node = node->prev;
981 result.q = node;
982 for (i = n2; i > 0; i--)
983 node = node->prev;
984 result.p = node;
985 }
986 else if (n2 > n3)
987 {
988
989 gl_list_node_t node;
990 size_t i;
991
992 node = list->root.next;
993 for (i = n1; i > 0; i--)
994 node = node->next;
995 result.p = node;
996
997 node = &list->root;
998 for (i = n3; i > 0; i--)
999 node = node->prev;
1000 result.q = node;
1001 }
1002 else
1003 {
1004
1005 gl_list_node_t node;
1006 size_t i;
1007
1008 node = list->root.next;
1009 for (i = n1; i > 0; i--)
1010 node = node->next;
1011 result.p = node;
1012 for (i = n2; i > 0; i--)
1013 node = node->next;
1014 result.q = node;
1015 }
1016
1017 #if defined GCC_LINT || defined lint
1018 result.i = 0;
1019 result.j = 0;
1020 result.count = 0;
1021 #endif
1022
1023 return result;
1024 }
1025
1026 static bool
1027 gl_linked_iterator_next (gl_list_iterator_t *iterator,
1028 const void **eltp, gl_list_node_t *nodep)
1029 {
1030 if (iterator->p != iterator->q)
1031 {
1032 gl_list_node_t node = (gl_list_node_t) iterator->p;
1033 *eltp = node->value;
1034 if (nodep != NULL)
1035 *nodep = node;
1036 iterator->p = node->next;
1037 return true;
1038 }
1039 else
1040 return false;
1041 }
1042
1043 static void
1044 gl_linked_iterator_free (_GL_ATTRIBUTE_MAYBE_UNUSED gl_list_iterator_t *iterator)
1045 {
1046 }
1047
1048
1049
1050 static gl_list_node_t _GL_ATTRIBUTE_PURE
1051 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
1052 const void *elt)
1053 {
1054 gl_list_node_t node;
1055
1056 for (node = list->root.next; node != &list->root; node = node->next)
1057 {
1058 int cmp = compar (node->value, elt);
1059
1060 if (cmp > 0)
1061 break;
1062 if (cmp == 0)
1063 return node;
1064 }
1065 return NULL;
1066 }
1067
1068 static gl_list_node_t _GL_ATTRIBUTE_PURE
1069 gl_linked_sortedlist_search_from_to (gl_list_t list,
1070 gl_listelement_compar_fn compar,
1071 size_t low, size_t high,
1072 const void *elt)
1073 {
1074 size_t count = list->count;
1075
1076 if (!(low <= high && high <= list->count))
1077
1078 abort ();
1079
1080 high -= low;
1081 if (high > 0)
1082 {
1083
1084 size_t position = low;
1085 gl_list_node_t node;
1086
1087 if (position <= ((count - 1) / 2))
1088 {
1089 node = list->root.next;
1090 for (; position > 0; position--)
1091 node = node->next;
1092 }
1093 else
1094 {
1095 position = count - 1 - position;
1096 node = list->root.prev;
1097 for (; position > 0; position--)
1098 node = node->prev;
1099 }
1100
1101 do
1102 {
1103 int cmp = compar (node->value, elt);
1104
1105 if (cmp > 0)
1106 break;
1107 if (cmp == 0)
1108 return node;
1109 node = node->next;
1110 }
1111 while (--high > 0);
1112 }
1113 return NULL;
1114 }
1115
1116 static size_t _GL_ATTRIBUTE_PURE
1117 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
1118 const void *elt)
1119 {
1120 gl_list_node_t node;
1121 size_t index;
1122
1123 for (node = list->root.next, index = 0;
1124 node != &list->root;
1125 node = node->next, index++)
1126 {
1127 int cmp = compar (node->value, elt);
1128
1129 if (cmp > 0)
1130 break;
1131 if (cmp == 0)
1132 return index;
1133 }
1134 return (size_t)(-1);
1135 }
1136
1137 static size_t _GL_ATTRIBUTE_PURE
1138 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
1139 gl_listelement_compar_fn compar,
1140 size_t low, size_t high,
1141 const void *elt)
1142 {
1143 size_t count = list->count;
1144
1145 if (!(low <= high && high <= list->count))
1146
1147 abort ();
1148
1149 high -= low;
1150 if (high > 0)
1151 {
1152
1153 size_t index = low;
1154 size_t position = low;
1155 gl_list_node_t node;
1156
1157 if (position <= ((count - 1) / 2))
1158 {
1159 node = list->root.next;
1160 for (; position > 0; position--)
1161 node = node->next;
1162 }
1163 else
1164 {
1165 position = count - 1 - position;
1166 node = list->root.prev;
1167 for (; position > 0; position--)
1168 node = node->prev;
1169 }
1170
1171 do
1172 {
1173 int cmp = compar (node->value, elt);
1174
1175 if (cmp > 0)
1176 break;
1177 if (cmp == 0)
1178 return index;
1179 node = node->next;
1180 index++;
1181 }
1182 while (--high > 0);
1183 }
1184 return (size_t)(-1);
1185 }
1186
1187 static gl_list_node_t
1188 gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
1189 const void *elt)
1190 {
1191 gl_list_node_t node;
1192
1193 for (node = list->root.next; node != &list->root; node = node->next)
1194 if (compar (node->value, elt) >= 0)
1195 return gl_linked_nx_add_before (list, node, elt);
1196 return gl_linked_nx_add_last (list, elt);
1197 }
1198
1199 static bool
1200 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1201 const void *elt)
1202 {
1203 gl_list_node_t node;
1204
1205 for (node = list->root.next; node != &list->root; node = node->next)
1206 {
1207 int cmp = compar (node->value, elt);
1208
1209 if (cmp > 0)
1210 break;
1211 if (cmp == 0)
1212 return gl_linked_remove_node (list, node);
1213 }
1214 return false;
1215 }