Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2015 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 "openvswitch/hmap.h"
19 : : #include <stdint.h>
20 : : #include <string.h>
21 : : #include "coverage.h"
22 : : #include "random.h"
23 : : #include "util.h"
24 : : #include "openvswitch/vlog.h"
25 : :
26 : 53956 : VLOG_DEFINE_THIS_MODULE(hmap);
27 : :
28 : 774190 : COVERAGE_DEFINE(hmap_pathological);
29 : 52990636 : COVERAGE_DEFINE(hmap_expand);
30 : 155068 : COVERAGE_DEFINE(hmap_shrink);
31 : 142582 : COVERAGE_DEFINE(hmap_reserve);
32 : :
33 : : /* Initializes 'hmap' as an empty hash table. */
34 : : void
35 : 25535328 : hmap_init(struct hmap *hmap)
36 : : {
37 : 25535328 : hmap->buckets = &hmap->one;
38 : 25535328 : hmap->one = NULL;
39 : 25535328 : hmap->mask = 0;
40 : 25535328 : hmap->n = 0;
41 : 25535328 : }
42 : :
43 : : /* Frees memory reserved by 'hmap'. It is the client's responsibility to free
44 : : * the nodes themselves, if necessary. */
45 : : void
46 : 24385081 : hmap_destroy(struct hmap *hmap)
47 : : {
48 [ + - ][ + + ]: 24385081 : if (hmap && hmap->buckets != &hmap->one) {
49 : 8757358 : free(hmap->buckets);
50 : : }
51 : 24385081 : }
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 did before. If 'hmap' will likely have fewer elements than
58 : : * before, use hmap_destroy() followed by hmap_init() to save memory and
59 : : * iteration time. */
60 : : void
61 : 0 : hmap_clear(struct hmap *hmap)
62 : : {
63 [ # # ]: 0 : if (hmap->n > 0) {
64 : 0 : hmap->n = 0;
65 : 0 : memset(hmap->buckets, 0, (hmap->mask + 1) * sizeof *hmap->buckets);
66 : : }
67 : 0 : }
68 : :
69 : : /* Exchanges hash maps 'a' and 'b'. */
70 : : void
71 : 8840466 : hmap_swap(struct hmap *a, struct hmap *b)
72 : : {
73 : 8840466 : struct hmap tmp = *a;
74 : 8840466 : *a = *b;
75 : 8840466 : *b = tmp;
76 : 8840466 : hmap_moved(a);
77 : 8840466 : hmap_moved(b);
78 : 8840466 : }
79 : :
80 : : /* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
81 : : * to realloc()). */
82 : : void
83 : 17687501 : hmap_moved(struct hmap *hmap)
84 : : {
85 [ + + ]: 17687501 : if (!hmap->mask) {
86 : 8136515 : hmap->buckets = &hmap->one;
87 : : }
88 : 17687501 : }
89 : :
90 : : static void
91 : 8810360 : resize(struct hmap *hmap, size_t new_mask, const char *where)
92 : : {
93 : : struct hmap tmp;
94 : : size_t i;
95 : :
96 [ - + ]: 8810360 : ovs_assert(is_pow2(new_mask + 1));
97 : :
98 : 8810360 : hmap_init(&tmp);
99 [ + + ]: 8810360 : if (new_mask) {
100 : 8808477 : tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
101 : 8808477 : tmp.mask = new_mask;
102 [ + + ]: 62721705 : for (i = 0; i <= tmp.mask; i++) {
103 : 53913228 : tmp.buckets[i] = NULL;
104 : : }
105 : : }
106 [ + + ]: 27710469 : for (i = 0; i <= hmap->mask; i++) {
107 : : struct hmap_node *node, *next;
108 : 18900109 : int count = 0;
109 [ + + ]: 56678835 : for (node = hmap->buckets[i]; node; node = next) {
110 : 37778726 : next = node->next;
111 : 37778726 : hmap_insert_fast(&tmp, node, node->hash);
112 : 37778726 : count++;
113 : : }
114 [ + + ]: 18900109 : if (count > 5) {
115 : : static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(10, 10);
116 : 105358 : COVERAGE_INC(hmap_pathological);
117 [ + + ]: 105358 : VLOG_DBG_RL(&rl, "%s: %d nodes in bucket (%"PRIuSIZE" nodes, %"PRIuSIZE" buckets)",
118 : : where, count, hmap->n, hmap->mask + 1);
119 : : }
120 : : }
121 : 8810360 : hmap_swap(hmap, &tmp);
122 : 8810360 : hmap_destroy(&tmp);
123 : 8810360 : }
124 : :
125 : : static size_t
126 : 8831684 : calc_mask(size_t capacity)
127 : : {
128 : 8831684 : size_t mask = capacity / 2;
129 : 8831684 : mask |= mask >> 1;
130 : 8831684 : mask |= mask >> 2;
131 : 8831684 : mask |= mask >> 4;
132 : 8831684 : mask |= mask >> 8;
133 : 8831684 : mask |= mask >> 16;
134 : : #if SIZE_MAX > UINT32_MAX
135 : 8831684 : 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 : 8831684 : mask |= (mask & 1) << 1;
141 : :
142 : 8831684 : 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 : 8808099 : hmap_expand_at(struct hmap *hmap, const char *where)
152 : : {
153 : 8808099 : size_t new_mask = calc_mask(hmap->n);
154 [ + - ]: 8808099 : if (new_mask > hmap->mask) {
155 : 8808099 : COVERAGE_INC(hmap_expand);
156 : 8808099 : resize(hmap, new_mask, where);
157 : : }
158 : 8808099 : }
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 : 23489 : hmap_shrink_at(struct hmap *hmap, const char *where)
167 : : {
168 : 23489 : size_t new_mask = calc_mask(hmap->n);
169 [ + + ]: 23489 : if (new_mask < hmap->mask) {
170 : 2171 : COVERAGE_INC(hmap_shrink);
171 : 2171 : resize(hmap, new_mask, where);
172 : : }
173 : 23489 : }
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 : 96 : hmap_reserve_at(struct hmap *hmap, size_t n, const char *where)
184 : : {
185 : 96 : size_t new_mask = calc_mask(n);
186 [ + + ]: 96 : if (new_mask > hmap->mask) {
187 : 90 : COVERAGE_INC(hmap_reserve);
188 : 90 : resize(hmap, new_mask, where);
189 : : }
190 : 96 : }
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 : 0 : hmap_node_moved(struct hmap *hmap,
196 : : struct hmap_node *old_node, struct hmap_node *node)
197 : : {
198 : 0 : struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
199 [ # # ]: 0 : while (*bucket != old_node) {
200 : 0 : bucket = &(*bucket)->next;
201 : : }
202 : 0 : *bucket = node;
203 : 0 : }
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 : 7936 : 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 (;;) {
218 : 30408 : bucket = hmap->buckets[random_uint32() & hmap->mask];
219 [ + + ]: 30408 : if (bucket) {
220 : 7936 : break;
221 : : }
222 : 22472 : }
223 : :
224 : : /* Count nodes in bucket. */
225 : 7936 : n = 0;
226 [ + + ]: 23172 : for (node = bucket; node; node = node->next) {
227 : 15236 : n++;
228 : : }
229 : :
230 : : /* Choose random node from bucket. */
231 : 7936 : i = random_range(n);
232 [ + + ]: 11509 : for (node = bucket; i-- > 0; node = node->next) {
233 : 3573 : continue;
234 : : }
235 : 7936 : return node;
236 : : }
237 : :
238 : : /* Returns the next node in 'hmap' in hash order, or NULL if no nodes remain in
239 : : * 'hmap'. Uses '*pos' to determine where to begin iteration, and updates
240 : : * '*pos' to pass on the next iteration into them before returning.
241 : : *
242 : : * It's better to use plain HMAP_FOR_EACH and related functions, since they are
243 : : * faster and better at dealing with hmaps that change during iteration.
244 : : *
245 : : * Before beginning iteration, set '*pos' to all zeros. */
246 : : struct hmap_node *
247 : 53320 : hmap_at_position(const struct hmap *hmap,
248 : : struct hmap_position *pos)
249 : : {
250 : : size_t offset;
251 : : size_t b_idx;
252 : :
253 : 53320 : offset = pos->offset;
254 [ + + ]: 72113 : for (b_idx = pos->bucket; b_idx <= hmap->mask; b_idx++) {
255 : : struct hmap_node *node;
256 : : size_t n_idx;
257 : :
258 [ + + ]: 73203 : for (n_idx = 0, node = hmap->buckets[b_idx]; node != NULL;
259 : 16821 : n_idx++, node = node->next) {
260 [ + + ]: 54410 : if (n_idx == offset) {
261 [ + + ]: 37589 : if (node->next) {
262 : 12244 : pos->bucket = node->hash & hmap->mask;
263 : 12244 : pos->offset = offset + 1;
264 : : } else {
265 : 25345 : pos->bucket = (node->hash & hmap->mask) + 1;
266 : 25345 : pos->offset = 0;
267 : : }
268 : 37589 : return node;
269 : : }
270 : : }
271 : 18793 : offset = 0;
272 : : }
273 : :
274 : 15731 : pos->bucket = 0;
275 : 15731 : pos->offset = 0;
276 : 15731 : return NULL;
277 : : }
278 : :
279 : : /* Returns true if 'node' is in 'hmap', false otherwise. */
280 : : bool
281 : 0 : hmap_contains(const struct hmap *hmap, const struct hmap_node *node)
282 : : {
283 : : struct hmap_node *p;
284 : :
285 [ # # ]: 0 : for (p = hmap_first_in_bucket(hmap, node->hash); p; p = p->next) {
286 [ # # ]: 0 : if (p == node) {
287 : 0 : return true;
288 : : }
289 : : }
290 : :
291 : 0 : return false;
292 : : }
|
