1 /************************************************************************** 2 * 3 * Copyright 2007 VMware, Inc. 4 * All Rights Reserved. 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a 7 * copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sub license, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice (including the 15 * next paragraph) shall be included in all copies or substantial portions 16 * of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. 21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR 22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 * 26 **************************************************************************/ 27 28 /* 29 * Authors: 30 * Zack Rusin <zackr (at) vmware.com> 31 */ 32 33 #ifdef HAVE_CONFIG_H 34 #include "config.h" 35 #endif 36 37 #include "util_hash.h" 38 39 #include <stdlib.h> 40 #include <assert.h> 41 42 #define MAX(a, b) ((a > b) ? (a) : (b)) 43 44 static const int MinNumBits = 4; 45 46 static const unsigned char prime_deltas[] = { 47 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 48 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 49 }; 50 51 static int primeForNumBits(int numBits) 52 { 53 return (1 << numBits) + prime_deltas[numBits]; 54 } 55 56 /* Returns the smallest integer n such that 57 primeForNumBits(n) >= hint. 58 */ 59 static int countBits(int hint) 60 { 61 int numBits = 0; 62 int bits = hint; 63 64 while (bits > 1) { 65 bits >>= 1; 66 numBits++; 67 } 68 69 if (numBits >= (int)sizeof(prime_deltas)) { 70 numBits = sizeof(prime_deltas) - 1; 71 } else if (primeForNumBits(numBits) < hint) { 72 ++numBits; 73 } 74 return numBits; 75 } 76 77 struct util_node { 78 struct util_node *next; 79 unsigned key; 80 void *value; 81 }; 82 83 struct util_hash_data { 84 struct util_node *fakeNext; 85 struct util_node **buckets; 86 int size; 87 int nodeSize; 88 short userNumBits; 89 short numBits; 90 int numBuckets; 91 }; 92 93 struct util_hash { 94 union { 95 struct util_hash_data *d; 96 struct util_node *e; 97 } data; 98 }; 99 100 static void *util_data_allocate_node(struct util_hash_data *hash) 101 { 102 return malloc(hash->nodeSize); 103 } 104 105 static void util_free_node(struct util_node *node) 106 { 107 free(node); 108 } 109 110 static struct util_node * 111 util_hash_create_node(struct util_hash *hash, 112 unsigned akey, void *avalue, 113 struct util_node **anextNode) 114 { 115 struct util_node *node = util_data_allocate_node(hash->data.d); 116 117 if (!node) 118 return NULL; 119 120 node->key = akey; 121 node->value = avalue; 122 123 node->next = (struct util_node*)(*anextNode); 124 *anextNode = node; 125 ++hash->data.d->size; 126 return node; 127 } 128 129 static void util_data_rehash(struct util_hash_data *hash, int hint) 130 { 131 if (hint < 0) { 132 hint = countBits(-hint); 133 if (hint < MinNumBits) 134 hint = MinNumBits; 135 hash->userNumBits = (short)hint; 136 while (primeForNumBits(hint) < (hash->size >> 1)) 137 ++hint; 138 } else if (hint < MinNumBits) { 139 hint = MinNumBits; 140 } 141 142 if (hash->numBits != hint) { 143 struct util_node *e = (struct util_node *)(hash); 144 struct util_node **oldBuckets = hash->buckets; 145 int oldNumBuckets = hash->numBuckets; 146 int i = 0; 147 148 hash->numBits = (short)hint; 149 hash->numBuckets = primeForNumBits(hint); 150 hash->buckets = malloc(sizeof(struct util_node*) * hash->numBuckets); 151 for (i = 0; i < hash->numBuckets; ++i) 152 hash->buckets[i] = e; 153 154 for (i = 0; i < oldNumBuckets; ++i) { 155 struct util_node *firstNode = oldBuckets[i]; 156 while (firstNode != e) { 157 unsigned h = firstNode->key; 158 struct util_node *lastNode = firstNode; 159 struct util_node *afterLastNode; 160 struct util_node **beforeFirstNode; 161 162 while (lastNode->next != e && lastNode->next->key == h) 163 lastNode = lastNode->next; 164 165 afterLastNode = lastNode->next; 166 beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 167 while (*beforeFirstNode != e) 168 beforeFirstNode = &(*beforeFirstNode)->next; 169 lastNode->next = *beforeFirstNode; 170 *beforeFirstNode = firstNode; 171 firstNode = afterLastNode; 172 } 173 } 174 free(oldBuckets); 175 } 176 } 177 178 static void util_data_might_grow(struct util_hash_data *hash) 179 { 180 if (hash->size >= hash->numBuckets) 181 util_data_rehash(hash, hash->numBits + 1); 182 } 183 184 static void util_data_has_shrunk(struct util_hash_data *hash) 185 { 186 if (hash->size <= (hash->numBuckets >> 3) && 187 hash->numBits > hash->userNumBits) { 188 int max = MAX(hash->numBits-2, hash->userNumBits); 189 util_data_rehash(hash, max); 190 } 191 } 192 193 static struct util_node *util_data_first_node(struct util_hash_data *hash) 194 { 195 struct util_node *e = (struct util_node *)(hash); 196 struct util_node **bucket = hash->buckets; 197 int n = hash->numBuckets; 198 while (n--) { 199 if (*bucket != e) 200 return *bucket; 201 ++bucket; 202 } 203 return e; 204 } 205 206 static struct util_node **util_hash_find_node(struct util_hash *hash, unsigned akey) 207 { 208 struct util_node **node; 209 210 if (hash->data.d->numBuckets) { 211 node = (struct util_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 212 assert(*node == hash->data.e || (*node)->next); 213 while (*node != hash->data.e && (*node)->key != akey) 214 node = &(*node)->next; 215 } else { 216 node = (struct util_node **)((const struct util_node * const *)(&hash->data.e)); 217 } 218 return node; 219 } 220 221 drm_private struct util_hash_iter 222 util_hash_insert(struct util_hash *hash, unsigned key, void *data) 223 { 224 util_data_might_grow(hash->data.d); 225 226 { 227 struct util_node **nextNode = util_hash_find_node(hash, key); 228 struct util_node *node = util_hash_create_node(hash, key, data, nextNode); 229 if (!node) { 230 struct util_hash_iter null_iter = {hash, 0}; 231 return null_iter; 232 } 233 234 { 235 struct util_hash_iter iter = {hash, node}; 236 return iter; 237 } 238 } 239 } 240 241 drm_private struct util_hash *util_hash_create(void) 242 { 243 struct util_hash *hash = malloc(sizeof(struct util_hash)); 244 if (!hash) 245 return NULL; 246 247 hash->data.d = malloc(sizeof(struct util_hash_data)); 248 if (!hash->data.d) { 249 free(hash); 250 return NULL; 251 } 252 253 hash->data.d->fakeNext = 0; 254 hash->data.d->buckets = 0; 255 hash->data.d->size = 0; 256 hash->data.d->nodeSize = sizeof(struct util_node); 257 hash->data.d->userNumBits = (short)MinNumBits; 258 hash->data.d->numBits = 0; 259 hash->data.d->numBuckets = 0; 260 261 return hash; 262 } 263 264 drm_private void util_hash_delete(struct util_hash *hash) 265 { 266 struct util_node *e_for_x = (struct util_node *)(hash->data.d); 267 struct util_node **bucket = (struct util_node **)(hash->data.d->buckets); 268 int n = hash->data.d->numBuckets; 269 while (n--) { 270 struct util_node *cur = *bucket++; 271 while (cur != e_for_x) { 272 struct util_node *next = cur->next; 273 util_free_node(cur); 274 cur = next; 275 } 276 } 277 free(hash->data.d->buckets); 278 free(hash->data.d); 279 free(hash); 280 } 281 282 drm_private struct util_hash_iter 283 util_hash_find(struct util_hash *hash, unsigned key) 284 { 285 struct util_node **nextNode = util_hash_find_node(hash, key); 286 struct util_hash_iter iter = {hash, *nextNode}; 287 return iter; 288 } 289 290 drm_private unsigned util_hash_iter_key(struct util_hash_iter iter) 291 { 292 if (!iter.node || iter.hash->data.e == iter.node) 293 return 0; 294 return iter.node->key; 295 } 296 297 drm_private void *util_hash_iter_data(struct util_hash_iter iter) 298 { 299 if (!iter.node || iter.hash->data.e == iter.node) 300 return 0; 301 return iter.node->value; 302 } 303 304 static struct util_node *util_hash_data_next(struct util_node *node) 305 { 306 union { 307 struct util_node *next; 308 struct util_node *e; 309 struct util_hash_data *d; 310 } a; 311 int start; 312 struct util_node **bucket; 313 int n; 314 315 a.next = node->next; 316 if (!a.next) { 317 /* iterating beyond the last element */ 318 return 0; 319 } 320 if (a.next->next) 321 return a.next; 322 323 start = (node->key % a.d->numBuckets) + 1; 324 bucket = a.d->buckets + start; 325 n = a.d->numBuckets - start; 326 while (n--) { 327 if (*bucket != a.e) 328 return *bucket; 329 ++bucket; 330 } 331 return a.e; 332 } 333 334 drm_private struct util_hash_iter 335 util_hash_iter_next(struct util_hash_iter iter) 336 { 337 struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)}; 338 return next; 339 } 340 341 drm_private int util_hash_iter_is_null(struct util_hash_iter iter) 342 { 343 if (!iter.node || iter.node == iter.hash->data.e) 344 return 1; 345 return 0; 346 } 347 348 drm_private void *util_hash_take(struct util_hash *hash, unsigned akey) 349 { 350 struct util_node **node = util_hash_find_node(hash, akey); 351 if (*node != hash->data.e) { 352 void *t = (*node)->value; 353 struct util_node *next = (*node)->next; 354 util_free_node(*node); 355 *node = next; 356 --hash->data.d->size; 357 util_data_has_shrunk(hash->data.d); 358 return t; 359 } 360 return 0; 361 } 362 363 drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash) 364 { 365 struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)}; 366 return iter; 367 } 368 369 drm_private struct util_hash_iter 370 util_hash_erase(struct util_hash *hash, struct util_hash_iter iter) 371 { 372 struct util_hash_iter ret = iter; 373 struct util_node *node = iter.node; 374 struct util_node **node_ptr; 375 376 if (node == hash->data.e) 377 return iter; 378 379 ret = util_hash_iter_next(ret); 380 node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 381 while (*node_ptr != node) 382 node_ptr = &(*node_ptr)->next; 383 *node_ptr = node->next; 384 util_free_node(node); 385 --hash->data.d->size; 386 return ret; 387 } 388