1 /* Sequential list data type implemented by a linked list.
2 Copyright (C) 2006-2008 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 <http://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) *(volatile type *)&
34 # define ASYNCSAFE(type)
37 /* -------------------------- gl_list_t Data Type -------------------------- */
40 gl_linked_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 = XMALLOC (struct gl_list_impl);
48 list->base.vtable = implementation;
49 list->base.equals_fn = equals_fn;
50 list->base.hashcode_fn = hashcode_fn;
51 list->base.dispose_fn = dispose_fn;
52 list->base.allow_duplicates = allow_duplicates;
54 list->table_size = 11;
55 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
57 list->root.next = &list->root;
58 list->root.prev = &list->root;
65 gl_linked_create (gl_list_implementation_t implementation,
66 gl_listelement_equals_fn equals_fn,
67 gl_listelement_hashcode_fn hashcode_fn,
68 gl_listelement_dispose_fn dispose_fn,
69 bool allow_duplicates,
70 size_t count, const void **contents)
72 struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
75 list->base.vtable = implementation;
76 list->base.equals_fn = equals_fn;
77 list->base.hashcode_fn = hashcode_fn;
78 list->base.dispose_fn = dispose_fn;
79 list->base.allow_duplicates = allow_duplicates;
82 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
85 list->table_size = next_prime (estimate);
86 list->table = XCALLOC (list->table_size, gl_hash_entry_t);
91 for (; count > 0; contents++, count--)
93 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
95 node->value = *contents;
98 (list->base.hashcode_fn != NULL
99 ? list->base.hashcode_fn (node->value)
100 : (size_t)(uintptr_t) node->value);
102 /* Add node to the hash table. */
103 add_to_bucket (list, node);
106 /* Add node to the list. */
111 tail->next = &list->root;
112 list->root.prev = tail;
118 gl_linked_size (gl_list_t list)
124 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
130 gl_linked_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
133 if (elt != node->value)
135 size_t new_hashcode =
136 (list->base.hashcode_fn != NULL
137 ? list->base.hashcode_fn (elt)
138 : (size_t)(uintptr_t) elt);
140 if (new_hashcode != node->h.hashcode)
142 remove_from_bucket (list, node);
144 node->h.hashcode = new_hashcode;
145 add_to_bucket (list, node);
155 static gl_list_node_t
156 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
158 return (node->next != &list->root ? node->next : NULL);
161 static gl_list_node_t
162 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
164 return (node->prev != &list->root ? node->prev : NULL);
168 gl_linked_get_at (gl_list_t list, size_t position)
170 size_t count = list->count;
173 if (!(position < count))
174 /* Invalid argument. */
176 /* Here we know count > 0. */
177 if (position <= ((count - 1) / 2))
179 node = list->root.next;
180 for (; position > 0; position--)
185 position = count - 1 - position;
186 node = list->root.prev;
187 for (; position > 0; position--)
193 static gl_list_node_t
194 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
196 size_t count = list->count;
199 if (!(position < count))
200 /* Invalid argument. */
202 /* Here we know count > 0. */
203 if (position <= ((count - 1) / 2))
205 node = list->root.next;
206 for (; position > 0; position--)
211 position = count - 1 - position;
212 node = list->root.prev;
213 for (; position > 0; position--)
217 if (elt != node->value)
219 size_t new_hashcode =
220 (list->base.hashcode_fn != NULL
221 ? list->base.hashcode_fn (elt)
222 : (size_t)(uintptr_t) elt);
224 if (new_hashcode != node->h.hashcode)
226 remove_from_bucket (list, node);
228 node->h.hashcode = new_hashcode;
229 add_to_bucket (list, node);
240 static gl_list_node_t
241 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
244 size_t count = list->count;
246 if (!(start_index <= end_index && end_index <= count))
247 /* Invalid arguments. */
252 (list->base.hashcode_fn != NULL
253 ? list->base.hashcode_fn (elt)
254 : (size_t)(uintptr_t) elt);
255 size_t bucket = hashcode % list->table_size;
256 gl_listelement_equals_fn equals = list->base.equals_fn;
258 if (!list->base.allow_duplicates)
260 /* Look for the first match in the hash bucket. */
261 gl_list_node_t found = NULL;
264 for (node = (gl_list_node_t) list->table[bucket];
266 node = (gl_list_node_t) node->h.hash_next)
267 if (node->h.hashcode == hashcode
269 ? equals (elt, node->value)
270 : elt == node->value))
276 /* Look whether found's index is < start_index. */
277 for (node = list->root.next; ; node = node->next)
281 if (--start_index == 0)
284 if (end_index < count)
285 /* Look whether found's index is >= end_index. */
287 end_index = count - end_index;
288 for (node = list->root.prev; ; node = node->prev)
292 if (--end_index == 0)
300 /* Look whether there is more than one match in the hash bucket. */
301 bool multiple_matches = false;
302 gl_list_node_t first_match = NULL;
305 for (node = (gl_list_node_t) list->table[bucket];
307 node = (gl_list_node_t) node->h.hash_next)
308 if (node->h.hashcode == hashcode
310 ? equals (elt, node->value)
311 : elt == node->value))
313 if (first_match == NULL)
317 multiple_matches = true;
321 if (multiple_matches)
323 /* We need the match with the smallest index. But we don't have
324 a fast mapping node -> index. So we have to walk the list. */
325 end_index -= start_index;
326 node = list->root.next;
327 for (; start_index > 0; start_index--)
332 node = node->next, end_index--)
333 if (node->h.hashcode == hashcode
335 ? equals (elt, node->value)
336 : elt == node->value))
338 /* The matches must have all been at indices < start_index or
345 /* Look whether first_match's index is < start_index. */
346 for (node = list->root.next; node != &list->root; node = node->next)
348 if (node == first_match)
350 if (--start_index == 0)
353 if (end_index < list->count)
354 /* Look whether first_match's index is >= end_index. */
356 end_index = list->count - end_index;
357 for (node = list->root.prev; ; node = node->prev)
359 if (node == first_match)
361 if (--end_index == 0)
369 gl_listelement_equals_fn equals = list->base.equals_fn;
370 gl_list_node_t node = list->root.next;
372 end_index -= start_index;
373 for (; start_index > 0; start_index--)
378 for (; end_index > 0; node = node->next, end_index--)
379 if (equals (elt, node->value))
384 for (; end_index > 0; node = node->next, end_index--)
385 if (elt == node->value)
394 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
397 size_t count = list->count;
399 if (!(start_index <= end_index && end_index <= count))
400 /* Invalid arguments. */
404 /* Here the hash table doesn't help much. It only allows us to minimize
405 the number of equals() calls, by looking up first the node and then
408 (list->base.hashcode_fn != NULL
409 ? list->base.hashcode_fn (elt)
410 : (size_t)(uintptr_t) elt);
411 size_t bucket = hashcode % list->table_size;
412 gl_listelement_equals_fn equals = list->base.equals_fn;
415 /* First step: Look up the node. */
416 if (!list->base.allow_duplicates)
418 /* Look for the first match in the hash bucket. */
419 for (node = (gl_list_node_t) list->table[bucket];
421 node = (gl_list_node_t) node->h.hash_next)
422 if (node->h.hashcode == hashcode
424 ? equals (elt, node->value)
425 : elt == node->value))
430 /* Look whether there is more than one match in the hash bucket. */
431 bool multiple_matches = false;
432 gl_list_node_t first_match = NULL;
434 for (node = (gl_list_node_t) list->table[bucket];
436 node = (gl_list_node_t) node->h.hash_next)
437 if (node->h.hashcode == hashcode
439 ? equals (elt, node->value)
440 : elt == node->value))
442 if (first_match == NULL)
446 multiple_matches = true;
450 if (multiple_matches)
452 /* We need the match with the smallest index. But we don't have
453 a fast mapping node -> index. So we have to walk the list. */
457 node = list->root.next;
458 for (; start_index > 0; start_index--)
463 node = node->next, index++)
464 if (node->h.hashcode == hashcode
466 ? equals (elt, node->value)
467 : elt == node->value))
469 /* The matches must have all been at indices < start_index or
476 /* Second step: Look up the index of the node. */
483 for (; node->prev != &list->root; node = node->prev)
486 if (index >= start_index && index < end_index)
492 gl_listelement_equals_fn equals = list->base.equals_fn;
493 size_t index = start_index;
494 gl_list_node_t node = list->root.next;
496 for (; start_index > 0; start_index--)
503 node = node->next, index++)
504 if (equals (elt, node->value))
511 node = node->next, index++)
512 if (elt == node->value)
520 static gl_list_node_t
521 gl_linked_add_first (gl_list_t list, const void *elt)
523 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
525 ASYNCSAFE(const void *) node->value = elt;
528 (list->base.hashcode_fn != NULL
529 ? list->base.hashcode_fn (node->value)
530 : (size_t)(uintptr_t) node->value);
532 /* Add node to the hash table. */
533 add_to_bucket (list, node);
536 /* Add node to the list. */
537 node->prev = &list->root;
538 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
539 node->next->prev = node;
540 ASYNCSAFE(gl_list_node_t) list->root.next = node;
544 hash_resize_after_add (list);
550 static gl_list_node_t
551 gl_linked_add_last (gl_list_t list, const void *elt)
553 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
555 ASYNCSAFE(const void *) node->value = elt;
558 (list->base.hashcode_fn != NULL
559 ? list->base.hashcode_fn (node->value)
560 : (size_t)(uintptr_t) node->value);
562 /* Add node to the hash table. */
563 add_to_bucket (list, node);
566 /* Add node to the list. */
567 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
568 node->prev = list->root.prev;
569 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
570 list->root.prev = node;
574 hash_resize_after_add (list);
580 static gl_list_node_t
581 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
583 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
585 ASYNCSAFE(const void *) new_node->value = elt;
587 new_node->h.hashcode =
588 (list->base.hashcode_fn != NULL
589 ? list->base.hashcode_fn (new_node->value)
590 : (size_t)(uintptr_t) new_node->value);
592 /* Add new_node to the hash table. */
593 add_to_bucket (list, new_node);
596 /* Add new_node to the list. */
597 ASYNCSAFE(gl_list_node_t) new_node->next = node;
598 new_node->prev = node->prev;
599 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
600 node->prev = new_node;
604 hash_resize_after_add (list);
610 static gl_list_node_t
611 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
613 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
615 ASYNCSAFE(const void *) new_node->value = elt;
617 new_node->h.hashcode =
618 (list->base.hashcode_fn != NULL
619 ? list->base.hashcode_fn (new_node->value)
620 : (size_t)(uintptr_t) new_node->value);
622 /* Add new_node to the hash table. */
623 add_to_bucket (list, new_node);
626 /* Add new_node to the list. */
627 new_node->prev = node;
628 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
629 new_node->next->prev = new_node;
630 ASYNCSAFE(gl_list_node_t) node->next = new_node;
634 hash_resize_after_add (list);
640 static gl_list_node_t
641 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
643 size_t count = list->count;
644 gl_list_node_t new_node;
646 if (!(position <= count))
647 /* Invalid argument. */
650 new_node = XMALLOC (struct gl_list_node_impl);
651 ASYNCSAFE(const void *) new_node->value = elt;
653 new_node->h.hashcode =
654 (list->base.hashcode_fn != NULL
655 ? list->base.hashcode_fn (new_node->value)
656 : (size_t)(uintptr_t) new_node->value);
658 /* Add new_node to the hash table. */
659 add_to_bucket (list, new_node);
662 /* Add new_node to the list. */
663 if (position <= (count / 2))
668 for (; position > 0; position--)
670 new_node->prev = node;
671 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
672 new_node->next->prev = new_node;
673 ASYNCSAFE(gl_list_node_t) node->next = new_node;
679 position = count - position;
681 for (; position > 0; position--)
683 ASYNCSAFE(gl_list_node_t) new_node->next = node;
684 new_node->prev = node->prev;
685 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
686 node->prev = new_node;
691 hash_resize_after_add (list);
698 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
704 /* Remove node from the hash table. */
705 remove_from_bucket (list, node);
708 /* Remove node from the list. */
712 ASYNCSAFE(gl_list_node_t) prev->next = next;
716 if (list->base.dispose_fn != NULL)
717 list->base.dispose_fn (node->value);
723 gl_linked_remove_at (gl_list_t list, size_t position)
725 size_t count = list->count;
726 gl_list_node_t removed_node;
728 if (!(position < count))
729 /* Invalid argument. */
731 /* Here we know count > 0. */
732 if (position <= ((count - 1) / 2))
735 gl_list_node_t after_removed;
738 for (; position > 0; position--)
740 removed_node = node->next;
741 after_removed = node->next->next;
742 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
743 after_removed->prev = node;
748 gl_list_node_t before_removed;
750 position = count - 1 - position;
752 for (; position > 0; position--)
754 removed_node = node->prev;
755 before_removed = node->prev->prev;
756 node->prev = before_removed;
757 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
760 remove_from_bucket (list, removed_node);
764 if (list->base.dispose_fn != NULL)
765 list->base.dispose_fn (removed_node->value);
771 gl_linked_remove (gl_list_t list, const void *elt)
773 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
776 return gl_linked_remove_node (list, node);
782 gl_linked_list_free (gl_list_t list)
784 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
787 for (node = list->root.next; node != &list->root; )
789 gl_list_node_t next = node->next;
791 dispose (node->value);
801 /* --------------------- gl_list_iterator_t Data Type --------------------- */
803 static gl_list_iterator_t
804 gl_linked_iterator (gl_list_t list)
806 gl_list_iterator_t result;
808 result.vtable = list->base.vtable;
810 result.p = list->root.next;
811 result.q = &list->root;
821 static gl_list_iterator_t
822 gl_linked_iterator_from_to (gl_list_t list,
823 size_t start_index, size_t end_index)
825 gl_list_iterator_t result;
828 if (!(start_index <= end_index && end_index <= list->count))
829 /* Invalid arguments. */
831 result.vtable = list->base.vtable;
834 n2 = end_index - start_index;
835 n3 = list->count - end_index;
836 /* Find the maximum among n1, n2, n3, so as to reduce the number of
837 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
838 if (n1 > n2 && n1 > n3)
840 /* n1 is the maximum, use n2 and n3. */
845 for (i = n3; i > 0; i--)
848 for (i = n2; i > 0; i--)
854 /* n2 is the maximum, use n1 and n3. */
858 node = list->root.next;
859 for (i = n1; i > 0; i--)
864 for (i = n3; i > 0; i--)
870 /* n3 is the maximum, use n1 and n2. */
874 node = list->root.next;
875 for (i = n1; i > 0; i--)
878 for (i = n2; i > 0; i--)
893 gl_linked_iterator_next (gl_list_iterator_t *iterator,
894 const void **eltp, gl_list_node_t *nodep)
896 if (iterator->p != iterator->q)
898 gl_list_node_t node = (gl_list_node_t) iterator->p;
902 iterator->p = node->next;
910 gl_linked_iterator_free (gl_list_iterator_t *iterator)
914 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
916 static gl_list_node_t
917 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
922 for (node = list->root.next; node != &list->root; node = node->next)
924 int cmp = compar (node->value, elt);
934 static gl_list_node_t
935 gl_linked_sortedlist_search_from_to (gl_list_t list,
936 gl_listelement_compar_fn compar,
937 size_t low, size_t high,
940 size_t count = list->count;
942 if (!(low <= high && high <= list->count))
943 /* Invalid arguments. */
949 /* Here we know low < count. */
950 size_t position = low;
953 if (position <= ((count - 1) / 2))
955 node = list->root.next;
956 for (; position > 0; position--)
961 position = count - 1 - position;
962 node = list->root.prev;
963 for (; position > 0; position--)
969 int cmp = compar (node->value, elt);
983 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
989 for (node = list->root.next, index = 0;
991 node = node->next, index++)
993 int cmp = compar (node->value, elt);
1000 return (size_t)(-1);
1004 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
1005 gl_listelement_compar_fn compar,
1006 size_t low, size_t high,
1009 size_t count = list->count;
1011 if (!(low <= high && high <= list->count))
1012 /* Invalid arguments. */
1018 /* Here we know low < count. */
1020 size_t position = low;
1021 gl_list_node_t node;
1023 if (position <= ((count - 1) / 2))
1025 node = list->root.next;
1026 for (; position > 0; position--)
1031 position = count - 1 - position;
1032 node = list->root.prev;
1033 for (; position > 0; position--)
1039 int cmp = compar (node->value, elt);
1050 return (size_t)(-1);
1053 static gl_list_node_t
1054 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
1057 gl_list_node_t node;
1059 for (node = list->root.next; node != &list->root; node = node->next)
1060 if (compar (node->value, elt) >= 0)
1061 return gl_linked_add_before (list, node, elt);
1062 return gl_linked_add_last (list, elt);
1066 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1069 gl_list_node_t node;
1071 for (node = list->root.next; node != &list->root; node = node->next)
1073 int cmp = compar (node->value, elt);
1078 return gl_linked_remove_node (list, node);