Xext/hashtable.c

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