Logo Search packages:      
Sourcecode: samba-doc-ja version File versions

hash.c

/*
   Unix SMB/Netbios implementation.
   Version 2.0

   Copyright (C) Ying Chen 2000.
   Copyright (C) Jeremy Allison 2000.
                 - added some defensive programming.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/*
 * NB. We may end up replacing this functionality in a future 2.x 
 * release to reduce the number of hashing/lookup methods we support. JRA.
 */

#include "includes.h"

static BOOL enlarge_hash_table(hash_table *table);
static int primes[] = 
        {17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411};

/****************************************************************************
 *      This function initializes the hash table.
 *      This hash function hashes on string keys.
 *      This number of hash buckets is always rounded up to a power of 
 *      2 first, then to a prime number that is large than the power of two. 
 *      Input:
 *              table -- the hash table pointer.
 *              num_buckets -- the number of buckets to be allocated. This
 *              hash function can dynamically increase its size when the 
 *              the hash table size becomes small. There is a MAX hash table
 *              size defined in hash.h.
 *              compare_func -- the function pointer to a comparison function
 *              used by the hash key comparison.
 ****************************************************************************
 */

BOOL hash_table_init(hash_table *table, int num_buckets, compare_function compare_func)
{
      int   i;
      ubi_dlList  *bucket;

      table->num_elements = 0;
      table->size = 2;
      table->comp_func = compare_func;
      while (table->size < num_buckets) 
            table->size <<= 1;
      for (i = 0; i < ARRAY_SIZE(primes); i++) {
            if (primes[i] > table->size) {
                  table->size = primes[i];
                  break;
            }
      }

      DEBUG(5, ("Hash size = %d.\n", table->size));

      if(!(table->buckets = (ubi_dlList *) malloc(sizeof(ubi_dlList) * table->size))) {
            DEBUG(0,("hash_table_init: malloc fail !\n"));
            return False;
      }
      ubi_dlInitList(&(table->lru_chain));
      for (i=0, bucket = table->buckets; i < table->size; i++, bucket++) 
            ubi_dlInitList(bucket);

      return True;
}

/*
 **************************************************************
 *    Compute a hash value based on a string key value.
 *    Make the string key into an array of int's if possible.
 *    For the last few chars that cannot be int'ed, use char instead.
 *    The function returns the bucket index number for the hashed 
 *    key.
 **************************************************************
 */

static int string_hash(int hash_size, const char *key)
{
      u32 value;  /* Used to compute the hash value.  */
      u32   i;    /* Used to cycle through random values. */

      for (value = 0x238F13AF, i=0; key[i]; i++)
            value = (value + (key[i] << (i*5 % 24)));

      return (1103515243 * value + 12345) % hash_size;  
}


/* *************************************************************************
 *    Search the hash table for the entry in the hash chain.
 *    The function returns the pointer to the 
 *    element found in the chain or NULL if none is found. 
 *    If the element is found, the element is also moved to 
 *    the head of the LRU list.
 *
 *    Input:
 *              table -- The hash table where the element is stored in.
 *              hash_chain -- The pointer to the bucket that stores the 
 *              element to be found.
 *              key -- The hash key to be found. 
 ***************************************************************************
 */

static hash_element *hash_chain_find(hash_table *table, ubi_dlList *hash_chain, char *key)
{
      hash_element *hash_elem;
      ubi_dlNodePtr lru_item;
      int   i = 0;

      for (hash_elem = (hash_element *)(ubi_dlFirst(hash_chain)); i < hash_chain->count; 
            i++, hash_elem = (hash_element *)(ubi_dlNext(hash_elem))) {
            if ((table->comp_func)(hash_elem->key, key) == 0) {
                  /* Move to the head of the lru List. */
                  lru_item = ubi_dlRemove(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
                  ubi_dlAddHead(&(table->lru_chain), lru_item);
                  return(hash_elem);
            }
      }
      return ((hash_element *) NULL);
}

/* ***************************************************************************
 *
 *    Lookup a hash table for an element with key.  
 *      The function returns a pointer to the hash element.
 *    If no element is found, the function returns NULL.
 *
 *      Input:
 *              table -- The hash table to be searched on.
 *              key -- The key to be found.
 *****************************************************************************
 */

hash_element *hash_lookup(hash_table *table, char *key)
{
      return (hash_chain_find(table, &table->buckets[string_hash(table->size, key)], key));
}

/* ***************************************************************
 *
 *    This function first checks if an element with key "key"
 *    exists in the hash table. If so, the function moves the 
 *    element to the front of the LRU list. Otherwise, a new 
 *    hash element corresponding to "value" and "key" is allocated
 *    and inserted into the hash table. The new elements are
 *    always inserted in the LRU order to the LRU list as well.
 *
 *      Input:
 *              table -- The hash table to be inserted in.
 *              value -- The content of the element to be inserted.
 *              key -- The key of the new element to be inserted.
 *
 ****************************************************************
 */

hash_element *hash_insert(hash_table *table, char *value, char *key)
{
      hash_element      *hash_elem;
      ubi_dlNodePtr lru_item;
      ubi_dlList *bucket; 
      size_t string_length;

      /* 
       * If the hash table size has not reached the MAX_HASH_TABLE_SIZE,
       * the hash table may be enlarged if the current hash table is full.
       * If the hash table size has reached the MAX_HASH_TABLE_SIZE, 
       * use LRU to remove the oldest element from the hash table.
       */

      if ((table->num_elements >= table->size) &&  
            (table->num_elements < MAX_HASH_TABLE_SIZE)) {
            if(!enlarge_hash_table(table))
                  return (hash_element *)NULL;
            table->num_elements += 1;
      } else if (table->num_elements >= MAX_HASH_TABLE_SIZE) {
            /* Do an LRU replacement. */
            lru_item = ubi_dlLast(&(table->lru_chain));
            hash_elem = (hash_element *)(((lru_node *)lru_item)->hash_elem);
            bucket = hash_elem->bucket;
            ubi_dlRemThis(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
            ubi_dlRemThis(bucket, (ubi_dlNodePtr)hash_elem);
            SAFE_FREE(hash_elem->value);
            SAFE_FREE(hash_elem);
      }  else  {
            table->num_elements += 1;
      }

      bucket = &table->buckets[string_hash(table->size, key)];

      /* Since we only have 1-byte for the key string, we need to 
       * allocate extra space in the hash_element to store the entire key
       * string.
       */

      string_length = strlen(key);
      if(!(hash_elem = (hash_element *) malloc(sizeof(hash_element) + string_length))) {
            DEBUG(0,("hash_insert: malloc fail !\n"));
            return (hash_element *)NULL;
      }

      safe_strcpy((char *) hash_elem->key, key, string_length);

      hash_elem->value = (char *)value;
      hash_elem->bucket = bucket;
      /* Insert in front of the lru list and the bucket list. */
      ubi_dlAddHead(bucket, hash_elem);
      hash_elem->lru_link.hash_elem = hash_elem;
      ubi_dlAddHead(&(table->lru_chain), &(hash_elem->lru_link.lru_link));

      return(hash_elem);
}

/* **************************************************************************
 *
 *    Remove a hash element from the hash table. The hash element is 
 *    removed from both the LRU list and the hash bucket chain.
 *
 *      Input:
 *              table -- the hash table to be manipulated on.
 *              hash_elem -- the element to be removed.
 **************************************************************************
 */

void hash_remove(hash_table *table, hash_element *hash_elem)
{
      if (hash_elem) { 
            ubi_dlRemove(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
            ubi_dlRemove(hash_elem->bucket, (ubi_dlNodePtr) hash_elem);
            SAFE_FREE(hash_elem->value);
            SAFE_FREE(hash_elem);
            table->num_elements--;
      }
}

/* ******************************************************************
 *    Increase the hash table size if it is too small. 
 *    The hash table size is increased by the HASH_TABLE_INCREMENT
 *    ratio.
 *      Input:
 *              table -- the hash table to be enlarged.
 ******************************************************************
 */

static BOOL enlarge_hash_table(hash_table *table)
{
      hash_element      *hash_elem;
      int size, hash_value;
      ubi_dlList  *buckets;
      ubi_dlList  *old_bucket;
      ubi_dlList  *bucket;
      ubi_dlList  lru_chain;

      buckets = table->buckets;
      lru_chain = table->lru_chain;
      size = table->size;

      /* Reinitialize the hash table. */
      if(!hash_table_init(table, table->size * HASH_TABLE_INCREMENT, table->comp_func))
            return False;

      for (old_bucket = buckets; size > 0; size--, old_bucket++) {
            while (old_bucket->count != 0) {
                  hash_elem = (hash_element *) ubi_dlRemHead(old_bucket);
                  ubi_dlRemove(&lru_chain, &(hash_elem->lru_link.lru_link));
                  hash_value = string_hash(table->size, (char *) hash_elem->key);
                  bucket = &(table->buckets[hash_value]);
                  ubi_dlAddHead(bucket, hash_elem);
                  ubi_dlAddHead(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
                  hash_elem->bucket = bucket;
                  hash_elem->lru_link.hash_elem = hash_elem;
                  table->num_elements++;
            }
      }
      SAFE_FREE(buckets);

      return True;
}

/* **********************************************************************
 *
 *    Remove everything from a hash table and free up the memory it 
 *    occupies. 
 *      Input: 
 *              table -- the hash table to be cleared.
 *
 *************************************************************************
 */

void hash_clear(hash_table *table)
{
      int i;
      ubi_dlList  *bucket = table->buckets;
      hash_element    *hash_elem;
      for (i = 0; i < table->size; bucket++, i++) {
            while (bucket->count != 0) {
                  hash_elem = (hash_element *) ubi_dlRemHead(bucket);
                  SAFE_FREE(hash_elem->value);
                  SAFE_FREE(hash_elem);
            }
      }
      table->size = 0;
      SAFE_FREE(table->buckets);
      table->buckets = NULL;
}

Generated by  Doxygen 1.6.0   Back to index