1 /* Sequential list data type implemented by a hash table with 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 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/>. */
21 #include "gl_linkedhash_list.h"
23 #include <stdint.h> /* for SIZE_MAX */
30 # define uintptr_t unsigned long
33 #define WITH_HASHTABLE 1
35 /* -------------------------- gl_list_t Data Type -------------------------- */
37 /* Generic hash-table code. */
38 #include "gl_anyhash_list1.h"
40 /* Generic linked list code. */
41 #include "gl_anylinked_list1.h"
43 /* Generic hash-table code. */
44 #include "gl_anyhash_list2.h"
46 /* Resize the hash table if needed, after list->count was incremented. */
48 hash_resize_after_add (gl_list_t list)
50 size_t count = list->count;
51 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
52 if (estimate > list->table_size)
53 hash_resize (list, estimate);
56 /* Add a node to the hash table structure. */
58 add_to_bucket (gl_list_t list, gl_list_node_t node)
60 size_t bucket = node->h.hashcode % list->table_size;
62 node->h.hash_next = list->table[bucket];
63 list->table[bucket] = &node->h;
66 /* Remove a node from the hash table structure. */
68 remove_from_bucket (gl_list_t list, gl_list_node_t node)
70 size_t bucket = node->h.hashcode % list->table_size;
73 for (p = &list->table[bucket]; ; p = &(*p)->hash_next)
77 *p = node->h.hash_next;
81 /* node is not in the right bucket. Did the hash codes
82 change inadvertently? */
87 /* Generic linked list code. */
88 #include "gl_anylinked_list2.h"
91 const struct gl_list_implementation gl_linkedhash_list_implementation =
93 gl_linked_create_empty,
98 gl_linked_previous_node,
101 gl_linked_search_from_to,
102 gl_linked_indexof_from_to,
105 gl_linked_add_before,
108 gl_linked_remove_node,
113 gl_linked_iterator_from_to,
114 gl_linked_iterator_next,
115 gl_linked_iterator_free,
116 gl_linked_sortedlist_search,
117 gl_linked_sortedlist_search_from_to,
118 gl_linked_sortedlist_indexof,
119 gl_linked_sortedlist_indexof_from_to,
120 gl_linked_sortedlist_add,
121 gl_linked_sortedlist_remove