1 /* Sequential list data type implemented by a linked list.
2 Copyright (C) 2006-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2006.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* Common code of gl_linked_list.c and gl_linkedhash_list.c. */
19
20 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
21 a way that a gl_list_t data structure may be used from within a signal
22 handler. The operations allowed in the signal handler are:
23 gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
24 The list and node fields that are therefore accessed from the signal handler
25 are:
26 list->root, node->next, node->value.
27 We are careful to make modifications to these fields only in an order
28 that maintains the consistency of the list data structure at any moment,
29 and we use 'volatile' assignments to prevent the compiler from reordering
30 such assignments. */
31 #ifdef SIGNAL_SAFE_LIST
32 # define ASYNCSAFE(type) *(type volatile *)&
33 #else
34 # define ASYNCSAFE(type)
35 #endif
36
37 /* -------------------------- gl_list_t Data Type -------------------------- */
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); /* 1.5 * count */
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 /* Add node to the hash table. */
129 if (add_to_bucket (list, node) < 0)
130 {
131 free (node);
132 goto fail2;
133 }
134 #endif
135
136 /* Add node to the list. */
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_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED,
174 gl_list_node_t node)
175 {
176 return node->value;
177 }
178
179 static int
180 gl_linked_node_nx_set_value (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED,
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 /* Out of memory. We removed node from a bucket but cannot add
200 it to another bucket. In order to avoid inconsistencies, we
201 must remove node entirely from the list. */
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 /* Invalid argument. */
258 abort ();
259 /* Here we know count > 0. */
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 /* Invalid argument. */
284 abort ();
285 /* Here we know count > 0. */
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 /* Out of memory. We removed node from a bucket but cannot add
315 it to another bucket. In order to avoid inconsistencies, we
316 must remove node entirely from the list. */
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 /* Invalid arguments. */
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 /* Look for the first match in the hash bucket. */
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 /* Look whether found's index is < start_index. */
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 /* Look whether found's index is >= end_index. */
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 /* Look whether there is more than one match in the hash bucket. */
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 /* We need the match with the smallest index. But we don't have
419 a fast mapping node -> index. So we have to walk the list. */
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 /* The matches must have all been at indices < start_index or
434 >= end_index. */
435 return NULL;
436 }
437 else
438 {
439 if (start_index > 0)
440 /* Look whether first_match's index is < start_index. */
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 /* Look whether first_match's index is >= end_index. */
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 /* Invalid arguments. */
496 abort ();
497 {
498 #if WITH_HASHTABLE
499 /* Here the hash table doesn't help much. It only allows us to minimize
500 the number of equals() calls, by looking up first the node and then
501 its index. */
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 /* First step: Look up the node. */
511 if (!list->base.allow_duplicates)
512 {
513 /* Look for the first match in the hash bucket. */
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 /* Look whether there is more than one match in the hash bucket. */
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 /* We need the match with the smallest index. But we don't have
548 a fast mapping node -> index. So we have to walk the list. */
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 /* The matches must have all been at indices < start_index or
565 >= end_index. */
566 return (size_t)(-1);
567 }
568 node = first_match;
569 }
570
571 /* Second step: Look up the index of the node. */
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 /* Add node to the hash table. */
632 if (add_to_bucket (list, node) < 0)
633 {
634 free (node);
635 return NULL;
636 }
637 #endif
638
639 /* Add node to the list. */
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 /* Add node to the hash table. */
670 if (add_to_bucket (list, node) < 0)
671 {
672 free (node);
673 return NULL;
674 }
675 #endif
676
677 /* Add node to the list. */
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 /* Add new_node to the hash table. */
708 if (add_to_bucket (list, new_node) < 0)
709 {
710 free (new_node);
711 return NULL;
712 }
713 #endif
714
715 /* Add new_node to the list. */
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 /* Add new_node to the hash table. */
746 if (add_to_bucket (list, new_node) < 0)
747 {
748 free (new_node);
749 return NULL;
750 }
751 #endif
752
753 /* Add new_node to the list. */
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 /* Invalid argument. */
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 /* Add new_node to the hash table. */
789 if (add_to_bucket (list, new_node) < 0)
790 {
791 free (new_node);
792 return NULL;
793 }
794 #endif
795
796 /* Add new_node to the list. */
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 /* Remove node from the hash table. */
839 remove_from_bucket (list, node);
840 #endif
841
842 /* Remove node from the list. */
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 /* Invalid argument. */
864 abort ();
865 /* Here we know count > 0. */
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 /* --------------------- gl_list_iterator_t Data Type --------------------- */
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 /* Invalid arguments. */
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 /* Find the maximum among n1, n2, n3, so as to reduce the number of
971 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
972 if (n1 > n2 && n1 > n3)
973 {
974 /* n1 is the maximum, use n2 and n3. */
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 /* n2 is the maximum, use n1 and n3. */
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 /* n3 is the maximum, use n1 and n2. */
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_list_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
1045 {
1046 }
1047
1048 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
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 /* Invalid arguments. */
1078 abort ();
1079
1080 high -= low;
1081 if (high > 0)
1082 {
1083 /* Here we know low < count. */
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 /* Invalid arguments. */
1147 abort ();
1148
1149 high -= low;
1150 if (high > 0)
1151 {
1152 /* Here we know low < count. */
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 }