hashtable.c revision 35c4bbdf 
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
15struct 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
29typedef struct {
30    struct xorg_list l;
31    void *key;
32    void *data;
33} BucketRec, *BucketPtr;
34
35HashTable
36ht_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
71void
72ht_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
86static Bool
87double_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 = xallocarray(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
120void *
121ht_add(HashTable ht, const void *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
166void
167ht_remove(HashTable ht, const void *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
185void *
186ht_find(HashTable ht, const void *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
201void
202ht_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 */
219static CARD32
220one_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
236unsigned
237ht_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
243int
244ht_generic_compare(void *cdata, const void *l, const void *r)
245{
246    HtGenericHashSetupPtr setup = cdata;
247    return memcmp(l, r, setup->keySize);
248}
249
250unsigned
251ht_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
259int
260ht_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
271void
272ht_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}
296