Home | History | Annotate | Download | only in libdrm 
      1 /* xf86drmHash.c -- Small hash table support for integer -> integer mapping
      2  * Created: Sun Apr 18 09:35:45 1999 by faith (at) precisioninsight.com
      3  *
      4  * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
      5  * All Rights Reserved.
      6  *
      7  * Permission is hereby granted, free of charge, to any person obtaining a
      8  * copy of this software and associated documentation files (the "Software"),
      9  * to deal in the Software without restriction, including without limitation
     10  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
     11  * and/or sell copies of the Software, and to permit persons to whom the
     12  * Software is furnished to do so, subject to the following conditions:
     13  *
     14  * The above copyright notice and this permission notice (including the next
     15  * paragraph) shall be included in all copies or substantial portions of the
     16  * Software.
     17  *
     18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
     21  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
     22  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
     23  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
     24  * DEALINGS IN THE SOFTWARE.
     25  *
     26  * Authors: Rickard E. (Rik) Faith <faith (at) valinux.com>
     27  *
     28  * DESCRIPTION
     29  *
     30  * This file contains a straightforward implementation of a fixed-sized
     31  * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
     32  * collision resolution.  There are two potentially interesting things
     33  * about this implementation:
     34  *
     35  * 1) The table is power-of-two sized.  Prime sized tables are more
     36  * traditional, but do not have a significant advantage over power-of-two
     37  * sized table, especially when double hashing is not used for collision
     38  * resolution.
     39  *
     40  * 2) The hash computation uses a table of random integers [Hanson97,
     41  * pp. 39-41].
     42  *
     43  * FUTURE ENHANCEMENTS
     44  *
     45  * With a table size of 512, the current implementation is sufficient for a
     46  * few hundred keys.  Since this is well above the expected size of the
     47  * tables for which this implementation was designed, the implementation of
     48  * dynamic hash tables was postponed until the need arises.  A common (and
     49  * naive) approach to dynamic hash table implementation simply creates a
     50  * new hash table when necessary, rehashes all the data into the new table,
     51  * and destroys the old table.  The approach in [Larson88] is superior in
     52  * two ways: 1) only a portion of the table is expanded when needed,
     53  * distributing the expansion cost over several insertions, and 2) portions
     54  * of the table can be locked, enabling a scalable thread-safe
     55  * implementation.
     56  *
     57  * REFERENCES
     58  *
     59  * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
     60  * Techniques for Creating Reusable Software.  Reading, Massachusetts:
     61  * Addison-Wesley, 1997.
     62  *
     63  * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
     64  * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
     65  *
     66  * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
     67  * 1988, pp. 446-457.
     68  *
     69  */
     70 
     71 #include <stdio.h>
     72 #include <stdlib.h>
     73 
     74 #include "xf86drm.h"
     75 #include "xf86drmHash.h"
     76 
     77 #define HASH_MAGIC 0xdeadbeef
     78 
     79 static unsigned long HashHash(unsigned long key)
     80 {
     81     unsigned long        hash = 0;
     82     unsigned long        tmp  = key;
     83     static int           init = 0;
     84     static unsigned long scatter[256];
     85     int                  i;
     86 
     87     if (!init) {
     88 	void *state;
     89 	state = drmRandomCreate(37);
     90 	for (i = 0; i < 256; i++) scatter[i] = drmRandom(state);
     91 	drmRandomDestroy(state);
     92 	++init;
     93     }
     94 
     95     while (tmp) {
     96 	hash = (hash << 1) + scatter[tmp & 0xff];
     97 	tmp >>= 8;
     98     }
     99 
    100     hash %= HASH_SIZE;
    101 #if DEBUG
    102     printf( "Hash(%lu) = %lu\n", key, hash);
    103 #endif
    104     return hash;
    105 }
    106 
    107 void *drmHashCreate(void)
    108 {
    109     HashTablePtr table;
    110     int          i;
    111 
    112     table           = drmMalloc(sizeof(*table));
    113     if (!table) return NULL;
    114     table->magic    = HASH_MAGIC;
    115     table->entries  = 0;
    116     table->hits     = 0;
    117     table->partials = 0;
    118     table->misses   = 0;
    119 
    120     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
    121     return table;
    122 }
    123 
    124 int drmHashDestroy(void *t)
    125 {
    126     HashTablePtr  table = (HashTablePtr)t;
    127     HashBucketPtr bucket;
    128     HashBucketPtr next;
    129     int           i;
    130 
    131     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    132 
    133     for (i = 0; i < HASH_SIZE; i++) {
    134 	for (bucket = table->buckets[i]; bucket;) {
    135 	    next = bucket->next;
    136 	    drmFree(bucket);
    137 	    bucket = next;
    138 	}
    139     }
    140     drmFree(table);
    141     return 0;
    142 }
    143 
    144 /* Find the bucket and organize the list so that this bucket is at the
    145    top. */
    146 
    147 static HashBucketPtr HashFind(HashTablePtr table,
    148 			      unsigned long key, unsigned long *h)
    149 {
    150     unsigned long hash = HashHash(key);
    151     HashBucketPtr prev = NULL;
    152     HashBucketPtr bucket;
    153 
    154     if (h) *h = hash;
    155 
    156     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
    157 	if (bucket->key == key) {
    158 	    if (prev) {
    159 				/* Organize */
    160 		prev->next           = bucket->next;
    161 		bucket->next         = table->buckets[hash];
    162 		table->buckets[hash] = bucket;
    163 		++table->partials;
    164 	    } else {
    165 		++table->hits;
    166 	    }
    167 	    return bucket;
    168 	}
    169 	prev = bucket;
    170     }
    171     ++table->misses;
    172     return NULL;
    173 }
    174 
    175 int drmHashLookup(void *t, unsigned long key, void **value)
    176 {
    177     HashTablePtr  table = (HashTablePtr)t;
    178     HashBucketPtr bucket;
    179 
    180     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
    181 
    182     bucket = HashFind(table, key, NULL);
    183     if (!bucket) return 1;	/* Not found */
    184     *value = bucket->value;
    185     return 0;			/* Found */
    186 }
    187 
    188 int drmHashInsert(void *t, unsigned long key, void *value)
    189 {
    190     HashTablePtr  table = (HashTablePtr)t;
    191     HashBucketPtr bucket;
    192     unsigned long hash;
    193 
    194     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    195 
    196     if (HashFind(table, key, &hash)) return 1; /* Already in table */
    197 
    198     bucket               = drmMalloc(sizeof(*bucket));
    199     if (!bucket) return -1;	/* Error */
    200     bucket->key          = key;
    201     bucket->value        = value;
    202     bucket->next         = table->buckets[hash];
    203     table->buckets[hash] = bucket;
    204 #if DEBUG
    205     printf("Inserted %lu at %lu/%p\n", key, hash, bucket);
    206 #endif
    207     return 0;			/* Added to table */
    208 }
    209 
    210 int drmHashDelete(void *t, unsigned long key)
    211 {
    212     HashTablePtr  table = (HashTablePtr)t;
    213     unsigned long hash;
    214     HashBucketPtr bucket;
    215 
    216     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    217 
    218     bucket = HashFind(table, key, &hash);
    219 
    220     if (!bucket) return 1;	/* Not found */
    221 
    222     table->buckets[hash] = bucket->next;
    223     drmFree(bucket);
    224     return 0;
    225 }
    226 
    227 int drmHashNext(void *t, unsigned long *key, void **value)
    228 {
    229     HashTablePtr  table = (HashTablePtr)t;
    230 
    231     while (table->p0 < HASH_SIZE) {
    232 	if (table->p1) {
    233 	    *key       = table->p1->key;
    234 	    *value     = table->p1->value;
    235 	    table->p1  = table->p1->next;
    236 	    return 1;
    237 	}
    238 	table->p1 = table->buckets[table->p0];
    239 	++table->p0;
    240     }
    241     return 0;
    242 }
    243 
    244 int drmHashFirst(void *t, unsigned long *key, void **value)
    245 {
    246     HashTablePtr  table = (HashTablePtr)t;
    247 
    248     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    249 
    250     table->p0 = 0;
    251     table->p1 = table->buckets[0];
    252     return drmHashNext(table, key, value);
    253 }
    254