2 * Copyright (c) 2008, 2009, 2010 Nicira Networks.
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.
26 /* Initializes 'hmap' as an empty hash table. */
28 hmap_init(struct hmap *hmap)
30 hmap->buckets = &hmap->one;
36 /* Frees memory reserved by 'hmap'. It is the client's responsibility to free
37 * the nodes themselves, if necessary. */
39 hmap_destroy(struct hmap *hmap)
41 if (hmap && hmap->buckets != &hmap->one) {
46 /* Removes all node from 'hmap', leaving it ready to accept more nodes. Does
47 * not free memory allocated for 'hmap'.
49 * This function is appropriate when 'hmap' will soon have about as many
50 * elements as it before. If 'hmap' will likely have fewer elements than
51 * before, use hmap_destroy() followed by hmap_clear() to save memory and
54 hmap_clear(struct hmap *hmap)
58 memset(hmap->buckets, 0, (hmap->mask + 1) * sizeof *hmap->buckets);
62 /* Exchanges hash maps 'a' and 'b'. */
64 hmap_swap(struct hmap *a, struct hmap *b)
73 /* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
76 hmap_moved(struct hmap *hmap)
79 hmap->buckets = &hmap->one;
84 resize(struct hmap *hmap, size_t new_mask)
89 assert(!(new_mask & (new_mask + 1)));
90 assert(new_mask != SIZE_MAX);
94 tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
96 for (i = 0; i <= tmp.mask; i++) {
97 tmp.buckets[i] = NULL;
100 for (i = 0; i <= hmap->mask; i++) {
101 struct hmap_node *node, *next;
103 for (node = hmap->buckets[i]; node; node = next) {
105 hmap_insert_fast(&tmp, node, node->hash);
109 COVERAGE_INC(hmap_pathological);
112 hmap_swap(hmap, &tmp);
117 calc_mask(size_t capacity)
119 size_t mask = capacity / 2;
125 #if SIZE_MAX > UINT32_MAX
129 /* If we need to dynamically allocate buckets we might as well allocate at
130 * least 4 of them. */
131 mask |= (mask & 1) << 1;
136 /* Expands 'hmap', if necessary, to optimize the performance of searches. */
138 hmap_expand(struct hmap *hmap)
140 size_t new_mask = calc_mask(hmap->n);
141 if (new_mask > hmap->mask) {
142 COVERAGE_INC(hmap_expand);
143 resize(hmap, new_mask);
147 /* Shrinks 'hmap', if necessary, to optimize the performance of iteration. */
149 hmap_shrink(struct hmap *hmap)
151 size_t new_mask = calc_mask(hmap->n);
152 if (new_mask < hmap->mask) {
153 COVERAGE_INC(hmap_shrink);
154 resize(hmap, new_mask);
158 /* Expands 'hmap', if necessary, to optimize the performance of searches when
159 * it has up to 'n' elements. (But iteration will be slow in a hash map whose
160 * allocated capacity is much higher than its current number of nodes.) */
162 hmap_reserve(struct hmap *hmap, size_t n)
164 size_t new_mask = calc_mask(n);
165 if (new_mask > hmap->mask) {
166 COVERAGE_INC(hmap_reserve);
167 resize(hmap, new_mask);
171 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
172 * to 'node' (e.g. due to realloc()). */
174 hmap_node_moved(struct hmap *hmap,
175 struct hmap_node *old_node, struct hmap_node *node)
177 struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
178 while (*bucket != old_node) {
179 bucket = &(*bucket)->next;
184 /* Chooses and returns a randomly selected node from 'hmap', which must not be
187 * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
188 * But it does at least ensure that any node in 'hmap' can be chosen. */
190 hmap_random_node(const struct hmap *hmap)
192 struct hmap_node *bucket, *node;
195 /* Choose a random non-empty bucket. */
196 for (i = random_uint32(); ; i++) {
197 bucket = hmap->buckets[i & hmap->mask];
203 /* Count nodes in bucket. */
205 for (node = bucket; node; node = node->next) {
209 /* Choose random node from bucket. */
211 for (node = bucket; i-- > 0; node = node->next) {