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 /* -------------------------- gl_list_t Data Type -------------------------- */
24 gl_linked_create_empty (gl_list_implementation_t implementation,
25 gl_listelement_equals_fn equals_fn,
26 gl_listelement_hashcode_fn hashcode_fn,
27 bool allow_duplicates)
29 struct gl_list_impl *list =
30 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
32 list->base.vtable = implementation;
33 list->base.equals_fn = equals_fn;
34 list->base.hashcode_fn = hashcode_fn;
35 list->base.allow_duplicates = allow_duplicates;
37 list->table_size = 11;
39 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
41 list->root.next = &list->root;
42 list->root.prev = &list->root;
49 gl_linked_create (gl_list_implementation_t implementation,
50 gl_listelement_equals_fn equals_fn,
51 gl_listelement_hashcode_fn hashcode_fn,
52 bool allow_duplicates,
53 size_t count, const void **contents)
55 struct gl_list_impl *list =
56 (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
59 list->base.vtable = implementation;
60 list->base.equals_fn = equals_fn;
61 list->base.hashcode_fn = hashcode_fn;
62 list->base.allow_duplicates = allow_duplicates;
65 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
68 list->table_size = next_prime (estimate);
70 (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
75 for (; count > 0; contents++, count--)
78 (struct gl_list_node_impl *)
79 xmalloc (sizeof (struct gl_list_node_impl));
81 node->value = *contents;
84 (list->base.hashcode_fn != NULL
85 ? list->base.hashcode_fn (node->value)
86 : (size_t)(uintptr_t) node->value);
88 /* Add node to the hash table. */
89 add_to_bucket (list, node);
92 /* Add node to the list. */
97 tail->next = &list->root;
98 list->root.prev = tail;
104 gl_linked_size (gl_list_t list)
110 gl_linked_node_value (gl_list_t list, gl_list_node_t node)
115 static gl_list_node_t
116 gl_linked_next_node (gl_list_t list, gl_list_node_t node)
118 return (node->next != &list->root ? node->next : NULL);
121 static gl_list_node_t
122 gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
124 return (node->prev != &list->root ? node->prev : NULL);
128 gl_linked_get_at (gl_list_t list, size_t position)
130 size_t count = list->count;
133 if (!(position < count))
134 /* Invalid argument. */
136 /* Here we know count > 0. */
137 if (position <= ((count - 1) / 2))
139 node = list->root.next;
140 for (; position > 0; position--)
145 position = count - 1 - position;
146 node = list->root.prev;
147 for (; position > 0; position--)
153 static gl_list_node_t
154 gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
156 size_t count = list->count;
159 if (!(position < count))
160 /* Invalid argument. */
162 /* Here we know count > 0. */
163 if (position <= ((count - 1) / 2))
165 node = list->root.next;
166 for (; position > 0; position--)
171 position = count - 1 - position;
172 node = list->root.prev;
173 for (; position > 0; position--)
177 if (elt != node->value)
179 size_t new_hashcode =
180 (list->base.hashcode_fn != NULL
181 ? list->base.hashcode_fn (elt)
182 : (size_t)(uintptr_t) elt);
184 if (new_hashcode != node->h.hashcode)
186 remove_from_bucket (list, node);
188 node->h.hashcode = new_hashcode;
189 add_to_bucket (list, node);
200 static gl_list_node_t
201 gl_linked_search (gl_list_t list, const void *elt)
205 (list->base.hashcode_fn != NULL
206 ? list->base.hashcode_fn (elt)
207 : (size_t)(uintptr_t) elt);
208 size_t index = hashcode % list->table_size;
209 gl_listelement_equals_fn equals = list->base.equals_fn;
211 if (!list->base.allow_duplicates)
213 /* Look for the first match in the hash bucket. */
216 for (node = (gl_list_node_t) list->table[index];
218 node = (gl_list_node_t) node->h.hash_next)
219 if (node->h.hashcode == hashcode
221 ? equals (elt, node->value)
222 : elt == node->value))
228 /* Look whether there is more than one match in the hash bucket. */
229 bool multiple_matches = false;
230 gl_list_node_t first_match = NULL;
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))
241 if (first_match == NULL)
245 multiple_matches = true;
249 if (!multiple_matches)
253 /* We need the match with the smallest index. But we don't have
254 a fast mapping node -> index. So we have to walk the list. */
255 for (node = list->root.next; node != &list->root; node = node->next)
256 if (node->h.hashcode == hashcode
258 ? equals (elt, node->value)
259 : elt == node->value))
261 /* We know there are at least two matches. */
266 gl_listelement_equals_fn equals = list->base.equals_fn;
271 for (node = list->root.next; node != &list->root; node = node->next)
272 if (equals (elt, node->value))
277 for (node = list->root.next; node != &list->root; node = node->next)
278 if (elt == node->value)
286 gl_linked_indexof (gl_list_t list, const void *elt)
289 /* Here the hash table doesn't help much. It only allows us to minimize
290 the number of equals() calls, by looking up first the node and then
293 (list->base.hashcode_fn != NULL
294 ? list->base.hashcode_fn (elt)
295 : (size_t)(uintptr_t) elt);
296 size_t index = hashcode % list->table_size;
297 gl_listelement_equals_fn equals = list->base.equals_fn;
300 /* First step: Look up the node. */
301 if (!list->base.allow_duplicates)
303 /* Look for the first match in the hash bucket. */
304 for (node = (gl_list_node_t) list->table[index];
306 node = (gl_list_node_t) node->h.hash_next)
307 if (node->h.hashcode == hashcode
309 ? equals (elt, node->value)
310 : elt == node->value))
315 /* Look whether there is more than one match in the hash bucket. */
316 bool multiple_matches = false;
317 gl_list_node_t first_match = NULL;
319 for (node = (gl_list_node_t) list->table[index];
321 node = (gl_list_node_t) node->h.hash_next)
322 if (node->h.hashcode == hashcode
324 ? equals (elt, node->value)
325 : elt == node->value))
327 if (first_match == NULL)
331 multiple_matches = true;
335 if (multiple_matches)
337 /* We need the match with the smallest index. But we don't have
338 a fast mapping node -> index. So we have to walk the list. */
341 for (node = list->root.next, index = 0;
343 node = node->next, index++)
344 if (node->h.hashcode == hashcode
346 ? equals (elt, node->value)
347 : elt == node->value))
349 /* We know there are at least two matches. */
355 /* Second step: Look up the index of the node. */
362 for (; node->prev != &list->root; node = node->prev)
368 gl_listelement_equals_fn equals = list->base.equals_fn;
374 for (node = list->root.next, index = 0;
376 node = node->next, index++)
377 if (equals (elt, node->value))
383 for (node = list->root.next, index = 0;
385 node = node->next, index++)
386 if (elt == node->value)
393 static gl_list_node_t
394 gl_linked_add_first (gl_list_t list, const void *elt)
396 gl_list_node_t node =
397 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
402 (list->base.hashcode_fn != NULL
403 ? list->base.hashcode_fn (node->value)
404 : (size_t)(uintptr_t) node->value);
406 /* Add node to the hash table. */
407 add_to_bucket (list, node);
410 /* Add node to the list. */
411 node->prev = &list->root;
412 node->next = list->root.next;
413 node->next->prev = node;
414 list->root.next = node;
418 hash_resize_after_add (list);
424 static gl_list_node_t
425 gl_linked_add_last (gl_list_t list, const void *elt)
427 gl_list_node_t node =
428 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
433 (list->base.hashcode_fn != NULL
434 ? list->base.hashcode_fn (node->value)
435 : (size_t)(uintptr_t) node->value);
437 /* Add node to the hash table. */
438 add_to_bucket (list, node);
441 /* Add node to the list. */
442 node->next = &list->root;
443 node->prev = list->root.prev;
444 node->prev->next = node;
445 list->root.prev = node;
449 hash_resize_after_add (list);
455 static gl_list_node_t
456 gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
458 gl_list_node_t new_node =
459 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
461 new_node->value = elt;
463 new_node->h.hashcode =
464 (list->base.hashcode_fn != NULL
465 ? list->base.hashcode_fn (new_node->value)
466 : (size_t)(uintptr_t) new_node->value);
468 /* Add new_node to the hash table. */
469 add_to_bucket (list, new_node);
472 /* Add new_node to the list. */
473 new_node->next = node;
474 new_node->prev = node->prev;
475 new_node->prev->next = new_node;
476 node->prev = new_node;
480 hash_resize_after_add (list);
486 static gl_list_node_t
487 gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
489 gl_list_node_t new_node =
490 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
492 new_node->value = elt;
494 new_node->h.hashcode =
495 (list->base.hashcode_fn != NULL
496 ? list->base.hashcode_fn (new_node->value)
497 : (size_t)(uintptr_t) new_node->value);
499 /* Add new_node to the hash table. */
500 add_to_bucket (list, new_node);
503 /* Add new_node to the list. */
504 new_node->prev = node;
505 new_node->next = node->next;
506 new_node->next->prev = new_node;
507 node->next = new_node;
511 hash_resize_after_add (list);
517 static gl_list_node_t
518 gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
520 size_t count = list->count;
521 gl_list_node_t new_node;
523 if (!(position <= count))
524 /* Invalid argument. */
528 (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
529 new_node->value = elt;
531 new_node->h.hashcode =
532 (list->base.hashcode_fn != NULL
533 ? list->base.hashcode_fn (new_node->value)
534 : (size_t)(uintptr_t) new_node->value);
536 /* Add new_node to the hash table. */
537 add_to_bucket (list, new_node);
540 /* Add new_node to the list. */
541 if (position <= (count / 2))
546 for (; position > 0; position--)
548 new_node->prev = node;
549 new_node->next = node->next;
550 new_node->next->prev = new_node;
551 node->next = new_node;
557 position = count - position;
559 for (; position > 0; position--)
561 new_node->next = node;
562 new_node->prev = node->prev;
563 new_node->prev->next = new_node;
564 node->prev = new_node;
569 hash_resize_after_add (list);
576 gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
582 /* Remove node from the hash table. */
583 remove_from_bucket (list, node);
586 /* Remove node from the list. */
599 gl_linked_remove_at (gl_list_t list, size_t position)
601 size_t count = list->count;
602 gl_list_node_t removed_node;
604 if (!(position < count))
605 /* Invalid argument. */
607 /* Here we know count > 0. */
608 if (position <= ((count - 1) / 2))
611 gl_list_node_t after_removed;
614 for (; position > 0; position--)
616 removed_node = node->next;
617 after_removed = node->next->next;
618 node->next = after_removed;
619 after_removed->prev = node;
624 gl_list_node_t before_removed;
626 position = count - 1 - position;
628 for (; position > 0; position--)
630 removed_node = node->prev;
631 before_removed = node->prev->prev;
632 node->prev = before_removed;
633 before_removed->next = node;
636 remove_from_bucket (list, removed_node);
645 gl_linked_remove (gl_list_t list, const void *elt)
647 gl_list_node_t node = gl_linked_search (list, elt);
650 return gl_linked_remove_node (list, node);
656 gl_linked_list_free (gl_list_t list)
660 for (node = list->root.next; node != &list->root; )
662 gl_list_node_t next = node->next;
672 /* --------------------- gl_list_iterator_t Data Type --------------------- */
674 static gl_list_iterator_t
675 gl_linked_iterator (gl_list_t list)
677 gl_list_iterator_t result;
679 result.vtable = list->base.vtable;
681 result.p = list->root.next;
682 result.q = &list->root;
687 static gl_list_iterator_t
688 gl_linked_iterator_from_to (gl_list_t list,
689 size_t start_index, size_t end_index)
691 gl_list_iterator_t result;
694 if (!(start_index <= end_index && end_index <= list->count))
695 /* Invalid arguments. */
697 result.vtable = list->base.vtable;
700 n2 = end_index - start_index;
701 n3 = list->count - end_index;
702 /* Find the maximum among n1, n2, n3, so as to reduce the number of
703 loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */
704 if (n1 > n2 && n1 > n3)
706 /* n1 is the maximum, use n2 and n3. */
711 for (i = n3; i > 0; i--)
714 for (i = n2; i > 0; i--)
720 /* n2 is the maximum, use n1 and n3. */
724 node = list->root.next;
725 for (i = n1; i > 0; i--)
730 for (i = n3; i > 0; i--)
736 /* n3 is the maximum, use n1 and n2. */
740 node = list->root.next;
741 for (i = n1; i > 0; i--)
744 for (i = n2; i > 0; i--)
753 gl_linked_iterator_next (gl_list_iterator_t *iterator,
754 const void **eltp, gl_list_node_t *nodep)
756 if (iterator->p != iterator->q)
758 gl_list_node_t node = (gl_list_node_t) iterator->p;
762 iterator->p = node->next;
770 gl_linked_iterator_free (gl_list_iterator_t *iterator)
774 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
776 static gl_list_node_t
777 gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
782 for (node = list->root.next; node != &list->root; node = node->next)
784 int cmp = compar (node->value, elt);
795 gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
801 for (node = list->root.next, index = 0;
803 node = node->next, index++)
805 int cmp = compar (node->value, elt);
815 static gl_list_node_t
816 gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
821 for (node = list->root.next; node != &list->root; node = node->next)
822 if (compar (node->value, elt) >= 0)
823 return gl_linked_add_before (list, node, elt);
824 return gl_linked_add_last (list, elt);
828 gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
833 for (node = list->root.next; node != &list->root; node = node->next)
835 int cmp = compar (node->value, elt);
840 return gl_linked_remove_node (list, node);