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