Back to index

libdrm  2.4.37
xf86drmHash.c
Go to the documentation of this file.
00001 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping
00002  * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
00003  *
00004  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
00005  * All Rights Reserved.
00006  *
00007  * Permission is hereby granted, free of charge, to any person obtaining a
00008  * copy of this software and associated documentation files (the "Software"),
00009  * to deal in the Software without restriction, including without limitation
00010  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
00011  * and/or sell copies of the Software, and to permit persons to whom the
00012  * Software is furnished to do so, subject to the following conditions:
00013  *
00014  * The above copyright notice and this permission notice (including the next
00015  * paragraph) shall be included in all copies or substantial portions of the
00016  * Software.
00017  *
00018  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00019  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00020  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
00021  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
00022  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
00023  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
00024  * DEALINGS IN THE SOFTWARE.
00025  *
00026  * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
00027  *
00028  * DESCRIPTION
00029  *
00030  * This file contains a straightforward implementation of a fixed-sized
00031  * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
00032  * collision resolution.  There are two potentially interesting things
00033  * about this implementation:
00034  *
00035  * 1) The table is power-of-two sized.  Prime sized tables are more
00036  * traditional, but do not have a significant advantage over power-of-two
00037  * sized table, especially when double hashing is not used for collision
00038  * resolution.
00039  *
00040  * 2) The hash computation uses a table of random integers [Hanson97,
00041  * pp. 39-41].
00042  *
00043  * FUTURE ENHANCEMENTS
00044  *
00045  * With a table size of 512, the current implementation is sufficient for a
00046  * few hundred keys.  Since this is well above the expected size of the
00047  * tables for which this implementation was designed, the implementation of
00048  * dynamic hash tables was postponed until the need arises.  A common (and
00049  * naive) approach to dynamic hash table implementation simply creates a
00050  * new hash table when necessary, rehashes all the data into the new table,
00051  * and destroys the old table.  The approach in [Larson88] is superior in
00052  * two ways: 1) only a portion of the table is expanded when needed,
00053  * distributing the expansion cost over several insertions, and 2) portions
00054  * of the table can be locked, enabling a scalable thread-safe
00055  * implementation.
00056  *
00057  * REFERENCES
00058  *
00059  * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
00060  * Techniques for Creating Reusable Software.  Reading, Massachusetts:
00061  * Addison-Wesley, 1997.
00062  *
00063  * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
00064  * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
00065  *
00066  * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
00067  * 1988, pp. 446-457.
00068  *
00069  */
00070 
00071 #include <stdio.h>
00072 #include <stdlib.h>
00073 
00074 #define HASH_MAIN 0
00075 
00076 #if !HASH_MAIN
00077 # include "xf86drm.h"
00078 #endif
00079 
00080 #define HASH_MAGIC 0xdeadbeef
00081 #define HASH_DEBUG 0
00082 #define HASH_SIZE  512             /* Good for about 100 entries */
00083                             /* If you change this value, you probably
00084                                    have to change the HashHash hashing
00085                                    function! */
00086 
00087 #if HASH_MAIN
00088 #define HASH_ALLOC malloc
00089 #define HASH_FREE  free
00090 #define HASH_RANDOM_DECL
00091 #define HASH_RANDOM_INIT(seed)  srandom(seed)
00092 #define HASH_RANDOM             random()
00093 #define HASH_RANDOM_DESTROY
00094 #else
00095 #define HASH_ALLOC drmMalloc
00096 #define HASH_FREE  drmFree
00097 #define HASH_RANDOM_DECL        void *state
00098 #define HASH_RANDOM_INIT(seed)  state = drmRandomCreate(seed)
00099 #define HASH_RANDOM             drmRandom(state)
00100 #define HASH_RANDOM_DESTROY     drmRandomDestroy(state)
00101 
00102 #endif
00103 
00104 typedef struct HashBucket {
00105     unsigned long     key;
00106     void              *value;
00107     struct HashBucket *next;
00108 } HashBucket, *HashBucketPtr;
00109 
00110 typedef struct HashTable {
00111     unsigned long    magic;
00112     unsigned long    entries;
00113     unsigned long    hits;  /* At top of linked list */
00114     unsigned long    partials;     /* Not at top of linked list */
00115     unsigned long    misses;       /* Not in table */
00116     HashBucketPtr    buckets[HASH_SIZE];
00117     int              p0;
00118     HashBucketPtr    p1;
00119 } HashTable, *HashTablePtr;
00120 
00121 #if HASH_MAIN
00122 extern void *drmHashCreate(void);
00123 extern int  drmHashDestroy(void *t);
00124 extern int  drmHashLookup(void *t, unsigned long key, unsigned long *value);
00125 extern int  drmHashInsert(void *t, unsigned long key, unsigned long value);
00126 extern int  drmHashDelete(void *t, unsigned long key);
00127 #endif
00128 
00129 static unsigned long HashHash(unsigned long key)
00130 {
00131     unsigned long        hash = 0;
00132     unsigned long        tmp  = key;
00133     static int           init = 0;
00134     static unsigned long scatter[256];
00135     int                  i;
00136 
00137     if (!init) {
00138        HASH_RANDOM_DECL;
00139        HASH_RANDOM_INIT(37);
00140        for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
00141        HASH_RANDOM_DESTROY;
00142        ++init;
00143     }
00144 
00145     while (tmp) {
00146        hash = (hash << 1) + scatter[tmp & 0xff];
00147        tmp >>= 8;
00148     }
00149 
00150     hash %= HASH_SIZE;
00151 #if HASH_DEBUG
00152     printf( "Hash(%d) = %d\n", key, hash);
00153 #endif
00154     return hash;
00155 }
00156 
00157 void *drmHashCreate(void)
00158 {
00159     HashTablePtr table;
00160     int          i;
00161 
00162     table           = HASH_ALLOC(sizeof(*table));
00163     if (!table) return NULL;
00164     table->magic    = HASH_MAGIC;
00165     table->entries  = 0;
00166     table->hits     = 0;
00167     table->partials = 0;
00168     table->misses   = 0;
00169 
00170     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
00171     return table;
00172 }
00173 
00174 int drmHashDestroy(void *t)
00175 {
00176     HashTablePtr  table = (HashTablePtr)t;
00177     HashBucketPtr bucket;
00178     HashBucketPtr next;
00179     int           i;
00180 
00181     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
00182 
00183     for (i = 0; i < HASH_SIZE; i++) {
00184        for (bucket = table->buckets[i]; bucket;) {
00185            next = bucket->next;
00186            HASH_FREE(bucket);
00187            bucket = next;
00188        }
00189     }
00190     HASH_FREE(table);
00191     return 0;
00192 }
00193 
00194 /* Find the bucket and organize the list so that this bucket is at the
00195    top. */
00196 
00197 static HashBucketPtr HashFind(HashTablePtr table,
00198                            unsigned long key, unsigned long *h)
00199 {
00200     unsigned long hash = HashHash(key);
00201     HashBucketPtr prev = NULL;
00202     HashBucketPtr bucket;
00203 
00204     if (h) *h = hash;
00205 
00206     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
00207        if (bucket->key == key) {
00208            if (prev) {
00209                             /* Organize */
00210               prev->next           = bucket->next;
00211               bucket->next         = table->buckets[hash];
00212               table->buckets[hash] = bucket;
00213               ++table->partials;
00214            } else {
00215               ++table->hits;
00216            }
00217            return bucket;
00218        }
00219        prev = bucket;
00220     }
00221     ++table->misses;
00222     return NULL;
00223 }
00224 
00225 int drmHashLookup(void *t, unsigned long key, void **value)
00226 {
00227     HashTablePtr  table = (HashTablePtr)t;
00228     HashBucketPtr bucket;
00229 
00230     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
00231 
00232     bucket = HashFind(table, key, NULL);
00233     if (!bucket) return 1;  /* Not found */
00234     *value = bucket->value;
00235     return 0;               /* Found */
00236 }
00237 
00238 int drmHashInsert(void *t, unsigned long key, void *value)
00239 {
00240     HashTablePtr  table = (HashTablePtr)t;
00241     HashBucketPtr bucket;
00242     unsigned long hash;
00243 
00244     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
00245 
00246     if (HashFind(table, key, &hash)) return 1; /* Already in table */
00247 
00248     bucket               = HASH_ALLOC(sizeof(*bucket));
00249     if (!bucket) return -1; /* Error */
00250     bucket->key          = key;
00251     bucket->value        = value;
00252     bucket->next         = table->buckets[hash];
00253     table->buckets[hash] = bucket;
00254 #if HASH_DEBUG
00255     printf("Inserted %d at %d/%p\n", key, hash, bucket);
00256 #endif
00257     return 0;               /* Added to table */
00258 }
00259 
00260 int drmHashDelete(void *t, unsigned long key)
00261 {
00262     HashTablePtr  table = (HashTablePtr)t;
00263     unsigned long hash;
00264     HashBucketPtr bucket;
00265 
00266     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
00267 
00268     bucket = HashFind(table, key, &hash);
00269 
00270     if (!bucket) return 1;  /* Not found */
00271 
00272     table->buckets[hash] = bucket->next;
00273     HASH_FREE(bucket);
00274     return 0;
00275 }
00276 
00277 int drmHashNext(void *t, unsigned long *key, void **value)
00278 {
00279     HashTablePtr  table = (HashTablePtr)t;
00280 
00281     while (table->p0 < HASH_SIZE) {
00282        if (table->p1) {
00283            *key       = table->p1->key;
00284            *value     = table->p1->value;
00285            table->p1  = table->p1->next;
00286            return 1;
00287        }
00288        table->p1 = table->buckets[table->p0];
00289        ++table->p0;
00290     }
00291     return 0;
00292 }
00293 
00294 int drmHashFirst(void *t, unsigned long *key, void **value)
00295 {
00296     HashTablePtr  table = (HashTablePtr)t;
00297 
00298     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
00299 
00300     table->p0 = 0;
00301     table->p1 = table->buckets[0];
00302     return drmHashNext(table, key, value);
00303 }
00304 
00305 #if HASH_MAIN
00306 #define DIST_LIMIT 10
00307 static int dist[DIST_LIMIT];
00308 
00309 static void clear_dist(void) {
00310     int i;
00311 
00312     for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0;
00313 }
00314 
00315 static int count_entries(HashBucketPtr bucket)
00316 {
00317     int count = 0;
00318 
00319     for (; bucket; bucket = bucket->next) ++count;
00320     return count;
00321 }
00322 
00323 static void update_dist(int count)
00324 {
00325     if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1];
00326     else                     ++dist[count];
00327 }
00328 
00329 static void compute_dist(HashTablePtr table)
00330 {
00331     int           i;
00332     HashBucketPtr bucket;
00333 
00334     printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
00335           table->entries, table->hits, table->partials, table->misses);
00336     clear_dist();
00337     for (i = 0; i < HASH_SIZE; i++) {
00338        bucket = table->buckets[i];
00339        update_dist(count_entries(bucket));
00340     }
00341     for (i = 0; i < DIST_LIMIT; i++) {
00342        if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]);
00343        else                   printf("other %10d\n", dist[i]);
00344     }
00345 }
00346 
00347 static void check_table(HashTablePtr table,
00348                      unsigned long key, unsigned long value)
00349 {
00350     unsigned long retval  = 0;
00351     int           retcode = drmHashLookup(table, key, &retval);
00352 
00353     switch (retcode) {
00354     case -1:
00355        printf("Bad magic = 0x%08lx:"
00356               " key = %lu, expected = %lu, returned = %lu\n",
00357               table->magic, key, value, retval);
00358        break;
00359     case 1:
00360        printf("Not found: key = %lu, expected = %lu returned = %lu\n",
00361               key, value, retval);
00362        break;
00363     case 0:
00364        if (value != retval)
00365            printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
00366                  key, value, retval);
00367        break;
00368     default:
00369        printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
00370               retcode, key, value, retval);
00371        break;
00372     }
00373 }
00374 
00375 int main(void)
00376 {
00377     HashTablePtr table;
00378     int          i;
00379 
00380     printf("\n***** 256 consecutive integers ****\n");
00381     table = drmHashCreate();
00382     for (i = 0; i < 256; i++) drmHashInsert(table, i, i);
00383     for (i = 0; i < 256; i++) check_table(table, i, i);
00384     for (i = 256; i >= 0; i--) check_table(table, i, i);
00385     compute_dist(table);
00386     drmHashDestroy(table);
00387 
00388     printf("\n***** 1024 consecutive integers ****\n");
00389     table = drmHashCreate();
00390     for (i = 0; i < 1024; i++) drmHashInsert(table, i, i);
00391     for (i = 0; i < 1024; i++) check_table(table, i, i);
00392     for (i = 1024; i >= 0; i--) check_table(table, i, i);
00393     compute_dist(table);
00394     drmHashDestroy(table);
00395 
00396     printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
00397     table = drmHashCreate();
00398     for (i = 0; i < 1024; i++) drmHashInsert(table, i*4096, i);
00399     for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
00400     for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
00401     compute_dist(table);
00402     drmHashDestroy(table);
00403 
00404     printf("\n***** 1024 random integers ****\n");
00405     table = drmHashCreate();
00406     srandom(0xbeefbeef);
00407     for (i = 0; i < 1024; i++) drmHashInsert(table, random(), i);
00408     srandom(0xbeefbeef);
00409     for (i = 0; i < 1024; i++) check_table(table, random(), i);
00410     srandom(0xbeefbeef);
00411     for (i = 0; i < 1024; i++) check_table(table, random(), i);
00412     compute_dist(table);
00413     drmHashDestroy(table);
00414 
00415     printf("\n***** 5000 random integers ****\n");
00416     table = drmHashCreate();
00417     srandom(0xbeefbeef);
00418     for (i = 0; i < 5000; i++) drmHashInsert(table, random(), i);
00419     srandom(0xbeefbeef);
00420     for (i = 0; i < 5000; i++) check_table(table, random(), i);
00421     srandom(0xbeefbeef);
00422     for (i = 0; i < 5000; i++) check_table(table, random(), i);
00423     compute_dist(table);
00424     drmHashDestroy(table);
00425 
00426     return 0;
00427 }
00428 #endif