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 extern int DEBUGLEVEL
;
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};
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.
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 ****************************************************************************
55 BOOL
hash_table_init(hash_table
*table
, int num_buckets
, compare_function compare_func
)
60 table
->num_elements
= 0;
62 table
->comp_func
= compare_func
;
63 while (table
->size
< num_buckets
)
65 for (i
= 0; i
< NUM_PRIMES
; i
++) {
66 if (primes
[i
] > table
->size
) {
67 table
->size
= primes
[i
];
72 DEBUG(5, ("Hash size = %d.\n", table
->size
));
74 if(!(table
->buckets
= (ubi_dlList
*) malloc(sizeof(ubi_dlList
) * table
->size
))) {
75 DEBUG(0,("hash_table_init: malloc fail !\n"));
78 ubi_dlInitList(&(table
->lru_chain
));
79 for (i
=0, bucket
= table
->buckets
; i
< table
->size
; i
++, bucket
++)
80 ubi_dlInitList(bucket
);
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
92 **************************************************************
95 int string_hash(int hash_size
, const char *key
)
100 return(((j
>=0)?j
:(-j
)) % 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 free((char*)(hash_elem
->value
));
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
);
242 free((char *)(hash_elem
->value
));
244 free((char *) hash_elem
);
245 table
->num_elements
--;
249 /* ******************************************************************
250 * Increase the hash table size if it is too small.
251 * The hash table size is increased by the HASH_TABLE_INCREMENT
254 * table -- the hash table to be enlarged.
255 ******************************************************************
258 static BOOL
enlarge_hash_table(hash_table
*table
)
260 hash_element
*hash_elem
;
261 int size
, hash_value
;
263 ubi_dlList
*old_bucket
;
265 ubi_dlList lru_chain
;
267 buckets
= table
->buckets
;
268 lru_chain
= table
->lru_chain
;
271 /* Reinitialize the hash table. */
272 if(!hash_table_init(table
, table
->size
* HASH_TABLE_INCREMENT
, table
->comp_func
))
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
++;
289 free((char *) buckets
);
294 /* **********************************************************************
296 * Remove everything from a hash table and free up the memory it
299 * table -- the hash table to be cleared.
301 *************************************************************************
304 void hash_clear(hash_table
*table
)
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
);
313 free((char *)(hash_elem
->value
));
315 free((char *)hash_elem
);
319 free((char *) table
->buckets
);