]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/hindex.c
2 * Copyright (c) 2013 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
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
);
26 COVERAGE_DEFINE(hindex_pathological
);
27 COVERAGE_DEFINE(hindex_expand
);
28 COVERAGE_DEFINE(hindex_shrink
);
29 COVERAGE_DEFINE(hindex_reserve
);
31 /* Initializes 'hindex' as an empty hash index. */
33 hindex_init(struct hindex
*hindex
)
35 hindex
->buckets
= &hindex
->one
;
41 /* Frees memory reserved by 'hindex'. It is the client's responsibility to
42 * free the nodes themselves, if necessary. */
44 hindex_destroy(struct hindex
*hindex
)
46 if (hindex
&& hindex
->buckets
!= &hindex
->one
) {
47 free(hindex
->buckets
);
51 /* Removes all node from 'hindex', leaving it ready to accept more nodes. Does
52 * not free memory allocated for 'hindex'.
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
59 hindex_clear(struct hindex
*hindex
)
61 if (hindex
->n_unique
> 0) {
63 memset(hindex
->buckets
, 0,
64 (hindex
->mask
+ 1) * sizeof *hindex
->buckets
);
68 /* Exchanges hash indexes 'a' and 'b'. */
70 hindex_swap(struct hindex
*a
, struct hindex
*b
)
72 struct hindex tmp
= *a
;
79 /* Adjusts 'hindex' to compensate for having moved position in memory (e.g. due
82 hindex_moved(struct hindex
*hindex
)
85 hindex
->buckets
= &hindex
->one
;
89 /* Expands 'hindex', if necessary, to optimize the performance of searches. */
91 hindex_expand(struct hindex
*hindex
)
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
);
100 /* Shrinks 'hindex', if necessary, to optimize the performance of iteration. */
102 hindex_shrink(struct hindex
*hindex
)
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
);
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
116 hindex_reserve(struct hindex
*hindex
, size_t n
)
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
);
125 /* Inserts 'node', with the given 'hash', into 'hindex'. Never automatically
126 * expands 'hindex' (use hindex_insert() instead if you want that). */
128 hindex_insert_fast(struct hindex
*hindex
,
129 struct hindex_node
*node
, size_t hash
)
131 struct hindex_node
*head
= hindex_node_with_hash(hindex
, hash
);
133 /* 'head' is an existing head with hash == 'hash'.
134 * Insert 'node' as a body node just below 'head'. */
142 /* No existing node has hash 'hash'. Insert 'node' as a new head in
144 struct hindex_node
**bucket
= &hindex
->buckets
[hash
& hindex
->mask
];
153 /* Inserts 'node', with the given 'hash', into 'hindex', and expands 'hindex'
154 * if necessary to optimize search performance. */
156 hindex_insert(struct hindex
*hindex
, struct hindex_node
*node
, size_t hash
)
158 hindex_insert_fast(hindex
, node
, hash
);
159 if (hindex
->n_unique
/ 2 > hindex
->mask
) {
160 hindex_expand(hindex
);
164 /* Removes 'node' from 'hindex'. Does not shrink the hash index; call
165 * hindex_shrink() directly if desired. */
167 hindex_remove(struct hindex
*hindex
, struct hindex_node
*node
)
169 if (!hindex_node_is_head(node
)) {
170 node
->d
->s
= node
->s
;
172 node
->s
->d
= node
->d
;
175 struct hindex_node
**head
;
177 for (head
= &hindex
->buckets
[node
->hash
& hindex
->mask
];
178 (*head
)->hash
!= node
->hash
;
186 node
->s
->d
= node
->d
;
194 /* Helper functions. */
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. */
200 hindex_node_is_body(const struct hindex_node
*node
)
202 return node
->d
&& node
->d
->hash
== node
->hash
;
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). */
210 hindex_node_is_head(const struct hindex_node
*node
)
212 return !hindex_node_is_body(node
);
215 /* Reallocates 'hindex''s array of buckets to use bitwise mask 'new_mask'. */
217 hindex_resize(struct hindex
*hindex
, size_t new_mask
)
222 ovs_assert(is_pow2(new_mask
+ 1));
223 ovs_assert(new_mask
!= SIZE_MAX
);
227 tmp
.buckets
= xmalloc(sizeof *tmp
.buckets
* (new_mask
+ 1));
229 for (i
= 0; i
<= tmp
.mask
; i
++) {
230 tmp
.buckets
[i
] = NULL
;
233 for (i
= 0; i
<= hindex
->mask
; i
++) {
234 struct hindex_node
*node
, *next
;
238 for (node
= hindex
->buckets
[i
]; node
; node
= next
) {
239 struct hindex_node
**head
= &tmp
.buckets
[node
->hash
& tmp
.mask
];
247 COVERAGE_INC(hindex_pathological
);
250 tmp
.n_unique
= hindex
->n_unique
;
251 hindex_swap(hindex
, &tmp
);
252 hindex_destroy(&tmp
);
255 /* Returns the bitwise mask to use in struct hindex to support 'capacity'
256 * hindex_nodes with unique hashes. */
258 hindex_calc_mask(size_t capacity
)
260 size_t mask
= capacity
/ 2;
266 #if SIZE_MAX > UINT32_MAX
270 /* If we need to dynamically allocate buckets we might as well allocate at
271 * least 4 of them. */
272 mask
|= (mask
& 1) << 1;
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 hindex_head_node(const struct hindex
*hindex
, size_t hash
)
282 struct hindex_node
*node
= hindex
->buckets
[hash
& hindex
->mask
];
284 while (node
->hash
!= hash
) {
290 static struct hindex_node
*
291 hindex_next__(const struct hindex
*hindex
, size_t start
)
294 for (i
= start
; i
<= hindex
->mask
; i
++) {
295 struct hindex_node
*node
= hindex
->buckets
[i
];
303 /* Returns the first node in 'hindex', in arbitrary order, or a null pointer if
304 * 'hindex' is empty. */
306 hindex_first(const struct hindex
*hindex
)
308 return hindex_next__(hindex
, 0);
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'.
314 * If the hash index has been reallocated since 'node' was visited, some nodes
315 * may be skipped or visited twice. */
317 hindex_next(const struct hindex
*hindex
, const struct hindex_node
*node
)
319 struct hindex_node
*head
;
321 /* If there's a node with the same hash, return it. */
326 /* If there's another node in the same bucket, return it. */
327 head
= hindex_head_node(hindex
, node
->hash
);
332 /* Return the first node in the next (or later) bucket. */
333 return hindex_next__(hindex
, (node
->hash
& hindex
->mask
) + 1);