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 "os.h" 46 47 #ifdef HAVE_MATH_H 48 #include <math.h> 49 #endif 50 51 #include "hash.h" 52 53 static int 54 next_prime(int x) 55 56 { 57 double i, j; 58 int f; 59 60 i = x; 61 while (i++) 62 { 63 f=1; 64 for (j=2; j<i; j++) 65 { 66 if ((i/j)==floor(i/j)) 67 { 68 f=0; 69 break; 70 } 71 } 72 if (f) 73 { 74 return (int)i; 75 } 76 } 77 return 1; 78 } 79 80 /* string hashes */ 81 82 static int 83 string_hash(hash_table *ht, char *key) 84 85 { 86 unsigned long s = 0; 87 unsigned char ch; 88 int shifting = 24; 89 90 while ((ch = (unsigned char)*key++) != '\0') 91 { 92 if (shifting == 0) 93 { 94 s = s + ch; 95 shifting = 24; 96 } 97 else 98 { 99 s = s + (ch << shifting); 100 shifting -= 8; 101 } 102 } 103 104 return (s % ht->num_buckets); 105 } 106 107 void ll_init(llist *q) 108 109 { 110 q->head = NULL; 111 q->count = 0; 112 } 113 114 llistitem *ll_newitem(int size) 115 116 { 117 llistitem *qi; 118 119 qi = emalloc(sizeof(llistitem) + size); 120 qi->datum = ((char *)qi + sizeof(llistitem)); 121 return qi; 122 } 123 124 void ll_freeitem(llistitem *li) 125 126 { 127 free(li); 128 } 129 130 void ll_add(llist *q, llistitem *new) 131 132 { 133 new->next = q->head; 134 q->head = new; 135 q->count++; 136 } 137 138 void ll_extract(llist *q, llistitem *qi, llistitem *last) 139 140 { 141 if (last == NULL) 142 { 143 q->head = qi->next; 144 } 145 else 146 { 147 last->next = qi->next; 148 } 149 qi->next = NULL; 150 q->count--; 151 } 152 153 #define LL_FIRST(q) ((q)->head) 154 llistitem * 155 ll_first(llist *q) 156 157 { 158 return q->head; 159 } 160 161 #define LL_NEXT(q, qi) ((qi) != NULL ? (qi)->next : NULL) 162 llistitem * 163 ll_next(llist *q, llistitem *qi) 164 165 { 166 return (qi != NULL ? qi->next : NULL); 167 } 168 169 #define LL_ISEMPTY(ll) ((ll)->count == 0) 170 int 171 ll_isempty(llist *ll) 172 173 { 174 return (ll->count == 0); 175 } 176 177 /* 178 * hash_table *hash_create(int num) 179 * 180 * Creates a hash table structure with at least "num" buckets. 181 */ 182 183 hash_table * 184 hash_create(int num) 185 186 { 187 hash_table *result; 188 bucket_t *b; 189 int bytes; 190 int i; 191 192 /* create the resultant structure */ 193 result = emalloc(sizeof(hash_table)); 194 195 /* adjust bucket count to be prime */ 196 num = next_prime(num); 197 198 /* create the buckets */ 199 bytes = sizeof(bucket_t) * num; 200 result->buckets = b = emalloc(bytes); 201 result->num_buckets = num; 202 203 /* create each bucket as a linked list */ 204 i = num; 205 while (--i >= 0) 206 { 207 ll_init(&(b->list)); 208 b++; 209 } 210 211 return result; 212 } 213 214 /* 215 * unsigned int hash_count(hash_table *ht) 216 * 217 * Return total number of elements contained in hash table. 218 */ 219 220 unsigned int 221 hash_count(hash_table *ht) 222 223 { 224 register int i = 0; 225 register int cnt = 0; 226 register bucket_t *bucket; 227 228 bucket = ht->buckets; 229 while (i++ < ht->num_buckets) 230 { 231 cnt += bucket->list.count; 232 bucket++; 233 } 234 235 return cnt; 236 } 237 238 /* 239 * void hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht) 240 * 241 * Fill in "sizes" with information about bucket lengths in hash 242 * table "max". 243 */ 244 245 void 246 hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht) 247 248 { 249 register int i; 250 register int idx; 251 register bucket_t *bucket; 252 253 memzero(sizes, max * sizeof(unsigned int)); 254 255 bucket = ht->buckets; 256 i = 0; 257 while (i++ < ht->num_buckets) 258 { 259 idx = bucket->list.count; 260 sizes[idx >= max ? max-1 : idx]++; 261 bucket++; 262 } 263 } 264 265 266 267 268 269 270 271 /* 272 * void hash_add_uint(hash_table *ht, unsigned int key, void *value) 273 * 274 * Add an element to table "ht". The element is described by 275 * "key" and "value". Return NULL on success. If the key 276 * already exists in the table, then no action is taken and 277 * the data for the existing element is returned. 278 * Key type is unsigned int 279 */ 280 281 void * 282 hash_add_uint(hash_table *ht, unsigned int key, void *value) 283 284 { 285 bucket_t *bucket; 286 hash_item_uint *hi; 287 hash_item_uint *h; 288 llist *ll; 289 llistitem *li; 290 llistitem *newli; 291 unsigned int k1; 292 293 /* allocate the space we will need */ 294 newli = ll_newitem(sizeof(hash_item_uint)); 295 hi = (hash_item_uint *)newli->datum; 296 297 /* fill in the values */ 298 hi->key = key; 299 hi->value = value; 300 301 /* hash to the bucket */ 302 bucket = &(ht->buckets[(key % ht->num_buckets)]); 303 304 /* walk the list to make sure we do not have a duplicate */ 305 ll = &(bucket->list); 306 li = LL_FIRST(ll); 307 while (li != NULL) 308 { 309 h = (hash_item_uint *)li->datum; 310 k1 = h->key; 311 if (key == k1) 312 { 313 /* found one */ 314 break; 315 } 316 li = LL_NEXT(ll, li); 317 } 318 li = NULL; 319 320 /* is there already one there? */ 321 if (li == NULL) 322 { 323 /* add the unique element to the buckets list */ 324 ll_add(&(bucket->list), newli); 325 return NULL; 326 } 327 else 328 { 329 /* free the stuff we just allocated */ 330 ll_freeitem(newli); 331 return ((hash_item_uint *)(li->datum))->value; 332 } 333 } 334 335 /* 336 * void *hash_replace_uint(hash_table *ht, unsigned int key, void *value) 337 * 338 * Replace an existing value in the hash table with a new one and 339 * return the old value. If the key does not already exist in 340 * the hash table, add a new element and return NULL. 341 * Key type is unsigned int 342 */ 343 344 void * 345 hash_replace_uint(hash_table *ht, unsigned int key, void *value) 346 347 { 348 bucket_t *bucket; 349 hash_item_uint *hi; 350 llist *ll; 351 llistitem *li; 352 void *result = NULL; 353 unsigned int k1; 354 355 /* find the bucket */ 356 bucket = &(ht->buckets[(key % ht->num_buckets)]); 357 358 /* walk the list until we find the existing item */ 359 ll = &(bucket->list); 360 li = LL_FIRST(ll); 361 while (li != NULL) 362 { 363 hi = (hash_item_uint *)li->datum; 364 k1 = hi->key; 365 if (key == k1) 366 { 367 /* found it: now replace the value with the new one */ 368 result = hi->value; 369 hi->value = value; 370 break; 371 } 372 li = LL_NEXT(ll, li); 373 } 374 375 /* if the element wasnt found, add it */ 376 if (result == NULL) 377 { 378 li = ll_newitem(sizeof(hash_item_uint)); 379 hi = (hash_item_uint *)li->datum; 380 hi->key = key; 381 hi->value = value; 382 ll_add(&(bucket->list), li); 383 } 384 385 /* return the old value (so it can be freed) */ 386 return result; 387 } 388 389 /* 390 * void *hash_lookup_uint(hash_table *ht, unsigned int key) 391 * 392 * Look up "key" in "ht" and return the associated value. If "key" 393 * is not found, return NULL. Key type is unsigned int 394 */ 395 396 void * 397 hash_lookup_uint(hash_table *ht, unsigned int key) 398 399 { 400 bucket_t *bucket; 401 llist *ll; 402 llistitem *li; 403 hash_item_uint *h; 404 void *result; 405 unsigned int k1; 406 407 result = NULL; 408 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 409 { 410 ll = &(bucket->list); 411 li = LL_FIRST(ll); 412 while (li != NULL) 413 { 414 h = (hash_item_uint *)li->datum; 415 k1 = h->key; 416 if (key == k1) 417 { 418 result = h->value; 419 break; 420 } 421 li = LL_NEXT(ll, li); 422 } 423 } 424 return result; 425 } 426 427 /* 428 * void *hash_remove_uint(hash_table *ht, unsigned int key) 429 * 430 * Remove the element associated with "key" from the hash table 431 * "ht". Return the value or NULL if the key was not found. 432 */ 433 434 void * 435 hash_remove_uint(hash_table *ht, unsigned int key) 436 437 { 438 bucket_t *bucket; 439 llist *ll; 440 llistitem *li; 441 llistitem *lilast; 442 hash_item_uint *hi; 443 void *result; 444 unsigned int k1; 445 446 result = NULL; 447 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 448 { 449 ll = &(bucket->list); 450 li = LL_FIRST(ll); 451 lilast = NULL; 452 while (li != NULL) 453 { 454 hi = (hash_item_uint *)li->datum; 455 k1 = hi->key; 456 if (key == k1) 457 { 458 ll_extract(ll, li, lilast); 459 result = hi->value; 460 key = hi->key; 461 ; 462 ll_freeitem(li); 463 break; 464 } 465 lilast = li; 466 li = LL_NEXT(ll, li); 467 } 468 } 469 return result; 470 } 471 472 /* 473 * hash_item_uint *hash_first_uint(hash_table *ht, hash_pos *pos) 474 * 475 * First function to call when iterating through all items in the hash 476 * table. Returns the first item in "ht" and initializes "*pos" to track 477 * the current position. 478 */ 479 480 hash_item_uint * 481 hash_first_uint(hash_table *ht, hash_pos *pos) 482 483 { 484 /* initialize pos for first item in first bucket */ 485 pos->num_buckets = ht->num_buckets; 486 pos->hash_bucket = ht->buckets; 487 pos->curr = 0; 488 pos->ll_last = NULL; 489 490 /* find the first non-empty bucket */ 491 while(pos->hash_bucket->list.count == 0) 492 { 493 pos->hash_bucket++; 494 if (++pos->curr >= pos->num_buckets) 495 { 496 return NULL; 497 } 498 } 499 500 /* set and return the first item */ 501 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 502 return (hash_item_uint *)pos->ll_item->datum; 503 } 504 505 506 /* 507 * hash_item_uint *hash_next_uint(hash_pos *pos) 508 * 509 * Return the next item in the hash table, using "pos" as a description 510 * of the present position in the hash table. "pos" also identifies the 511 * specific hash table. Return NULL if there are no more elements. 512 */ 513 514 hash_item_uint * 515 hash_next_uint(hash_pos *pos) 516 517 { 518 llistitem *li; 519 520 /* move item to last and check for NULL */ 521 if ((pos->ll_last = pos->ll_item) == NULL) 522 { 523 /* are we really at the end of the hash table? */ 524 if (pos->curr >= pos->num_buckets) 525 { 526 /* yes: return NULL */ 527 return NULL; 528 } 529 /* no: regrab first item in current bucket list (might be NULL) */ 530 li = LL_FIRST(&(pos->hash_bucket->list)); 531 } 532 else 533 { 534 /* get the next item in the llist */ 535 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 536 } 537 538 /* if its NULL we have to find another bucket */ 539 while (li == NULL) 540 { 541 /* locate another bucket */ 542 pos->ll_last = NULL; 543 544 /* move to the next one */ 545 pos->hash_bucket++; 546 if (++pos->curr >= pos->num_buckets) 547 { 548 /* at the end of the hash table */ 549 pos->ll_item = NULL; 550 return NULL; 551 } 552 553 /* get the first element (might be NULL) */ 554 li = LL_FIRST(&(pos->hash_bucket->list)); 555 } 556 557 /* li is the next element to dish out */ 558 pos->ll_item = li; 559 return (hash_item_uint *)li->datum; 560 } 561 562 /* 563 * void *hash_remove_pos_uint(hash_pos *pos) 564 * 565 * Remove the hash table entry pointed to by position marker "pos". 566 * The data from the entry is returned upon success, otherwise NULL. 567 */ 568 569 570 void * 571 hash_remove_pos_uint(hash_pos *pos) 572 573 { 574 llistitem *li; 575 void *ans; 576 hash_item_uint *hi; 577 unsigned int key; 578 579 /* sanity checks */ 580 if (pos == NULL || pos->ll_last == pos->ll_item) 581 { 582 return NULL; 583 } 584 585 /* at this point pos contains the item to remove (ll_item) 586 and its predecesor (ll_last) */ 587 /* extract the item from the llist */ 588 li = pos->ll_item; 589 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 590 591 /* retain the data */ 592 hi = (hash_item_uint *)li->datum; 593 ans = hi->value; 594 595 /* free up the space */ 596 key = hi->key; 597 ; 598 ll_freeitem(li); 599 600 /* back up to previous item */ 601 /* its okay for ll_item to be null: hash_next will detect it */ 602 pos->ll_item = pos->ll_last; 603 604 return ans; 605 } 606 607 608 609 /* 610 * void hash_add_pid(hash_table *ht, pid_t key, void *value) 611 * 612 * Add an element to table "ht". The element is described by 613 * "key" and "value". Return NULL on success. If the key 614 * already exists in the table, then no action is taken and 615 * the data for the existing element is returned. 616 * Key type is pid_t 617 */ 618 619 void * 620 hash_add_pid(hash_table *ht, pid_t key, void *value) 621 622 { 623 bucket_t *bucket; 624 hash_item_pid *hi; 625 hash_item_pid *h; 626 llist *ll; 627 llistitem *li; 628 llistitem *newli; 629 pid_t k1; 630 631 /* allocate the space we will need */ 632 newli = ll_newitem(sizeof(hash_item_pid)); 633 hi = (hash_item_pid *)newli->datum; 634 635 /* fill in the values */ 636 hi->key = key; 637 hi->value = value; 638 639 /* hash to the bucket */ 640 bucket = &(ht->buckets[(key % ht->num_buckets)]); 641 642 /* walk the list to make sure we do not have a duplicate */ 643 ll = &(bucket->list); 644 li = LL_FIRST(ll); 645 while (li != NULL) 646 { 647 h = (hash_item_pid *)li->datum; 648 k1 = h->key; 649 if (key == k1) 650 { 651 /* found one */ 652 break; 653 } 654 li = LL_NEXT(ll, li); 655 } 656 li = NULL; 657 658 /* is there already one there? */ 659 if (li == NULL) 660 { 661 /* add the unique element to the buckets list */ 662 ll_add(&(bucket->list), newli); 663 return NULL; 664 } 665 else 666 { 667 /* free the stuff we just allocated */ 668 ll_freeitem(newli); 669 return ((hash_item_pid *)(li->datum))->value; 670 } 671 } 672 673 /* 674 * void *hash_replace_pid(hash_table *ht, pid_t key, void *value) 675 * 676 * Replace an existing value in the hash table with a new one and 677 * return the old value. If the key does not already exist in 678 * the hash table, add a new element and return NULL. 679 * Key type is pid_t 680 */ 681 682 void * 683 hash_replace_pid(hash_table *ht, pid_t key, void *value) 684 685 { 686 bucket_t *bucket; 687 hash_item_pid *hi; 688 llist *ll; 689 llistitem *li; 690 void *result = NULL; 691 pid_t k1; 692 693 /* find the bucket */ 694 bucket = &(ht->buckets[(key % ht->num_buckets)]); 695 696 /* walk the list until we find the existing item */ 697 ll = &(bucket->list); 698 li = LL_FIRST(ll); 699 while (li != NULL) 700 { 701 hi = (hash_item_pid *)li->datum; 702 k1 = hi->key; 703 if (key == k1) 704 { 705 /* found it: now replace the value with the new one */ 706 result = hi->value; 707 hi->value = value; 708 break; 709 } 710 li = LL_NEXT(ll, li); 711 } 712 713 /* if the element wasnt found, add it */ 714 if (result == NULL) 715 { 716 li = ll_newitem(sizeof(hash_item_pid)); 717 hi = (hash_item_pid *)li->datum; 718 hi->key = key; 719 hi->value = value; 720 ll_add(&(bucket->list), li); 721 } 722 723 /* return the old value (so it can be freed) */ 724 return result; 725 } 726 727 /* 728 * void *hash_lookup_pid(hash_table *ht, pid_t key) 729 * 730 * Look up "key" in "ht" and return the associated value. If "key" 731 * is not found, return NULL. Key type is pid_t 732 */ 733 734 void * 735 hash_lookup_pid(hash_table *ht, pid_t key) 736 737 { 738 bucket_t *bucket; 739 llist *ll; 740 llistitem *li; 741 hash_item_pid *h; 742 void *result; 743 pid_t k1; 744 745 result = NULL; 746 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 747 { 748 ll = &(bucket->list); 749 li = LL_FIRST(ll); 750 while (li != NULL) 751 { 752 h = (hash_item_pid *)li->datum; 753 k1 = h->key; 754 if (key == k1) 755 { 756 result = h->value; 757 break; 758 } 759 li = LL_NEXT(ll, li); 760 } 761 } 762 return result; 763 } 764 765 /* 766 * void *hash_remove_pid(hash_table *ht, pid_t key) 767 * 768 * Remove the element associated with "key" from the hash table 769 * "ht". Return the value or NULL if the key was not found. 770 */ 771 772 void * 773 hash_remove_pid(hash_table *ht, pid_t key) 774 775 { 776 bucket_t *bucket; 777 llist *ll; 778 llistitem *li; 779 llistitem *lilast; 780 hash_item_pid *hi; 781 void *result; 782 pid_t k1; 783 784 result = NULL; 785 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 786 { 787 ll = &(bucket->list); 788 li = LL_FIRST(ll); 789 lilast = NULL; 790 while (li != NULL) 791 { 792 hi = (hash_item_pid *)li->datum; 793 k1 = hi->key; 794 if (key == k1) 795 { 796 ll_extract(ll, li, lilast); 797 result = hi->value; 798 key = hi->key; 799 ; 800 ll_freeitem(li); 801 break; 802 } 803 lilast = li; 804 li = LL_NEXT(ll, li); 805 } 806 } 807 return result; 808 } 809 810 /* 811 * hash_item_pid *hash_first_pid(hash_table *ht, hash_pos *pos) 812 * 813 * First function to call when iterating through all items in the hash 814 * table. Returns the first item in "ht" and initializes "*pos" to track 815 * the current position. 816 */ 817 818 hash_item_pid * 819 hash_first_pid(hash_table *ht, hash_pos *pos) 820 821 { 822 /* initialize pos for first item in first bucket */ 823 pos->num_buckets = ht->num_buckets; 824 pos->hash_bucket = ht->buckets; 825 pos->curr = 0; 826 pos->ll_last = NULL; 827 828 /* find the first non-empty bucket */ 829 while(pos->hash_bucket->list.count == 0) 830 { 831 pos->hash_bucket++; 832 if (++pos->curr >= pos->num_buckets) 833 { 834 return NULL; 835 } 836 } 837 838 /* set and return the first item */ 839 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 840 return (hash_item_pid *)pos->ll_item->datum; 841 } 842 843 844 /* 845 * hash_item_pid *hash_next_pid(hash_pos *pos) 846 * 847 * Return the next item in the hash table, using "pos" as a description 848 * of the present position in the hash table. "pos" also identifies the 849 * specific hash table. Return NULL if there are no more elements. 850 */ 851 852 hash_item_pid * 853 hash_next_pid(hash_pos *pos) 854 855 { 856 llistitem *li; 857 858 /* move item to last and check for NULL */ 859 if ((pos->ll_last = pos->ll_item) == NULL) 860 { 861 /* are we really at the end of the hash table? */ 862 if (pos->curr >= pos->num_buckets) 863 { 864 /* yes: return NULL */ 865 return NULL; 866 } 867 /* no: regrab first item in current bucket list (might be NULL) */ 868 li = LL_FIRST(&(pos->hash_bucket->list)); 869 } 870 else 871 { 872 /* get the next item in the llist */ 873 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 874 } 875 876 /* if its NULL we have to find another bucket */ 877 while (li == NULL) 878 { 879 /* locate another bucket */ 880 pos->ll_last = NULL; 881 882 /* move to the next one */ 883 pos->hash_bucket++; 884 if (++pos->curr >= pos->num_buckets) 885 { 886 /* at the end of the hash table */ 887 pos->ll_item = NULL; 888 return NULL; 889 } 890 891 /* get the first element (might be NULL) */ 892 li = LL_FIRST(&(pos->hash_bucket->list)); 893 } 894 895 /* li is the next element to dish out */ 896 pos->ll_item = li; 897 return (hash_item_pid *)li->datum; 898 } 899 900 /* 901 * void *hash_remove_pos_pid(hash_pos *pos) 902 * 903 * Remove the hash table entry pointed to by position marker "pos". 904 * The data from the entry is returned upon success, otherwise NULL. 905 */ 906 907 908 void * 909 hash_remove_pos_pid(hash_pos *pos) 910 911 { 912 llistitem *li; 913 void *ans; 914 hash_item_pid *hi; 915 pid_t key; 916 917 /* sanity checks */ 918 if (pos == NULL || pos->ll_last == pos->ll_item) 919 { 920 return NULL; 921 } 922 923 /* at this point pos contains the item to remove (ll_item) 924 and its predecesor (ll_last) */ 925 /* extract the item from the llist */ 926 li = pos->ll_item; 927 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 928 929 /* retain the data */ 930 hi = (hash_item_pid *)li->datum; 931 ans = hi->value; 932 933 /* free up the space */ 934 key = hi->key; 935 ; 936 ll_freeitem(li); 937 938 /* back up to previous item */ 939 /* its okay for ll_item to be null: hash_next will detect it */ 940 pos->ll_item = pos->ll_last; 941 942 return ans; 943 } 944 945 946 947 /* 948 * void hash_add_string(hash_table *ht, char * key, void *value) 949 * 950 * Add an element to table "ht". The element is described by 951 * "key" and "value". Return NULL on success. If the key 952 * already exists in the table, then no action is taken and 953 * the data for the existing element is returned. 954 * Key type is char * 955 */ 956 957 void * 958 hash_add_string(hash_table *ht, char * key, void *value) 959 960 { 961 bucket_t *bucket; 962 hash_item_string *hi; 963 hash_item_string *h; 964 llist *ll; 965 llistitem *li; 966 llistitem *newli; 967 char * k1; 968 969 /* allocate the space we will need */ 970 newli = ll_newitem(sizeof(hash_item_string)); 971 hi = (hash_item_string *)newli->datum; 972 973 /* fill in the values */ 974 hi->key = estrdup(key); 975 hi->value = value; 976 977 /* hash to the bucket */ 978 bucket = &(ht->buckets[string_hash(ht, key)]); 979 980 /* walk the list to make sure we do not have a duplicate */ 981 ll = &(bucket->list); 982 li = LL_FIRST(ll); 983 while (li != NULL) 984 { 985 h = (hash_item_string *)li->datum; 986 k1 = h->key; 987 if (strcmp(key, k1) == 0) 988 { 989 /* found one */ 990 break; 991 } 992 li = LL_NEXT(ll, li); 993 } 994 li = NULL; 995 996 /* is there already one there? */ 997 if (li == NULL) 998 { 999 /* add the unique element to the buckets list */ 1000 ll_add(&(bucket->list), newli); 1001 return NULL; 1002 } 1003 else 1004 { 1005 /* free the stuff we just allocated */ 1006 ll_freeitem(newli); 1007 return ((hash_item_string *)(li->datum))->value; 1008 } 1009 } 1010 1011 /* 1012 * void *hash_replace_string(hash_table *ht, char * key, void *value) 1013 * 1014 * Replace an existing value in the hash table with a new one and 1015 * return the old value. If the key does not already exist in 1016 * the hash table, add a new element and return NULL. 1017 * Key type is char * 1018 */ 1019 1020 void * 1021 hash_replace_string(hash_table *ht, char * key, void *value) 1022 1023 { 1024 bucket_t *bucket; 1025 hash_item_string *hi; 1026 llist *ll; 1027 llistitem *li; 1028 void *result = NULL; 1029 char * k1; 1030 1031 /* find the bucket */ 1032 bucket = &(ht->buckets[string_hash(ht, key)]); 1033 1034 /* walk the list until we find the existing item */ 1035 ll = &(bucket->list); 1036 li = LL_FIRST(ll); 1037 while (li != NULL) 1038 { 1039 hi = (hash_item_string *)li->datum; 1040 k1 = hi->key; 1041 if (strcmp(key, k1) == 0) 1042 { 1043 /* found it: now replace the value with the new one */ 1044 result = hi->value; 1045 hi->value = value; 1046 break; 1047 } 1048 li = LL_NEXT(ll, li); 1049 } 1050 1051 /* if the element wasnt found, add it */ 1052 if (result == NULL) 1053 { 1054 li = ll_newitem(sizeof(hash_item_string)); 1055 hi = (hash_item_string *)li->datum; 1056 hi->key = estrdup(key); 1057 hi->value = value; 1058 ll_add(&(bucket->list), li); 1059 } 1060 1061 /* return the old value (so it can be freed) */ 1062 return result; 1063 } 1064 1065 /* 1066 * void *hash_lookup_string(hash_table *ht, char * key) 1067 * 1068 * Look up "key" in "ht" and return the associated value. If "key" 1069 * is not found, return NULL. Key type is char * 1070 */ 1071 1072 void * 1073 hash_lookup_string(hash_table *ht, char * key) 1074 1075 { 1076 bucket_t *bucket; 1077 llist *ll; 1078 llistitem *li; 1079 hash_item_string *h; 1080 void *result; 1081 char * k1; 1082 1083 result = NULL; 1084 if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL) 1085 { 1086 ll = &(bucket->list); 1087 li = LL_FIRST(ll); 1088 while (li != NULL) 1089 { 1090 h = (hash_item_string *)li->datum; 1091 k1 = h->key; 1092 if (strcmp(key, k1) == 0) 1093 { 1094 result = h->value; 1095 break; 1096 } 1097 li = LL_NEXT(ll, li); 1098 } 1099 } 1100 return result; 1101 } 1102 1103 /* 1104 * void *hash_remove_string(hash_table *ht, char * key) 1105 * 1106 * Remove the element associated with "key" from the hash table 1107 * "ht". Return the value or NULL if the key was not found. 1108 */ 1109 1110 void * 1111 hash_remove_string(hash_table *ht, char * key) 1112 1113 { 1114 bucket_t *bucket; 1115 llist *ll; 1116 llistitem *li; 1117 llistitem *lilast; 1118 hash_item_string *hi; 1119 void *result; 1120 char * k1; 1121 1122 result = NULL; 1123 if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL) 1124 { 1125 ll = &(bucket->list); 1126 li = LL_FIRST(ll); 1127 lilast = NULL; 1128 while (li != NULL) 1129 { 1130 hi = (hash_item_string *)li->datum; 1131 k1 = hi->key; 1132 if (strcmp(key, k1) == 0) 1133 { 1134 ll_extract(ll, li, lilast); 1135 result = hi->value; 1136 key = hi->key; 1137 free(key); 1138 ll_freeitem(li); 1139 break; 1140 } 1141 lilast = li; 1142 li = LL_NEXT(ll, li); 1143 } 1144 } 1145 return result; 1146 } 1147 1148 /* 1149 * hash_item_string *hash_first_string(hash_table *ht, hash_pos *pos) 1150 * 1151 * First function to call when iterating through all items in the hash 1152 * table. Returns the first item in "ht" and initializes "*pos" to track 1153 * the current position. 1154 */ 1155 1156 hash_item_string * 1157 hash_first_string(hash_table *ht, hash_pos *pos) 1158 1159 { 1160 /* initialize pos for first item in first bucket */ 1161 pos->num_buckets = ht->num_buckets; 1162 pos->hash_bucket = ht->buckets; 1163 pos->curr = 0; 1164 pos->ll_last = NULL; 1165 1166 /* find the first non-empty bucket */ 1167 while(pos->hash_bucket->list.count == 0) 1168 { 1169 pos->hash_bucket++; 1170 if (++pos->curr >= pos->num_buckets) 1171 { 1172 return NULL; 1173 } 1174 } 1175 1176 /* set and return the first item */ 1177 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 1178 return (hash_item_string *)pos->ll_item->datum; 1179 } 1180 1181 1182 /* 1183 * hash_item_string *hash_next_string(hash_pos *pos) 1184 * 1185 * Return the next item in the hash table, using "pos" as a description 1186 * of the present position in the hash table. "pos" also identifies the 1187 * specific hash table. Return NULL if there are no more elements. 1188 */ 1189 1190 hash_item_string * 1191 hash_next_string(hash_pos *pos) 1192 1193 { 1194 llistitem *li; 1195 1196 /* move item to last and check for NULL */ 1197 if ((pos->ll_last = pos->ll_item) == NULL) 1198 { 1199 /* are we really at the end of the hash table? */ 1200 if (pos->curr >= pos->num_buckets) 1201 { 1202 /* yes: return NULL */ 1203 return NULL; 1204 } 1205 /* no: regrab first item in current bucket list (might be NULL) */ 1206 li = LL_FIRST(&(pos->hash_bucket->list)); 1207 } 1208 else 1209 { 1210 /* get the next item in the llist */ 1211 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 1212 } 1213 1214 /* if its NULL we have to find another bucket */ 1215 while (li == NULL) 1216 { 1217 /* locate another bucket */ 1218 pos->ll_last = NULL; 1219 1220 /* move to the next one */ 1221 pos->hash_bucket++; 1222 if (++pos->curr >= pos->num_buckets) 1223 { 1224 /* at the end of the hash table */ 1225 pos->ll_item = NULL; 1226 return NULL; 1227 } 1228 1229 /* get the first element (might be NULL) */ 1230 li = LL_FIRST(&(pos->hash_bucket->list)); 1231 } 1232 1233 /* li is the next element to dish out */ 1234 pos->ll_item = li; 1235 return (hash_item_string *)li->datum; 1236 } 1237 1238 /* 1239 * void *hash_remove_pos_string(hash_pos *pos) 1240 * 1241 * Remove the hash table entry pointed to by position marker "pos". 1242 * The data from the entry is returned upon success, otherwise NULL. 1243 */ 1244 1245 1246 void * 1247 hash_remove_pos_string(hash_pos *pos) 1248 1249 { 1250 llistitem *li; 1251 void *ans; 1252 hash_item_string *hi; 1253 char * key; 1254 1255 /* sanity checks */ 1256 if (pos == NULL || pos->ll_last == pos->ll_item) 1257 { 1258 return NULL; 1259 } 1260 1261 /* at this point pos contains the item to remove (ll_item) 1262 and its predecesor (ll_last) */ 1263 /* extract the item from the llist */ 1264 li = pos->ll_item; 1265 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 1266 1267 /* retain the data */ 1268 hi = (hash_item_string *)li->datum; 1269 ans = hi->value; 1270 1271 /* free up the space */ 1272 key = hi->key; 1273 free(key); 1274 ll_freeitem(li); 1275 1276 /* back up to previous item */ 1277 /* its okay for ll_item to be null: hash_next will detect it */ 1278 pos->ll_item = pos->ll_last; 1279 1280 return ans; 1281 } 1282 1283 1284 1285 /* 1286 * void hash_add_pidthr(hash_table *ht, pidthr_t key, void *value) 1287 * 1288 * Add an element to table "ht". The element is described by 1289 * "key" and "value". Return NULL on success. If the key 1290 * already exists in the table, then no action is taken and 1291 * the data for the existing element is returned. 1292 * Key type is pidthr_t 1293 */ 1294 1295 void * 1296 hash_add_pidthr(hash_table *ht, pidthr_t key, void *value) 1297 1298 { 1299 bucket_t *bucket; 1300 hash_item_pidthr *hi; 1301 hash_item_pidthr *h; 1302 llist *ll; 1303 llistitem *li; 1304 llistitem *newli; 1305 pidthr_t k1; 1306 1307 /* allocate the space we will need */ 1308 newli = ll_newitem(sizeof(hash_item_pidthr)); 1309 hi = (hash_item_pidthr *)newli->datum; 1310 1311 /* fill in the values */ 1312 hi->key = key; 1313 hi->value = value; 1314 1315 /* hash to the bucket */ 1316 bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]); 1317 1318 /* walk the list to make sure we do not have a duplicate */ 1319 ll = &(bucket->list); 1320 li = LL_FIRST(ll); 1321 while (li != NULL) 1322 { 1323 h = (hash_item_pidthr *)li->datum; 1324 k1 = h->key; 1325 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)) 1326 { 1327 /* found one */ 1328 break; 1329 } 1330 li = LL_NEXT(ll, li); 1331 } 1332 li = NULL; 1333 1334 /* is there already one there? */ 1335 if (li == NULL) 1336 { 1337 /* add the unique element to the buckets list */ 1338 ll_add(&(bucket->list), newli); 1339 return NULL; 1340 } 1341 else 1342 { 1343 /* free the stuff we just allocated */ 1344 ll_freeitem(newli); 1345 return ((hash_item_pidthr *)(li->datum))->value; 1346 } 1347 } 1348 1349 /* 1350 * void *hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value) 1351 * 1352 * Replace an existing value in the hash table with a new one and 1353 * return the old value. If the key does not already exist in 1354 * the hash table, add a new element and return NULL. 1355 * Key type is pidthr_t 1356 */ 1357 1358 void * 1359 hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value) 1360 1361 { 1362 bucket_t *bucket; 1363 hash_item_pidthr *hi; 1364 llist *ll; 1365 llistitem *li; 1366 void *result = NULL; 1367 pidthr_t k1; 1368 1369 /* find the bucket */ 1370 bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]); 1371 1372 /* walk the list until we find the existing item */ 1373 ll = &(bucket->list); 1374 li = LL_FIRST(ll); 1375 while (li != NULL) 1376 { 1377 hi = (hash_item_pidthr *)li->datum; 1378 k1 = hi->key; 1379 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)) 1380 { 1381 /* found it: now replace the value with the new one */ 1382 result = hi->value; 1383 hi->value = value; 1384 break; 1385 } 1386 li = LL_NEXT(ll, li); 1387 } 1388 1389 /* if the element wasnt found, add it */ 1390 if (result == NULL) 1391 { 1392 li = ll_newitem(sizeof(hash_item_pidthr)); 1393 hi = (hash_item_pidthr *)li->datum; 1394 hi->key = key; 1395 hi->value = value; 1396 ll_add(&(bucket->list), li); 1397 } 1398 1399 /* return the old value (so it can be freed) */ 1400 return result; 1401 } 1402 1403 /* 1404 * void *hash_lookup_pidthr(hash_table *ht, pidthr_t key) 1405 * 1406 * Look up "key" in "ht" and return the associated value. If "key" 1407 * is not found, return NULL. Key type is pidthr_t 1408 */ 1409 1410 void * 1411 hash_lookup_pidthr(hash_table *ht, pidthr_t key) 1412 1413 { 1414 bucket_t *bucket; 1415 llist *ll; 1416 llistitem *li; 1417 hash_item_pidthr *h; 1418 void *result; 1419 pidthr_t k1; 1420 1421 result = NULL; 1422 if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL) 1423 { 1424 ll = &(bucket->list); 1425 li = LL_FIRST(ll); 1426 while (li != NULL) 1427 { 1428 h = (hash_item_pidthr *)li->datum; 1429 k1 = h->key; 1430 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)) 1431 { 1432 result = h->value; 1433 break; 1434 } 1435 li = LL_NEXT(ll, li); 1436 } 1437 } 1438 return result; 1439 } 1440 1441 /* 1442 * void *hash_remove_pidthr(hash_table *ht, pidthr_t key) 1443 * 1444 * Remove the element associated with "key" from the hash table 1445 * "ht". Return the value or NULL if the key was not found. 1446 */ 1447 1448 void * 1449 hash_remove_pidthr(hash_table *ht, pidthr_t key) 1450 1451 { 1452 bucket_t *bucket; 1453 llist *ll; 1454 llistitem *li; 1455 llistitem *lilast; 1456 hash_item_pidthr *hi; 1457 void *result; 1458 pidthr_t k1; 1459 1460 result = NULL; 1461 if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL) 1462 { 1463 ll = &(bucket->list); 1464 li = LL_FIRST(ll); 1465 lilast = NULL; 1466 while (li != NULL) 1467 { 1468 hi = (hash_item_pidthr *)li->datum; 1469 k1 = hi->key; 1470 if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr)) 1471 { 1472 ll_extract(ll, li, lilast); 1473 result = hi->value; 1474 key = hi->key; 1475 ; 1476 ll_freeitem(li); 1477 break; 1478 } 1479 lilast = li; 1480 li = LL_NEXT(ll, li); 1481 } 1482 } 1483 return result; 1484 } 1485 1486 /* 1487 * hash_item_pidthr *hash_first_pidthr(hash_table *ht, hash_pos *pos) 1488 * 1489 * First function to call when iterating through all items in the hash 1490 * table. Returns the first item in "ht" and initializes "*pos" to track 1491 * the current position. 1492 */ 1493 1494 hash_item_pidthr * 1495 hash_first_pidthr(hash_table *ht, hash_pos *pos) 1496 1497 { 1498 /* initialize pos for first item in first bucket */ 1499 pos->num_buckets = ht->num_buckets; 1500 pos->hash_bucket = ht->buckets; 1501 pos->curr = 0; 1502 pos->ll_last = NULL; 1503 1504 /* find the first non-empty bucket */ 1505 while(pos->hash_bucket->list.count == 0) 1506 { 1507 pos->hash_bucket++; 1508 if (++pos->curr >= pos->num_buckets) 1509 { 1510 return NULL; 1511 } 1512 } 1513 1514 /* set and return the first item */ 1515 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 1516 return (hash_item_pidthr *)pos->ll_item->datum; 1517 } 1518 1519 1520 /* 1521 * hash_item_pidthr *hash_next_pidthr(hash_pos *pos) 1522 * 1523 * Return the next item in the hash table, using "pos" as a description 1524 * of the present position in the hash table. "pos" also identifies the 1525 * specific hash table. Return NULL if there are no more elements. 1526 */ 1527 1528 hash_item_pidthr * 1529 hash_next_pidthr(hash_pos *pos) 1530 1531 { 1532 llistitem *li; 1533 1534 /* move item to last and check for NULL */ 1535 if ((pos->ll_last = pos->ll_item) == NULL) 1536 { 1537 /* are we really at the end of the hash table? */ 1538 if (pos->curr >= pos->num_buckets) 1539 { 1540 /* yes: return NULL */ 1541 return NULL; 1542 } 1543 /* no: regrab first item in current bucket list (might be NULL) */ 1544 li = LL_FIRST(&(pos->hash_bucket->list)); 1545 } 1546 else 1547 { 1548 /* get the next item in the llist */ 1549 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 1550 } 1551 1552 /* if its NULL we have to find another bucket */ 1553 while (li == NULL) 1554 { 1555 /* locate another bucket */ 1556 pos->ll_last = NULL; 1557 1558 /* move to the next one */ 1559 pos->hash_bucket++; 1560 if (++pos->curr >= pos->num_buckets) 1561 { 1562 /* at the end of the hash table */ 1563 pos->ll_item = NULL; 1564 return NULL; 1565 } 1566 1567 /* get the first element (might be NULL) */ 1568 li = LL_FIRST(&(pos->hash_bucket->list)); 1569 } 1570 1571 /* li is the next element to dish out */ 1572 pos->ll_item = li; 1573 return (hash_item_pidthr *)li->datum; 1574 } 1575 1576 /* 1577 * void *hash_remove_pos_pidthr(hash_pos *pos) 1578 * 1579 * Remove the hash table entry pointed to by position marker "pos". 1580 * The data from the entry is returned upon success, otherwise NULL. 1581 */ 1582 1583 1584 void * 1585 hash_remove_pos_pidthr(hash_pos *pos) 1586 1587 { 1588 llistitem *li; 1589 void *ans; 1590 hash_item_pidthr *hi; 1591 pidthr_t key; 1592 1593 /* sanity checks */ 1594 if (pos == NULL || pos->ll_last == pos->ll_item) 1595 { 1596 return NULL; 1597 } 1598 1599 /* at this point pos contains the item to remove (ll_item) 1600 and its predecesor (ll_last) */ 1601 /* extract the item from the llist */ 1602 li = pos->ll_item; 1603 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 1604 1605 /* retain the data */ 1606 hi = (hash_item_pidthr *)li->datum; 1607 ans = hi->value; 1608 1609 /* free up the space */ 1610 key = hi->key; 1611 ; 1612 ll_freeitem(li); 1613 1614 /* back up to previous item */ 1615 /* its okay for ll_item to be null: hash_next will detect it */ 1616 pos->ll_item = pos->ll_last; 1617 1618 return ans; 1619 } 1620 1621 #if HAVE_LWPID_T 1622 1623 1624 /* 1625 * void hash_add_lwpid(hash_table *ht, lwpid_t key, void *value) 1626 * 1627 * Add an element to table "ht". The element is described by 1628 * "key" and "value". Return NULL on success. If the key 1629 * already exists in the table, then no action is taken and 1630 * the data for the existing element is returned. 1631 * Key type is lwpid_t 1632 */ 1633 1634 void * 1635 hash_add_lwpid(hash_table *ht, lwpid_t key, void *value) 1636 1637 { 1638 bucket_t *bucket; 1639 hash_item_lwpid *hi; 1640 hash_item_lwpid *h; 1641 llist *ll; 1642 llistitem *li; 1643 llistitem *newli; 1644 lwpid_t k1; 1645 1646 /* allocate the space we will need */ 1647 newli = ll_newitem(sizeof(hash_item_lwpid)); 1648 hi = (hash_item_lwpid *)newli->datum; 1649 1650 /* fill in the values */ 1651 hi->key = key; 1652 hi->value = value; 1653 1654 /* hash to the bucket */ 1655 bucket = &(ht->buckets[(key % ht->num_buckets)]); 1656 1657 /* walk the list to make sure we do not have a duplicate */ 1658 ll = &(bucket->list); 1659 li = LL_FIRST(ll); 1660 while (li != NULL) 1661 { 1662 h = (hash_item_lwpid *)li->datum; 1663 k1 = h->key; 1664 if (key == k1) 1665 { 1666 /* found one */ 1667 break; 1668 } 1669 li = LL_NEXT(ll, li); 1670 } 1671 li = NULL; 1672 1673 /* is there already one there? */ 1674 if (li == NULL) 1675 { 1676 /* add the unique element to the buckets list */ 1677 ll_add(&(bucket->list), newli); 1678 return NULL; 1679 } 1680 else 1681 { 1682 /* free the stuff we just allocated */ 1683 ll_freeitem(newli); 1684 return ((hash_item_lwpid *)(li->datum))->value; 1685 } 1686 } 1687 1688 /* 1689 * void *hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value) 1690 * 1691 * Replace an existing value in the hash table with a new one and 1692 * return the old value. If the key does not already exist in 1693 * the hash table, add a new element and return NULL. 1694 * Key type is lwpid_t 1695 */ 1696 1697 void * 1698 hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value) 1699 1700 { 1701 bucket_t *bucket; 1702 hash_item_lwpid *hi; 1703 llist *ll; 1704 llistitem *li; 1705 void *result = NULL; 1706 lwpid_t k1; 1707 1708 /* find the bucket */ 1709 bucket = &(ht->buckets[(key % ht->num_buckets)]); 1710 1711 /* walk the list until we find the existing item */ 1712 ll = &(bucket->list); 1713 li = LL_FIRST(ll); 1714 while (li != NULL) 1715 { 1716 hi = (hash_item_lwpid *)li->datum; 1717 k1 = hi->key; 1718 if (key == k1) 1719 { 1720 /* found it: now replace the value with the new one */ 1721 result = hi->value; 1722 hi->value = value; 1723 break; 1724 } 1725 li = LL_NEXT(ll, li); 1726 } 1727 1728 /* if the element wasnt found, add it */ 1729 if (result == NULL) 1730 { 1731 li = ll_newitem(sizeof(hash_item_lwpid)); 1732 hi = (hash_item_lwpid *)li->datum; 1733 hi->key = key; 1734 hi->value = value; 1735 ll_add(&(bucket->list), li); 1736 } 1737 1738 /* return the old value (so it can be freed) */ 1739 return result; 1740 } 1741 1742 /* 1743 * void *hash_lookup_lwpid(hash_table *ht, lwpid_t key) 1744 * 1745 * Look up "key" in "ht" and return the associated value. If "key" 1746 * is not found, return NULL. Key type is lwpid_t 1747 */ 1748 1749 void * 1750 hash_lookup_lwpid(hash_table *ht, lwpid_t key) 1751 1752 { 1753 bucket_t *bucket; 1754 llist *ll; 1755 llistitem *li; 1756 hash_item_lwpid *h; 1757 void *result; 1758 lwpid_t k1; 1759 1760 result = NULL; 1761 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 1762 { 1763 ll = &(bucket->list); 1764 li = LL_FIRST(ll); 1765 while (li != NULL) 1766 { 1767 h = (hash_item_lwpid *)li->datum; 1768 k1 = h->key; 1769 if (key == k1) 1770 { 1771 result = h->value; 1772 break; 1773 } 1774 li = LL_NEXT(ll, li); 1775 } 1776 } 1777 return result; 1778 } 1779 1780 /* 1781 * void *hash_remove_lwpid(hash_table *ht, lwpid_t key) 1782 * 1783 * Remove the element associated with "key" from the hash table 1784 * "ht". Return the value or NULL if the key was not found. 1785 */ 1786 1787 void * 1788 hash_remove_lwpid(hash_table *ht, lwpid_t key) 1789 1790 { 1791 bucket_t *bucket; 1792 llist *ll; 1793 llistitem *li; 1794 llistitem *lilast; 1795 hash_item_lwpid *hi; 1796 void *result; 1797 lwpid_t k1; 1798 1799 result = NULL; 1800 if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL) 1801 { 1802 ll = &(bucket->list); 1803 li = LL_FIRST(ll); 1804 lilast = NULL; 1805 while (li != NULL) 1806 { 1807 hi = (hash_item_lwpid *)li->datum; 1808 k1 = hi->key; 1809 if (key == k1) 1810 { 1811 ll_extract(ll, li, lilast); 1812 result = hi->value; 1813 key = hi->key; 1814 ; 1815 ll_freeitem(li); 1816 break; 1817 } 1818 lilast = li; 1819 li = LL_NEXT(ll, li); 1820 } 1821 } 1822 return result; 1823 } 1824 1825 /* 1826 * hash_item_lwpid *hash_first_lwpid(hash_table *ht, hash_pos *pos) 1827 * 1828 * First function to call when iterating through all items in the hash 1829 * table. Returns the first item in "ht" and initializes "*pos" to track 1830 * the current position. 1831 */ 1832 1833 hash_item_lwpid * 1834 hash_first_lwpid(hash_table *ht, hash_pos *pos) 1835 1836 { 1837 /* initialize pos for first item in first bucket */ 1838 pos->num_buckets = ht->num_buckets; 1839 pos->hash_bucket = ht->buckets; 1840 pos->curr = 0; 1841 pos->ll_last = NULL; 1842 1843 /* find the first non-empty bucket */ 1844 while(pos->hash_bucket->list.count == 0) 1845 { 1846 pos->hash_bucket++; 1847 if (++pos->curr >= pos->num_buckets) 1848 { 1849 return NULL; 1850 } 1851 } 1852 1853 /* set and return the first item */ 1854 pos->ll_item = LL_FIRST(&(pos->hash_bucket->list)); 1855 return (hash_item_lwpid *)pos->ll_item->datum; 1856 } 1857 1858 1859 /* 1860 * hash_item_lwpid *hash_next_lwpid(hash_pos *pos) 1861 * 1862 * Return the next item in the hash table, using "pos" as a description 1863 * of the present position in the hash table. "pos" also identifies the 1864 * specific hash table. Return NULL if there are no more elements. 1865 */ 1866 1867 hash_item_lwpid * 1868 hash_next_lwpid(hash_pos *pos) 1869 1870 { 1871 llistitem *li; 1872 1873 /* move item to last and check for NULL */ 1874 if ((pos->ll_last = pos->ll_item) == NULL) 1875 { 1876 /* are we really at the end of the hash table? */ 1877 if (pos->curr >= pos->num_buckets) 1878 { 1879 /* yes: return NULL */ 1880 return NULL; 1881 } 1882 /* no: regrab first item in current bucket list (might be NULL) */ 1883 li = LL_FIRST(&(pos->hash_bucket->list)); 1884 } 1885 else 1886 { 1887 /* get the next item in the llist */ 1888 li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item); 1889 } 1890 1891 /* if its NULL we have to find another bucket */ 1892 while (li == NULL) 1893 { 1894 /* locate another bucket */ 1895 pos->ll_last = NULL; 1896 1897 /* move to the next one */ 1898 pos->hash_bucket++; 1899 if (++pos->curr >= pos->num_buckets) 1900 { 1901 /* at the end of the hash table */ 1902 pos->ll_item = NULL; 1903 return NULL; 1904 } 1905 1906 /* get the first element (might be NULL) */ 1907 li = LL_FIRST(&(pos->hash_bucket->list)); 1908 } 1909 1910 /* li is the next element to dish out */ 1911 pos->ll_item = li; 1912 return (hash_item_lwpid *)li->datum; 1913 } 1914 1915 /* 1916 * void *hash_remove_pos_lwpid(hash_pos *pos) 1917 * 1918 * Remove the hash table entry pointed to by position marker "pos". 1919 * The data from the entry is returned upon success, otherwise NULL. 1920 */ 1921 1922 1923 void * 1924 hash_remove_pos_lwpid(hash_pos *pos) 1925 1926 { 1927 llistitem *li; 1928 void *ans; 1929 hash_item_lwpid *hi; 1930 lwpid_t key; 1931 1932 /* sanity checks */ 1933 if (pos == NULL || pos->ll_last == pos->ll_item) 1934 { 1935 return NULL; 1936 } 1937 1938 /* at this point pos contains the item to remove (ll_item) 1939 and its predecesor (ll_last) */ 1940 /* extract the item from the llist */ 1941 li = pos->ll_item; 1942 ll_extract(&(pos->hash_bucket->list), li, pos->ll_last); 1943 1944 /* retain the data */ 1945 hi = (hash_item_lwpid *)li->datum; 1946 ans = hi->value; 1947 1948 /* free up the space */ 1949 key = hi->key; 1950 ; 1951 ll_freeitem(li); 1952 1953 /* back up to previous item */ 1954 /* its okay for ll_item to be null: hash_next will detect it */ 1955 pos->ll_item = pos->ll_last; 1956 1957 return ans; 1958 } 1959 1960 #endif 1961