aboutsummaryrefslogtreecommitdiffstats
path: root/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'hash.c')
-rw-r--r--hash.c2001
1 files changed, 2001 insertions, 0 deletions
diff --git a/hash.c b/hash.c
new file mode 100644
index 000000000000..f65fe9210562
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,2001 @@
+/*
+ * Copyright (c) 1984 through 2008, William LeFebvre
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of William LeFebvre nor the names of other
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/* hash.m4c */
+
+/* The file hash.c is generated from hash.m4c via the preprocessor M4 */
+
+/*
+ * Hash table functions: init, add, lookup, first, next, sizeinfo.
+ * This is a conventional "bucket hash". The key is hashed in to a number
+ * less than or equal to the number of buckets and the result is used
+ * to index in to the array of buckets. Each bucket is a linked list
+ * that contains all the key/value pairs which hashed to that index.
+ */
+
+#include "config.h"
+
+#if STDC_HEADERS
+#include <string.h>
+#include <stdlib.h>
+#define memzero(a, b) memset((a), 0, (b))
+#else /* !STDC_HEADERS */
+#ifdef HAVE_MEMCPY
+#define memzero(a, b) memset((a), 0, (b))
+#else
+#define memcpy(a, b, c) bcopy((b), (a), (c))
+#define memzero(a, b) bzero((a), (b))
+#define memcmp(a, b, c) bcmp((a), (b), (c))
+#endif /* HAVE_MEMCPY */
+#ifdef HAVE_STRINGS_H
+#include <strings.h>
+#else
+#ifdef HAVE_STRING_H
+#include <string.h>
+#endif
+#endif
+void *malloc();
+void free();
+char *strdup();
+#endif /* !STDC_HEADERS */
+
+/* After all that there are still some systems that don't have NULL defined */
+#ifndef NULL
+#define NULL 0
+#endif
+
+#ifdef HAVE_MATH_H
+#include <math.h>
+#endif
+
+#if !HAVE_PID_T
+typedef long pid_t;
+#endif
+#if !HAVE_ID_T
+typedef long id_t;
+#endif
+
+#include "hash.h"
+
+
+
+
+
+
+static int
+next_prime(int x)
+
+{
+ double i, j;
+ int f;
+
+ i = x;
+ while (i++)
+ {
+ f=1;
+ for (j=2; j<i; j++)
+ {
+ if ((i/j)==floor(i/j))
+ {
+ f=0;
+ break;
+ }
+ }
+ if (f)
+ {
+ return (int)i;
+ }
+ }
+ return 1;
+}
+
+/* string hashes */
+
+static int
+string_hash(hash_table *ht, char *key)
+
+{
+ unsigned long s = 0;
+ unsigned char ch;
+ int shifting = 24;
+
+ while ((ch = (unsigned char)*key++) != '\0')
+ {
+ if (shifting == 0)
+ {
+ s = s + ch;
+ shifting = 24;
+ }
+ else
+ {
+ s = s + (ch << shifting);
+ shifting -= 8;
+ }
+ }
+
+ return (s % ht->num_buckets);
+}
+
+void ll_init(llist *q)
+
+{
+ q->head = NULL;
+ q->count = 0;
+}
+
+llistitem *ll_newitem(int size)
+
+{
+ llistitem *qi;
+
+ qi = (llistitem *)malloc(sizeof(llistitem) + size);
+ qi->datum = ((void *)qi + sizeof(llistitem));
+ return qi;
+}
+
+void ll_freeitem(llistitem *li)
+
+{
+ free(li);
+}
+
+void ll_add(llist *q, llistitem *new)
+
+{
+ new->next = q->head;
+ q->head = new;
+ q->count++;
+}
+
+void ll_extract(llist *q, llistitem *qi, llistitem *last)
+
+{
+ if (last == NULL)
+ {
+ q->head = qi->next;
+ }
+ else
+ {
+ last->next = qi->next;
+ }
+ qi->next = NULL;
+ q->count--;
+}
+
+#define LL_FIRST(q) ((q)->head)
+llistitem *
+ll_first(llist *q)
+
+{
+ return q->head;
+}
+
+#define LL_NEXT(q, qi) ((qi) != NULL ? (qi)->next : NULL)
+llistitem *
+ll_next(llist *q, llistitem *qi)
+
+{
+ return (qi != NULL ? qi->next : NULL);
+}
+
+#define LL_ISEMPTY(ll) ((ll)->count == 0)
+int
+ll_isempty(llist *ll)
+
+{
+ return (ll->count == 0);
+}
+
+/*
+ * hash_table *hash_create(int num)
+ *
+ * Creates a hash table structure with at least "num" buckets.
+ */
+
+hash_table *
+hash_create(int num)
+
+{
+ hash_table *result;
+ bucket_t *b;
+ int bytes;
+ int i;
+
+ /* create the resultant structure */
+ result = (hash_table *)malloc(sizeof(hash_table));
+
+ /* adjust bucket count to be prime */
+ num = next_prime(num);
+
+ /* create the buckets */
+ bytes = sizeof(bucket_t) * num;
+ result->buckets = b = (bucket_t *)malloc(bytes);
+ result->num_buckets = num;
+
+ /* create each bucket as a linked list */
+ i = num;
+ while (--i >= 0)
+ {
+ ll_init(&(b->list));
+ b++;
+ }
+
+ return result;
+}
+
+/*
+ * unsigned int hash_count(hash_table *ht)
+ *
+ * Return total number of elements contained in hash table.
+ */
+
+unsigned int
+hash_count(hash_table *ht)
+
+{
+ register int i = 0;
+ register int cnt = 0;
+ register bucket_t *bucket;
+
+ bucket = ht->buckets;
+ while (i++ < ht->num_buckets)
+ {
+ cnt += bucket->list.count;
+ bucket++;
+ }
+
+ return cnt;
+}
+
+/*
+ * void hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
+ *
+ * Fill in "sizes" with information about bucket lengths in hash
+ * table "max".
+ */
+
+void
+hash_sizeinfo(unsigned int *sizes, int max, hash_table *ht)
+
+{
+ register int i;
+ register int idx;
+ register bucket_t *bucket;
+
+ memzero(sizes, max * sizeof(unsigned int));
+
+ bucket = ht->buckets;
+ i = 0;
+ while (i++ < ht->num_buckets)
+ {
+ idx = bucket->list.count;
+ sizes[idx >= max ? max-1 : idx]++;
+ bucket++;
+ }
+}
+
+
+
+
+
+
+
+/*
+ * void hash_add_uint(hash_table *ht, unsigned int key, void *value)
+ *
+ * Add an element to table "ht". The element is described by
+ * "key" and "value". Return NULL on success. If the key
+ * already exists in the table, then no action is taken and
+ * the data for the existing element is returned.
+ * Key type is unsigned int
+ */
+
+void *
+hash_add_uint(hash_table *ht, unsigned int key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_uint *hi;
+ hash_item_uint *h;
+ llist *ll;
+ llistitem *li;
+ llistitem *newli;
+ unsigned int k1;
+
+ /* allocate the space we will need */
+ newli = ll_newitem(sizeof(hash_item_uint));
+ hi = (hash_item_uint *)newli->datum;
+
+ /* fill in the values */
+ hi->key = key;
+ hi->value = value;
+
+ /* hash to the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list to make sure we do not have a duplicate */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_uint *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ /* found one */
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ li = NULL;
+
+ /* is there already one there? */
+ if (li == NULL)
+ {
+ /* add the unique element to the buckets list */
+ ll_add(&(bucket->list), newli);
+ return NULL;
+ }
+ else
+ {
+ /* free the stuff we just allocated */
+ ll_freeitem(newli);
+ return ((hash_item_uint *)(li->datum))->value;
+ }
+}
+
+/*
+ * void *hash_replace_uint(hash_table *ht, unsigned int key, void *value)
+ *
+ * Replace an existing value in the hash table with a new one and
+ * return the old value. If the key does not already exist in
+ * the hash table, add a new element and return NULL.
+ * Key type is unsigned int
+ */
+
+void *
+hash_replace_uint(hash_table *ht, unsigned int key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_uint *hi;
+ llist *ll;
+ llistitem *li;
+ void *result = NULL;
+ unsigned int k1;
+
+ /* find the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list until we find the existing item */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ hi = (hash_item_uint *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ /* found it: now replace the value with the new one */
+ result = hi->value;
+ hi->value = value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+
+ /* if the element wasnt found, add it */
+ if (result == NULL)
+ {
+ li = ll_newitem(sizeof(hash_item_uint));
+ hi = (hash_item_uint *)li->datum;
+ hi->key = key;
+ hi->value = value;
+ ll_add(&(bucket->list), li);
+ }
+
+ /* return the old value (so it can be freed) */
+ return result;
+}
+
+/*
+ * void *hash_lookup_uint(hash_table *ht, unsigned int key)
+ *
+ * Look up "key" in "ht" and return the associated value. If "key"
+ * is not found, return NULL. Key type is unsigned int
+ */
+
+void *
+hash_lookup_uint(hash_table *ht, unsigned int key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ hash_item_uint *h;
+ void *result;
+ unsigned int k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_uint *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ result = h->value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * void *hash_remove_uint(hash_table *ht, unsigned int key)
+ *
+ * Remove the element associated with "key" from the hash table
+ * "ht". Return the value or NULL if the key was not found.
+ */
+
+void *
+hash_remove_uint(hash_table *ht, unsigned int key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ llistitem *lilast;
+ hash_item_uint *hi;
+ void *result;
+ unsigned int k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ lilast = NULL;
+ while (li != NULL)
+ {
+ hi = (hash_item_uint *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ ll_extract(ll, li, lilast);
+ result = hi->value;
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+ break;
+ }
+ lilast = li;
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * hash_item_uint *hash_first_uint(hash_table *ht, hash_pos *pos)
+ *
+ * First function to call when iterating through all items in the hash
+ * table. Returns the first item in "ht" and initializes "*pos" to track
+ * the current position.
+ */
+
+hash_item_uint *
+hash_first_uint(hash_table *ht, hash_pos *pos)
+
+{
+ /* initialize pos for first item in first bucket */
+ pos->num_buckets = ht->num_buckets;
+ pos->hash_bucket = ht->buckets;
+ pos->curr = 0;
+ pos->ll_last = NULL;
+
+ /* find the first non-empty bucket */
+ while(pos->hash_bucket->list.count == 0)
+ {
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ return NULL;
+ }
+ }
+
+ /* set and return the first item */
+ pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
+ return (hash_item_uint *)pos->ll_item->datum;
+}
+
+
+/*
+ * hash_item_uint *hash_next_uint(hash_pos *pos)
+ *
+ * Return the next item in the hash table, using "pos" as a description
+ * of the present position in the hash table. "pos" also identifies the
+ * specific hash table. Return NULL if there are no more elements.
+ */
+
+hash_item_uint *
+hash_next_uint(hash_pos *pos)
+
+{
+ llistitem *li;
+
+ /* move item to last and check for NULL */
+ if ((pos->ll_last = pos->ll_item) == NULL)
+ {
+ /* are we really at the end of the hash table? */
+ if (pos->curr >= pos->num_buckets)
+ {
+ /* yes: return NULL */
+ return NULL;
+ }
+ /* no: regrab first item in current bucket list (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+ else
+ {
+ /* get the next item in the llist */
+ li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
+ }
+
+ /* if its NULL we have to find another bucket */
+ while (li == NULL)
+ {
+ /* locate another bucket */
+ pos->ll_last = NULL;
+
+ /* move to the next one */
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ /* at the end of the hash table */
+ pos->ll_item = NULL;
+ return NULL;
+ }
+
+ /* get the first element (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+
+ /* li is the next element to dish out */
+ pos->ll_item = li;
+ return (hash_item_uint *)li->datum;
+}
+
+/*
+ * void *hash_remove_pos_uint(hash_pos *pos)
+ *
+ * Remove the hash table entry pointed to by position marker "pos".
+ * The data from the entry is returned upon success, otherwise NULL.
+ */
+
+
+void *
+hash_remove_pos_uint(hash_pos *pos)
+
+{
+ llistitem *li;
+ void *ans;
+ hash_item_uint *hi;
+ unsigned int key;
+
+ /* sanity checks */
+ if (pos == NULL || pos->ll_last == pos->ll_item)
+ {
+ return NULL;
+ }
+
+ /* at this point pos contains the item to remove (ll_item)
+ and its predecesor (ll_last) */
+ /* extract the item from the llist */
+ li = pos->ll_item;
+ ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
+
+ /* retain the data */
+ hi = (hash_item_uint *)li->datum;
+ ans = hi->value;
+
+ /* free up the space */
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+
+ /* back up to previous item */
+ /* its okay for ll_item to be null: hash_next will detect it */
+ pos->ll_item = pos->ll_last;
+
+ return ans;
+}
+
+
+
+/*
+ * void hash_add_pid(hash_table *ht, pid_t key, void *value)
+ *
+ * Add an element to table "ht". The element is described by
+ * "key" and "value". Return NULL on success. If the key
+ * already exists in the table, then no action is taken and
+ * the data for the existing element is returned.
+ * Key type is pid_t
+ */
+
+void *
+hash_add_pid(hash_table *ht, pid_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_pid *hi;
+ hash_item_pid *h;
+ llist *ll;
+ llistitem *li;
+ llistitem *newli;
+ pid_t k1;
+
+ /* allocate the space we will need */
+ newli = ll_newitem(sizeof(hash_item_pid));
+ hi = (hash_item_pid *)newli->datum;
+
+ /* fill in the values */
+ hi->key = key;
+ hi->value = value;
+
+ /* hash to the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list to make sure we do not have a duplicate */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_pid *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ /* found one */
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ li = NULL;
+
+ /* is there already one there? */
+ if (li == NULL)
+ {
+ /* add the unique element to the buckets list */
+ ll_add(&(bucket->list), newli);
+ return NULL;
+ }
+ else
+ {
+ /* free the stuff we just allocated */
+ ll_freeitem(newli);
+ return ((hash_item_pid *)(li->datum))->value;
+ }
+}
+
+/*
+ * void *hash_replace_pid(hash_table *ht, pid_t key, void *value)
+ *
+ * Replace an existing value in the hash table with a new one and
+ * return the old value. If the key does not already exist in
+ * the hash table, add a new element and return NULL.
+ * Key type is pid_t
+ */
+
+void *
+hash_replace_pid(hash_table *ht, pid_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_pid *hi;
+ llist *ll;
+ llistitem *li;
+ void *result = NULL;
+ pid_t k1;
+
+ /* find the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list until we find the existing item */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ hi = (hash_item_pid *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ /* found it: now replace the value with the new one */
+ result = hi->value;
+ hi->value = value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+
+ /* if the element wasnt found, add it */
+ if (result == NULL)
+ {
+ li = ll_newitem(sizeof(hash_item_pid));
+ hi = (hash_item_pid *)li->datum;
+ hi->key = key;
+ hi->value = value;
+ ll_add(&(bucket->list), li);
+ }
+
+ /* return the old value (so it can be freed) */
+ return result;
+}
+
+/*
+ * void *hash_lookup_pid(hash_table *ht, pid_t key)
+ *
+ * Look up "key" in "ht" and return the associated value. If "key"
+ * is not found, return NULL. Key type is pid_t
+ */
+
+void *
+hash_lookup_pid(hash_table *ht, pid_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ hash_item_pid *h;
+ void *result;
+ pid_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_pid *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ result = h->value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * void *hash_remove_pid(hash_table *ht, pid_t key)
+ *
+ * Remove the element associated with "key" from the hash table
+ * "ht". Return the value or NULL if the key was not found.
+ */
+
+void *
+hash_remove_pid(hash_table *ht, pid_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ llistitem *lilast;
+ hash_item_pid *hi;
+ void *result;
+ pid_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ lilast = NULL;
+ while (li != NULL)
+ {
+ hi = (hash_item_pid *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ ll_extract(ll, li, lilast);
+ result = hi->value;
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+ break;
+ }
+ lilast = li;
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * hash_item_pid *hash_first_pid(hash_table *ht, hash_pos *pos)
+ *
+ * First function to call when iterating through all items in the hash
+ * table. Returns the first item in "ht" and initializes "*pos" to track
+ * the current position.
+ */
+
+hash_item_pid *
+hash_first_pid(hash_table *ht, hash_pos *pos)
+
+{
+ /* initialize pos for first item in first bucket */
+ pos->num_buckets = ht->num_buckets;
+ pos->hash_bucket = ht->buckets;
+ pos->curr = 0;
+ pos->ll_last = NULL;
+
+ /* find the first non-empty bucket */
+ while(pos->hash_bucket->list.count == 0)
+ {
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ return NULL;
+ }
+ }
+
+ /* set and return the first item */
+ pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
+ return (hash_item_pid *)pos->ll_item->datum;
+}
+
+
+/*
+ * hash_item_pid *hash_next_pid(hash_pos *pos)
+ *
+ * Return the next item in the hash table, using "pos" as a description
+ * of the present position in the hash table. "pos" also identifies the
+ * specific hash table. Return NULL if there are no more elements.
+ */
+
+hash_item_pid *
+hash_next_pid(hash_pos *pos)
+
+{
+ llistitem *li;
+
+ /* move item to last and check for NULL */
+ if ((pos->ll_last = pos->ll_item) == NULL)
+ {
+ /* are we really at the end of the hash table? */
+ if (pos->curr >= pos->num_buckets)
+ {
+ /* yes: return NULL */
+ return NULL;
+ }
+ /* no: regrab first item in current bucket list (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+ else
+ {
+ /* get the next item in the llist */
+ li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
+ }
+
+ /* if its NULL we have to find another bucket */
+ while (li == NULL)
+ {
+ /* locate another bucket */
+ pos->ll_last = NULL;
+
+ /* move to the next one */
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ /* at the end of the hash table */
+ pos->ll_item = NULL;
+ return NULL;
+ }
+
+ /* get the first element (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+
+ /* li is the next element to dish out */
+ pos->ll_item = li;
+ return (hash_item_pid *)li->datum;
+}
+
+/*
+ * void *hash_remove_pos_pid(hash_pos *pos)
+ *
+ * Remove the hash table entry pointed to by position marker "pos".
+ * The data from the entry is returned upon success, otherwise NULL.
+ */
+
+
+void *
+hash_remove_pos_pid(hash_pos *pos)
+
+{
+ llistitem *li;
+ void *ans;
+ hash_item_pid *hi;
+ pid_t key;
+
+ /* sanity checks */
+ if (pos == NULL || pos->ll_last == pos->ll_item)
+ {
+ return NULL;
+ }
+
+ /* at this point pos contains the item to remove (ll_item)
+ and its predecesor (ll_last) */
+ /* extract the item from the llist */
+ li = pos->ll_item;
+ ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
+
+ /* retain the data */
+ hi = (hash_item_pid *)li->datum;
+ ans = hi->value;
+
+ /* free up the space */
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+
+ /* back up to previous item */
+ /* its okay for ll_item to be null: hash_next will detect it */
+ pos->ll_item = pos->ll_last;
+
+ return ans;
+}
+
+
+
+/*
+ * void hash_add_string(hash_table *ht, char * key, void *value)
+ *
+ * Add an element to table "ht". The element is described by
+ * "key" and "value". Return NULL on success. If the key
+ * already exists in the table, then no action is taken and
+ * the data for the existing element is returned.
+ * Key type is char *
+ */
+
+void *
+hash_add_string(hash_table *ht, char * key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_string *hi;
+ hash_item_string *h;
+ llist *ll;
+ llistitem *li;
+ llistitem *newli;
+ char * k1;
+
+ /* allocate the space we will need */
+ newli = ll_newitem(sizeof(hash_item_string));
+ hi = (hash_item_string *)newli->datum;
+
+ /* fill in the values */
+ hi->key = strdup(key);
+ hi->value = value;
+
+ /* hash to the bucket */
+ bucket = &(ht->buckets[string_hash(ht, key)]);
+
+ /* walk the list to make sure we do not have a duplicate */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_string *)li->datum;
+ k1 = h->key;
+ if (strcmp(key, k1) == 0)
+ {
+ /* found one */
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ li = NULL;
+
+ /* is there already one there? */
+ if (li == NULL)
+ {
+ /* add the unique element to the buckets list */
+ ll_add(&(bucket->list), newli);
+ return NULL;
+ }
+ else
+ {
+ /* free the stuff we just allocated */
+ ll_freeitem(newli);
+ return ((hash_item_string *)(li->datum))->value;
+ }
+}
+
+/*
+ * void *hash_replace_string(hash_table *ht, char * key, void *value)
+ *
+ * Replace an existing value in the hash table with a new one and
+ * return the old value. If the key does not already exist in
+ * the hash table, add a new element and return NULL.
+ * Key type is char *
+ */
+
+void *
+hash_replace_string(hash_table *ht, char * key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_string *hi;
+ llist *ll;
+ llistitem *li;
+ void *result = NULL;
+ char * k1;
+
+ /* find the bucket */
+ bucket = &(ht->buckets[string_hash(ht, key)]);
+
+ /* walk the list until we find the existing item */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ hi = (hash_item_string *)li->datum;
+ k1 = hi->key;
+ if (strcmp(key, k1) == 0)
+ {
+ /* found it: now replace the value with the new one */
+ result = hi->value;
+ hi->value = value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+
+ /* if the element wasnt found, add it */
+ if (result == NULL)
+ {
+ li = ll_newitem(sizeof(hash_item_string));
+ hi = (hash_item_string *)li->datum;
+ hi->key = strdup(key);
+ hi->value = value;
+ ll_add(&(bucket->list), li);
+ }
+
+ /* return the old value (so it can be freed) */
+ return result;
+}
+
+/*
+ * void *hash_lookup_string(hash_table *ht, char * key)
+ *
+ * Look up "key" in "ht" and return the associated value. If "key"
+ * is not found, return NULL. Key type is char *
+ */
+
+void *
+hash_lookup_string(hash_table *ht, char * key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ hash_item_string *h;
+ void *result;
+ char * k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_string *)li->datum;
+ k1 = h->key;
+ if (strcmp(key, k1) == 0)
+ {
+ result = h->value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * void *hash_remove_string(hash_table *ht, char * key)
+ *
+ * Remove the element associated with "key" from the hash table
+ * "ht". Return the value or NULL if the key was not found.
+ */
+
+void *
+hash_remove_string(hash_table *ht, char * key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ llistitem *lilast;
+ hash_item_string *hi;
+ void *result;
+ char * k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[string_hash(ht, key)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ lilast = NULL;
+ while (li != NULL)
+ {
+ hi = (hash_item_string *)li->datum;
+ k1 = hi->key;
+ if (strcmp(key, k1) == 0)
+ {
+ ll_extract(ll, li, lilast);
+ result = hi->value;
+ key = hi->key;
+ free(key);
+ ll_freeitem(li);
+ break;
+ }
+ lilast = li;
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * hash_item_string *hash_first_string(hash_table *ht, hash_pos *pos)
+ *
+ * First function to call when iterating through all items in the hash
+ * table. Returns the first item in "ht" and initializes "*pos" to track
+ * the current position.
+ */
+
+hash_item_string *
+hash_first_string(hash_table *ht, hash_pos *pos)
+
+{
+ /* initialize pos for first item in first bucket */
+ pos->num_buckets = ht->num_buckets;
+ pos->hash_bucket = ht->buckets;
+ pos->curr = 0;
+ pos->ll_last = NULL;
+
+ /* find the first non-empty bucket */
+ while(pos->hash_bucket->list.count == 0)
+ {
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ return NULL;
+ }
+ }
+
+ /* set and return the first item */
+ pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
+ return (hash_item_string *)pos->ll_item->datum;
+}
+
+
+/*
+ * hash_item_string *hash_next_string(hash_pos *pos)
+ *
+ * Return the next item in the hash table, using "pos" as a description
+ * of the present position in the hash table. "pos" also identifies the
+ * specific hash table. Return NULL if there are no more elements.
+ */
+
+hash_item_string *
+hash_next_string(hash_pos *pos)
+
+{
+ llistitem *li;
+
+ /* move item to last and check for NULL */
+ if ((pos->ll_last = pos->ll_item) == NULL)
+ {
+ /* are we really at the end of the hash table? */
+ if (pos->curr >= pos->num_buckets)
+ {
+ /* yes: return NULL */
+ return NULL;
+ }
+ /* no: regrab first item in current bucket list (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+ else
+ {
+ /* get the next item in the llist */
+ li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
+ }
+
+ /* if its NULL we have to find another bucket */
+ while (li == NULL)
+ {
+ /* locate another bucket */
+ pos->ll_last = NULL;
+
+ /* move to the next one */
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ /* at the end of the hash table */
+ pos->ll_item = NULL;
+ return NULL;
+ }
+
+ /* get the first element (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+
+ /* li is the next element to dish out */
+ pos->ll_item = li;
+ return (hash_item_string *)li->datum;
+}
+
+/*
+ * void *hash_remove_pos_string(hash_pos *pos)
+ *
+ * Remove the hash table entry pointed to by position marker "pos".
+ * The data from the entry is returned upon success, otherwise NULL.
+ */
+
+
+void *
+hash_remove_pos_string(hash_pos *pos)
+
+{
+ llistitem *li;
+ void *ans;
+ hash_item_string *hi;
+ char * key;
+
+ /* sanity checks */
+ if (pos == NULL || pos->ll_last == pos->ll_item)
+ {
+ return NULL;
+ }
+
+ /* at this point pos contains the item to remove (ll_item)
+ and its predecesor (ll_last) */
+ /* extract the item from the llist */
+ li = pos->ll_item;
+ ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
+
+ /* retain the data */
+ hi = (hash_item_string *)li->datum;
+ ans = hi->value;
+
+ /* free up the space */
+ key = hi->key;
+ free(key);
+ ll_freeitem(li);
+
+ /* back up to previous item */
+ /* its okay for ll_item to be null: hash_next will detect it */
+ pos->ll_item = pos->ll_last;
+
+ return ans;
+}
+
+
+
+/*
+ * void hash_add_pidthr(hash_table *ht, pidthr_t key, void *value)
+ *
+ * Add an element to table "ht". The element is described by
+ * "key" and "value". Return NULL on success. If the key
+ * already exists in the table, then no action is taken and
+ * the data for the existing element is returned.
+ * Key type is pidthr_t
+ */
+
+void *
+hash_add_pidthr(hash_table *ht, pidthr_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_pidthr *hi;
+ hash_item_pidthr *h;
+ llist *ll;
+ llistitem *li;
+ llistitem *newli;
+ pidthr_t k1;
+
+ /* allocate the space we will need */
+ newli = ll_newitem(sizeof(hash_item_pidthr));
+ hi = (hash_item_pidthr *)newli->datum;
+
+ /* fill in the values */
+ hi->key = key;
+ hi->value = value;
+
+ /* hash to the bucket */
+ bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]);
+
+ /* walk the list to make sure we do not have a duplicate */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_pidthr *)li->datum;
+ k1 = h->key;
+ if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
+ {
+ /* found one */
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ li = NULL;
+
+ /* is there already one there? */
+ if (li == NULL)
+ {
+ /* add the unique element to the buckets list */
+ ll_add(&(bucket->list), newli);
+ return NULL;
+ }
+ else
+ {
+ /* free the stuff we just allocated */
+ ll_freeitem(newli);
+ return ((hash_item_pidthr *)(li->datum))->value;
+ }
+}
+
+/*
+ * void *hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value)
+ *
+ * Replace an existing value in the hash table with a new one and
+ * return the old value. If the key does not already exist in
+ * the hash table, add a new element and return NULL.
+ * Key type is pidthr_t
+ */
+
+void *
+hash_replace_pidthr(hash_table *ht, pidthr_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_pidthr *hi;
+ llist *ll;
+ llistitem *li;
+ void *result = NULL;
+ pidthr_t k1;
+
+ /* find the bucket */
+ bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)]);
+
+ /* walk the list until we find the existing item */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ hi = (hash_item_pidthr *)li->datum;
+ k1 = hi->key;
+ if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
+ {
+ /* found it: now replace the value with the new one */
+ result = hi->value;
+ hi->value = value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+
+ /* if the element wasnt found, add it */
+ if (result == NULL)
+ {
+ li = ll_newitem(sizeof(hash_item_pidthr));
+ hi = (hash_item_pidthr *)li->datum;
+ hi->key = key;
+ hi->value = value;
+ ll_add(&(bucket->list), li);
+ }
+
+ /* return the old value (so it can be freed) */
+ return result;
+}
+
+/*
+ * void *hash_lookup_pidthr(hash_table *ht, pidthr_t key)
+ *
+ * Look up "key" in "ht" and return the associated value. If "key"
+ * is not found, return NULL. Key type is pidthr_t
+ */
+
+void *
+hash_lookup_pidthr(hash_table *ht, pidthr_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ hash_item_pidthr *h;
+ void *result;
+ pidthr_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_pidthr *)li->datum;
+ k1 = h->key;
+ if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
+ {
+ result = h->value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * void *hash_remove_pidthr(hash_table *ht, pidthr_t key)
+ *
+ * Remove the element associated with "key" from the hash table
+ * "ht". Return the value or NULL if the key was not found.
+ */
+
+void *
+hash_remove_pidthr(hash_table *ht, pidthr_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ llistitem *lilast;
+ hash_item_pidthr *hi;
+ void *result;
+ pidthr_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[((key.k_thr * 10000 + key.k_pid) % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ lilast = NULL;
+ while (li != NULL)
+ {
+ hi = (hash_item_pidthr *)li->datum;
+ k1 = hi->key;
+ if ((key.k_pid == k1.k_pid && key.k_thr == k1.k_thr))
+ {
+ ll_extract(ll, li, lilast);
+ result = hi->value;
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+ break;
+ }
+ lilast = li;
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * hash_item_pidthr *hash_first_pidthr(hash_table *ht, hash_pos *pos)
+ *
+ * First function to call when iterating through all items in the hash
+ * table. Returns the first item in "ht" and initializes "*pos" to track
+ * the current position.
+ */
+
+hash_item_pidthr *
+hash_first_pidthr(hash_table *ht, hash_pos *pos)
+
+{
+ /* initialize pos for first item in first bucket */
+ pos->num_buckets = ht->num_buckets;
+ pos->hash_bucket = ht->buckets;
+ pos->curr = 0;
+ pos->ll_last = NULL;
+
+ /* find the first non-empty bucket */
+ while(pos->hash_bucket->list.count == 0)
+ {
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ return NULL;
+ }
+ }
+
+ /* set and return the first item */
+ pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
+ return (hash_item_pidthr *)pos->ll_item->datum;
+}
+
+
+/*
+ * hash_item_pidthr *hash_next_pidthr(hash_pos *pos)
+ *
+ * Return the next item in the hash table, using "pos" as a description
+ * of the present position in the hash table. "pos" also identifies the
+ * specific hash table. Return NULL if there are no more elements.
+ */
+
+hash_item_pidthr *
+hash_next_pidthr(hash_pos *pos)
+
+{
+ llistitem *li;
+
+ /* move item to last and check for NULL */
+ if ((pos->ll_last = pos->ll_item) == NULL)
+ {
+ /* are we really at the end of the hash table? */
+ if (pos->curr >= pos->num_buckets)
+ {
+ /* yes: return NULL */
+ return NULL;
+ }
+ /* no: regrab first item in current bucket list (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+ else
+ {
+ /* get the next item in the llist */
+ li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
+ }
+
+ /* if its NULL we have to find another bucket */
+ while (li == NULL)
+ {
+ /* locate another bucket */
+ pos->ll_last = NULL;
+
+ /* move to the next one */
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ /* at the end of the hash table */
+ pos->ll_item = NULL;
+ return NULL;
+ }
+
+ /* get the first element (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+
+ /* li is the next element to dish out */
+ pos->ll_item = li;
+ return (hash_item_pidthr *)li->datum;
+}
+
+/*
+ * void *hash_remove_pos_pidthr(hash_pos *pos)
+ *
+ * Remove the hash table entry pointed to by position marker "pos".
+ * The data from the entry is returned upon success, otherwise NULL.
+ */
+
+
+void *
+hash_remove_pos_pidthr(hash_pos *pos)
+
+{
+ llistitem *li;
+ void *ans;
+ hash_item_pidthr *hi;
+ pidthr_t key;
+
+ /* sanity checks */
+ if (pos == NULL || pos->ll_last == pos->ll_item)
+ {
+ return NULL;
+ }
+
+ /* at this point pos contains the item to remove (ll_item)
+ and its predecesor (ll_last) */
+ /* extract the item from the llist */
+ li = pos->ll_item;
+ ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
+
+ /* retain the data */
+ hi = (hash_item_pidthr *)li->datum;
+ ans = hi->value;
+
+ /* free up the space */
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+
+ /* back up to previous item */
+ /* its okay for ll_item to be null: hash_next will detect it */
+ pos->ll_item = pos->ll_last;
+
+ return ans;
+}
+
+#if HAVE_LWPID_T
+
+
+/*
+ * void hash_add_lwpid(hash_table *ht, lwpid_t key, void *value)
+ *
+ * Add an element to table "ht". The element is described by
+ * "key" and "value". Return NULL on success. If the key
+ * already exists in the table, then no action is taken and
+ * the data for the existing element is returned.
+ * Key type is lwpid_t
+ */
+
+void *
+hash_add_lwpid(hash_table *ht, lwpid_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_lwpid *hi;
+ hash_item_lwpid *h;
+ llist *ll;
+ llistitem *li;
+ llistitem *newli;
+ lwpid_t k1;
+
+ /* allocate the space we will need */
+ newli = ll_newitem(sizeof(hash_item_lwpid));
+ hi = (hash_item_lwpid *)newli->datum;
+
+ /* fill in the values */
+ hi->key = key;
+ hi->value = value;
+
+ /* hash to the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list to make sure we do not have a duplicate */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_lwpid *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ /* found one */
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ li = NULL;
+
+ /* is there already one there? */
+ if (li == NULL)
+ {
+ /* add the unique element to the buckets list */
+ ll_add(&(bucket->list), newli);
+ return NULL;
+ }
+ else
+ {
+ /* free the stuff we just allocated */
+ ll_freeitem(newli);
+ return ((hash_item_lwpid *)(li->datum))->value;
+ }
+}
+
+/*
+ * void *hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value)
+ *
+ * Replace an existing value in the hash table with a new one and
+ * return the old value. If the key does not already exist in
+ * the hash table, add a new element and return NULL.
+ * Key type is lwpid_t
+ */
+
+void *
+hash_replace_lwpid(hash_table *ht, lwpid_t key, void *value)
+
+{
+ bucket_t *bucket;
+ hash_item_lwpid *hi;
+ llist *ll;
+ llistitem *li;
+ void *result = NULL;
+ lwpid_t k1;
+
+ /* find the bucket */
+ bucket = &(ht->buckets[(key % ht->num_buckets)]);
+
+ /* walk the list until we find the existing item */
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ hi = (hash_item_lwpid *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ /* found it: now replace the value with the new one */
+ result = hi->value;
+ hi->value = value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+
+ /* if the element wasnt found, add it */
+ if (result == NULL)
+ {
+ li = ll_newitem(sizeof(hash_item_lwpid));
+ hi = (hash_item_lwpid *)li->datum;
+ hi->key = key;
+ hi->value = value;
+ ll_add(&(bucket->list), li);
+ }
+
+ /* return the old value (so it can be freed) */
+ return result;
+}
+
+/*
+ * void *hash_lookup_lwpid(hash_table *ht, lwpid_t key)
+ *
+ * Look up "key" in "ht" and return the associated value. If "key"
+ * is not found, return NULL. Key type is lwpid_t
+ */
+
+void *
+hash_lookup_lwpid(hash_table *ht, lwpid_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ hash_item_lwpid *h;
+ void *result;
+ lwpid_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ while (li != NULL)
+ {
+ h = (hash_item_lwpid *)li->datum;
+ k1 = h->key;
+ if (key == k1)
+ {
+ result = h->value;
+ break;
+ }
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * void *hash_remove_lwpid(hash_table *ht, lwpid_t key)
+ *
+ * Remove the element associated with "key" from the hash table
+ * "ht". Return the value or NULL if the key was not found.
+ */
+
+void *
+hash_remove_lwpid(hash_table *ht, lwpid_t key)
+
+{
+ bucket_t *bucket;
+ llist *ll;
+ llistitem *li;
+ llistitem *lilast;
+ hash_item_lwpid *hi;
+ void *result;
+ lwpid_t k1;
+
+ result = NULL;
+ if ((bucket = &(ht->buckets[(key % ht->num_buckets)])) != NULL)
+ {
+ ll = &(bucket->list);
+ li = LL_FIRST(ll);
+ lilast = NULL;
+ while (li != NULL)
+ {
+ hi = (hash_item_lwpid *)li->datum;
+ k1 = hi->key;
+ if (key == k1)
+ {
+ ll_extract(ll, li, lilast);
+ result = hi->value;
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+ break;
+ }
+ lilast = li;
+ li = LL_NEXT(ll, li);
+ }
+ }
+ return result;
+}
+
+/*
+ * hash_item_lwpid *hash_first_lwpid(hash_table *ht, hash_pos *pos)
+ *
+ * First function to call when iterating through all items in the hash
+ * table. Returns the first item in "ht" and initializes "*pos" to track
+ * the current position.
+ */
+
+hash_item_lwpid *
+hash_first_lwpid(hash_table *ht, hash_pos *pos)
+
+{
+ /* initialize pos for first item in first bucket */
+ pos->num_buckets = ht->num_buckets;
+ pos->hash_bucket = ht->buckets;
+ pos->curr = 0;
+ pos->ll_last = NULL;
+
+ /* find the first non-empty bucket */
+ while(pos->hash_bucket->list.count == 0)
+ {
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ return NULL;
+ }
+ }
+
+ /* set and return the first item */
+ pos->ll_item = LL_FIRST(&(pos->hash_bucket->list));
+ return (hash_item_lwpid *)pos->ll_item->datum;
+}
+
+
+/*
+ * hash_item_lwpid *hash_next_lwpid(hash_pos *pos)
+ *
+ * Return the next item in the hash table, using "pos" as a description
+ * of the present position in the hash table. "pos" also identifies the
+ * specific hash table. Return NULL if there are no more elements.
+ */
+
+hash_item_lwpid *
+hash_next_lwpid(hash_pos *pos)
+
+{
+ llistitem *li;
+
+ /* move item to last and check for NULL */
+ if ((pos->ll_last = pos->ll_item) == NULL)
+ {
+ /* are we really at the end of the hash table? */
+ if (pos->curr >= pos->num_buckets)
+ {
+ /* yes: return NULL */
+ return NULL;
+ }
+ /* no: regrab first item in current bucket list (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+ else
+ {
+ /* get the next item in the llist */
+ li = LL_NEXT(&(pos->hash_bucket->list), pos->ll_item);
+ }
+
+ /* if its NULL we have to find another bucket */
+ while (li == NULL)
+ {
+ /* locate another bucket */
+ pos->ll_last = NULL;
+
+ /* move to the next one */
+ pos->hash_bucket++;
+ if (++pos->curr >= pos->num_buckets)
+ {
+ /* at the end of the hash table */
+ pos->ll_item = NULL;
+ return NULL;
+ }
+
+ /* get the first element (might be NULL) */
+ li = LL_FIRST(&(pos->hash_bucket->list));
+ }
+
+ /* li is the next element to dish out */
+ pos->ll_item = li;
+ return (hash_item_lwpid *)li->datum;
+}
+
+/*
+ * void *hash_remove_pos_lwpid(hash_pos *pos)
+ *
+ * Remove the hash table entry pointed to by position marker "pos".
+ * The data from the entry is returned upon success, otherwise NULL.
+ */
+
+
+void *
+hash_remove_pos_lwpid(hash_pos *pos)
+
+{
+ llistitem *li;
+ void *ans;
+ hash_item_lwpid *hi;
+ lwpid_t key;
+
+ /* sanity checks */
+ if (pos == NULL || pos->ll_last == pos->ll_item)
+ {
+ return NULL;
+ }
+
+ /* at this point pos contains the item to remove (ll_item)
+ and its predecesor (ll_last) */
+ /* extract the item from the llist */
+ li = pos->ll_item;
+ ll_extract(&(pos->hash_bucket->list), li, pos->ll_last);
+
+ /* retain the data */
+ hi = (hash_item_lwpid *)li->datum;
+ ans = hi->value;
+
+ /* free up the space */
+ key = hi->key;
+ ;
+ ll_freeitem(li);
+
+ /* back up to previous item */
+ /* its okay for ll_item to be null: hash_next will detect it */
+ pos->ll_item = pos->ll_last;
+
+ return ans;
+}
+
+#endif