ia64/xen-unstable

changeset 9126:26af50da86b7

Added hashtable implementation, to support the reachability check against the
store. This code is by Christopher Clark.

Signed-off-by: Ewan Mellor <ewan@xensource.com>
author emellor@leeni.uk.xensource.com
date Thu Mar 02 21:44:49 2006 +0100 (2006-03-02)
parents af04fef70bad
children 1a1e3dcbbf19
files tools/xenstore/hashtable.c tools/xenstore/hashtable.h tools/xenstore/hashtable_private.h
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/tools/xenstore/hashtable.c	Thu Mar 02 21:44:49 2006 +0100
     1.3 @@ -0,0 +1,274 @@
     1.4 +/* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
     1.5 +
     1.6 +#include "hashtable.h"
     1.7 +#include "hashtable_private.h"
     1.8 +#include <stdlib.h>
     1.9 +#include <stdio.h>
    1.10 +#include <string.h>
    1.11 +#include <math.h>
    1.12 +
    1.13 +/*
    1.14 +Credit for primes table: Aaron Krowne
    1.15 + http://br.endernet.org/~akrowne/
    1.16 + http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
    1.17 +*/
    1.18 +static const unsigned int primes[] = {
    1.19 +53, 97, 193, 389,
    1.20 +769, 1543, 3079, 6151,
    1.21 +12289, 24593, 49157, 98317,
    1.22 +196613, 393241, 786433, 1572869,
    1.23 +3145739, 6291469, 12582917, 25165843,
    1.24 +50331653, 100663319, 201326611, 402653189,
    1.25 +805306457, 1610612741
    1.26 +};
    1.27 +const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
    1.28 +const float max_load_factor = 0.65;
    1.29 +
    1.30 +/*****************************************************************************/
    1.31 +struct hashtable *
    1.32 +create_hashtable(unsigned int minsize,
    1.33 +                 unsigned int (*hashf) (void*),
    1.34 +                 int (*eqf) (void*,void*))
    1.35 +{
    1.36 +    struct hashtable *h;
    1.37 +    unsigned int pindex, size = primes[0];
    1.38 +    /* Check requested hashtable isn't too large */
    1.39 +    if (minsize > (1u << 30)) return NULL;
    1.40 +    /* Enforce size as prime */
    1.41 +    for (pindex=0; pindex < prime_table_length; pindex++) {
    1.42 +        if (primes[pindex] > minsize) { size = primes[pindex]; break; }
    1.43 +    }
    1.44 +    h = (struct hashtable *)malloc(sizeof(struct hashtable));
    1.45 +    if (NULL == h) return NULL; /*oom*/
    1.46 +    h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
    1.47 +    if (NULL == h->table) { free(h); return NULL; } /*oom*/
    1.48 +    memset(h->table, 0, size * sizeof(struct entry *));
    1.49 +    h->tablelength  = size;
    1.50 +    h->primeindex   = pindex;
    1.51 +    h->entrycount   = 0;
    1.52 +    h->hashfn       = hashf;
    1.53 +    h->eqfn         = eqf;
    1.54 +    h->loadlimit    = (unsigned int) ceil(size * max_load_factor);
    1.55 +    return h;
    1.56 +}
    1.57 +
    1.58 +/*****************************************************************************/
    1.59 +unsigned int
    1.60 +hash(struct hashtable *h, void *k)
    1.61 +{
    1.62 +    /* Aim to protect against poor hash functions by adding logic here
    1.63 +     * - logic taken from java 1.4 hashtable source */
    1.64 +    unsigned int i = h->hashfn(k);
    1.65 +    i += ~(i << 9);
    1.66 +    i ^=  ((i >> 14) | (i << 18)); /* >>> */
    1.67 +    i +=  (i << 4);
    1.68 +    i ^=  ((i >> 10) | (i << 22)); /* >>> */
    1.69 +    return i;
    1.70 +}
    1.71 +
    1.72 +/*****************************************************************************/
    1.73 +static int
    1.74 +hashtable_expand(struct hashtable *h)
    1.75 +{
    1.76 +    /* Double the size of the table to accomodate more entries */
    1.77 +    struct entry **newtable;
    1.78 +    struct entry *e;
    1.79 +    struct entry **pE;
    1.80 +    unsigned int newsize, i, index;
    1.81 +    /* Check we're not hitting max capacity */
    1.82 +    if (h->primeindex == (prime_table_length - 1)) return 0;
    1.83 +    newsize = primes[++(h->primeindex)];
    1.84 +
    1.85 +    newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
    1.86 +    if (NULL != newtable)
    1.87 +    {
    1.88 +        memset(newtable, 0, newsize * sizeof(struct entry *));
    1.89 +        /* This algorithm is not 'stable'. ie. it reverses the list
    1.90 +         * when it transfers entries between the tables */
    1.91 +        for (i = 0; i < h->tablelength; i++) {
    1.92 +            while (NULL != (e = h->table[i])) {
    1.93 +                h->table[i] = e->next;
    1.94 +                index = indexFor(newsize,e->h);
    1.95 +                e->next = newtable[index];
    1.96 +                newtable[index] = e;
    1.97 +            }
    1.98 +        }
    1.99 +        free(h->table);
   1.100 +        h->table = newtable;
   1.101 +    }
   1.102 +    /* Plan B: realloc instead */
   1.103 +    else 
   1.104 +    {
   1.105 +        newtable = (struct entry **)
   1.106 +                   realloc(h->table, newsize * sizeof(struct entry *));
   1.107 +        if (NULL == newtable) { (h->primeindex)--; return 0; }
   1.108 +        h->table = newtable;
   1.109 +        memset(newtable[h->tablelength], 0, newsize - h->tablelength);
   1.110 +        for (i = 0; i < h->tablelength; i++) {
   1.111 +            for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
   1.112 +                index = indexFor(newsize,e->h);
   1.113 +                if (index == i)
   1.114 +                {
   1.115 +                    pE = &(e->next);
   1.116 +                }
   1.117 +                else
   1.118 +                {
   1.119 +                    *pE = e->next;
   1.120 +                    e->next = newtable[index];
   1.121 +                    newtable[index] = e;
   1.122 +                }
   1.123 +            }
   1.124 +        }
   1.125 +    }
   1.126 +    h->tablelength = newsize;
   1.127 +    h->loadlimit   = (unsigned int) ceil(newsize * max_load_factor);
   1.128 +    return -1;
   1.129 +}
   1.130 +
   1.131 +/*****************************************************************************/
   1.132 +unsigned int
   1.133 +hashtable_count(struct hashtable *h)
   1.134 +{
   1.135 +    return h->entrycount;
   1.136 +}
   1.137 +
   1.138 +/*****************************************************************************/
   1.139 +int
   1.140 +hashtable_insert(struct hashtable *h, void *k, void *v)
   1.141 +{
   1.142 +    /* This method allows duplicate keys - but they shouldn't be used */
   1.143 +    unsigned int index;
   1.144 +    struct entry *e;
   1.145 +    if (++(h->entrycount) > h->loadlimit)
   1.146 +    {
   1.147 +        /* Ignore the return value. If expand fails, we should
   1.148 +         * still try cramming just this value into the existing table
   1.149 +         * -- we may not have memory for a larger table, but one more
   1.150 +         * element may be ok. Next time we insert, we'll try expanding again.*/
   1.151 +        hashtable_expand(h);
   1.152 +    }
   1.153 +    e = (struct entry *)malloc(sizeof(struct entry));
   1.154 +    if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
   1.155 +    e->h = hash(h,k);
   1.156 +    index = indexFor(h->tablelength,e->h);
   1.157 +    e->k = k;
   1.158 +    e->v = v;
   1.159 +    e->next = h->table[index];
   1.160 +    h->table[index] = e;
   1.161 +    return -1;
   1.162 +}
   1.163 +
   1.164 +/*****************************************************************************/
   1.165 +void * /* returns value associated with key */
   1.166 +hashtable_search(struct hashtable *h, void *k)
   1.167 +{
   1.168 +    struct entry *e;
   1.169 +    unsigned int hashvalue, index;
   1.170 +    hashvalue = hash(h,k);
   1.171 +    index = indexFor(h->tablelength,hashvalue);
   1.172 +    e = h->table[index];
   1.173 +    while (NULL != e)
   1.174 +    {
   1.175 +        /* Check hash value to short circuit heavier comparison */
   1.176 +        if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
   1.177 +        e = e->next;
   1.178 +    }
   1.179 +    return NULL;
   1.180 +}
   1.181 +
   1.182 +/*****************************************************************************/
   1.183 +void * /* returns value associated with key */
   1.184 +hashtable_remove(struct hashtable *h, void *k)
   1.185 +{
   1.186 +    /* TODO: consider compacting the table when the load factor drops enough,
   1.187 +     *       or provide a 'compact' method. */
   1.188 +
   1.189 +    struct entry *e;
   1.190 +    struct entry **pE;
   1.191 +    void *v;
   1.192 +    unsigned int hashvalue, index;
   1.193 +
   1.194 +    hashvalue = hash(h,k);
   1.195 +    index = indexFor(h->tablelength,hash(h,k));
   1.196 +    pE = &(h->table[index]);
   1.197 +    e = *pE;
   1.198 +    while (NULL != e)
   1.199 +    {
   1.200 +        /* Check hash value to short circuit heavier comparison */
   1.201 +        if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
   1.202 +        {
   1.203 +            *pE = e->next;
   1.204 +            h->entrycount--;
   1.205 +            v = e->v;
   1.206 +            freekey(e->k);
   1.207 +            free(e);
   1.208 +            return v;
   1.209 +        }
   1.210 +        pE = &(e->next);
   1.211 +        e = e->next;
   1.212 +    }
   1.213 +    return NULL;
   1.214 +}
   1.215 +
   1.216 +/*****************************************************************************/
   1.217 +/* destroy */
   1.218 +void
   1.219 +hashtable_destroy(struct hashtable *h, int free_values)
   1.220 +{
   1.221 +    unsigned int i;
   1.222 +    struct entry *e, *f;
   1.223 +    struct entry **table = h->table;
   1.224 +    if (free_values)
   1.225 +    {
   1.226 +        for (i = 0; i < h->tablelength; i++)
   1.227 +        {
   1.228 +            e = table[i];
   1.229 +            while (NULL != e)
   1.230 +            { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
   1.231 +        }
   1.232 +    }
   1.233 +    else
   1.234 +    {
   1.235 +        for (i = 0; i < h->tablelength; i++)
   1.236 +        {
   1.237 +            e = table[i];
   1.238 +            while (NULL != e)
   1.239 +            { f = e; e = e->next; freekey(f->k); free(f); }
   1.240 +        }
   1.241 +    }
   1.242 +    free(h->table);
   1.243 +    free(h);
   1.244 +}
   1.245 +
   1.246 +/*
   1.247 + * Copyright (c) 2002, Christopher Clark
   1.248 + * All rights reserved.
   1.249 + * 
   1.250 + * Redistribution and use in source and binary forms, with or without
   1.251 + * modification, are permitted provided that the following conditions
   1.252 + * are met:
   1.253 + * 
   1.254 + * * Redistributions of source code must retain the above copyright
   1.255 + * notice, this list of conditions and the following disclaimer.
   1.256 + * 
   1.257 + * * Redistributions in binary form must reproduce the above copyright
   1.258 + * notice, this list of conditions and the following disclaimer in the
   1.259 + * documentation and/or other materials provided with the distribution.
   1.260 + * 
   1.261 + * * Neither the name of the original author; nor the names of any contributors
   1.262 + * may be used to endorse or promote products derived from this software
   1.263 + * without specific prior written permission.
   1.264 + * 
   1.265 + * 
   1.266 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   1.267 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   1.268 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   1.269 + * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
   1.270 + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   1.271 + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   1.272 + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   1.273 + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   1.274 + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   1.275 + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   1.276 + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   1.277 +*/
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/tools/xenstore/hashtable.h	Thu Mar 02 21:44:49 2006 +0100
     2.3 @@ -0,0 +1,199 @@
     2.4 +/* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
     2.5 +
     2.6 +#ifndef __HASHTABLE_CWC22_H__
     2.7 +#define __HASHTABLE_CWC22_H__
     2.8 +
     2.9 +struct hashtable;
    2.10 +
    2.11 +/* Example of use:
    2.12 + *
    2.13 + *      struct hashtable  *h;
    2.14 + *      struct some_key   *k;
    2.15 + *      struct some_value *v;
    2.16 + *
    2.17 + *      static unsigned int         hash_from_key_fn( void *k );
    2.18 + *      static int                  keys_equal_fn ( void *key1, void *key2 );
    2.19 + *
    2.20 + *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
    2.21 + *      k = (struct some_key *)     malloc(sizeof(struct some_key));
    2.22 + *      v = (struct some_value *)   malloc(sizeof(struct some_value));
    2.23 + *
    2.24 + *      (initialise k and v to suitable values)
    2.25 + * 
    2.26 + *      if (! hashtable_insert(h,k,v) )
    2.27 + *      {     exit(-1);               }
    2.28 + *
    2.29 + *      if (NULL == (found = hashtable_search(h,k) ))
    2.30 + *      {    printf("not found!");                  }
    2.31 + *
    2.32 + *      if (NULL == (found = hashtable_remove(h,k) ))
    2.33 + *      {    printf("Not found\n");                 }
    2.34 + *
    2.35 + */
    2.36 +
    2.37 +/* Macros may be used to define type-safe(r) hashtable access functions, with
    2.38 + * methods specialized to take known key and value types as parameters.
    2.39 + * 
    2.40 + * Example:
    2.41 + *
    2.42 + * Insert this at the start of your file:
    2.43 + *
    2.44 + * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
    2.45 + * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
    2.46 + * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
    2.47 + *
    2.48 + * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
    2.49 + * These operate just like hashtable_insert etc., with the same parameters,
    2.50 + * but their function signatures have 'struct some_key *' rather than
    2.51 + * 'void *', and hence can generate compile time errors if your program is
    2.52 + * supplying incorrect data as a key (and similarly for value).
    2.53 + *
    2.54 + * Note that the hash and key equality functions passed to create_hashtable
    2.55 + * still take 'void *' parameters instead of 'some key *'. This shouldn't be
    2.56 + * a difficult issue as they're only defined and passed once, and the other
    2.57 + * functions will ensure that only valid keys are supplied to them.
    2.58 + *
    2.59 + * The cost for this checking is increased code size and runtime overhead
    2.60 + * - if performance is important, it may be worth switching back to the
    2.61 + * unsafe methods once your program has been debugged with the safe methods.
    2.62 + * This just requires switching to some simple alternative defines - eg:
    2.63 + * #define insert_some hashtable_insert
    2.64 + *
    2.65 + */
    2.66 +
    2.67 +/*****************************************************************************
    2.68 + * create_hashtable
    2.69 +   
    2.70 + * @name                    create_hashtable
    2.71 + * @param   minsize         minimum initial size of hashtable
    2.72 + * @param   hashfunction    function for hashing keys
    2.73 + * @param   key_eq_fn       function for determining key equality
    2.74 + * @return                  newly created hashtable or NULL on failure
    2.75 + */
    2.76 +
    2.77 +struct hashtable *
    2.78 +create_hashtable(unsigned int minsize,
    2.79 +                 unsigned int (*hashfunction) (void*),
    2.80 +                 int (*key_eq_fn) (void*,void*));
    2.81 +
    2.82 +/*****************************************************************************
    2.83 + * hashtable_insert
    2.84 +   
    2.85 + * @name        hashtable_insert
    2.86 + * @param   h   the hashtable to insert into
    2.87 + * @param   k   the key - hashtable claims ownership and will free on removal
    2.88 + * @param   v   the value - does not claim ownership
    2.89 + * @return      non-zero for successful insertion
    2.90 + *
    2.91 + * This function will cause the table to expand if the insertion would take
    2.92 + * the ratio of entries to table size over the maximum load factor.
    2.93 + *
    2.94 + * This function does not check for repeated insertions with a duplicate key.
    2.95 + * The value returned when using a duplicate key is undefined -- when
    2.96 + * the hashtable changes size, the order of retrieval of duplicate key
    2.97 + * entries is reversed.
    2.98 + * If in doubt, remove before insert.
    2.99 + */
   2.100 +
   2.101 +int 
   2.102 +hashtable_insert(struct hashtable *h, void *k, void *v);
   2.103 +
   2.104 +#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
   2.105 +int fnname (struct hashtable *h, keytype *k, valuetype *v) \
   2.106 +{ \
   2.107 +    return hashtable_insert(h,k,v); \
   2.108 +}
   2.109 +
   2.110 +/*****************************************************************************
   2.111 + * hashtable_search
   2.112 +   
   2.113 + * @name        hashtable_search
   2.114 + * @param   h   the hashtable to search
   2.115 + * @param   k   the key to search for  - does not claim ownership
   2.116 + * @return      the value associated with the key, or NULL if none found
   2.117 + */
   2.118 +
   2.119 +void *
   2.120 +hashtable_search(struct hashtable *h, void *k);
   2.121 +
   2.122 +#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
   2.123 +valuetype * fnname (struct hashtable *h, keytype *k) \
   2.124 +{ \
   2.125 +    return (valuetype *) (hashtable_search(h,k)); \
   2.126 +}
   2.127 +
   2.128 +/*****************************************************************************
   2.129 + * hashtable_remove
   2.130 +   
   2.131 + * @name        hashtable_remove
   2.132 + * @param   h   the hashtable to remove the item from
   2.133 + * @param   k   the key to search for  - does not claim ownership
   2.134 + * @return      the value associated with the key, or NULL if none found
   2.135 + */
   2.136 +
   2.137 +void * /* returns value */
   2.138 +hashtable_remove(struct hashtable *h, void *k);
   2.139 +
   2.140 +#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
   2.141 +valuetype * fnname (struct hashtable *h, keytype *k) \
   2.142 +{ \
   2.143 +    return (valuetype *) (hashtable_remove(h,k)); \
   2.144 +}
   2.145 +
   2.146 +
   2.147 +/*****************************************************************************
   2.148 + * hashtable_count
   2.149 +   
   2.150 + * @name        hashtable_count
   2.151 + * @param   h   the hashtable
   2.152 + * @return      the number of items stored in the hashtable
   2.153 + */
   2.154 +unsigned int
   2.155 +hashtable_count(struct hashtable *h);
   2.156 +
   2.157 +
   2.158 +/*****************************************************************************
   2.159 + * hashtable_destroy
   2.160 +   
   2.161 + * @name        hashtable_destroy
   2.162 + * @param   h   the hashtable
   2.163 + * @param       free_values     whether to call 'free' on the remaining values
   2.164 + */
   2.165 +
   2.166 +void
   2.167 +hashtable_destroy(struct hashtable *h, int free_values);
   2.168 +
   2.169 +#endif /* __HASHTABLE_CWC22_H__ */
   2.170 +
   2.171 +/*
   2.172 + * Copyright (c) 2002, Christopher Clark
   2.173 + * All rights reserved.
   2.174 + * 
   2.175 + * Redistribution and use in source and binary forms, with or without
   2.176 + * modification, are permitted provided that the following conditions
   2.177 + * are met:
   2.178 + * 
   2.179 + * * Redistributions of source code must retain the above copyright
   2.180 + * notice, this list of conditions and the following disclaimer.
   2.181 + * 
   2.182 + * * Redistributions in binary form must reproduce the above copyright
   2.183 + * notice, this list of conditions and the following disclaimer in the
   2.184 + * documentation and/or other materials provided with the distribution.
   2.185 + * 
   2.186 + * * Neither the name of the original author; nor the names of any contributors
   2.187 + * may be used to endorse or promote products derived from this software
   2.188 + * without specific prior written permission.
   2.189 + * 
   2.190 + * 
   2.191 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   2.192 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   2.193 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   2.194 + * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
   2.195 + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   2.196 + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   2.197 + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   2.198 + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   2.199 + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   2.200 + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   2.201 + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   2.202 +*/
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/tools/xenstore/hashtable_private.h	Thu Mar 02 21:44:49 2006 +0100
     3.3 @@ -0,0 +1,85 @@
     3.4 +/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
     3.5 +
     3.6 +#ifndef __HASHTABLE_PRIVATE_CWC22_H__
     3.7 +#define __HASHTABLE_PRIVATE_CWC22_H__
     3.8 +
     3.9 +#include "hashtable.h"
    3.10 +
    3.11 +/*****************************************************************************/
    3.12 +struct entry
    3.13 +{
    3.14 +    void *k, *v;
    3.15 +    unsigned int h;
    3.16 +    struct entry *next;
    3.17 +};
    3.18 +
    3.19 +struct hashtable {
    3.20 +    unsigned int tablelength;
    3.21 +    struct entry **table;
    3.22 +    unsigned int entrycount;
    3.23 +    unsigned int loadlimit;
    3.24 +    unsigned int primeindex;
    3.25 +    unsigned int (*hashfn) (void *k);
    3.26 +    int (*eqfn) (void *k1, void *k2);
    3.27 +};
    3.28 +
    3.29 +/*****************************************************************************/
    3.30 +unsigned int
    3.31 +hash(struct hashtable *h, void *k);
    3.32 +
    3.33 +/*****************************************************************************/
    3.34 +/* indexFor */
    3.35 +static inline unsigned int
    3.36 +indexFor(unsigned int tablelength, unsigned int hashvalue) {
    3.37 +    return (hashvalue % tablelength);
    3.38 +};
    3.39 +
    3.40 +/* Only works if tablelength == 2^N */
    3.41 +/*static inline unsigned int
    3.42 +indexFor(unsigned int tablelength, unsigned int hashvalue)
    3.43 +{
    3.44 +    return (hashvalue & (tablelength - 1u));
    3.45 +}
    3.46 +*/
    3.47 +
    3.48 +/*****************************************************************************/
    3.49 +#define freekey(X) free(X)
    3.50 +/*define freekey(X) ; */
    3.51 +
    3.52 +
    3.53 +/*****************************************************************************/
    3.54 +
    3.55 +#endif /* __HASHTABLE_PRIVATE_CWC22_H__*/
    3.56 +
    3.57 +/*
    3.58 + * Copyright (c) 2002, Christopher Clark
    3.59 + * All rights reserved.
    3.60 + * 
    3.61 + * Redistribution and use in source and binary forms, with or without
    3.62 + * modification, are permitted provided that the following conditions
    3.63 + * are met:
    3.64 + * 
    3.65 + * * Redistributions of source code must retain the above copyright
    3.66 + * notice, this list of conditions and the following disclaimer.
    3.67 + * 
    3.68 + * * Redistributions in binary form must reproduce the above copyright
    3.69 + * notice, this list of conditions and the following disclaimer in the
    3.70 + * documentation and/or other materials provided with the distribution.
    3.71 + * 
    3.72 + * * Neither the name of the original author; nor the names of any contributors
    3.73 + * may be used to endorse or promote products derived from this software
    3.74 + * without specific prior written permission.
    3.75 + * 
    3.76 + * 
    3.77 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    3.78 + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    3.79 + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    3.80 + * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
    3.81 + * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    3.82 + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    3.83 + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    3.84 + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    3.85 + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    3.86 + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    3.87 + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    3.88 +*/