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. */
22 #include "gl_linkedhash_list.h"
31 # define uintptr_t unsigned long
34 #define WITH_HASHTABLE 1
36 /* -------------------------- gl_list_t Data Type -------------------------- */
38 /* Generic hash-table code. */
39 #include "gl_anyhash_list1.h"
41 /* Generic linked list code. */
42 #include "gl_anylinked_list1.h"
44 /* Generic hash-table code. */
45 #include "gl_anyhash_list2.h"
47 /* Resize the hash table if needed, after list->count was incremented. */
49 hash_resize_after_add (gl_list_t list)
51 size_t count = list->count;
52 size_t estimate = xsum (count, count / 2); /* 1.5 * count */
53 if (estimate > list->table_size)
54 hash_resize (list, estimate);
57 /* Add a node to the hash table structure. */
59 add_to_bucket (gl_list_t list, gl_list_node_t node)
61 size_t index = node->h.hashcode % list->table_size;
63 node->h.hash_next = list->table[index];
64 list->table[index] = &node->h;
67 /* Remove a node from the hash table structure. */
69 remove_from_bucket (gl_list_t list, gl_list_node_t node)
71 size_t index = node->h.hashcode % list->table_size;
74 for (p = &list->table[index]; ; p = &(*p)->hash_next)
78 *p = node->h.hash_next;
82 /* node is not in the right bucket. Did the hash codes
83 change inadvertently? */
88 /* Generic linked list code. */
89 #include "gl_anylinked_list2.h"
92 const struct gl_list_implementation gl_linkedhash_list_implementation =
94 gl_linked_create_empty,
99 gl_linked_previous_node,
106 gl_linked_add_before,
109 gl_linked_remove_node,
114 gl_linked_iterator_from_to,
115 gl_linked_iterator_next,
116 gl_linked_iterator_free,
117 gl_linked_sortedlist_search,
118 gl_linked_sortedlist_indexof,
119 gl_linked_sortedlist_add,
120 gl_linked_sortedlist_remove