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.
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.
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.
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/>. */
18 /* Common code of gl_linked_list.c and gl_linkedhash_list.c. */
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
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
31 #ifdef SIGNAL_SAFE_LIST
32 # define ASYNCSAFE(type) *(type volatile *)&
34 # define ASYNCSAFE(type)
37 /* -------------------------- gl_list_t Data Type -------------------------- */
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)
46 struct gl_list_impl *list =
47 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
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;
58 list->table_size = 11;
60 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
61 if (list->table == NULL)
64 list->root.next = &list->root;
65 list->root.prev = &list->root;
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)
85 struct gl_list_impl *list =
86 (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
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;
99 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
102 list->table_size = next_prime (estimate);
103 if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
106 (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
107 if (list->table == NULL)
113 for (; count > 0; contents++, count--)
115 gl_list_node_t node =
116 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
121 node->value = *contents;
124 (list->base.hashcode_fn != NULL
125 ? list->base.hashcode_fn (node->value)
126 : (size_t)(uintptr_t) node->value);
128 /* Add node to the hash table. */
129 if (add_to_bucket (list, node) < 0)
136 /* Add node to the list. */
141 tail->next = &list->root;
142 list->root.prev = tail;
150 for (node = tail; node != &list->root; )
152 gl_list_node_t prev = node->prev;
166 static size_t _GL_ATTRIBUTE_PURE
167 gl_linked_size (gl_list_t list)
172 static const void * _GL_ATTRIBUTE_PURE
173 gl_linked_node_value (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED,
180 gl_linked_node_nx_set_value (gl_list_t list _GL_ATTRIBUTE_MAYBE_UNUSED,
185 if (elt != node->value)
187 size_t new_hashcode =
188 (list->base.hashcode_fn != NULL
189 ? list->base.hashcode_fn (elt)
190 : (size_t)(uintptr_t) elt);
192 if (new_hashcode != node->h.hashcode)
194 remove_from_bucket (list, node);
196 node->h.hashcode = new_hashcode;
197 if (add_to_bucket (list, node) < 0)
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;
220 static gl_list_node_t _GL_ATTRIBUTE_PURE
221 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
223 return (node->next != &list->root ? node->next : NULL);
226 static gl_list_node_t _GL_ATTRIBUTE_PURE
227 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
229 return (node->prev != &list->root ? node->prev : NULL);
232 static gl_list_node_t _GL_ATTRIBUTE_PURE
233 gl_linked_first_node (gl_list_t list)
236 return list->root.next;
241 static gl_list_node_t _GL_ATTRIBUTE_PURE
242 gl_linked_last_node (gl_list_t list)
245 return list->root.prev;
250 static const void * _GL_ATTRIBUTE_PURE
251 gl_linked_get_at (gl_list_t list, size_t position)
253 size_t count = list->count;
256 if (!(position < count))
257 /* Invalid argument. */
259 /* Here we know count > 0. */
260 if (position <= ((count - 1) / 2))
262 node = list->root.next;
263 for (; position > 0; position--)
268 position = count - 1 - position;
269 node = list->root.prev;
270 for (; position > 0; position--)
276 static gl_list_node_t
277 gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt)
279 size_t count = list->count;
282 if (!(position < count))
283 /* Invalid argument. */
285 /* Here we know count > 0. */
286 if (position <= ((count - 1) / 2))
288 node = list->root.next;
289 for (; position > 0; position--)
294 position = count - 1 - position;
295 node = list->root.prev;
296 for (; position > 0; position--)
300 if (elt != node->value)
302 size_t new_hashcode =
303 (list->base.hashcode_fn != NULL
304 ? list->base.hashcode_fn (elt)
305 : (size_t)(uintptr_t) elt);
307 if (new_hashcode != node->h.hashcode)
309 remove_from_bucket (list, node);
311 node->h.hashcode = new_hashcode;
312 if (add_to_bucket (list, node) < 0)
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;
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,
339 size_t count = list->count;
341 if (!(start_index <= end_index && end_index <= count))
342 /* Invalid arguments. */
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;
353 if (!list->base.allow_duplicates)
355 /* Look for the first match in the hash bucket. */
356 gl_list_node_t found = NULL;
359 for (node = (gl_list_node_t) list->table[bucket];
361 node = (gl_list_node_t) node->h.hash_next)
362 if (node->h.hashcode == hashcode
364 ? equals (elt, node->value)
365 : elt == node->value))
371 /* Look whether found's index is < start_index. */
372 for (node = list->root.next; ; node = node->next)
376 if (--start_index == 0)
379 if (end_index < count)
380 /* Look whether found's index is >= end_index. */
382 end_index = count - end_index;
383 for (node = list->root.prev; ; node = node->prev)
387 if (--end_index == 0)
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;
400 for (node = (gl_list_node_t) list->table[bucket];
402 node = (gl_list_node_t) node->h.hash_next)
403 if (node->h.hashcode == hashcode
405 ? equals (elt, node->value)
406 : elt == node->value))
408 if (first_match == NULL)
412 multiple_matches = true;
416 if (multiple_matches)
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--)
427 node = node->next, end_index--)
428 if (node->h.hashcode == hashcode
430 ? equals (elt, node->value)
431 : elt == node->value))
433 /* The matches must have all been at indices < start_index or
440 /* Look whether first_match's index is < start_index. */
441 for (node = list->root.next; node != &list->root; node = node->next)
443 if (node == first_match)
445 if (--start_index == 0)
448 if (end_index < list->count)
449 /* Look whether first_match's index is >= end_index. */
451 end_index = list->count - end_index;
452 for (node = list->root.prev; ; node = node->prev)
454 if (node == first_match)
456 if (--end_index == 0)
464 gl_listelement_equals_fn equals = list->base.equals_fn;
465 gl_list_node_t node = list->root.next;
467 end_index -= start_index;
468 for (; start_index > 0; start_index--)
473 for (; end_index > 0; node = node->next, end_index--)
474 if (equals (elt, node->value))
479 for (; end_index > 0; node = node->next, end_index--)
480 if (elt == node->value)
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,
492 size_t count = list->count;
494 if (!(start_index <= end_index && end_index <= count))
495 /* Invalid arguments. */
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
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;
510 /* First step: Look up the node. */
511 if (!list->base.allow_duplicates)
513 /* Look for the first match in the hash bucket. */
514 for (node = (gl_list_node_t) list->table[bucket];
516 node = (gl_list_node_t) node->h.hash_next)
517 if (node->h.hashcode == hashcode
519 ? equals (elt, node->value)
520 : elt == node->value))
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;
529 for (node = (gl_list_node_t) list->table[bucket];
531 node = (gl_list_node_t) node->h.hash_next)
532 if (node->h.hashcode == hashcode
534 ? equals (elt, node->value)
535 : elt == node->value))
537 if (first_match == NULL)
541 multiple_matches = true;
545 if (multiple_matches)
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. */
552 node = list->root.next;
553 for (; start_index > 0; start_index--)
558 node = node->next, index++)
559 if (node->h.hashcode == hashcode
561 ? equals (elt, node->value)
562 : elt == node->value))
564 /* The matches must have all been at indices < start_index or
571 /* Second step: Look up the index of the node. */
578 for (; node->prev != &list->root; node = node->prev)
581 if (index >= start_index && index < end_index)
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;
591 for (; start_index > 0; start_index--)
598 node = node->next, index++)
599 if (equals (elt, node->value))
606 node = node->next, index++)
607 if (elt == node->value)
615 static gl_list_node_t
616 gl_linked_nx_add_first (gl_list_t list, const void *elt)
618 gl_list_node_t node =
619 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
624 ASYNCSAFE(const void *) node->value = elt;
627 (list->base.hashcode_fn != NULL
628 ? list->base.hashcode_fn (node->value)
629 : (size_t)(uintptr_t) node->value);
631 /* Add node to the hash table. */
632 if (add_to_bucket (list, node) < 0)
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;
647 hash_resize_after_add (list);
653 static gl_list_node_t
654 gl_linked_nx_add_last (gl_list_t list, const void *elt)
656 gl_list_node_t node =
657 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
662 ASYNCSAFE(const void *) node->value = elt;
665 (list->base.hashcode_fn != NULL
666 ? list->base.hashcode_fn (node->value)
667 : (size_t)(uintptr_t) node->value);
669 /* Add node to the hash table. */
670 if (add_to_bucket (list, node) < 0)
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;
685 hash_resize_after_add (list);
691 static gl_list_node_t
692 gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
694 gl_list_node_t new_node =
695 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
697 if (new_node == NULL)
700 ASYNCSAFE(const void *) new_node->value = elt;
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);
707 /* Add new_node to the hash table. */
708 if (add_to_bucket (list, new_node) < 0)
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;
723 hash_resize_after_add (list);
729 static gl_list_node_t
730 gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
732 gl_list_node_t new_node =
733 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
735 if (new_node == NULL)
738 ASYNCSAFE(const void *) new_node->value = elt;
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);
745 /* Add new_node to the hash table. */
746 if (add_to_bucket (list, new_node) < 0)
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;
761 hash_resize_after_add (list);
767 static gl_list_node_t
768 gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt)
770 size_t count = list->count;
771 gl_list_node_t new_node;
773 if (!(position <= count))
774 /* Invalid argument. */
777 new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
778 if (new_node == NULL)
781 ASYNCSAFE(const void *) new_node->value = elt;
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);
788 /* Add new_node to the hash table. */
789 if (add_to_bucket (list, new_node) < 0)
796 /* Add new_node to the list. */
797 if (position <= (count / 2))
802 for (; position > 0; position--)
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;
813 position = count - position;
815 for (; position > 0; position--)
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;
825 hash_resize_after_add (list);
832 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
838 /* Remove node from the hash table. */
839 remove_from_bucket (list, node);
842 /* Remove node from the list. */
846 ASYNCSAFE(gl_list_node_t) prev->next = next;
850 if (list->base.dispose_fn != NULL)
851 list->base.dispose_fn (node->value);
857 gl_linked_remove_at (gl_list_t list, size_t position)
859 size_t count = list->count;
860 gl_list_node_t removed_node;
862 if (!(position < count))
863 /* Invalid argument. */
865 /* Here we know count > 0. */
866 if (position <= ((count - 1) / 2))
869 gl_list_node_t after_removed;
872 for (; position > 0; position--)
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;
882 gl_list_node_t before_removed;
884 position = count - 1 - position;
886 for (; position > 0; position--)
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;
894 remove_from_bucket (list, removed_node);
898 if (list->base.dispose_fn != NULL)
899 list->base.dispose_fn (removed_node->value);
905 gl_linked_remove (gl_list_t list, const void *elt)
907 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
910 return gl_linked_remove_node (list, node);
916 gl_linked_list_free (gl_list_t list)
918 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
921 for (node = list->root.next; node != &list->root; )
923 gl_list_node_t next = node->next;
925 dispose (node->value);
935 /* --------------------- gl_list_iterator_t Data Type --------------------- */
937 static gl_list_iterator_t _GL_ATTRIBUTE_PURE
938 gl_linked_iterator (gl_list_t list)
940 gl_list_iterator_t result;
942 result.vtable = list->base.vtable;
944 result.p = list->root.next;
945 result.q = &list->root;
946 #if defined GCC_LINT || defined lint
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)
959 gl_list_iterator_t result;
962 if (!(start_index <= end_index && end_index <= list->count))
963 /* Invalid arguments. */
965 result.vtable = list->base.vtable;
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)
974 /* n1 is the maximum, use n2 and n3. */
979 for (i = n3; i > 0; i--)
982 for (i = n2; i > 0; i--)
988 /* n2 is the maximum, use n1 and n3. */
992 node = list->root.next;
993 for (i = n1; i > 0; i--)
998 for (i = n3; i > 0; i--)
1004 /* n3 is the maximum, use n1 and n2. */
1005 gl_list_node_t node;
1008 node = list->root.next;
1009 for (i = n1; i > 0; i--)
1012 for (i = n2; i > 0; i--)
1017 #if defined GCC_LINT || defined lint
1027 gl_linked_iterator_next (gl_list_iterator_t *iterator,
1028 const void **eltp, gl_list_node_t *nodep)
1030 if (iterator->p != iterator->q)
1032 gl_list_node_t node = (gl_list_node_t) iterator->p;
1033 *eltp = node->value;
1036 iterator->p = node->next;
1044 gl_linked_iterator_free (gl_list_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
1048 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
1050 static gl_list_node_t _GL_ATTRIBUTE_PURE
1051 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
1054 gl_list_node_t node;
1056 for (node = list->root.next; node != &list->root; node = node->next)
1058 int cmp = compar (node->value, elt);
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,
1074 size_t count = list->count;
1076 if (!(low <= high && high <= list->count))
1077 /* Invalid arguments. */
1083 /* Here we know low < count. */
1084 size_t position = low;
1085 gl_list_node_t node;
1087 if (position <= ((count - 1) / 2))
1089 node = list->root.next;
1090 for (; position > 0; position--)
1095 position = count - 1 - position;
1096 node = list->root.prev;
1097 for (; position > 0; position--)
1103 int cmp = compar (node->value, elt);
1116 static size_t _GL_ATTRIBUTE_PURE
1117 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
1120 gl_list_node_t node;
1123 for (node = list->root.next, index = 0;
1124 node != &list->root;
1125 node = node->next, index++)
1127 int cmp = compar (node->value, elt);
1134 return (size_t)(-1);
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,
1143 size_t count = list->count;
1145 if (!(low <= high && high <= list->count))
1146 /* Invalid arguments. */
1152 /* Here we know low < count. */
1154 size_t position = low;
1155 gl_list_node_t node;
1157 if (position <= ((count - 1) / 2))
1159 node = list->root.next;
1160 for (; position > 0; position--)
1165 position = count - 1 - position;
1166 node = list->root.prev;
1167 for (; position > 0; position--)
1173 int cmp = compar (node->value, elt);
1184 return (size_t)(-1);
1187 static gl_list_node_t
1188 gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
1191 gl_list_node_t node;
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);
1200 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1203 gl_list_node_t node;
1205 for (node = list->root.next; node != &list->root; node = node->next)
1207 int cmp = compar (node->value, elt);
1212 return gl_linked_remove_node (list, node);