#ifndef lint static char *rcsid = "$Id: strhash.c,v 1.1.1.1 2003-06-04 00:26:13 marka Exp $"; #endif /* * Copyright (c) 2000 Japan Network Information Center. All rights reserved. * * By using this file, you agree to the terms and conditions set forth bellow. * * LICENSE TERMS AND CONDITIONS * * The following License Terms and Conditions apply, unless a different * license is obtained from Japan Network Information Center ("JPNIC"), * a Japanese association, Kokusai-Kougyou-Kanda Bldg 6F, 2-3-4 Uchi-Kanda, * Chiyoda-ku, Tokyo 101-0047, Japan. * * 1. Use, Modification and Redistribution (including distribution of any * modified or derived work) in source and/or binary forms is permitted * under this License Terms and Conditions. * * 2. Redistribution of source code must retain the copyright notices as they * appear in each source code file, this License Terms and Conditions. * * 3. Redistribution in binary form must reproduce the Copyright Notice, * this License Terms and Conditions, in the documentation and/or other * materials provided with the distribution. For the purposes of binary * distribution the "Copyright Notice" refers to the following language: * "Copyright (c) 2000-2002 Japan Network Information Center. All rights reserved." * * 4. The name of JPNIC may not be used to endorse or promote products * derived from this Software without specific prior written approval of * JPNIC. * * 5. Disclaimer/Limitation of Liability: THIS SOFTWARE IS PROVIDED BY JPNIC * "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 JPNIC 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 DAMAGES. */ #include #include #include #include #include #include #include #include /* * Initially, the number of hash buckets is INITIAL_HASH_SIZE. * As the more elements are put in the hash, the number of elements * per bucket will exceed THRESHOLD eventually. When it happens, * the number of buckets will be multiplied by FACTOR. */ #define INITIAL_HASH_SIZE 67 #define FACTOR 7 #define THRESHOLD 5 #define HASH_MULT 31 typedef struct strhash_entry { struct strhash_entry *next; unsigned long hash_value; char *key; void *value; } strhash_entry_t; struct idn__strhash { int nbins; int nelements; strhash_entry_t **bins; }; static unsigned long hash_value(const char *key); static strhash_entry_t *find_entry(strhash_entry_t *entry, const char *key, unsigned long hash); static strhash_entry_t *new_entry(const char *key, void *value); static idn_result_t expand_bins(idn__strhash_t hash, int new_size); idn_result_t idn__strhash_create(idn__strhash_t *hashp) { idn__strhash_t hash; idn_result_t r; TRACE(("idn__strhash_create()\n")); assert(hashp != NULL); *hashp = NULL; if ((hash = malloc(sizeof(struct idn__strhash))) == NULL) { WARNING(("idn__strhash_create: malloc failed (hash)\n")); return (idn_nomemory); } hash->nbins = 0; hash->nelements = 0; hash->bins = NULL; if ((r = expand_bins(hash, INITIAL_HASH_SIZE)) != idn_success) { WARNING(("idn__strhash_create: malloc failed (bins)\n")); free(hash); return (r); } *hashp = hash; return (idn_success); } void idn__strhash_destroy(idn__strhash_t hash, idn__strhash_freeproc_t proc) { int i; assert(hash != NULL && hash->bins != NULL); for (i = 0; i < hash->nbins; i++) { strhash_entry_t *bin = hash->bins[i]; strhash_entry_t *next; while (bin != NULL) { next = bin->next; if (proc != NULL) (*proc)(bin->value); free(bin); bin = next; } } free(hash->bins); free(hash); } idn_result_t idn__strhash_put(idn__strhash_t hash, const char *key, void *value) { unsigned long h, h_index; strhash_entry_t *entry; assert(hash != NULL && key != NULL); h = hash_value(key); h_index = h % hash->nbins; if ((entry = find_entry(hash->bins[h_index], key, h)) != NULL) { /* Entry exists. Replace the value. */ entry->value = value; } else { /* Create new entry. */ if ((entry = new_entry(key, value)) == NULL) { return (idn_nomemory); } /* Insert it to the list. */ entry->next = hash->bins[h_index]; hash->bins[h_index] = entry; hash->nelements++; if (hash->nelements > hash->nbins * THRESHOLD) { idn_result_t r; r = expand_bins(hash, hash->nbins * FACTOR); if (r != idn_success) { TRACE(("idn__strhash_put: hash table " "expansion failed\n")); } } } return (idn_success); } idn_result_t idn__strhash_get(idn__strhash_t hash, const char *key, void **valuep) { unsigned long h; strhash_entry_t *entry; assert(hash != NULL && key != NULL && valuep != NULL); h = hash_value(key); entry = find_entry(hash->bins[h % hash->nbins], key, h); if (entry == NULL) return (idn_noentry); *valuep = entry->value; return (idn_success); } int idn__strhash_exists(idn__strhash_t hash, const char *key) { unsigned long h; assert(hash != NULL && key != NULL); h = hash_value(key); return (find_entry(hash->bins[h % hash->nbins], key, h) != NULL); } static unsigned long hash_value(const char *key) { unsigned long h = 0; unsigned char *p = (unsigned char *)key; int c; while ((c = *p++) != '\0') { h = h * HASH_MULT + c; } return (h); } static strhash_entry_t * find_entry(strhash_entry_t *entry, const char *key, unsigned long hash) { assert(key != NULL); while (entry != NULL) { if (entry->hash_value == hash && strcmp(key, entry->key) == 0) return (entry); entry = entry->next; } return (NULL); } static strhash_entry_t * new_entry(const char *key, void *value) { strhash_entry_t *entry; int len; assert(key != NULL); len = strlen(key) + 1; if ((entry = malloc(sizeof(strhash_entry_t) + len)) == NULL) { return (NULL); } entry->next = NULL; entry->hash_value = hash_value(key); entry->key = (char *)(entry + 1); (void)strcpy(entry->key, key); entry->value = value; return (entry); } static idn_result_t expand_bins(idn__strhash_t hash, int new_size) { strhash_entry_t **old_bins, **new_bins; int old_size; int old_index, new_index; new_bins = malloc(sizeof(strhash_entry_t *) * new_size); if (new_bins == NULL) return (idn_nomemory); memset(new_bins, 0, sizeof(strhash_entry_t *) * new_size); old_bins = hash->bins; old_size = hash->nbins; for (old_index = 0; old_index < old_size; old_index++) { strhash_entry_t *entries = old_bins[old_index]; while (entries != NULL) { strhash_entry_t *e = entries; /* Remove the top element from the linked list. */ entries = entries->next; /* ..and move to the new hash. */ new_index = e->hash_value % new_size; e->next = new_bins[new_index]; new_bins[new_index] = e; } } hash->nbins = new_size; hash->bins = new_bins; if (old_bins != NULL) free(old_bins); return (idn_success); }