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     return hash;
    102 }
    103 
    104 void *drmHashCreate(void)
    105 {
    106     HashTablePtr table;
    107     int          i;
    108 
    109     table           = drmMalloc(sizeof(*table));
    110     if (!table) return NULL;
    111     table->magic    = HASH_MAGIC;
    112     table->entries  = 0;
    113     table->hits     = 0;
    114     table->partials = 0;
    115     table->misses   = 0;
    116 
    117     for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
    118     return table;
    119 }
    120 
    121 int drmHashDestroy(void *t)
    122 {
    123     HashTablePtr  table = (HashTablePtr)t;
    124     HashBucketPtr bucket;
    125     HashBucketPtr next;
    126     int           i;
    127 
    128     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    129 
    130     for (i = 0; i < HASH_SIZE; i++) {
    131 	for (bucket = table->buckets[i]; bucket;) {
    132 	    next = bucket->next;
    133 	    drmFree(bucket);
    134 	    bucket = next;
    135 	}
    136     }
    137     drmFree(table);
    138     return 0;
    139 }
    140 
    141 /* Find the bucket and organize the list so that this bucket is at the
    142    top. */
    143 
    144 static HashBucketPtr HashFind(HashTablePtr table,
    145 			      unsigned long key, unsigned long *h)
    146 {
    147     unsigned long hash = HashHash(key);
    148     HashBucketPtr prev = NULL;
    149     HashBucketPtr bucket;
    150 
    151     if (h) *h = hash;
    152 
    153     for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
    154 	if (bucket->key == key) {
    155 	    if (prev) {
    156 				/* Organize */
    157 		prev->next           = bucket->next;
    158 		bucket->next         = table->buckets[hash];
    159 		table->buckets[hash] = bucket;
    160 		++table->partials;
    161 	    } else {
    162 		++table->hits;
    163 	    }
    164 	    return bucket;
    165 	}
    166 	prev = bucket;
    167     }
    168     ++table->misses;
    169     return NULL;
    170 }
    171 
    172 int drmHashLookup(void *t, unsigned long key, void **value)
    173 {
    174     HashTablePtr  table = (HashTablePtr)t;
    175     HashBucketPtr bucket;
    176 
    177     if (!table || table->magic != HASH_MAGIC) return -1; /* Bad magic */
    178 
    179     bucket = HashFind(table, key, NULL);
    180     if (!bucket) return 1;	/* Not found */
    181     *value = bucket->value;
    182     return 0;			/* Found */
    183 }
    184 
    185 int drmHashInsert(void *t, unsigned long key, void *value)
    186 {
    187     HashTablePtr  table = (HashTablePtr)t;
    188     HashBucketPtr bucket;
    189     unsigned long hash;
    190 
    191     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    192 
    193     if (HashFind(table, key, &hash)) return 1; /* Already in table */
    194 
    195     bucket               = drmMalloc(sizeof(*bucket));
    196     if (!bucket) return -1;	/* Error */
    197     bucket->key          = key;
    198     bucket->value        = value;
    199     bucket->next         = table->buckets[hash];
    200     table->buckets[hash] = bucket;
    201     return 0;			/* Added to table */
    202 }
    203 
    204 int drmHashDelete(void *t, unsigned long key)
    205 {
    206     HashTablePtr  table = (HashTablePtr)t;
    207     unsigned long hash;
    208     HashBucketPtr bucket;
    209 
    210     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    211 
    212     bucket = HashFind(table, key, &hash);
    213 
    214     if (!bucket) return 1;	/* Not found */
    215 
    216     table->buckets[hash] = bucket->next;
    217     drmFree(bucket);
    218     return 0;
    219 }
    220 
    221 int drmHashNext(void *t, unsigned long *key, void **value)
    222 {
    223     HashTablePtr  table = (HashTablePtr)t;
    224 
    225     while (table->p0 < HASH_SIZE) {
    226 	if (table->p1) {
    227 	    *key       = table->p1->key;
    228 	    *value     = table->p1->value;
    229 	    table->p1  = table->p1->next;
    230 	    return 1;
    231 	}
    232 	table->p1 = table->buckets[table->p0];
    233 	++table->p0;
    234     }
    235     return 0;
    236 }
    237 
    238 int drmHashFirst(void *t, unsigned long *key, void **value)
    239 {
    240     HashTablePtr  table = (HashTablePtr)t;
    241 
    242     if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
    243 
    244     table->p0 = 0;
    245     table->p1 = table->buckets[0];
    246     return drmHashNext(table, key, value);
    247 }
    248