Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 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 "hindex.h"
19 : : #include "coverage.h"
20 : :
21 : : static bool hindex_node_is_body(const struct hindex_node *);
22 : : static bool hindex_node_is_head(const struct hindex_node *);
23 : : static void hindex_resize(struct hindex *, size_t new_mask);
24 : : static size_t hindex_calc_mask(size_t capacity);
25 : :
26 : 72938 : COVERAGE_DEFINE(hindex_pathological);
27 : 169022 : COVERAGE_DEFINE(hindex_expand);
28 : 75998 : COVERAGE_DEFINE(hindex_shrink);
29 : 74198 : COVERAGE_DEFINE(hindex_reserve);
30 : :
31 : : /* Initializes 'hindex' as an empty hash index. */
32 : : void
33 : 32043 : hindex_init(struct hindex *hindex)
34 : : {
35 : 32043 : hindex->buckets = &hindex->one;
36 : 32043 : hindex->one = NULL;
37 : 32043 : hindex->mask = 0;
38 : 32043 : hindex->n_unique = 0;
39 : 32043 : }
40 : :
41 : : /* Frees memory reserved by 'hindex'. It is the client's responsibility to
42 : : * free the nodes themselves, if necessary. */
43 : : void
44 : 31417 : hindex_destroy(struct hindex *hindex)
45 : : {
46 [ + - ][ + + ]: 31417 : if (hindex && hindex->buckets != &hindex->one) {
47 : 16488 : free(hindex->buckets);
48 : : }
49 : 31417 : }
50 : :
51 : : /* Removes all node from 'hindex', leaving it ready to accept more nodes. Does
52 : : * not free memory allocated for 'hindex'.
53 : : *
54 : : * This function is appropriate when 'hindex' will soon have about as many
55 : : * elements as it before. If 'hindex' will likely have fewer elements than
56 : : * before, use hindex_destroy() followed by hindex_clear() to save memory and
57 : : * iteration time. */
58 : : void
59 : 0 : hindex_clear(struct hindex *hindex)
60 : : {
61 [ # # ]: 0 : if (hindex->n_unique > 0) {
62 : 0 : hindex->n_unique = 0;
63 : 0 : memset(hindex->buckets, 0,
64 : 0 : (hindex->mask + 1) * sizeof *hindex->buckets);
65 : : }
66 : 0 : }
67 : :
68 : : /* Exchanges hash indexes 'a' and 'b'. */
69 : : void
70 : 16734 : hindex_swap(struct hindex *a, struct hindex *b)
71 : : {
72 : 16734 : struct hindex tmp = *a;
73 : 16734 : *a = *b;
74 : 16734 : *b = tmp;
75 : 16734 : hindex_moved(a);
76 : 16734 : hindex_moved(b);
77 : 16734 : }
78 : :
79 : : /* Adjusts 'hindex' to compensate for having moved position in memory (e.g. due
80 : : * to realloc()). */
81 : : void
82 : 33468 : hindex_moved(struct hindex *hindex)
83 : : {
84 [ + + ]: 33468 : if (!hindex->mask) {
85 : 12740 : hindex->buckets = &hindex->one;
86 : : }
87 : 33468 : }
88 : :
89 : : /* Expands 'hindex', if necessary, to optimize the performance of searches. */
90 : : void
91 : 16014 : hindex_expand(struct hindex *hindex)
92 : : {
93 : 16014 : size_t new_mask = hindex_calc_mask(hindex->n_unique);
94 [ + - ]: 16014 : if (new_mask > hindex->mask) {
95 : 16014 : COVERAGE_INC(hindex_expand);
96 : 16014 : hindex_resize(hindex, new_mask);
97 : : }
98 : 16014 : }
99 : :
100 : : /* Shrinks 'hindex', if necessary, to optimize the performance of iteration. */
101 : : void
102 : 7168 : hindex_shrink(struct hindex *hindex)
103 : : {
104 : 7168 : size_t new_mask = hindex_calc_mask(hindex->n_unique);
105 [ + + ]: 7168 : if (new_mask < hindex->mask) {
106 : 510 : COVERAGE_INC(hindex_shrink);
107 : 510 : hindex_resize(hindex, new_mask);
108 : : }
109 : 7168 : }
110 : :
111 : : /* Expands 'hindex', if necessary, to optimize the performance of searches when
112 : : * it has up to 'n' unique hashes. (But iteration will be slow in a hash index
113 : : * whose allocated capacity is much higher than its current number of
114 : : * nodes.) */
115 : : void
116 : 224 : hindex_reserve(struct hindex *hindex, size_t n)
117 : : {
118 : 224 : size_t new_mask = hindex_calc_mask(n);
119 [ + + ]: 224 : if (new_mask > hindex->mask) {
120 : 210 : COVERAGE_INC(hindex_reserve);
121 : 210 : hindex_resize(hindex, new_mask);
122 : : }
123 : 224 : }
124 : :
125 : : /* Inserts 'node', with the given 'hash', into 'hindex'. Never automatically
126 : : * expands 'hindex' (use hindex_insert() instead if you want that). */
127 : : void
128 : 168337 : hindex_insert_fast(struct hindex *hindex,
129 : : struct hindex_node *node, size_t hash)
130 : : {
131 : 168337 : struct hindex_node *head = hindex_node_with_hash(hindex, hash);
132 [ + + ]: 168337 : if (head) {
133 : : /* 'head' is an existing head with hash == 'hash'.
134 : : * Insert 'node' as a body node just below 'head'. */
135 : 99342 : node->s = head->s;
136 : 99342 : node->d = head;
137 [ + + ]: 99342 : if (node->s) {
138 : 70538 : node->s->d = node;
139 : : }
140 : 99342 : head->s = node;
141 : : } else {
142 : : /* No existing node has hash 'hash'. Insert 'node' as a new head in
143 : : * its bucket. */
144 : 68995 : struct hindex_node **bucket = &hindex->buckets[hash & hindex->mask];
145 : 68995 : node->s = NULL;
146 : 68995 : node->d = *bucket;
147 : 68995 : *bucket = node;
148 : 68995 : hindex->n_unique++;
149 : : }
150 : 168337 : node->hash = hash;
151 : 168337 : }
152 : :
153 : : /* Inserts 'node', with the given 'hash', into 'hindex', and expands 'hindex'
154 : : * if necessary to optimize search performance. */
155 : : void
156 : 168337 : hindex_insert(struct hindex *hindex, struct hindex_node *node, size_t hash)
157 : : {
158 : 168337 : hindex_insert_fast(hindex, node, hash);
159 [ + + ]: 168337 : if (hindex->n_unique / 2 > hindex->mask) {
160 : 16014 : hindex_expand(hindex);
161 : : }
162 : 168337 : }
163 : :
164 : : /* Removes 'node' from 'hindex'. Does not shrink the hash index; call
165 : : * hindex_shrink() directly if desired. */
166 : : void
167 : 103818 : hindex_remove(struct hindex *hindex, struct hindex_node *node)
168 : : {
169 [ + + ]: 103818 : if (!hindex_node_is_head(node)) {
170 : 49138 : node->d->s = node->s;
171 [ + + ]: 49138 : if (node->s) {
172 : 49138 : node->s->d = node->d;
173 : : }
174 : : } else {
175 : : struct hindex_node **head;
176 : :
177 [ + + ]: 67944 : for (head = &hindex->buckets[node->hash & hindex->mask];
178 : 67944 : (*head)->hash != node->hash;
179 : 13264 : head = &(*head)->d)
180 : : {
181 : 13264 : continue;
182 : : }
183 : :
184 [ + + ]: 54680 : if (node->s) {
185 : 27981 : *head = node->s;
186 : 27981 : node->s->d = node->d;
187 : : } else {
188 : 26699 : *head = node->d;
189 : 26699 : hindex->n_unique--;
190 : : }
191 : : }
192 : 103818 : }
193 : :
194 : : /* Helper functions. */
195 : :
196 : : /* Returns true if 'node', which must be inserted into an hindex, is a "body"
197 : : * node, that is, it is not reachable from a bucket by following zero or more
198 : : * 'd' pointers. Returns false otherwise. */
199 : : static bool
200 : 103818 : hindex_node_is_body(const struct hindex_node *node)
201 : : {
202 [ + + ][ + + ]: 103818 : return node->d && node->d->hash == node->hash;
203 : : }
204 : :
205 : : /* Returns true if 'node', which must be inserted into an hindex, is a "head"
206 : : * node, that is, if it is reachable from a bucket by following zero or more
207 : : * 'd' pointers. Returns false if 'node' is a body node (and therefore one
208 : : * must follow at least one 's' pointer to reach it). */
209 : : static bool
210 : 103818 : hindex_node_is_head(const struct hindex_node *node)
211 : : {
212 : 103818 : return !hindex_node_is_body(node);
213 : : }
214 : :
215 : : /* Reallocates 'hindex''s array of buckets to use bitwise mask 'new_mask'. */
216 : : static void
217 : 16734 : hindex_resize(struct hindex *hindex, size_t new_mask)
218 : : {
219 : : struct hindex tmp;
220 : : size_t i;
221 : :
222 [ - + ]: 16734 : ovs_assert(is_pow2(new_mask + 1));
223 [ - + ]: 16734 : ovs_assert(new_mask != SIZE_MAX);
224 : :
225 : 16734 : hindex_init(&tmp);
226 [ + + ]: 16734 : if (new_mask) {
227 : 16512 : tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
228 : 16512 : tmp.mask = new_mask;
229 [ + + ]: 101944 : for (i = 0; i <= tmp.mask; i++) {
230 : 85432 : tmp.buckets[i] = NULL;
231 : : }
232 : : }
233 [ + + ]: 51036 : for (i = 0; i <= hindex->mask; i++) {
234 : : struct hindex_node *node, *next;
235 : : int count;
236 : :
237 : 34302 : count = 0;
238 [ + + ]: 94460 : for (node = hindex->buckets[i]; node; node = next) {
239 : 60158 : struct hindex_node **head = &tmp.buckets[node->hash & tmp.mask];
240 : :
241 : 60158 : next = node->d;
242 : 60158 : node->d = *head;
243 : 60158 : *head = node;
244 : 60158 : count++;
245 : : }
246 [ - + ]: 34302 : if (count > 5) {
247 : 0 : COVERAGE_INC(hindex_pathological);
248 : : }
249 : : }
250 : 16734 : tmp.n_unique = hindex->n_unique;
251 : 16734 : hindex_swap(hindex, &tmp);
252 : 16734 : hindex_destroy(&tmp);
253 : 16734 : }
254 : :
255 : : /* Returns the bitwise mask to use in struct hindex to support 'capacity'
256 : : * hindex_nodes with unique hashes. */
257 : : static size_t
258 : 23406 : hindex_calc_mask(size_t capacity)
259 : : {
260 : 23406 : size_t mask = capacity / 2;
261 : 23406 : mask |= mask >> 1;
262 : 23406 : mask |= mask >> 2;
263 : 23406 : mask |= mask >> 4;
264 : 23406 : mask |= mask >> 8;
265 : 23406 : mask |= mask >> 16;
266 : : #if SIZE_MAX > UINT32_MAX
267 : 23406 : mask |= mask >> 32;
268 : : #endif
269 : :
270 : : /* If we need to dynamically allocate buckets we might as well allocate at
271 : : * least 4 of them. */
272 : 23406 : mask |= (mask & 1) << 1;
273 : :
274 : 23406 : return mask;
275 : : }
276 : :
277 : : /* Returns the head node in 'hindex' with the given 'hash'. 'hindex' must
278 : : * contain a head node with the given hash. */
279 : : static struct hindex_node *
280 : 665460 : hindex_head_node(const struct hindex *hindex, size_t hash)
281 : : {
282 : 665460 : struct hindex_node *node = hindex->buckets[hash & hindex->mask];
283 : :
284 [ + + ]: 920108 : while (node->hash != hash) {
285 : 254648 : node = node->d;
286 : : }
287 : 665460 : return node;
288 : : }
289 : :
290 : : static struct hindex_node *
291 : 647903 : hindex_next__(const struct hindex *hindex, size_t start)
292 : : {
293 : : size_t i;
294 [ + + ]: 968398 : for (i = start; i <= hindex->mask; i++) {
295 : 809295 : struct hindex_node *node = hindex->buckets[i];
296 [ + + ]: 809295 : if (node) {
297 : 488800 : return node;
298 : : }
299 : : }
300 : 159103 : return NULL;
301 : : }
302 : :
303 : : /* Returns the first node in 'hindex', in arbitrary order, or a null pointer if
304 : : * 'hindex' is empty. */
305 : : struct hindex_node *
306 : 159103 : hindex_first(const struct hindex *hindex)
307 : : {
308 : 159103 : return hindex_next__(hindex, 0);
309 : : }
310 : :
311 : : /* Returns the next node in 'hindex' following 'node', in arbitrary order, or a
312 : : * null pointer if 'node' is the last node in 'hindex'.
313 : : *
314 : : * If the hash index has been reallocated since 'node' was visited, some nodes
315 : : * may be skipped or visited twice. */
316 : : struct hindex_node *
317 : 1288539 : hindex_next(const struct hindex *hindex, const struct hindex_node *node)
318 : : {
319 : : struct hindex_node *head;
320 : :
321 : : /* If there's a node with the same hash, return it. */
322 [ + + ]: 1288539 : if (node->s) {
323 : 623079 : return node->s;
324 : : }
325 : :
326 : : /* If there's another node in the same bucket, return it. */
327 : 665460 : head = hindex_head_node(hindex, node->hash);
328 [ + + ]: 665460 : if (head->d) {
329 : 176660 : return head->d;
330 : : }
331 : :
332 : : /* Return the first node in the next (or later) bucket. */
333 : 488800 : return hindex_next__(hindex, (node->hash & hindex->mask) + 1);
334 : : }
|
