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->key);
81            free(it->data);
82            free(it);
83        }
84    }
85    free(ht->buckets);
86    free(ht);
87}
88
89static Bool
90double_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
123void *
124ht_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
169void
170ht_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
188void *
189ht_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
204void
205ht_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 */
222static CARD32
223one_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
239unsigned
240ht_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
246int
247ht_generic_compare(void *cdata, const void *l, const void *r)
248{
249    HtGenericHashSetupPtr setup = cdata;
250    return memcmp(l, r, setup->keySize);
251}
252
253unsigned
254ht_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
262int
263ht_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
274void
275ht_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}
299