1 /* -*- mode: c; tab-width: 3; indent-tabs-mode: nil; c-basic-offset: 3; coding: utf-8-unix -*- */
2 /* glxhash.c -- Small hash table support for integer -> integer mapping
5 * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
7 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
10 * Permission is hereby granted, free of charge, to any person obtaining a
11 * copy of this software and associated documentation files (the "Software"),
12 * to deal in the Software without restriction, including without limitation
13 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 * and/or sell copies of the Software, and to permit persons to whom the
15 * Software is furnished to do so, subject to the following conditions:
17 * The above copyright notice and this permission notice (including the next
18 * paragraph) shall be included in all copies or substantial portions of the
21 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
24 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
25 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
26 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
27 * DEALINGS IN THE SOFTWARE.
29 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
33 * This file contains a straightforward implementation of a fixed-sized
34 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
35 * collision resolution. There are two potentially interesting things
36 * about this implementation:
38 * 1) The table is power-of-two sized. Prime sized tables are more
39 * traditional, but do not have a significant advantage over power-of-two
40 * sized table, especially when double hashing is not used for collision
43 * 2) The hash computation uses a table of random integers [Hanson97,
48 * With a table size of 512, the current implementation is sufficient for a
49 * few hundred keys. Since this is well above the expected size of the
50 * tables for which this implementation was designed, the implementation of
51 * dynamic hash tables was postponed until the need arises. A common (and
52 * naive) approach to dynamic hash table implementation simply creates a
53 * new hash table when necessary, rehashes all the data into the new table,
54 * and destroys the old table. The approach in [Larson88] is superior in
55 * two ways: 1) only a portion of the table is expanded when needed,
56 * distributing the expansion cost over several insertions, and 2) portions
57 * of the table can be locked, enabling a scalable thread-safe
62 * [Hanson97] David R. Hanson. C Interfaces and Implementations:
63 * Techniques for Creating Reusable Software. Reading, Massachusetts:
64 * Addison-Wesley, 1997.
66 * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3:
67 * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973.
69 * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April
75 #include <X11/Xfuncproto.h>
82 #define HASH_MAGIC 0xdeadbeef
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
89 #define HASH_ALLOC malloc
90 #define HASH_FREE free
91 #define HASH_RANDOM_DECL
92 #define HASH_RANDOM_INIT(seed) srandom(seed)
93 #define HASH_RANDOM random()
94 #define HASH_RANDOM_DESTROY
96 typedef struct __glxHashBucket
100 struct __glxHashBucket
*next
;
101 } __glxHashBucket
, *__glxHashBucketPtr
;
103 typedef struct __glxHashTable
*__glxHashTablePtr
;
104 struct __glxHashTable
107 unsigned long hits
; /* At top of linked list */
108 unsigned long partials
; /* Not at top of linked list */
109 unsigned long misses
; /* Not in table */
110 __glxHashBucketPtr buckets
[HASH_SIZE
];
112 __glxHashBucketPtr p1
;
116 HashHash(unsigned long key
)
118 unsigned long hash
= 0;
119 unsigned long tmp
= key
;
121 static unsigned long scatter
[256];
126 HASH_RANDOM_INIT(37);
127 for (i
= 0; i
< 256; i
++)
128 scatter
[i
] = HASH_RANDOM
;
134 hash
= (hash
<< 1) + scatter
[tmp
& 0xff];
140 printf("Hash(%d) = %d\n", key
, hash
);
145 _X_HIDDEN __glxHashTable
*
146 __glxHashCreate(void)
148 __glxHashTablePtr table
;
151 table
= HASH_ALLOC(sizeof(*table
));
154 table
->magic
= HASH_MAGIC
;
159 for (i
= 0; i
< HASH_SIZE
; i
++)
160 table
->buckets
[i
] = NULL
;
165 __glxHashDestroy(__glxHashTable
* t
)
167 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
168 __glxHashBucketPtr bucket
;
169 __glxHashBucketPtr next
;
172 if (table
->magic
!= HASH_MAGIC
)
173 return -1; /* Bad magic */
175 for (i
= 0; i
< HASH_SIZE
; i
++) {
176 for (bucket
= table
->buckets
[i
]; bucket
;) {
186 /* Find the bucket and organize the list so that this bucket is at the
189 static __glxHashBucketPtr
190 HashFind(__glxHashTablePtr table
, unsigned long key
, unsigned long *h
)
192 unsigned long hash
= HashHash(key
);
193 __glxHashBucketPtr prev
= NULL
;
194 __glxHashBucketPtr bucket
;
199 for (bucket
= table
->buckets
[hash
]; bucket
; bucket
= bucket
->next
) {
200 if (bucket
->key
== key
) {
203 prev
->next
= bucket
->next
;
204 bucket
->next
= table
->buckets
[hash
];
205 table
->buckets
[hash
] = bucket
;
220 __glxHashLookup(__glxHashTable
* t
, unsigned long key
, void **value
)
222 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
223 __glxHashBucketPtr bucket
;
225 if (!table
|| table
->magic
!= HASH_MAGIC
)
226 return -1; /* Bad magic */
228 bucket
= HashFind(table
, key
, NULL
);
230 return 1; /* Not found */
231 *value
= bucket
->value
;
232 return 0; /* Found */
236 __glxHashInsert(__glxHashTable
* t
, unsigned long key
, void *value
)
238 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
239 __glxHashBucketPtr bucket
;
242 if (table
->magic
!= HASH_MAGIC
)
243 return -1; /* Bad magic */
245 if (HashFind(table
, key
, &hash
))
246 return 1; /* Already in table */
248 bucket
= HASH_ALLOC(sizeof(*bucket
));
250 return -1; /* Error */
252 bucket
->value
= value
;
253 bucket
->next
= table
->buckets
[hash
];
254 table
->buckets
[hash
] = bucket
;
256 printf("Inserted %d at %d/%p\n", key
, hash
, bucket
);
258 return 0; /* Added to table */
262 __glxHashDelete(__glxHashTable
* t
, unsigned long key
)
264 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
266 __glxHashBucketPtr bucket
;
268 if (table
->magic
!= HASH_MAGIC
)
269 return -1; /* Bad magic */
271 bucket
= HashFind(table
, key
, &hash
);
274 return 1; /* Not found */
276 table
->buckets
[hash
] = bucket
->next
;
282 __glxHashNext(__glxHashTable
* t
, unsigned long *key
, void **value
)
284 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
286 while (table
->p0
< HASH_SIZE
) {
288 *key
= table
->p1
->key
;
289 *value
= table
->p1
->value
;
290 table
->p1
= table
->p1
->next
;
293 table
->p1
= table
->buckets
[table
->p0
];
300 __glxHashFirst(__glxHashTable
* t
, unsigned long *key
, void **value
)
302 __glxHashTablePtr table
= (__glxHashTablePtr
) t
;
304 if (table
->magic
!= HASH_MAGIC
)
305 return -1; /* Bad magic */
308 table
->p1
= table
->buckets
[0];
309 return __glxHashNext(table
, key
, value
);
313 #define DIST_LIMIT 10
314 static int dist
[DIST_LIMIT
];
321 for (i
= 0; i
< DIST_LIMIT
; i
++)
326 count_entries(__glxHashBucketPtr bucket
)
330 for (; bucket
; bucket
= bucket
->next
)
336 update_dist(int count
)
338 if (count
>= DIST_LIMIT
)
339 ++dist
[DIST_LIMIT
- 1];
345 compute_dist(__glxHashTablePtr table
)
348 __glxHashBucketPtr bucket
;
350 printf("Hits = %ld, partials = %ld, misses = %ld\n",
351 table
->hits
, table
->partials
, table
->misses
);
353 for (i
= 0; i
< HASH_SIZE
; i
++) {
354 bucket
= table
->buckets
[i
];
355 update_dist(count_entries(bucket
));
357 for (i
= 0; i
< DIST_LIMIT
; i
++) {
358 if (i
!= DIST_LIMIT
- 1)
359 printf("%5d %10d\n", i
, dist
[i
]);
361 printf("other %10d\n", dist
[i
]);
366 check_table(__glxHashTablePtr table
, unsigned long key
, unsigned long value
)
368 unsigned long retval
= 0;
369 int retcode
= __glxHashLookup(table
, key
, &retval
);
373 printf("Bad magic = 0x%08lx:"
374 " key = %lu, expected = %lu, returned = %lu\n",
375 table
->magic
, key
, value
, retval
);
378 printf("Not found: key = %lu, expected = %lu returned = %lu\n",
383 printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
387 printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
388 retcode
, key
, value
, retval
);
396 __glxHashTablePtr table
;
399 printf("\n***** 256 consecutive integers ****\n");
400 table
= __glxHashCreate();
401 for (i
= 0; i
< 256; i
++)
402 __glxHashInsert(table
, i
, i
);
403 for (i
= 0; i
< 256; i
++)
404 check_table(table
, i
, i
);
405 for (i
= 256; i
>= 0; i
--)
406 check_table(table
, i
, i
);
408 __glxHashDestroy(table
);
410 printf("\n***** 1024 consecutive integers ****\n");
411 table
= __glxHashCreate();
412 for (i
= 0; i
< 1024; i
++)
413 __glxHashInsert(table
, i
, i
);
414 for (i
= 0; i
< 1024; i
++)
415 check_table(table
, i
, i
);
416 for (i
= 1024; i
>= 0; i
--)
417 check_table(table
, i
, i
);
419 __glxHashDestroy(table
);
421 printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
422 table
= __glxHashCreate();
423 for (i
= 0; i
< 1024; i
++)
424 __glxHashInsert(table
, i
* 4096, i
);
425 for (i
= 0; i
< 1024; i
++)
426 check_table(table
, i
* 4096, i
);
427 for (i
= 1024; i
>= 0; i
--)
428 check_table(table
, i
* 4096, i
);
430 __glxHashDestroy(table
);
432 printf("\n***** 1024 random integers ****\n");
433 table
= __glxHashCreate();
435 for (i
= 0; i
< 1024; i
++)
436 __glxHashInsert(table
, random(), i
);
438 for (i
= 0; i
< 1024; i
++)
439 check_table(table
, random(), i
);
441 for (i
= 0; i
< 1024; i
++)
442 check_table(table
, random(), i
);
444 __glxHashDestroy(table
);
446 printf("\n***** 5000 random integers ****\n");
447 table
= __glxHashCreate();
449 for (i
= 0; i
< 5000; i
++)
450 __glxHashInsert(table
, random(), i
);
452 for (i
= 0; i
< 5000; i
++)
453 check_table(table
, random(), i
);
455 for (i
= 0; i
< 5000; i
++)
456 check_table(table
, random(), i
);
458 __glxHashDestroy(table
);