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