2 Unix SMB/Netbios implementation.
5 Copyright (C) Ying Chen 2000.
6 Copyright (C) Jeremy Allison 2000.
7 - added some defensive programming.
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.
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.
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.
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.
31 static BOOL
enlarge_hash_table(hash_table
*table
);
33 {17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411};
35 /****************************************************************************
36 * This function initializes the hash table.
37 * This hash function hashes on string keys.
38 * This number of hash buckets is always rounded up to a power of
39 * 2 first, then to a prime number that is large than the power of two.
41 * table -- the hash table pointer.
42 * num_buckets -- the number of buckets to be allocated. This
43 * hash function can dynamically increase its size when the
44 * the hash table size becomes small. There is a MAX hash table
45 * size defined in hash.h.
46 * compare_func -- the function pointer to a comparison function
47 * used by the hash key comparison.
48 ****************************************************************************
51 BOOL
hash_table_init(hash_table
*table
, int num_buckets
, compare_function compare_func
)
56 table
->num_elements
= 0;
58 table
->comp_func
= compare_func
;
59 while (table
->size
< num_buckets
)
61 for (i
= 0; i
< ARRAY_SIZE(primes
); i
++) {
62 if (primes
[i
] > table
->size
) {
63 table
->size
= primes
[i
];
68 DEBUG(5, ("Hash size = %d.\n", table
->size
));
70 if(!(table
->buckets
= (ubi_dlList
*) malloc(sizeof(ubi_dlList
) * table
->size
))) {
71 DEBUG(0,("hash_table_init: malloc fail !\n"));
74 ubi_dlInitList(&(table
->lru_chain
));
75 for (i
=0, bucket
= table
->buckets
; i
< table
->size
; i
++, bucket
++)
76 ubi_dlInitList(bucket
);
82 **************************************************************
83 * Compute a hash value based on a string key value.
84 * Make the string key into an array of int's if possible.
85 * For the last few chars that cannot be int'ed, use char instead.
86 * The function returns the bucket index number for the hashed
88 **************************************************************
91 static int string_hash(int hash_size
, const char *key
)
93 u32 value
; /* Used to compute the hash value. */
94 u32 i
; /* Used to cycle through random values. */
96 for (value
= 0x238F13AF, i
=0; key
[i
]; i
++)
97 value
= (value
+ (key
[i
] << (i
*5 % 24)));
99 return (1103515243 * value
+ 12345) % hash_size
;
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.
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 ***************************************************************************
118 static hash_element
*hash_chain_find(hash_table
*table
, ubi_dlList
*hash_chain
, char *key
)
120 hash_element
*hash_elem
;
121 ubi_dlNodePtr lru_item
;
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
);
133 return ((hash_element
*) NULL
);
136 /* ***************************************************************************
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.
143 * table -- The hash table to be searched on.
144 * key -- The key to be found.
145 *****************************************************************************
148 hash_element
*hash_lookup(hash_table
*table
, char *key
)
150 return (hash_chain_find(table
, &table
->buckets
[string_hash(table
->size
, key
)], key
));
153 /* ***************************************************************
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.
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.
167 ****************************************************************
170 hash_element
*hash_insert(hash_table
*table
, char *value
, char *key
)
172 hash_element
*hash_elem
;
173 ubi_dlNodePtr lru_item
;
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.
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 SAFE_FREE(hash_elem
->value
);
196 SAFE_FREE(hash_elem
);
198 table
->num_elements
+= 1;
201 bucket
= &table
->buckets
[string_hash(table
->size
, key
)];
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
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
;
213 safe_strcpy((char *) hash_elem
->key
, key
, strlen(key
)+1);
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
));
225 /* **************************************************************************
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.
231 * table -- the hash table to be manipulated on.
232 * hash_elem -- the element to be removed.
233 **************************************************************************
236 void hash_remove(hash_table
*table
, hash_element
*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
--;
247 /* ******************************************************************
248 * Increase the hash table size if it is too small.
249 * The hash table size is increased by the HASH_TABLE_INCREMENT
252 * table -- the hash table to be enlarged.
253 ******************************************************************
256 static BOOL
enlarge_hash_table(hash_table
*table
)
258 hash_element
*hash_elem
;
259 int size
, hash_value
;
261 ubi_dlList
*old_bucket
;
263 ubi_dlList lru_chain
;
265 buckets
= table
->buckets
;
266 lru_chain
= table
->lru_chain
;
269 /* Reinitialize the hash table. */
270 if(!hash_table_init(table
, table
->size
* HASH_TABLE_INCREMENT
, table
->comp_func
))
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
++;
291 /* **********************************************************************
293 * Remove everything from a hash table and free up the memory it
296 * table -- the hash table to be cleared.
298 *************************************************************************
301 void hash_clear(hash_table
*table
)
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
);
314 SAFE_FREE(table
->buckets
);
315 table
->buckets
= NULL
;