external/bsd/bind/dist/contrib/idn/idnkit-1.0-src/lib/strhash.c

   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 }