lib/hmap.h

   1 /*
   2  * Copyright (c) 2008, 2009, 2010 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef HMAP_H
  18 #define HMAP_H 1
  19
  20 #include <stdbool.h>
  21 #include <stdlib.h>
  22 #include "util.h"
  23
  24 /* A hash map node, to be embedded inside the data structure being mapped. */
  25 struct hmap_node {
  26     size_t hash;                /* Hash value. */
  27     struct hmap_node *next;     /* Next in linked list. */
  28 };
  29
  30 /* Returns the hash value embedded in 'node'. */
  31 static inline size_t hmap_node_hash(const struct hmap_node *node)
  32 {
  33     return node->hash;
  34 }
  35
  36 #define HMAP_NODE_NULL ((struct hmap_node *) 1)
  37
  38 /* Returns true if 'node' has been set to null by hmap_node_nullify() and has
  39  * not been un-nullified by being inserted into an hmap. */
  40 static inline bool
  41 hmap_node_is_null(const struct hmap_node *node)
  42 {
  43     return node->next == HMAP_NODE_NULL;
  44 }
  45
  46 /* Marks 'node' with a distinctive value that can be tested with
  47  * hmap_node_is_null().  */
  48 static inline void
  49 hmap_node_nullify(struct hmap_node *node)
  50 {
  51     node->next = HMAP_NODE_NULL;
  52 }
  53
  54 /* A hash map. */
  55 struct hmap {
  56     struct hmap_node **buckets; /* Must point to 'one' iff 'mask' == 0. */
  57     struct hmap_node *one;
  58     size_t mask;
  59     size_t n;
  60 };
  61
  62 /* Initializer for an empty hash map. */
  63 #define HMAP_INITIALIZER(HMAP) { &(HMAP)->one, NULL, 0, 0 }
  64
  65 /* Initialization. */
  66 void hmap_init(struct hmap *);
  67 void hmap_destroy(struct hmap *);
  68 void hmap_swap(struct hmap *a, struct hmap *b);
  69 void hmap_moved(struct hmap *);
  70 static inline size_t hmap_count(const struct hmap *);
  71 static inline bool hmap_is_empty(const struct hmap *);
  72
  73 /* Adjusting capacity. */
  74 void hmap_expand(struct hmap *);
  75 void hmap_shrink(struct hmap *);
  76 void hmap_reserve(struct hmap *, size_t capacity);
  77
  78 /* Insertion and deletion. */
  79 static inline void hmap_insert_fast(struct hmap *,
  80                                     struct hmap_node *, size_t hash);
  81 static inline void hmap_insert(struct hmap *, struct hmap_node *, size_t hash);
  82 static inline void hmap_remove(struct hmap *, struct hmap_node *);
  83 void hmap_node_moved(struct hmap *, struct hmap_node *, struct hmap_node *);
  84 static inline void hmap_replace(struct hmap *, const struct hmap_node *old,
  85                                 struct hmap_node *new);
  86
  87 /* Search.
  88  *
  89  * HMAP_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HMAP that
  90  * have hash value equal to HASH.  HMAP_FOR_EACH_IN_BUCKET iterates NODE over
  91  * all of the nodes in HMAP that would fall in the same bucket as HASH.  STRUCT
  92  * and MEMBER must be the name of the struct that contains the 'struct
  93  * hmap_node' and the name of the 'struct hmap_node' member, respectively.
  94  *
  95  * These macros may be used interchangeably to search for a particular value in
  96  * an hmap, see, e.g. shash_find() for an example.  Usually, using
  97  * HMAP_FOR_EACH_WITH_HASH provides an optimization, because comparing a hash
  98  * value is usually cheaper than comparing an entire hash map key.  But for
  99  * simple hash map keys, it makes sense to use HMAP_FOR_EACH_IN_BUCKET because
 100  * it avoids doing two comparisons when a single simple comparison suffices.
 101  *
 102  * The loop should not change NODE to point to a different node or insert or
 103  * delete nodes in HMAP (unless it "break"s out of the loop to terminate
 104  * iteration).
 105  *
 106  * HASH is only evaluated once.
 107  */
 108 #define HMAP_FOR_EACH_WITH_HASH(NODE, STRUCT, MEMBER, HASH, HMAP)       \
 109     for ((NODE) = CONTAINER_OF(hmap_first_with_hash(HMAP, HASH),        \
 110                                STRUCT, MEMBER);                         \
 111          &(NODE)->MEMBER != NULL;                                       \
 112          (NODE) = CONTAINER_OF(hmap_next_with_hash(&(NODE)->MEMBER),    \
 113                                STRUCT, MEMBER))
 114 #define HMAP_FOR_EACH_IN_BUCKET(NODE, STRUCT, MEMBER, HASH, HMAP)       \
 115     for ((NODE) = CONTAINER_OF(hmap_first_in_bucket(HMAP, HASH),        \
 116                                STRUCT, MEMBER);                         \
 117          &(NODE)->MEMBER != NULL;                                       \
 118          (NODE) = CONTAINER_OF(hmap_next_in_bucket(&(NODE)->MEMBER),    \
 119                                STRUCT, MEMBER))
 120
 121 static inline struct hmap_node *hmap_first_with_hash(const struct hmap *,
 122                                                      size_t hash);
 123 static inline struct hmap_node *hmap_next_with_hash(const struct hmap_node *);
 124 static inline struct hmap_node *hmap_first_in_bucket(const struct hmap *,
 125                                                      size_t hash);
 126 static inline struct hmap_node *hmap_next_in_bucket(const struct hmap_node *);
 127
 128 /* Iteration.
 129  *
 130  * The _SAFE version is needed when NODE may be freed.  It is not needed when
 131  * NODE may be removed from the hash map but its members remain accessible and
 132  * intact. */
 133 #define HMAP_FOR_EACH(NODE, STRUCT, MEMBER, HMAP)                   \
 134     for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER);   \
 135          &(NODE)->MEMBER != NULL;                                   \
 136          (NODE) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER),    \
 137                                STRUCT, MEMBER))
 138
 139 #define HMAP_FOR_EACH_SAFE(NODE, NEXT, STRUCT, MEMBER, HMAP)        \
 140     for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER);   \
 141          (&(NODE)->MEMBER != NULL                                   \
 142           ? (NEXT) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \
 143                                   STRUCT, MEMBER), 1                \
 144           : 0);                                                     \
 145          (NODE) = (NEXT))
 146
 147 static inline struct hmap_node *hmap_first(const struct hmap *);
 148 static inline struct hmap_node *hmap_next(const struct hmap *,
 149                                           const struct hmap_node *);
 150
 151 /* Returns the number of nodes currently in 'hmap'. */
 152 static inline size_t
 153 hmap_count(const struct hmap *hmap)
 154 {
 155     return hmap->n;
 156 }
 157
 158 /* Returns the maximum number of nodes that 'hmap' may hold before it should be
 159  * rehashed. */
 160 static inline size_t
 161 hmap_capacity(const struct hmap *hmap)
 162 {
 163     return hmap->mask * 2 + 1;
 164 }
 165
 166 /* Returns true if 'hmap' currently contains no nodes,
 167  * false otherwise. */
 168 static inline bool
 169 hmap_is_empty(const struct hmap *hmap)
 170 {
 171     return hmap->n == 0;
 172 }
 173
 174 /* Inserts 'node', with the given 'hash', into 'hmap'.  'hmap' is never
 175  * expanded automatically. */
 176 static inline void
 177 hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash)
 178 {
 179     struct hmap_node **bucket = &hmap->buckets[hash & hmap->mask];
 180     node->hash = hash;
 181     node->next = *bucket;
 182     *bucket = node;
 183     hmap->n++;
 184 }
 185
 186 /* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if
 187  * necessary to optimize search performance. */
 188 static inline void
 189 hmap_insert(struct hmap *hmap, struct hmap_node *node, size_t hash)
 190 {
 191     hmap_insert_fast(hmap, node, hash);
 192     if (hmap->n / 2 > hmap->mask) {
 193         hmap_expand(hmap);
 194     }
 195 }
 196
 197 /* Removes 'node' from 'hmap'.  Does not shrink the hash table; call
 198  * hmap_shrink() directly if desired. */
 199 static inline void
 200 hmap_remove(struct hmap *hmap, struct hmap_node *node)
 201 {
 202     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
 203     while (*bucket != node) {
 204         bucket = &(*bucket)->next;
 205     }
 206     *bucket = node->next;
 207     hmap->n--;
 208 }
 209
 210 /* Puts 'new' in the position in 'hmap' currently occupied by 'old'.  The 'new'
 211  * node must hash to the same value as 'old'.  The client is responsible for
 212  * ensuring that the replacement does not violate any client-imposed
 213  * invariants (e.g. uniqueness of keys within a map).
 214  *
 215  * Afterward, 'old' is not part of 'hmap', and the client is responsible for
 216  * freeing it (if this is desirable). */
 217 static inline void
 218 hmap_replace(struct hmap *hmap,
 219              const struct hmap_node *old, struct hmap_node *new)
 220 {
 221     struct hmap_node **bucket = &hmap->buckets[old->hash & hmap->mask];
 222     while (*bucket != old) {
 223         bucket = &(*bucket)->next;
 224     }
 225     *bucket = new;
 226     new->hash = old->hash;
 227     new->next = old->next;
 228 }
 229
 230 static inline struct hmap_node *
 231 hmap_next_with_hash__(const struct hmap_node *node, size_t hash)
 232 {
 233     while (node != NULL && node->hash != hash) {
 234         node = node->next;
 235     }
 236     return (struct hmap_node *) node;
 237 }
 238
 239 /* Returns the first node in 'hmap' with the given 'hash', or a null pointer if
 240  * no nodes have that hash value. */
 241 static inline struct hmap_node *
 242 hmap_first_with_hash(const struct hmap *hmap, size_t hash)
 243 {
 244     return hmap_next_with_hash__(hmap->buckets[hash & hmap->mask], hash);
 245 }
 246
 247 /* Returns the first node in 'hmap' in the bucket in which the given 'hash'
 248  * would land, or a null pointer if that bucket is empty. */
 249 static inline struct hmap_node *
 250 hmap_first_in_bucket(const struct hmap *hmap, size_t hash)
 251 {
 252     return hmap->buckets[hash & hmap->mask];
 253 }
 254
 255 /* Returns the next node in the same bucket as 'node', or a null pointer if
 256  * there are no more nodes in that bucket.
 257  *
 258  * If the hash map has been reallocated since 'node' was visited, some nodes
 259  * may be skipped; if new nodes with the same hash value have been added, they
 260  * will be skipped.  (Removing 'node' from the hash map does not prevent
 261  * calling this function, since node->next is preserved, although freeing
 262  * 'node' of course does.) */
 263 static inline struct hmap_node *
 264 hmap_next_in_bucket(const struct hmap_node *node)
 265 {
 266     return node->next;
 267 }
 268
 269 /* Returns the next node in the same hash map as 'node' with the same hash
 270  * value, or a null pointer if no more nodes have that hash value.
 271  *
 272  * If the hash map has been reallocated since 'node' was visited, some nodes
 273  * may be skipped; if new nodes with the same hash value have been added, they
 274  * will be skipped.  (Removing 'node' from the hash map does not prevent
 275  * calling this function, since node->next is preserved, although freeing
 276  * 'node' of course does.) */
 277 static inline struct hmap_node *
 278 hmap_next_with_hash(const struct hmap_node *node)
 279 {
 280     return hmap_next_with_hash__(node->next, node->hash);
 281 }
 282
 283 static inline struct hmap_node *
 284 hmap_next__(const struct hmap *hmap, size_t start)
 285 {
 286     size_t i;
 287     for (i = start; i <= hmap->mask; i++) {
 288         struct hmap_node *node = hmap->buckets[i];
 289         if (node) {
 290             return node;
 291         }
 292     }
 293     return NULL;
 294 }
 295
 296 /* Returns the first node in 'hmap', in arbitrary order, or a null pointer if
 297  * 'hmap' is empty. */
 298 static inline struct hmap_node *
 299 hmap_first(const struct hmap *hmap)
 300 {
 301     return hmap_next__(hmap, 0);
 302 }
 303
 304 /* Returns the next node in 'hmap' following 'node', in arbitrary order, or a
 305  * null pointer if 'node' is the last node in 'hmap'.
 306  *
 307  * If the hash map has been reallocated since 'node' was visited, some nodes
 308  * may be skipped or visited twice.  (Removing 'node' from the hash map does
 309  * not prevent calling this function, since node->next is preserved, although
 310  * freeing 'node' of course does.) */
 311 static inline struct hmap_node *
 312 hmap_next(const struct hmap *hmap, const struct hmap_node *node)
 313 {
 314     return (node->next
 315             ? node->next
 316             : hmap_next__(hmap, (node->hash & hmap->mask) + 1));
 317 }
 318
 319 #endif /* hmap.h */