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