From b16ac5b53f6b943b7017f01d411721173b4f1b96 Mon Sep 17 00:00:00 2001 From: Edwin Groothuis Date: Thu, 21 May 2009 07:54:21 +0000 Subject: Vendor import of top-3.8b1 Obtained from: http://www.unixtop.org --- hash.c | 2001 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 2001 insertions(+) create mode 100644 hash.c (limited to 'hash.c') 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 +#include +#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 +#else +#ifdef HAVE_STRING_H +#include +#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 +#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; jnum_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 -- cgit v1.2.3