Commit | Line | Data |
---|---|---|
a09e091a JB |
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 | pointer 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 | pointer 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 = malloc(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); | |
81 | } | |
82 | } | |
83 | free(ht->buckets); | |
84 | } | |
85 | ||
86 | static Bool | |
87 | double_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 = malloc(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 | ||
120 | pointer | |
121 | ht_add(HashTable ht, pointer 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 | ||
166 | void | |
167 | ht_remove(HashTable ht, pointer 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 | ||
185 | pointer | |
186 | ht_find(HashTable ht, pointer 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 | ||
201 | void | |
202 | ht_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 */ | |
219 | static CARD32 | |
220 | one_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 | ||
236 | unsigned | |
237 | ht_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 | ||
243 | int | |
244 | ht_generic_compare(void *cdata, const void *l, const void *r) | |
245 | { | |
246 | HtGenericHashSetupPtr setup = cdata; | |
247 | return memcmp(l, r, setup->keySize); | |
248 | } | |
249 | ||
250 | unsigned | |
251 | ht_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 | ||
259 | int | |
260 | ht_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 | ||
271 | void | |
272 | ht_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 | } |