2 * Copyright (c) 2008, 2009 Nicira Networks.
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.
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.
24 /* A hash map node, to be embedded inside the data structure being mapped. */
26 size_t hash; /* Hash value. */
27 struct hmap_node *next; /* Next in linked list. */
30 /* Returns the hash value embedded in 'node'. */
31 static inline size_t hmap_node_hash(const struct hmap_node *node)
38 struct hmap_node **buckets;
39 struct hmap_node *one;
44 /* Initializer for an empty hash map. */
45 #define HMAP_INITIALIZER(HMAP) { &(HMAP)->one, NULL, 0, 0 }
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 *);
54 /* Adjusting capacity. */
55 void hmap_expand(struct hmap *);
56 void hmap_shrink(struct hmap *);
57 void hmap_reserve(struct hmap *, size_t capacity);
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);
70 #define HMAP_FOR_EACH_WITH_HASH(NODE, STRUCT, MEMBER, HASH, HMAP) \
71 for ((NODE) = CONTAINER_OF(hmap_first_with_hash(HMAP, HASH), \
73 &(NODE)->MEMBER != NULL; \
74 (NODE) = CONTAINER_OF(hmap_next_with_hash(&(NODE)->MEMBER), \
77 static inline struct hmap_node *hmap_first_with_hash(const struct hmap *,
79 static inline struct hmap_node *hmap_next_with_hash(const struct hmap_node *);
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
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), \
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), \
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 *);
104 /* Returns the number of nodes currently in 'hmap'. */
106 hmap_count(const struct hmap *hmap)
111 /* Returns true if 'hmap' currently contains no nodes,
112 * false otherwise. */
114 hmap_is_empty(const struct hmap *hmap)
119 /* Inserts 'node', with the given 'hash', into 'hmap'. 'hmap' is never
120 * expanded automatically. */
122 hmap_insert_fast(struct hmap *hmap, struct hmap_node *node, size_t hash)
124 struct hmap_node **bucket = &hmap->buckets[hash & hmap->mask];
126 node->next = *bucket;
131 /* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if
132 * necessary to optimize search performance. */
134 hmap_insert(struct hmap *hmap, struct hmap_node *node, size_t hash)
136 hmap_insert_fast(hmap, node, hash);
137 if (hmap->n / 2 > hmap->mask) {
142 /* Removes 'node' from 'hmap'. Does not shrink the hash table; call
143 * hmap_shrink() directly if desired. */
145 hmap_remove(struct hmap *hmap, struct hmap_node *node)
147 struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
148 while (*bucket != node) {
149 bucket = &(*bucket)->next;
151 *bucket = node->next;
155 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
156 * to 'node' (e.g. due to realloc()). */
158 hmap_moved(struct hmap *hmap,
159 struct hmap_node *old_node, struct hmap_node *node)
161 struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
162 while (*bucket != old_node) {
163 bucket = &(*bucket)->next;
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).
173 * Afterward, 'old' is not part of 'hmap', and the client is responsible for
174 * freeing it (if this is desirable). */
176 hmap_replace(struct hmap *hmap,
177 const struct hmap_node *old, struct hmap_node *new)
179 struct hmap_node **bucket = &hmap->buckets[old->hash & hmap->mask];
180 while (*bucket != old) {
181 bucket = &(*bucket)->next;
184 new->hash = old->hash;
187 static inline struct hmap_node *
188 hmap_next_with_hash__(const struct hmap_node *node, size_t hash)
190 while (node != NULL && node->hash != hash) {
193 return (struct hmap_node *) node;
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)
201 return hmap_next_with_hash__(hmap->buckets[hash & hmap->mask], hash);
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.
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)
215 return hmap_next_with_hash__(node->next, node->hash);
218 static inline struct hmap_node *
219 hmap_next__(const struct hmap *hmap, size_t start)
222 for (i = start; i <= hmap->mask; i++) {
223 struct hmap_node *node = hmap->buckets[i];
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)
236 return hmap_next__(hmap, 0);
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'.
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)
251 : hmap_next__(hmap, (node->hash & hmap->mask) + 1));