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 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. */
24 #include "gl_linked_list.h"
33 # define uintptr_t unsigned long
36 #define WITH_HASHTABLE 1
38 /* -------------------------- gl_list_t Data Type -------------------------- */
40 /* Generic hash-table code. */
41 #include "gl_anyhash_list1.h"
43 /* Generic linked list code. */
44 #include "gl_anylinked_list1.h"
46 /* Generic hash-table code. */
47 #include "gl_anyhash_list2.h"
49 /* Resize the hash table if needed, after list->count was incremented. */
51 hash_resize_after_add (gl_list_t list)
53 size_t count = list->count;
54 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
55 if (estimate > list->table_size)
56 hash_resize (list, estimate);
59 /* Add a node to the hash table structure. */
61 add_to_bucket (gl_list_t list, gl_list_node_t node)
63 size_t index = node->h.hashcode % list->table_size;
65 node->h.hash_next = list->table[index];
66 list->table[index] = &node->h;
69 /* Remove a node from the hash table structure. */
71 remove_from_bucket (gl_list_t list, gl_list_node_t node)
73 size_t index = node->h.hashcode % list->table_size;
76 for (p = &list->table[index]; ; p = &(*p)->hash_next)
80 *p = node->h.hash_next;
84 /* node is not in the right bucket. Did the hash codes
85 change inadvertently? */
90 /* Generic linked list code. */
91 #include "gl_anylinked_list2.h"
94 const struct gl_list_implementation gl_linkedhash_list_implementation =
96 gl_linked_create_empty,
101 gl_linked_previous_node,
108 gl_linked_add_before,
111 gl_linked_remove_node,
116 gl_linked_iterator_from_to,
117 gl_linked_iterator_next,
118 gl_linked_iterator_free,
119 gl_linked_sortedlist_search,
120 gl_linked_sortedlist_indexof,
121 gl_linked_sortedlist_add,
122 gl_linked_sortedlist_remove