1 /* Sequential list data type implemented by a linked list.
2 Copyright (C) 2006-2007 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)
129 static gl_list_node_t
130 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
132 return (node->next != &list->root ? node->next : NULL);
135 static gl_list_node_t
136 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
138 return (node->prev != &list->root ? node->prev : NULL);
142 gl_linked_get_at (gl_list_t list, size_t position)
144 size_t count = list->count;
147 if (!(position < count))
148 /* Invalid argument. */
150 /* Here we know count > 0. */
151 if (position <= ((count - 1) / 2))
153 node = list->root.next;
154 for (; position > 0; position--)
159 position = count - 1 - position;
160 node = list->root.prev;
161 for (; position > 0; position--)
167 static gl_list_node_t
168 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
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--)
191 if (elt != node->value)
193 size_t new_hashcode =
194 (list->base.hashcode_fn != NULL
195 ? list->base.hashcode_fn (elt)
196 : (size_t)(uintptr_t) elt);
198 if (new_hashcode != node->h.hashcode)
200 remove_from_bucket (list, node);
202 node->h.hashcode = new_hashcode;
203 add_to_bucket (list, node);
214 static gl_list_node_t
215 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
218 size_t count = list->count;
220 if (!(start_index <= end_index && end_index <= count))
221 /* Invalid arguments. */
226 (list->base.hashcode_fn != NULL
227 ? list->base.hashcode_fn (elt)
228 : (size_t)(uintptr_t) elt);
229 size_t bucket = hashcode % list->table_size;
230 gl_listelement_equals_fn equals = list->base.equals_fn;
232 if (!list->base.allow_duplicates)
234 /* Look for the first match in the hash bucket. */
235 gl_list_node_t found = NULL;
238 for (node = (gl_list_node_t) list->table[bucket];
240 node = (gl_list_node_t) node->h.hash_next)
241 if (node->h.hashcode == hashcode
243 ? equals (elt, node->value)
244 : elt == node->value))
250 /* Look whether found's index is < start_index. */
251 for (node = list->root.next; ; node = node->next)
255 if (--start_index == 0)
258 if (end_index < count)
259 /* Look whether found's index is >= end_index. */
261 end_index = count - end_index;
262 for (node = list->root.prev; ; node = node->prev)
266 if (--end_index == 0)
274 /* Look whether there is more than one match in the hash bucket. */
275 bool multiple_matches = false;
276 gl_list_node_t first_match = NULL;
279 for (node = (gl_list_node_t) list->table[bucket];
281 node = (gl_list_node_t) node->h.hash_next)
282 if (node->h.hashcode == hashcode
284 ? equals (elt, node->value)
285 : elt == node->value))
287 if (first_match == NULL)
291 multiple_matches = true;
295 if (multiple_matches)
297 /* We need the match with the smallest index. But we don't have
298 a fast mapping node -> index. So we have to walk the list. */
299 end_index -= start_index;
300 node = list->root.next;
301 for (; start_index > 0; start_index--)
306 node = node->next, end_index--)
307 if (node->h.hashcode == hashcode
309 ? equals (elt, node->value)
310 : elt == node->value))
312 /* The matches must have all been at indices < start_index or
319 /* Look whether first_match's index is < start_index. */
320 for (node = list->root.next; node != &list->root; node = node->next)
322 if (node == first_match)
324 if (--start_index == 0)
327 if (end_index < list->count)
328 /* Look whether first_match's index is >= end_index. */
330 end_index = list->count - end_index;
331 for (node = list->root.prev; ; node = node->prev)
333 if (node == first_match)
335 if (--end_index == 0)
343 gl_listelement_equals_fn equals = list->base.equals_fn;
344 gl_list_node_t node = list->root.next;
346 end_index -= start_index;
347 for (; start_index > 0; start_index--)
352 for (; end_index > 0; node = node->next, end_index--)
353 if (equals (elt, node->value))
358 for (; end_index > 0; node = node->next, end_index--)
359 if (elt == node->value)
368 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
371 size_t count = list->count;
373 if (!(start_index <= end_index && end_index <= count))
374 /* Invalid arguments. */
378 /* Here the hash table doesn't help much. It only allows us to minimize
379 the number of equals() calls, by looking up first the node and then
382 (list->base.hashcode_fn != NULL
383 ? list->base.hashcode_fn (elt)
384 : (size_t)(uintptr_t) elt);
385 size_t bucket = hashcode % list->table_size;
386 gl_listelement_equals_fn equals = list->base.equals_fn;
389 /* First step: Look up the node. */
390 if (!list->base.allow_duplicates)
392 /* Look for the first match in the hash bucket. */
393 for (node = (gl_list_node_t) list->table[bucket];
395 node = (gl_list_node_t) node->h.hash_next)
396 if (node->h.hashcode == hashcode
398 ? equals (elt, node->value)
399 : elt == node->value))
404 /* Look whether there is more than one match in the hash bucket. */
405 bool multiple_matches = false;
406 gl_list_node_t first_match = NULL;
408 for (node = (gl_list_node_t) list->table[bucket];
410 node = (gl_list_node_t) node->h.hash_next)
411 if (node->h.hashcode == hashcode
413 ? equals (elt, node->value)
414 : elt == node->value))
416 if (first_match == NULL)
420 multiple_matches = true;
424 if (multiple_matches)
426 /* We need the match with the smallest index. But we don't have
427 a fast mapping node -> index. So we have to walk the list. */
431 node = list->root.next;
432 for (; start_index > 0; start_index--)
437 node = node->next, index++)
438 if (node->h.hashcode == hashcode
440 ? equals (elt, node->value)
441 : elt == node->value))
443 /* The matches must have all been at indices < start_index or
450 /* Second step: Look up the index of the node. */
457 for (; node->prev != &list->root; node = node->prev)
460 if (index >= start_index && index < end_index)
466 gl_listelement_equals_fn equals = list->base.equals_fn;
467 size_t index = start_index;
468 gl_list_node_t node = list->root.next;
470 for (; start_index > 0; start_index--)
477 node = node->next, index++)
478 if (equals (elt, node->value))
485 node = node->next, index++)
486 if (elt == node->value)
494 static gl_list_node_t
495 gl_linked_add_first (gl_list_t list, const void *elt)
497 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
499 ASYNCSAFE(const void *) node->value = elt;
502 (list->base.hashcode_fn != NULL
503 ? list->base.hashcode_fn (node->value)
504 : (size_t)(uintptr_t) node->value);
506 /* Add node to the hash table. */
507 add_to_bucket (list, node);
510 /* Add node to the list. */
511 node->prev = &list->root;
512 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
513 node->next->prev = node;
514 ASYNCSAFE(gl_list_node_t) list->root.next = node;
518 hash_resize_after_add (list);
524 static gl_list_node_t
525 gl_linked_add_last (gl_list_t list, const void *elt)
527 gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
529 ASYNCSAFE(const void *) node->value = elt;
532 (list->base.hashcode_fn != NULL
533 ? list->base.hashcode_fn (node->value)
534 : (size_t)(uintptr_t) node->value);
536 /* Add node to the hash table. */
537 add_to_bucket (list, node);
540 /* Add node to the list. */
541 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
542 node->prev = list->root.prev;
543 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
544 list->root.prev = node;
548 hash_resize_after_add (list);
554 static gl_list_node_t
555 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
557 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
559 ASYNCSAFE(const void *) new_node->value = elt;
561 new_node->h.hashcode =
562 (list->base.hashcode_fn != NULL
563 ? list->base.hashcode_fn (new_node->value)
564 : (size_t)(uintptr_t) new_node->value);
566 /* Add new_node to the hash table. */
567 add_to_bucket (list, new_node);
570 /* Add new_node to the list. */
571 ASYNCSAFE(gl_list_node_t) new_node->next = node;
572 new_node->prev = node->prev;
573 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
574 node->prev = new_node;
578 hash_resize_after_add (list);
584 static gl_list_node_t
585 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
587 gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
589 ASYNCSAFE(const void *) new_node->value = elt;
591 new_node->h.hashcode =
592 (list->base.hashcode_fn != NULL
593 ? list->base.hashcode_fn (new_node->value)
594 : (size_t)(uintptr_t) new_node->value);
596 /* Add new_node to the hash table. */
597 add_to_bucket (list, new_node);
600 /* Add new_node to the list. */
601 new_node->prev = node;
602 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
603 new_node->next->prev = new_node;
604 ASYNCSAFE(gl_list_node_t) node->next = new_node;
608 hash_resize_after_add (list);
614 static gl_list_node_t
615 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
617 size_t count = list->count;
618 gl_list_node_t new_node;
620 if (!(position <= count))
621 /* Invalid argument. */
624 new_node = XMALLOC (struct gl_list_node_impl);
625 ASYNCSAFE(const void *) new_node->value = elt;
627 new_node->h.hashcode =
628 (list->base.hashcode_fn != NULL
629 ? list->base.hashcode_fn (new_node->value)
630 : (size_t)(uintptr_t) new_node->value);
632 /* Add new_node to the hash table. */
633 add_to_bucket (list, new_node);
636 /* Add new_node to the list. */
637 if (position <= (count / 2))
642 for (; position > 0; position--)
644 new_node->prev = node;
645 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
646 new_node->next->prev = new_node;
647 ASYNCSAFE(gl_list_node_t) node->next = new_node;
653 position = count - position;
655 for (; position > 0; position--)
657 ASYNCSAFE(gl_list_node_t) new_node->next = node;
658 new_node->prev = node->prev;
659 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
660 node->prev = new_node;
665 hash_resize_after_add (list);
672 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
678 /* Remove node from the hash table. */
679 remove_from_bucket (list, node);
682 /* Remove node from the list. */
686 ASYNCSAFE(gl_list_node_t) prev->next = next;
690 if (list->base.dispose_fn != NULL)
691 list->base.dispose_fn (node->value);
697 gl_linked_remove_at (gl_list_t list, size_t position)
699 size_t count = list->count;
700 gl_list_node_t removed_node;
702 if (!(position < count))
703 /* Invalid argument. */
705 /* Here we know count > 0. */
706 if (position <= ((count - 1) / 2))
709 gl_list_node_t after_removed;
712 for (; position > 0; position--)
714 removed_node = node->next;
715 after_removed = node->next->next;
716 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
717 after_removed->prev = node;
722 gl_list_node_t before_removed;
724 position = count - 1 - position;
726 for (; position > 0; position--)
728 removed_node = node->prev;
729 before_removed = node->prev->prev;
730 node->prev = before_removed;
731 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
734 remove_from_bucket (list, removed_node);
738 if (list->base.dispose_fn != NULL)
739 list->base.dispose_fn (removed_node->value);
745 gl_linked_remove (gl_list_t list, const void *elt)
747 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
750 return gl_linked_remove_node (list, node);
756 gl_linked_list_free (gl_list_t list)
758 gl_listelement_dispose_fn dispose = list->base.dispose_fn;
761 for (node = list->root.next; node != &list->root; )
763 gl_list_node_t next = node->next;
765 dispose (node->value);
775 /* --------------------- gl_list_iterator_t Data Type --------------------- */
777 static gl_list_iterator_t
778 gl_linked_iterator (gl_list_t list)
780 gl_list_iterator_t result;
782 result.vtable = list->base.vtable;
784 result.p = list->root.next;
785 result.q = &list->root;
795 static gl_list_iterator_t
796 gl_linked_iterator_from_to (gl_list_t list,
797 size_t start_index, size_t end_index)
799 gl_list_iterator_t result;
802 if (!(start_index <= end_index && end_index <= list->count))
803 /* Invalid arguments. */
805 result.vtable = list->base.vtable;
808 n2 = end_index - start_index;
809 n3 = list->count - end_index;
810 /* Find the maximum among n1, n2, n3, so as to reduce the number of
811 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
812 if (n1 > n2 && n1 > n3)
814 /* n1 is the maximum, use n2 and n3. */
819 for (i = n3; i > 0; i--)
822 for (i = n2; i > 0; i--)
828 /* n2 is the maximum, use n1 and n3. */
832 node = list->root.next;
833 for (i = n1; i > 0; i--)
838 for (i = n3; i > 0; i--)
844 /* n3 is the maximum, use n1 and n2. */
848 node = list->root.next;
849 for (i = n1; i > 0; i--)
852 for (i = n2; i > 0; i--)
867 gl_linked_iterator_next (gl_list_iterator_t *iterator,
868 const void **eltp, gl_list_node_t *nodep)
870 if (iterator->p != iterator->q)
872 gl_list_node_t node = (gl_list_node_t) iterator->p;
876 iterator->p = node->next;
884 gl_linked_iterator_free (gl_list_iterator_t *iterator)
888 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
890 static gl_list_node_t
891 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
896 for (node = list->root.next; node != &list->root; node = node->next)
898 int cmp = compar (node->value, elt);
908 static gl_list_node_t
909 gl_linked_sortedlist_search_from_to (gl_list_t list,
910 gl_listelement_compar_fn compar,
911 size_t low, size_t high,
914 size_t count = list->count;
916 if (!(low <= high && high <= list->count))
917 /* Invalid arguments. */
923 /* Here we know low < count. */
924 size_t position = low;
927 if (position <= ((count - 1) / 2))
929 node = list->root.next;
930 for (; position > 0; position--)
935 position = count - 1 - position;
936 node = list->root.prev;
937 for (; position > 0; position--)
943 int cmp = compar (node->value, elt);
957 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
963 for (node = list->root.next, index = 0;
965 node = node->next, index++)
967 int cmp = compar (node->value, elt);
978 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
979 gl_listelement_compar_fn compar,
980 size_t low, size_t high,
983 size_t count = list->count;
985 if (!(low <= high && high <= list->count))
986 /* Invalid arguments. */
992 /* Here we know low < count. */
994 size_t position = low;
997 if (position <= ((count - 1) / 2))
999 node = list->root.next;
1000 for (; position > 0; position--)
1005 position = count - 1 - position;
1006 node = list->root.prev;
1007 for (; position > 0; position--)
1013 int cmp = compar (node->value, elt);
1024 return (size_t)(-1);
1027 static gl_list_node_t
1028 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
1031 gl_list_node_t node;
1033 for (node = list->root.next; node != &list->root; node = node->next)
1034 if (compar (node->value, elt) >= 0)
1035 return gl_linked_add_before (list, node, elt);
1036 return gl_linked_add_last (list, elt);
1040 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1043 gl_list_node_t node;
1045 for (node = list->root.next; node != &list->root; node = node->next)
1047 int cmp = compar (node->value, elt);
1052 return gl_linked_remove_node (list, node);