Fix GCC 4.3 warning about uninitialized structure member.
[pspp] / src / libpspp / hmap.h
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2008 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* Hash table with separate chaining.
18
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.)
29
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.
39
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. */
50
51 #ifndef LIBPSPP_HMAP_H
52 #define LIBPSPP_HMAP_H 1
53
54 /* Embedded hash table with separate chaining.
55
56    To create an embedded hash table, declare an instance of
57    struct hmap, then initialize it with hmap_init():
58      struct hmap map;
59      hmap_init (&map);
60    or, alternatively:
61      struct hmap map = HMAP_INITIALIZER (map);
62    
63    Each node in the hash table, presumably a structure type, must
64    include a struct hmap_node member.  Here's an example:
65      struct foo
66        {
67          struct hmap_node node;   // hmap_node member.
68          const char *string;      // Another member.
69        };
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.
73
74    Inserting and deleting elements is straightforward.  Use
75    hmap_insert() to insert an element and hmap_delete() to delete
76    an element, e.g.:
77      struct foo my_foo;
78      my_foo.string = "My string";
79      hmap_insert (&map, &my_foo.node, hsh_hash_string (my_foo.string));
80      ...
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
85    hash table grows.
86
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.
90
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:
96      const struct foo *
97      find_foo (const struct hmap *map, const char *name)
98      {
99        const struct foo *foo;
100        size_t hash;
101
102        hash = hsh_hash_string (name);
103        HMAP_FOR_EACH_WITH_HASH (foo, struct foo, node, hash, map)
104          if (!strcmp (foo->name, name))
105            break;
106        return foo;
107      }
108
109    Here is how to iterate through the elements currently in the
110    hash table:
111      struct foo *foo;
112      HMAP_FOR_EACH (foo, struct foo, node, &map)
113        {
114          ...do something with foo...
115        }
116    */
117
118 #include <stddef.h>
119
120 /* Returns the data structure corresponding to the given NODE,
121    assuming that NODE is embedded as the given MEMBER name in
122    data type STRUCT.  NODE must not be a null pointer. */
123 #define HMAP_DATA(NODE, STRUCT, MEMBER)                         \
124   ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
125
126 /* Like HMAP_DATA, except that a null NODE yields a null pointer
127    result. */
128 #define HMAP_NULLABLE_DATA(NODE, STRUCT, MEMBER)        \
129   hmap_nullable_data__ (NODE, offsetof (STRUCT, MEMBER))
130
131 /* Hash table node. */
132 struct hmap_node
133   {
134     struct hmap_node *next;     /* Next in chain. */
135     size_t hash;                /* Hash value. */
136   };
137
138 static inline size_t hmap_node_hash (const struct hmap_node *);
139
140 /* Hash table. */
141 struct hmap
142   {
143     size_t count;               /* Number of inserted nodes. */
144     size_t mask;                /* Number of buckets (power of 2), minus 1. */
145     struct hmap_node **buckets; /* Array of buckets. */
146     struct hmap_node *one;      /* One bucket, to eliminate corner cases. */
147   };
148
149 /* Suitable for use as the initializer for a struct hmap named
150    MAP.  Typical usage:
151        struct hmap map = HMAP_INITIALIZER (map);
152    HMAP_INITIALIZER() is an alternative to hmap_init(). */
153 #define HMAP_INITIALIZER(MAP) { 0, 0, &(MAP).one, NULL }
154
155 /* Creation and destruction. */
156 void hmap_init (struct hmap *);
157 void hmap_swap (struct hmap *, struct hmap *);
158 void hmap_destroy (struct hmap *);
159
160 /* Storage management. */
161 void hmap_reserve (struct hmap *, size_t capacity);
162 void hmap_shrink (struct hmap *);
163
164 /* Search.  Refer to the large comment near the top of this file
165    for an example.*/
166 static inline struct hmap_node *hmap_first_with_hash (const struct hmap *,
167                                                       size_t hash);
168 static inline struct hmap_node *hmap_next_with_hash (const struct hmap_node *);
169
170 /* Insertion and deletion. */
171 static inline void hmap_insert (struct hmap *, struct hmap_node *,
172                                 size_t hash);
173 static inline void hmap_insert_fast (struct hmap *, struct hmap_node *,
174                                      size_t hash);
175 static inline void hmap_delete (struct hmap *, struct hmap_node *);
176
177 /* Iteration. */
178 static inline struct hmap_node *hmap_first (const struct hmap *);
179 static inline struct hmap_node *hmap_next (const struct hmap *,
180                                            const struct hmap_node *);
181
182 /* Counting. */
183 static inline size_t hmap_count (const struct hmap *);
184 static inline size_t hmap_capacity (const struct hmap *);
185
186 /* Updating data elements. */
187 void hmap_changed (struct hmap *, struct hmap_node *, size_t new_hash);
188 void hmap_moved (struct hmap *,
189                  struct hmap_node *, const struct hmap_node *old);
190
191 /* Convenience macros for search.
192
193    These macros automatically use HMAP_DATA to obtain the data
194    elements that encapsulate hmap nodes, which often saves typing
195    and can make code easier to read.  Refer to the large comment
196    near the top of this file for an example.
197
198    These macros evaluate HASH only once.  They evaluate their
199    other arguments many times. */
200 #define HMAP_FIRST_WITH_HASH(STRUCT, MEMBER, HMAP, HASH)                \
201   HMAP_NULLABLE_DATA (hmap_first_with_hash (HMAP, HASH), STRUCT, MEMBER)
202 #define HMAP_NEXT_WITH_HASH(DATA, STRUCT, MEMBER)                       \
203   HMAP_NULLABLE_DATA (hmap_next_with_hash (&(DATA)->MEMBER), STRUCT, MEMBER)
204 #define HMAP_FOR_EACH_WITH_HASH(DATA, STRUCT, MEMBER, HASH, HMAP)       \
205   for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH);      \
206        (DATA) != NULL;                                                  \
207        (DATA) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER))
208 #define HMAP_FOR_EACH_WITH_HASH_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
209   for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH);      \
210        ((DATA) != NULL                                                  \
211         ? ((NEXT) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER), 1)      \
212         : 0);                                                           \
213        (DATA) = (NEXT))
214
215 /* Convenience macros for iteration.
216
217    These macros automatically use HMAP_DATA to obtain the data
218    elements that encapsulate hmap nodes, which often saves typing
219    and can make code easier to read.  Refer to the large comment
220    near the top of this file for an example.
221
222    These macros evaluate their arguments many times. */
223 #define HMAP_FIRST(STRUCT, MEMBER, HMAP)                        \
224   HMAP_NULLABLE_DATA (hmap_first (HMAP), STRUCT, MEMBER)
225 #define HMAP_NEXT(DATA, STRUCT, MEMBER, HMAP)                           \
226   HMAP_NULLABLE_DATA (hmap_next (HMAP, &(DATA)->MEMBER), STRUCT, MEMBER)
227 #define HMAP_FOR_EACH(DATA, STRUCT, MEMBER, HMAP)       \
228   for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP);      \
229        (DATA) != NULL;                                  \
230        (DATA) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP))
231 #define HMAP_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, HMAP)    \
232   for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP);              \
233        ((DATA) != NULL                                          \
234         ? ((NEXT) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP), 1)  \
235         : 0);                                                   \
236        (DATA) = (NEXT))
237 \f
238 /* Inline definitions. */
239
240 static inline struct hmap_node *hmap_find_hash__ (struct hmap_node *, size_t);
241 static inline struct hmap_node *hmap_first_nonempty_bucket__ (
242   const struct hmap *, size_t start);
243 static inline size_t hmap_mask_to_capacity__ (size_t mask);
244
245 /* Returns the hash value associated with NODE. */
246 size_t
247 hmap_node_hash (const struct hmap_node *node) 
248 {
249   return node->hash;
250 }
251
252 /* Returns the first node in MAP that has hash value HASH, or a
253    null pointer if MAP does not contain any node with that hash
254    value.
255
256    Assuming uniform hashing and no duplicate data items in MAP,
257    this function runs in constant time.  (Amortized over an
258    iteration over all data items with a given HASH, its runtime
259    is proportional to the length of the hash chain for HASH, so
260    given a pathological hash function, e.g. one that returns a
261    constant value, its runtime degenerates to linear in the
262    length of NODE's hash chain.)
263
264    Nodes are returned in arbitrary order that may change whenever
265    the hash table's current capacity changes, as reported by
266    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
267    hmap_shrink() can change the capacity of a hash map.
268    Inserting a node with hmap_insert_fast() or deleting one with
269    hmap_delete() will not change the relative ordering of nodes.
270
271    The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
272    macros provide convenient ways to iterate over all the nodes
273    with a given hash.  The HMAP_FIRST_WITH_HASH macro is an
274    interface to this particular function that is often more
275    convenient. */
276 static inline struct hmap_node *
277 hmap_first_with_hash (const struct hmap *map, size_t hash)
278 {
279   return hmap_find_hash__ (map->buckets[hash & map->mask], hash);
280 }
281
282 /* Returns the next node in MAP after NODE that has the same hash
283    value as NODE, or a null pointer if MAP does not contain any
284    more nodes with that hash value.
285
286    Assuming uniform hashing and no duplicate data items in MAP,
287    this function runs in constant time.  (Amortized over an
288    iteration over all data items with a given HASH, its runtime
289    is proportional to the length of the hash chain for HASH, so
290    given a pathological hash function, e.g. one that returns a
291    constant value, its runtime degenerates to linear in the
292    length of NODE's hash chain.)
293
294    Nodes are returned in arbitrary order that may change whenever
295    the hash table's current capacity changes, as reported by
296    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
297    hmap_shrink() can change the capacity of a hash map.
298    Inserting a node with hmap_insert_fast() or deleting one with
299    hmap_delete() will not change the relative ordering of nodes.
300
301    The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
302    macros provide convenient ways to iterate over all the nodes
303    with a given hash.  The HMAP_NEXT_WITH_HASH macro is an
304    interface to this particular function that is often more
305    convenient. */
306 static inline struct hmap_node *
307 hmap_next_with_hash (const struct hmap_node *node) 
308 {
309   return hmap_find_hash__ (node->next, node->hash);
310 }
311
312 /* Inserts NODE into MAP with hash value HASH.  If the insertion
313    causes MAP's current capacity, as reported by hmap_capacity(),
314    to be exceeded, rehashes MAP with an increased number of hash
315    buckets.
316
317    This function runs in constant time amortized over all the
318    insertions into MAP.
319
320    This function does not verify that MAP does not already
321    contain a data item with the same value as NODE.  If
322    duplicates should be disallowed (which is the usual case),
323    then the client must check for duplicates itself before
324    inserting the new node. */
325 static inline void
326 hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
327 {
328   hmap_insert_fast (map, node, hash);
329   if (map->count > hmap_capacity (map))
330     hmap_reserve (map, map->count);
331 }
332
333 /* Inserts NODE into MAP with hash value HASH.  Does not check
334    whether this causes MAP's current capacity to be exceeded.
335    The caller must take responsibility for that (or use
336    hmap_insert() instead).
337
338    This function runs in constant time.
339
340    This function does not verify that MAP does not already
341    contain a data item with the same value as NODE.  If
342    duplicates should be disallowed (which is the usual case),
343    then the client must check for duplicates itself before
344    inserting the new node. */
345 static inline void
346 hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash) 
347 {
348   struct hmap_node **bucket = &map->buckets[hash & map->mask];
349   node->hash = hash;
350   node->next = *bucket;
351   *bucket = node;
352   map->count++;
353 }
354
355 /* Removes NODE from MAP.  The client is responsible for freeing
356    any data associated with NODE, if necessary.
357
358    Assuming uniform hashing, this function runs in constant time.
359    (Its runtime is proportional to the position of NODE in its
360    hash chain, so given a pathological hash function, e.g. one
361    that returns a constant value, its runtime degenerates to
362    linear in the length of NODE's hash chain.)
363
364    This function never reduces the number of buckets in MAP.
365    When one deletes a large number of nodes from a hash table,
366    calling hmap_shrink() afterward may therefore save a small
367    amount of memory.  It is also more expensive to iterate
368    through a very sparse hash table than a denser one, so
369    shrinking the hash table could also save some time.  However,
370    rehashing has an immediate cost that must be weighed against
371    these benefits.
372
373    hmap_delete() does not change NODE's hash value reported by
374    hmap_node_hash(). */
375 static inline void
376 hmap_delete (struct hmap *map, struct hmap_node *node)
377 {
378   struct hmap_node **bucket = &map->buckets[node->hash & map->mask];
379   while (*bucket != node)
380     bucket = &(*bucket)->next;
381   *bucket = (*bucket)->next;
382   map->count--;
383 }
384
385 /* Returns the first node in MAP, or a null pointer if MAP is
386    empty.
387
388    Amortized over iterating through every data element in MAP,
389    this function runs in constant time.  However, this assumes
390    that MAP is not excessively sparse, that is, that
391    hmap_capacity(MAP) is at most a constant factor greater than
392    hmap_count(MAP).  This will always be true unless many nodes
393    have been inserted into MAP and then most or all of them
394    deleted; in such a case, calling hmap_shrink() is advised.
395
396    Nodes are returned in arbitrary order that may change whenever
397    the hash table's current capacity changes, as reported by
398    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
399    hmap_shrink() can change the capacity of a hash map.
400    Inserting a node with hmap_insert_fast() or deleting one with
401    hmap_delete() will not change the relative ordering of nodes.
402
403    The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
404    convenient ways to iterate over all the nodes in a hash map.
405    The HMAP_FIRST macro is an interface to this particular
406    function that is often more convenient. */
407 static inline struct hmap_node *
408 hmap_first (const struct hmap *map) 
409 {
410   return hmap_first_nonempty_bucket__ (map, 0);
411 }
412
413 /* Returns the next node in MAP following NODE, or a null pointer
414    if NODE is the last node in MAP.
415
416    Amortized over iterating through every data element in MAP,
417    this function runs in constant time.  However, this assumes
418    that MAP is not excessively sparse, that is, that
419    hmap_capacity(MAP) is at most a constant factor greater than
420    hmap_count(MAP).  This will always be true unless many nodes
421    have been inserted into MAP and then most or all of them
422    deleted; in such a case, calling hmap_shrink() is advised.
423
424    Nodes are returned in arbitrary order that may change whenever
425    the hash table's current capacity changes, as reported by
426    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
427    hmap_shrink() can change the capacity of a hash map.
428    Inserting a node with hmap_insert_fast() or deleting one with
429    hmap_delete() will not change the relative ordering of nodes.
430
431    The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
432    convenient ways to iterate over all the nodes in a hash map.
433    The HMAP_NEXT macro is an interface to this particular
434    function that is often more convenient. */
435 static inline struct hmap_node *
436 hmap_next (const struct hmap *map, const struct hmap_node *node) 
437 {
438   return (node->next != NULL
439           ? node->next
440           : hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
441 }
442
443 /* Returns the number of data items currently in MAP. */
444 static inline size_t
445 hmap_count (const struct hmap *map) 
446 {
447   return map->count;
448 }
449
450 /* Returns the current capacity of MAP, that is, the maximum
451    number of data elements that MAP may hold before it becomes
452    advisable to rehash.
453
454    The capacity is advisory only: it is possible to insert any
455    number of data elements into a hash map regardless of its
456    capacity.  However, inserting many more elements than the
457    map's capacity will degrade search performance. */
458 static inline size_t
459 hmap_capacity (const struct hmap *map) 
460 {
461   return hmap_mask_to_capacity__ (map->mask);
462 }
463 \f
464 /* Implementation details. */
465
466 /* Returns the first node at or after NODE in NODE's chain that
467    has hash value HASH. */
468 static inline struct hmap_node *
469 hmap_find_hash__ (struct hmap_node *node, size_t hash) 
470 {
471   for (; node != NULL; node = node->next) 
472     if (node->hash == hash)
473       break;
474   return node;
475 }
476
477 /* Returns the first node in the lowest-numbered nonempty bucket
478    in MAP whose index is START or higher, or a null pointer if
479    all such buckets are empty. */
480 static inline struct hmap_node *
481 hmap_first_nonempty_bucket__ (const struct hmap *map, size_t start)
482 {
483   size_t i;
484
485   for (i = start; i <= map->mask; i++)
486     if (map->buckets[i] != NULL)
487       return map->buckets[i];
488   return NULL;
489 }
490
491 /* Returns the hash table capacity associated with a given MASK,
492    which should be a value for the "mask" member of struct hmap.
493    MASK must be a power of 2 minus 1 (including 0), that is, its
494    value in binary must be all 1-bits.  */
495 static inline size_t
496 hmap_mask_to_capacity__ (size_t mask) 
497 {
498   return (mask + 1) * 2;
499 }
500
501 /* Helper for HMAP_NULLABLE_DATA (to avoid evaluating its NODE
502    argument more than once).  */
503 static inline void *
504 hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
505
506   return node != NULL ? (char *) node - member_offset : NULL;
507 }
508
509 #endif /* libpspp/hmap.h */