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