Import from old repository commit 61ef2b42a9c4ba8e1600f15bb0236765edc2ad45.
[openvswitch] / 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 */