lib/hmap.h

   1 /*
   2  * Copyright (c) 2008, 2009 Nicira Networks.
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  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 /* A hash map. */
  37 struct hmap {
  38     struct hmap_node **buckets;
  39     struct hmap_node *one;
  40     size_t mask;
  41     size_t n;
  42 };
  43
  44 /* Initializer for an empty hash map. */
  45 #define HMAP_INITIALIZER(HMAP) { &(HMAP)->one, NULL, 0, 0 }
  46
  47 /* Initialization. */
  48 void hmap_init(struct hmap *);
  49 void hmap_destroy(struct hmap *);
  50 void hmap_swap(struct hmap *a, struct hmap *b);
  51 static inline size_t hmap_count(const struct hmap *);
  52 static inline bool hmap_is_empty(const struct hmap *);
  53
  54 /* Adjusting capacity. */
  55 void hmap_expand(struct hmap *);
  56 void hmap_shrink(struct hmap *);
  57 void hmap_reserve(struct hmap *, size_t capacity);
  58
  59 /* Insertion and deletion. */
  60 static inline void hmap_insert_fast(struct hmap *,
  61                                     struct hmap_node *, size_t hash);
  62 static inline void hmap_insert(struct hmap *, struct hmap_node *, size_t hash);
  63 static inline void hmap_remove(struct hmap *, struct hmap_node *);
  64 static inline void hmap_moved(struct hmap *,
  65                               struct hmap_node *, struct hmap_node *);
  66 static inline void hmap_replace(struct hmap *, const struct hmap_node *old,
  67                                 struct hmap_node *new);
  68
  69 /* Search. */
  70 #define HMAP_FOR_EACH_WITH_HASH(NODE, STRUCT, MEMBER, HASH, HMAP)       \
  71     for ((NODE) = CONTAINER_OF(hmap_first_with_hash(HMAP, HASH),        \
  72                                STRUCT, MEMBER);                         \
  73          &(NODE)->MEMBER != NULL;                                       \
  74          (NODE) = CONTAINER_OF(hmap_next_with_hash(&(NODE)->MEMBER),    \
  75                                STRUCT, MEMBER))
  76
  77 static inline struct hmap_node *hmap_first_with_hash(const struct hmap *,
  78                                                      size_t hash);
  79 static inline struct hmap_node *hmap_next_with_hash(const struct hmap_node *);
  80
  81 /* Iteration.
  82  *
  83  * The _SAFE version is needed when NODE may be freed.  It is not needed when
  84  * NODE may be removed from the hash map but its members remain accessible and
  85  * intact. */
  86 #define HMAP_FOR_EACH(NODE, STRUCT, MEMBER, HMAP)                   \
  87     for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER);   \
  88          &(NODE)->MEMBER != NULL;                                   \
  89          (NODE) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER),    \
  90                                STRUCT, MEMBER))
  91
  92 #define HMAP_FOR_EACH_SAFE(NODE, NEXT, STRUCT, MEMBER, HMAP)        \
  93     for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER);   \
  94          (&(NODE)->MEMBER != NULL                                   \
  95           ? (NEXT) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \
  96                                   STRUCT, MEMBER), 1                \
  97           : 0);                                                     \
  98          (NODE) = (NEXT))
  99
 100 static inline struct hmap_node *hmap_first(const struct hmap *);
 101 static inline struct hmap_node *hmap_next(const struct hmap *,
 102                                           const struct hmap_node *);
 103
 104 /* Returns the number of nodes currently in 'hmap'. */
 105 static inline size_t
 106 hmap_count(const struct hmap *hmap)
 107 {
 108     return hmap->n;
 109 }
 110
 111 /* Returns true if 'hmap' currently contains no nodes,
 112  * false otherwise. */
 113 static inline bool
 114 hmap_is_empty(const struct hmap *hmap)
 115 {
 116     return hmap->n == 0;
 117 }
 118
 119 /* Inserts 'node', with the given 'hash', into 'hmap'.  'hmap' is never
 120  * expanded automatically. */
 121 static inline void
 122 hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash)
 123 {
 124     struct hmap_node **bucket = &hmap->buckets[hash & hmap->mask];
 125     node->hash = hash;
 126     node->next = *bucket;
 127     *bucket = node;
 128     hmap->n++;
 129 }
 130
 131 /* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if
 132  * necessary to optimize search performance. */
 133 static inline void
 134 hmap_insert(struct hmap *hmap, struct hmap_node *node, size_t hash)
 135 {
 136     hmap_insert_fast(hmap, node, hash);
 137     if (hmap->n / 2 > hmap->mask) {
 138         hmap_expand(hmap);
 139     }
 140 }
 141
 142 /* Removes 'node' from 'hmap'.  Does not shrink the hash table; call
 143  * hmap_shrink() directly if desired. */
 144 static inline void
 145 hmap_remove(struct hmap *hmap, struct hmap_node *node)
 146 {
 147     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
 148     while (*bucket != node) {
 149         bucket = &(*bucket)->next;
 150     }
 151     *bucket = node->next;
 152     hmap->n--;
 153 }
 154
 155 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
 156  * to 'node' (e.g. due to realloc()). */
 157 static inline void
 158 hmap_moved(struct hmap *hmap,
 159            struct hmap_node *old_node, struct hmap_node *node)
 160 {
 161     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
 162     while (*bucket != old_node) {
 163         bucket = &(*bucket)->next;
 164     }
 165     *bucket = node;
 166 }
 167
 168 /* Puts 'new' in the position in 'hmap' currently occupied by 'old'.  The 'new'
 169  * node must hash to the same value as 'old'.  The client is responsible for
 170  * ensuring that the replacement does not violate any client-imposed
 171  * invariants (e.g. uniqueness of keys within a map).
 172  *
 173  * Afterward, 'old' is not part of 'hmap', and the client is responsible for
 174  * freeing it (if this is desirable). */
 175 static inline void
 176 hmap_replace(struct hmap *hmap,
 177              const struct hmap_node *old, struct hmap_node *new)
 178 {
 179     struct hmap_node **bucket = &hmap->buckets[old->hash & hmap->mask];
 180     while (*bucket != old) {
 181         bucket = &(*bucket)->next;
 182     }
 183     *bucket = new;
 184     new->hash = old->hash;
 185 }
 186
 187 static inline struct hmap_node *
 188 hmap_next_with_hash__(const struct hmap_node *node, size_t hash)
 189 {
 190     while (node != NULL && node->hash != hash) {
 191         node = node->next;
 192     }
 193     return (struct hmap_node *) node;
 194 }
 195
 196 /* Returns the first node in 'hmap' with the given 'hash', or a null pointer if
 197  * no nodes have that hash value. */
 198 static inline struct hmap_node *
 199 hmap_first_with_hash(const struct hmap *hmap, size_t hash)
 200 {
 201     return hmap_next_with_hash__(hmap->buckets[hash & hmap->mask], hash);
 202 }
 203
 204 /* Returns the next node in the same hash map as 'node' with the same hash
 205  * value, or a null pointer if no more nodes have that hash value.
 206  *
 207  * If the hash map has been reallocated since 'node' was visited, some nodes
 208  * may be skipped; if new nodes with the same hash value have been added, they
 209  * will be skipped.  (Removing 'node' from the hash map does not prevent
 210  * calling this function, since node->next is preserved, although freeing
 211  * 'node' of course does.) */
 212 static inline struct hmap_node *
 213 hmap_next_with_hash(const struct hmap_node *node)
 214 {
 215     return hmap_next_with_hash__(node->next, node->hash);
 216 }
 217
 218 static inline struct hmap_node *
 219 hmap_next__(const struct hmap *hmap, size_t start)
 220 {
 221     size_t i;
 222     for (i = start; i <= hmap->mask; i++) {
 223         struct hmap_node *node = hmap->buckets[i];
 224         if (node) {
 225             return node;
 226         }
 227     }
 228     return NULL;
 229 }
 230
 231 /* Returns the first node in 'hmap', in arbitrary order, or a null pointer if
 232  * 'hmap' is empty. */
 233 static inline struct hmap_node *
 234 hmap_first(const struct hmap *hmap)
 235 {
 236     return hmap_next__(hmap, 0);
 237 }
 238
 239 /* Returns the next node in 'hmap' following 'node', in arbitrary order, or a
 240  * null pointer if 'node' is the last node in 'hmap'.
 241  *
 242  * If the hash map has been reallocated since 'node' was visited, some nodes
 243  * may be skipped or visited twice.  (Removing 'node' from the hash map does
 244  * not prevent calling this function, since node->next is preserved, although
 245  * freeing 'node' of course does.) */
 246 static inline struct hmap_node *
 247 hmap_next(const struct hmap *hmap, const struct hmap_node *node)
 248 {
 249     return (node->next
 250             ? node->next
 251             : hmap_next__(hmap, (node->hash & hmap->mask) + 1));
 252 }
 253
 254 #endif /* hmap.h */