0338cb3b4748a0883a2664da0e4f7a6b06e8e936
1 /**************************************************************************
3 * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas.
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 TUNGSTEN GRAPHICS 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 <zack@tungstengraphics.com>
40 #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_data_free_node(struct cso_node
*node
)
106 /* XXX still a leak here.
107 * Need to cast value ptr to original cso type, then free the
108 * driver-specific data hanging off of it. For example:
109 struct cso_sampler *csamp = (struct cso_sampler *) node->value;
116 static struct cso_node
*
117 cso_hash_create_node(struct cso_hash
*hash
,
118 unsigned akey
, void *avalue
,
119 struct cso_node
**anextNode
)
121 struct cso_node
*node
= cso_data_allocate_node(hash
->data
.d
);
123 node
->value
= avalue
;
125 node
->next
= (struct cso_node
*)(*anextNode
);
127 ++hash
->data
.d
->size
;
131 static void cso_data_rehash(struct cso_hash_data
*hash
, int hint
)
134 hint
= countBits(-hint
);
135 if (hint
< MinNumBits
)
137 hash
->userNumBits
= hint
;
138 while (primeForNumBits(hint
) < (hash
->size
>> 1))
140 } else if (hint
< MinNumBits
) {
144 if (hash
->numBits
!= hint
) {
145 struct cso_node
*e
= (struct cso_node
*)(hash
);
146 struct cso_node
**oldBuckets
= hash
->buckets
;
147 int oldNumBuckets
= hash
->numBuckets
;
150 hash
->numBits
= hint
;
151 hash
->numBuckets
= primeForNumBits(hint
);
152 hash
->buckets
= malloc(sizeof(struct cso_node
*) * hash
->numBuckets
);
153 for (i
= 0; i
< hash
->numBuckets
; ++i
)
154 hash
->buckets
[i
] = e
;
156 for (i
= 0; i
< oldNumBuckets
; ++i
) {
157 struct cso_node
*firstNode
= oldBuckets
[i
];
158 while (firstNode
!= e
) {
159 unsigned h
= firstNode
->key
;
160 struct cso_node
*lastNode
= firstNode
;
161 while (lastNode
->next
!= e
&& lastNode
->next
->key
== h
)
162 lastNode
= lastNode
->next
;
164 struct cso_node
*afterLastNode
= lastNode
->next
;
165 struct cso_node
**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
);
225 struct cso_node
**nextNode
= cso_hash_find_node(hash
, key
);
226 struct cso_node
*node
= cso_hash_create_node(hash
, key
, data
, nextNode
);
227 struct cso_hash_iter iter
= {hash
, node
};
231 struct cso_hash
* cso_hash_create(void)
233 struct cso_hash
*hash
= malloc(sizeof(struct cso_hash
));
234 hash
->data
.d
= malloc(sizeof(struct cso_hash_data
));
235 hash
->data
.d
->fakeNext
= 0;
236 hash
->data
.d
->buckets
= 0;
237 hash
->data
.d
->size
= 0;
238 hash
->data
.d
->nodeSize
= sizeof(struct cso_node
);
239 hash
->data
.d
->userNumBits
= MinNumBits
;
240 hash
->data
.d
->numBits
= 0;
241 hash
->data
.d
->numBuckets
= 0;
246 void cso_hash_delete(struct cso_hash
*hash
)
248 struct cso_node
*e_for_x
= (struct cso_node
*)(hash
->data
.d
);
249 struct cso_node
**bucket
= (struct cso_node
**)(hash
->data
.d
->buckets
);
250 int n
= hash
->data
.d
->numBuckets
;
252 struct cso_node
*cur
= *bucket
++;
253 while (cur
!= e_for_x
) {
254 struct cso_node
*next
= cur
->next
;
255 cso_data_free_node(cur
);
259 free(hash
->data
.d
->buckets
);
264 struct cso_hash_iter
cso_hash_find(struct cso_hash
*hash
,
267 struct cso_node
**nextNode
= cso_hash_find_node(hash
, key
);
268 struct cso_hash_iter iter
= {hash
, *nextNode
};
272 unsigned cso_hash_iter_key(struct cso_hash_iter iter
)
274 if (!iter
.node
|| iter
.hash
->data
.e
== iter
.node
)
276 return iter
.node
->key
;
279 void * cso_hash_iter_data(struct cso_hash_iter iter
)
281 if (!iter
.node
|| iter
.hash
->data
.e
== iter
.node
)
283 return iter
.node
->value
;
286 static struct cso_node
*cso_hash_data_next(struct cso_node
*node
)
289 struct cso_node
*next
;
291 struct cso_hash_data
*d
;
295 fprintf(stderr
, "iterating beyond the last element\n");
301 int start
= (node
->key
% a
.d
->numBuckets
) + 1;
302 struct cso_node
**bucket
= a
.d
->buckets
+ start
;
303 int n
= a
.d
->numBuckets
- start
;
313 static struct cso_node
*cso_hash_data_prev(struct cso_node
*node
)
317 struct cso_hash_data
*d
;
326 start
= a
.d
->numBuckets
- 1;
328 start
= node
->key
% a
.d
->numBuckets
;
330 struct cso_node
*sentinel
= node
;
331 struct cso_node
**bucket
= a
.d
->buckets
+ start
;
333 if (*bucket
!= sentinel
) {
334 struct cso_node
*prev
= *bucket
;
335 while (prev
->next
!= sentinel
)
344 fprintf(stderr
, "iterating backward beyond first element\n");
348 struct cso_hash_iter
cso_hash_iter_next(struct cso_hash_iter iter
)
350 struct cso_hash_iter next
= {iter
.hash
, cso_hash_data_next(iter
.node
)};
354 int cso_hash_iter_is_null(struct cso_hash_iter iter
)
356 if (!iter
.node
|| iter
.node
== iter
.hash
->data
.e
)
361 void * cso_hash_take(struct cso_hash
*hash
,
364 struct cso_node
**node
= cso_hash_find_node(hash
, akey
);
365 if (*node
!= hash
->data
.e
) {
366 void *t
= (*node
)->value
;
367 struct cso_node
*next
= (*node
)->next
;
368 cso_data_free_node(*node
);
370 --hash
->data
.d
->size
;
371 cso_data_has_shrunk(hash
->data
.d
);
377 struct cso_hash_iter
cso_hash_iter_prev(struct cso_hash_iter iter
)
379 struct cso_hash_iter prev
= {iter
.hash
,
380 cso_hash_data_prev(iter
.node
)};
384 struct cso_hash_iter
cso_hash_first_node(struct cso_hash
*hash
)
386 struct cso_hash_iter iter
= {hash
, cso_data_first_node(hash
->data
.d
)};