e42f1feb9b50894cd368075fcc5457ad5097f881
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
) {
76 static struct cso_node
*
77 cso_hash_create_node(struct cso_hash
*hash
,
78 unsigned akey
, void *avalue
,
79 struct cso_node
**anextNode
)
81 struct cso_node
*node
= MALLOC(sizeof(struct cso_node
));
89 node
->next
= *anextNode
;
95 static void cso_data_rehash(struct cso_hash_data
*hash
, int hint
)
98 hint
= countBits(-hint
);
99 if (hint
< MinNumBits
)
101 hash
->userNumBits
= (short)hint
;
102 while (primeForNumBits(hint
) < (hash
->size
>> 1))
104 } else if (hint
< MinNumBits
) {
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
;
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
;
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
;
128 while (lastNode
->next
!= e
&& lastNode
->next
->key
== h
)
129 lastNode
= lastNode
->next
;
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
;
144 static void cso_data_might_grow(struct cso_hash_data
*hash
)
146 if (hash
->size
>= hash
->numBuckets
)
147 cso_data_rehash(hash
, hash
->numBits
+ 1);
150 static void cso_data_has_shrunk(struct cso_hash_data
*hash
)
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
);
159 static struct cso_node
*cso_data_first_node(struct cso_hash_data
*hash
)
161 struct cso_node
*e
= (struct cso_node
*)hash
;
162 struct cso_node
**bucket
= hash
->buckets
;
163 int n
= hash
->numBuckets
;
173 struct cso_hash_iter
cso_hash_insert(struct cso_hash
*hash
,
174 unsigned key
, void *data
)
176 cso_data_might_grow(hash
->data
.d
);
178 struct cso_node
**nextNode
= cso_hash_find_node(hash
, key
);
179 struct cso_node
*node
= cso_hash_create_node(hash
, key
, data
, nextNode
);
181 struct cso_hash_iter null_iter
= {hash
, 0};
185 struct cso_hash_iter iter
= {hash
, node
};
189 bool cso_hash_init(struct cso_hash
*hash
)
191 hash
->data
.d
= MALLOC_STRUCT(cso_hash_data
);
195 hash
->data
.d
->fakeNext
= 0;
196 hash
->data
.d
->buckets
= 0;
197 hash
->data
.d
->size
= 0;
198 hash
->data
.d
->userNumBits
= (short)MinNumBits
;
199 hash
->data
.d
->numBits
= 0;
200 hash
->data
.d
->numBuckets
= 0;
204 void cso_hash_deinit(struct cso_hash
*hash
)
206 struct cso_node
*e_for_x
= (struct cso_node
*)hash
->data
.d
;
207 struct cso_node
**bucket
= hash
->data
.d
->buckets
;
208 int n
= hash
->data
.d
->numBuckets
;
211 struct cso_node
*cur
= *bucket
++;
212 while (cur
!= e_for_x
) {
213 struct cso_node
*next
= cur
->next
;
218 FREE(hash
->data
.d
->buckets
);
223 unsigned cso_hash_iter_key(struct cso_hash_iter iter
)
225 if (!iter
.node
|| iter
.hash
->data
.e
== iter
.node
)
227 return iter
.node
->key
;
230 struct cso_node
*cso_hash_data_next(struct cso_node
*node
)
233 struct cso_node
*next
;
235 struct cso_hash_data
*d
;
238 struct cso_node
**bucket
;
243 debug_printf("iterating beyond the last element\n");
249 start
= (node
->key
% a
.d
->numBuckets
) + 1;
250 bucket
= a
.d
->buckets
+ start
;
251 n
= a
.d
->numBuckets
- start
;
261 static struct cso_node
*cso_hash_data_prev(struct cso_node
*node
)
265 struct cso_hash_data
*d
;
268 struct cso_node
*sentinel
;
269 struct cso_node
**bucket
;
276 start
= a
.d
->numBuckets
- 1;
278 start
= node
->key
% a
.d
->numBuckets
;
281 bucket
= a
.d
->buckets
+ start
;
283 if (*bucket
!= sentinel
) {
284 struct cso_node
*prev
= *bucket
;
285 while (prev
->next
!= sentinel
)
294 debug_printf("iterating backward beyond first element\n");
298 void *cso_hash_take(struct cso_hash
*hash
, unsigned akey
)
300 struct cso_node
**node
= cso_hash_find_node(hash
, akey
);
302 if (*node
!= hash
->data
.e
) {
303 void *t
= (*node
)->value
;
304 struct cso_node
*next
= (*node
)->next
;
307 --hash
->data
.d
->size
;
308 cso_data_has_shrunk(hash
->data
.d
);
314 struct cso_hash_iter
cso_hash_iter_prev(struct cso_hash_iter iter
)
316 struct cso_hash_iter prev
= {iter
.hash
,
317 cso_hash_data_prev(iter
.node
)};
321 struct cso_hash_iter
cso_hash_first_node(struct cso_hash
*hash
)
323 struct cso_hash_iter iter
= {hash
, cso_data_first_node(hash
->data
.d
)};
327 int cso_hash_size(struct cso_hash
*hash
)
329 return hash
->data
.d
->size
;
332 struct cso_hash_iter
cso_hash_erase(struct cso_hash
*hash
, struct cso_hash_iter iter
)
334 struct cso_hash_iter ret
= iter
;
335 struct cso_node
*node
= iter
.node
;
336 struct cso_node
**node_ptr
;
338 if (node
== hash
->data
.e
)
341 ret
= cso_hash_iter_next(ret
);
342 node_ptr
= &hash
->data
.d
->buckets
[node
->key
% hash
->data
.d
->numBuckets
];
343 while (*node_ptr
!= node
)
344 node_ptr
= &(*node_ptr
)->next
;
345 *node_ptr
= node
->next
;
347 --hash
->data
.d
->size
;
351 bool cso_hash_contains(struct cso_hash
*hash
, unsigned key
)
353 struct cso_node
**node
= cso_hash_find_node(hash
, key
);
354 return *node
!= hash
->data
.e
;