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