util/src/hash.c - axis-axis2-c-core - Git at Google

 /*
  * Licensed to the Apache Software Foundation (ASF) under one or more
  * contributor license agreements.  See the NOTICE file distributed with
  * this work for additional information regarding copyright ownership.
  * The ASF licenses this file to You under the Apache License, Version 2.0
  * (the "License"); you may not use this file except in compliance with
  * the License.  You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "axutil_hash.h"

 #include <axutil_string.h>
 #include <axutil_utils.h>

 /*
  * The internal form of a hash table.
  *
  * The table is an array indexed by the hash of the key; collisions
  * are resolved by hanging a linked list of hash entries off each
  * element of the array. Although this is a really simple design it
  * isn't too bad given that environments have a low allocation overhead.
  */

 typedef struct axutil_hash_entry_t axutil_hash_entry_t;

 struct axutil_hash_entry_t
 {
     axutil_hash_entry_t *next;
     unsigned int hash;
     const void *key;
     axis2_ssize_t klen;
     const void *val;
 };

 /*
  * Data structure for iterating through a hash table.
  * We keep a pointer to the next hash entry here to allow the current
  * hash entry to be freed or otherwise mangled between calls to
  * axutil_hash_next().
  */
 struct axutil_hash_index_t
 {
     axutil_hash_t *ht;
     axutil_hash_entry_t *this, *next;
     unsigned int index;
 };

 /*
  * The size of the array is always a power of two. We use the maximum
  * index rather than the size so that we can use bitwise-AND for
  * modular arithmetic.
  * The count of hash entries may be greater depending on the chosen
  * collision rate.
  */
 struct axutil_hash_t
 {
     const axutil_env_t *env;
     axutil_hash_entry_t **array;
     axutil_hash_index_t iterator; /* For axutil_hash_first(NULL, ...) */
     unsigned int count;
     unsigned int max;
     axutil_hashfunc_t hash_func;
     axutil_hash_entry_t *free; /* List of recycled entries */
 };

 #define INITIAL_MAX 15          /* tunable == 2^n - 1 */

 /*
  * Hash creation functions.
  */

 static axutil_hash_entry_t **
 axutil_hash_alloc_array(
     axutil_hash_t *ht,
     unsigned int max)
 {
     axutil_hash_entry_t **he = AXIS2_MALLOC(ht->env->allocator, sizeof(*ht->array) * (max + 1));

     if (!he)
         return NULL;

     memset(he, 0, sizeof(*ht->array) * (max + 1));
     return he;
 }

 AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
 axutil_hash_make(
     const axutil_env_t *env)
 {
     axutil_hash_t *ht;
     AXIS2_ENV_CHECK(env, NULL);

     ht = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t));
     if(!ht)
     {
         AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_MEMORY, AXIS2_FAILURE);
         return NULL;
     }
     axutil_env_increment_ref((axutil_env_t*)env);
     ht->env = env;
     ht->free = NULL;
     ht->count = 0;
     ht->max = INITIAL_MAX;
     ht->array = axutil_hash_alloc_array(ht, ht->max);
     ht->hash_func = axutil_hashfunc_default;
     return ht;
 }

 AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
 axutil_hash_make_custom(
     const axutil_env_t *env,
     axutil_hashfunc_t hash_func)
 {
     axutil_hash_t *ht;
     AXIS2_ENV_CHECK(env, NULL);
     ht = axutil_hash_make(env);
     if(ht)
     {
         ht->hash_func = hash_func;
     }
     return ht;
 }

 /*
  * Hash iteration functions.
  */

 AXIS2_EXTERN axutil_hash_index_t *AXIS2_CALL
 axutil_hash_next(
     const axutil_env_t *env,
     axutil_hash_index_t *hi)
 {
     hi->this = hi->next;
     while(!hi->this)
     {
         if(hi->index > hi->ht->max)
         {
             if(env)
                 AXIS2_FREE(env->allocator, hi);
             return NULL;
         }

         hi->this = hi->ht->array[hi->index++];
     }
     hi->next = hi->this->next;
     return hi;
 }

 AXIS2_EXTERN axutil_hash_index_t *AXIS2_CALL
 axutil_hash_first(
     axutil_hash_t *ht,
     const axutil_env_t *env)
 {
     axutil_hash_index_t *hi;
     if(env)
         hi = AXIS2_MALLOC(env->allocator, sizeof(*hi));
     else
         hi = &ht->iterator;

     hi->ht = ht;
     hi->index = 0;
     hi->this = NULL;
     hi->next = NULL;
     return axutil_hash_next(env, hi);
 }

 AXIS2_EXTERN void AXIS2_CALL
 axutil_hash_this(
     axutil_hash_index_t *hi,
     const void **key,
     axis2_ssize_t *klen,
     void **val)
 {
     if(key)
         *key = hi->this->key;
     if(klen)
         *klen = hi->this->klen;
     if(val)
         *val = (void *)hi->this->val;
 }

 /*
  * Expanding a hash table
  */

 static void
 axutil_hash_expand_array(
     axutil_hash_t *ht)
 {
     axutil_hash_index_t *hi;

     axutil_hash_entry_t **new_array;
     unsigned int new_max;

     new_max = ht->max * 2 + 1;
     new_array = axutil_hash_alloc_array(ht, new_max);
     for(hi = axutil_hash_first(ht, NULL); hi; hi = axutil_hash_next(NULL, hi))
     {
         unsigned int i = hi->this->hash & new_max;
         hi->this->next = new_array[i];
         new_array[i] = hi->this;
     }
     AXIS2_FREE(ht->env->allocator, ht->array);
     ht->array = new_array;
     ht->max = new_max;
 }

 unsigned int
 axutil_hashfunc_default(
     const char *char_key,
     axis2_ssize_t *klen)
 {
     unsigned int hash = 0;
     const unsigned char *key = (const unsigned char *)char_key;
     const unsigned char *p;
     axis2_ssize_t i;

     /*
      * This is the popular `times 33' hash algorithm which is used by
      * perl and also appears in Berkeley DB. This is one of the best
      * known hash functions for strings because it is both computed
      * very fast and distributes very well.
      *
      * The originator may be Dan Bernstein but the code in Berkeley DB
      * cites Chris Torek as the source. The best citation I have found
      * is "Chris Torek, Hash function for text in C, Usenet message
      * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
      * Salz's USENIX 1992 paper about INN which can be found at
      * <http://citeseer.nj.nec.com/salz92internetnews.html>.
      *
      * The magic of number 33, i.e. why it works better than many other
      * constants, prime or not, has never been adequately explained by
      * anyone. So I try an explanation: if one experimentally tests all
      * multipliers between 1 and 256 (as I did while writing a low-level
      * data structure library some time ago) one detects that even
      * numbers are not useable at all. The remaining 128 odd numbers
      * (except for the number 1) work more or less all equally well.
      * They all distribute in an acceptable way and this way fill a hash
      * table with an average percent of approx. 86%.
      *
      * If one compares the chi^2 values of the variants (see
      * Bob Jenkins ``Hashing Frequently Asked Questions'' at
      * http://burtleburtle.net/bob/hash/hashfaq.html for a description
      * of chi^2), the number 33 not even has the best value. But the
      * number 33 and a few other equally good numbers like 17, 31, 63,
      * 127 and 129 have nevertheless a great advantage to the remaining
      * numbers in the large set of possible multipliers: their multiply
      * op can be replaced by a faster op based on just one
      * shift plus either a single addition or subtraction op. And
      * because a hash function has to both distribute good _and_ has to
      * be very fast to compute, those few numbers should be preferred.
      *
      *                  -- Ralf S. Engelschall <rse@engelschall.com>
      */

     if(*klen == AXIS2_HASH_KEY_STRING)
     {
         for(p = key; *p; p++)
         {
             hash = hash * 33 + *p;
         }
         *klen = (axis2_ssize_t)(p - key);
         /* We are sure that the difference lies within the axis2_ssize_t range */
     }
     else
     {
         for(p = key, i = *klen; i; i--, p++)
         {
             hash = hash * 33 + *p;
         }
     }

     return hash;
 }

 /*
  * This is where we keep the details of the hash function and control
  * the maximum collision rate.
  *
  * If val is non-NULL it creates and initializes a new hash entry if
  * there isn't already one there; it returns an updatable pointer so
  * that hash entries can be removed.
  */

 static axutil_hash_entry_t **
 axutil_hash_find_entry(
     axutil_hash_t *ht,
     const void *key,
     axis2_ssize_t klen,
     const void *val)
 {
     axutil_hash_entry_t **hep, *he;
     unsigned int hash;

     hash = ht->hash_func(key, &klen);

     /* scan linked list */
     for(hep = &ht->array[hash & ht->max], he = *hep; he; hep = &he->next, he = *hep)
     {
         if(he->hash == hash && he->klen == klen && memcmp(he->key, key, klen) == 0)
             break;
     }

     if(he || !val)
         return hep;

     /* add a new entry for non-NULL values */
     he = ht->free;
     if(he)
         ht->free = he->next;
     else
         he = AXIS2_MALLOC(ht->env->allocator, sizeof(*he));
     he->next = NULL;
     he->hash = hash;
     he->key = key;
     he->klen = klen;
     he->val = val;
     *hep = he;
     ht->count++;
     return hep;
 }

 AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
 axutil_hash_copy(
     const axutil_hash_t *orig,
     const axutil_env_t *env)
 {
     axutil_hash_t *ht;
     axutil_hash_entry_t *new_vals;
     unsigned int i, j;

     ht = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t) + sizeof(*ht->array) * (orig->max + 1)
         + sizeof(axutil_hash_entry_t) * orig->count);
     ht->env = env;
     axutil_env_increment_ref((axutil_env_t*)env);
     ht->free = NULL;
     ht->count = orig->count;
     ht->max = orig->max;
     ht->hash_func = orig->hash_func;
     ht->array = (axutil_hash_entry_t **)((char *)ht + sizeof(axutil_hash_t));

     new_vals = (axutil_hash_entry_t *)((char *)(ht) + sizeof(axutil_hash_t) + sizeof(*ht->array)
         * (orig->max + 1));
     j = 0;
     for(i = 0; i <= ht->max; i++)
     {
         axutil_hash_entry_t **new_entry = &(ht->array[i]);
         axutil_hash_entry_t *orig_entry = orig->array[i];
         while(orig_entry)
         {
             *new_entry = &new_vals[j++];
             (*new_entry)->hash = orig_entry->hash;
             (*new_entry)->key = orig_entry->key;
             (*new_entry)->klen = orig_entry->klen;
             (*new_entry)->val = orig_entry->val;
             new_entry = &((*new_entry)->next);
             orig_entry = orig_entry->next;
         }
         *new_entry = NULL;
     }
     return ht;
 }

 AXIS2_EXTERN void *AXIS2_CALL
 axutil_hash_get(
     axutil_hash_t *ht,
     const void *key,
     axis2_ssize_t klen)
 {
     axutil_hash_entry_t *he;
     he = *axutil_hash_find_entry(ht, key, klen, NULL);
     if(he)
         return (void *)he->val;
     else
         return NULL;
 }

 AXIS2_EXTERN void AXIS2_CALL
 axutil_hash_set(
     axutil_hash_t *ht,
     const void *key,
     axis2_ssize_t klen,
     const void *val)
 {
     axutil_hash_entry_t **hep;
     hep = axutil_hash_find_entry(ht, key, klen, val);
     if(*hep)
     {
         if(!val)
         {
             /* delete entry */
             axutil_hash_entry_t *old = *hep;
             *hep = (*hep)->next;
             old->next = ht->free;
             ht->free = old;
             --ht->count;
         }
         else
         {
             /* replace entry */
             (*hep)->val = val;
             /* check that the collision rate isn't too high */
             if(ht->count > ht->max)
             {
                 axutil_hash_expand_array(ht);
             }
         }
     }
     /* else key not present and val==NULL */
 }

 AXIS2_EXTERN unsigned int AXIS2_CALL
 axutil_hash_count(
     axutil_hash_t *ht)
 {
     return ht->count;
 }

 AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
 axutil_hash_overlay(
     const axutil_hash_t *overlay,
     const axutil_env_t *env,
     const axutil_hash_t *base)
 {
     return axutil_hash_merge(overlay, env, base, NULL, NULL);
 }

 AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
 axutil_hash_merge(
     const axutil_hash_t *overlay,
     const axutil_env_t *env,
     const axutil_hash_t *base,
     void *
     (*merger)(
         const axutil_env_t *env,
         const void *key,
         axis2_ssize_t klen,
         const void *h1_val,
         const void *h2_val,
         const void *data),
     const void *data)
 {
     axutil_hash_t *res;
     axutil_hash_entry_t *new_vals = NULL;
     axutil_hash_entry_t *iter;
     axutil_hash_entry_t *ent;
     unsigned int i, k;

 #if AXIS2_POOL_DEBUG
     /* we don't copy keys and values, so it's necessary that
      * overlay->a.env and base->a.env have a life span at least
      * as long as p
      */
     if (!axutil_env_is_ancestor(overlay->env, p))
     {
         fprintf(stderr,
             "axutil_hash_merge: overlay's env is not an ancestor of p\n");
         abort();
     }
     if (!axutil_env_is_ancestor(base->env, p))
     {
         fprintf(stderr,
             "axutil_hash_merge: base's env is not an ancestor of p\n");
         abort();
     }
 #endif

     res = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t));
     res->env = env;
     axutil_env_increment_ref((axutil_env_t*)env);
     res->free = NULL;
     res->hash_func = base->hash_func;
     res->count = base->count;
     res->max = (overlay->max > base->max) ? overlay->max : base->max;
     if(base->count + overlay->count > res->max)
     {
         res->max = res->max * 2 + 1;
     }
     res->array = axutil_hash_alloc_array(res, res->max);
     for(k = 0; k <= base->max; k++)
     {
         for(iter = base->array[k]; iter; iter = iter->next)
         {
             i = iter->hash & res->max;
             new_vals = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_entry_t));
             new_vals->klen = iter->klen;
             new_vals->key = iter->key;
             new_vals->val = iter->val;
             new_vals->hash = iter->hash;
             new_vals->next = res->array[i];
             res->array[i] = new_vals;
         }
     }

     for(k = 0; k <= overlay->max; k++)
     {
         for(iter = overlay->array[k]; iter; iter = iter->next)
         {
             i = iter->hash & res->max;
             for(ent = res->array[i]; ent; ent = ent->next)
             {
                 if((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0))
                 {
                     if(merger)
                     {
                         ent->val = (*merger)(env, iter->key, iter->klen, iter->val, ent->val, data);
                     }
                     else
                     {
                         ent->val = iter->val;
                     }
                     break;
                 }
             }
             if(!ent)
             {
                 new_vals = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_entry_t));
                 new_vals->klen = iter->klen;
                 new_vals->key = iter->key;
                 new_vals->val = iter->val;
                 new_vals->hash = iter->hash;
                 new_vals->next = res->array[i];
                 res->array[i] = new_vals;
                 res->count++;
             }
         }
     }
     return res;
 }

 AXIS2_EXTERN axis2_bool_t AXIS2_CALL
 axutil_hash_contains_key(
     axutil_hash_t *ht,
     const axutil_env_t *env,
     const axis2_char_t *key)
 {
     axutil_hash_index_t *i = NULL;

     for(i = axutil_hash_first(ht, env); i; i = axutil_hash_next(env, i))
     {
         const void *v = NULL;
         const axis2_char_t *key_l = NULL;

         axutil_hash_this(i, &v, NULL, NULL);
         key_l = (const axis2_char_t *)v;
         if(0 == axutil_strcmp(key, key_l))
             return AXIS2_TRUE;
     }

     return AXIS2_FALSE;
 }

 /*
  void
  axutil_hash_entry_free(
  const axutil_env_t *env,
  axutil_hash_entry_t *hash_entry)
  {
  if (!hash_entry)
  return;
  if (hash_entry->next)
  {
  axutil_hash_entry_free(env, hash_entry->next);
  }
  AXIS2_FREE(env->allocator, hash_entry);
  return;
  }
  */

 AXIS2_EXTERN void AXIS2_CALL
 axutil_hash_free(
     axutil_hash_t *ht,
     const axutil_env_t *env)
 {
     unsigned int i = 0;
     if(ht)
     {
         for(i = 0; i <= ht->max; i++)
         {
             axutil_hash_entry_t *next = NULL;
             axutil_hash_entry_t *current = ht->array[i];
             while(current)
             {
                 next = current->next;
                 AXIS2_FREE(env->allocator, current);
                 current = NULL;
                 current = next;
             }
         }
         if(ht->free)
         {
             axutil_hash_entry_t *next = NULL;
             axutil_hash_entry_t *current = ht->free;
             while(current)
             {
                 next = current->next;
                 AXIS2_FREE(env->allocator, current);
                 current = NULL;
                 current = next;
             }
         }

         if(ht->env)
         {
             /*since we now keep a ref count in env and incrementing it
              *inside hash_make we need to free the env.Depending on the
              situation the env struct is freed or ref count will be
              decremented.*/

             axutil_free_thread_env((axutil_env_t*)(ht->env));
             ht->env = NULL;
         }

         AXIS2_FREE(env->allocator, (ht->array));
         AXIS2_FREE(env->allocator, ht);
     }
     return;
 }

 AXIS2_EXTERN void AXIS2_CALL
 axutil_hash_free_void_arg(
     void *ht_void,
     const axutil_env_t *env)
 {
     unsigned int i = 0;
     axutil_hash_t *ht = (axutil_hash_t *)ht_void;
     if(ht)
     {
         for(i = 0; i < ht->max; i++)
         {
             axutil_hash_entry_t *next = NULL;
             axutil_hash_entry_t *current = ht->array[i];
             while(current)
             {
                 next = current->next;
                 AXIS2_FREE(env->allocator, current);
                 current = next;
             }
         }
         AXIS2_FREE(env->allocator, (ht->array));
         AXIS2_FREE(env->allocator, ht);
     }
     return;
 }

 AXIS2_EXTERN void AXIS2_CALL
 axutil_hash_set_env(
     axutil_hash_t * ht,
     const axutil_env_t * env)
 {
     AXIS2_ENV_CHECK(env, AXIS2_FAILURE);
     if(ht)
     {
         if(ht->env)
         {
             /*since we now keep a ref count in env and incrementing it
              *inside hash_make we need to free the env.Depending on the
              situation the env struct is freed or ref count will be
              decremented.*/

             axutil_free_thread_env((axutil_env_t*)(ht->env));
             ht->env = NULL;
         }
         ht->env = env;
         axutil_env_increment_ref((axutil_env_t*)env);
     }
 }
	/*
	* Licensed to the Apache Software Foundation (ASF) under one or more
	* contributor license agreements. See the NOTICE file distributed with
	* this work for additional information regarding copyright ownership.
	* The ASF licenses this file to You under the Apache License, Version 2.0
	* (the "License"); you may not use this file except in compliance with
	* the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "axutil_hash.h"

	#include <axutil_string.h>
	#include <axutil_utils.h>

	/*
	* The internal form of a hash table.
	*
	* The table is an array indexed by the hash of the key; collisions
	* are resolved by hanging a linked list of hash entries off each
	* element of the array. Although this is a really simple design it
	* isn't too bad given that environments have a low allocation overhead.
	*/

	typedef struct axutil_hash_entry_t axutil_hash_entry_t;

	struct axutil_hash_entry_t
	{
	axutil_hash_entry_t *next;
	unsigned int hash;
	const void *key;
	axis2_ssize_t klen;
	const void *val;
	};

	/*
	* Data structure for iterating through a hash table.
	* We keep a pointer to the next hash entry here to allow the current
	* hash entry to be freed or otherwise mangled between calls to
	* axutil_hash_next().
	*/
	struct axutil_hash_index_t
	{
	axutil_hash_t *ht;
	axutil_hash_entry_t this, next;
	unsigned int index;
	};

	/*
	* The size of the array is always a power of two. We use the maximum
	* index rather than the size so that we can use bitwise-AND for
	* modular arithmetic.
	* The count of hash entries may be greater depending on the chosen
	* collision rate.
	*/
	struct axutil_hash_t
	{
	const axutil_env_t *env;
	axutil_hash_entry_t **array;
	axutil_hash_index_t iterator; /* For axutil_hash_first(NULL, ...) */
	unsigned int count;
	unsigned int max;
	axutil_hashfunc_t hash_func;
	axutil_hash_entry_t free; / List of recycled entries */
	};

	#define INITIAL_MAX 15 /* tunable == 2^n - 1 */

	/*
	* Hash creation functions.
	*/

	static axutil_hash_entry_t **
	axutil_hash_alloc_array(
	axutil_hash_t *ht,
	unsigned int max)
	{
	axutil_hash_entry_t *he = AXIS2_MALLOC(ht->env->allocator, sizeof(ht->array) * (max + 1));

	if (!he)
	return NULL;

	memset(he, 0, sizeof(ht->array) (max + 1));
	return he;
	}

	AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
	axutil_hash_make(
	const axutil_env_t *env)
	{
	axutil_hash_t *ht;
	AXIS2_ENV_CHECK(env, NULL);

	ht = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t));
	if(!ht)
	{
	AXIS2_ERROR_SET(env->error, AXIS2_ERROR_NO_MEMORY, AXIS2_FAILURE);
	return NULL;
	}
	axutil_env_increment_ref((axutil_env_t*)env);
	ht->env = env;
	ht->free = NULL;
	ht->count = 0;
	ht->max = INITIAL_MAX;
	ht->array = axutil_hash_alloc_array(ht, ht->max);
	ht->hash_func = axutil_hashfunc_default;
	return ht;
	}

	AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
	axutil_hash_make_custom(
	const axutil_env_t *env,
	axutil_hashfunc_t hash_func)
	{
	axutil_hash_t *ht;
	AXIS2_ENV_CHECK(env, NULL);
	ht = axutil_hash_make(env);
	if(ht)
	{
	ht->hash_func = hash_func;
	}
	return ht;
	}

	/*
	* Hash iteration functions.
	*/

	AXIS2_EXTERN axutil_hash_index_t *AXIS2_CALL
	axutil_hash_next(
	const axutil_env_t *env,
	axutil_hash_index_t *hi)
	{
	hi->this = hi->next;
	while(!hi->this)
	{
	if(hi->index > hi->ht->max)
	{
	if(env)
	AXIS2_FREE(env->allocator, hi);
	return NULL;
	}

	hi->this = hi->ht->array[hi->index++];
	}
	hi->next = hi->this->next;
	return hi;
	}

	AXIS2_EXTERN axutil_hash_index_t *AXIS2_CALL
	axutil_hash_first(
	axutil_hash_t *ht,
	const axutil_env_t *env)
	{
	axutil_hash_index_t *hi;
	if(env)
	hi = AXIS2_MALLOC(env->allocator, sizeof(*hi));
	else
	hi = &ht->iterator;

	hi->ht = ht;
	hi->index = 0;
	hi->this = NULL;
	hi->next = NULL;
	return axutil_hash_next(env, hi);
	}

	AXIS2_EXTERN void AXIS2_CALL
	axutil_hash_this(
	axutil_hash_index_t *hi,
	const void **key,
	axis2_ssize_t *klen,
	void **val)
	{
	if(key)
	*key = hi->this->key;
	if(klen)
	*klen = hi->this->klen;
	if(val)
	val = (void )hi->this->val;
	}

	/*
	* Expanding a hash table
	*/

	static void
	axutil_hash_expand_array(
	axutil_hash_t *ht)
	{
	axutil_hash_index_t *hi;

	axutil_hash_entry_t **new_array;
	unsigned int new_max;

	new_max = ht->max * 2 + 1;
	new_array = axutil_hash_alloc_array(ht, new_max);
	for(hi = axutil_hash_first(ht, NULL); hi; hi = axutil_hash_next(NULL, hi))
	{
	unsigned int i = hi->this->hash & new_max;
	hi->this->next = new_array[i];
	new_array[i] = hi->this;
	}
	AXIS2_FREE(ht->env->allocator, ht->array);
	ht->array = new_array;
	ht->max = new_max;
	}

	unsigned int
	axutil_hashfunc_default(
	const char *char_key,
	axis2_ssize_t *klen)
	{
	unsigned int hash = 0;
	const unsigned char key = (const unsigned char )char_key;
	const unsigned char *p;
	axis2_ssize_t i;

	/*
	* This is the popular `times 33' hash algorithm which is used by
	* perl and also appears in Berkeley DB. This is one of the best
	* known hash functions for strings because it is both computed
	* very fast and distributes very well.
	*
	* The originator may be Dan Bernstein but the code in Berkeley DB
	* cites Chris Torek as the source. The best citation I have found
	* is "Chris Torek, Hash function for text in C, Usenet message
	* <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich
	* Salz's USENIX 1992 paper about INN which can be found at
	* <http://citeseer.nj.nec.com/salz92internetnews.html>.
	*
	* The magic of number 33, i.e. why it works better than many other
	* constants, prime or not, has never been adequately explained by
	* anyone. So I try an explanation: if one experimentally tests all
	* multipliers between 1 and 256 (as I did while writing a low-level
	* data structure library some time ago) one detects that even
	* numbers are not useable at all. The remaining 128 odd numbers
	* (except for the number 1) work more or less all equally well.
	* They all distribute in an acceptable way and this way fill a hash
	* table with an average percent of approx. 86%.
	*
	* If one compares the chi^2 values of the variants (see
	* Bob Jenkins ``Hashing Frequently Asked Questions'' at
	* http://burtleburtle.net/bob/hash/hashfaq.html for a description
	* of chi^2), the number 33 not even has the best value. But the
	* number 33 and a few other equally good numbers like 17, 31, 63,
	* 127 and 129 have nevertheless a great advantage to the remaining
	* numbers in the large set of possible multipliers: their multiply
	* op can be replaced by a faster op based on just one
	* shift plus either a single addition or subtraction op. And
	* because a hash function has to both distribute good _and_ has to
	* be very fast to compute, those few numbers should be preferred.
	*
	* -- Ralf S. Engelschall <rse@engelschall.com>
	*/

	if(*klen == AXIS2_HASH_KEY_STRING)
	{
	for(p = key; *p; p++)
	{
	hash = hash * 33 + *p;
	}
	*klen = (axis2_ssize_t)(p - key);
	/* We are sure that the difference lies within the axis2_ssize_t range */
	}
	else
	{
	for(p = key, i = *klen; i; i--, p++)
	{
	hash = hash * 33 + *p;
	}
	}

	return hash;
	}

	/*
	* This is where we keep the details of the hash function and control
	* the maximum collision rate.
	*
	* If val is non-NULL it creates and initializes a new hash entry if
	* there isn't already one there; it returns an updatable pointer so
	* that hash entries can be removed.
	*/

	static axutil_hash_entry_t **
	axutil_hash_find_entry(
	axutil_hash_t *ht,
	const void *key,
	axis2_ssize_t klen,
	const void *val)
	{
	axutil_hash_entry_t *hep, he;
	unsigned int hash;

	hash = ht->hash_func(key, &klen);

	/* scan linked list */
	for(hep = &ht->array[hash & ht->max], he = hep; he; hep = &he->next, he = hep)
	{
	if(he->hash == hash && he->klen == klen && memcmp(he->key, key, klen) == 0)
	break;
	}

	if(he \|\| !val)
	return hep;

	/* add a new entry for non-NULL values */
	he = ht->free;
	if(he)
	ht->free = he->next;
	else
	he = AXIS2_MALLOC(ht->env->allocator, sizeof(*he));
	he->next = NULL;
	he->hash = hash;
	he->key = key;
	he->klen = klen;
	he->val = val;
	*hep = he;
	ht->count++;
	return hep;
	}

	AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
	axutil_hash_copy(
	const axutil_hash_t *orig,
	const axutil_env_t *env)
	{
	axutil_hash_t *ht;
	axutil_hash_entry_t *new_vals;
	unsigned int i, j;

	ht = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t) + sizeof(ht->array) (orig->max + 1)
	+ sizeof(axutil_hash_entry_t) * orig->count);
	ht->env = env;
	axutil_env_increment_ref((axutil_env_t*)env);
	ht->free = NULL;
	ht->count = orig->count;
	ht->max = orig->max;
	ht->hash_func = orig->hash_func;
	ht->array = (axutil_hash_entry_t *)((char )ht + sizeof(axutil_hash_t));

	new_vals = (axutil_hash_entry_t )((char )(ht) + sizeof(axutil_hash_t) + sizeof(*ht->array)
	* (orig->max + 1));
	j = 0;
	for(i = 0; i <= ht->max; i++)
	{
	axutil_hash_entry_t **new_entry = &(ht->array[i]);
	axutil_hash_entry_t *orig_entry = orig->array[i];
	while(orig_entry)
	{
	*new_entry = &new_vals[j++];
	(*new_entry)->hash = orig_entry->hash;
	(*new_entry)->key = orig_entry->key;
	(*new_entry)->klen = orig_entry->klen;
	(*new_entry)->val = orig_entry->val;
	new_entry = &((*new_entry)->next);
	orig_entry = orig_entry->next;
	}
	*new_entry = NULL;
	}
	return ht;
	}

	AXIS2_EXTERN void *AXIS2_CALL
	axutil_hash_get(
	axutil_hash_t *ht,
	const void *key,
	axis2_ssize_t klen)
	{
	axutil_hash_entry_t *he;
	he = *axutil_hash_find_entry(ht, key, klen, NULL);
	if(he)
	return (void *)he->val;
	else
	return NULL;
	}

	AXIS2_EXTERN void AXIS2_CALL
	axutil_hash_set(
	axutil_hash_t *ht,
	const void *key,
	axis2_ssize_t klen,
	const void *val)
	{
	axutil_hash_entry_t **hep;
	hep = axutil_hash_find_entry(ht, key, klen, val);
	if(*hep)
	{
	if(!val)
	{
	/* delete entry */
	axutil_hash_entry_t old = hep;
	hep = (hep)->next;
	old->next = ht->free;
	ht->free = old;
	--ht->count;
	}
	else
	{
	/* replace entry */
	(*hep)->val = val;
	/* check that the collision rate isn't too high */
	if(ht->count > ht->max)
	{
	axutil_hash_expand_array(ht);
	}
	}
	}
	/* else key not present and val==NULL */
	}

	AXIS2_EXTERN unsigned int AXIS2_CALL
	axutil_hash_count(
	axutil_hash_t *ht)
	{
	return ht->count;
	}

	AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
	axutil_hash_overlay(
	const axutil_hash_t *overlay,
	const axutil_env_t *env,
	const axutil_hash_t *base)
	{
	return axutil_hash_merge(overlay, env, base, NULL, NULL);
	}

	AXIS2_EXTERN axutil_hash_t *AXIS2_CALL
	axutil_hash_merge(
	const axutil_hash_t *overlay,
	const axutil_env_t *env,
	const axutil_hash_t *base,
	void *
	(*merger)(
	const axutil_env_t *env,
	const void *key,
	axis2_ssize_t klen,
	const void *h1_val,
	const void *h2_val,
	const void *data),
	const void *data)
	{
	axutil_hash_t *res;
	axutil_hash_entry_t *new_vals = NULL;
	axutil_hash_entry_t *iter;
	axutil_hash_entry_t *ent;
	unsigned int i, k;

	#if AXIS2_POOL_DEBUG
	/* we don't copy keys and values, so it's necessary that
	* overlay->a.env and base->a.env have a life span at least
	* as long as p
	*/
	if (!axutil_env_is_ancestor(overlay->env, p))
	{
	fprintf(stderr,
	"axutil_hash_merge: overlay's env is not an ancestor of p\n");
	abort();
	}
	if (!axutil_env_is_ancestor(base->env, p))
	{
	fprintf(stderr,
	"axutil_hash_merge: base's env is not an ancestor of p\n");
	abort();
	}
	#endif

	res = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_t));
	res->env = env;
	axutil_env_increment_ref((axutil_env_t*)env);
	res->free = NULL;
	res->hash_func = base->hash_func;
	res->count = base->count;
	res->max = (overlay->max > base->max) ? overlay->max : base->max;
	if(base->count + overlay->count > res->max)
	{
	res->max = res->max * 2 + 1;
	}
	res->array = axutil_hash_alloc_array(res, res->max);
	for(k = 0; k <= base->max; k++)
	{
	for(iter = base->array[k]; iter; iter = iter->next)
	{
	i = iter->hash & res->max;
	new_vals = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_entry_t));
	new_vals->klen = iter->klen;
	new_vals->key = iter->key;
	new_vals->val = iter->val;
	new_vals->hash = iter->hash;
	new_vals->next = res->array[i];
	res->array[i] = new_vals;
	}
	}

	for(k = 0; k <= overlay->max; k++)
	{
	for(iter = overlay->array[k]; iter; iter = iter->next)
	{
	i = iter->hash & res->max;
	for(ent = res->array[i]; ent; ent = ent->next)
	{
	if((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0))
	{
	if(merger)
	{
	ent->val = (*merger)(env, iter->key, iter->klen, iter->val, ent->val, data);
	}
	else
	{
	ent->val = iter->val;
	}
	break;
	}
	}
	if(!ent)
	{
	new_vals = AXIS2_MALLOC(env->allocator, sizeof(axutil_hash_entry_t));
	new_vals->klen = iter->klen;
	new_vals->key = iter->key;
	new_vals->val = iter->val;
	new_vals->hash = iter->hash;
	new_vals->next = res->array[i];
	res->array[i] = new_vals;
	res->count++;
	}
	}
	}
	return res;
	}

	AXIS2_EXTERN axis2_bool_t AXIS2_CALL
	axutil_hash_contains_key(
	axutil_hash_t *ht,
	const axutil_env_t *env,
	const axis2_char_t *key)
	{
	axutil_hash_index_t *i = NULL;

	for(i = axutil_hash_first(ht, env); i; i = axutil_hash_next(env, i))
	{
	const void *v = NULL;
	const axis2_char_t *key_l = NULL;

	axutil_hash_this(i, &v, NULL, NULL);
	key_l = (const axis2_char_t *)v;
	if(0 == axutil_strcmp(key, key_l))
	return AXIS2_TRUE;
	}

	return AXIS2_FALSE;
	}

	/*
	void
	axutil_hash_entry_free(
	const axutil_env_t *env,
	axutil_hash_entry_t *hash_entry)
	{
	if (!hash_entry)
	return;
	if (hash_entry->next)
	{
	axutil_hash_entry_free(env, hash_entry->next);
	}
	AXIS2_FREE(env->allocator, hash_entry);
	return;
	}
	*/

	AXIS2_EXTERN void AXIS2_CALL
	axutil_hash_free(
	axutil_hash_t *ht,
	const axutil_env_t *env)
	{
	unsigned int i = 0;
	if(ht)
	{
	for(i = 0; i <= ht->max; i++)
	{
	axutil_hash_entry_t *next = NULL;
	axutil_hash_entry_t *current = ht->array[i];
	while(current)
	{
	next = current->next;
	AXIS2_FREE(env->allocator, current);
	current = NULL;
	current = next;
	}
	}
	if(ht->free)
	{
	axutil_hash_entry_t *next = NULL;
	axutil_hash_entry_t *current = ht->free;
	while(current)
	{
	next = current->next;
	AXIS2_FREE(env->allocator, current);
	current = NULL;
	current = next;
	}
	}

	if(ht->env)
	{
	/*since we now keep a ref count in env and incrementing it
	*inside hash_make we need to free the env.Depending on the
	situation the env struct is freed or ref count will be
	decremented.*/

	axutil_free_thread_env((axutil_env_t*)(ht->env));
	ht->env = NULL;
	}

	AXIS2_FREE(env->allocator, (ht->array));
	AXIS2_FREE(env->allocator, ht);
	}
	return;
	}

	AXIS2_EXTERN void AXIS2_CALL
	axutil_hash_free_void_arg(
	void *ht_void,
	const axutil_env_t *env)
	{
	unsigned int i = 0;
	axutil_hash_t ht = (axutil_hash_t )ht_void;
	if(ht)
	{
	for(i = 0; i < ht->max; i++)
	{
	axutil_hash_entry_t *next = NULL;
	axutil_hash_entry_t *current = ht->array[i];
	while(current)
	{
	next = current->next;
	AXIS2_FREE(env->allocator, current);
	current = next;
	}
	}
	AXIS2_FREE(env->allocator, (ht->array));
	AXIS2_FREE(env->allocator, ht);
	}
	return;
	}

	AXIS2_EXTERN void AXIS2_CALL
	axutil_hash_set_env(
	axutil_hash_t * ht,
	const axutil_env_t * env)
	{
	AXIS2_ENV_CHECK(env, AXIS2_FAILURE);
	if(ht)
	{
	if(ht->env)
	{
	/*since we now keep a ref count in env and incrementing it
	*inside hash_make we need to free the env.Depending on the
	situation the env struct is freed or ref count will be
	decremented.*/

	axutil_free_thread_env((axutil_env_t*)(ht->env));
	ht->env = NULL;
	}
	ht->env = env;
	axutil_env_increment_ref((axutil_env_t*)env);
	}
	}