source3/lib/hash.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    Copyright (C) Ying Chen 2000.
   5    Copyright (C) Jeremy Allison 2000.
   6                  - added some defensive programming.
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 2 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21 */
  22
  23 /*
  24  * NB. We may end up replacing this functionality in a future 2.x
  25  * release to reduce the number of hashing/lookup methods we support. JRA.
  26  */
  27
  28 #include "includes.h"
  29
  30 static BOOL enlarge_hash_table(hash_table *table);
  31 static int primes[] =
  32         {17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411};
  33
  34 /****************************************************************************
  35  *      This function initializes the hash table.
  36  *      This hash function hashes on string keys.
  37  *      This number of hash buckets is always rounded up to a power of
  38  *      2 first, then to a prime number that is large than the power of two.
  39  *      Input:
  40  *              table -- the hash table pointer.
  41  *              num_buckets -- the number of buckets to be allocated. This
  42  *              hash function can dynamically increase its size when the
  43  *              the hash table size becomes small. There is a MAX hash table
  44  *              size defined in hash.h.
  45  *              compare_func -- the function pointer to a comparison function
  46  *              used by the hash key comparison.
  47  ****************************************************************************
  48  */
  49
  50 BOOL hash_table_init(hash_table *table, int num_buckets, compare_function compare_func)
  51 {
  52         int     i;
  53         ubi_dlList      *bucket;
  54
  55         table->num_elements = 0;
  56         table->size = 2;
  57         table->comp_func = compare_func;
  58         while (table->size < num_buckets)
  59                 table->size <<= 1;
  60         for (i = 0; i < ARRAY_SIZE(primes); i++) {
  61                 if (primes[i] > table->size) {
  62                         table->size = primes[i];
  63                         break;
  64                 }
  65         }
  66
  67         DEBUG(5, ("Hash size = %d.\n", table->size));
  68
  69         if(!(table->buckets = (ubi_dlList *) malloc(sizeof(ubi_dlList) * table->size))) {
  70                 DEBUG(0,("hash_table_init: malloc fail !\n"));
  71                 return False;
  72         }
  73         ubi_dlInitList(&(table->lru_chain));
  74         for (i=0, bucket = table->buckets; i < table->size; i++, bucket++)
  75                 ubi_dlInitList(bucket);
  76
  77         return True;
  78 }
  79
  80 /*
  81  **************************************************************
  82  *      Compute a hash value based on a string key value.
  83  *      Make the string key into an array of int's if possible.
  84  *      For the last few chars that cannot be int'ed, use char instead.
  85  *      The function returns the bucket index number for the hashed
  86  *      key.
  87  **************************************************************
  88  */
  89
  90 static int string_hash(int hash_size, const char *key)
  91 {
  92         u32 value;      /* Used to compute the hash value.  */
  93         u32   i;        /* Used to cycle through random values. */
  94
  95         for (value = 0x238F13AF, i=0; key[i]; i++)
  96                 value = (value + (key[i] << (i*5 % 24)));
  97
  98         return (1103515243 * value + 12345) % hash_size;
  99 }
 100
 101
 102 /* *************************************************************************
 103  *      Search the hash table for the entry in the hash chain.
 104  *      The function returns the pointer to the
 105  *      element found in the chain or NULL if none is found.
 106  *      If the element is found, the element is also moved to
 107  *      the head of the LRU list.
 108  *
 109  *      Input:
 110  *              table -- The hash table where the element is stored in.
 111  *              hash_chain -- The pointer to the bucket that stores the
 112  *              element to be found.
 113  *              key -- The hash key to be found.
 114  ***************************************************************************
 115  */
 116
 117 static hash_element *hash_chain_find(hash_table *table, ubi_dlList *hash_chain, char *key)
 118 {
 119         hash_element *hash_elem;
 120         ubi_dlNodePtr lru_item;
 121         int     i = 0;
 122
 123         for (hash_elem = (hash_element *)(ubi_dlFirst(hash_chain)); i < hash_chain->count;
 124                 i++, hash_elem = (hash_element *)(ubi_dlNext(hash_elem))) {
 125                 if ((table->comp_func)(hash_elem->key, key) == 0) {
 126                         /* Move to the head of the lru List. */
 127                         lru_item = ubi_dlRemove(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
 128                         ubi_dlAddHead(&(table->lru_chain), lru_item);
 129                         return(hash_elem);
 130                 }
 131         }
 132         return ((hash_element *) NULL);
 133 }
 134
 135 /* ***************************************************************************
 136  *
 137  *      Lookup a hash table for an element with key.
 138  *      The function returns a pointer to the hash element.
 139  *      If no element is found, the function returns NULL.
 140  *
 141  *      Input:
 142  *              table -- The hash table to be searched on.
 143  *              key -- The key to be found.
 144  *****************************************************************************
 145  */
 146
 147 hash_element *hash_lookup(hash_table *table, char *key)
 148 {
 149         return (hash_chain_find(table, &table->buckets[string_hash(table->size, key)], key));
 150 }
 151
 152 /* ***************************************************************
 153  *
 154  *      This function first checks if an element with key "key"
 155  *      exists in the hash table. If so, the function moves the
 156  *      element to the front of the LRU list. Otherwise, a new
 157  *      hash element corresponding to "value" and "key" is allocated
 158  *      and inserted into the hash table. The new elements are
 159  *      always inserted in the LRU order to the LRU list as well.
 160  *
 161  *      Input:
 162  *              table -- The hash table to be inserted in.
 163  *              value -- The content of the element to be inserted.
 164  *              key -- The key of the new element to be inserted.
 165  *
 166  ****************************************************************
 167  */
 168
 169 hash_element *hash_insert(hash_table *table, char *value, char *key)
 170 {
 171         hash_element    *hash_elem;
 172         ubi_dlNodePtr lru_item;
 173         ubi_dlList *bucket;
 174
 175         /*
 176          * If the hash table size has not reached the MAX_HASH_TABLE_SIZE,
 177          * the hash table may be enlarged if the current hash table is full.
 178          * If the hash table size has reached the MAX_HASH_TABLE_SIZE,
 179          * use LRU to remove the oldest element from the hash table.
 180          */
 181
 182         if ((table->num_elements >= table->size) &&
 183                 (table->num_elements < MAX_HASH_TABLE_SIZE)) {
 184                 if(!enlarge_hash_table(table))
 185                         return (hash_element *)NULL;
 186                 table->num_elements += 1;
 187         } else if (table->num_elements >= MAX_HASH_TABLE_SIZE) {
 188                 /* Do an LRU replacement. */
 189                 lru_item = ubi_dlLast(&(table->lru_chain));
 190                 hash_elem = (hash_element *)(((lru_node *)lru_item)->hash_elem);
 191                 bucket = hash_elem->bucket;
 192                 ubi_dlRemThis(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
 193                 ubi_dlRemThis(bucket, (ubi_dlNodePtr)hash_elem);
 194                 SAFE_FREE(hash_elem->value);
 195                 SAFE_FREE(hash_elem);
 196         }  else  {
 197                 table->num_elements += 1;
 198         }
 199
 200         bucket = &table->buckets[string_hash(table->size, key)];
 201
 202         /* Since we only have 1-byte for the key string, we need to
 203          * allocate extra space in the hash_element to store the entire key
 204          * string.
 205          */
 206
 207         if(!(hash_elem = (hash_element *) malloc(sizeof(hash_element) + strlen(key)))) {
 208                 DEBUG(0,("hash_insert: malloc fail !\n"));
 209                 return (hash_element *)NULL;
 210         }
 211
 212         safe_strcpy((char *) hash_elem->key, key, strlen(key)+1);
 213
 214         hash_elem->value = (char *)value;
 215         hash_elem->bucket = bucket;
 216         /* Insert in front of the lru list and the bucket list. */
 217         ubi_dlAddHead(bucket, hash_elem);
 218         hash_elem->lru_link.hash_elem = hash_elem;
 219         ubi_dlAddHead(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
 220
 221         return(hash_elem);
 222 }
 223
 224 /* **************************************************************************
 225  *
 226  *      Remove a hash element from the hash table. The hash element is
 227  *      removed from both the LRU list and the hash bucket chain.
 228  *
 229  *      Input:
 230  *              table -- the hash table to be manipulated on.
 231  *              hash_elem -- the element to be removed.
 232  **************************************************************************
 233  */
 234
 235 void hash_remove(hash_table *table, hash_element *hash_elem)
 236 {
 237         if (hash_elem) {
 238                 ubi_dlRemove(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
 239                 ubi_dlRemove(hash_elem->bucket, (ubi_dlNodePtr) hash_elem);
 240                 SAFE_FREE(hash_elem->value);
 241                 SAFE_FREE(hash_elem);
 242                 table->num_elements--;
 243         }
 244 }
 245
 246 /* ******************************************************************
 247  *      Increase the hash table size if it is too small.
 248  *      The hash table size is increased by the HASH_TABLE_INCREMENT
 249  *      ratio.
 250  *      Input:
 251  *              table -- the hash table to be enlarged.
 252  ******************************************************************
 253  */
 254
 255 static BOOL enlarge_hash_table(hash_table *table)
 256 {
 257         hash_element    *hash_elem;
 258         int size, hash_value;
 259         ubi_dlList      *buckets;
 260         ubi_dlList      *old_bucket;
 261         ubi_dlList      *bucket;
 262         ubi_dlList  lru_chain;
 263
 264         buckets = table->buckets;
 265         lru_chain = table->lru_chain;
 266         size = table->size;
 267
 268         /* Reinitialize the hash table. */
 269         if(!hash_table_init(table, table->size * HASH_TABLE_INCREMENT, table->comp_func))
 270                 return False;
 271
 272         for (old_bucket = buckets; size > 0; size--, old_bucket++) {
 273                 while (old_bucket->count != 0) {
 274                         hash_elem = (hash_element *) ubi_dlRemHead(old_bucket);
 275                         ubi_dlRemove(&lru_chain, &(hash_elem->lru_link.lru_link));
 276                         hash_value = string_hash(table->size, (char *) hash_elem->key);
 277                         bucket = &(table->buckets[hash_value]);
 278                         ubi_dlAddHead(bucket, hash_elem);
 279                         ubi_dlAddHead(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
 280                         hash_elem->bucket = bucket;
 281                         hash_elem->lru_link.hash_elem = hash_elem;
 282                         table->num_elements++;
 283                 }
 284         }
 285         SAFE_FREE(buckets);
 286
 287         return True;
 288 }
 289
 290 /* **********************************************************************
 291  *
 292  *      Remove everything from a hash table and free up the memory it
 293  *      occupies.
 294  *      Input:
 295  *              table -- the hash table to be cleared.
 296  *
 297  *************************************************************************
 298  */
 299
 300 void hash_clear(hash_table *table)
 301 {
 302         int i;
 303         ubi_dlList      *bucket = table->buckets;
 304         hash_element    *hash_elem;
 305         for (i = 0; i < table->size; bucket++, i++) {
 306                 while (bucket->count != 0) {
 307                         hash_elem = (hash_element *) ubi_dlRemHead(bucket);
 308                         SAFE_FREE(hash_elem->value);
 309                         SAFE_FREE(hash_elem);
 310                 }
 311         }
 312         table->size = 0;
 313         SAFE_FREE(table->buckets);
 314         table->buckets = NULL;
 315 }