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 #include "util/u_debug.h" 34 #include "util/u_memory.h" 35 36 #include "cso_hash.h" 37 38 #ifndef MAX 39 #define MAX(a, b) ((a > b) ? (a) : (b)) 40 #endif 41 42 static const int MinNumBits = 4; 43 44 static const unsigned char prime_deltas[] = { 45 0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 9, 25, 3, 46 1, 21, 3, 21, 7, 15, 9, 5, 3, 29, 15, 0, 0, 0, 0, 0 47 }; 48 49 static int primeForNumBits(int numBits) 50 { 51 return (1 << numBits) + prime_deltas[numBits]; 52 } 53 54 /* 55 Returns the smallest integer n such that 56 primeForNumBits(n) >= hint. 57 */ 58 static int countBits(int hint) 59 { 60 int numBits = 0; 61 int bits = hint; 62 63 while (bits > 1) { 64 bits >>= 1; 65 numBits++; 66 } 67 68 if (numBits >= (int)sizeof(prime_deltas)) { 69 numBits = sizeof(prime_deltas) - 1; 70 } else if (primeForNumBits(numBits) < hint) { 71 ++numBits; 72 } 73 return numBits; 74 } 75 76 struct cso_node { 77 struct cso_node *next; 78 unsigned key; 79 void *value; 80 }; 81 82 struct cso_hash_data { 83 struct cso_node *fakeNext; 84 struct cso_node **buckets; 85 int size; 86 int nodeSize; 87 short userNumBits; 88 short numBits; 89 int numBuckets; 90 }; 91 92 struct cso_hash { 93 union { 94 struct cso_hash_data *d; 95 struct cso_node *e; 96 } data; 97 }; 98 99 static void *cso_data_allocate_node(struct cso_hash_data *hash) 100 { 101 return MALLOC(hash->nodeSize); 102 } 103 104 static void cso_free_node(struct cso_node *node) 105 { 106 FREE(node); 107 } 108 109 static struct cso_node * 110 cso_hash_create_node(struct cso_hash *hash, 111 unsigned akey, void *avalue, 112 struct cso_node **anextNode) 113 { 114 struct cso_node *node = cso_data_allocate_node(hash->data.d); 115 116 if (!node) 117 return NULL; 118 119 node->key = akey; 120 node->value = avalue; 121 122 node->next = (struct cso_node*)(*anextNode); 123 *anextNode = node; 124 ++hash->data.d->size; 125 return node; 126 } 127 128 static void cso_data_rehash(struct cso_hash_data *hash, int hint) 129 { 130 if (hint < 0) { 131 hint = countBits(-hint); 132 if (hint < MinNumBits) 133 hint = MinNumBits; 134 hash->userNumBits = (short)hint; 135 while (primeForNumBits(hint) < (hash->size >> 1)) 136 ++hint; 137 } else if (hint < MinNumBits) { 138 hint = MinNumBits; 139 } 140 141 if (hash->numBits != hint) { 142 struct cso_node *e = (struct cso_node *)(hash); 143 struct cso_node **oldBuckets = hash->buckets; 144 int oldNumBuckets = hash->numBuckets; 145 int i = 0; 146 147 hash->numBits = (short)hint; 148 hash->numBuckets = primeForNumBits(hint); 149 hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets); 150 for (i = 0; i < hash->numBuckets; ++i) 151 hash->buckets[i] = e; 152 153 for (i = 0; i < oldNumBuckets; ++i) { 154 struct cso_node *firstNode = oldBuckets[i]; 155 while (firstNode != e) { 156 unsigned h = firstNode->key; 157 struct cso_node *lastNode = firstNode; 158 struct cso_node *afterLastNode; 159 struct cso_node **beforeFirstNode; 160 161 while (lastNode->next != e && lastNode->next->key == h) 162 lastNode = lastNode->next; 163 164 afterLastNode = lastNode->next; 165 beforeFirstNode = &hash->buckets[h % hash->numBuckets]; 166 while (*beforeFirstNode != e) 167 beforeFirstNode = &(*beforeFirstNode)->next; 168 lastNode->next = *beforeFirstNode; 169 *beforeFirstNode = firstNode; 170 firstNode = afterLastNode; 171 } 172 } 173 FREE(oldBuckets); 174 } 175 } 176 177 static void cso_data_might_grow(struct cso_hash_data *hash) 178 { 179 if (hash->size >= hash->numBuckets) 180 cso_data_rehash(hash, hash->numBits + 1); 181 } 182 183 static void cso_data_has_shrunk(struct cso_hash_data *hash) 184 { 185 if (hash->size <= (hash->numBuckets >> 3) && 186 hash->numBits > hash->userNumBits) { 187 int max = MAX(hash->numBits-2, hash->userNumBits); 188 cso_data_rehash(hash, max); 189 } 190 } 191 192 static struct cso_node *cso_data_first_node(struct cso_hash_data *hash) 193 { 194 struct cso_node *e = (struct cso_node *)(hash); 195 struct cso_node **bucket = hash->buckets; 196 int n = hash->numBuckets; 197 while (n--) { 198 if (*bucket != e) 199 return *bucket; 200 ++bucket; 201 } 202 return e; 203 } 204 205 static struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey) 206 { 207 struct cso_node **node; 208 209 if (hash->data.d->numBuckets) { 210 node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]); 211 assert(*node == hash->data.e || (*node)->next); 212 while (*node != hash->data.e && (*node)->key != akey) 213 node = &(*node)->next; 214 } else { 215 node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e)); 216 } 217 return node; 218 } 219 220 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash, 221 unsigned key, void *data) 222 { 223 cso_data_might_grow(hash->data.d); 224 225 { 226 struct cso_node **nextNode = cso_hash_find_node(hash, key); 227 struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode); 228 if (!node) { 229 struct cso_hash_iter null_iter = {hash, 0}; 230 return null_iter; 231 } 232 233 { 234 struct cso_hash_iter iter = {hash, node}; 235 return iter; 236 } 237 } 238 } 239 240 struct cso_hash * cso_hash_create(void) 241 { 242 struct cso_hash *hash = MALLOC_STRUCT(cso_hash); 243 if (!hash) 244 return NULL; 245 246 hash->data.d = MALLOC_STRUCT(cso_hash_data); 247 if (!hash->data.d) { 248 FREE(hash); 249 return NULL; 250 } 251 252 hash->data.d->fakeNext = 0; 253 hash->data.d->buckets = 0; 254 hash->data.d->size = 0; 255 hash->data.d->nodeSize = sizeof(struct cso_node); 256 hash->data.d->userNumBits = (short)MinNumBits; 257 hash->data.d->numBits = 0; 258 hash->data.d->numBuckets = 0; 259 260 return hash; 261 } 262 263 void cso_hash_delete(struct cso_hash *hash) 264 { 265 struct cso_node *e_for_x = (struct cso_node *)(hash->data.d); 266 struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets); 267 int n = hash->data.d->numBuckets; 268 while (n--) { 269 struct cso_node *cur = *bucket++; 270 while (cur != e_for_x) { 271 struct cso_node *next = cur->next; 272 cso_free_node(cur); 273 cur = next; 274 } 275 } 276 FREE(hash->data.d->buckets); 277 FREE(hash->data.d); 278 FREE(hash); 279 } 280 281 struct cso_hash_iter cso_hash_find(struct cso_hash *hash, 282 unsigned key) 283 { 284 struct cso_node **nextNode = cso_hash_find_node(hash, key); 285 struct cso_hash_iter iter = {hash, *nextNode}; 286 return iter; 287 } 288 289 unsigned cso_hash_iter_key(struct cso_hash_iter iter) 290 { 291 if (!iter.node || iter.hash->data.e == iter.node) 292 return 0; 293 return iter.node->key; 294 } 295 296 void * cso_hash_iter_data(struct cso_hash_iter iter) 297 { 298 if (!iter.node || iter.hash->data.e == iter.node) 299 return 0; 300 return iter.node->value; 301 } 302 303 static struct cso_node *cso_hash_data_next(struct cso_node *node) 304 { 305 union { 306 struct cso_node *next; 307 struct cso_node *e; 308 struct cso_hash_data *d; 309 } a; 310 int start; 311 struct cso_node **bucket; 312 int n; 313 314 a.next = node->next; 315 if (!a.next) { 316 debug_printf("iterating beyond the last element\n"); 317 return 0; 318 } 319 if (a.next->next) 320 return a.next; 321 322 start = (node->key % a.d->numBuckets) + 1; 323 bucket = a.d->buckets + start; 324 n = a.d->numBuckets - start; 325 while (n--) { 326 if (*bucket != a.e) 327 return *bucket; 328 ++bucket; 329 } 330 return a.e; 331 } 332 333 334 static struct cso_node *cso_hash_data_prev(struct cso_node *node) 335 { 336 union { 337 struct cso_node *e; 338 struct cso_hash_data *d; 339 } a; 340 int start; 341 struct cso_node *sentinel; 342 struct cso_node **bucket; 343 344 a.e = node; 345 while (a.e->next) 346 a.e = a.e->next; 347 348 if (node == a.e) 349 start = a.d->numBuckets - 1; 350 else 351 start = node->key % a.d->numBuckets; 352 353 sentinel = node; 354 bucket = a.d->buckets + start; 355 while (start >= 0) { 356 if (*bucket != sentinel) { 357 struct cso_node *prev = *bucket; 358 while (prev->next != sentinel) 359 prev = prev->next; 360 return prev; 361 } 362 363 sentinel = a.e; 364 --bucket; 365 --start; 366 } 367 debug_printf("iterating backward beyond first element\n"); 368 return a.e; 369 } 370 371 struct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter) 372 { 373 struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)}; 374 return next; 375 } 376 377 int cso_hash_iter_is_null(struct cso_hash_iter iter) 378 { 379 if (!iter.node || iter.node == iter.hash->data.e) 380 return 1; 381 return 0; 382 } 383 384 void * cso_hash_take(struct cso_hash *hash, 385 unsigned akey) 386 { 387 struct cso_node **node = cso_hash_find_node(hash, akey); 388 if (*node != hash->data.e) { 389 void *t = (*node)->value; 390 struct cso_node *next = (*node)->next; 391 cso_free_node(*node); 392 *node = next; 393 --hash->data.d->size; 394 cso_data_has_shrunk(hash->data.d); 395 return t; 396 } 397 return 0; 398 } 399 400 struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter) 401 { 402 struct cso_hash_iter prev = {iter.hash, 403 cso_hash_data_prev(iter.node)}; 404 return prev; 405 } 406 407 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash) 408 { 409 struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)}; 410 return iter; 411 } 412 413 int cso_hash_size(struct cso_hash *hash) 414 { 415 return hash->data.d->size; 416 } 417 418 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter) 419 { 420 struct cso_hash_iter ret = iter; 421 struct cso_node *node = iter.node; 422 struct cso_node **node_ptr; 423 424 if (node == hash->data.e) 425 return iter; 426 427 ret = cso_hash_iter_next(ret); 428 node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]); 429 while (*node_ptr != node) 430 node_ptr = &(*node_ptr)->next; 431 *node_ptr = node->next; 432 cso_free_node(node); 433 --hash->data.d->size; 434 return ret; 435 } 436 437 boolean cso_hash_contains(struct cso_hash *hash, unsigned key) 438 { 439 struct cso_node **node = cso_hash_find_node(hash, key); 440 return (*node != hash->data.e); 441 } 442