1 /* Sequential list data type implemented by a linked list.
2 Copyright (C) 2006 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 2, or (at your option)
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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* Common code of gl_linked_list.c and gl_linkedhash_list.c. */
21 /* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such
22 a way that a gl_list_t data structure may be used from within a signal
23 handler. The operations allowed in the signal handler are:
24 gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free.
25 The list and node fields that are therefore accessed from the signal handler
27 list->root, node->next, node->value.
28 We are careful to make modifications to these fields only in an order
29 that maintains the consistency of the list data structure at any moment,
30 and we use 'volatile' assignments to prevent the compiler from reordering
32 #ifdef SIGNAL_SAFE_LIST
33 # define ASYNCSAFE(type) *(volatile type *)&
35 # define ASYNCSAFE(type)
38 /* -------------------------- gl_list_t Data Type -------------------------- */
41 gl_linked_create_empty (gl_list_implementation_t implementation,
42 gl_listelement_equals_fn equals_fn,
43 gl_listelement_hashcode_fn hashcode_fn,
44 bool allow_duplicates)
46 struct gl_list_impl *list =
47 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
49 list->base.vtable = implementation;
50 list->base.equals_fn = equals_fn;
51 list->base.hashcode_fn = hashcode_fn;
52 list->base.allow_duplicates = allow_duplicates;
54 list->table_size = 11;
56 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
58 list->root.next = &list->root;
59 list->root.prev = &list->root;
66 gl_linked_create (gl_list_implementation_t implementation,
67 gl_listelement_equals_fn equals_fn,
68 gl_listelement_hashcode_fn hashcode_fn,
69 bool allow_duplicates,
70 size_t count, const void **contents)
72 struct gl_list_impl *list =
73 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
76 list->base.vtable = implementation;
77 list->base.equals_fn = equals_fn;
78 list->base.hashcode_fn = hashcode_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);
87 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
92 for (; count > 0; contents++, count--)
95 (struct gl_list_node_impl *)
96 xmalloc (sizeof (struct gl_list_node_impl));
98 node->value = *contents;
101 (list->base.hashcode_fn != NULL
102 ? list->base.hashcode_fn (node->value)
103 : (size_t)(uintptr_t) node->value);
105 /* Add node to the hash table. */
106 add_to_bucket (list, node);
109 /* Add node to the list. */
114 tail->next = &list->root;
115 list->root.prev = tail;
121 gl_linked_size (gl_list_t list)
127 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
132 static gl_list_node_t
133 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
135 return (node->next != &list->root ? node->next : NULL);
138 static gl_list_node_t
139 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
141 return (node->prev != &list->root ? node->prev : NULL);
145 gl_linked_get_at (gl_list_t list, size_t position)
147 size_t count = list->count;
150 if (!(position < count))
151 /* Invalid argument. */
153 /* Here we know count > 0. */
154 if (position <= ((count - 1) / 2))
156 node = list->root.next;
157 for (; position > 0; position--)
162 position = count - 1 - position;
163 node = list->root.prev;
164 for (; position > 0; position--)
170 static gl_list_node_t
171 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
173 size_t count = list->count;
176 if (!(position < count))
177 /* Invalid argument. */
179 /* Here we know count > 0. */
180 if (position <= ((count - 1) / 2))
182 node = list->root.next;
183 for (; position > 0; position--)
188 position = count - 1 - position;
189 node = list->root.prev;
190 for (; position > 0; position--)
194 if (elt != node->value)
196 size_t new_hashcode =
197 (list->base.hashcode_fn != NULL
198 ? list->base.hashcode_fn (elt)
199 : (size_t)(uintptr_t) elt);
201 if (new_hashcode != node->h.hashcode)
203 remove_from_bucket (list, node);
205 node->h.hashcode = new_hashcode;
206 add_to_bucket (list, node);
217 static gl_list_node_t
218 gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
221 size_t count = list->count;
223 if (!(start_index <= end_index && end_index <= count))
224 /* Invalid arguments. */
229 (list->base.hashcode_fn != NULL
230 ? list->base.hashcode_fn (elt)
231 : (size_t)(uintptr_t) elt);
232 size_t bucket = hashcode % list->table_size;
233 gl_listelement_equals_fn equals = list->base.equals_fn;
235 if (!list->base.allow_duplicates)
237 /* Look for the first match in the hash bucket. */
238 gl_list_node_t found = NULL;
241 for (node = (gl_list_node_t) list->table[bucket];
243 node = (gl_list_node_t) node->h.hash_next)
244 if (node->h.hashcode == hashcode
246 ? equals (elt, node->value)
247 : elt == node->value))
253 /* Look whether found's index is < start_index. */
254 for (node = list->root.next; ; node = node->next)
258 if (--start_index == 0)
261 if (end_index < count)
262 /* Look whether found's index is >= end_index. */
264 end_index = count - end_index;
265 for (node = list->root.prev; ; node = node->prev)
269 if (--end_index == 0)
277 /* Look whether there is more than one match in the hash bucket. */
278 bool multiple_matches = false;
279 gl_list_node_t first_match = NULL;
282 for (node = (gl_list_node_t) list->table[bucket];
284 node = (gl_list_node_t) node->h.hash_next)
285 if (node->h.hashcode == hashcode
287 ? equals (elt, node->value)
288 : elt == node->value))
290 if (first_match == NULL)
294 multiple_matches = true;
298 if (multiple_matches)
300 /* We need the match with the smallest index. But we don't have
301 a fast mapping node -> index. So we have to walk the list. */
302 end_index -= start_index;
303 node = list->root.next;
304 for (; start_index > 0; start_index--)
309 node = node->next, end_index--)
310 if (node->h.hashcode == hashcode
312 ? equals (elt, node->value)
313 : elt == node->value))
315 /* The matches must have all been at indices < start_index or
322 /* Look whether first_match's index is < start_index. */
323 for (node = list->root.next; node != &list->root; node = node->next)
325 if (node == first_match)
327 if (--start_index == 0)
330 if (end_index < list->count)
331 /* Look whether first_match's index is >= end_index. */
333 end_index = list->count - end_index;
334 for (node = list->root.prev; ; node = node->prev)
336 if (node == first_match)
338 if (--end_index == 0)
346 gl_listelement_equals_fn equals = list->base.equals_fn;
347 gl_list_node_t node = list->root.next;
349 end_index -= start_index;
350 for (; start_index > 0; start_index--)
355 for (; end_index > 0; node = node->next, end_index--)
356 if (equals (elt, node->value))
361 for (; end_index > 0; node = node->next, end_index--)
362 if (elt == node->value)
371 gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
374 size_t count = list->count;
376 if (!(start_index <= end_index && end_index <= count))
377 /* Invalid arguments. */
381 /* Here the hash table doesn't help much. It only allows us to minimize
382 the number of equals() calls, by looking up first the node and then
385 (list->base.hashcode_fn != NULL
386 ? list->base.hashcode_fn (elt)
387 : (size_t)(uintptr_t) elt);
388 size_t bucket = hashcode % list->table_size;
389 gl_listelement_equals_fn equals = list->base.equals_fn;
392 /* First step: Look up the node. */
393 if (!list->base.allow_duplicates)
395 /* Look for the first match in the hash bucket. */
396 for (node = (gl_list_node_t) list->table[bucket];
398 node = (gl_list_node_t) node->h.hash_next)
399 if (node->h.hashcode == hashcode
401 ? equals (elt, node->value)
402 : elt == node->value))
407 /* Look whether there is more than one match in the hash bucket. */
408 bool multiple_matches = false;
409 gl_list_node_t first_match = NULL;
411 for (node = (gl_list_node_t) list->table[bucket];
413 node = (gl_list_node_t) node->h.hash_next)
414 if (node->h.hashcode == hashcode
416 ? equals (elt, node->value)
417 : elt == node->value))
419 if (first_match == NULL)
423 multiple_matches = true;
427 if (multiple_matches)
429 /* We need the match with the smallest index. But we don't have
430 a fast mapping node -> index. So we have to walk the list. */
434 node = list->root.next;
435 for (; start_index > 0; start_index--)
440 node = node->next, index++)
441 if (node->h.hashcode == hashcode
443 ? equals (elt, node->value)
444 : elt == node->value))
446 /* The matches must have all been at indices < start_index or
453 /* Second step: Look up the index of the node. */
460 for (; node->prev != &list->root; node = node->prev)
463 if (index >= start_index && index < end_index)
469 gl_listelement_equals_fn equals = list->base.equals_fn;
470 size_t index = start_index;
471 gl_list_node_t node = list->root.next;
473 for (; start_index > 0; start_index--)
480 node = node->next, index++)
481 if (equals (elt, node->value))
488 node = node->next, index++)
489 if (elt == node->value)
497 static gl_list_node_t
498 gl_linked_add_first (gl_list_t list, const void *elt)
500 gl_list_node_t node =
501 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
503 ASYNCSAFE(const void *) node->value = elt;
506 (list->base.hashcode_fn != NULL
507 ? list->base.hashcode_fn (node->value)
508 : (size_t)(uintptr_t) node->value);
510 /* Add node to the hash table. */
511 add_to_bucket (list, node);
514 /* Add node to the list. */
515 node->prev = &list->root;
516 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
517 node->next->prev = node;
518 ASYNCSAFE(gl_list_node_t) list->root.next = node;
522 hash_resize_after_add (list);
528 static gl_list_node_t
529 gl_linked_add_last (gl_list_t list, const void *elt)
531 gl_list_node_t node =
532 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
534 ASYNCSAFE(const void *) node->value = elt;
537 (list->base.hashcode_fn != NULL
538 ? list->base.hashcode_fn (node->value)
539 : (size_t)(uintptr_t) node->value);
541 /* Add node to the hash table. */
542 add_to_bucket (list, node);
545 /* Add node to the list. */
546 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
547 node->prev = list->root.prev;
548 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
549 list->root.prev = node;
553 hash_resize_after_add (list);
559 static gl_list_node_t
560 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
562 gl_list_node_t new_node =
563 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
565 ASYNCSAFE(const void *) new_node->value = elt;
567 new_node->h.hashcode =
568 (list->base.hashcode_fn != NULL
569 ? list->base.hashcode_fn (new_node->value)
570 : (size_t)(uintptr_t) new_node->value);
572 /* Add new_node to the hash table. */
573 add_to_bucket (list, new_node);
576 /* Add new_node to the list. */
577 ASYNCSAFE(gl_list_node_t) new_node->next = node;
578 new_node->prev = node->prev;
579 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
580 node->prev = new_node;
584 hash_resize_after_add (list);
590 static gl_list_node_t
591 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
593 gl_list_node_t new_node =
594 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
596 ASYNCSAFE(const void *) new_node->value = elt;
598 new_node->h.hashcode =
599 (list->base.hashcode_fn != NULL
600 ? list->base.hashcode_fn (new_node->value)
601 : (size_t)(uintptr_t) new_node->value);
603 /* Add new_node to the hash table. */
604 add_to_bucket (list, new_node);
607 /* Add new_node to the list. */
608 new_node->prev = node;
609 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
610 new_node->next->prev = new_node;
611 ASYNCSAFE(gl_list_node_t) node->next = new_node;
615 hash_resize_after_add (list);
621 static gl_list_node_t
622 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
624 size_t count = list->count;
625 gl_list_node_t new_node;
627 if (!(position <= count))
628 /* Invalid argument. */
632 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
633 ASYNCSAFE(const void *) new_node->value = elt;
635 new_node->h.hashcode =
636 (list->base.hashcode_fn != NULL
637 ? list->base.hashcode_fn (new_node->value)
638 : (size_t)(uintptr_t) new_node->value);
640 /* Add new_node to the hash table. */
641 add_to_bucket (list, new_node);
644 /* Add new_node to the list. */
645 if (position <= (count / 2))
650 for (; position > 0; position--)
652 new_node->prev = node;
653 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
654 new_node->next->prev = new_node;
655 ASYNCSAFE(gl_list_node_t) node->next = new_node;
661 position = count - position;
663 for (; position > 0; position--)
665 ASYNCSAFE(gl_list_node_t) new_node->next = node;
666 new_node->prev = node->prev;
667 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
668 node->prev = new_node;
673 hash_resize_after_add (list);
680 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
686 /* Remove node from the hash table. */
687 remove_from_bucket (list, node);
690 /* Remove node from the list. */
694 ASYNCSAFE(gl_list_node_t) prev->next = next;
703 gl_linked_remove_at (gl_list_t list, size_t position)
705 size_t count = list->count;
706 gl_list_node_t removed_node;
708 if (!(position < count))
709 /* Invalid argument. */
711 /* Here we know count > 0. */
712 if (position <= ((count - 1) / 2))
715 gl_list_node_t after_removed;
718 for (; position > 0; position--)
720 removed_node = node->next;
721 after_removed = node->next->next;
722 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
723 after_removed->prev = node;
728 gl_list_node_t before_removed;
730 position = count - 1 - position;
732 for (; position > 0; position--)
734 removed_node = node->prev;
735 before_removed = node->prev->prev;
736 node->prev = before_removed;
737 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
740 remove_from_bucket (list, removed_node);
749 gl_linked_remove (gl_list_t list, const void *elt)
751 gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt);
754 return gl_linked_remove_node (list, node);
760 gl_linked_list_free (gl_list_t list)
764 for (node = list->root.next; node != &list->root; )
766 gl_list_node_t next = node->next;
776 /* --------------------- gl_list_iterator_t Data Type --------------------- */
778 static gl_list_iterator_t
779 gl_linked_iterator (gl_list_t list)
781 gl_list_iterator_t result;
783 result.vtable = list->base.vtable;
785 result.p = list->root.next;
786 result.q = &list->root;
796 static gl_list_iterator_t
797 gl_linked_iterator_from_to (gl_list_t list,
798 size_t start_index, size_t end_index)
800 gl_list_iterator_t result;
803 if (!(start_index <= end_index && end_index <= list->count))
804 /* Invalid arguments. */
806 result.vtable = list->base.vtable;
809 n2 = end_index - start_index;
810 n3 = list->count - end_index;
811 /* Find the maximum among n1, n2, n3, so as to reduce the number of
812 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
813 if (n1 > n2 && n1 > n3)
815 /* n1 is the maximum, use n2 and n3. */
820 for (i = n3; i > 0; i--)
823 for (i = n2; i > 0; i--)
829 /* n2 is the maximum, use n1 and n3. */
833 node = list->root.next;
834 for (i = n1; i > 0; i--)
839 for (i = n3; i > 0; i--)
845 /* n3 is the maximum, use n1 and n2. */
849 node = list->root.next;
850 for (i = n1; i > 0; i--)
853 for (i = n2; i > 0; i--)
868 gl_linked_iterator_next (gl_list_iterator_t *iterator,
869 const void **eltp, gl_list_node_t *nodep)
871 if (iterator->p != iterator->q)
873 gl_list_node_t node = (gl_list_node_t) iterator->p;
877 iterator->p = node->next;
885 gl_linked_iterator_free (gl_list_iterator_t *iterator)
889 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
891 static gl_list_node_t
892 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
897 for (node = list->root.next; node != &list->root; node = node->next)
899 int cmp = compar (node->value, elt);
909 static gl_list_node_t
910 gl_linked_sortedlist_search_from_to (gl_list_t list,
911 gl_listelement_compar_fn compar,
912 size_t low, size_t high,
915 size_t count = list->count;
917 if (!(low <= high && high <= list->count))
918 /* Invalid arguments. */
924 /* Here we know low < count. */
925 size_t position = low;
928 if (position <= ((count - 1) / 2))
930 node = list->root.next;
931 for (; position > 0; position--)
936 position = count - 1 - position;
937 node = list->root.prev;
938 for (; position > 0; position--)
944 int cmp = compar (node->value, elt);
958 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
964 for (node = list->root.next, index = 0;
966 node = node->next, index++)
968 int cmp = compar (node->value, elt);
979 gl_linked_sortedlist_indexof_from_to (gl_list_t list,
980 gl_listelement_compar_fn compar,
981 size_t low, size_t high,
984 size_t count = list->count;
986 if (!(low <= high && high <= list->count))
987 /* Invalid arguments. */
993 /* Here we know low < count. */
995 size_t position = low;
998 if (position <= ((count - 1) / 2))
1000 node = list->root.next;
1001 for (; position > 0; position--)
1006 position = count - 1 - position;
1007 node = list->root.prev;
1008 for (; position > 0; position--)
1014 int cmp = compar (node->value, elt);
1025 return (size_t)(-1);
1028 static gl_list_node_t
1029 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
1032 gl_list_node_t node;
1034 for (node = list->root.next; node != &list->root; node = node->next)
1035 if (compar (node->value, elt) >= 0)
1036 return gl_linked_add_before (list, node, elt);
1037 return gl_linked_add_last (list, elt);
1041 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
1044 gl_list_node_t node;
1046 for (node = list->root.next; node != &list->root; node = node->next)
1048 int cmp = compar (node->value, elt);
1053 return gl_linked_remove_node (list, node);