1 /* Set data type implemented by a hash table with a linked list.
2 Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2018.
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 <https://www.gnu.org/licenses/>. */
21 #include "gl_linkedhash_set.h"
23 #include <stdint.h> /* for SIZE_MAX */
29 # define uintptr_t unsigned long
32 /* --------------------------- gl_set_t Data Type --------------------------- */
34 #include "gl_anyhash1.h"
36 /* Concrete list node implementation, valid for this file only. */
37 struct gl_list_node_impl
39 struct gl_hash_entry h
; /* hash table entry fields; must be first */
40 struct gl_list_node_impl
*next
;
41 struct gl_list_node_impl
*prev
;
44 typedef struct gl_list_node_impl
* gl_list_node_t
;
46 /* Concrete gl_set_impl type, valid for this file only. */
49 struct gl_set_impl_base base
;
50 gl_setelement_hashcode_fn hashcode_fn
;
51 /* A hash table: managed as an array of collision lists. */
52 struct gl_hash_entry
**table
;
54 /* A circular list anchored at root.
55 The first node is = root.next, the last node is = root.prev.
56 The root's value is unused. */
57 struct gl_list_node_impl root
;
58 /* Number of list nodes, excluding the root. */
62 #define CONTAINER_T gl_set_t
63 #define CONTAINER_COUNT(set) (set)->count
64 #include "gl_anyhash2.h"
66 /* If the symbol SIGNAL_SAFE_SET is defined, the code is compiled in such
67 a way that a gl_set_t data structure may be used from within a signal
68 handler. The operations allowed in the signal handler are:
69 gl_set_iterator, gl_set_iterator_next, gl_set_iterator_free.
70 The set and node fields that are therefore accessed from the signal handler
72 set->root, node->next, node->value.
73 We are careful to make modifications to these fields only in an order
74 that maintains the consistency of the list data structure at any moment,
75 and we use 'volatile' assignments to prevent the compiler from reordering
77 #ifdef SIGNAL_SAFE_SET
78 # define ASYNCSAFE(type) *(type volatile *)&
80 # define ASYNCSAFE(type)
83 /* --------------------------- gl_set_t Data Type --------------------------- */
86 gl_linkedhash_nx_create_empty (gl_set_implementation_t implementation
,
87 gl_setelement_equals_fn equals_fn
,
88 gl_setelement_hashcode_fn hashcode_fn
,
89 gl_setelement_dispose_fn dispose_fn
)
91 struct gl_set_impl
*set
=
92 (struct gl_set_impl
*) malloc (sizeof (struct gl_set_impl
));
97 set
->base
.vtable
= implementation
;
98 set
->base
.equals_fn
= equals_fn
;
99 set
->base
.dispose_fn
= dispose_fn
;
100 set
->hashcode_fn
= hashcode_fn
;
101 set
->table_size
= 11;
103 (gl_hash_entry_t
*) calloc (set
->table_size
, sizeof (gl_hash_entry_t
));
104 if (set
->table
== NULL
)
106 set
->root
.next
= &set
->root
;
107 set
->root
.prev
= &set
->root
;
117 static size_t _GL_ATTRIBUTE_PURE
118 gl_linkedhash_size (gl_set_t set
)
123 static bool _GL_ATTRIBUTE_PURE
124 gl_linkedhash_search (gl_set_t set
, const void *elt
)
127 (set
->hashcode_fn
!= NULL
128 ? set
->hashcode_fn (elt
)
129 : (size_t)(uintptr_t) elt
);
130 size_t bucket
= hashcode
% set
->table_size
;
131 gl_setelement_equals_fn equals
= set
->base
.equals_fn
;
133 /* Look for a match in the hash bucket. */
136 for (node
= (gl_list_node_t
) set
->table
[bucket
];
138 node
= (gl_list_node_t
) node
->h
.hash_next
)
139 if (node
->h
.hashcode
== hashcode
141 ? equals (elt
, node
->value
)
142 : elt
== node
->value
))
148 gl_linkedhash_nx_add (gl_set_t set
, const void *elt
)
151 (set
->hashcode_fn
!= NULL
152 ? set
->hashcode_fn (elt
)
153 : (size_t)(uintptr_t) elt
);
154 size_t bucket
= hashcode
% set
->table_size
;
155 gl_setelement_equals_fn equals
= set
->base
.equals_fn
;
157 /* Look for a match in the hash bucket. */
161 for (node
= (gl_list_node_t
) set
->table
[bucket
];
163 node
= (gl_list_node_t
) node
->h
.hash_next
)
164 if (node
->h
.hashcode
== hashcode
166 ? equals (elt
, node
->value
)
167 : elt
== node
->value
))
171 /* Allocate a new node. */
172 gl_list_node_t node
=
173 (struct gl_list_node_impl
*) malloc (sizeof (struct gl_list_node_impl
));
178 ASYNCSAFE(const void *) node
->value
= elt
;
179 node
->h
.hashcode
= hashcode
;
181 /* Add node to the hash table. */
182 node
->h
.hash_next
= set
->table
[bucket
];
183 set
->table
[bucket
] = &node
->h
;
185 /* Add node to the set. */
186 ASYNCSAFE(gl_list_node_t
) node
->next
= &set
->root
;
187 node
->prev
= set
->root
.prev
;
188 ASYNCSAFE(gl_list_node_t
) node
->prev
->next
= node
;
189 set
->root
.prev
= node
;
192 hash_resize_after_add (set
);
198 gl_linkedhash_remove (gl_set_t set
, const void *elt
)
201 (set
->hashcode_fn
!= NULL
202 ? set
->hashcode_fn (elt
)
203 : (size_t)(uintptr_t) elt
);
204 size_t bucket
= hashcode
% set
->table_size
;
205 gl_setelement_equals_fn equals
= set
->base
.equals_fn
;
207 /* Look for the first match in the hash bucket. */
208 gl_list_node_t
*nodep
;
210 for (nodep
= (gl_list_node_t
*) &set
->table
[bucket
];
212 nodep
= (gl_list_node_t
*) &(*nodep
)->h
.hash_next
)
214 gl_list_node_t node
= *nodep
;
215 if (node
->h
.hashcode
== hashcode
217 ? equals (elt
, node
->value
)
218 : elt
== node
->value
))
220 /* Remove node from the hash table. */
221 *nodep
= (gl_list_node_t
) node
->h
.hash_next
;
223 /* Remove node from the list. */
225 gl_list_node_t prev
= node
->prev
;
226 gl_list_node_t next
= node
->next
;
228 ASYNCSAFE(gl_list_node_t
) prev
->next
= next
;
233 if (set
->base
.dispose_fn
!= NULL
)
234 set
->base
.dispose_fn (node
->value
);
244 gl_linkedhash_free (gl_set_t set
)
246 gl_setelement_dispose_fn dispose
= set
->base
.dispose_fn
;
249 for (node
= set
->root
.next
; node
!= &set
->root
; )
251 gl_list_node_t next
= node
->next
;
253 dispose (node
->value
);
261 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
263 /* Iterate through the list, not through the hash buckets, so that the order
264 in which the elements are returned is predictable. */
266 static gl_set_iterator_t
267 gl_linkedhash_iterator (gl_set_t set
)
269 gl_set_iterator_t result
;
271 result
.vtable
= set
->base
.vtable
;
273 result
.p
= set
->root
.next
;
274 result
.q
= &set
->root
;
275 #if defined GCC_LINT || defined lint
285 gl_linkedhash_iterator_next (gl_set_iterator_t
*iterator
, const void **eltp
)
287 if (iterator
->p
!= iterator
->q
)
289 gl_list_node_t node
= (gl_list_node_t
) iterator
->p
;
291 iterator
->p
= node
->next
;
299 gl_linkedhash_iterator_free (gl_set_iterator_t
*iterator
)
304 const struct gl_set_implementation gl_linkedhash_set_implementation
=
306 gl_linkedhash_nx_create_empty
,
308 gl_linkedhash_search
,
309 gl_linkedhash_nx_add
,
310 gl_linkedhash_remove
,
312 gl_linkedhash_iterator
,
313 gl_linkedhash_iterator_next
,
314 gl_linkedhash_iterator_free