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