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