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