1 /**************************************************************************
3 * Copyright 2007 VMware, Inc.
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:
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
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.
26 **************************************************************************/
30 * Zack Rusin <zackr@vmware.com>
33 #include "util/u_debug.h"
34 #include "util/u_memory.h"
39 #define MAX(a, b) ((a > b) ? (a) : (b))
42 static const int MinNumBits
= 4;
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
49 static int primeForNumBits(int numBits
)
51 return (1 << numBits
) + prime_deltas
[numBits
];
55 Returns the smallest integer n such that
56 primeForNumBits(n) >= hint.
58 static int countBits(int hint
)
68 if (numBits
>= (int)sizeof(prime_deltas
)) {
69 numBits
= sizeof(prime_deltas
) - 1;
70 } else if (primeForNumBits(numBits
) < hint
) {
77 struct cso_node
*next
;
82 struct cso_hash_data
{
83 struct cso_node
*fakeNext
;
84 struct cso_node
**buckets
;
94 struct cso_hash_data
*d
;
99 static void *cso_data_allocate_node(struct cso_hash_data
*hash
)
101 return MALLOC(hash
->nodeSize
);
104 static void cso_free_node(struct cso_node
*node
)
109 static struct cso_node
*
110 cso_hash_create_node(struct cso_hash
*hash
,
111 unsigned akey
, void *avalue
,
112 struct cso_node
**anextNode
)
114 struct cso_node
*node
= cso_data_allocate_node(hash
->data
.d
);
120 node
->value
= avalue
;
122 node
->next
= (struct cso_node
*)(*anextNode
);
124 ++hash
->data
.d
->size
;
128 static void cso_data_rehash(struct cso_hash_data
*hash
, int hint
)
131 hint
= countBits(-hint
);
132 if (hint
< MinNumBits
)
134 hash
->userNumBits
= (short)hint
;
135 while (primeForNumBits(hint
) < (hash
->size
>> 1))
137 } else if (hint
< MinNumBits
) {
141 if (hash
->numBits
!= hint
) {
142 struct cso_node
*e
= (struct cso_node
*)(hash
);
143 struct cso_node
**oldBuckets
= hash
->buckets
;
144 int oldNumBuckets
= hash
->numBuckets
;
147 hash
->numBits
= (short)hint
;
148 hash
->numBuckets
= primeForNumBits(hint
);
149 hash
->buckets
= MALLOC(sizeof(struct cso_node
*) * hash
->numBuckets
);
150 for (i
= 0; i
< hash
->numBuckets
; ++i
)
151 hash
->buckets
[i
] = e
;
153 for (i
= 0; i
< oldNumBuckets
; ++i
) {
154 struct cso_node
*firstNode
= oldBuckets
[i
];
155 while (firstNode
!= e
) {
156 unsigned h
= firstNode
->key
;
157 struct cso_node
*lastNode
= firstNode
;
158 struct cso_node
*afterLastNode
;
159 struct cso_node
**beforeFirstNode
;
161 while (lastNode
->next
!= e
&& lastNode
->next
->key
== h
)
162 lastNode
= lastNode
->next
;
164 afterLastNode
= lastNode
->next
;
165 beforeFirstNode
= &hash
->buckets
[h
% hash
->numBuckets
];
166 while (*beforeFirstNode
!= e
)
167 beforeFirstNode
= &(*beforeFirstNode
)->next
;
168 lastNode
->next
= *beforeFirstNode
;
169 *beforeFirstNode
= firstNode
;
170 firstNode
= afterLastNode
;
177 static void cso_data_might_grow(struct cso_hash_data
*hash
)
179 if (hash
->size
>= hash
->numBuckets
)
180 cso_data_rehash(hash
, hash
->numBits
+ 1);
183 static void cso_data_has_shrunk(struct cso_hash_data
*hash
)
185 if (hash
->size
<= (hash
->numBuckets
>> 3) &&
186 hash
->numBits
> hash
->userNumBits
) {
187 int max
= MAX(hash
->numBits
-2, hash
->userNumBits
);
188 cso_data_rehash(hash
, max
);
192 static struct cso_node
*cso_data_first_node(struct cso_hash_data
*hash
)
194 struct cso_node
*e
= (struct cso_node
*)(hash
);
195 struct cso_node
**bucket
= hash
->buckets
;
196 int n
= hash
->numBuckets
;
205 static struct cso_node
**cso_hash_find_node(struct cso_hash
*hash
, unsigned akey
)
207 struct cso_node
**node
;
209 if (hash
->data
.d
->numBuckets
) {
210 node
= (struct cso_node
**)(&hash
->data
.d
->buckets
[akey
% hash
->data
.d
->numBuckets
]);
211 assert(*node
== hash
->data
.e
|| (*node
)->next
);
212 while (*node
!= hash
->data
.e
&& (*node
)->key
!= akey
)
213 node
= &(*node
)->next
;
215 node
= (struct cso_node
**)((const struct cso_node
* const *)(&hash
->data
.e
));
220 struct cso_hash_iter
cso_hash_insert(struct cso_hash
*hash
,
221 unsigned key
, void *data
)
223 cso_data_might_grow(hash
->data
.d
);
226 struct cso_node
**nextNode
= cso_hash_find_node(hash
, key
);
227 struct cso_node
*node
= cso_hash_create_node(hash
, key
, data
, nextNode
);
229 struct cso_hash_iter null_iter
= {hash
, 0};
234 struct cso_hash_iter iter
= {hash
, node
};
240 struct cso_hash
* cso_hash_create(void)
242 struct cso_hash
*hash
= MALLOC_STRUCT(cso_hash
);
246 hash
->data
.d
= MALLOC_STRUCT(cso_hash_data
);
252 hash
->data
.d
->fakeNext
= 0;
253 hash
->data
.d
->buckets
= 0;
254 hash
->data
.d
->size
= 0;
255 hash
->data
.d
->nodeSize
= sizeof(struct cso_node
);
256 hash
->data
.d
->userNumBits
= (short)MinNumBits
;
257 hash
->data
.d
->numBits
= 0;
258 hash
->data
.d
->numBuckets
= 0;
263 void cso_hash_delete(struct cso_hash
*hash
)
265 struct cso_node
*e_for_x
= (struct cso_node
*)(hash
->data
.d
);
266 struct cso_node
**bucket
= (struct cso_node
**)(hash
->data
.d
->buckets
);
267 int n
= hash
->data
.d
->numBuckets
;
269 struct cso_node
*cur
= *bucket
++;
270 while (cur
!= e_for_x
) {
271 struct cso_node
*next
= cur
->next
;
276 FREE(hash
->data
.d
->buckets
);
281 struct cso_hash_iter
cso_hash_find(struct cso_hash
*hash
,
284 struct cso_node
**nextNode
= cso_hash_find_node(hash
, key
);
285 struct cso_hash_iter iter
= {hash
, *nextNode
};
289 unsigned cso_hash_iter_key(struct cso_hash_iter iter
)
291 if (!iter
.node
|| iter
.hash
->data
.e
== iter
.node
)
293 return iter
.node
->key
;
296 void * cso_hash_iter_data(struct cso_hash_iter iter
)
298 if (!iter
.node
|| iter
.hash
->data
.e
== iter
.node
)
300 return iter
.node
->value
;
303 static struct cso_node
*cso_hash_data_next(struct cso_node
*node
)
306 struct cso_node
*next
;
308 struct cso_hash_data
*d
;
311 struct cso_node
**bucket
;
316 debug_printf("iterating beyond the last element\n");
322 start
= (node
->key
% a
.d
->numBuckets
) + 1;
323 bucket
= a
.d
->buckets
+ start
;
324 n
= a
.d
->numBuckets
- start
;
334 static struct cso_node
*cso_hash_data_prev(struct cso_node
*node
)
338 struct cso_hash_data
*d
;
341 struct cso_node
*sentinel
;
342 struct cso_node
**bucket
;
349 start
= a
.d
->numBuckets
- 1;
351 start
= node
->key
% a
.d
->numBuckets
;
354 bucket
= a
.d
->buckets
+ start
;
356 if (*bucket
!= sentinel
) {
357 struct cso_node
*prev
= *bucket
;
358 while (prev
->next
!= sentinel
)
367 debug_printf("iterating backward beyond first element\n");
371 struct cso_hash_iter
cso_hash_iter_next(struct cso_hash_iter iter
)
373 struct cso_hash_iter next
= {iter
.hash
, cso_hash_data_next(iter
.node
)};
377 int cso_hash_iter_is_null(struct cso_hash_iter iter
)
379 if (!iter
.node
|| iter
.node
== iter
.hash
->data
.e
)
384 void * cso_hash_take(struct cso_hash
*hash
,
387 struct cso_node
**node
= cso_hash_find_node(hash
, akey
);
388 if (*node
!= hash
->data
.e
) {
389 void *t
= (*node
)->value
;
390 struct cso_node
*next
= (*node
)->next
;
391 cso_free_node(*node
);
393 --hash
->data
.d
->size
;
394 cso_data_has_shrunk(hash
->data
.d
);
400 struct cso_hash_iter
cso_hash_iter_prev(struct cso_hash_iter iter
)
402 struct cso_hash_iter prev
= {iter
.hash
,
403 cso_hash_data_prev(iter
.node
)};
407 struct cso_hash_iter
cso_hash_first_node(struct cso_hash
*hash
)
409 struct cso_hash_iter iter
= {hash
, cso_data_first_node(hash
->data
.d
)};
413 int cso_hash_size(struct cso_hash
*hash
)
415 return hash
->data
.d
->size
;
418 struct cso_hash_iter
cso_hash_erase(struct cso_hash
*hash
, struct cso_hash_iter iter
)
420 struct cso_hash_iter ret
= iter
;
421 struct cso_node
*node
= iter
.node
;
422 struct cso_node
**node_ptr
;
424 if (node
== hash
->data
.e
)
427 ret
= cso_hash_iter_next(ret
);
428 node_ptr
= (struct cso_node
**)(&hash
->data
.d
->buckets
[node
->key
% hash
->data
.d
->numBuckets
]);
429 while (*node_ptr
!= node
)
430 node_ptr
= &(*node_ptr
)->next
;
431 *node_ptr
= node
->next
;
433 --hash
->data
.d
->size
;
437 boolean
cso_hash_contains(struct cso_hash
*hash
, unsigned key
)
439 struct cso_node
**node
= cso_hash_find_node(hash
, key
);
440 return (*node
!= hash
->data
.e
);