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.
4
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)
8 any later version.
9
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.
14
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. */
18
19 #include <config.h>
20
21 /* Specification. */
22 #include "gl_linkedhash_list.h"
23
24 #include <stdint.h> /* for SIZE_MAX */
25 #include <stdlib.h>
26
27 #include "xalloc.h"
28 #include "xsize.h"
29
30 #ifndef uintptr_t
31 # define uintptr_t unsigned long
32 #endif
33
34 #define WITH_HASHTABLE 1
35
36 /* -------------------------- gl_list_t Data Type -------------------------- */
37
38 /* Generic hash-table code. */
39 #include "gl_anyhash_list1.h"
40
41 /* Generic linked list code. */
42 #include "gl_anylinked_list1.h"
43
44 /* Generic hash-table code. */
45 #include "gl_anyhash_list2.h"
46
47 /* Resize the hash table if needed, after list->count was incremented. */
48 static inline void
hash_resize_after_add(gl_list_t list)49 hash_resize_after_add (gl_list_t list)
50 {
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);
55 }
56
57 /* Add a node to the hash table structure. */
58 static inline void
add_to_bucket(gl_list_t list,gl_list_node_t node)59 add_to_bucket (gl_list_t list, gl_list_node_t node)
60 {
61 size_t bucket = node->h.hashcode % list->table_size;
62
63 node->h.hash_next = list->table[bucket];
64 list->table[bucket] = &node->h;
65 }
66
67 /* Remove a node from the hash table structure. */
68 static inline void
remove_from_bucket(gl_list_t list,gl_list_node_t node)69 remove_from_bucket (gl_list_t list, gl_list_node_t node)
70 {
71 size_t bucket = node->h.hashcode % list->table_size;
72 gl_hash_entry_t *p;
73
74 for (p = &list->table[bucket]; ; p = &(*p)->hash_next)
75 {
76 if (*p == &node->h)
77 {
78 *p = node->h.hash_next;
79 break;
80 }
81 if (*p == NULL)
82 /* node is not in the right bucket. Did the hash codes
83 change inadvertently? */
84 abort ();
85 }
86 }
87
88 /* Generic linked list code. */
89 #include "gl_anylinked_list2.h"
90
91
92 const struct gl_list_implementation gl_linkedhash_list_implementation =
93 {
94 gl_linked_create_empty,
95 gl_linked_create,
96 gl_linked_size,
97 gl_linked_node_value,
98 gl_linked_next_node,
99 gl_linked_previous_node,
100 gl_linked_get_at,
101 gl_linked_set_at,
102 gl_linked_search_from_to,
103 gl_linked_indexof_from_to,
104 gl_linked_add_first,
105 gl_linked_add_last,
106 gl_linked_add_before,
107 gl_linked_add_after,
108 gl_linked_add_at,
109 gl_linked_remove_node,
110 gl_linked_remove_at,
111 gl_linked_remove,
112 gl_linked_list_free,
113 gl_linked_iterator,
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_search_from_to,
119 gl_linked_sortedlist_indexof,
120 gl_linked_sortedlist_indexof_from_to,
121 gl_linked_sortedlist_add,
122 gl_linked_sortedlist_remove
123 };
124