Xext/hashtable.c

   1 #ifdef HAVE_DIX_CONFIG_H
   2 #include <dix-config.h>
   3 #endif
   4
   5 #include <stdlib.h>
   6 #include "misc.h"
   7 #include "hashtable.h"
   8
   9 /* HashResourceID */
  10 #include "resource.h"
  11
  12 #define INITHASHSIZE 6
  13 #define MAXHASHSIZE 11
  14
  15 struct HashTableRec {
  16     int             keySize;
  17     int             dataSize;
  18
  19     int             elements;   /* number of elements inserted */
  20     int             bucketBits; /* number of buckets is 1 << bucketBits */
  21     struct xorg_list *buckets;  /* array of bucket list heads */
  22
  23     HashFunc        hash;
  24     HashCompareFunc compare;
  25
  26     pointer         cdata;
  27 };
  28
  29 typedef struct {
  30     struct xorg_list l;
  31     void *key;
  32     void *data;
  33 } BucketRec, *BucketPtr;
  34
  35 HashTable
  36 ht_create(int             keySize,
  37           int             dataSize,
  38           HashFunc        hash,
  39           HashCompareFunc compare,
  40           pointer         cdata)
  41 {
  42     int c;
  43     int numBuckets;
  44     HashTable ht = malloc(sizeof(struct HashTableRec));
  45
  46     if (!ht) {
  47         return NULL;
  48     }
  49
  50     ht->keySize = keySize;
  51     ht->dataSize = dataSize;
  52     ht->hash = hash;
  53     ht->compare = compare;
  54     ht->elements = 0;
  55     ht->bucketBits = INITHASHSIZE;
  56     numBuckets = 1 << ht->bucketBits;
  57     ht->buckets = malloc(numBuckets * sizeof(*ht->buckets));
  58     ht->cdata = cdata;
  59
  60     if (ht->buckets) {
  61         for (c = 0; c < numBuckets; ++c) {
  62             xorg_list_init(&ht->buckets[c]);
  63         }
  64         return ht;
  65     } else {
  66         free(ht);
  67         return NULL;
  68     }
  69 }
  70
  71 void
  72 ht_destroy(HashTable ht)
  73 {
  74     int c;
  75     BucketPtr it, tmp;
  76     int numBuckets = 1 << ht->bucketBits;
  77     for (c = 0; c < numBuckets; ++c) {
  78         xorg_list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
  79             xorg_list_del(&it->l);
  80             free(it);
  81         }
  82     }
  83     free(ht->buckets);
  84 }
  85
  86 static Bool
  87 double_size(HashTable ht)
  88 {
  89     struct xorg_list *newBuckets;
  90     int numBuckets = 1 << ht->bucketBits;
  91     int newBucketBits = ht->bucketBits + 1;
  92     int newNumBuckets = 1 << newBucketBits;
  93     int c;
  94
  95     newBuckets = malloc(newNumBuckets * sizeof(*ht->buckets));
  96     if (newBuckets) {
  97         for (c = 0; c < newNumBuckets; ++c) {
  98             xorg_list_init(&newBuckets[c]);
  99         }
 100
 101         for (c = 0; c < numBuckets; ++c) {
 102             BucketPtr it, tmp;
 103             xorg_list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
 104                 struct xorg_list *newBucket =
 105                     &newBuckets[ht->hash(ht->cdata, it->key, newBucketBits)];
 106                 xorg_list_del(&it->l);
 107                 xorg_list_add(&it->l, newBucket);
 108             }
 109         }
 110         free(ht->buckets);
 111
 112         ht->buckets = newBuckets;
 113         ht->bucketBits = newBucketBits;
 114         return TRUE;
 115     } else {
 116         return FALSE;
 117     }
 118 }
 119
 120 pointer
 121 ht_add(HashTable ht, pointer key)
 122 {
 123     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
 124     struct xorg_list *bucket = &ht->buckets[index];
 125     BucketRec *elem = calloc(1, sizeof(BucketRec));
 126     if (!elem) {
 127         goto outOfMemory;
 128     }
 129     elem->key = malloc(ht->keySize);
 130     if (!elem->key) {
 131         goto outOfMemory;
 132     }
 133     /* we avoid signaling an out-of-memory error if dataSize is 0 */
 134     elem->data = calloc(1, ht->dataSize);
 135     if (ht->dataSize && !elem->data) {
 136         goto outOfMemory;
 137     }
 138     xorg_list_add(&elem->l, bucket);
 139     ++ht->elements;
 140
 141     memcpy(elem->key, key, ht->keySize);
 142
 143     if (ht->elements > 4 * (1 << ht->bucketBits) &&
 144         ht->bucketBits < MAXHASHSIZE) {
 145         if (!double_size(ht)) {
 146             --ht->elements;
 147             xorg_list_del(&elem->l);
 148             goto outOfMemory;
 149         }
 150     }
 151
 152     /* if memory allocation has failed due to dataSize being 0, return
 153        a "dummy" pointer pointing at the of the key */
 154     return elem->data ? elem->data : ((char*) elem->key + ht->keySize);
 155
 156  outOfMemory:
 157     if (elem) {
 158         free(elem->key);
 159         free(elem->data);
 160         free(elem);
 161     }
 162
 163     return NULL;
 164 }
 165
 166 void
 167 ht_remove(HashTable ht, pointer key)
 168 {
 169     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
 170     struct xorg_list *bucket = &ht->buckets[index];
 171     BucketPtr it;
 172
 173     xorg_list_for_each_entry(it, bucket, l) {
 174         if (ht->compare(ht->cdata, key, it->key) == 0) {
 175             xorg_list_del(&it->l);
 176             --ht->elements;
 177             free(it->key);
 178             free(it->data);
 179             free(it);
 180             return;
 181         }
 182     }
 183 }
 184
 185 pointer
 186 ht_find(HashTable ht, pointer key)
 187 {
 188     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
 189     struct xorg_list *bucket = &ht->buckets[index];
 190     BucketPtr it;
 191
 192     xorg_list_for_each_entry(it, bucket, l) {
 193         if (ht->compare(ht->cdata, key, it->key) == 0) {
 194             return it->data ? it->data : ((char*) it->key + ht->keySize);
 195         }
 196     }
 197
 198     return NULL;
 199 }
 200
 201 void
 202 ht_dump_distribution(HashTable ht)
 203 {
 204     int c;
 205     int numBuckets = 1 << ht->bucketBits;
 206     for (c = 0; c < numBuckets; ++c) {
 207         BucketPtr it;
 208         int n = 0;
 209
 210         xorg_list_for_each_entry(it, &ht->buckets[c], l) {
 211             ++n;
 212         }
 213         printf("%d: %d\n", c, n);
 214     }
 215 }
 216
 217 /* Picked the function from http://burtleburtle.net/bob/hash/doobs.html by
 218    Bob Jenkins, which is released in public domain */
 219 static CARD32
 220 one_at_a_time_hash(const void *data, int len)
 221 {
 222     CARD32 hash;
 223     int i;
 224     const char *key = data;
 225     for (hash=0, i=0; i<len; ++i) {
 226         hash += key[i];
 227         hash += (hash << 10);
 228         hash ^= (hash >> 6);
 229     }
 230     hash += (hash << 3);
 231     hash ^= (hash >> 11);
 232     hash += (hash << 15);
 233     return hash;
 234 }
 235
 236 unsigned
 237 ht_generic_hash(void *cdata, const void *ptr, int numBits)
 238 {
 239     HtGenericHashSetupPtr setup = cdata;
 240     return one_at_a_time_hash(ptr, setup->keySize) & ~((~0) << numBits);
 241 }
 242
 243 int
 244 ht_generic_compare(void *cdata, const void *l, const void *r)
 245 {
 246     HtGenericHashSetupPtr setup = cdata;
 247     return memcmp(l, r, setup->keySize);
 248 }
 249
 250 unsigned
 251 ht_resourceid_hash(void * cdata, const void * data, int numBits)
 252 {
 253     const XID* idPtr = data;
 254     XID id = *idPtr & RESOURCE_ID_MASK;
 255     (void) cdata;
 256     return HashResourceID(id, numBits);
 257 }
 258
 259 int
 260 ht_resourceid_compare(void* cdata, const void* a, const void* b)
 261 {
 262     const XID* xa = a;
 263     const XID* xb = b;
 264     (void) cdata;
 265     return
 266         *xa < *xb ? -1 :
 267         *xa > *xb ? 1 :
 268         0;
 269 }
 270
 271 void
 272 ht_dump_contents(HashTable ht,
 273                  void (*print_key)(void *opaque, void *key),
 274                  void (*print_value)(void *opaque, void *value),
 275                  void* opaque)
 276 {
 277     int c;
 278     int numBuckets = 1 << ht->bucketBits;
 279     for (c = 0; c < numBuckets; ++c) {
 280         BucketPtr it;
 281         int n = 0;
 282
 283         printf("%d: ", c);
 284         xorg_list_for_each_entry(it, &ht->buckets[c], l) {
 285             if (n > 0) {
 286                 printf(", ");
 287             }
 288             print_key(opaque, it->key);
 289             printf("->");
 290             print_value(opaque, it->data);
 291             ++n;
 292         }
 293         printf("\n");
 294     }
 295 }