| 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 | } |