• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 <faith@valinux.com>
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 <X11/Xfuncproto.h>
75 
76 #define HASH_MAIN 0
77 
78 #include <stdio.h>
79 #include <stdlib.h>
80 #include <string.h>
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
HashHash(unsigned long key)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 *
__glxHashCreate(void)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
__glxHashDestroy(__glxHashTable * t)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
HashFind(__glxHashTablePtr table,unsigned long key,unsigned long * h)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
__glxHashLookup(__glxHashTable * t,unsigned long key,void ** value)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
__glxHashInsert(__glxHashTable * t,unsigned long key,void * value)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
__glxHashDelete(__glxHashTable * t,unsigned long key)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
__glxHashNext(__glxHashTable * t,unsigned long * key,void ** value)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
__glxHashFirst(__glxHashTable * t,unsigned long * key,void ** value)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
clear_dist(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
count_entries(__glxHashBucketPtr bucket)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
update_dist(int count)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
compute_dist(__glxHashTablePtr table)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
check_table(__glxHashTablePtr table,unsigned long key,unsigned long value)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
main(void)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
474