Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4358 | Serge | 1 | /* glxhash.c -- Small hash table support for integer -> integer mapping |
2 | * Taken from libdrm. |
||
3 | * |
||
4 | * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com |
||
5 | * |
||
6 | * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. |
||
7 | * All Rights Reserved. |
||
8 | * |
||
9 | * Permission is hereby granted, free of charge, to any person obtaining a |
||
10 | * copy of this software and associated documentation files (the "Software"), |
||
11 | * to deal in the Software without restriction, including without limitation |
||
12 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
||
13 | * and/or sell copies of the Software, and to permit persons to whom the |
||
14 | * Software is furnished to do so, subject to the following conditions: |
||
15 | * |
||
16 | * The above copyright notice and this permission notice (including the next |
||
17 | * paragraph) shall be included in all copies or substantial portions of the |
||
18 | * Software. |
||
19 | * |
||
20 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
||
21 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
||
22 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
||
23 | * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
||
24 | * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
||
25 | * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
||
26 | * DEALINGS IN THE SOFTWARE. |
||
27 | * |
||
28 | * Authors: Rickard E. (Rik) Faith |
||
29 | * |
||
30 | * DESCRIPTION |
||
31 | * |
||
32 | * This file contains a straightforward implementation of a fixed-sized |
||
33 | * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for |
||
34 | * collision resolution. There are two potentially interesting things |
||
35 | * about this implementation: |
||
36 | * |
||
37 | * 1) The table is power-of-two sized. Prime sized tables are more |
||
38 | * traditional, but do not have a significant advantage over power-of-two |
||
39 | * sized table, especially when double hashing is not used for collision |
||
40 | * resolution. |
||
41 | * |
||
42 | * 2) The hash computation uses a table of random integers [Hanson97, |
||
43 | * pp. 39-41]. |
||
44 | * |
||
45 | * FUTURE ENHANCEMENTS |
||
46 | * |
||
47 | * With a table size of 512, the current implementation is sufficient for a |
||
48 | * few hundred keys. Since this is well above the expected size of the |
||
49 | * tables for which this implementation was designed, the implementation of |
||
50 | * dynamic hash tables was postponed until the need arises. A common (and |
||
51 | * naive) approach to dynamic hash table implementation simply creates a |
||
52 | * new hash table when necessary, rehashes all the data into the new table, |
||
53 | * and destroys the old table. The approach in [Larson88] is superior in |
||
54 | * two ways: 1) only a portion of the table is expanded when needed, |
||
55 | * distributing the expansion cost over several insertions, and 2) portions |
||
56 | * of the table can be locked, enabling a scalable thread-safe |
||
57 | * implementation. |
||
58 | * |
||
59 | * REFERENCES |
||
60 | * |
||
61 | * [Hanson97] David R. Hanson. C Interfaces and Implementations: |
||
62 | * Techniques for Creating Reusable Software. Reading, Massachusetts: |
||
63 | * Addison-Wesley, 1997. |
||
64 | * |
||
65 | * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3: |
||
66 | * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973. |
||
67 | * |
||
68 | * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April |
||
69 | * 1988, pp. 446-457. |
||
70 | * |
||
71 | */ |
||
72 | |||
73 | #include "glxhash.h" |
||
74 | #include |
||
75 | |||
76 | #define HASH_MAIN 0 |
||
77 | |||
78 | #include |
||
79 | #include |
||
80 | #include |
||
81 | |||
82 | #define HASH_MAGIC 0xdeadbeef |
||
83 | #define HASH_DEBUG 0 |
||
84 | #define HASH_SIZE 512 /* Good for about 100 entries */ |
||
85 | /* If you change this value, you probably |
||
86 | have to change the HashHash hashing |
||
87 | function! */ |
||
88 | |||
89 | #define HASH_ALLOC malloc |
||
90 | #define HASH_FREE free |
||
91 | #ifndef __GLIBC__ |
||
92 | #define HASH_RANDOM_DECL char *ps, rs[256] |
||
93 | #define HASH_RANDOM_INIT(seed) ps = initstate(seed, rs, sizeof(rs)) |
||
94 | #define HASH_RANDOM random() |
||
95 | #define HASH_RANDOM_DESTROY setstate(ps) |
||
96 | #else |
||
97 | #define HASH_RANDOM_DECL struct random_data rd; int32_t rv; char rs[256] |
||
98 | #define HASH_RANDOM_INIT(seed) \ |
||
99 | do { \ |
||
100 | (void) memset(&rd, 0, sizeof(rd)); \ |
||
101 | (void) initstate_r(seed, rs, sizeof(rs), &rd); \ |
||
102 | } while(0) |
||
103 | #define HASH_RANDOM ((void) random_r(&rd, &rv), rv) |
||
104 | #define HASH_RANDOM_DESTROY |
||
105 | #endif |
||
106 | |||
107 | typedef struct __glxHashBucket |
||
108 | { |
||
109 | unsigned long key; |
||
110 | void *value; |
||
111 | struct __glxHashBucket *next; |
||
112 | } __glxHashBucket, *__glxHashBucketPtr; |
||
113 | |||
114 | typedef struct __glxHashTable *__glxHashTablePtr; |
||
115 | struct __glxHashTable |
||
116 | { |
||
117 | unsigned long magic; |
||
118 | unsigned long hits; /* At top of linked list */ |
||
119 | unsigned long partials; /* Not at top of linked list */ |
||
120 | unsigned long misses; /* Not in table */ |
||
121 | __glxHashBucketPtr buckets[HASH_SIZE]; |
||
122 | int p0; |
||
123 | __glxHashBucketPtr p1; |
||
124 | }; |
||
125 | |||
126 | static unsigned long |
||
127 | HashHash(unsigned long key) |
||
128 | { |
||
129 | unsigned long hash = 0; |
||
130 | unsigned long tmp = key; |
||
131 | static int init = 0; |
||
132 | static unsigned long scatter[256]; |
||
133 | int i; |
||
134 | |||
135 | if (!init) { |
||
136 | HASH_RANDOM_DECL; |
||
137 | HASH_RANDOM_INIT(37); |
||
138 | for (i = 0; i < 256; i++) |
||
139 | scatter[i] = HASH_RANDOM; |
||
140 | HASH_RANDOM_DESTROY; |
||
141 | ++init; |
||
142 | } |
||
143 | |||
144 | while (tmp) { |
||
145 | hash = (hash << 1) + scatter[tmp & 0xff]; |
||
146 | tmp >>= 8; |
||
147 | } |
||
148 | |||
149 | hash %= HASH_SIZE; |
||
150 | #if HASH_DEBUG |
||
151 | printf("Hash(%d) = %d\n", key, hash); |
||
152 | #endif |
||
153 | return hash; |
||
154 | } |
||
155 | |||
156 | _X_HIDDEN __glxHashTable * |
||
157 | __glxHashCreate(void) |
||
158 | { |
||
159 | __glxHashTablePtr table; |
||
160 | int i; |
||
161 | |||
162 | table = HASH_ALLOC(sizeof(*table)); |
||
163 | if (!table) |
||
164 | return NULL; |
||
165 | table->magic = HASH_MAGIC; |
||
166 | table->hits = 0; |
||
167 | table->partials = 0; |
||
168 | table->misses = 0; |
||
169 | |||
170 | for (i = 0; i < HASH_SIZE; i++) |
||
171 | table->buckets[i] = NULL; |
||
172 | return table; |
||
173 | } |
||
174 | |||
175 | _X_HIDDEN int |
||
176 | __glxHashDestroy(__glxHashTable * t) |
||
177 | { |
||
178 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
179 | __glxHashBucketPtr bucket; |
||
180 | __glxHashBucketPtr next; |
||
181 | int i; |
||
182 | |||
183 | if (table->magic != HASH_MAGIC) |
||
184 | return -1; /* Bad magic */ |
||
185 | |||
186 | for (i = 0; i < HASH_SIZE; i++) { |
||
187 | for (bucket = table->buckets[i]; bucket;) { |
||
188 | next = bucket->next; |
||
189 | HASH_FREE(bucket); |
||
190 | bucket = next; |
||
191 | } |
||
192 | } |
||
193 | HASH_FREE(table); |
||
194 | return 0; |
||
195 | } |
||
196 | |||
197 | /* Find the bucket and organize the list so that this bucket is at the |
||
198 | top. */ |
||
199 | |||
200 | static __glxHashBucketPtr |
||
201 | HashFind(__glxHashTablePtr table, unsigned long key, unsigned long *h) |
||
202 | { |
||
203 | unsigned long hash = HashHash(key); |
||
204 | __glxHashBucketPtr prev = NULL; |
||
205 | __glxHashBucketPtr bucket; |
||
206 | |||
207 | if (h) |
||
208 | *h = hash; |
||
209 | |||
210 | for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) { |
||
211 | if (bucket->key == key) { |
||
212 | if (prev) { |
||
213 | /* Organize */ |
||
214 | prev->next = bucket->next; |
||
215 | bucket->next = table->buckets[hash]; |
||
216 | table->buckets[hash] = bucket; |
||
217 | ++table->partials; |
||
218 | } |
||
219 | else { |
||
220 | ++table->hits; |
||
221 | } |
||
222 | return bucket; |
||
223 | } |
||
224 | prev = bucket; |
||
225 | } |
||
226 | ++table->misses; |
||
227 | return NULL; |
||
228 | } |
||
229 | |||
230 | _X_HIDDEN int |
||
231 | __glxHashLookup(__glxHashTable * t, unsigned long key, void **value) |
||
232 | { |
||
233 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
234 | __glxHashBucketPtr bucket; |
||
235 | |||
236 | if (!table || table->magic != HASH_MAGIC) |
||
237 | return -1; /* Bad magic */ |
||
238 | |||
239 | bucket = HashFind(table, key, NULL); |
||
240 | if (!bucket) |
||
241 | return 1; /* Not found */ |
||
242 | *value = bucket->value; |
||
243 | return 0; /* Found */ |
||
244 | } |
||
245 | |||
246 | _X_HIDDEN int |
||
247 | __glxHashInsert(__glxHashTable * t, unsigned long key, void *value) |
||
248 | { |
||
249 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
250 | __glxHashBucketPtr bucket; |
||
251 | unsigned long hash; |
||
252 | |||
253 | if (table->magic != HASH_MAGIC) |
||
254 | return -1; /* Bad magic */ |
||
255 | |||
256 | if (HashFind(table, key, &hash)) |
||
257 | return 1; /* Already in table */ |
||
258 | |||
259 | bucket = HASH_ALLOC(sizeof(*bucket)); |
||
260 | if (!bucket) |
||
261 | return -1; /* Error */ |
||
262 | bucket->key = key; |
||
263 | bucket->value = value; |
||
264 | bucket->next = table->buckets[hash]; |
||
265 | table->buckets[hash] = bucket; |
||
266 | #if HASH_DEBUG |
||
267 | printf("Inserted %d at %d/%p\n", key, hash, bucket); |
||
268 | #endif |
||
269 | return 0; /* Added to table */ |
||
270 | } |
||
271 | |||
272 | _X_HIDDEN int |
||
273 | __glxHashDelete(__glxHashTable * t, unsigned long key) |
||
274 | { |
||
275 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
276 | unsigned long hash; |
||
277 | __glxHashBucketPtr bucket; |
||
278 | |||
279 | if (table->magic != HASH_MAGIC) |
||
280 | return -1; /* Bad magic */ |
||
281 | |||
282 | bucket = HashFind(table, key, &hash); |
||
283 | |||
284 | if (!bucket) |
||
285 | return 1; /* Not found */ |
||
286 | |||
287 | table->buckets[hash] = bucket->next; |
||
288 | HASH_FREE(bucket); |
||
289 | return 0; |
||
290 | } |
||
291 | |||
292 | _X_HIDDEN int |
||
293 | __glxHashNext(__glxHashTable * t, unsigned long *key, void **value) |
||
294 | { |
||
295 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
296 | |||
297 | while (table->p0 < HASH_SIZE) { |
||
298 | if (table->p1) { |
||
299 | *key = table->p1->key; |
||
300 | *value = table->p1->value; |
||
301 | table->p1 = table->p1->next; |
||
302 | return 1; |
||
303 | } |
||
304 | table->p1 = table->buckets[table->p0]; |
||
305 | ++table->p0; |
||
306 | } |
||
307 | return 0; |
||
308 | } |
||
309 | |||
310 | _X_HIDDEN int |
||
311 | __glxHashFirst(__glxHashTable * t, unsigned long *key, void **value) |
||
312 | { |
||
313 | __glxHashTablePtr table = (__glxHashTablePtr) t; |
||
314 | |||
315 | if (table->magic != HASH_MAGIC) |
||
316 | return -1; /* Bad magic */ |
||
317 | |||
318 | table->p0 = 0; |
||
319 | table->p1 = table->buckets[0]; |
||
320 | return __glxHashNext(table, key, value); |
||
321 | } |
||
322 | |||
323 | #if HASH_MAIN |
||
324 | #define DIST_LIMIT 10 |
||
325 | static int dist[DIST_LIMIT]; |
||
326 | |||
327 | static void |
||
328 | clear_dist(void) |
||
329 | { |
||
330 | int i; |
||
331 | |||
332 | for (i = 0; i < DIST_LIMIT; i++) |
||
333 | dist[i] = 0; |
||
334 | } |
||
335 | |||
336 | static int |
||
337 | count_entries(__glxHashBucketPtr bucket) |
||
338 | { |
||
339 | int count = 0; |
||
340 | |||
341 | for (; bucket; bucket = bucket->next) |
||
342 | ++count; |
||
343 | return count; |
||
344 | } |
||
345 | |||
346 | static void |
||
347 | update_dist(int count) |
||
348 | { |
||
349 | if (count >= DIST_LIMIT) |
||
350 | ++dist[DIST_LIMIT - 1]; |
||
351 | else |
||
352 | ++dist[count]; |
||
353 | } |
||
354 | |||
355 | static void |
||
356 | compute_dist(__glxHashTablePtr table) |
||
357 | { |
||
358 | int i; |
||
359 | __glxHashBucketPtr bucket; |
||
360 | |||
361 | printf("Hits = %ld, partials = %ld, misses = %ld\n", |
||
362 | table->hits, table->partials, table->misses); |
||
363 | clear_dist(); |
||
364 | for (i = 0; i < HASH_SIZE; i++) { |
||
365 | bucket = table->buckets[i]; |
||
366 | update_dist(count_entries(bucket)); |
||
367 | } |
||
368 | for (i = 0; i < DIST_LIMIT; i++) { |
||
369 | if (i != DIST_LIMIT - 1) |
||
370 | printf("%5d %10d\n", i, dist[i]); |
||
371 | else |
||
372 | printf("other %10d\n", dist[i]); |
||
373 | } |
||
374 | } |
||
375 | |||
376 | static void |
||
377 | check_table(__glxHashTablePtr table, unsigned long key, unsigned long value) |
||
378 | { |
||
379 | unsigned long retval = 0; |
||
380 | int retcode = __glxHashLookup(table, key, &retval); |
||
381 | |||
382 | switch (retcode) { |
||
383 | case -1: |
||
384 | printf("Bad magic = 0x%08lx:" |
||
385 | " key = %lu, expected = %lu, returned = %lu\n", |
||
386 | table->magic, key, value, retval); |
||
387 | break; |
||
388 | case 1: |
||
389 | printf("Not found: key = %lu, expected = %lu returned = %lu\n", |
||
390 | key, value, retval); |
||
391 | break; |
||
392 | case 0: |
||
393 | if (value != retval) |
||
394 | printf("Bad value: key = %lu, expected = %lu, returned = %lu\n", |
||
395 | key, value, retval); |
||
396 | break; |
||
397 | default: |
||
398 | printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n", |
||
399 | retcode, key, value, retval); |
||
400 | break; |
||
401 | } |
||
402 | } |
||
403 | |||
404 | int |
||
405 | main(void) |
||
406 | { |
||
407 | __glxHashTablePtr table; |
||
408 | int i; |
||
409 | |||
410 | printf("\n***** 256 consecutive integers ****\n"); |
||
411 | table = __glxHashCreate(); |
||
412 | for (i = 0; i < 256; i++) |
||
413 | __glxHashInsert(table, i, i); |
||
414 | for (i = 0; i < 256; i++) |
||
415 | check_table(table, i, i); |
||
416 | for (i = 256; i >= 0; i--) |
||
417 | check_table(table, i, i); |
||
418 | compute_dist(table); |
||
419 | __glxHashDestroy(table); |
||
420 | |||
421 | printf("\n***** 1024 consecutive integers ****\n"); |
||
422 | table = __glxHashCreate(); |
||
423 | for (i = 0; i < 1024; i++) |
||
424 | __glxHashInsert(table, i, i); |
||
425 | for (i = 0; i < 1024; i++) |
||
426 | check_table(table, i, i); |
||
427 | for (i = 1024; i >= 0; i--) |
||
428 | check_table(table, i, i); |
||
429 | compute_dist(table); |
||
430 | __glxHashDestroy(table); |
||
431 | |||
432 | printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); |
||
433 | table = __glxHashCreate(); |
||
434 | for (i = 0; i < 1024; i++) |
||
435 | __glxHashInsert(table, i * 4096, i); |
||
436 | for (i = 0; i < 1024; i++) |
||
437 | check_table(table, i * 4096, i); |
||
438 | for (i = 1024; i >= 0; i--) |
||
439 | check_table(table, i * 4096, i); |
||
440 | compute_dist(table); |
||
441 | __glxHashDestroy(table); |
||
442 | |||
443 | printf("\n***** 1024 random integers ****\n"); |
||
444 | table = __glxHashCreate(); |
||
445 | srandom(0xbeefbeef); |
||
446 | for (i = 0; i < 1024; i++) |
||
447 | __glxHashInsert(table, random(), i); |
||
448 | srandom(0xbeefbeef); |
||
449 | for (i = 0; i < 1024; i++) |
||
450 | check_table(table, random(), i); |
||
451 | srandom(0xbeefbeef); |
||
452 | for (i = 0; i < 1024; i++) |
||
453 | check_table(table, random(), i); |
||
454 | compute_dist(table); |
||
455 | __glxHashDestroy(table); |
||
456 | |||
457 | printf("\n***** 5000 random integers ****\n"); |
||
458 | table = __glxHashCreate(); |
||
459 | srandom(0xbeefbeef); |
||
460 | for (i = 0; i < 5000; i++) |
||
461 | __glxHashInsert(table, random(), i); |
||
462 | srandom(0xbeefbeef); |
||
463 | for (i = 0; i < 5000; i++) |
||
464 | check_table(table, random(), i); |
||
465 | srandom(0xbeefbeef); |
||
466 | for (i = 0; i < 5000; i++) |
||
467 | check_table(table, random(), i); |
||
468 | compute_dist(table); |
||
469 | __glxHashDestroy(table); |
||
470 | |||
471 | return 0; |
||
472 | } |
||
473 | #endif>>>>>>>>>>>>>>>>>>><>> |