1 /**************************************************************************
2 *
3 * Copyright 2007 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28 /*
29 * Authors:
30 * Zack Rusin <[email protected]>
31 */
32
33 #include "util/u_debug.h"
34 #include "util/u_memory.h"
35 #include "util/bitscan.h"
36
37 #include "cso_hash.h"
38
39 #ifndef MAX
40 #define MAX(a, b) ((a > b) ? (a) : (b))
41 #endif
42
43 static const int MinNumBits = 4;
44
45 static const unsigned char prime_deltas[] = {
46 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
47 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
48 };
49
50
51 static int
primeForNumBits(int numBits)52 primeForNumBits(int numBits)
53 {
54 return (1 << numBits) + prime_deltas[numBits];
55 }
56
57
58 /*
59 * Returns the smallest integer n such that
60 * primeForNumBits(n) >= hint.
61 */
62 static int
countBits(int hint)63 countBits(int hint)
64 {
65 int numBits = util_bitcount(hint);
66
67 if (numBits >= (int)sizeof(prime_deltas)) {
68 numBits = sizeof(prime_deltas) - 1;
69 } else if (primeForNumBits(numBits) < hint) {
70 ++numBits;
71 }
72 return numBits;
73 }
74
75
76 static struct cso_node *
cso_hash_create_node(struct cso_hash * hash,unsigned akey,void * avalue,struct cso_node ** anextNode)77 cso_hash_create_node(struct cso_hash *hash,
78 unsigned akey, void *avalue,
79 struct cso_node **anextNode)
80 {
81 struct cso_node *node = MALLOC(sizeof(struct cso_node));
82
83 if (!node)
84 return NULL;
85
86 node->key = akey;
87 node->value = avalue;
88
89 node->next = *anextNode;
90 *anextNode = node;
91 ++hash->size;
92 return node;
93 }
94
95
96 static void
cso_data_rehash(struct cso_hash * hash,int hint)97 cso_data_rehash(struct cso_hash *hash, int hint)
98 {
99 if (hint < 0) {
100 hint = countBits(-hint);
101 if (hint < MinNumBits)
102 hint = MinNumBits;
103 hash->userNumBits = (short)hint;
104 while (primeForNumBits(hint) < (hash->size >> 1))
105 ++hint;
106 } else if (hint < MinNumBits) {
107 hint = MinNumBits;
108 }
109
110 if (hash->numBits != hint) {
111 struct cso_node *e = (struct cso_node *)hash;
112 struct cso_node **oldBuckets = hash->buckets;
113 const int oldNumBuckets = hash->numBuckets;
114
115 hash->numBits = (short)hint;
116 hash->numBuckets = primeForNumBits(hint);
117 hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
118 for (int i = 0; i < hash->numBuckets; ++i)
119 hash->buckets[i] = e;
120
121 for (int i = 0; i < oldNumBuckets; ++i) {
122 struct cso_node *firstNode = oldBuckets[i];
123 while (firstNode != e) {
124 unsigned h = firstNode->key;
125 struct cso_node *lastNode = firstNode;
126 struct cso_node *afterLastNode;
127 struct cso_node **beforeFirstNode;
128
129 while (lastNode->next != e && lastNode->next->key == h)
130 lastNode = lastNode->next;
131
132 afterLastNode = lastNode->next;
133 beforeFirstNode = &hash->buckets[h % hash->numBuckets];
134 while (*beforeFirstNode != e)
135 beforeFirstNode = &(*beforeFirstNode)->next;
136 lastNode->next = *beforeFirstNode;
137 *beforeFirstNode = firstNode;
138 firstNode = afterLastNode;
139 }
140 }
141 FREE(oldBuckets);
142 }
143 }
144
145
146 static void
cso_data_might_grow(struct cso_hash * hash)147 cso_data_might_grow(struct cso_hash *hash)
148 {
149 if (hash->size >= hash->numBuckets)
150 cso_data_rehash(hash, hash->numBits + 1);
151 }
152
153
154 static void
cso_data_has_shrunk(struct cso_hash * hash)155 cso_data_has_shrunk(struct cso_hash *hash)
156 {
157 if (hash->size <= (hash->numBuckets >> 3) &&
158 hash->numBits > hash->userNumBits) {
159 int max = MAX(hash->numBits-2, hash->userNumBits);
160 cso_data_rehash(hash, max);
161 }
162 }
163
164
165 static struct cso_node *
cso_data_first_node(struct cso_hash * hash)166 cso_data_first_node(struct cso_hash *hash)
167 {
168 struct cso_node *e = (struct cso_node *)hash;
169 struct cso_node **bucket = hash->buckets;
170 int n = hash->numBuckets;
171
172 while (n--) {
173 if (*bucket != e)
174 return *bucket;
175 ++bucket;
176 }
177 return e;
178 }
179
180
181 struct cso_hash_iter
cso_hash_insert(struct cso_hash * hash,unsigned key,void * data)182 cso_hash_insert(struct cso_hash *hash, unsigned key, void *data)
183 {
184 cso_data_might_grow(hash);
185
186 struct cso_node **nextNode = cso_hash_find_node(hash, key);
187 struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
188 if (!node) {
189 struct cso_hash_iter null_iter = {hash, NULL};
190 return null_iter;
191 }
192
193 struct cso_hash_iter iter = {hash, node};
194 return iter;
195 }
196
197
198 void
cso_hash_init(struct cso_hash * hash)199 cso_hash_init(struct cso_hash *hash)
200 {
201 hash->fakeNext = NULL;
202 hash->buckets = NULL;
203 hash->size = 0;
204 hash->userNumBits = (short)MinNumBits;
205 hash->numBits = 0;
206 hash->numBuckets = 0;
207 hash->end = (struct cso_node*)hash;
208 }
209
210
211 void
cso_hash_deinit(struct cso_hash * hash)212 cso_hash_deinit(struct cso_hash *hash)
213 {
214 struct cso_node *e_for_x = hash->end;
215 struct cso_node **bucket = hash->buckets;
216 int n = hash->numBuckets;
217
218 while (n--) {
219 struct cso_node *cur = *bucket++;
220 while (cur != e_for_x) {
221 struct cso_node *next = cur->next;
222 FREE(cur);
223 cur = next;
224 }
225 }
226 FREE(hash->buckets);
227 }
228
229
230 unsigned
cso_hash_iter_key(struct cso_hash_iter iter)231 cso_hash_iter_key(struct cso_hash_iter iter)
232 {
233 if (!iter.node || iter.hash->end == iter.node)
234 return 0;
235 return iter.node->key;
236 }
237
238
239 struct cso_node *
cso_hash_data_next(struct cso_node * node)240 cso_hash_data_next(struct cso_node *node)
241 {
242 union {
243 struct cso_node *next;
244 struct cso_node *e;
245 struct cso_hash *d;
246 } a;
247
248 a.next = node->next;
249 if (!a.next) {
250 debug_printf("iterating beyond the last element\n");
251 return NULL;
252 }
253 if (a.next->next)
254 return a.next;
255
256 int start = (node->key % a.d->numBuckets) + 1;
257 struct cso_node **bucket = a.d->buckets + start;
258 int n = a.d->numBuckets - start;
259 while (n--) {
260 if (*bucket != a.e)
261 return *bucket;
262 ++bucket;
263 }
264 return a.e;
265 }
266
267
268 void *
cso_hash_take(struct cso_hash * hash,unsigned akey)269 cso_hash_take(struct cso_hash *hash, unsigned akey)
270 {
271 struct cso_node **node = cso_hash_find_node(hash, akey);
272
273 if (*node != hash->end) {
274 void *t = (*node)->value;
275 struct cso_node *next = (*node)->next;
276 FREE(*node);
277 *node = next;
278 --hash->size;
279 cso_data_has_shrunk(hash);
280 return t;
281 }
282 return NULL;
283 }
284
285
286 struct cso_hash_iter
cso_hash_first_node(struct cso_hash * hash)287 cso_hash_first_node(struct cso_hash *hash)
288 {
289 struct cso_hash_iter iter = {hash, cso_data_first_node(hash)};
290 return iter;
291 }
292
293
294 int
cso_hash_size(const struct cso_hash * hash)295 cso_hash_size(const struct cso_hash *hash)
296 {
297 return hash->size;
298 }
299
300
301 struct cso_hash_iter
cso_hash_erase(struct cso_hash * hash,struct cso_hash_iter iter)302 cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
303 {
304 struct cso_hash_iter ret = iter;
305 struct cso_node *node = iter.node;
306 struct cso_node **node_ptr;
307
308 if (node == hash->end)
309 return iter;
310
311 ret = cso_hash_iter_next(ret);
312 node_ptr = &hash->buckets[node->key % hash->numBuckets];
313 while (*node_ptr != node)
314 node_ptr = &(*node_ptr)->next;
315 *node_ptr = node->next;
316 FREE(node);
317 --hash->size;
318 return ret;
319 }
320
321
322 bool
cso_hash_contains(struct cso_hash * hash,unsigned key)323 cso_hash_contains(struct cso_hash *hash, unsigned key)
324 {
325 struct cso_node **node = cso_hash_find_node(hash, key);
326 return *node != hash->end;
327 }
328