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 (gl_list_t list, const void *elt)
222 (list->base.hashcode_fn != NULL
223 ? list->base.hashcode_fn (elt)
224 : (size_t)(uintptr_t) elt);
225 size_t index = hashcode % list->table_size;
226 gl_listelement_equals_fn equals = list->base.equals_fn;
228 if (!list->base.allow_duplicates)
230 /* Look for the first match in the hash bucket. */
233 for (node = (gl_list_node_t) list->table[index];
235 node = (gl_list_node_t) node->h.hash_next)
236 if (node->h.hashcode == hashcode
238 ? equals (elt, node->value)
239 : elt == node->value))
245 /* Look whether there is more than one match in the hash bucket. */
246 bool multiple_matches = false;
247 gl_list_node_t first_match = NULL;
250 for (node = (gl_list_node_t) list->table[index];
252 node = (gl_list_node_t) node->h.hash_next)
253 if (node->h.hashcode == hashcode
255 ? equals (elt, node->value)
256 : elt == node->value))
258 if (first_match == NULL)
262 multiple_matches = true;
266 if (!multiple_matches)
270 /* We need the match with the smallest index. But we don't have
271 a fast mapping node -> index. So we have to walk the list. */
272 for (node = list->root.next; node != &list->root; node = node->next)
273 if (node->h.hashcode == hashcode
275 ? equals (elt, node->value)
276 : elt == node->value))
278 /* We know there are at least two matches. */
283 gl_listelement_equals_fn equals = list->base.equals_fn;
288 for (node = list->root.next; node != &list->root; node = node->next)
289 if (equals (elt, node->value))
294 for (node = list->root.next; node != &list->root; node = node->next)
295 if (elt == node->value)
303 gl_linked_indexof (gl_list_t list, const void *elt)
306 /* Here the hash table doesn't help much. It only allows us to minimize
307 the number of equals() calls, by looking up first the node and then
310 (list->base.hashcode_fn != NULL
311 ? list->base.hashcode_fn (elt)
312 : (size_t)(uintptr_t) elt);
313 size_t index = hashcode % list->table_size;
314 gl_listelement_equals_fn equals = list->base.equals_fn;
317 /* First step: Look up the node. */
318 if (!list->base.allow_duplicates)
320 /* Look for the first match in the hash bucket. */
321 for (node = (gl_list_node_t) list->table[index];
323 node = (gl_list_node_t) node->h.hash_next)
324 if (node->h.hashcode == hashcode
326 ? equals (elt, node->value)
327 : elt == node->value))
332 /* Look whether there is more than one match in the hash bucket. */
333 bool multiple_matches = false;
334 gl_list_node_t first_match = NULL;
336 for (node = (gl_list_node_t) list->table[index];
338 node = (gl_list_node_t) node->h.hash_next)
339 if (node->h.hashcode == hashcode
341 ? equals (elt, node->value)
342 : elt == node->value))
344 if (first_match == NULL)
348 multiple_matches = true;
352 if (multiple_matches)
354 /* We need the match with the smallest index. But we don't have
355 a fast mapping node -> index. So we have to walk the list. */
358 for (node = list->root.next, index = 0;
360 node = node->next, index++)
361 if (node->h.hashcode == hashcode
363 ? equals (elt, node->value)
364 : elt == node->value))
366 /* We know there are at least two matches. */
372 /* Second step: Look up the index of the node. */
379 for (; node->prev != &list->root; node = node->prev)
385 gl_listelement_equals_fn equals = list->base.equals_fn;
391 for (node = list->root.next, index = 0;
393 node = node->next, index++)
394 if (equals (elt, node->value))
400 for (node = list->root.next, index = 0;
402 node = node->next, index++)
403 if (elt == node->value)
410 static gl_list_node_t
411 gl_linked_add_first (gl_list_t list, const void *elt)
413 gl_list_node_t node =
414 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
416 ASYNCSAFE(const void *) node->value = elt;
419 (list->base.hashcode_fn != NULL
420 ? list->base.hashcode_fn (node->value)
421 : (size_t)(uintptr_t) node->value);
423 /* Add node to the hash table. */
424 add_to_bucket (list, node);
427 /* Add node to the list. */
428 node->prev = &list->root;
429 ASYNCSAFE(gl_list_node_t) node->next = list->root.next;
430 node->next->prev = node;
431 ASYNCSAFE(gl_list_node_t) list->root.next = node;
435 hash_resize_after_add (list);
441 static gl_list_node_t
442 gl_linked_add_last (gl_list_t list, const void *elt)
444 gl_list_node_t node =
445 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
447 ASYNCSAFE(const void *) node->value = elt;
450 (list->base.hashcode_fn != NULL
451 ? list->base.hashcode_fn (node->value)
452 : (size_t)(uintptr_t) node->value);
454 /* Add node to the hash table. */
455 add_to_bucket (list, node);
458 /* Add node to the list. */
459 ASYNCSAFE(gl_list_node_t) node->next = &list->root;
460 node->prev = list->root.prev;
461 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
462 list->root.prev = node;
466 hash_resize_after_add (list);
472 static gl_list_node_t
473 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
475 gl_list_node_t new_node =
476 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
478 ASYNCSAFE(const void *) new_node->value = elt;
480 new_node->h.hashcode =
481 (list->base.hashcode_fn != NULL
482 ? list->base.hashcode_fn (new_node->value)
483 : (size_t)(uintptr_t) new_node->value);
485 /* Add new_node to the hash table. */
486 add_to_bucket (list, new_node);
489 /* Add new_node to the list. */
490 ASYNCSAFE(gl_list_node_t) new_node->next = node;
491 new_node->prev = node->prev;
492 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
493 node->prev = new_node;
497 hash_resize_after_add (list);
503 static gl_list_node_t
504 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
506 gl_list_node_t new_node =
507 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
509 ASYNCSAFE(const void *) new_node->value = elt;
511 new_node->h.hashcode =
512 (list->base.hashcode_fn != NULL
513 ? list->base.hashcode_fn (new_node->value)
514 : (size_t)(uintptr_t) new_node->value);
516 /* Add new_node to the hash table. */
517 add_to_bucket (list, new_node);
520 /* Add new_node to the list. */
521 new_node->prev = node;
522 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
523 new_node->next->prev = new_node;
524 ASYNCSAFE(gl_list_node_t) node->next = new_node;
528 hash_resize_after_add (list);
534 static gl_list_node_t
535 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
537 size_t count = list->count;
538 gl_list_node_t new_node;
540 if (!(position <= count))
541 /* Invalid argument. */
545 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
546 ASYNCSAFE(const void *) new_node->value = elt;
548 new_node->h.hashcode =
549 (list->base.hashcode_fn != NULL
550 ? list->base.hashcode_fn (new_node->value)
551 : (size_t)(uintptr_t) new_node->value);
553 /* Add new_node to the hash table. */
554 add_to_bucket (list, new_node);
557 /* Add new_node to the list. */
558 if (position <= (count / 2))
563 for (; position > 0; position--)
565 new_node->prev = node;
566 ASYNCSAFE(gl_list_node_t) new_node->next = node->next;
567 new_node->next->prev = new_node;
568 ASYNCSAFE(gl_list_node_t) node->next = new_node;
574 position = count - position;
576 for (; position > 0; position--)
578 ASYNCSAFE(gl_list_node_t) new_node->next = node;
579 new_node->prev = node->prev;
580 ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node;
581 node->prev = new_node;
586 hash_resize_after_add (list);
593 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
599 /* Remove node from the hash table. */
600 remove_from_bucket (list, node);
603 /* Remove node from the list. */
607 ASYNCSAFE(gl_list_node_t) prev->next = next;
616 gl_linked_remove_at (gl_list_t list, size_t position)
618 size_t count = list->count;
619 gl_list_node_t removed_node;
621 if (!(position < count))
622 /* Invalid argument. */
624 /* Here we know count > 0. */
625 if (position <= ((count - 1) / 2))
628 gl_list_node_t after_removed;
631 for (; position > 0; position--)
633 removed_node = node->next;
634 after_removed = node->next->next;
635 ASYNCSAFE(gl_list_node_t) node->next = after_removed;
636 after_removed->prev = node;
641 gl_list_node_t before_removed;
643 position = count - 1 - position;
645 for (; position > 0; position--)
647 removed_node = node->prev;
648 before_removed = node->prev->prev;
649 node->prev = before_removed;
650 ASYNCSAFE(gl_list_node_t) before_removed->next = node;
653 remove_from_bucket (list, removed_node);
662 gl_linked_remove (gl_list_t list, const void *elt)
664 gl_list_node_t node = gl_linked_search (list, elt);
667 return gl_linked_remove_node (list, node);
673 gl_linked_list_free (gl_list_t list)
677 for (node = list->root.next; node != &list->root; )
679 gl_list_node_t next = node->next;
689 /* --------------------- gl_list_iterator_t Data Type --------------------- */
691 static gl_list_iterator_t
692 gl_linked_iterator (gl_list_t list)
694 gl_list_iterator_t result;
696 result.vtable = list->base.vtable;
698 result.p = list->root.next;
699 result.q = &list->root;
704 static gl_list_iterator_t
705 gl_linked_iterator_from_to (gl_list_t list,
706 size_t start_index, size_t end_index)
708 gl_list_iterator_t result;
711 if (!(start_index <= end_index && end_index <= list->count))
712 /* Invalid arguments. */
714 result.vtable = list->base.vtable;
717 n2 = end_index - start_index;
718 n3 = list->count - end_index;
719 /* Find the maximum among n1, n2, n3, so as to reduce the number of
720 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
721 if (n1 > n2 && n1 > n3)
723 /* n1 is the maximum, use n2 and n3. */
728 for (i = n3; i > 0; i--)
731 for (i = n2; i > 0; i--)
737 /* n2 is the maximum, use n1 and n3. */
741 node = list->root.next;
742 for (i = n1; i > 0; i--)
747 for (i = n3; i > 0; i--)
753 /* n3 is the maximum, use n1 and n2. */
757 node = list->root.next;
758 for (i = n1; i > 0; i--)
761 for (i = n2; i > 0; i--)
770 gl_linked_iterator_next (gl_list_iterator_t *iterator,
771 const void **eltp, gl_list_node_t *nodep)
773 if (iterator->p != iterator->q)
775 gl_list_node_t node = (gl_list_node_t) iterator->p;
779 iterator->p = node->next;
787 gl_linked_iterator_free (gl_list_iterator_t *iterator)
791 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
793 static gl_list_node_t
794 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
799 for (node = list->root.next; node != &list->root; node = node->next)
801 int cmp = compar (node->value, elt);
812 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
818 for (node = list->root.next, index = 0;
820 node = node->next, index++)
822 int cmp = compar (node->value, elt);
832 static gl_list_node_t
833 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
838 for (node = list->root.next; node != &list->root; node = node->next)
839 if (compar (node->value, elt) >= 0)
840 return gl_linked_add_before (list, node, elt);
841 return gl_linked_add_last (list, elt);
845 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
850 for (node = list->root.next; node != &list->root; node = node->next)
852 int cmp = compar (node->value, elt);
857 return gl_linked_remove_node (list, node);