| /* glxhash.c -- Small hash table support for integer -> integer mapping |
| * Taken from libdrm. |
| * |
| * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com |
| * |
| * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. |
| * All Rights Reserved. |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR |
| * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
| * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| * DEALINGS IN THE SOFTWARE. |
| * |
| * Authors: Rickard E. (Rik) Faith <faith@valinux.com> |
| * |
| * DESCRIPTION |
| * |
| * This file contains a straightforward implementation of a fixed-sized |
| * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for |
| * collision resolution. There are two potentially interesting things |
| * about this implementation: |
| * |
| * 1) The table is power-of-two sized. Prime sized tables are more |
| * traditional, but do not have a significant advantage over power-of-two |
| * sized table, especially when double hashing is not used for collision |
| * resolution. |
| * |
| * 2) The hash computation uses a table of random integers [Hanson97, |
| * pp. 39-41]. |
| * |
| * FUTURE ENHANCEMENTS |
| * |
| * With a table size of 512, the current implementation is sufficient for a |
| * few hundred keys. Since this is well above the expected size of the |
| * tables for which this implementation was designed, the implementation of |
| * dynamic hash tables was postponed until the need arises. A common (and |
| * naive) approach to dynamic hash table implementation simply creates a |
| * new hash table when necessary, rehashes all the data into the new table, |
| * and destroys the old table. The approach in [Larson88] is superior in |
| * two ways: 1) only a portion of the table is expanded when needed, |
| * distributing the expansion cost over several insertions, and 2) portions |
| * of the table can be locked, enabling a scalable thread-safe |
| * implementation. |
| * |
| * REFERENCES |
| * |
| * [Hanson97] David R. Hanson. C Interfaces and Implementations: |
| * Techniques for Creating Reusable Software. Reading, Massachusetts: |
| * Addison-Wesley, 1997. |
| * |
| * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3: |
| * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973. |
| * |
| * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April |
| * 1988, pp. 446-457. |
| * |
| */ |
| |
| #include "glxhash.h" |
| #include <X11/Xfuncproto.h> |
| |
| #define HASH_MAIN 0 |
| |
| #include <stdio.h> |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #define HASH_MAGIC 0xdeadbeef |
| #define HASH_DEBUG 0 |
| #define HASH_SIZE 512 /* Good for about 100 entries */ |
| /* If you change this value, you probably |
| have to change the HashHash hashing |
| function! */ |
| |
| #define HASH_ALLOC malloc |
| #define HASH_FREE free |
| #ifndef __GLIBC__ |
| #define HASH_RANDOM_DECL char *ps, rs[256] |
| #define HASH_RANDOM_INIT(seed) ps = initstate(seed, rs, sizeof(rs)) |
| #define HASH_RANDOM random() |
| #define HASH_RANDOM_DESTROY setstate(ps) |
| #else |
| #define HASH_RANDOM_DECL struct random_data rd; int32_t rv; char rs[256] |
| #define HASH_RANDOM_INIT(seed) \ |
| do { \ |
| (void) memset(&rd, 0, sizeof(rd)); \ |
| (void) initstate_r(seed, rs, sizeof(rs), &rd); \ |
| } while(0) |
| #define HASH_RANDOM ((void) random_r(&rd, &rv), rv) |
| #define HASH_RANDOM_DESTROY |
| #endif |
| |
| typedef struct __glxHashBucket |
| { |
| unsigned long key; |
| void *value; |
| struct __glxHashBucket *next; |
| } __glxHashBucket, *__glxHashBucketPtr; |
| |
| typedef struct __glxHashTable *__glxHashTablePtr; |
| struct __glxHashTable |
| { |
| unsigned long magic; |
| unsigned long hits; /* At top of linked list */ |
| unsigned long partials; /* Not at top of linked list */ |
| unsigned long misses; /* Not in table */ |
| __glxHashBucketPtr buckets[HASH_SIZE]; |
| int p0; |
| __glxHashBucketPtr p1; |
| }; |
| |
| static unsigned long |
| HashHash(unsigned long key) |
| { |
| unsigned long hash = 0; |
| unsigned long tmp = key; |
| static int init = 0; |
| static unsigned long scatter[256]; |
| int i; |
| |
| if (!init) { |
| HASH_RANDOM_DECL; |
| HASH_RANDOM_INIT(37); |
| for (i = 0; i < 256; i++) |
| scatter[i] = HASH_RANDOM; |
| HASH_RANDOM_DESTROY; |
| ++init; |
| } |
| |
| while (tmp) { |
| hash = (hash << 1) + scatter[tmp & 0xff]; |
| tmp >>= 8; |
| } |
| |
| hash %= HASH_SIZE; |
| #if HASH_DEBUG |
| printf("Hash(%d) = %d\n", key, hash); |
| #endif |
| return hash; |
| } |
| |
| _X_HIDDEN __glxHashTable * |
| __glxHashCreate(void) |
| { |
| __glxHashTablePtr table; |
| int i; |
| |
| table = HASH_ALLOC(sizeof(*table)); |
| if (!table) |
| return NULL; |
| table->magic = HASH_MAGIC; |
| table->hits = 0; |
| table->partials = 0; |
| table->misses = 0; |
| |
| for (i = 0; i < HASH_SIZE; i++) |
| table->buckets[i] = NULL; |
| return table; |
| } |
| |
| _X_HIDDEN int |
| __glxHashDestroy(__glxHashTable * t) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| __glxHashBucketPtr bucket; |
| __glxHashBucketPtr next; |
| int i; |
| |
| if (table->magic != HASH_MAGIC) |
| return -1; /* Bad magic */ |
| |
| for (i = 0; i < HASH_SIZE; i++) { |
| for (bucket = table->buckets[i]; bucket;) { |
| next = bucket->next; |
| HASH_FREE(bucket); |
| bucket = next; |
| } |
| } |
| HASH_FREE(table); |
| return 0; |
| } |
| |
| /* Find the bucket and organize the list so that this bucket is at the |
| top. */ |
| |
| static __glxHashBucketPtr |
| HashFind(__glxHashTablePtr table, unsigned long key, unsigned long *h) |
| { |
| unsigned long hash = HashHash(key); |
| __glxHashBucketPtr prev = NULL; |
| __glxHashBucketPtr bucket; |
| |
| if (h) |
| *h = hash; |
| |
| for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) { |
| if (bucket->key == key) { |
| if (prev) { |
| /* Organize */ |
| prev->next = bucket->next; |
| bucket->next = table->buckets[hash]; |
| table->buckets[hash] = bucket; |
| ++table->partials; |
| } |
| else { |
| ++table->hits; |
| } |
| return bucket; |
| } |
| prev = bucket; |
| } |
| ++table->misses; |
| return NULL; |
| } |
| |
| _X_HIDDEN int |
| __glxHashLookup(__glxHashTable * t, unsigned long key, void **value) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| __glxHashBucketPtr bucket; |
| |
| if (!table || table->magic != HASH_MAGIC) |
| return -1; /* Bad magic */ |
| |
| bucket = HashFind(table, key, NULL); |
| if (!bucket) |
| return 1; /* Not found */ |
| *value = bucket->value; |
| return 0; /* Found */ |
| } |
| |
| _X_HIDDEN int |
| __glxHashInsert(__glxHashTable * t, unsigned long key, void *value) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| __glxHashBucketPtr bucket; |
| unsigned long hash; |
| |
| if (table->magic != HASH_MAGIC) |
| return -1; /* Bad magic */ |
| |
| if (HashFind(table, key, &hash)) |
| return 1; /* Already in table */ |
| |
| bucket = HASH_ALLOC(sizeof(*bucket)); |
| if (!bucket) |
| return -1; /* Error */ |
| bucket->key = key; |
| bucket->value = value; |
| bucket->next = table->buckets[hash]; |
| table->buckets[hash] = bucket; |
| #if HASH_DEBUG |
| printf("Inserted %d at %d/%p\n", key, hash, bucket); |
| #endif |
| return 0; /* Added to table */ |
| } |
| |
| _X_HIDDEN int |
| __glxHashDelete(__glxHashTable * t, unsigned long key) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| unsigned long hash; |
| __glxHashBucketPtr bucket; |
| |
| if (table->magic != HASH_MAGIC) |
| return -1; /* Bad magic */ |
| |
| bucket = HashFind(table, key, &hash); |
| |
| if (!bucket) |
| return 1; /* Not found */ |
| |
| table->buckets[hash] = bucket->next; |
| HASH_FREE(bucket); |
| return 0; |
| } |
| |
| _X_HIDDEN int |
| __glxHashNext(__glxHashTable * t, unsigned long *key, void **value) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| |
| while (table->p0 < HASH_SIZE) { |
| if (table->p1) { |
| *key = table->p1->key; |
| *value = table->p1->value; |
| table->p1 = table->p1->next; |
| return 1; |
| } |
| table->p1 = table->buckets[table->p0]; |
| ++table->p0; |
| } |
| return 0; |
| } |
| |
| _X_HIDDEN int |
| __glxHashFirst(__glxHashTable * t, unsigned long *key, void **value) |
| { |
| __glxHashTablePtr table = (__glxHashTablePtr) t; |
| |
| if (table->magic != HASH_MAGIC) |
| return -1; /* Bad magic */ |
| |
| table->p0 = 0; |
| table->p1 = table->buckets[0]; |
| return __glxHashNext(table, key, value); |
| } |
| |
| #if HASH_MAIN |
| #define DIST_LIMIT 10 |
| static int dist[DIST_LIMIT]; |
| |
| static void |
| clear_dist(void) |
| { |
| int i; |
| |
| for (i = 0; i < DIST_LIMIT; i++) |
| dist[i] = 0; |
| } |
| |
| static int |
| count_entries(__glxHashBucketPtr bucket) |
| { |
| int count = 0; |
| |
| for (; bucket; bucket = bucket->next) |
| ++count; |
| return count; |
| } |
| |
| static void |
| update_dist(int count) |
| { |
| if (count >= DIST_LIMIT) |
| ++dist[DIST_LIMIT - 1]; |
| else |
| ++dist[count]; |
| } |
| |
| static void |
| compute_dist(__glxHashTablePtr table) |
| { |
| int i; |
| __glxHashBucketPtr bucket; |
| |
| printf("Hits = %ld, partials = %ld, misses = %ld\n", |
| table->hits, table->partials, table->misses); |
| clear_dist(); |
| for (i = 0; i < HASH_SIZE; i++) { |
| bucket = table->buckets[i]; |
| update_dist(count_entries(bucket)); |
| } |
| for (i = 0; i < DIST_LIMIT; i++) { |
| if (i != DIST_LIMIT - 1) |
| printf("%5d %10d\n", i, dist[i]); |
| else |
| printf("other %10d\n", dist[i]); |
| } |
| } |
| |
| static void |
| check_table(__glxHashTablePtr table, unsigned long key, unsigned long value) |
| { |
| unsigned long retval = 0; |
| int retcode = __glxHashLookup(table, key, &retval); |
| |
| switch (retcode) { |
| case -1: |
| printf("Bad magic = 0x%08lx:" |
| " key = %lu, expected = %lu, returned = %lu\n", |
| table->magic, key, value, retval); |
| break; |
| case 1: |
| printf("Not found: key = %lu, expected = %lu returned = %lu\n", |
| key, value, retval); |
| break; |
| case 0: |
| if (value != retval) |
| printf("Bad value: key = %lu, expected = %lu, returned = %lu\n", |
| key, value, retval); |
| break; |
| default: |
| printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n", |
| retcode, key, value, retval); |
| break; |
| } |
| } |
| |
| int |
| main(void) |
| { |
| __glxHashTablePtr table; |
| int i; |
| |
| printf("\n***** 256 consecutive integers ****\n"); |
| table = __glxHashCreate(); |
| for (i = 0; i < 256; i++) |
| __glxHashInsert(table, i, i); |
| for (i = 0; i < 256; i++) |
| check_table(table, i, i); |
| for (i = 256; i >= 0; i--) |
| check_table(table, i, i); |
| compute_dist(table); |
| __glxHashDestroy(table); |
| |
| printf("\n***** 1024 consecutive integers ****\n"); |
| table = __glxHashCreate(); |
| for (i = 0; i < 1024; i++) |
| __glxHashInsert(table, i, i); |
| for (i = 0; i < 1024; i++) |
| check_table(table, i, i); |
| for (i = 1024; i >= 0; i--) |
| check_table(table, i, i); |
| compute_dist(table); |
| __glxHashDestroy(table); |
| |
| printf("\n***** 1024 consecutive page addresses (4k pages) ****\n"); |
| table = __glxHashCreate(); |
| for (i = 0; i < 1024; i++) |
| __glxHashInsert(table, i * 4096, i); |
| for (i = 0; i < 1024; i++) |
| check_table(table, i * 4096, i); |
| for (i = 1024; i >= 0; i--) |
| check_table(table, i * 4096, i); |
| compute_dist(table); |
| __glxHashDestroy(table); |
| |
| printf("\n***** 1024 random integers ****\n"); |
| table = __glxHashCreate(); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 1024; i++) |
| __glxHashInsert(table, random(), i); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 1024; i++) |
| check_table(table, random(), i); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 1024; i++) |
| check_table(table, random(), i); |
| compute_dist(table); |
| __glxHashDestroy(table); |
| |
| printf("\n***** 5000 random integers ****\n"); |
| table = __glxHashCreate(); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 5000; i++) |
| __glxHashInsert(table, random(), i); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 5000; i++) |
| check_table(table, random(), i); |
| srandom(0xbeefbeef); |
| for (i = 0; i < 5000; i++) |
| check_table(table, random(), i); |
| compute_dist(table); |
| __glxHashDestroy(table); |
| |
| return 0; |
| } |
| #endif |
