Lev Walkin | adfcde2 | 2017-11-05 22:45:54 -0800 | [diff] [blame^] | 1 | /* |
| 2 | * Copyright (c) 2002-2005 Lev Walkin <vlm@lionet.info>. All rights reserved. |
| 3 | * Copyright (c) 2001-2004 Netli, Inc. All rights reserved. |
| 4 | * |
| 5 | * Redistribution and use in source and binary forms, with or without |
| 6 | * modification, are permitted provided that the following conditions |
| 7 | * are met: |
| 8 | * 1. Redistributions of source code must retain the above copyright |
| 9 | * notice, this list of conditions and the following disclaimer. |
| 10 | * 2. Redistributions in binary form must reproduce the above copyright |
| 11 | * notice, this list of conditions and the following disclaimer in the |
| 12 | * documentation and/or other materials provided with the distribution. |
| 13 | * |
| 14 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
| 15 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 16 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 17 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| 18 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 19 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 20 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 21 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 22 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 23 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 24 | * SUCH DAMAGE. |
| 25 | * |
| 26 | * $Id: genhash.c 447 2005-06-07 06:51:10Z vlm $ |
| 27 | */ |
| 28 | /* |
| 29 | * Implementation of a hash data structure. |
| 30 | * This particular implementation is supposed to be space-efficient |
| 31 | * particularly in the case of tiny number of hash elements. |
| 32 | * It also has an aggressive hash buckets expanding technique, which allows |
| 33 | * to deal with increasing number of elements without a loss of search speed. |
| 34 | * |
| 35 | * Generally, one structure of type genhash_t is allocated per hash set. |
| 36 | * This structure is supposed to hold all information related to the current |
| 37 | * set, and also holds a tiny number of hash elements, when hash hasn't yet |
| 38 | * grown up. When the number of elements reaches some point, part of the |
| 39 | * genhash_t structure is reused to contain the pointers to the actual |
| 40 | * hash buckets and LRU (Least Recently Used) list's head and tail. |
| 41 | * Elements which were held inside genhash_t will be moved to the hash buckets. |
| 42 | * |
| 43 | * Said above effectively means two modes of operation: TINY and NORMAL. |
| 44 | * They can be distinguished by examining the h->numbuckets value, which |
| 45 | * is 0 for TINY and greater for NORMAL mode. |
| 46 | * |
| 47 | * In the TINY mode we use a lower part of the genhash_t structure |
| 48 | * (lower 32 bytes from 64 bytes of genhash_t) to hold up to IH_VALUE (4) |
| 49 | * key/value pairs. |
| 50 | * |
| 51 | * In the NORMAL mode we use the lower part of the genhash_t structure |
| 52 | * to hold a set of pointers, including a pointer to the hash buckets. |
| 53 | * We agressively expand hash buckets size when adding new elements |
| 54 | * to lower the number of key comparisons. |
| 55 | */ |
| 56 | |
| 57 | #include <sys/types.h> |
| 58 | #include <stdlib.h> |
| 59 | #include <string.h> |
| 60 | #include <assert.h> |
| 61 | #include <errno.h> |
| 62 | #include "genhash.h" |
| 63 | |
| 64 | /* 1M entries, 4M RAM */ |
| 65 | #define DEFAULT_MAXIMUM_HASH_BUCKETS_NUMBER (1024 * 1024) |
| 66 | static int maximum_hash_buckets_number = DEFAULT_MAXIMUM_HASH_BUCKETS_NUMBER; |
| 67 | |
| 68 | /* |
| 69 | * A single hash element structure which binds a value to its key. |
| 70 | */ |
| 71 | typedef struct genhash_el_s { |
| 72 | unsigned int key_hash; /* Saved hash of the key */ |
| 73 | void *key; |
| 74 | void *value; |
| 75 | struct genhash_el_s *hash_next; /* Collision list inside the bucket */ |
| 76 | struct genhash_el_s *hash_prev; |
| 77 | struct genhash_el_s *lru_prev; /* Per-hash LRU list */ |
| 78 | struct genhash_el_s *lru_next; |
| 79 | } genhash_el; |
| 80 | |
| 81 | /* |
| 82 | * A hash structure with buckets etc. |
| 83 | */ |
| 84 | struct genhash_s { |
| 85 | int (*keycmpf) (const void *lkey1, const void *rkey2); |
| 86 | unsigned int (*keyhashf) (const void *key); /* hash function */ |
| 87 | void (*keydestroyf) (void *key); /* key destructor */ |
| 88 | void (*valuedestroyf) (void *value); /* value destructor */ |
| 89 | |
| 90 | int numelements; /* Total number of hash elements */ |
| 91 | int numbuckets; /* 0 means "use _TINY" */ |
| 92 | int lru_limit; /* Must be initialized explicitly */ |
| 93 | genhash_iter_t *iters; /* Active iterators */ |
| 94 | |
| 95 | /* 32-byte boundary here */ |
| 96 | |
| 97 | union { |
| 98 | #define IH_VALUES 4 /* Internally held key/value pairs for TINY mode */ |
| 99 | struct _internal_tiny_s { |
| 100 | void *keys[IH_VALUES]; |
| 101 | void *values[IH_VALUES]; |
| 102 | } _TINY; /* 32-byte structure */ |
| 103 | struct _internal_normal_s { |
| 104 | genhash_el *lru_head; /* LRU list head */ |
| 105 | genhash_el *lru_tail; /* LRU list tail */ |
| 106 | genhash_el **buckets; /* Hash buckets */ |
| 107 | /* void *unused; */ |
| 108 | } _NORMAL; |
| 109 | } un; |
| 110 | #define tiny_keys un._TINY.keys |
| 111 | #define tiny_values un._TINY.values |
| 112 | #define lru_head un._NORMAL.lru_head |
| 113 | #define lru_tail un._NORMAL.lru_tail |
| 114 | #define buckets un._NORMAL.buckets |
| 115 | }; |
| 116 | |
| 117 | |
| 118 | static int |
| 119 | _genhash_normal_add(genhash_t *h, genhash_el *el, void *key, void *value); |
| 120 | |
| 121 | |
| 122 | genhash_t * |
| 123 | genhash_new( |
| 124 | int (*keycmpf) (const void *key1, const void *key2), |
| 125 | unsigned int (*keyhashf) (const void *key), |
| 126 | void (*keydestroyf) (void *key), |
| 127 | void (*valuedestroyf) (void *value) |
| 128 | ) { |
| 129 | genhash_t *h; |
| 130 | |
| 131 | h = (genhash_t *)malloc(sizeof(genhash_t)); |
| 132 | if (!h) |
| 133 | return NULL; |
| 134 | |
| 135 | memset(h, 0, sizeof(genhash_t)); |
| 136 | |
| 137 | genhash_reinit(h, keycmpf, keyhashf, keydestroyf, valuedestroyf); |
| 138 | |
| 139 | return h; |
| 140 | } |
| 141 | |
| 142 | int |
| 143 | genhash_reinit( |
| 144 | genhash_t *h, |
| 145 | int (*keycmpf) (const void *key1, const void *key2), |
| 146 | unsigned int (*keyhashf) (const void *key), |
| 147 | void (*keydestroyf) (void *key), |
| 148 | void (*valuedestroyf) (void *value) |
| 149 | ) { |
| 150 | |
| 151 | assert(keycmpf && keyhashf); |
| 152 | |
| 153 | h->keycmpf = keycmpf; |
| 154 | h->keyhashf = keyhashf; |
| 155 | h->keydestroyf = keydestroyf; |
| 156 | h->valuedestroyf = valuedestroyf; |
| 157 | |
| 158 | return 0; |
| 159 | } |
| 160 | |
| 161 | int |
| 162 | genhash_count(genhash_t *h) { |
| 163 | if(h) { |
| 164 | return h->numelements; |
| 165 | } else { |
| 166 | return 0; |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | |
| 171 | static void |
| 172 | _remove_normal_hash_el(genhash_t *h, genhash_el *el) { |
| 173 | genhash_iter_t *iter; |
| 174 | void *kd_arg; |
| 175 | void *vd_arg; |
| 176 | |
| 177 | /* Remove from the collision list */ |
| 178 | if (el->hash_prev) { |
| 179 | if((el->hash_prev->hash_next = el->hash_next)) |
| 180 | el->hash_next->hash_prev = el->hash_prev; |
| 181 | |
| 182 | } else { |
| 183 | if((h->buckets[el->key_hash % h->numbuckets] = el->hash_next)) |
| 184 | el->hash_next->hash_prev = NULL; |
| 185 | } |
| 186 | |
| 187 | /* Remove from LRU list */ |
| 188 | if(el->lru_prev) { |
| 189 | if((el->lru_prev->lru_next = el->lru_next)) |
| 190 | el->lru_next->lru_prev = el->lru_prev; |
| 191 | else |
| 192 | h->lru_tail = el->lru_prev; |
| 193 | } else { |
| 194 | if(h->lru_head == el) { |
| 195 | if((h->lru_head = el->lru_next) == NULL) |
| 196 | h->lru_tail = NULL; |
| 197 | else |
| 198 | h->lru_head->lru_prev = NULL; |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | /* Remember key and value */ |
| 203 | kd_arg = el->key; |
| 204 | vd_arg = el->value; |
| 205 | |
| 206 | /* Move iterators off the element being deleted */ |
| 207 | for(iter = h->iters; iter; iter = iter->iter_next) { |
| 208 | assert(iter->hash_ptr == h); |
| 209 | if(iter->un.location == el) { |
| 210 | iter->un.location = iter->order_lru_first |
| 211 | ? el->lru_prev : el->lru_next; |
| 212 | } |
| 213 | } |
| 214 | |
| 215 | free(el); |
| 216 | h->numelements--; |
| 217 | |
| 218 | /* Remove key and value */ |
| 219 | if (h->keydestroyf) h->keydestroyf(kd_arg); |
| 220 | if (h->valuedestroyf) h->valuedestroyf(vd_arg); |
| 221 | } |
| 222 | |
| 223 | static inline void |
| 224 | _genhash_normal_el_move2top(genhash_t *h, genhash_el *el) { |
| 225 | |
| 226 | /* Disable sorting if iterators are running */ |
| 227 | if(h->iters) return; |
| 228 | |
| 229 | /* Move to the top of the hash bucket */ |
| 230 | if(el->hash_prev) { |
| 231 | int bucket = el->key_hash % h->numbuckets; |
| 232 | |
| 233 | /* Remove from the current location */ |
| 234 | if((el->hash_prev->hash_next = el->hash_next)) |
| 235 | el->hash_next->hash_prev = el->hash_prev; |
| 236 | |
| 237 | /* Move to the top of the hash bucket */ |
| 238 | if((el->hash_next = h->buckets[bucket])) |
| 239 | el->hash_next->hash_prev = el; |
| 240 | h->buckets[bucket] = el; |
| 241 | el->hash_prev = NULL; |
| 242 | } |
| 243 | |
| 244 | /* Move to the top of LRU list */ |
| 245 | if(h->lru_limit && el->lru_prev) { |
| 246 | |
| 247 | /* Remove from current location */ |
| 248 | if((el->lru_prev->lru_next = el->lru_next)) |
| 249 | el->lru_next->lru_prev = el->lru_prev; |
| 250 | else |
| 251 | h->lru_tail = el->lru_prev; |
| 252 | |
| 253 | /* Append to the head */ |
| 254 | el->lru_prev = NULL; |
| 255 | h->lru_head->lru_prev = el; |
| 256 | el->lru_next = h->lru_head; |
| 257 | h->lru_head = el; |
| 258 | } |
| 259 | } |
| 260 | |
| 261 | static int |
| 262 | _expand_hash(genhash_t *h) { |
| 263 | int newbuckets_count; |
| 264 | genhash_el **newbuckets; |
| 265 | |
| 266 | /* |
| 267 | * Compute a new number of buckets value. |
| 268 | */ |
| 269 | if(h->numbuckets) { |
| 270 | newbuckets_count = h->numbuckets << 2; |
| 271 | /* Too big hash table */ |
| 272 | if(newbuckets_count > maximum_hash_buckets_number) { |
| 273 | if(h->numbuckets < maximum_hash_buckets_number) { |
| 274 | newbuckets_count = maximum_hash_buckets_number; |
| 275 | } else { |
| 276 | /* No need to set errno here. */ |
| 277 | return -1; |
| 278 | } |
| 279 | } |
| 280 | } else { |
| 281 | /* 8 buckets -> 32 bytes of memory */ |
| 282 | newbuckets_count = IH_VALUES << 1; |
| 283 | if(newbuckets_count > maximum_hash_buckets_number) { |
| 284 | if(maximum_hash_buckets_number) { |
| 285 | newbuckets_count = maximum_hash_buckets_number; |
| 286 | } else { |
| 287 | /* Allowed to store only IH_VALUES elements */ |
| 288 | errno = EPERM; |
| 289 | return -1; |
| 290 | } |
| 291 | } |
| 292 | } |
| 293 | |
| 294 | /* |
| 295 | * Allocate a new storage for buckets. |
| 296 | */ |
| 297 | newbuckets = malloc(newbuckets_count * sizeof(*newbuckets)); |
| 298 | if(newbuckets) { |
| 299 | memset(newbuckets, 0, newbuckets_count * sizeof(*newbuckets)); |
| 300 | } else { |
| 301 | return -1; |
| 302 | } |
| 303 | |
| 304 | if(h->numbuckets) { |
| 305 | genhash_el *el; |
| 306 | int bucket; |
| 307 | |
| 308 | /* |
| 309 | * Rehash elements from old h->buckets to newbuckets. |
| 310 | * No need to touch LRU pointers and other stuff - it is okay. |
| 311 | */ |
| 312 | for(el = h->lru_tail; el; el = el->lru_prev) { |
| 313 | bucket = el->key_hash % newbuckets_count; |
| 314 | el->hash_prev = NULL; |
| 315 | if((el->hash_next = newbuckets[bucket])) |
| 316 | el->hash_next->hash_prev = el; |
| 317 | newbuckets[bucket] = el; |
| 318 | } |
| 319 | |
| 320 | free(h->buckets); |
| 321 | h->buckets = newbuckets; |
| 322 | h->numbuckets = newbuckets_count; |
| 323 | } else { |
| 324 | /* |
| 325 | * Moving from inline tiny storage into buckets. |
| 326 | */ |
| 327 | genhash_el *els[IH_VALUES] = { NULL }; |
| 328 | struct _internal_tiny_s tiny_substruct; |
| 329 | int i; |
| 330 | int saved_numelements; |
| 331 | int saved_lru_limit; |
| 332 | genhash_iter_t *iter; |
| 333 | |
| 334 | /* Pre-allocate hash elements (for "undo") */ |
| 335 | for(i = 0; i < h->numelements; i++) { |
| 336 | els[i] = (genhash_el *)malloc(sizeof(genhash_el)); |
| 337 | if(els[i] == NULL) { |
| 338 | for(i = 0; i < h->numelements; i++) |
| 339 | if(els[i]) |
| 340 | free(els[i]); |
| 341 | free(newbuckets); |
| 342 | return -1; |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | /* Save part of the union */ |
| 347 | tiny_substruct = h->un._TINY; |
| 348 | /* Re-initialize this part in NORMAL model */ |
| 349 | memset(&h->un._NORMAL, 0, sizeof(h->un._NORMAL)); |
| 350 | |
| 351 | /* There was no allocated buckets, when in tiny hash mode. */ |
| 352 | h->buckets = newbuckets; |
| 353 | h->numbuckets = newbuckets_count; |
| 354 | |
| 355 | saved_numelements = h->numelements; |
| 356 | saved_lru_limit = h->lru_limit; |
| 357 | h->numelements = 0; |
| 358 | h->lru_limit = 0; /* Disable LRU expiration for a while */ |
| 359 | |
| 360 | for(i = saved_numelements - 1; i >= 0; --i) { |
| 361 | /* |
| 362 | * genhash_normal_add won't fail, if we supply |
| 363 | * an already allocated genhash_el *. |
| 364 | */ |
| 365 | (void)_genhash_normal_add(h, els[i], |
| 366 | tiny_substruct.keys[i], |
| 367 | tiny_substruct.values[i]); |
| 368 | } |
| 369 | |
| 370 | /* Now, scan through iterators and convert them TINY->NORMAL */ |
| 371 | for(iter = h->iters; iter; iter = iter->iter_next) { |
| 372 | assert(iter->hash_ptr == h); |
| 373 | if(iter->un.item_number < 0 |
| 374 | || iter->un.item_number >= saved_numelements) { |
| 375 | iter->un.location = 0; |
| 376 | } else { |
| 377 | iter->un.location = els[iter->un.item_number]; |
| 378 | } |
| 379 | } |
| 380 | |
| 381 | h->lru_limit = saved_lru_limit; |
| 382 | } |
| 383 | |
| 384 | return 0; |
| 385 | } |
| 386 | |
| 387 | /* |
| 388 | * Won't return with error if el is provided. |
| 389 | */ |
| 390 | static int |
| 391 | _genhash_normal_add(genhash_t *h, genhash_el *el, void *key, void *value) { |
| 392 | genhash_el **bucket; |
| 393 | |
| 394 | if(el == NULL) { |
| 395 | el = malloc(sizeof (*el)); |
| 396 | if(el == NULL) { |
| 397 | /* Errno will be set by malloc() */ |
| 398 | return -1; |
| 399 | } |
| 400 | } |
| 401 | |
| 402 | /* Maintain maximum number of entries */ |
| 403 | if(h->lru_limit) { |
| 404 | while(h->numelements >= h->lru_limit) |
| 405 | _remove_normal_hash_el(h, h->lru_tail); |
| 406 | } |
| 407 | |
| 408 | memset(el, 0, sizeof(genhash_el)); |
| 409 | |
| 410 | /* Compute the index of the collision list */ |
| 411 | el->key_hash = h->keyhashf(key); |
| 412 | bucket = &h->buckets[el->key_hash % h->numbuckets]; |
| 413 | |
| 414 | el->key = key; |
| 415 | el->value = value; |
| 416 | |
| 417 | /* |
| 418 | * Add to the collision list |
| 419 | */ |
| 420 | el->hash_prev = NULL; |
| 421 | if((el->hash_next = *bucket)) |
| 422 | (*bucket)->hash_prev = el; |
| 423 | *bucket = el; |
| 424 | |
| 425 | /* |
| 426 | * Add to the LRU list. |
| 427 | */ |
| 428 | if(h->lru_head) { |
| 429 | el->lru_next = h->lru_head; |
| 430 | el->lru_next->lru_prev = el; |
| 431 | h->lru_head = el; |
| 432 | } else { |
| 433 | h->lru_head = el; |
| 434 | h->lru_tail = el; |
| 435 | } |
| 436 | |
| 437 | h->numelements++; |
| 438 | |
| 439 | return 0; |
| 440 | } |
| 441 | |
| 442 | |
| 443 | int |
| 444 | genhash_add(genhash_t *h, void *key, void *value) { |
| 445 | |
| 446 | if(key == NULL) { |
| 447 | errno = EINVAL; |
| 448 | return -1; |
| 449 | } |
| 450 | |
| 451 | if(h->numbuckets == 0) { |
| 452 | |
| 453 | /* We have a tiny internally-held set of elements */ |
| 454 | if(h->numelements < IH_VALUES) { |
| 455 | h->tiny_keys[h->numelements] = key; |
| 456 | h->tiny_values[h->numelements] = value; |
| 457 | h->numelements++; |
| 458 | return 0; |
| 459 | } |
| 460 | |
| 461 | if(_expand_hash(h) == -1) |
| 462 | return -1; |
| 463 | |
| 464 | } else { |
| 465 | |
| 466 | if((h->numelements / h->numbuckets) > 2) |
| 467 | (void)_expand_hash(h); |
| 468 | } |
| 469 | |
| 470 | return _genhash_normal_add(h, NULL, key, value); |
| 471 | } |
| 472 | |
| 473 | int |
| 474 | genhash_addunique(genhash_t *h, void *key, void *value) { |
| 475 | if(genhash_get(h, key)) { |
| 476 | errno = EEXIST; |
| 477 | return -1; |
| 478 | } |
| 479 | return genhash_add(h, key, value); |
| 480 | } |
| 481 | |
| 482 | void * |
| 483 | genhash_get(genhash_t *h, const void *key) { |
| 484 | |
| 485 | if(h->numbuckets) { |
| 486 | |
| 487 | genhash_el *walk; |
| 488 | int bucket = h->keyhashf(key) % h->numbuckets; |
| 489 | |
| 490 | for(walk = h->buckets[bucket]; |
| 491 | walk; walk = walk->hash_next) { |
| 492 | |
| 493 | if (h->keycmpf(walk->key, key) == 0) { |
| 494 | _genhash_normal_el_move2top(h, walk); |
| 495 | return walk->value; |
| 496 | } |
| 497 | } |
| 498 | |
| 499 | } else { |
| 500 | /* TINY mode */ |
| 501 | int i; |
| 502 | |
| 503 | assert(h->numelements <= IH_VALUES); |
| 504 | for(i = 0; i < h->numelements; i++) { |
| 505 | if(h->keycmpf(h->tiny_keys[i], key) == 0) |
| 506 | /* Don't reorder in TINY mode */ |
| 507 | return h->tiny_values[i]; |
| 508 | } |
| 509 | |
| 510 | } |
| 511 | |
| 512 | errno = ESRCH; |
| 513 | return NULL; |
| 514 | } |
| 515 | |
| 516 | int |
| 517 | genhash_del(genhash_t *h, void *key) { |
| 518 | |
| 519 | if(h->numbuckets) { |
| 520 | /* NORMAL mode */ |
| 521 | genhash_el *walk; |
| 522 | int bucket; |
| 523 | |
| 524 | if(h->numelements == 0) { |
| 525 | errno = ESRCH; |
| 526 | return -1; /* not found */ |
| 527 | } |
| 528 | |
| 529 | bucket = h->keyhashf(key) % h->numbuckets; |
| 530 | |
| 531 | for(walk = h->buckets[bucket]; walk; walk = walk->hash_next) |
| 532 | if(h->keycmpf(walk->key, key) == 0) |
| 533 | break; |
| 534 | |
| 535 | if(walk) { |
| 536 | _remove_normal_hash_el(h, walk); |
| 537 | return 0; |
| 538 | } |
| 539 | } else { |
| 540 | /* TINY mode */ |
| 541 | int i; |
| 542 | |
| 543 | /* Look for matching key */ |
| 544 | for(i = 0; i < h->numelements; i++) |
| 545 | if(h->keycmpf(h->tiny_keys[i], key) == 0) |
| 546 | break; |
| 547 | |
| 548 | if(i < h->numelements) { |
| 549 | /* Remember values */ |
| 550 | void *kd_arg = h->tiny_keys[i]; |
| 551 | void *vd_arg = h->tiny_values[i]; |
| 552 | |
| 553 | h->numelements--; |
| 554 | |
| 555 | if(h->iters) { |
| 556 | /* If iterators are involved, we have to |
| 557 | * shift elements to maintain iteration order |
| 558 | * and avoid duplications */ |
| 559 | genhash_iter_t *iter; |
| 560 | memmove(&h->tiny_keys[i], |
| 561 | &h->tiny_keys[i+1], |
| 562 | (h->numelements - i) |
| 563 | * sizeof(h->tiny_keys[0])); |
| 564 | memmove(&h->tiny_values[i], |
| 565 | &h->tiny_values[i+1], |
| 566 | (h->numelements - i) |
| 567 | * sizeof(h->tiny_values[0])); |
| 568 | /* Shift the iterator's indexes */ |
| 569 | for(iter = h->iters; iter; |
| 570 | iter = iter->iter_next) { |
| 571 | int in = iter->un.item_number; |
| 572 | if(iter->order_lru_first) { |
| 573 | if(in > i) |
| 574 | iter->un.item_number--; |
| 575 | } else { |
| 576 | if(in >= i) |
| 577 | iter->un.item_number--; |
| 578 | } |
| 579 | } |
| 580 | } else { |
| 581 | /* Substitute it with the last one */ |
| 582 | /* No harm if overwriting itself */ |
| 583 | h->tiny_keys[i] = h->tiny_keys[h->numelements]; |
| 584 | h->tiny_values[i] = h->tiny_values[h->numelements]; |
| 585 | } |
| 586 | h->tiny_keys[h->numelements] = 0; |
| 587 | h->tiny_values[h->numelements] = 0; |
| 588 | /* Delete for real */ |
| 589 | if(h->keydestroyf) h->keydestroyf(kd_arg); |
| 590 | if(h->valuedestroyf) h->valuedestroyf(vd_arg); |
| 591 | return 0; |
| 592 | } |
| 593 | } |
| 594 | |
| 595 | errno = ESRCH; |
| 596 | return -1; |
| 597 | } |
| 598 | |
| 599 | /* |
| 600 | * Initialize a hash iterator. |
| 601 | */ |
| 602 | int |
| 603 | genhash_iter_init(genhash_iter_t *iter, genhash_t *h, int reverse_order) { |
| 604 | |
| 605 | iter->hash_ptr = h; |
| 606 | iter->iter_prev = 0; /* Add itself to the iterators list */ |
| 607 | iter->iter_next = h->iters; |
| 608 | h->iters = iter; |
| 609 | iter->order_lru_first = reverse_order; |
| 610 | |
| 611 | if(h->numbuckets) { |
| 612 | /* NORMAL mode */ |
| 613 | if(reverse_order) { |
| 614 | /* Least recent first order */ |
| 615 | iter->un.location = h->lru_tail; |
| 616 | } else { |
| 617 | /* Most recent first order */ |
| 618 | iter->un.location = h->lru_head; |
| 619 | } |
| 620 | } else { |
| 621 | /* TINY mode */ |
| 622 | if(reverse_order) { |
| 623 | iter->un.item_number = 0; |
| 624 | } else { |
| 625 | iter->un.item_number = h->numelements - 1; |
| 626 | } |
| 627 | } |
| 628 | |
| 629 | return h->numelements; |
| 630 | } |
| 631 | |
| 632 | int |
| 633 | genhash_iter(genhash_iter_t *iter, void *key_p, void *val_p) { |
| 634 | void **key = key_p; |
| 635 | void **val = val_p; |
| 636 | genhash_t *h = iter->hash_ptr; |
| 637 | |
| 638 | if(h->numbuckets) { |
| 639 | /* NORMAL mode */ |
| 640 | genhash_el *cur_el = iter->un.location; |
| 641 | if(!cur_el) |
| 642 | /* Already finished */ |
| 643 | return 0; |
| 644 | |
| 645 | if(key) *key = cur_el->key; |
| 646 | if(val) *val = cur_el->value; |
| 647 | |
| 648 | /* Move pointer to the next hash element */ |
| 649 | iter->un.location = iter->order_lru_first |
| 650 | ? cur_el->lru_prev : cur_el->lru_next; |
| 651 | } else { |
| 652 | /* TINY mode */ |
| 653 | if(iter->un.item_number < 0 |
| 654 | || iter->un.item_number >= h->numelements |
| 655 | || h->tiny_keys[iter->un.item_number] == 0) |
| 656 | return 0; |
| 657 | |
| 658 | if(key) *key = h->tiny_keys[iter->un.item_number]; |
| 659 | if(val) *val = h->tiny_values[iter->un.item_number]; |
| 660 | |
| 661 | /* Advance to the next element */ |
| 662 | if(iter->order_lru_first) |
| 663 | iter->un.item_number++; |
| 664 | else |
| 665 | iter->un.item_number--; |
| 666 | } |
| 667 | |
| 668 | |
| 669 | return 1; |
| 670 | } |
| 671 | |
| 672 | void |
| 673 | genhash_iter_done(genhash_iter_t *iter) { |
| 674 | assert(iter->hash_ptr->iters); |
| 675 | /* Remove itself from the iterators list */ |
| 676 | if(iter->iter_next) |
| 677 | iter->iter_next->iter_prev = iter->iter_prev; |
| 678 | if(iter->iter_prev) |
| 679 | iter->iter_prev->iter_next = iter->iter_next; |
| 680 | else |
| 681 | iter->hash_ptr->iters = iter->iter_next; /* Shift the head */ |
| 682 | iter->hash_ptr = (void *)0xdeadbeef; |
| 683 | } |
| 684 | |
| 685 | int |
| 686 | genhash_set_lru_limit(genhash_t *h, int value) { |
| 687 | if(h) { |
| 688 | int prev_limit = h->lru_limit; |
| 689 | if(value >= 0) |
| 690 | h->lru_limit = value; |
| 691 | return prev_limit; |
| 692 | } else { |
| 693 | errno = EINVAL; |
| 694 | return -1; |
| 695 | } |
| 696 | } |
| 697 | |
| 698 | int |
| 699 | genhash_set_buckets_limit(int value) { |
| 700 | int prev_limit = maximum_hash_buckets_number; |
| 701 | if(value > 0) { |
| 702 | maximum_hash_buckets_number = value; |
| 703 | } |
| 704 | return prev_limit; |
| 705 | } |
| 706 | |
| 707 | void |
| 708 | genhash_destroy(genhash_t *h) { |
| 709 | if(h) { |
| 710 | assert(h->iters == 0); /* All iterators MUST be _done(). */ |
| 711 | genhash_empty(h, 1, 1); |
| 712 | free(h); |
| 713 | } |
| 714 | } |
| 715 | |
| 716 | void |
| 717 | genhash_empty(genhash_t *h, int freekeys, int freevalues) { |
| 718 | genhash_iter_t *iter; |
| 719 | |
| 720 | if(h == NULL) return; |
| 721 | |
| 722 | /* |
| 723 | * Don't free what could not be freed. |
| 724 | */ |
| 725 | if(h->keydestroyf == NULL) freekeys = 0; |
| 726 | if(h->valuedestroyf == NULL) freevalues = 0; |
| 727 | |
| 728 | if(h->numbuckets == 0) { |
| 729 | while(h->numelements > 0) { |
| 730 | int n = --h->numelements; |
| 731 | void *kd_arg = h->tiny_keys[n]; |
| 732 | void *vd_arg = h->tiny_values[n]; |
| 733 | |
| 734 | if (freekeys) h->keydestroyf(kd_arg); |
| 735 | if (freevalues) h->valuedestroyf(vd_arg); |
| 736 | } |
| 737 | } else { |
| 738 | genhash_el *el, *el_next; |
| 739 | |
| 740 | for(el = h->lru_head; el; el = el_next) { |
| 741 | void *kd_arg = el->key; |
| 742 | void *vd_arg = el->value; |
| 743 | el_next = el->lru_next; |
| 744 | free(el); |
| 745 | |
| 746 | h->numelements --; |
| 747 | |
| 748 | if (freekeys) h->keydestroyf(kd_arg); |
| 749 | if (freevalues) h->valuedestroyf(vd_arg); |
| 750 | } |
| 751 | free(h->buckets); |
| 752 | h->numbuckets = 0; /* Move back to TINY model */ |
| 753 | } |
| 754 | memset(&h->un, 0, sizeof(h->un)); |
| 755 | |
| 756 | /* Invalidate iterators in TINY model */ |
| 757 | for(iter = h->iters; iter; iter = iter->iter_next) { |
| 758 | assert(iter->hash_ptr == h); |
| 759 | iter->un.item_number = -1; |
| 760 | } |
| 761 | |
| 762 | assert(h->numelements == 0); |
| 763 | } |
| 764 | |
| 765 | |
| 766 | /*----- Simple hash and compare functions for common data types ------*/ |
| 767 | |
| 768 | unsigned int |
| 769 | hashf_int (const void *key) { |
| 770 | return (*(const int *)key ^ (*(const int *)key >> 16)); |
| 771 | } |
| 772 | |
| 773 | int |
| 774 | cmpf_int (const void *key1, const void *key2) { |
| 775 | return (*(const int *)key1 != *(const int *)key2); |
| 776 | } |
| 777 | |
| 778 | unsigned int |
| 779 | hashf_void (const void *key) { |
| 780 | return ((int)key ^ ((int)key >> 16)); |
| 781 | } |
| 782 | |
| 783 | int |
| 784 | cmpf_void (const void *key1, const void *key2) { |
| 785 | return (key1 != key2); |
| 786 | } |
| 787 | |
| 788 | |
| 789 | /* |
| 790 | * Phong's linear congruential hash |
| 791 | */ |
| 792 | #define dcharhash(h, c) ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c)) |
| 793 | |
| 794 | unsigned int |
| 795 | hashf_string(const void *keyarg) { |
| 796 | register const unsigned char *key; |
| 797 | register unsigned int h; |
| 798 | register unsigned char c; |
| 799 | |
| 800 | key = keyarg; |
| 801 | for (h = 0; (c = *key++);) |
| 802 | dcharhash(h, c); |
| 803 | |
| 804 | return (h); |
| 805 | } |
| 806 | |
| 807 | int |
| 808 | cmpf_string(const void *key1, const void *key2) { |
| 809 | return strcmp((const char *)key1, (const char *)key2); |
| 810 | } |
| 811 | |