1#ifndef lint 2static char *rcsid = "$Id: strhash.c,v 1.1 2003/06/04 00:26:13 marka Exp $"; 3#endif 4 5/* 6 * Copyright (c) 2000 Japan Network Information Center. All rights reserved. 7 * 8 * By using this file, you agree to the terms and conditions set forth bellow. 9 * 10 * LICENSE TERMS AND CONDITIONS 11 * 12 * The following License Terms and Conditions apply, unless a different 13 * license is obtained from Japan Network Information Center ("JPNIC"), 14 * a Japanese association, Kokusai-Kougyou-Kanda Bldg 6F, 2-3-4 Uchi-Kanda, 15 * Chiyoda-ku, Tokyo 101-0047, Japan. 16 * 17 * 1. Use, Modification and Redistribution (including distribution of any 18 * modified or derived work) in source and/or binary forms is permitted 19 * under this License Terms and Conditions. 20 * 21 * 2. Redistribution of source code must retain the copyright notices as they 22 * appear in each source code file, this License Terms and Conditions. 23 * 24 * 3. Redistribution in binary form must reproduce the Copyright Notice, 25 * this License Terms and Conditions, in the documentation and/or other 26 * materials provided with the distribution. For the purposes of binary 27 * distribution the "Copyright Notice" refers to the following language: 28 * "Copyright (c) 2000-2002 Japan Network Information Center. All rights reserved." 29 * 30 * 4. The name of JPNIC may not be used to endorse or promote products 31 * derived from this Software without specific prior written approval of 32 * JPNIC. 33 * 34 * 5. Disclaimer/Limitation of Liability: THIS SOFTWARE IS PROVIDED BY JPNIC 35 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 36 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 37 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JPNIC BE LIABLE 38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 39 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 40 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 41 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 42 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 43 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 44 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. 45 */ 46 47#include <config.h> 48 49#include <stddef.h> 50#include <stdlib.h> 51#include <string.h> 52 53#include <idn/assert.h> 54#include <idn/logmacro.h> 55#include <idn/result.h> 56#include <idn/strhash.h> 57 58/* 59 * Initially, the number of hash buckets is INITIAL_HASH_SIZE. 60 * As the more elements are put in the hash, the number of elements 61 * per bucket will exceed THRESHOLD eventually. When it happens, 62 * the number of buckets will be multiplied by FACTOR. 63 */ 64#define INITIAL_HASH_SIZE 67 65#define FACTOR 7 66#define THRESHOLD 5 67 68#define HASH_MULT 31 69 70typedef struct strhash_entry { 71 struct strhash_entry *next; 72 unsigned long hash_value; 73 char *key; 74 void *value; 75} strhash_entry_t; 76 77struct idn__strhash { 78 int nbins; 79 int nelements; 80 strhash_entry_t **bins; 81}; 82 83static unsigned long hash_value(const char *key); 84static strhash_entry_t *find_entry(strhash_entry_t *entry, const char *key, 85 unsigned long hash); 86static strhash_entry_t *new_entry(const char *key, void *value); 87static idn_result_t expand_bins(idn__strhash_t hash, int new_size); 88 89idn_result_t 90idn__strhash_create(idn__strhash_t *hashp) { 91 idn__strhash_t hash; 92 idn_result_t r; 93 94 TRACE(("idn__strhash_create()\n")); 95 96 assert(hashp != NULL); 97 98 *hashp = NULL; 99 100 if ((hash = malloc(sizeof(struct idn__strhash))) == NULL) { 101 WARNING(("idn__strhash_create: malloc failed (hash)\n")); 102 return (idn_nomemory); 103 } 104 hash->nbins = 0; 105 hash->nelements = 0; 106 hash->bins = NULL; 107 if ((r = expand_bins(hash, INITIAL_HASH_SIZE)) != idn_success) { 108 WARNING(("idn__strhash_create: malloc failed (bins)\n")); 109 free(hash); 110 return (r); 111 } 112 113 *hashp = hash; 114 115 return (idn_success); 116} 117 118void 119idn__strhash_destroy(idn__strhash_t hash, idn__strhash_freeproc_t proc) { 120 int i; 121 122 assert(hash != NULL && hash->bins != NULL); 123 124 for (i = 0; i < hash->nbins; i++) { 125 strhash_entry_t *bin = hash->bins[i]; 126 strhash_entry_t *next; 127 128 while (bin != NULL) { 129 next = bin->next; 130 if (proc != NULL) 131 (*proc)(bin->value); 132 free(bin); 133 bin = next; 134 } 135 } 136 free(hash->bins); 137 free(hash); 138} 139 140idn_result_t 141idn__strhash_put(idn__strhash_t hash, const char *key, void *value) { 142 unsigned long h, h_index; 143 strhash_entry_t *entry; 144 145 assert(hash != NULL && key != NULL); 146 147 h = hash_value(key); 148 h_index = h % hash->nbins; 149 150 if ((entry = find_entry(hash->bins[h_index], key, h)) != NULL) { 151 /* Entry exists. Replace the value. */ 152 entry->value = value; 153 } else { 154 /* Create new entry. */ 155 if ((entry = new_entry(key, value)) == NULL) { 156 return (idn_nomemory); 157 } 158 /* Insert it to the list. */ 159 entry->next = hash->bins[h_index]; 160 hash->bins[h_index] = entry; 161 hash->nelements++; 162 163 if (hash->nelements > hash->nbins * THRESHOLD) { 164 idn_result_t r; 165 r = expand_bins(hash, hash->nbins * FACTOR); 166 if (r != idn_success) { 167 TRACE(("idn__strhash_put: hash table " 168 "expansion failed\n")); 169 } 170 } 171 } 172 173 return (idn_success); 174} 175 176idn_result_t 177idn__strhash_get(idn__strhash_t hash, const char *key, void **valuep) { 178 unsigned long h; 179 strhash_entry_t *entry; 180 181 assert(hash != NULL && key != NULL && valuep != NULL); 182 183 h = hash_value(key); 184 entry = find_entry(hash->bins[h % hash->nbins], key, h); 185 if (entry == NULL) 186 return (idn_noentry); 187 188 *valuep = entry->value; 189 return (idn_success); 190} 191 192int 193idn__strhash_exists(idn__strhash_t hash, const char *key) { 194 unsigned long h; 195 196 assert(hash != NULL && key != NULL); 197 198 h = hash_value(key); 199 return (find_entry(hash->bins[h % hash->nbins], key, h) != NULL); 200} 201 202static unsigned long 203hash_value(const char *key) { 204 unsigned long h = 0; 205 unsigned char *p = (unsigned char *)key; 206 int c; 207 208 while ((c = *p++) != '\0') { 209 h = h * HASH_MULT + c; 210 } 211 return (h); 212} 213 214static strhash_entry_t * 215find_entry(strhash_entry_t *entry, const char *key, unsigned long hash) { 216 assert(key != NULL); 217 218 while (entry != NULL) { 219 if (entry->hash_value == hash && strcmp(key, entry->key) == 0) 220 return (entry); 221 entry = entry->next; 222 } 223 return (NULL); 224} 225 226static strhash_entry_t * 227new_entry(const char *key, void *value) { 228 strhash_entry_t *entry; 229 int len; 230 231 assert(key != NULL); 232 233 len = strlen(key) + 1; 234 if ((entry = malloc(sizeof(strhash_entry_t) + len)) == NULL) { 235 return (NULL); 236 } 237 entry->next = NULL; 238 entry->hash_value = hash_value(key); 239 entry->key = (char *)(entry + 1); 240 (void)strcpy(entry->key, key); 241 entry->value = value; 242 243 return (entry); 244} 245 246static idn_result_t 247expand_bins(idn__strhash_t hash, int new_size) { 248 strhash_entry_t **old_bins, **new_bins; 249 int old_size; 250 int old_index, new_index; 251 252 new_bins = malloc(sizeof(strhash_entry_t *) * new_size); 253 if (new_bins == NULL) 254 return (idn_nomemory); 255 256 memset(new_bins, 0, sizeof(strhash_entry_t *) * new_size); 257 258 old_bins = hash->bins; 259 old_size = hash->nbins; 260 for (old_index = 0; old_index < old_size; old_index++) { 261 strhash_entry_t *entries = old_bins[old_index]; 262 263 while (entries != NULL) { 264 strhash_entry_t *e = entries; 265 266 /* Remove the top element from the linked list. */ 267 entries = entries->next; 268 269 /* ..and move to the new hash. */ 270 new_index = e->hash_value % new_size; 271 e->next = new_bins[new_index]; 272 new_bins[new_index] = e; 273 } 274 } 275 276 hash->nbins = new_size; 277 hash->bins = new_bins; 278 279 if (old_bins != NULL) 280 free(old_bins); 281 282 return (idn_success); 283} 284