source3/lib/hash.c

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