pintos-os.org Git - pspp/blob - src/libpspp/hmap.h

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2008, 2009, 2010, 2011, 2012 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 <stdbool.h>
 119 #include <stddef.h>
 120 #include "libpspp/cast.h"
 121
 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))
 128
 129 /* Like HMAP_DATA, except that a null NODE yields a null pointer
 130    result. */
 131 #define HMAP_NULLABLE_DATA(NODE, STRUCT, MEMBER)        \
 132   hmap_nullable_data__ (NODE, offsetof (STRUCT, MEMBER))
 133
 134 /* Hash table node. */
 135 struct hmap_node
 136   {
 137     struct hmap_node *next;     /* Next in chain. */
 138     size_t hash;                /* Hash value. */
 139   };
 140
 141 static inline size_t hmap_node_hash (const struct hmap_node *);
 142
 143 /* Hash table. */
 144 struct hmap
 145   {
 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. */
 150   };
 151
 152 /* Suitable for use as the initializer for a struct hmap named
 153    MAP.  Typical usage:
 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 }
 157
 158 /* Creation and destruction. */
 159 void hmap_init (struct hmap *);
 160 void hmap_swap (struct hmap *, struct hmap *);
 161 void hmap_clear (struct hmap *);
 162 void hmap_destroy (struct hmap *);
 163
 164 /* Storage management. */
 165 void hmap_reserve (struct hmap *, size_t capacity);
 166 void hmap_shrink (struct hmap *);
 167
 168 /* Search.  Refer to the large comment near the top of this file
 169    for an example.*/
 170 static inline struct hmap_node *hmap_first_with_hash (const struct hmap *,
 171                                                       size_t hash);
 172 static inline struct hmap_node *hmap_next_with_hash (const struct hmap_node *);
 173
 174 /* Insertion and deletion. */
 175 static inline void hmap_insert (struct hmap *, struct hmap_node *,
 176                                 size_t hash);
 177 static inline void hmap_insert_fast (struct hmap *, struct hmap_node *,
 178                                      size_t hash);
 179 static inline void hmap_delete (struct hmap *, struct hmap_node *);
 180
 181 /* Iteration. */
 182 static inline struct hmap_node *hmap_first (const struct hmap *);
 183 static inline struct hmap_node *hmap_next (const struct hmap *,
 184                                            const struct hmap_node *);
 185
 186 /* Counting. */
 187 static bool hmap_is_empty (const struct hmap *);
 188 static inline size_t hmap_count (const struct hmap *);
 189 static inline size_t hmap_capacity (const struct hmap *);
 190
 191 /* Updating data elements. */
 192 void hmap_changed (struct hmap *, struct hmap_node *, size_t new_hash);
 193 void hmap_moved (struct hmap *,
 194                  struct hmap_node *, const struct hmap_node *old);
 195
 196 /* Convenience macros for search.
 197
 198    These macros automatically use HMAP_DATA to obtain the data
 199    elements that encapsulate hmap nodes, which often saves typing
 200    and can make code easier to read.  Refer to the large comment
 201    near the top of this file for an example.
 202
 203    These macros evaluate HASH only once.  They evaluate their
 204    other arguments many times. */
 205 #define HMAP_FIRST_WITH_HASH(STRUCT, MEMBER, HMAP, HASH)                \
 206   HMAP_NULLABLE_DATA (hmap_first_with_hash (HMAP, HASH), STRUCT, MEMBER)
 207 #define HMAP_NEXT_WITH_HASH(DATA, STRUCT, MEMBER)                       \
 208   HMAP_NULLABLE_DATA (hmap_next_with_hash (&(DATA)->MEMBER), STRUCT, MEMBER)
 209 #define HMAP_FOR_EACH_WITH_HASH(DATA, STRUCT, MEMBER, HASH, HMAP)       \
 210   for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH);      \
 211        (DATA) != NULL;                                                  \
 212        (DATA) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER))
 213 #define HMAP_FOR_EACH_WITH_HASH_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
 214   for ((DATA) = HMAP_FIRST_WITH_HASH (STRUCT, MEMBER, HMAP, HASH);      \
 215        ((DATA) != NULL                                                  \
 216         ? ((NEXT) = HMAP_NEXT_WITH_HASH (DATA, STRUCT, MEMBER), 1)      \
 217         : 0);                                                           \
 218        (DATA) = (NEXT))
 219
 220 /* These macros are like the *_WITH_HASH macros above, except that they don't
 221    skip data elements that are in the same hash bucket but have different hash
 222    values.  This is a small optimization in code where comparing keys is just
 223    as fast as comparing hashes (e.g. the key is an "int") or comparing keys
 224    would duplicate comparing the hashes (e.g. the hash is the first word of a
 225    multi-word random key).
 226
 227    These macros evaluate HASH only once.  They evaluate their
 228    other arguments many times. */
 229 #define HMAP_FIRST_IN_BUCKET(STRUCT, MEMBER, HMAP, HASH)                \
 230   HMAP_NULLABLE_DATA (hmap_first_in_bucket (HMAP, HASH), STRUCT, MEMBER)
 231 #define HMAP_NEXT_IN_BUCKET(DATA, STRUCT, MEMBER)                       \
 232   HMAP_NULLABLE_DATA (hmap_next_in_bucket (&(DATA)->MEMBER), STRUCT, MEMBER)
 233 #define HMAP_FOR_EACH_IN_BUCKET(DATA, STRUCT, MEMBER, HASH, HMAP)       \
 234   for ((DATA) = HMAP_FIRST_IN_BUCKET (STRUCT, MEMBER, HMAP, HASH);      \
 235        (DATA) != NULL;                                                  \
 236        (DATA) = HMAP_NEXT_IN_BUCKET (DATA, STRUCT, MEMBER))
 237 #define HMAP_FOR_EACH_IN_BUCKET_SAFE(DATA, NEXT, STRUCT, MEMBER, HASH, HMAP) \
 238   for ((DATA) = HMAP_FIRST_IN_BUCKET (STRUCT, MEMBER, HMAP, HASH);      \
 239        ((DATA) != NULL                                                  \
 240         ? ((NEXT) = HMAP_NEXT_IN_BUCKET (DATA, STRUCT, MEMBER), 1)      \
 241         : 0);                                                           \
 242        (DATA) = (NEXT))
 243
 244 /* Convenience macros for iteration.
 245
 246    These macros automatically use HMAP_DATA to obtain the data
 247    elements that encapsulate hmap nodes, which often saves typing
 248    and can make code easier to read.  Refer to the large comment
 249    near the top of this file for an example.
 250
 251    These macros evaluate their arguments many times. */
 252 #define HMAP_FIRST(STRUCT, MEMBER, HMAP)                        \
 253   HMAP_NULLABLE_DATA (hmap_first (HMAP), STRUCT, MEMBER)
 254 #define HMAP_NEXT(DATA, STRUCT, MEMBER, HMAP)                           \
 255   HMAP_NULLABLE_DATA (hmap_next (HMAP, &(DATA)->MEMBER), STRUCT, MEMBER)
 256 #define HMAP_FOR_EACH(DATA, STRUCT, MEMBER, HMAP)       \
 257   for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP);      \
 258        (DATA) != NULL;                                  \
 259        (DATA) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP))
 260 #define HMAP_FOR_EACH_SAFE(DATA, NEXT, STRUCT, MEMBER, HMAP)    \
 261   for ((DATA) = HMAP_FIRST (STRUCT, MEMBER, HMAP);              \
 262        ((DATA) != NULL                                          \
 263         ? ((NEXT) = HMAP_NEXT (DATA, STRUCT, MEMBER, HMAP), 1)  \
 264         : 0);                                                   \
 265        (DATA) = (NEXT))
 266 \f
 267 /* Inline definitions. */
 268
 269 static inline struct hmap_node *hmap_find_hash__ (struct hmap_node *, size_t);
 270 static inline struct hmap_node *hmap_first_nonempty_bucket__ (
 271   const struct hmap *, size_t start);
 272 static inline size_t hmap_mask_to_capacity__ (size_t mask);
 273
 274 /* Returns the hash value associated with NODE. */
 275 static inline size_t
 276 hmap_node_hash (const struct hmap_node *node)
 277 {
 278   return node->hash;
 279 }
 280
 281 /* Returns the first node in MAP that has hash value HASH, or a
 282    null pointer if MAP does not contain any node with that hash
 283    value.
 284
 285    Assuming uniform hashing and no duplicate data items in MAP,
 286    this function runs in constant time.  (Amortized over an
 287    iteration over all data items with a given HASH, its runtime
 288    is proportional to the length of the hash chain for HASH, so
 289    given a pathological hash function, e.g. one that returns a
 290    constant value, its runtime degenerates to linear in the
 291    length of NODE's hash chain.)
 292
 293    Nodes are returned in arbitrary order that may change whenever
 294    the hash table's current capacity changes, as reported by
 295    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
 296    hmap_shrink() can change the capacity of a hash map.
 297    Inserting a node with hmap_insert_fast() or deleting one with
 298    hmap_delete() will not change the relative ordering of nodes.
 299
 300    The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
 301    macros provide convenient ways to iterate over all the nodes
 302    with a given hash.  The HMAP_FIRST_WITH_HASH macro is an
 303    interface to this particular function that is often more
 304    convenient. */
 305 static inline struct hmap_node *
 306 hmap_first_with_hash (const struct hmap *map, size_t hash)
 307 {
 308   return hmap_find_hash__ (map->buckets[hash & map->mask], hash);
 309 }
 310
 311 /* Returns the next node in MAP after NODE that has the same hash
 312    value as NODE, or a null pointer if MAP does not contain any
 313    more nodes with that hash value.
 314
 315    Assuming uniform hashing and no duplicate data items in MAP,
 316    this function runs in constant time.  (Amortized over an
 317    iteration over all data items with a given HASH, its runtime
 318    is proportional to the length of the hash chain for HASH, so
 319    given a pathological hash function, e.g. one that returns a
 320    constant value, its runtime degenerates to linear in the
 321    length of NODE's hash chain.)
 322
 323    Nodes are returned in arbitrary order that may change whenever
 324    the hash table's current capacity changes, as reported by
 325    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
 326    hmap_shrink() can change the capacity of a hash map.
 327    Inserting a node with hmap_insert_fast() or deleting one with
 328    hmap_delete() will not change the relative ordering of nodes.
 329
 330    The HMAP_FOR_EACH_WITH_HASH and HMAP_FOR_EACH_WITH_HASH_SAFE
 331    macros provide convenient ways to iterate over all the nodes
 332    with a given hash.  The HMAP_NEXT_WITH_HASH macro is an
 333    interface to this particular function that is often more
 334    convenient. */
 335 static inline struct hmap_node *
 336 hmap_next_with_hash (const struct hmap_node *node)
 337 {
 338   return hmap_find_hash__ (node->next, node->hash);
 339 }
 340
 341 /* Inserts NODE into MAP with hash value HASH.  If the insertion
 342    causes MAP's current capacity, as reported by hmap_capacity(),
 343    to be exceeded, rehashes MAP with an increased number of hash
 344    buckets.
 345
 346    This function runs in constant time amortized over all the
 347    insertions into MAP.
 348
 349    This function does not verify that MAP does not already
 350    contain a data item with the same value as NODE.  If
 351    duplicates should be disallowed (which is the usual case),
 352    then the client must check for duplicates itself before
 353    inserting the new node. */
 354 static inline void
 355 hmap_insert (struct hmap *map, struct hmap_node *node, size_t hash)
 356 {
 357   hmap_insert_fast (map, node, hash);
 358   if (map->count > hmap_capacity (map))
 359     hmap_reserve (map, map->count);
 360 }
 361
 362 /* Inserts NODE into MAP with hash value HASH.  Does not check
 363    whether this causes MAP's current capacity to be exceeded.
 364    The caller must take responsibility for that (or use
 365    hmap_insert() instead).
 366
 367    This function runs in constant time.
 368
 369    This function does not verify that MAP does not already
 370    contain a data item with the same value as NODE.  If
 371    duplicates should be disallowed (which is the usual case),
 372    then the client must check for duplicates itself before
 373    inserting the new node. */
 374 static inline void
 375 hmap_insert_fast (struct hmap *map, struct hmap_node *node, size_t hash)
 376 {
 377   struct hmap_node **bucket = &map->buckets[hash & map->mask];
 378   node->hash = hash;
 379   node->next = *bucket;
 380   *bucket = node;
 381   map->count++;
 382 }
 383
 384 /* Returns the first node in MAP in the bucket for HASH, or a null pointer if
 385    that bucket in HASH is empty.
 386
 387    This function runs in constant time.
 388
 389    Nodes are returned in arbitrary order that may change whenever the hash
 390    table's current capacity changes, as reported by hmap_capacity().  Calls to
 391    hmap_insert(), hmap_reserve(), and hmap_shrink() can change the capacity of
 392    a hash map.  Inserting a node with hmap_insert_fast() or deleting one with
 393    hmap_delete() will not change the relative ordering of nodes.
 394
 395    The HMAP_FOR_EACH_IN_BUCKET and HMAP_FOR_EACH_IN_BUCKET_SAFE macros provide
 396    convenient ways to iterate over all the nodes with a given hash.  The
 397    HMAP_FIRST_IN_BUCKET macro is an interface to this particular function that
 398    is often more convenient. */
 399 static inline struct hmap_node *
 400 hmap_first_in_bucket (const struct hmap *map, size_t hash)
 401 {
 402   return map->buckets[hash & map->mask];
 403 }
 404
 405 /* Returns the next node following NODE within the same bucket, or a null
 406    pointer if NODE is the last node in its bucket.
 407
 408    This function runs in constant time.
 409
 410    Nodes are returned in arbitrary order that may change whenever the hash
 411    table's current capacity changes, as reported by hmap_capacity().  Calls to
 412    hmap_insert(), hmap_reserve(), and hmap_shrink() can change the capacity of
 413    a hash map.  Inserting a node with hmap_insert_fast() or deleting one with
 414    hmap_delete() will not change the relative ordering of nodes.
 415
 416    The HMAP_FOR_EACH_IN_BUCKET and HMAP_FOR_EACH_IN_BUCKET_SAFE macros provide
 417    convenient ways to iterate over all the nodes with a given hash.  The
 418    HMAP_NEXT_IN_BUCKET macro is an interface to this particular function that
 419    is often more convenient. */
 420 static inline struct hmap_node *
 421 hmap_next_in_bucket (const struct hmap_node *node)
 422 {
 423   return node->next;
 424 }
 425
 426 /* Removes NODE from MAP.  The client is responsible for freeing
 427    any data associated with NODE, if necessary.
 428
 429    Assuming uniform hashing, this function runs in constant time.
 430    (Its runtime is proportional to the position of NODE in its
 431    hash chain, so given a pathological hash function, e.g. one
 432    that returns a constant value, its runtime degenerates to
 433    linear in the length of NODE's hash chain.)
 434
 435    This function never reduces the number of buckets in MAP.
 436    When one deletes a large number of nodes from a hash table,
 437    calling hmap_shrink() afterward may therefore save a small
 438    amount of memory.  It is also more expensive to iterate
 439    through a very sparse hash table than a denser one, so
 440    shrinking the hash table could also save some time.  However,
 441    rehashing has an immediate cost that must be weighed against
 442    these benefits.
 443
 444    hmap_delete() does not change NODE's hash value reported by
 445    hmap_node_hash(). */
 446 static inline void
 447 hmap_delete (struct hmap *map, struct hmap_node *node)
 448 {
 449   struct hmap_node **bucket = &map->buckets[node->hash & map->mask];
 450   while (*bucket != node)
 451     bucket = &(*bucket)->next;
 452   *bucket = (*bucket)->next;
 453   map->count--;
 454 }
 455
 456 /* Returns the first node in MAP, or a null pointer if MAP is
 457    empty.
 458
 459    Amortized over iterating through every data element in MAP,
 460    this function runs in constant time.  However, this assumes
 461    that MAP is not excessively sparse, that is, that
 462    hmap_capacity(MAP) is at most a constant factor greater than
 463    hmap_count(MAP).  This will always be true unless many nodes
 464    have been inserted into MAP and then most or all of them
 465    deleted; in such a case, calling hmap_shrink() is advised.
 466
 467    Nodes are returned in arbitrary order that may change whenever
 468    the hash table's current capacity changes, as reported by
 469    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
 470    hmap_shrink() can change the capacity of a hash map.
 471    Inserting a node with hmap_insert_fast() or deleting one with
 472    hmap_delete() will not change the relative ordering of nodes.
 473
 474    The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
 475    convenient ways to iterate over all the nodes in a hash map.
 476    The HMAP_FIRST macro is an interface to this particular
 477    function that is often more convenient. */
 478 static inline struct hmap_node *
 479 hmap_first (const struct hmap *map)
 480 {
 481   return hmap_first_nonempty_bucket__ (map, 0);
 482 }
 483
 484 /* Returns the next node in MAP following NODE, or a null pointer
 485    if NODE is the last node in MAP.
 486
 487    Amortized over iterating through every data element in MAP,
 488    this function runs in constant time.  However, this assumes
 489    that MAP is not excessively sparse, that is, that
 490    hmap_capacity(MAP) is at most a constant factor greater than
 491    hmap_count(MAP).  This will always be true unless many nodes
 492    have been inserted into MAP and then most or all of them
 493    deleted; in such a case, calling hmap_shrink() is advised.
 494
 495    Nodes are returned in arbitrary order that may change whenever
 496    the hash table's current capacity changes, as reported by
 497    hmap_capacity().  Calls to hmap_insert(), hmap_reserve(), and
 498    hmap_shrink() can change the capacity of a hash map.
 499    Inserting a node with hmap_insert_fast() or deleting one with
 500    hmap_delete() will not change the relative ordering of nodes.
 501
 502    The HMAP_FOR_EACH and HMAP_FOR_EACH_SAFE macros provide
 503    convenient ways to iterate over all the nodes in a hash map.
 504    The HMAP_NEXT macro is an interface to this particular
 505    function that is often more convenient. */
 506 static inline struct hmap_node *
 507 hmap_next (const struct hmap *map, const struct hmap_node *node)
 508 {
 509   return (node->next != NULL
 510           ? node->next
 511           : hmap_first_nonempty_bucket__ (map, (node->hash & map->mask) + 1));
 512 }
 513
 514 /* Returns true if MAP currently contains no data items, false
 515    otherwise. */
 516 static inline bool
 517 hmap_is_empty (const struct hmap *map)
 518 {
 519   return map->count == 0;
 520 }
 521
 522 /* Returns the number of data items currently in MAP. */
 523 static inline size_t
 524 hmap_count (const struct hmap *map)
 525 {
 526   return map->count;
 527 }
 528
 529 /* Returns the current capacity of MAP, that is, the maximum
 530    number of data elements that MAP may hold before it becomes
 531    advisable to rehash.
 532
 533    The capacity is advisory only: it is possible to insert any
 534    number of data elements into a hash map regardless of its
 535    capacity.  However, inserting many more elements than the
 536    map's capacity will degrade search performance. */
 537 static inline size_t
 538 hmap_capacity (const struct hmap *map)
 539 {
 540   return hmap_mask_to_capacity__ (map->mask);
 541 }
 542 \f
 543 /* Implementation details. */
 544
 545 /* Returns the first node at or after NODE in NODE's chain that
 546    has hash value HASH. */
 547 static inline struct hmap_node *
 548 hmap_find_hash__ (struct hmap_node *node, size_t hash)
 549 {
 550   for (; node != NULL; node = node->next)
 551     if (node->hash == hash)
 552       break;
 553   return node;
 554 }
 555
 556 /* Returns the first node in the lowest-numbered nonempty bucket
 557    in MAP whose index is START or higher, or a null pointer if
 558    all such buckets are empty. */
 559 static inline struct hmap_node *
 560 hmap_first_nonempty_bucket__ (const struct hmap *map, size_t start)
 561 {
 562   size_t i;
 563
 564   for (i = start; i <= map->mask; i++)
 565     if (map->buckets[i] != NULL)
 566       return map->buckets[i];
 567   return NULL;
 568 }
 569
 570 /* Returns the hash table capacity associated with a given MASK,
 571    which should be a value for the "mask" member of struct hmap.
 572    MASK must be a power of 2 minus 1 (including 0), that is, its
 573    value in binary must be all 1-bits.  */
 574 static inline size_t
 575 hmap_mask_to_capacity__ (size_t mask)
 576 {
 577   return (mask + 1) * 2;
 578 }
 579
 580 /* Helper for HMAP_NULLABLE_DATA (to avoid evaluating its NODE
 581    argument more than once).  */
 582 static inline void *
 583 hmap_nullable_data__ (struct hmap_node *node, size_t member_offset)
 584 {
 585   return node != NULL ? (char *) node - member_offset : NULL;
 586 }
 587
 588 #endif /* libpspp/hmap.h */