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
ht_create(int keySize,int dataSize,HashFunc hash,HashCompareFunc compare,void * cdata)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
ht_destroy(HashTable ht)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
double_size(HashTable ht)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 *
ht_add(HashTable ht,const void * key)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
ht_remove(HashTable ht,const void * key)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 *
ht_find(HashTable ht,const void * key)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
ht_dump_distribution(HashTable ht)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
one_at_a_time_hash(const void * data,int len)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
ht_generic_hash(void * cdata,const void * ptr,int numBits)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) & ~((~0) << numBits);
244 }
245
246 int
ht_generic_compare(void * cdata,const void * l,const void * r)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
ht_resourceid_hash(void * cdata,const void * data,int numBits)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
ht_resourceid_compare(void * cdata,const void * a,const void * b)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
ht_dump_contents(HashTable ht,void (* print_key)(void * opaque,void * key),void (* print_value)(void * opaque,void * value),void * opaque)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 }
299