xserver

xserver with xephyr scale patch
git clone https://git.neptards.moe/u3shit/xserver.git
Log | Files | Refs | README | LICENSE

hashtable.c (7069B)

      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     void            *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           void            *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 = xallocarray(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->key);
     81             free(it->data);
     82             free(it);
     83         }
     84     }
     85     free(ht->buckets);
     86     free(ht);
     87 }
     88 
     89 static Bool
     90 double_size(HashTable ht)
     91 {
     92     struct xorg_list *newBuckets;
     93     int numBuckets = 1 << ht->bucketBits;
     94     int newBucketBits = ht->bucketBits + 1;
     95     int newNumBuckets = 1 << newBucketBits;
     96     int c;
     97 
     98     newBuckets = xallocarray(newNumBuckets, sizeof(*ht->buckets));
     99     if (newBuckets) {
    100         for (c = 0; c < newNumBuckets; ++c) {
    101             xorg_list_init(&newBuckets[c]);
    102         }
    103 
    104         for (c = 0; c < numBuckets; ++c) {
    105             BucketPtr it, tmp;
    106             xorg_list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
    107                 struct xorg_list *newBucket =
    108                     &newBuckets[ht->hash(ht->cdata, it->key, newBucketBits)];
    109                 xorg_list_del(&it->l);
    110                 xorg_list_add(&it->l, newBucket);
    111             }
    112         }
    113         free(ht->buckets);
    114 
    115         ht->buckets = newBuckets;
    116         ht->bucketBits = newBucketBits;
    117         return TRUE;
    118     } else {
    119         return FALSE;
    120     }
    121 }
    122 
    123 void *
    124 ht_add(HashTable ht, const void *key)
    125 {
    126     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
    127     struct xorg_list *bucket = &ht->buckets[index];
    128     BucketRec *elem = calloc(1, sizeof(BucketRec));
    129     if (!elem) {
    130         goto outOfMemory;
    131     }
    132     elem->key = malloc(ht->keySize);
    133     if (!elem->key) {
    134         goto outOfMemory;
    135     }
    136     /* we avoid signaling an out-of-memory error if dataSize is 0 */
    137     elem->data = calloc(1, ht->dataSize);
    138     if (ht->dataSize && !elem->data) {
    139         goto outOfMemory;
    140     }
    141     xorg_list_add(&elem->l, bucket);
    142     ++ht->elements;
    143 
    144     memcpy(elem->key, key, ht->keySize);
    145 
    146     if (ht->elements > 4 * (1 << ht->bucketBits) &&
    147         ht->bucketBits < MAXHASHSIZE) {
    148         if (!double_size(ht)) {
    149             --ht->elements;
    150             xorg_list_del(&elem->l);
    151             goto outOfMemory;
    152         }
    153     }
    154 
    155     /* if memory allocation has failed due to dataSize being 0, return
    156        a "dummy" pointer pointing at the of the key */
    157     return elem->data ? elem->data : ((char*) elem->key + ht->keySize);
    158 
    159  outOfMemory:
    160     if (elem) {
    161         free(elem->key);
    162         free(elem->data);
    163         free(elem);
    164     }
    165 
    166     return NULL;
    167 }
    168 
    169 void
    170 ht_remove(HashTable ht, const void *key)
    171 {
    172     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
    173     struct xorg_list *bucket = &ht->buckets[index];
    174     BucketPtr it;
    175 
    176     xorg_list_for_each_entry(it, bucket, l) {
    177         if (ht->compare(ht->cdata, key, it->key) == 0) {
    178             xorg_list_del(&it->l);
    179             --ht->elements;
    180             free(it->key);
    181             free(it->data);
    182             free(it);
    183             return;
    184         }
    185     }
    186 }
    187 
    188 void *
    189 ht_find(HashTable ht, const void *key)
    190 {
    191     unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
    192     struct xorg_list *bucket = &ht->buckets[index];
    193     BucketPtr it;
    194 
    195     xorg_list_for_each_entry(it, bucket, l) {
    196         if (ht->compare(ht->cdata, key, it->key) == 0) {
    197             return it->data ? it->data : ((char*) it->key + ht->keySize);
    198         }
    199     }
    200 
    201     return NULL;
    202 }
    203 
    204 void
    205 ht_dump_distribution(HashTable ht)
    206 {
    207     int c;
    208     int numBuckets = 1 << ht->bucketBits;
    209     for (c = 0; c < numBuckets; ++c) {
    210         BucketPtr it;
    211         int n = 0;
    212 
    213         xorg_list_for_each_entry(it, &ht->buckets[c], l) {
    214             ++n;
    215         }
    216         printf("%d: %d\n", c, n);
    217     }
    218 }
    219 
    220 /* Picked the function from http://burtleburtle.net/bob/hash/doobs.html by
    221    Bob Jenkins, which is released in public domain */
    222 static CARD32
    223 one_at_a_time_hash(const void *data, int len)
    224 {
    225     CARD32 hash;
    226     int i;
    227     const char *key = data;
    228     for (hash=0, i=0; i<len; ++i) {
    229         hash += key[i];
    230         hash += (hash << 10);
    231         hash ^= (hash >> 6);
    232     }
    233     hash += (hash << 3);
    234     hash ^= (hash >> 11);
    235     hash += (hash << 15);
    236     return hash;
    237 }
    238 
    239 unsigned
    240 ht_generic_hash(void *cdata, const void *ptr, int numBits)
    241 {
    242     HtGenericHashSetupPtr setup = cdata;
    243     return one_at_a_time_hash(ptr, setup->keySize) & ~((~0U) << numBits);
    244 }
    245 
    246 int
    247 ht_generic_compare(void *cdata, const void *l, const void *r)
    248 {
    249     HtGenericHashSetupPtr setup = cdata;
    250     return memcmp(l, r, setup->keySize);
    251 }
    252 
    253 unsigned
    254 ht_resourceid_hash(void * cdata, const void * data, int numBits)
    255 {
    256     const XID* idPtr = data;
    257     XID id = *idPtr & RESOURCE_ID_MASK;
    258     (void) cdata;
    259     return HashResourceID(id, numBits);
    260 }
    261 
    262 int
    263 ht_resourceid_compare(void* cdata, const void* a, const void* b)
    264 {
    265     const XID* xa = a;
    266     const XID* xb = b;
    267     (void) cdata;
    268     return
    269         *xa < *xb ? -1 :
    270         *xa > *xb ? 1 :
    271         0;
    272 }
    273 
    274 void
    275 ht_dump_contents(HashTable ht,
    276                  void (*print_key)(void *opaque, void *key),
    277                  void (*print_value)(void *opaque, void *value),
    278                  void* opaque)
    279 {
    280     int c;
    281     int numBuckets = 1 << ht->bucketBits;
    282     for (c = 0; c < numBuckets; ++c) {
    283         BucketPtr it;
    284         int n = 0;
    285 
    286         printf("%d: ", c);
    287         xorg_list_for_each_entry(it, &ht->buckets[c], l) {
    288             if (n > 0) {
    289                 printf(", ");
    290             }
    291             print_key(opaque, it->key);
    292             printf("->");
    293             print_value(opaque, it->data);
    294             ++n;
    295         }
    296         printf("\n");
    297     }
    298 }