src/libpspp/hmap.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2008, 2009 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 #include <libpspp/cast.h>
 120
 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))
 127
 128 /* Like HMAP_DATA, except that a null NODE yields a null pointer
 129    result. */
 130 #define HMAP_NULLABLE_DATA(NODE, STRUCT, MEMBER)        \
 131   hmap_nullable_data__ (NODE, offsetof (STRUCT, MEMBER))
 132
 133 /* Hash table node. */
 134 struct hmap_node
 135   {
 136     struct hmap_node *next;     /* Next in chain. */
 137     size_t hash;                /* Hash value. */
 138   };
 139
 140 static inline size_t hmap_node_hash (const struct hmap_node *);
 141
 142 /* Hash table. */
 143 struct hmap
 144   {
 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. */
 149   };
 150
 151 /* Suitable for use as the initializer for a struct hmap named
 152    MAP.  Typical usage:
 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 }
 156
 157 /* Creation and destruction. */
 158 void hmap_init (struct hmap *);
 159 void hmap_swap (struct hmap *, struct hmap *);
 160 void hmap_destroy (struct hmap *);
 161
 162 /* Storage management. */
 163 void hmap_reserve (struct hmap *, size_t capacity);
 164 void hmap_shrink (struct hmap *);
 165
 166 /* Search.  Refer to the large comment near the top of this file
 167    for an example.*/
 168 static inline struct hmap_node *hmap_first_with_hash (const struct hmap *,
 169                                                       size_t hash);
 170 static inline struct hmap_node *hmap_next_with_hash (const struct hmap_node *);
 171
 172 /* Insertion and deletion. */
 173 static inline void hmap_insert (struct hmap *, struct hmap_node *,
 174                                 size_t hash);
 175 static inline void hmap_insert_fast (struct hmap *, struct hmap_node *,
 176                                      size_t hash);
 177 static inline void hmap_delete (struct hmap *, struct hmap_node *);
 178
 179 /* Iteration. */
 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 *);
 183
 184 /* Counting. */
 185 static inline size_t hmap_count (const struct hmap *);
 186 static inline size_t hmap_capacity (const struct hmap *);
 187
 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);
 192
 193 /* Convenience macros for search.
 194
 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.
 199
 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);      \
 208        (DATA) != NULL;                                                  \
 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);      \
 212        ((DATA) != NULL                                                  \
 213         ? ((NEXT) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER), 1)      \
 214         : 0);                                                           \
 215        (DATA) = (NEXT))
 216
 217 /* Convenience macros for iteration.
 218
 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.
 223
 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);      \
 231        (DATA) != NULL;                                  \
 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);              \
 235        ((DATA) != NULL                                          \
 236         ? ((NEXT) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP), 1)  \
 237         : 0);                                                   \
 238        (DATA) = (NEXT))
 239 \f
 240 /* Inline definitions. */
 241
 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);
 246
 247 /* Returns the hash value associated with NODE. */
 248 size_t
 249 hmap_node_hash (const struct hmap_node *node)
 250 {
 251   return node->hash;
 252 }
 253
 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
 256    value.
 257
 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.)
 265
 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.
 272
 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
 277    convenient. */
 278 static inline struct hmap_node *
 279 hmap_first_with_hash (const struct hmap *map, size_t hash)
 280 {
 281   return hmap_find_hash__ (map->buckets[hash & map->mask], hash);
 282 }
 283
 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.
 287
 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.)
 295
 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.
 302
 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
 307    convenient. */
 308 static inline struct hmap_node *
 309 hmap_next_with_hash (const struct hmap_node *node)
 310 {
 311   return hmap_find_hash__ (node->next, node->hash);
 312 }
 313
 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
 317    buckets.
 318
 319    This function runs in constant time amortized over all the
 320    insertions into MAP.
 321
 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. */
 327 static inline void
 328 hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
 329 {
 330   hmap_insert_fast (map, node, hash);
 331   if (map->count > hmap_capacity (map))
 332     hmap_reserve (map, map->count);
 333 }
 334
 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).
 339
 340    This function runs in constant time.
 341
 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. */
 347 static inline void
 348 hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
 349 {
 350   struct hmap_node **bucket = &map->buckets[hash & map->mask];
 351   node->hash = hash;
 352   node->next = *bucket;
 353   *bucket = node;
 354   map->count++;
 355 }
 356
 357 /* Removes NODE from MAP.  The client is responsible for freeing
 358    any data associated with NODE, if necessary.
 359
 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.)
 365
 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
 373    these benefits.
 374
 375    hmap_delete() does not change NODE's hash value reported by
 376    hmap_node_hash(). */
 377 static inline void
 378 hmap_delete (struct hmap *map, struct hmap_node *node)
 379 {
 380   struct hmap_node **bucket = &map->buckets[node->hash & map->mask];
 381   while (*bucket != node)
 382     bucket = &(*bucket)->next;
 383   *bucket = (*bucket)->next;
 384   map->count--;
 385 }
 386
 387 /* Returns the first node in MAP, or a null pointer if MAP is
 388    empty.
 389
 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.
 397
 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.
 404
 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)
 411 {
 412   return hmap_first_nonempty_bucket__ (map, 0);
 413 }
 414
 415 /* Returns the next node in MAP following NODE, or a null pointer
 416    if NODE is the last node in MAP.
 417
 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.
 425
 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.
 432
 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)
 439 {
 440   return (node->next != NULL
 441           ? node->next
 442           : hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
 443 }
 444
 445 /* Returns the number of data items currently in MAP. */
 446 static inline size_t
 447 hmap_count (const struct hmap *map)
 448 {
 449   return map->count;
 450 }
 451
 452 /* Returns the current capacity of MAP, that is, the maximum
 453    number of data elements that MAP may hold before it becomes
 454    advisable to rehash.
 455
 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. */
 460 static inline size_t
 461 hmap_capacity (const struct hmap *map)
 462 {
 463   return hmap_mask_to_capacity__ (map->mask);
 464 }
 465 \f
 466 /* Implementation details. */
 467
 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)
 472 {
 473   for (; node != NULL; node = node->next)
 474     if (node->hash == hash)
 475       break;
 476   return node;
 477 }
 478
 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)
 484 {
 485   size_t i;
 486
 487   for (i = start; i <= map->mask; i++)
 488     if (map->buckets[i] != NULL)
 489       return map->buckets[i];
 490   return NULL;
 491 }
 492
 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.  */
 497 static inline size_t
 498 hmap_mask_to_capacity__ (size_t mask)
 499 {
 500   return (mask + 1) * 2;
 501 }
 502
 503 /* Helper for HMAP_NULLABLE_DATA (to avoid evaluating its NODE
 504    argument more than once).  */
 505 static inline void *
 506 hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
 507 {
 508   return node != NULL ? (char *) node - member_offset : NULL;
 509 }
 510
 511 #endif /* libpspp/hmap.h */