2 Unix SMB/CIFS implementation.
4 Copyright (C) Ying Chen 2000.
5 Copyright (C) Jeremy Allison 2000.
6 - added some defensive programming.
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.
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.
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.
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.
30 static BOOL
enlarge_hash_table(hash_table
*table
);
32 {17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411};
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.
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 ****************************************************************************
50 BOOL
hash_table_init(hash_table
*table
, int num_buckets
, compare_function compare_func
)
55 table
->num_elements
= 0;
57 table
->comp_func
= compare_func
;
58 while (table
->size
< num_buckets
)
60 for (i
= 0; i
< ARRAY_SIZE(primes
); i
++) {
61 if (primes
[i
] > table
->size
) {
62 table
->size
= primes
[i
];
67 DEBUG(5, ("Hash size = %d.\n", table
->size
));
69 if(!(table
->buckets
= (ubi_dlList
*) malloc(sizeof(ubi_dlList
) * table
->size
))) {
70 DEBUG(0,("hash_table_init: malloc fail !\n"));
73 ubi_dlInitList(&(table
->lru_chain
));
74 for (i
=0, bucket
= table
->buckets
; i
< table
->size
; i
++, bucket
++)
75 ubi_dlInitList(bucket
);
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
87 **************************************************************
90 static int string_hash(int hash_size
, const char *key
)
92 u32 value
; /* Used to compute the hash value. */
93 u32 i
; /* Used to cycle through random values. */
95 for (value
= 0x238F13AF, i
=0; key
[i
]; i
++)
96 value
= (value
+ (key
[i
] << (i
*5 % 24)));
98 return (1103515243 * value
+ 12345) % hash_size
;
102 /* *************************************************************************
103 * Search the hash table for the entry in the hash chain.
104 * The function returns the pointer to the
105 * element found in the chain or NULL if none is found.
106 * If the element is found, the element is also moved to
107 * the head of the LRU list.
110 * table -- The hash table where the element is stored in.
111 * hash_chain -- The pointer to the bucket that stores the
112 * element to be found.
113 * key -- The hash key to be found.
114 ***************************************************************************
117 static hash_element
*hash_chain_find(hash_table
*table
, ubi_dlList
*hash_chain
, char *key
)
119 hash_element
*hash_elem
;
120 ubi_dlNodePtr lru_item
;
123 for (hash_elem
= (hash_element
*)(ubi_dlFirst(hash_chain
)); i
< hash_chain
->count
;
124 i
++, hash_elem
= (hash_element
*)(ubi_dlNext(hash_elem
))) {
125 if ((table
->comp_func
)(hash_elem
->key
, key
) == 0) {
126 /* Move to the head of the lru List. */
127 lru_item
= ubi_dlRemove(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
128 ubi_dlAddHead(&(table
->lru_chain
), lru_item
);
132 return ((hash_element
*) NULL
);
135 /* ***************************************************************************
137 * Lookup a hash table for an element with key.
138 * The function returns a pointer to the hash element.
139 * If no element is found, the function returns NULL.
142 * table -- The hash table to be searched on.
143 * key -- The key to be found.
144 *****************************************************************************
147 hash_element
*hash_lookup(hash_table
*table
, char *key
)
149 return (hash_chain_find(table
, &table
->buckets
[string_hash(table
->size
, key
)], key
));
152 /* ***************************************************************
154 * This function first checks if an element with key "key"
155 * exists in the hash table. If so, the function moves the
156 * element to the front of the LRU list. Otherwise, a new
157 * hash element corresponding to "value" and "key" is allocated
158 * and inserted into the hash table. The new elements are
159 * always inserted in the LRU order to the LRU list as well.
162 * table -- The hash table to be inserted in.
163 * value -- The content of the element to be inserted.
164 * key -- The key of the new element to be inserted.
166 ****************************************************************
169 hash_element
*hash_insert(hash_table
*table
, char *value
, char *key
)
171 hash_element
*hash_elem
;
172 ubi_dlNodePtr lru_item
;
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.
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
);
197 table
->num_elements
+= 1;
200 bucket
= &table
->buckets
[string_hash(table
->size
, key
)];
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
207 if(!(hash_elem
= (hash_element
*) malloc(sizeof(hash_element
) + strlen(key
)))) {
208 DEBUG(0,("hash_insert: malloc fail !\n"));
209 return (hash_element
*)NULL
;
212 safe_strcpy((char *) hash_elem
->key
, key
, strlen(key
)+1);
214 hash_elem
->value
= (char *)value
;
215 hash_elem
->bucket
= bucket
;
216 /* Insert in front of the lru list and the bucket list. */
217 ubi_dlAddHead(bucket
, hash_elem
);
218 hash_elem
->lru_link
.hash_elem
= hash_elem
;
219 ubi_dlAddHead(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
224 /* **************************************************************************
226 * Remove a hash element from the hash table. The hash element is
227 * removed from both the LRU list and the hash bucket chain.
230 * table -- the hash table to be manipulated on.
231 * hash_elem -- the element to be removed.
232 **************************************************************************
235 void hash_remove(hash_table
*table
, hash_element
*hash_elem
)
238 ubi_dlRemove(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
239 ubi_dlRemove(hash_elem
->bucket
, (ubi_dlNodePtr
) hash_elem
);
240 SAFE_FREE(hash_elem
->value
);
241 SAFE_FREE(hash_elem
);
242 table
->num_elements
--;
246 /* ******************************************************************
247 * Increase the hash table size if it is too small.
248 * The hash table size is increased by the HASH_TABLE_INCREMENT
251 * table -- the hash table to be enlarged.
252 ******************************************************************
255 static BOOL
enlarge_hash_table(hash_table
*table
)
257 hash_element
*hash_elem
;
258 int size
, hash_value
;
260 ubi_dlList
*old_bucket
;
262 ubi_dlList lru_chain
;
264 buckets
= table
->buckets
;
265 lru_chain
= table
->lru_chain
;
268 /* Reinitialize the hash table. */
269 if(!hash_table_init(table
, table
->size
* HASH_TABLE_INCREMENT
, table
->comp_func
))
272 for (old_bucket
= buckets
; size
> 0; size
--, old_bucket
++) {
273 while (old_bucket
->count
!= 0) {
274 hash_elem
= (hash_element
*) ubi_dlRemHead(old_bucket
);
275 ubi_dlRemove(&lru_chain
, &(hash_elem
->lru_link
.lru_link
));
276 hash_value
= string_hash(table
->size
, (char *) hash_elem
->key
);
277 bucket
= &(table
->buckets
[hash_value
]);
278 ubi_dlAddHead(bucket
, hash_elem
);
279 ubi_dlAddHead(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
280 hash_elem
->bucket
= bucket
;
281 hash_elem
->lru_link
.hash_elem
= hash_elem
;
282 table
->num_elements
++;
290 /* **********************************************************************
292 * Remove everything from a hash table and free up the memory it
295 * table -- the hash table to be cleared.
297 *************************************************************************
300 void hash_clear(hash_table
*table
)
303 ubi_dlList
*bucket
= table
->buckets
;
304 hash_element
*hash_elem
;
305 for (i
= 0; i
< table
->size
; bucket
++, i
++) {
306 while (bucket
->count
!= 0) {
307 hash_elem
= (hash_element
*) ubi_dlRemHead(bucket
);
308 SAFE_FREE(hash_elem
->value
);
309 SAFE_FREE(hash_elem
);
313 SAFE_FREE(table
->buckets
);
314 table
->buckets
= NULL
;