import HEAD into svn+ssh://svn.samba.org/home/svn/samba/trunk
[metze/old/v3-2-winbind-ndr.git] / source / 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 unsigned 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, unsigned num_buckets, compare_function compare_func)
51 {
52         unsigned        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  *      JRA. Use a djb-algorithm hash for speed.
88  **************************************************************
89  */
90
91 static int string_hash(int hash_size, const char *key)
92 {
93         u32 n = 0;
94         const char *p;
95         for (p = key; *p != '\0'; p++) {
96                 n = ((n << 5) + n) ^ (u32)(*p);
97         }
98         return (n % hash_size);
99 }
100
101 /* *************************************************************************
102  *      Search the hash table for the entry in the hash chain.
103  *      The function returns the pointer to the 
104  *      element found in the chain or NULL if none is found. 
105  *      If the element is found, the element is also moved to 
106  *      the head of the LRU list.
107  *
108  *      Input:
109  *              table -- The hash table where the element is stored in.
110  *              hash_chain -- The pointer to the bucket that stores the 
111  *              element to be found.
112  *              key -- The hash key to be found. 
113  ***************************************************************************
114  */
115
116 static hash_element *hash_chain_find(hash_table *table, ubi_dlList *hash_chain, char *key)
117 {
118         hash_element *hash_elem;
119         ubi_dlNodePtr lru_item;
120         unsigned int    i = 0;
121
122         for (hash_elem = (hash_element *)(ubi_dlFirst(hash_chain)); i < hash_chain->count; 
123                 i++, hash_elem = (hash_element *)(ubi_dlNext(hash_elem))) {
124                 if ((table->comp_func)(hash_elem->key, key) == 0) {
125                         /* Move to the head of the lru List. */
126                         lru_item = ubi_dlRemove(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
127                         ubi_dlAddHead(&(table->lru_chain), lru_item);
128                         return(hash_elem);
129                 }
130         }
131         return ((hash_element *) NULL);
132 }
133
134 /* ***************************************************************************
135  *
136  *      Lookup a hash table for an element with key.  
137  *      The function returns a pointer to the hash element.
138  *      If no element is found, the function returns NULL.
139  *
140  *      Input:
141  *              table -- The hash table to be searched on.
142  *              key -- The key to be found.
143  *****************************************************************************
144  */
145
146 hash_element *hash_lookup(hash_table *table, char *key)
147 {
148         return (hash_chain_find(table, &table->buckets[string_hash(table->size, key)], key));
149 }
150
151 /* ***************************************************************
152  *
153  *      This function first checks if an element with key "key"
154  *      exists in the hash table. If so, the function moves the 
155  *      element to the front of the LRU list. Otherwise, a new 
156  *      hash element corresponding to "value" and "key" is allocated
157  *      and inserted into the hash table. The new elements are
158  *      always inserted in the LRU order to the LRU list as well.
159  *
160  *      Input:
161  *              table -- The hash table to be inserted in.
162  *              value -- The content of the element to be inserted.
163  *              key -- The key of the new element to be inserted.
164  *
165  ****************************************************************
166  */
167
168 hash_element *hash_insert(hash_table *table, char *value, char *key)
169 {
170         hash_element    *hash_elem;
171         ubi_dlNodePtr lru_item;
172         ubi_dlList *bucket; 
173         size_t string_length;
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         string_length = strlen(key);
208         if(!(hash_elem = (hash_element *) malloc(sizeof(hash_element) + string_length))) {
209                 DEBUG(0,("hash_insert: malloc fail !\n"));
210                 return (hash_element *)NULL;
211         }
212
213         safe_strcpy((char *) hash_elem->key, key, string_length);
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                 SAFE_FREE(hash_elem->value);
242                 SAFE_FREE(hash_elem);
243                 table->num_elements--;
244         }
245 }
246
247 /* ******************************************************************
248  *      Increase the hash table size if it is too small. 
249  *      The hash table size is increased by the HASH_TABLE_INCREMENT
250  *      ratio.
251  *      Input:
252  *              table -- the hash table to be enlarged.
253  ******************************************************************
254  */
255
256 static BOOL enlarge_hash_table(hash_table *table)
257 {
258         hash_element    *hash_elem;
259         int size, hash_value;
260         ubi_dlList      *buckets;
261         ubi_dlList      *old_bucket;
262         ubi_dlList      *bucket;
263         ubi_dlList  lru_chain;
264
265         buckets = table->buckets;
266         lru_chain = table->lru_chain;
267         size = table->size;
268
269         /* Reinitialize the hash table. */
270         if(!hash_table_init(table, table->size * HASH_TABLE_INCREMENT, table->comp_func))
271                 return False;
272
273         for (old_bucket = buckets; size > 0; size--, old_bucket++) {
274                 while (old_bucket->count != 0) {
275                         hash_elem = (hash_element *) ubi_dlRemHead(old_bucket);
276                         ubi_dlRemove(&lru_chain, &(hash_elem->lru_link.lru_link));
277                         hash_value = string_hash(table->size, (char *) hash_elem->key);
278                         bucket = &(table->buckets[hash_value]);
279                         ubi_dlAddHead(bucket, hash_elem);
280                         ubi_dlAddHead(&(table->lru_chain), &(hash_elem->lru_link.lru_link));
281                         hash_elem->bucket = bucket;
282                         hash_elem->lru_link.hash_elem = hash_elem;
283                         table->num_elements++;
284                 }
285         }
286         SAFE_FREE(buckets);
287
288         return True;
289 }
290
291 /* **********************************************************************
292  *
293  *      Remove everything from a hash table and free up the memory it 
294  *      occupies. 
295  *      Input: 
296  *              table -- the hash table to be cleared.
297  *
298  *************************************************************************
299  */
300
301 void hash_clear(hash_table *table)
302 {
303         unsigned int i;
304         ubi_dlList      *bucket = table->buckets;
305         hash_element    *hash_elem;
306         for (i = 0; i < table->size; bucket++, i++) {
307                 while (bucket->count != 0) {
308                         hash_elem = (hash_element *) ubi_dlRemHead(bucket);
309                         SAFE_FREE(hash_elem->value);
310                         SAFE_FREE(hash_elem);
311                 }
312         }
313         table->size = 0;
314         SAFE_FREE(table->buckets);
315         table->buckets = NULL;
316 }