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...
119 #include <libpspp/cast.h>
121 /* Returns the data structure corresponding to the given NODE,
122 assuming that NODE is embedded as the given MEMBER name in
123 data type STRUCT. NODE must not be a null pointer. */
124 #define HMAP_DATA(NODE, STRUCT, MEMBER) \
125 (CHECK_POINTER_HAS_TYPE (NODE, struct hmap_node *), \
126 UP_CAST (NODE, STRUCT, MEMBER))
128 /* Like HMAP_DATA, except that a null NODE yields a null pointer
130 #define HMAP_NULLABLE_DATA(NODE, STRUCT, MEMBER) \
131 hmap_nullable_data__ (NODE, offsetof (STRUCT, MEMBER))
133 /* Hash table node. */
136 struct hmap_node *next; /* Next in chain. */
137 size_t hash; /* Hash value. */
140 static inline size_t hmap_node_hash (const struct hmap_node *);
145 size_t count; /* Number of inserted nodes. */
146 size_t mask; /* Number of buckets (power of 2), minus 1. */
147 struct hmap_node **buckets; /* Array of buckets. */
148 struct hmap_node *one; /* One bucket, to eliminate corner cases. */
151 /* Suitable for use as the initializer for a struct hmap named
153 struct hmap map = HMAP_INITIALIZER (map);
154 HMAP_INITIALIZER() is an alternative to hmap_init(). */
155 #define HMAP_INITIALIZER(MAP) { 0, 0, &(MAP).one, NULL }
157 /* Creation and destruction. */
158 void hmap_init (struct hmap *);
159 void hmap_swap (struct hmap *, struct hmap *);
160 void hmap_destroy (struct hmap *);
162 /* Storage management. */
163 void hmap_reserve (struct hmap *, size_t capacity);
164 void hmap_shrink (struct hmap *);
166 /* Search. Refer to the large comment near the top of this file
168 static inline struct hmap_node *hmap_first_with_hash (const struct hmap *,
170 static inline struct hmap_node *hmap_next_with_hash (const struct hmap_node *);
172 /* Insertion and deletion. */
173 static inline void hmap_insert (struct hmap *, struct hmap_node *,
175 static inline void hmap_insert_fast (struct hmap *, struct hmap_node *,
177 static inline void hmap_delete (struct hmap *, struct hmap_node *);
180 static inline struct hmap_node *hmap_first (const struct hmap *);
181 static inline struct hmap_node *hmap_next (const struct hmap *,
182 const struct hmap_node *);
185 static inline size_t hmap_count (const struct hmap *);
186 static inline size_t hmap_capacity (const struct hmap *);
188 /* Updating data elements. */
189 void hmap_changed (struct hmap *, struct hmap_node *, size_t new_hash);
190 void hmap_moved (struct hmap *,
191 struct hmap_node *, const struct hmap_node *old);
193 /* Convenience macros for search.
195 These macros automatically use HMAP_DATA to obtain the data
196 elements that encapsulate hmap nodes, which often saves typing
197 and can make code easier to read. Refer to the large comment
198 near the top of this file for an example.
200 These macros evaluate HASH only once. They evaluate their
201 other arguments many times. */
202 #define HMAP_FIRST_WITH_HASH(STRUCT, MEMBER, HMAP, HASH) \
203 HMAP_NULLABLE_DATA (hmap_first_with_hash (HMAP, HASH), STRUCT, MEMBER)
204 #define HMAP_NEXT_WITH_HASH(DATA, STRUCT, MEMBER) \
205 HMAP_NULLABLE_DATA (hmap_next_with_hash (&(DATA)->MEMBER), STRUCT, MEMBER)
206 #define HMAP_FOR_EACH_WITH_HASH(DATA, STRUCT, MEMBER, HASH, HMAP) \
207 for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH); \
209 (DATA) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER))
210 #define HMAP_FOR_EACH_WITH_HASH_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
211 for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH); \
213 ? ((NEXT) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER), 1) \
217 /* Convenience macros for iteration.
219 These macros automatically use HMAP_DATA to obtain the data
220 elements that encapsulate hmap nodes, which often saves typing
221 and can make code easier to read. Refer to the large comment
222 near the top of this file for an example.
224 These macros evaluate their arguments many times. */
225 #define HMAP_FIRST(STRUCT, MEMBER, HMAP) \
226 HMAP_NULLABLE_DATA (hmap_first (HMAP), STRUCT, MEMBER)
227 #define HMAP_NEXT(DATA, STRUCT, MEMBER, HMAP) \
228 HMAP_NULLABLE_DATA (hmap_next (HMAP, &(DATA)->MEMBER), STRUCT, MEMBER)
229 #define HMAP_FOR_EACH(DATA, STRUCT, MEMBER, HMAP) \
230 for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP); \
232 (DATA) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP))
233 #define HMAP_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, HMAP) \
234 for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP); \
236 ? ((NEXT) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP), 1) \
240 /* Inline definitions. */
242 static inline struct hmap_node *hmap_find_hash__ (struct hmap_node *, size_t);
243 static inline struct hmap_node *hmap_first_nonempty_bucket__ (
244 const struct hmap *, size_t start);
245 static inline size_t hmap_mask_to_capacity__ (size_t mask);
247 /* Returns the hash value associated with NODE. */
249 hmap_node_hash (const struct hmap_node *node)
254 /* Returns the first node in MAP that has hash value HASH, or a
255 null pointer if MAP does not contain any node with that hash
258 Assuming uniform hashing and no duplicate data items in MAP,
259 this function runs in constant time. (Amortized over an
260 iteration over all data items with a given HASH, its runtime
261 is proportional to the length of the hash chain for HASH, so
262 given a pathological hash function, e.g. one that returns a
263 constant value, its runtime degenerates to linear in the
264 length of NODE's hash chain.)
266 Nodes are returned in arbitrary order that may change whenever
267 the hash table's current capacity changes, as reported by
268 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
269 hmap_shrink() can change the capacity of a hash map.
270 Inserting a node with hmap_insert_fast() or deleting one with
271 hmap_delete() will not change the relative ordering of nodes.
273 The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
274 macros provide convenient ways to iterate over all the nodes
275 with a given hash. The HMAP_FIRST_WITH_HASH macro is an
276 interface to this particular function that is often more
278 static inline struct hmap_node *
279 hmap_first_with_hash (const struct hmap *map, size_t hash)
281 return hmap_find_hash__ (map->buckets[hash & map->mask], hash);
284 /* Returns the next node in MAP after NODE that has the same hash
285 value as NODE, or a null pointer if MAP does not contain any
286 more nodes with that hash value.
288 Assuming uniform hashing and no duplicate data items in MAP,
289 this function runs in constant time. (Amortized over an
290 iteration over all data items with a given HASH, its runtime
291 is proportional to the length of the hash chain for HASH, so
292 given a pathological hash function, e.g. one that returns a
293 constant value, its runtime degenerates to linear in the
294 length of NODE's hash chain.)
296 Nodes are returned in arbitrary order that may change whenever
297 the hash table's current capacity changes, as reported by
298 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
299 hmap_shrink() can change the capacity of a hash map.
300 Inserting a node with hmap_insert_fast() or deleting one with
301 hmap_delete() will not change the relative ordering of nodes.
303 The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
304 macros provide convenient ways to iterate over all the nodes
305 with a given hash. The HMAP_NEXT_WITH_HASH macro is an
306 interface to this particular function that is often more
308 static inline struct hmap_node *
309 hmap_next_with_hash (const struct hmap_node *node)
311 return hmap_find_hash__ (node->next, node->hash);
314 /* Inserts NODE into MAP with hash value HASH. If the insertion
315 causes MAP's current capacity, as reported by hmap_capacity(),
316 to be exceeded, rehashes MAP with an increased number of hash
319 This function runs in constant time amortized over all the
322 This function does not verify that MAP does not already
323 contain a data item with the same value as NODE. If
324 duplicates should be disallowed (which is the usual case),
325 then the client must check for duplicates itself before
326 inserting the new node. */
328 hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
330 hmap_insert_fast (map, node, hash);
331 if (map->count > hmap_capacity (map))
332 hmap_reserve (map, map->count);
335 /* Inserts NODE into MAP with hash value HASH. Does not check
336 whether this causes MAP's current capacity to be exceeded.
337 The caller must take responsibility for that (or use
338 hmap_insert() instead).
340 This function runs in constant time.
342 This function does not verify that MAP does not already
343 contain a data item with the same value as NODE. If
344 duplicates should be disallowed (which is the usual case),
345 then the client must check for duplicates itself before
346 inserting the new node. */
348 hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
350 struct hmap_node **bucket = &map->buckets[hash & map->mask];
352 node->next = *bucket;
357 /* Removes NODE from MAP. The client is responsible for freeing
358 any data associated with NODE, if necessary.
360 Assuming uniform hashing, this function runs in constant time.
361 (Its runtime is proportional to the position of NODE in its
362 hash chain, so given a pathological hash function, e.g. one
363 that returns a constant value, its runtime degenerates to
364 linear in the length of NODE's hash chain.)
366 This function never reduces the number of buckets in MAP.
367 When one deletes a large number of nodes from a hash table,
368 calling hmap_shrink() afterward may therefore save a small
369 amount of memory. It is also more expensive to iterate
370 through a very sparse hash table than a denser one, so
371 shrinking the hash table could also save some time. However,
372 rehashing has an immediate cost that must be weighed against
375 hmap_delete() does not change NODE's hash value reported by
378 hmap_delete (struct hmap *map, struct hmap_node *node)
380 struct hmap_node **bucket = &map->buckets[node->hash & map->mask];
381 while (*bucket != node)
382 bucket = &(*bucket)->next;
383 *bucket = (*bucket)->next;
387 /* Returns the first node in MAP, or a null pointer if MAP is
390 Amortized over iterating through every data element in MAP,
391 this function runs in constant time. However, this assumes
392 that MAP is not excessively sparse, that is, that
393 hmap_capacity(MAP) is at most a constant factor greater than
394 hmap_count(MAP). This will always be true unless many nodes
395 have been inserted into MAP and then most or all of them
396 deleted; in such a case, calling hmap_shrink() is advised.
398 Nodes are returned in arbitrary order that may change whenever
399 the hash table's current capacity changes, as reported by
400 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
401 hmap_shrink() can change the capacity of a hash map.
402 Inserting a node with hmap_insert_fast() or deleting one with
403 hmap_delete() will not change the relative ordering of nodes.
405 The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
406 convenient ways to iterate over all the nodes in a hash map.
407 The HMAP_FIRST macro is an interface to this particular
408 function that is often more convenient. */
409 static inline struct hmap_node *
410 hmap_first (const struct hmap *map)
412 return hmap_first_nonempty_bucket__ (map, 0);
415 /* Returns the next node in MAP following NODE, or a null pointer
416 if NODE is the last node in MAP.
418 Amortized over iterating through every data element in MAP,
419 this function runs in constant time. However, this assumes
420 that MAP is not excessively sparse, that is, that
421 hmap_capacity(MAP) is at most a constant factor greater than
422 hmap_count(MAP). This will always be true unless many nodes
423 have been inserted into MAP and then most or all of them
424 deleted; in such a case, calling hmap_shrink() is advised.
426 Nodes are returned in arbitrary order that may change whenever
427 the hash table's current capacity changes, as reported by
428 hmap_capacity(). Calls to hmap_insert(), hmap_reserve(), and
429 hmap_shrink() can change the capacity of a hash map.
430 Inserting a node with hmap_insert_fast() or deleting one with
431 hmap_delete() will not change the relative ordering of nodes.
433 The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
434 convenient ways to iterate over all the nodes in a hash map.
435 The HMAP_NEXT macro is an interface to this particular
436 function that is often more convenient. */
437 static inline struct hmap_node *
438 hmap_next (const struct hmap *map, const struct hmap_node *node)
440 return (node->next != NULL
442 : hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
445 /* Returns the number of data items currently in MAP. */
447 hmap_count (const struct hmap *map)
452 /* Returns the current capacity of MAP, that is, the maximum
453 number of data elements that MAP may hold before it becomes
456 The capacity is advisory only: it is possible to insert any
457 number of data elements into a hash map regardless of its
458 capacity. However, inserting many more elements than the
459 map's capacity will degrade search performance. */
461 hmap_capacity (const struct hmap *map)
463 return hmap_mask_to_capacity__ (map->mask);
466 /* Implementation details. */
468 /* Returns the first node at or after NODE in NODE's chain that
469 has hash value HASH. */
470 static inline struct hmap_node *
471 hmap_find_hash__ (struct hmap_node *node, size_t hash)
473 for (; node != NULL; node = node->next)
474 if (node->hash == hash)
479 /* Returns the first node in the lowest-numbered nonempty bucket
480 in MAP whose index is START or higher, or a null pointer if
481 all such buckets are empty. */
482 static inline struct hmap_node *
483 hmap_first_nonempty_bucket__ (const struct hmap *map, size_t start)
487 for (i = start; i <= map->mask; i++)
488 if (map->buckets[i] != NULL)
489 return map->buckets[i];
493 /* Returns the hash table capacity associated with a given MASK,
494 which should be a value for the "mask" member of struct hmap.
495 MASK must be a power of 2 minus 1 (including 0), that is, its
496 value in binary must be all 1-bits. */
498 hmap_mask_to_capacity__ (size_t mask)
500 return (mask + 1) * 2;
503 /* Helper for HMAP_NULLABLE_DATA (to avoid evaluating its NODE
504 argument more than once). */
506 hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
508 return node != NULL ? (char *) node - member_offset : NULL;
511 #endif /* libpspp/hmap.h */