1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2008, 2009 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* Hash table with separate chaining.
19 This header (hmap.h) supplies an "embedded" implementation of
20 a hash table that uses linked lists to resolve collisions
21 ("separate chaining"). Its companion header (hmapx.h)
22 supplies a "external" implementation that is otherwise
23 similar. The two variants are described briefly here. The
24 embedded variant, for which this is the header, is described
25 in slightly more detail below. Each function also has a
26 detailed usage comment at its point of definition. (Many of
27 those definitions are inline in this file, because they are so
28 simple. Others are in hmap.c.)
30 The "hmap" embedded hash table implementation puts the hash
31 table node (which includes the linked list used for resolving
32 collisions) within the data structure that the hash table
33 contains. This makes allocation efficient, in space and time,
34 because no additional call into an allocator is needed to
35 obtain memory for the hash table node. It also makes it easy
36 to find the hash table node associated with a given object.
37 However, it's difficult to include a given object in an
38 arbitrary number of hash tables.
40 The "hmapx" external hash table implementation allocates hash
41 table nodes separately from the objects in the hash table.
42 Inserting and removing hash table elements requires dynamic
43 allocation, so it is normally slower and takes more memory
44 than the embedded implementation. It also requires searching
45 the table to find the node associated with a given object.
46 However, it's easy to include a given object in an arbitrary
47 number of hash tables. It's also possible to create an
48 external hash table without adding a member to the data
49 structure that the hash table contains. */
51 #ifndef LIBPSPP_HMAP_H
52 #define LIBPSPP_HMAP_H 1
54 /* Embedded hash table with separate chaining.
56 To create an embedded hash table, declare an instance of
57 struct hmap, then initialize it with hmap_init():
61 struct hmap map = HMAP_INITIALIZER (map);
63 Each node in the hash table, presumably a structure type, must
64 include a struct hmap_node member. Here's an example:
67 struct hmap_node node; // hmap_node member.
68 const char *string; // Another member.
70 The hash table functions work with pointers to struct
71 hmap_node. To obtain a pointer to your structure type given a
72 pointer to struct hmap_node, use the HMAP_DATA macro.
74 Inserting and deleting elements is straightforward. Use
75 hmap_insert() to insert an element and hmap_delete() to delete
78 my_foo.string = "My string";
79 hmap_insert (&map, &my_foo.node, hsh_hash_string (my_foo.string));
81 hmap_delete (&map, &my_foo.node);
82 You must pass the element's hash value as one of
83 hmap_insert()'s arguments. The hash table saves this hash
84 value for use later to speed searches and to rehash as the
87 hmap_insert() does not check whether the newly inserted
88 element duplicates an element already in the hash table. The
89 client is responsible for doing so, if this is desirable.
91 The hash table does not provide a direct way to search for an
92 existing element. Instead, it provides the means to iterate
93 over all the elements in the hash table with a given hash
94 value. It is easy to compose a search function from such a
95 building block. For example:
97 find_foo (const struct hmap *map, const char *name)
99 const struct foo *foo;
102 hash = hsh_hash_string (name);
103 HMAP_FOR_EACH_WITH_HASH (foo, struct foo, node, hash, map)
104 if (!strcmp (foo->name, name))
109 Here is how to iterate through the elements currently in the
112 HMAP_FOR_EACH (foo, struct foo, node, &map)
114 ...do something with foo...
120 #include <libpspp/cast.h>
122 /* Returns the data structure corresponding to the given NODE,
123 assuming that NODE is embedded as the given MEMBER name in
124 data type STRUCT. NODE must not be a null pointer. */
125 #define HMAP_DATA(NODE, STRUCT, MEMBER) \
126 (CHECK_POINTER_HAS_TYPE (NODE, struct hmap_node *), \
127 UP_CAST (NODE, STRUCT, MEMBER))
129 /* Like HMAP_DATA, except that a null NODE yields a null pointer
131 #define HMAP_NULLABLE_DATA(NODE, STRUCT, MEMBER) \
132 hmap_nullable_data__ (NODE, offsetof (STRUCT, MEMBER))
134 /* Hash table node. */
137 struct hmap_node *next; /* Next in chain. */
138 size_t hash; /* Hash value. */
141 static inline size_t hmap_node_hash (const struct hmap_node *);
146 size_t count; /* Number of inserted nodes. */
147 size_t mask; /* Number of buckets (power of 2), minus 1. */
148 struct hmap_node **buckets; /* Array of buckets. */
149 struct hmap_node *one; /* One bucket, to eliminate corner cases. */
152 /* Suitable for use as the initializer for a struct hmap named
154 struct hmap map = HMAP_INITIALIZER (map);
155 HMAP_INITIALIZER() is an alternative to hmap_init(). */
156 #define HMAP_INITIALIZER(MAP) { 0, 0, &(MAP).one, NULL }
158 /* Creation and destruction. */
159 void hmap_init (struct hmap *);
160 void hmap_swap (struct hmap *, struct hmap *);
161 void hmap_destroy (struct hmap *);
163 /* Storage management. */
164 void hmap_reserve (struct hmap *, size_t capacity);
165 void hmap_shrink (struct hmap *);
167 /* Search. Refer to the large comment near the top of this file
169 static inline struct hmap_node *hmap_first_with_hash (const struct hmap *,
171 static inline struct hmap_node *hmap_next_with_hash (const struct hmap_node *);
173 /* Insertion and deletion. */
174 static inline void hmap_insert (struct hmap *, struct hmap_node *,
176 static inline void hmap_insert_fast (struct hmap *, struct hmap_node *,
178 static inline void hmap_delete (struct hmap *, struct hmap_node *);
181 static inline struct hmap_node *hmap_first (const struct hmap *);
182 static inline struct hmap_node *hmap_next (const struct hmap *,
183 const struct hmap_node *);
186 static bool hmap_is_empty (const struct hmap *);
187 static inline size_t hmap_count (const struct hmap *);
188 static inline size_t hmap_capacity (const struct hmap *);
190 /* Updating data elements. */
191 void hmap_changed (struct hmap *, struct hmap_node *, size_t new_hash);
192 void hmap_moved (struct hmap *,
193 struct hmap_node *, const struct hmap_node *old);
195 /* Convenience macros for search.
197 These macros automatically use HMAP_DATA to obtain the data
198 elements that encapsulate hmap nodes, which often saves typing
199 and can make code easier to read. Refer to the large comment
200 near the top of this file for an example.
202 These macros evaluate HASH only once. They evaluate their
203 other arguments many times. */
204 #define HMAP_FIRST_WITH_HASH(STRUCT, MEMBER, HMAP, HASH) \
205 HMAP_NULLABLE_DATA (hmap_first_with_hash (HMAP, HASH), STRUCT, MEMBER)
206 #define HMAP_NEXT_WITH_HASH(DATA, STRUCT, MEMBER) \
207 HMAP_NULLABLE_DATA (hmap_next_with_hash (&(DATA)->MEMBER), STRUCT, MEMBER)
208 #define HMAP_FOR_EACH_WITH_HASH(DATA, STRUCT, MEMBER, HASH, HMAP) \
209 for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH); \
211 (DATA) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER))
212 #define HMAP_FOR_EACH_WITH_HASH_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
213 for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH); \
215 ? ((NEXT) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER), 1) \
219 /* Convenience macros for iteration.
221 These macros automatically use HMAP_DATA to obtain the data
222 elements that encapsulate hmap nodes, which often saves typing
223 and can make code easier to read. Refer to the large comment
224 near the top of this file for an example.
226 These macros evaluate their arguments many times. */
227 #define HMAP_FIRST(STRUCT, MEMBER, HMAP) \
228 HMAP_NULLABLE_DATA (hmap_first (HMAP), STRUCT, MEMBER)
229 #define HMAP_NEXT(DATA, STRUCT, MEMBER, HMAP) \
230 HMAP_NULLABLE_DATA (hmap_next (HMAP, &(DATA)->MEMBER), STRUCT, MEMBER)
231 #define HMAP_FOR_EACH(DATA, STRUCT, MEMBER, HMAP) \
232 for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP); \
234 (DATA) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP))
235 #define HMAP_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, HMAP) \
236 for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP); \
238 ? ((NEXT) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP), 1) \
242 /* Inline definitions. */
244 static inline struct hmap_node *hmap_find_hash__ (struct hmap_node *, size_t);
245 static inline struct hmap_node *hmap_first_nonempty_bucket__ (
246 const struct hmap *, size_t start);
247 static inline size_t hmap_mask_to_capacity__ (size_t mask);
249 /* Returns the hash value associated with NODE. */
251 hmap_node_hash (const struct hmap_node *node)
256 /* Returns the first node in MAP that has hash value HASH, or a
257 null pointer if MAP does not contain any node with that hash
260 Assuming uniform hashing and no duplicate data items in MAP,
261 this function runs in constant time. (Amortized over an
262 iteration over all data items with a given HASH, its runtime
263 is proportional to the length of the hash chain for HASH, so
264 given a pathological hash function, e.g. one that returns a
265 constant value, its runtime degenerates to linear in the
266 length of NODE's hash chain.)
268 Nodes are returned in arbitrary order that may change whenever
269 the hash table's current capacity changes, as reported by
270 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
271 hmap_shrink() can change the capacity of a hash map.
272 Inserting a node with hmap_insert_fast() or deleting one with
273 hmap_delete() will not change the relative ordering of nodes.
275 The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
276 macros provide convenient ways to iterate over all the nodes
277 with a given hash. The HMAP_FIRST_WITH_HASH macro is an
278 interface to this particular function that is often more
280 static inline struct hmap_node *
281 hmap_first_with_hash (const struct hmap *map, size_t hash)
283 return hmap_find_hash__ (map->buckets[hash & map->mask], hash);
286 /* Returns the next node in MAP after NODE that has the same hash
287 value as NODE, or a null pointer if MAP does not contain any
288 more nodes with that hash value.
290 Assuming uniform hashing and no duplicate data items in MAP,
291 this function runs in constant time. (Amortized over an
292 iteration over all data items with a given HASH, its runtime
293 is proportional to the length of the hash chain for HASH, so
294 given a pathological hash function, e.g. one that returns a
295 constant value, its runtime degenerates to linear in the
296 length of NODE's hash chain.)
298 Nodes are returned in arbitrary order that may change whenever
299 the hash table's current capacity changes, as reported by
300 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
301 hmap_shrink() can change the capacity of a hash map.
302 Inserting a node with hmap_insert_fast() or deleting one with
303 hmap_delete() will not change the relative ordering of nodes.
305 The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
306 macros provide convenient ways to iterate over all the nodes
307 with a given hash. The HMAP_NEXT_WITH_HASH macro is an
308 interface to this particular function that is often more
310 static inline struct hmap_node *
311 hmap_next_with_hash (const struct hmap_node *node)
313 return hmap_find_hash__ (node->next, node->hash);
316 /* Inserts NODE into MAP with hash value HASH. If the insertion
317 causes MAP's current capacity, as reported by hmap_capacity(),
318 to be exceeded, rehashes MAP with an increased number of hash
321 This function runs in constant time amortized over all the
324 This function does not verify that MAP does not already
325 contain a data item with the same value as NODE. If
326 duplicates should be disallowed (which is the usual case),
327 then the client must check for duplicates itself before
328 inserting the new node. */
330 hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
332 hmap_insert_fast (map, node, hash);
333 if (map->count > hmap_capacity (map))
334 hmap_reserve (map, map->count);
337 /* Inserts NODE into MAP with hash value HASH. Does not check
338 whether this causes MAP's current capacity to be exceeded.
339 The caller must take responsibility for that (or use
340 hmap_insert() instead).
342 This function runs in constant time.
344 This function does not verify that MAP does not already
345 contain a data item with the same value as NODE. If
346 duplicates should be disallowed (which is the usual case),
347 then the client must check for duplicates itself before
348 inserting the new node. */
350 hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
352 struct hmap_node **bucket = &map->buckets[hash & map->mask];
354 node->next = *bucket;
359 /* Removes NODE from MAP. The client is responsible for freeing
360 any data associated with NODE, if necessary.
362 Assuming uniform hashing, this function runs in constant time.
363 (Its runtime is proportional to the position of NODE in its
364 hash chain, so given a pathological hash function, e.g. one
365 that returns a constant value, its runtime degenerates to
366 linear in the length of NODE's hash chain.)
368 This function never reduces the number of buckets in MAP.
369 When one deletes a large number of nodes from a hash table,
370 calling hmap_shrink() afterward may therefore save a small
371 amount of memory. It is also more expensive to iterate
372 through a very sparse hash table than a denser one, so
373 shrinking the hash table could also save some time. However,
374 rehashing has an immediate cost that must be weighed against
377 hmap_delete() does not change NODE's hash value reported by
380 hmap_delete (struct hmap *map, struct hmap_node *node)
382 struct hmap_node **bucket = &map->buckets[node->hash & map->mask];
383 while (*bucket != node)
384 bucket = &(*bucket)->next;
385 *bucket = (*bucket)->next;
389 /* Returns the first node in MAP, or a null pointer if MAP is
392 Amortized over iterating through every data element in MAP,
393 this function runs in constant time. However, this assumes
394 that MAP is not excessively sparse, that is, that
395 hmap_capacity(MAP) is at most a constant factor greater than
396 hmap_count(MAP). This will always be true unless many nodes
397 have been inserted into MAP and then most or all of them
398 deleted; in such a case, calling hmap_shrink() is advised.
400 Nodes are returned in arbitrary order that may change whenever
401 the hash table's current capacity changes, as reported by
402 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
403 hmap_shrink() can change the capacity of a hash map.
404 Inserting a node with hmap_insert_fast() or deleting one with
405 hmap_delete() will not change the relative ordering of nodes.
407 The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
408 convenient ways to iterate over all the nodes in a hash map.
409 The HMAP_FIRST macro is an interface to this particular
410 function that is often more convenient. */
411 static inline struct hmap_node *
412 hmap_first (const struct hmap *map)
414 return hmap_first_nonempty_bucket__ (map, 0);
417 /* Returns the next node in MAP following NODE, or a null pointer
418 if NODE is the last node in MAP.
420 Amortized over iterating through every data element in MAP,
421 this function runs in constant time. However, this assumes
422 that MAP is not excessively sparse, that is, that
423 hmap_capacity(MAP) is at most a constant factor greater than
424 hmap_count(MAP). This will always be true unless many nodes
425 have been inserted into MAP and then most or all of them
426 deleted; in such a case, calling hmap_shrink() is advised.
428 Nodes are returned in arbitrary order that may change whenever
429 the hash table's current capacity changes, as reported by
430 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
431 hmap_shrink() can change the capacity of a hash map.
432 Inserting a node with hmap_insert_fast() or deleting one with
433 hmap_delete() will not change the relative ordering of nodes.
435 The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
436 convenient ways to iterate over all the nodes in a hash map.
437 The HMAP_NEXT macro is an interface to this particular
438 function that is often more convenient. */
439 static inline struct hmap_node *
440 hmap_next (const struct hmap *map, const struct hmap_node *node)
442 return (node->next != NULL
444 : hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
447 /* Returns true if MAP currently contains no data items, false
450 hmap_is_empty (const struct hmap *map)
452 return map->count == 0;
455 /* Returns the number of data items currently in MAP. */
457 hmap_count (const struct hmap *map)
462 /* Returns the current capacity of MAP, that is, the maximum
463 number of data elements that MAP may hold before it becomes
466 The capacity is advisory only: it is possible to insert any
467 number of data elements into a hash map regardless of its
468 capacity. However, inserting many more elements than the
469 map's capacity will degrade search performance. */
471 hmap_capacity (const struct hmap *map)
473 return hmap_mask_to_capacity__ (map->mask);
476 /* Implementation details. */
478 /* Returns the first node at or after NODE in NODE's chain that
479 has hash value HASH. */
480 static inline struct hmap_node *
481 hmap_find_hash__ (struct hmap_node *node, size_t hash)
483 for (; node != NULL; node = node->next)
484 if (node->hash == hash)
489 /* Returns the first node in the lowest-numbered nonempty bucket
490 in MAP whose index is START or higher, or a null pointer if
491 all such buckets are empty. */
492 static inline struct hmap_node *
493 hmap_first_nonempty_bucket__ (const struct hmap *map, size_t start)
497 for (i = start; i <= map->mask; i++)
498 if (map->buckets[i] != NULL)
499 return map->buckets[i];
503 /* Returns the hash table capacity associated with a given MASK,
504 which should be a value for the "mask" member of struct hmap.
505 MASK must be a power of 2 minus 1 (including 0), that is, its
506 value in binary must be all 1-bits. */
508 hmap_mask_to_capacity__ (size_t mask)
510 return (mask + 1) * 2;
513 /* Helper for HMAP_NULLABLE_DATA (to avoid evaluating its NODE
514 argument more than once). */
516 hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
518 return node != NULL ? (char *) node - member_offset : NULL;
521 #endif /* libpspp/hmap.h */