1/* 2 * Copyright (c) 1984 through 2008, William LeFebvre 3 * 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 are met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * * Neither the name of William LeFebvre nor the names of other 17 * contributors may be used to endorse or promote products derived from 18 * this software without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33/* hash.m4c */ 34 35/* The file hash.c is generated from hash.m4c via the preprocessor M4 */ 36 37/* 38 * Hash table functions: init, add, lookup, first, next, sizeinfo. 39 * This is a conventional "bucket hash". The key is hashed in to a number 40 * less than or equal to the number of buckets and the result is used 41 * to index in to the array of buckets. Each bucket is a linked list 42 * that contains all the key/value pairs which hashed to that index. 43 */ 44 45#include "config.h" 46 47#if STDC_HEADERS 48#include <string.h> 49#include <stdlib.h> 50#define memzero(a, b) memset((a), 0, (b)) 51#else /* !STDC_HEADERS */ 52#ifdef HAVE_MEMCPY 53#define memzero(a, b) memset((a), 0, (b)) 54#else 55#define memcpy(a, b, c) bcopy((b), (a), (c)) 56#define memzero(a, b) bzero((a), (b)) 57#define memcmp(a, b, c) bcmp((a), (b), (c)) 58#endif /* HAVE_MEMCPY */ 59#ifdef HAVE_STRINGS_H 60#include <strings.h> 61#else 62#ifdef HAVE_STRING_H 63#include <string.h> 64#endif 65#endif 66void *malloc(); 67void free(); 68char *strdup(); 69#endif /* !STDC_HEADERS */ 70 71/* After all that there are still some systems that don't have NULL defined */ 72#ifndef NULL 73#define NULL 0 74#endif 75 76#ifdef HAVE_MATH_H 77#include <math.h> 78#endif 79 80#if !HAVE_PID_T 81typedef long pid_t; 82#endif 83#if !HAVE_ID_T 84typedef long id_t; 85#endif 86 87#include "hash.h" 88 89dnl # The m4 code uses MALLOC, FREE, and STRDUP for dynamic allocation. 90dnl # You can change what these get mapped to here: 91 92define(`MALLOC', `malloc($1)') 93define(`FREE', `free($1)') 94define(`STRDUP', `strdup($1)') 95 96static int 97next_prime(int x) 98 99{ 100 double i, j; 101 int f; 102 103 i = x; 104 while (i++) 105 { 106 f=1; 107 for (j=2; j<i; j++) 108 { 109 if ((i/j)==floor(i/j)) 110 { 111 f=0; 112 break; 113 } 114 } 115 if (f) 116 { 117 return (int)i; 118 } 119 } 120 return 1; 121} 122 123/* string hashes */ 124 125static int 126string_hash(hash_table *ht, char *key) 127 128{ 129 unsigned long s = 0; 130 unsigned char ch; 131 int shifting = 24; 132 133 while ((ch = (unsigned char)*key++) != '\0') 134 { 135 if (shifting == 0) 136 { 137 s = s + ch; 138 shifting = 24; 139 } 140 else 141 { 142 s = s + (ch << shifting); 143 shifting -= 8; 144 } 145 } 146 147 return (s % ht->num_buckets); 148} 149 150void ll_init(llist *q) 151 152{ 153 q->head = NULL; 154 q->count = 0; 155} 156 157llistitem *ll_newitem(int size) 158 159{ 160 llistitem *qi; 161 162 qi = (llistitem *)MALLOC(sizeof(llistitem) + size); 163 qi->datum = ((void *)qi + sizeof(llistitem)); 164 return qi; 165} 166 167void ll_freeitem(llistitem *li) 168 169{ 170 FREE(li); 171} 172 173void ll_add(llist *q, llistitem *new) 174 175{ 176 new->next = q->head; 177 q->head = new; 178 q->count++; 179} 180 181void ll_extract(llist *q, llistitem *qi, llistitem *last) 182 183{ 184 if (last == NULL) 185 { 186 q->head = qi->next; 187 } 188 else 189 { 190 last->next = qi->next; 191 } 192 qi->next = NULL; 193 q->count--; 194} 195 196#define LL_FIRST(q) ((q)->head) 197llistitem * 198ll_first(llist *q) 199 200{ 201 return q->head; 202} 203 204#define LL_NEXT(q, qi) ((qi) != NULL ? (qi)->next : NULL) 205llistitem * 206ll_next(llist *q, llistitem *qi) 207 208{ 209 return (qi != NULL ? qi->next : NULL); 210} 211 212#define LL_ISEMPTY(ll) ((ll)->count == 0) 213int 214ll_isempty(llist *ll) 215 216{ 217 return (ll->count == 0); 218} 219 220/* 221 * hash_table *hash_create(int num) 222 * 223 * Creates a hash table structure with at least "num" buckets. 224 */ 225 226hash_table * 227hash_create(int num) 228 229{ 230 hash_table *result; 231 bucket_t *b; 232 int bytes; 233 int i; 234 235 /* create the resultant structure */ 236 result = (hash_table *)MALLOC(sizeof(hash_table)); 237 238 /* adjust bucket count to be prime */ 239 num = next_prime(num); 240 241 /* create the buckets */ 242 bytes = sizeof(bucket_t) * num; 243 result->buckets = b = (bucket_t *)MALLOC(bytes); 244 result->num_buckets = num; 245 246 /* create each bucket as a linked list */ 247 i = num; 248 while (--i >= 0) 249 { 250 ll_init(&(b->list)); 251 b++; 252 } 253 254 return result; 255} 256 257/* 258 * unsigned int hash_count(hash_table *ht) 259 * 260 * Return total number of elements contained in hash table. 261 */ 262 263unsigned int 264hash_count(hash_table *ht) 265 266{ 267 register int i = 0; 268 register int cnt = 0; 269 register bucket_t *bucket; 270 271 bucket = ht->buckets; 272 while (i++ < ht->num_buckets) 273 { 274 cnt += bucket->list.count; 275 bucket++; 276 } 277 278 return cnt; 279} 280 281/* 282 * void hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht) 283 * 284 * Fill in "sizes" with information about bucket lengths in hash 285 * table "max". 286 */ 287 288void 289hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht) 290 291{ 292 register int i; 293 register int idx; 294 register bucket_t *bucket; 295 296 memzero(sizes, max * sizeof(unsigned int)); 297 298 bucket = ht->buckets; 299 i = 0; 300 while (i++ < ht->num_buckets) 301 { 302 idx = bucket->list.count; 303 sizes[idx >= max ? max-1 : idx]++; 304 bucket++; 305 } 306} 307 308dnl # HASH_TABLE_TMPL(suffix, keytype, to_hash, to_cmp, to_alloc, to_free) 309dnl # 310dnl # This generates hash table functions suitable for keys 311dnl # of type "keytype". The function names all end with "suffix". 312dnl # "to_hash" is an expression that generates a hash index (this 313dnl # expression can include key and ht). "to_cmp" is an expression 314dnl # that compares "key" to "k1". "to_alloc" is an expression that 315dnl # allocates space for "key", or empty if no allocation is needed. 316dnl # "to_free" is an expression that frees "key", or empty if no 317dnl # allocation is needed. 318 319define(`HASH_TABLE_TMPL', ` 320 321/* 322 * void hash_add_$1(hash_table *ht, $2 key, void *value) 323 * 324 * Add an element to table "ht". The element is described by 325 * "key" and "value". Return NULL on success. If the key 326 * already exists in the table, then no action is taken and 327 * the data for the existing element is returned. 328 * Key type is $2 329 */ 330 331void * 332hash_add_$1(hash_table *ht, $2 key, void *value) 333 334{ 335 bucket_t *bucket; 336 hash_item_$1 *hi; 337 hash_item_$1 *h; 338 llist *ll; 339 llistitem *li; 340 llistitem *newli; 341 $2 k1; 342 343 /* allocate the space we will need */ 344 newli = ll_newitem(sizeof(hash_item_$1)); 345 hi = (hash_item_$1 *)newli->datum; 346 347 /* fill in the values */ 348 hi->key = ifelse($5, , key, $5); 349 hi->value = value; 350 351 /* hash to the bucket */ 352 bucket = &(ht->buckets[$3]); 353 354 /* walk the list to make sure we do not have a duplicate */ 355 ll = &(bucket->list); 356 li = LL_FIRST(ll); 357 while (li != NULL) 358 { 359 h = (hash_item_$1 *)li->datum; 360 k1 = h->key; 361 if ($4) 362 { 363 /* found one */ 364 break; 365 } 366 li = LL_NEXT(ll, li); 367 } 368 li = NULL; 369 370 /* is there already one there? */ 371 if (li == NULL) 372 { 373 /* add the unique element to the buckets list */ 374 ll_add(&(bucket->list), newli); 375 return NULL; 376 } 377 else 378 { 379 /* free the stuff we just allocated */ 380 ll_freeitem(newli); 381 return ((hash_item_$1 *)(li->datum))->value; 382 } 383} 384 385/* 386 * void *hash_replace_$1(hash_table *ht, $2 key, void *value) 387 * 388 * Replace an existing value in the hash table with a new one and 389 * return the old value. If the key does not already exist in 390 * the hash table, add a new element and return NULL. 391 * Key type is $2 392 */ 393 394void * 395hash_replace_$1(hash_table *ht, $2 key, void *value) 396 397{ 398 bucket_t *bucket; 399 hash_item_$1 *hi; 400 llist *ll; 401 llistitem *li; 402 void *result = NULL; 403 $2 k1; 404 405 /* find the bucket */ 406 bucket = &(ht->buckets[$3]); 407 408 /* walk the list until we find the existing item */ 409 ll = &(bucket->list); 410 li = LL_FIRST(ll); 411 while (li != NULL) 412 { 413 hi = (hash_item_$1 *)li->datum; 414 k1 = hi->key; 415 if ($4) 416 { 417 /* found it: now replace the value with the new one */ 418 result = hi->value; 419 hi->value = value; 420 break; 421 } 422 li = LL_NEXT(ll, li); 423 } 424 425 /* if the element wasnt found, add it */ 426 if (result == NULL) 427 { 428 li = ll_newitem(sizeof(hash_item_$1)); 429 hi = (hash_item_$1 *)li->datum; 430 hi->key = ifelse($5, , key, $5); 431 hi->value = value; 432 ll_add(&(bucket->list), li); 433 } 434 435 /* return the old value (so it can be freed) */ 436 return result; 437} 438 439/* 440 * void *hash_lookup_$1(hash_table *ht, $2 key) 441 * 442 * Look up "key" in "ht" and return the associated value. If "key" 443 * is not found, return NULL. Key type is $2 444 */ 445 446void * 447hash_lookup_$1(hash_table *ht, $2 key) 448 449{ 450 bucket_t *bucket; 451 llist *ll; 452 llistitem *li; 453 hash_item_$1 *h; 454 void *result; 455 $2 k1; 456 457 result = NULL; 458 if ((bucket = &(ht->buckets[$3])) != NULL) 459 { 460 ll = &(bucket->list); 461 li = LL_FIRST(ll); 462 while (li != NULL) 463 { 464 h = (hash_item_$1 *)li->datum; 465 k1 = h->key; 466 if ($4) 467 { 468 result = h->value; 469 break; 470 } 471 li = LL_NEXT(ll, li); 472 } 473 } 474 return result; 475} 476 477/* 478 * void *hash_remove_$1(hash_table *ht, $2 key) 479 * 480 * Remove the element associated with "key" from the hash table 481 * "ht". Return the value or NULL if the key was not found. 482 */ 483 484void * 485hash_remove_$1(hash_table *ht, $2 key) 486 487{ 488 bucket_t *bucket; 489 llist *ll; 490 llistitem *li; 491 llistitem *lilast; 492 hash_item_$1 *hi; 493 void *result; 494 $2 k1; 495 496 result = NULL; 497 if ((bucket = &(ht->buckets[$3])) != NULL) 498 { 499 ll = &(bucket->list); 500 li = LL_FIRST(ll); 501 lilast = NULL; 502 while (li != NULL) 503 { 504 hi = (hash_item_$1 *)li->datum; 505 k1 = hi->key; 506 if ($4) 507 { 508 ll_extract(ll, li, lilast); 509 result = hi->value; 510 key = hi->key; 511 $6; 512 ll_freeitem(li); 513 break; 514 } 515 lilast = li; 516 li = LL_NEXT(ll, li); 517 } 518 } 519 return result; 520} 521 522/* 523 * hash_item_$1 *hash_first_$1(hash_table *ht, hash_pos *pos) 524 * 525 * First function to call when iterating through all items in the hash 526 * table. Returns the first item in "ht" and initializes "*pos" to track 527 * the current position. 528 */ 529 530hash_item_$1 * 531hash_first_$1(hash_table *ht, hash_pos *pos) 532 533{ 534 /* initialize pos for first item in first bucket */ 535 pos->num_buckets = ht->num_buckets; 536 pos->hash_bucket = ht->buckets; 537 pos->curr = 0; 538 pos->ll_last = NULL; 539 540 /* find the first non-empty bucket */ 541 while(pos->hash_bucket->list.count == 0) 542 { 543 pos->hash_bucket++; 544 if (++pos->curr >= pos->num_buckets) 545 { 546 return NULL; 547 } 548 } 549 550 /* set and return the first item */ 551 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 552 return (hash_item_$1 *)pos->ll_item->datum; 553} 554 555 556/* 557 * hash_item_$1 *hash_next_$1(hash_pos *pos) 558 * 559 * Return the next item in the hash table, using "pos" as a description 560 * of the present position in the hash table. "pos" also identifies the 561 * specific hash table. Return NULL if there are no more elements. 562 */ 563 564hash_item_$1 * 565hash_next_$1(hash_pos *pos) 566 567{ 568 llistitem *li; 569 570 /* move item to last and check for NULL */ 571 if ((pos->ll_last = pos->ll_item) == NULL) 572 { 573 /* are we really at the end of the hash table? */ 574 if (pos->curr >= pos->num_buckets) 575 { 576 /* yes: return NULL */ 577 return NULL; 578 } 579 /* no: regrab first item in current bucket list (might be NULL) */ 580 li = LL_FIRST(&(pos->hash_bucket->list)); 581 } 582 else 583 { 584 /* get the next item in the llist */ 585 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 586 } 587 588 /* if its NULL we have to find another bucket */ 589 while (li == NULL) 590 { 591 /* locate another bucket */ 592 pos->ll_last = NULL; 593 594 /* move to the next one */ 595 pos->hash_bucket++; 596 if (++pos->curr >= pos->num_buckets) 597 { 598 /* at the end of the hash table */ 599 pos->ll_item = NULL; 600 return NULL; 601 } 602 603 /* get the first element (might be NULL) */ 604 li = LL_FIRST(&(pos->hash_bucket->list)); 605 } 606 607 /* li is the next element to dish out */ 608 pos->ll_item = li; 609 return (hash_item_$1 *)li->datum; 610} 611 612/* 613 * void *hash_remove_pos_$1(hash_pos *pos) 614 * 615 * Remove the hash table entry pointed to by position marker "pos". 616 * The data from the entry is returned upon success, otherwise NULL. 617 */ 618 619 620void * 621hash_remove_pos_$1(hash_pos *pos) 622 623{ 624 llistitem *li; 625 void *ans; 626 hash_item_$1 *hi; 627 $2 key; 628 629 /* sanity checks */ 630 if (pos == NULL || pos->ll_last == pos->ll_item) 631 { 632 return NULL; 633 } 634 635 /* at this point pos contains the item to remove (ll_item) 636 and its predecesor (ll_last) */ 637 /* extract the item from the llist */ 638 li = pos->ll_item; 639 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 640 641 /* retain the data */ 642 hi = (hash_item_$1 *)li->datum; 643 ans = hi->value; 644 645 /* free up the space */ 646 key = hi->key; 647 $6; 648 ll_freeitem(li); 649 650 /* back up to previous item */ 651 /* its okay for ll_item to be null: hash_next will detect it */ 652 pos->ll_item = pos->ll_last; 653 654 return ans; 655} 656') 657 658dnl # create hash talbe functions for unsigned int and for strings */ 659 660HASH_TABLE_TMPL(`uint', `unsigned int', `(key % ht->num_buckets)', `key == k1', ,) 661HASH_TABLE_TMPL(`pid', `pid_t', `(key % ht->num_buckets)', `key == k1', ,) 662HASH_TABLE_TMPL(`string', `char *', `string_hash(ht, key)', `strcmp(key, k1) == 0', `STRDUP(key)', `FREE(key)') 663HASH_TABLE_TMPL(`pidthr', `pidthr_t', `((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)', `(key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)', ,) 664#if HAVE_LWPID_T 665HASH_TABLE_TMPL(`lwpid', `lwpid_t', `(key % ht->num_buckets)', `key == k1', ,) 666#endif 667