/* 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; /* * 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. */ if(!(hash_elem = (hash_element *) malloc(sizeof(hash_element) + strlen(key)))) { DEBUG(0,("hash_insert: malloc fail !\n")); return (hash_element *)NULL; } safe_strcpy((char *) hash_elem->key, key, strlen(key)+1); 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; }