5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#ifndef lint
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic char *rcsid = "$Id: strhash.c,v 1.1 2003/06/04 00:26:13 marka Exp $";
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#endif
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews/*
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * Copyright (c) 2000 Japan Network Information Center. All rights reserved.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * By using this file, you agree to the terms and conditions set forth bellow.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * LICENSE TERMS AND CONDITIONS
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * The following License Terms and Conditions apply, unless a different
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * license is obtained from Japan Network Information Center ("JPNIC"),
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * a Japanese association, Kokusai-Kougyou-Kanda Bldg 6F, 2-3-4 Uchi-Kanda,
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * Chiyoda-ku, Tokyo 101-0047, Japan.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * 1. Use, Modification and Redistribution (including distribution of any
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * modified or derived work) in source and/or binary forms is permitted
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * under this License Terms and Conditions.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * 2. Redistribution of source code must retain the copyright notices as they
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * appear in each source code file, this License Terms and Conditions.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * 3. Redistribution in binary form must reproduce the Copyright Notice,
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * this License Terms and Conditions, in the documentation and/or other
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * materials provided with the distribution. For the purposes of binary
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * distribution the "Copyright Notice" refers to the following language:
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * "Copyright (c) 2000-2002 Japan Network Information Center. All rights reserved."
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * 4. The name of JPNIC may not be used to endorse or promote products
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * derived from this Software without specific prior written approval of
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * JPNIC.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * 5. Disclaimer/Limitation of Liability: THIS SOFTWARE IS PROVIDED BY JPNIC
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JPNIC BE LIABLE
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <config.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <stddef.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <stdlib.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <string.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <idn/assert.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <idn/logmacro.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <idn/result.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#include <idn/strhash.h>
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews/*
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * Initially, the number of hash buckets is INITIAL_HASH_SIZE.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * As the more elements are put in the hash, the number of elements
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * per bucket will exceed THRESHOLD eventually. When it happens,
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews * the number of buckets will be multiplied by FACTOR.
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#define INITIAL_HASH_SIZE 67
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#define FACTOR 7
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#define THRESHOLD 5
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews#define HASH_MULT 31
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewstypedef struct strhash_entry {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews struct strhash_entry *next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long hash_value;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews char *key;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews void *value;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews} strhash_entry_t;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstruct idn__strhash {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int nbins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int nelements;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t **bins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews};
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic unsigned long hash_value(const char *key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic strhash_entry_t *find_entry(strhash_entry_t *entry, const char *key,
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long hash);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic strhash_entry_t *new_entry(const char *key, void *value);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic idn_result_t expand_bins(idn__strhash_t hash, int new_size);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn_result_t
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn__strhash_create(idn__strhash_t *hashp) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews idn__strhash_t hash;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews idn_result_t r;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews TRACE(("idn__strhash_create()\n"));
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(hashp != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *hashp = NULL;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if ((hash = malloc(sizeof(struct idn__strhash))) == NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews WARNING(("idn__strhash_create: malloc failed (hash)\n"));
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_nomemory);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->nbins = 0;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->nelements = 0;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->bins = NULL;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if ((r = expand_bins(hash, INITIAL_HASH_SIZE)) != idn_success) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews WARNING(("idn__strhash_create: malloc failed (bins)\n"));
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews free(hash);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (r);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *hashp = hash;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_success);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsvoid
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn__strhash_destroy(idn__strhash_t hash, idn__strhash_freeproc_t proc) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int i;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(hash != NULL && hash->bins != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews for (i = 0; i < hash->nbins; i++) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *bin = hash->bins[i];
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews while (bin != NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews next = bin->next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (proc != NULL)
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews (*proc)(bin->value);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews free(bin);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews bin = next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews free(hash->bins);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews free(hash);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn_result_t
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn__strhash_put(idn__strhash_t hash, const char *key, void *value) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long h, h_index;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *entry;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(hash != NULL && key != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews h = hash_value(key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews h_index = h % hash->nbins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if ((entry = find_entry(hash->bins[h_index], key, h)) != NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews /* Entry exists. Replace the value. */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->value = value;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews } else {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews /* Create new entry. */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if ((entry = new_entry(key, value)) == NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_nomemory);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews /* Insert it to the list. */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->next = hash->bins[h_index];
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->bins[h_index] = entry;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->nelements++;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (hash->nelements > hash->nbins * THRESHOLD) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews idn_result_t r;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews r = expand_bins(hash, hash->nbins * FACTOR);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (r != idn_success) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews TRACE(("idn__strhash_put: hash table "
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews "expansion failed\n"));
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_success);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn_result_t
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn__strhash_get(idn__strhash_t hash, const char *key, void **valuep) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long h;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *entry;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(hash != NULL && key != NULL && valuep != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews h = hash_value(key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry = find_entry(hash->bins[h % hash->nbins], key, h);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (entry == NULL)
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_noentry);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews *valuep = entry->value;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_success);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsint
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsidn__strhash_exists(idn__strhash_t hash, const char *key) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long h;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(hash != NULL && key != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews h = hash_value(key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (find_entry(hash->bins[h % hash->nbins], key, h) != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic unsigned long
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewshash_value(const char *key) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned long h = 0;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews unsigned char *p = (unsigned char *)key;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int c;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews while ((c = *p++) != '\0') {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews h = h * HASH_MULT + c;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (h);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic strhash_entry_t *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsfind_entry(strhash_entry_t *entry, const char *key, unsigned long hash) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(key != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews while (entry != NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (entry->hash_value == hash && strcmp(key, entry->key) == 0)
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (entry);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry = entry->next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic strhash_entry_t *
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsnew_entry(const char *key, void *value) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *entry;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int len;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews assert(key != NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews len = strlen(key) + 1;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if ((entry = malloc(sizeof(strhash_entry_t) + len)) == NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (NULL);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->next = NULL;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->hash_value = hash_value(key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->key = (char *)(entry + 1);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews (void)strcpy(entry->key, key);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entry->value = value;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (entry);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsstatic idn_result_t
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrewsexpand_bins(idn__strhash_t hash, int new_size) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t **old_bins, **new_bins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int old_size;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews int old_index, new_index;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews new_bins = malloc(sizeof(strhash_entry_t *) * new_size);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (new_bins == NULL)
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_nomemory);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews memset(new_bins, 0, sizeof(strhash_entry_t *) * new_size);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews old_bins = hash->bins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews old_size = hash->nbins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews for (old_index = 0; old_index < old_size; old_index++) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *entries = old_bins[old_index];
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews while (entries != NULL) {
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews strhash_entry_t *e = entries;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews /* Remove the top element from the linked list. */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews entries = entries->next;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews /* ..and move to the new hash. */
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews new_index = e->hash_value % new_size;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews e->next = new_bins[new_index];
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews new_bins[new_index] = e;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews }
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->nbins = new_size;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews hash->bins = new_bins;
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews if (old_bins != NULL)
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews free(old_bins);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews return (idn_success);
5c526acb82c882e41b655c31f5fa4425c87b671cMark Andrews}