| /* @configure_input@ */ |
| |
| /* |
| ** Copyright 1998-2002 University of Illinois Board of Trustees |
| ** Copyright 1998-2002 Mark D. Roth |
| ** All rights reserved. |
| ** |
| ** @LISTHASH_PREFIX@_hash.c - hash table routines |
| ** |
| ** Mark D. Roth <roth@uiuc.edu> |
| ** Campus Information Technologies and Educational Services |
| ** University of Illinois at Urbana-Champaign |
| */ |
| |
| #include <@LISTHASH_PREFIX@/config.h> |
| #include <@LISTHASH_PREFIX@/compat.h> |
| |
| #include <@LISTHASH_PREFIX@/@LISTHASH_PREFIX@_listhash.h> |
| |
| #include <stdio.h> |
| #include <errno.h> |
| |
| #ifdef STDC_HEADERS |
| # include <stdlib.h> |
| #endif |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hashptr_reset() - reset a hash pointer |
| */ |
| void |
| @LISTHASH_PREFIX@_hashptr_reset(@LISTHASH_PREFIX@_hashptr_t *hp) |
| { |
| @LISTHASH_PREFIX@_listptr_reset(&(hp->node)); |
| hp->bucket = -1; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hashptr_data() - retrieve the data being pointed to |
| */ |
| void * |
| @LISTHASH_PREFIX@_hashptr_data(@LISTHASH_PREFIX@_hashptr_t *hp) |
| { |
| return @LISTHASH_PREFIX@_listptr_data(&(hp->node)); |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_str_hashfunc() - default hash function, optimized for |
| ** 7-bit strings |
| */ |
| unsigned int |
| @LISTHASH_PREFIX@_str_hashfunc(char *key, unsigned int num_buckets) |
| { |
| #if 0 |
| register unsigned result = 0; |
| register int i; |
| |
| if (key == NULL) |
| return 0; |
| |
| for (i = 0; *key != '\0' && i < 32; i++) |
| result = result * 33U + *key++; |
| |
| return (result % num_buckets); |
| #else |
| if (key == NULL) |
| return 0; |
| |
| return (key[0] % num_buckets); |
| #endif |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_nents() - return number of elements from hash |
| */ |
| unsigned int |
| @LISTHASH_PREFIX@_hash_nents(@LISTHASH_PREFIX@_hash_t *h) |
| { |
| return h->nents; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_new() - create a new hash |
| */ |
| @LISTHASH_PREFIX@_hash_t * |
| @LISTHASH_PREFIX@_hash_new(int num, @LISTHASH_PREFIX@_hashfunc_t hashfunc) |
| { |
| @LISTHASH_PREFIX@_hash_t *hash; |
| |
| hash = (@LISTHASH_PREFIX@_hash_t *)calloc(1, sizeof(@LISTHASH_PREFIX@_hash_t)); |
| if (hash == NULL) |
| return NULL; |
| hash->numbuckets = num; |
| if (hashfunc != NULL) |
| hash->hashfunc = hashfunc; |
| else |
| hash->hashfunc = (@LISTHASH_PREFIX@_hashfunc_t)@LISTHASH_PREFIX@_str_hashfunc; |
| |
| hash->table = (@LISTHASH_PREFIX@_list_t **)calloc(num, sizeof(@LISTHASH_PREFIX@_list_t *)); |
| if (hash->table == NULL) |
| { |
| free(hash); |
| return NULL; |
| } |
| |
| return hash; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_next() - get next element in hash |
| ** returns: |
| ** 1 data found |
| ** 0 end of list |
| */ |
| int |
| @LISTHASH_PREFIX@_hash_next(@LISTHASH_PREFIX@_hash_t *h, |
| @LISTHASH_PREFIX@_hashptr_t *hp) |
| { |
| #ifdef DS_DEBUG |
| printf("==> @LISTHASH_PREFIX@_hash_next(h=0x%lx, hp={%d,0x%lx})\n", |
| h, hp->bucket, hp->node); |
| #endif |
| |
| if (hp->bucket >= 0 && hp->node != NULL && |
| @LISTHASH_PREFIX@_list_next(h->table[hp->bucket], &(hp->node)) != 0) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_next(): found additional " |
| "data in current bucket (%d), returing 1\n", |
| hp->bucket); |
| #endif |
| return 1; |
| } |
| |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_next(): done with bucket %d\n", |
| hp->bucket); |
| #endif |
| |
| for (hp->bucket++; hp->bucket < h->numbuckets; hp->bucket++) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_next(): " |
| "checking bucket %d\n", hp->bucket); |
| #endif |
| hp->node = NULL; |
| if (h->table[hp->bucket] != NULL && |
| @LISTHASH_PREFIX@_list_next(h->table[hp->bucket], |
| &(hp->node)) != 0) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_next(): " |
| "found data in bucket %d, returing 1\n", |
| hp->bucket); |
| #endif |
| return 1; |
| } |
| } |
| |
| if (hp->bucket == h->numbuckets) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_next(): hash pointer " |
| "wrapped to 0\n"); |
| #endif |
| hp->bucket = -1; |
| hp->node = NULL; |
| } |
| |
| #ifdef DS_DEBUG |
| printf("<== @LISTHASH_PREFIX@_hash_next(): no more data, " |
| "returning 0\n"); |
| #endif |
| return 0; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_del() - delete an entry from the hash |
| ** returns: |
| ** 0 success |
| ** -1 (and sets errno) failure |
| */ |
| int |
| @LISTHASH_PREFIX@_hash_del(@LISTHASH_PREFIX@_hash_t *h, |
| @LISTHASH_PREFIX@_hashptr_t *hp) |
| { |
| if (hp->bucket < 0 |
| || hp->bucket >= h->numbuckets |
| || h->table[hp->bucket] == NULL |
| || hp->node == NULL) |
| { |
| errno = EINVAL; |
| return -1; |
| } |
| |
| @LISTHASH_PREFIX@_list_del(h->table[hp->bucket], &(hp->node)); |
| h->nents--; |
| return 0; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_empty() - empty the hash |
| */ |
| void |
| @LISTHASH_PREFIX@_hash_empty(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc) |
| { |
| int i; |
| |
| for (i = 0; i < h->numbuckets; i++) |
| if (h->table[i] != NULL) |
| @LISTHASH_PREFIX@_list_empty(h->table[i], freefunc); |
| |
| h->nents = 0; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_free() - delete all of the nodes in the hash |
| */ |
| void |
| @LISTHASH_PREFIX@_hash_free(@LISTHASH_PREFIX@_hash_t *h, @LISTHASH_PREFIX@_freefunc_t freefunc) |
| { |
| int i; |
| |
| for (i = 0; i < h->numbuckets; i++) |
| if (h->table[i] != NULL) |
| @LISTHASH_PREFIX@_list_free(h->table[i], freefunc); |
| |
| free(h->table); |
| free(h); |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_search() - iterative search for an element in a hash |
| ** returns: |
| ** 1 match found |
| ** 0 no match |
| */ |
| int |
| @LISTHASH_PREFIX@_hash_search(@LISTHASH_PREFIX@_hash_t *h, |
| @LISTHASH_PREFIX@_hashptr_t *hp, void *data, |
| @LISTHASH_PREFIX@_matchfunc_t matchfunc) |
| { |
| while (@LISTHASH_PREFIX@_hash_next(h, hp) != 0) |
| if ((*matchfunc)(data, @LISTHASH_PREFIX@_listptr_data(&(hp->node))) != 0) |
| return 1; |
| |
| return 0; |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_getkey() - hash-based search for an element in a hash |
| ** returns: |
| ** 1 match found |
| ** 0 no match |
| */ |
| int |
| @LISTHASH_PREFIX@_hash_getkey(@LISTHASH_PREFIX@_hash_t *h, |
| @LISTHASH_PREFIX@_hashptr_t *hp, void *key, |
| @LISTHASH_PREFIX@_matchfunc_t matchfunc) |
| { |
| #ifdef DS_DEBUG |
| printf("==> @LISTHASH_PREFIX@_hash_getkey(h=0x%lx, hp={%d,0x%lx}, " |
| "key=0x%lx, matchfunc=0x%lx)\n", |
| h, hp->bucket, hp->node, key, matchfunc); |
| #endif |
| |
| if (hp->bucket == -1) |
| { |
| hp->bucket = (*(h->hashfunc))(key, h->numbuckets); |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_getkey(): hp->bucket " |
| "set to %d\n", hp->bucket); |
| #endif |
| } |
| |
| if (h->table[hp->bucket] == NULL) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_getkey(): no list " |
| "for bucket %d, returning 0\n", hp->bucket); |
| #endif |
| hp->bucket = -1; |
| return 0; |
| } |
| |
| #ifdef DS_DEBUG |
| printf("<== @LISTHASH_PREFIX@_hash_getkey(): " |
| "returning @LISTHASH_PREFIX@_list_search()\n"); |
| #endif |
| return @LISTHASH_PREFIX@_list_search(h->table[hp->bucket], &(hp->node), |
| key, matchfunc); |
| } |
| |
| |
| /* |
| ** @LISTHASH_PREFIX@_hash_add() - add an element to the hash |
| ** returns: |
| ** 0 success |
| ** -1 (and sets errno) failure |
| */ |
| int |
| @LISTHASH_PREFIX@_hash_add(@LISTHASH_PREFIX@_hash_t *h, void *data) |
| { |
| int bucket, i; |
| |
| #ifdef DS_DEBUG |
| printf("==> @LISTHASH_PREFIX@_hash_add(h=0x%lx, data=0x%lx)\n", |
| h, data); |
| #endif |
| |
| bucket = (*(h->hashfunc))(data, h->numbuckets); |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_add(): inserting in bucket %d\n", |
| bucket); |
| #endif |
| if (h->table[bucket] == NULL) |
| { |
| #ifdef DS_DEBUG |
| printf(" @LISTHASH_PREFIX@_hash_add(): creating new list\n"); |
| #endif |
| h->table[bucket] = @LISTHASH_PREFIX@_list_new(LIST_QUEUE, NULL); |
| } |
| |
| #ifdef DS_DEBUG |
| printf("<== @LISTHASH_PREFIX@_hash_add(): " |
| "returning @LISTHASH_PREFIX@_list_add()\n"); |
| #endif |
| i = @LISTHASH_PREFIX@_list_add(h->table[bucket], data); |
| if (i == 0) |
| h->nents++; |
| return i; |
| } |
| |
| |