ofp-util: Fix a typo in ofputil_decode_ofp11_port
[sliver-openvswitch.git] / lib / hindex.c
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 COVERAGE_DEFINE(hindex_pathological);
27 COVERAGE_DEFINE(hindex_expand);
28 COVERAGE_DEFINE(hindex_shrink);
29 COVERAGE_DEFINE(hindex_reserve);
30
31 /* Initializes 'hindex' as an empty hash index. */
32 void
33 hindex_init(struct hindex *hindex)
34 {
35     hindex->buckets = &hindex->one;
36     hindex->one = NULL;
37     hindex->mask = 0;
38     hindex->n_unique = 0;
39 }
40
41 /* Frees memory reserved by 'hindex'.  It is the client's responsibility to
42  * free the nodes themselves, if necessary. */
43 void
44 hindex_destroy(struct hindex *hindex)
45 {
46     if (hindex && hindex->buckets != &hindex->one) {
47         free(hindex->buckets);
48     }
49 }
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 hindex_clear(struct hindex *hindex)
60 {
61     if (hindex->n_unique > 0) {
62         hindex->n_unique = 0;
63         memset(hindex->buckets, 0,
64                (hindex->mask + 1) * sizeof *hindex->buckets);
65     }
66 }
67
68 /* Exchanges hash indexes 'a' and 'b'. */
69 void
70 hindex_swap(struct hindex *a, struct hindex *b)
71 {
72     struct hindex tmp = *a;
73     *a = *b;
74     *b = tmp;
75     hindex_moved(a);
76     hindex_moved(b);
77 }
78
79 /* Adjusts 'hindex' to compensate for having moved position in memory (e.g. due
80  * to realloc()). */
81 void
82 hindex_moved(struct hindex *hindex)
83 {
84     if (!hindex->mask) {
85         hindex->buckets = &hindex->one;
86     }
87 }
88
89 /* Expands 'hindex', if necessary, to optimize the performance of searches. */
90 void
91 hindex_expand(struct hindex *hindex)
92 {
93     size_t new_mask = hindex_calc_mask(hindex->n_unique);
94     if (new_mask > hindex->mask) {
95         COVERAGE_INC(hindex_expand);
96         hindex_resize(hindex, new_mask);
97     }
98 }
99
100 /* Shrinks 'hindex', if necessary, to optimize the performance of iteration. */
101 void
102 hindex_shrink(struct hindex *hindex)
103 {
104     size_t new_mask = hindex_calc_mask(hindex->n_unique);
105     if (new_mask < hindex->mask) {
106         COVERAGE_INC(hindex_shrink);
107         hindex_resize(hindex, new_mask);
108     }
109 }
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 hindex_reserve(struct hindex *hindex, size_t n)
117 {
118     size_t new_mask = hindex_calc_mask(n);
119     if (new_mask > hindex->mask) {
120         COVERAGE_INC(hindex_reserve);
121         hindex_resize(hindex, new_mask);
122     }
123 }
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 hindex_insert_fast(struct hindex *hindex,
129                    struct hindex_node *node, size_t hash)
130 {
131     struct hindex_node *head = hindex_node_with_hash(hindex, hash);
132     if (head) {
133         /* 'head' is an existing head with hash == 'hash'.
134          * Insert 'node' as a body node just below 'head'. */
135         node->s = head->s;
136         node->d = head;
137         if (node->s) {
138             node->s->d = node;
139         }
140         head->s = node;
141     } else {
142         /* No existing node has hash 'hash'.  Insert 'node' as a new head in
143          * its bucket. */
144         struct hindex_node **bucket = &hindex->buckets[hash & hindex->mask];
145         node->s = NULL;
146         node->d = *bucket;
147         *bucket = node;
148         hindex->n_unique++;
149     }
150     node->hash = hash;
151 }
152
153 /* Inserts 'node', with the given 'hash', into 'hindex', and expands 'hindex'
154  * if necessary to optimize search performance. */
155 void
156 hindex_insert(struct hindex *hindex, struct hindex_node *node, size_t hash)
157 {
158     hindex_insert_fast(hindex, node, hash);
159     if (hindex->n_unique / 2 > hindex->mask) {
160         hindex_expand(hindex);
161     }
162 }
163
164 /* Removes 'node' from 'hindex'.  Does not shrink the hash index; call
165  * hindex_shrink() directly if desired. */
166 void
167 hindex_remove(struct hindex *hindex, struct hindex_node *node)
168 {
169     if (!hindex_node_is_head(node)) {
170         node->d->s = node->s;
171         if (node->s) {
172             node->s->d = node->d;
173         }
174     } else {
175         struct hindex_node **head;
176
177         for (head = &hindex->buckets[node->hash & hindex->mask];
178              (*head)->hash != node->hash;
179              head = &(*head)->d)
180         {
181             continue;
182         }
183
184         if (node->s) {
185             *head = node->s;
186             node->s->d = node->d;
187         } else {
188             *head = node->d;
189             hindex->n_unique--;
190         }
191     }
192 }
193 \f
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 hindex_node_is_body(const struct hindex_node *node)
201 {
202     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 hindex_node_is_head(const struct hindex_node *node)
211 {
212     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 hindex_resize(struct hindex *hindex, size_t new_mask)
218 {
219     struct hindex tmp;
220     size_t i;
221
222     ovs_assert(is_pow2(new_mask + 1));
223     ovs_assert(new_mask != SIZE_MAX);
224
225     hindex_init(&tmp);
226     if (new_mask) {
227         tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
228         tmp.mask = new_mask;
229         for (i = 0; i <= tmp.mask; i++) {
230             tmp.buckets[i] = NULL;
231         }
232     }
233     for (i = 0; i <= hindex->mask; i++) {
234         struct hindex_node *node, *next;
235         int count;
236
237         count = 0;
238         for (node = hindex->buckets[i]; node; node = next) {
239             struct hindex_node **head = &tmp.buckets[node->hash & tmp.mask];
240
241             next = node->d;
242             node->d = *head;
243             *head = node;
244             count++;
245         }
246         if (count > 5) {
247             COVERAGE_INC(hindex_pathological);
248         }
249     }
250     tmp.n_unique = hindex->n_unique;
251     hindex_swap(hindex, &tmp);
252     hindex_destroy(&tmp);
253 }
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 hindex_calc_mask(size_t capacity)
259 {
260     size_t mask = capacity / 2;
261     mask |= mask >> 1;
262     mask |= mask >> 2;
263     mask |= mask >> 4;
264     mask |= mask >> 8;
265     mask |= mask >> 16;
266 #if SIZE_MAX > UINT32_MAX
267     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     mask |= (mask & 1) << 1;
273
274     return mask;
275 }
276
277 /* Returns the head node in 'hindex' with the given 'hash', or a null pointer
278  * if no nodes have that hash value. */
279 struct hindex_node *
280 hindex_node_with_hash(const struct hindex *hindex, size_t hash)
281 {
282     struct hindex_node *node = hindex->buckets[hash & hindex->mask];
283
284     while (node && node->hash != hash) {
285         node = node->d;
286     }
287     return node;
288 }
289
290 /* Returns the head node in 'hindex' with the given 'hash'.  'hindex' must
291  * contain a head node with the given hash. */
292 static struct hindex_node *
293 hindex_head_node(const struct hindex *hindex, size_t hash)
294 {
295     struct hindex_node *node = hindex->buckets[hash & hindex->mask];
296
297     while (node->hash != hash) {
298         node = node->d;
299     }
300     return node;
301 }
302
303 static struct hindex_node *
304 hindex_next__(const struct hindex *hindex, size_t start)
305 {
306     size_t i;
307     for (i = start; i <= hindex->mask; i++) {
308         struct hindex_node *node = hindex->buckets[i];
309         if (node) {
310             return node;
311         }
312     }
313     return NULL;
314 }
315
316 /* Returns the first node in 'hindex', in arbitrary order, or a null pointer if
317  * 'hindex' is empty. */
318 struct hindex_node *
319 hindex_first(const struct hindex *hindex)
320 {
321     return hindex_next__(hindex, 0);
322 }
323
324 /* Returns the next node in 'hindex' following 'node', in arbitrary order, or a
325  * null pointer if 'node' is the last node in 'hindex'.
326  *
327  * If the hash index has been reallocated since 'node' was visited, some nodes
328  * may be skipped or visited twice. */
329 struct hindex_node *
330 hindex_next(const struct hindex *hindex, const struct hindex_node *node)
331 {
332     struct hindex_node *head;
333
334     /* If there's a node with the same hash, return it. */
335     if (node->s) {
336         return node->s;
337     }
338
339     /* If there's another node in the same bucket, return it. */
340     head = hindex_head_node(hindex, node->hash);
341     if (head->d) {
342         return head->d;
343     }
344
345     /* Return the first node in the next (or later) bucket. */
346     return hindex_next__(hindex, (node->hash & hindex->mask) + 1);
347 }