ofproto-provider: Update documentation.
[sliver-openvswitch.git] / lib / hmap.c
1 /*
2  * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
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 #include <config.h>
18 #include "hmap.h"
19 #include <stdint.h>
20 #include <string.h>
21 #include "coverage.h"
22 #include "random.h"
23 #include "util.h"
24 #include "vlog.h"
25
26 VLOG_DEFINE_THIS_MODULE(hmap);
27
28 COVERAGE_DEFINE(hmap_pathological);
29 COVERAGE_DEFINE(hmap_expand);
30 COVERAGE_DEFINE(hmap_shrink);
31 COVERAGE_DEFINE(hmap_reserve);
32
33 /* Initializes 'hmap' as an empty hash table. */
34 void
35 hmap_init(struct hmap *hmap)
36 {
37     hmap->buckets = &hmap->one;
38     hmap->one = NULL;
39     hmap->mask = 0;
40     hmap->n = 0;
41 }
42
43 /* Frees memory reserved by 'hmap'.  It is the client's responsibility to free
44  * the nodes themselves, if necessary. */
45 void
46 hmap_destroy(struct hmap *hmap)
47 {
48     if (hmap && hmap->buckets != &hmap->one) {
49         free(hmap->buckets);
50     }
51 }
52
53 /* Removes all node from 'hmap', leaving it ready to accept more nodes.  Does
54  * not free memory allocated for 'hmap'.
55  *
56  * This function is appropriate when 'hmap' will soon have about as many
57  * elements as it before.  If 'hmap' will likely have fewer elements than
58  * before, use hmap_destroy() followed by hmap_clear() to save memory and
59  * iteration time. */
60 void
61 hmap_clear(struct hmap *hmap)
62 {
63     if (hmap->n > 0) {
64         hmap->n = 0;
65         memset(hmap->buckets, 0, (hmap->mask + 1) * sizeof *hmap->buckets);
66     }
67 }
68
69 /* Exchanges hash maps 'a' and 'b'. */
70 void
71 hmap_swap(struct hmap *a, struct hmap *b)
72 {
73     struct hmap tmp = *a;
74     *a = *b;
75     *b = tmp;
76     hmap_moved(a);
77     hmap_moved(b);
78 }
79
80 /* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
81  * to realloc()). */
82 void
83 hmap_moved(struct hmap *hmap)
84 {
85     if (!hmap->mask) {
86         hmap->buckets = &hmap->one;
87     }
88 }
89
90 static void
91 resize(struct hmap *hmap, size_t new_mask, const char *where)
92 {
93     struct hmap tmp;
94     size_t i;
95
96     ovs_assert(is_pow2(new_mask + 1));
97
98     hmap_init(&tmp);
99     if (new_mask) {
100         tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
101         tmp.mask = new_mask;
102         for (i = 0; i <= tmp.mask; i++) {
103             tmp.buckets[i] = NULL;
104         }
105     }
106     for (i = 0; i <= hmap->mask; i++) {
107         struct hmap_node *node, *next;
108         int count = 0;
109         for (node = hmap->buckets[i]; node; node = next) {
110             next = node->next;
111             hmap_insert_fast(&tmp, node, node->hash);
112             count++;
113         }
114         if (count > 5) {
115             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
116             COVERAGE_INC(hmap_pathological);
117             VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%"PRIuSIZE" nodes, %"PRIuSIZE" buckets)",
118                         where, count, hmap->n, hmap->mask + 1);
119         }
120     }
121     hmap_swap(hmap, &tmp);
122     hmap_destroy(&tmp);
123 }
124
125 static size_t
126 calc_mask(size_t capacity)
127 {
128     size_t mask = capacity / 2;
129     mask |= mask >> 1;
130     mask |= mask >> 2;
131     mask |= mask >> 4;
132     mask |= mask >> 8;
133     mask |= mask >> 16;
134 #if SIZE_MAX > UINT32_MAX
135     mask |= mask >> 32;
136 #endif
137
138     /* If we need to dynamically allocate buckets we might as well allocate at
139      * least 4 of them. */
140     mask |= (mask & 1) << 1;
141
142     return mask;
143 }
144
145 /* Expands 'hmap', if necessary, to optimize the performance of searches.
146  *
147  * ('where' is used in debug logging.  Commonly one would use hmap_expand() to
148  * automatically provide the caller's source file and line number for
149  * 'where'.) */
150 void
151 hmap_expand_at(struct hmap *hmap, const char *where)
152 {
153     size_t new_mask = calc_mask(hmap->n);
154     if (new_mask > hmap->mask) {
155         COVERAGE_INC(hmap_expand);
156         resize(hmap, new_mask, where);
157     }
158 }
159
160 /* Shrinks 'hmap', if necessary, to optimize the performance of iteration.
161  *
162  * ('where' is used in debug logging.  Commonly one would use hmap_shrink() to
163  * automatically provide the caller's source file and line number for
164  * 'where'.) */
165 void
166 hmap_shrink_at(struct hmap *hmap, const char *where)
167 {
168     size_t new_mask = calc_mask(hmap->n);
169     if (new_mask < hmap->mask) {
170         COVERAGE_INC(hmap_shrink);
171         resize(hmap, new_mask, where);
172     }
173 }
174
175 /* Expands 'hmap', if necessary, to optimize the performance of searches when
176  * it has up to 'n' elements.  (But iteration will be slow in a hash map whose
177  * allocated capacity is much higher than its current number of nodes.)
178  *
179  * ('where' is used in debug logging.  Commonly one would use hmap_reserve() to
180  * automatically provide the caller's source file and line number for
181  * 'where'.) */
182 void
183 hmap_reserve_at(struct hmap *hmap, size_t n, const char *where)
184 {
185     size_t new_mask = calc_mask(n);
186     if (new_mask > hmap->mask) {
187         COVERAGE_INC(hmap_reserve);
188         resize(hmap, new_mask, where);
189     }
190 }
191
192 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
193  * to 'node' (e.g. due to realloc()). */
194 void
195 hmap_node_moved(struct hmap *hmap,
196                 struct hmap_node *old_node, struct hmap_node *node)
197 {
198     struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
199     while (*bucket != old_node) {
200         bucket = &(*bucket)->next;
201     }
202     *bucket = node;
203 }
204
205 /* Chooses and returns a randomly selected node from 'hmap', which must not be
206  * empty.
207  *
208  * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
209  * But it does at least ensure that any node in 'hmap' can be chosen. */
210 struct hmap_node *
211 hmap_random_node(const struct hmap *hmap)
212 {
213     struct hmap_node *bucket, *node;
214     size_t n, i;
215
216     /* Choose a random non-empty bucket. */
217     for (i = random_uint32(); ; i++) {
218         bucket = hmap->buckets[i & hmap->mask];
219         if (bucket) {
220             break;
221         }
222     }
223
224     /* Count nodes in bucket. */
225     n = 0;
226     for (node = bucket; node; node = node->next) {
227         n++;
228     }
229
230     /* Choose random node from bucket. */
231     i = random_range(n);
232     for (node = bucket; i-- > 0; node = node->next) {
233         continue;
234     }
235     return node;
236 }
237
238 /* Returns the next node in 'hmap' in hash order, or NULL if no nodes remain in
239  * 'hmap'.  Uses '*bucketp' and '*offsetp' to determine where to begin
240  * iteration, and stores new values to pass on the next iteration into them
241  * before returning.
242  *
243  * It's better to use plain HMAP_FOR_EACH and related functions, since they are
244  * faster and better at dealing with hmaps that change during iteration.
245  *
246  * Before beginning iteration, store 0 into '*bucketp' and '*offsetp'.
247  */
248 struct hmap_node *
249 hmap_at_position(const struct hmap *hmap,
250                  uint32_t *bucketp, uint32_t *offsetp)
251 {
252     size_t offset;
253     size_t b_idx;
254
255     offset = *offsetp;
256     for (b_idx = *bucketp; b_idx <= hmap->mask; b_idx++) {
257         struct hmap_node *node;
258         size_t n_idx;
259
260         for (n_idx = 0, node = hmap->buckets[b_idx]; node != NULL;
261              n_idx++, node = node->next) {
262             if (n_idx == offset) {
263                 if (node->next) {
264                     *bucketp = node->hash & hmap->mask;
265                     *offsetp = offset + 1;
266                 } else {
267                     *bucketp = (node->hash & hmap->mask) + 1;
268                     *offsetp = 0;
269                 }
270                 return node;
271             }
272         }
273         offset = 0;
274     }
275
276     *bucketp = 0;
277     *offsetp = 0;
278     return NULL;
279 }
280
281 /* Returns true if 'node' is in 'hmap', false otherwise. */
282 bool
283 hmap_contains(const struct hmap *hmap, const struct hmap_node *node)
284 {
285     struct hmap_node *p;
286
287     for (p = hmap_first_in_bucket(hmap, node->hash); p; p = p->next) {
288         if (p == node) {
289             return true;
290         }
291     }
292
293     return false;
294 }