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 <zackr@vmware.com>
31 */
32
33 #include "util/u_debug.h"
34 #include "util/u_memory.h"
35
36 #include "cso_hash.h"
37
38 #ifndef MAX
39 #define MAX(a, b) ((a > b) ? (a) : (b))
40 #endif
41
42 static const int MinNumBits = 4;
43
44 static const unsigned char prime_deltas[] = {
45 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3,
46 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0
47 };
48
primeForNumBits(int numBits)49 static int primeForNumBits(int numBits)
50 {
51 return (1 << numBits) + prime_deltas[numBits];
52 }
53
54 /*
55 Returns the smallest integer n such that
56 primeForNumBits(n) >= hint.
57 */
countBits(int hint)58 static int countBits(int hint)
59 {
60 int numBits = 0;
61 int bits = hint;
62
63 while (bits > 1) {
64 bits >>= 1;
65 numBits++;
66 }
67
68 if (numBits >= (int)sizeof(prime_deltas)) {
69 numBits = sizeof(prime_deltas) - 1;
70 } else if (primeForNumBits(numBits) < hint) {
71 ++numBits;
72 }
73 return numBits;
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
cso_data_rehash(struct cso_hash * hash,int hint)95 static void cso_data_rehash(struct cso_hash *hash, int hint)
96 {
97 if (hint < 0) {
98 hint = countBits(-hint);
99 if (hint < MinNumBits)
100 hint = MinNumBits;
101 hash->userNumBits = (short)hint;
102 while (primeForNumBits(hint) < (hash->size >> 1))
103 ++hint;
104 } else if (hint < MinNumBits) {
105 hint = MinNumBits;
106 }
107
108 if (hash->numBits != hint) {
109 struct cso_node *e = (struct cso_node *)hash;
110 struct cso_node **oldBuckets = hash->buckets;
111 int oldNumBuckets = hash->numBuckets;
112 int i = 0;
113
114 hash->numBits = (short)hint;
115 hash->numBuckets = primeForNumBits(hint);
116 hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
117 for (i = 0; i < hash->numBuckets; ++i)
118 hash->buckets[i] = e;
119
120 for (i = 0; i < oldNumBuckets; ++i) {
121 struct cso_node *firstNode = oldBuckets[i];
122 while (firstNode != e) {
123 unsigned h = firstNode->key;
124 struct cso_node *lastNode = firstNode;
125 struct cso_node *afterLastNode;
126 struct cso_node **beforeFirstNode;
127
128 while (lastNode->next != e && lastNode->next->key == h)
129 lastNode = lastNode->next;
130
131 afterLastNode = lastNode->next;
132 beforeFirstNode = &hash->buckets[h % hash->numBuckets];
133 while (*beforeFirstNode != e)
134 beforeFirstNode = &(*beforeFirstNode)->next;
135 lastNode->next = *beforeFirstNode;
136 *beforeFirstNode = firstNode;
137 firstNode = afterLastNode;
138 }
139 }
140 FREE(oldBuckets);
141 }
142 }
143
cso_data_might_grow(struct cso_hash * hash)144 static void cso_data_might_grow(struct cso_hash *hash)
145 {
146 if (hash->size >= hash->numBuckets)
147 cso_data_rehash(hash, hash->numBits + 1);
148 }
149
cso_data_has_shrunk(struct cso_hash * hash)150 static void cso_data_has_shrunk(struct cso_hash *hash)
151 {
152 if (hash->size <= (hash->numBuckets >> 3) &&
153 hash->numBits > hash->userNumBits) {
154 int max = MAX(hash->numBits-2, hash->userNumBits);
155 cso_data_rehash(hash, max);
156 }
157 }
158
cso_data_first_node(struct cso_hash * hash)159 static struct cso_node *cso_data_first_node(struct cso_hash *hash)
160 {
161 struct cso_node *e = (struct cso_node *)hash;
162 struct cso_node **bucket = hash->buckets;
163 int n = hash->numBuckets;
164
165 while (n--) {
166 if (*bucket != e)
167 return *bucket;
168 ++bucket;
169 }
170 return e;
171 }
172
cso_hash_insert(struct cso_hash * hash,unsigned key,void * data)173 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
174 unsigned key, void *data)
175 {
176 cso_data_might_grow(hash);
177
178 struct cso_node **nextNode = cso_hash_find_node(hash, key);
179 struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
180 if (!node) {
181 struct cso_hash_iter null_iter = {hash, 0};
182 return null_iter;
183 }
184
185 struct cso_hash_iter iter = {hash, node};
186 return iter;
187 }
188
cso_hash_init(struct cso_hash * hash)189 void cso_hash_init(struct cso_hash *hash)
190 {
191 hash->fakeNext = 0;
192 hash->buckets = 0;
193 hash->size = 0;
194 hash->userNumBits = (short)MinNumBits;
195 hash->numBits = 0;
196 hash->numBuckets = 0;
197 hash->end = (struct cso_node*)hash;
198 }
199
cso_hash_deinit(struct cso_hash * hash)200 void cso_hash_deinit(struct cso_hash *hash)
201 {
202 struct cso_node *e_for_x = hash->end;
203 struct cso_node **bucket = hash->buckets;
204 int n = hash->numBuckets;
205
206 while (n--) {
207 struct cso_node *cur = *bucket++;
208 while (cur != e_for_x) {
209 struct cso_node *next = cur->next;
210 FREE(cur);
211 cur = next;
212 }
213 }
214 FREE(hash->buckets);
215 }
216
cso_hash_iter_key(struct cso_hash_iter iter)217 unsigned cso_hash_iter_key(struct cso_hash_iter iter)
218 {
219 if (!iter.node || iter.hash->end == iter.node)
220 return 0;
221 return iter.node->key;
222 }
223
cso_hash_data_next(struct cso_node * node)224 struct cso_node *cso_hash_data_next(struct cso_node *node)
225 {
226 union {
227 struct cso_node *next;
228 struct cso_node *e;
229 struct cso_hash *d;
230 } a;
231 int start;
232 struct cso_node **bucket;
233 int n;
234
235 a.next = node->next;
236 if (!a.next) {
237 debug_printf("iterating beyond the last element\n");
238 return NULL;
239 }
240 if (a.next->next)
241 return a.next;
242
243 start = (node->key % a.d->numBuckets) + 1;
244 bucket = a.d->buckets + start;
245 n = a.d->numBuckets - start;
246 while (n--) {
247 if (*bucket != a.e)
248 return *bucket;
249 ++bucket;
250 }
251 return a.e;
252 }
253
254
cso_hash_data_prev(struct cso_node * node)255 static struct cso_node *cso_hash_data_prev(struct cso_node *node)
256 {
257 union {
258 struct cso_node *e;
259 struct cso_hash *d;
260 } a;
261 int start;
262 struct cso_node *sentinel;
263 struct cso_node **bucket;
264
265 a.e = node;
266 while (a.e->next)
267 a.e = a.e->next;
268
269 if (node == a.e)
270 start = a.d->numBuckets - 1;
271 else
272 start = node->key % a.d->numBuckets;
273
274 sentinel = node;
275 bucket = a.d->buckets + start;
276 while (start >= 0) {
277 if (*bucket != sentinel) {
278 struct cso_node *prev = *bucket;
279 while (prev->next != sentinel)
280 prev = prev->next;
281 return prev;
282 }
283
284 sentinel = a.e;
285 --bucket;
286 --start;
287 }
288 debug_printf("iterating backward beyond first element\n");
289 return a.e;
290 }
291
cso_hash_take(struct cso_hash * hash,unsigned akey)292 void *cso_hash_take(struct cso_hash *hash, unsigned akey)
293 {
294 struct cso_node **node = cso_hash_find_node(hash, akey);
295
296 if (*node != hash->end) {
297 void *t = (*node)->value;
298 struct cso_node *next = (*node)->next;
299 FREE(*node);
300 *node = next;
301 --hash->size;
302 cso_data_has_shrunk(hash);
303 return t;
304 }
305 return NULL;
306 }
307
cso_hash_iter_prev(struct cso_hash_iter iter)308 struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter)
309 {
310 struct cso_hash_iter prev = {iter.hash,
311 cso_hash_data_prev(iter.node)};
312 return prev;
313 }
314
cso_hash_first_node(struct cso_hash * hash)315 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
316 {
317 struct cso_hash_iter iter = {hash, cso_data_first_node(hash)};
318 return iter;
319 }
320
cso_hash_size(struct cso_hash * hash)321 int cso_hash_size(struct cso_hash *hash)
322 {
323 return hash->size;
324 }
325
cso_hash_erase(struct cso_hash * hash,struct cso_hash_iter iter)326 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
327 {
328 struct cso_hash_iter ret = iter;
329 struct cso_node *node = iter.node;
330 struct cso_node **node_ptr;
331
332 if (node == hash->end)
333 return iter;
334
335 ret = cso_hash_iter_next(ret);
336 node_ptr = &hash->buckets[node->key % hash->numBuckets];
337 while (*node_ptr != node)
338 node_ptr = &(*node_ptr)->next;
339 *node_ptr = node->next;
340 FREE(node);
341 --hash->size;
342 return ret;
343 }
344
cso_hash_contains(struct cso_hash * hash,unsigned key)345 bool cso_hash_contains(struct cso_hash *hash, unsigned key)
346 {
347 struct cso_node **node = cso_hash_find_node(hash, key);
348 return *node != hash->end;
349 }
350