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
);
31 static unsigned primes
[] =
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
, unsigned 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
;
174 size_t string_length
;
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 string_length
= strlen(key
);
209 if(!(hash_elem
= (hash_element
*) malloc(sizeof(hash_element
) + string_length
))) {
210 DEBUG(0,("hash_insert: malloc fail !\n"));
211 return (hash_element
*)NULL
;
214 safe_strcpy((char *) hash_elem
->key
, key
, string_length
);
216 hash_elem
->value
= (char *)value
;
217 hash_elem
->bucket
= bucket
;
218 /* Insert in front of the lru list and the bucket list. */
219 ubi_dlAddHead(bucket
, hash_elem
);
220 hash_elem
->lru_link
.hash_elem
= hash_elem
;
221 ubi_dlAddHead(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
226 /* **************************************************************************
228 * Remove a hash element from the hash table. The hash element is
229 * removed from both the LRU list and the hash bucket chain.
232 * table -- the hash table to be manipulated on.
233 * hash_elem -- the element to be removed.
234 **************************************************************************
237 void hash_remove(hash_table
*table
, hash_element
*hash_elem
)
240 ubi_dlRemove(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
241 ubi_dlRemove(hash_elem
->bucket
, (ubi_dlNodePtr
) hash_elem
);
242 SAFE_FREE(hash_elem
->value
);
243 SAFE_FREE(hash_elem
);
244 table
->num_elements
--;
248 /* ******************************************************************
249 * Increase the hash table size if it is too small.
250 * The hash table size is increased by the HASH_TABLE_INCREMENT
253 * table -- the hash table to be enlarged.
254 ******************************************************************
257 static BOOL
enlarge_hash_table(hash_table
*table
)
259 hash_element
*hash_elem
;
260 int size
, hash_value
;
262 ubi_dlList
*old_bucket
;
264 ubi_dlList lru_chain
;
266 buckets
= table
->buckets
;
267 lru_chain
= table
->lru_chain
;
270 /* Reinitialize the hash table. */
271 if(!hash_table_init(table
, table
->size
* HASH_TABLE_INCREMENT
, table
->comp_func
))
274 for (old_bucket
= buckets
; size
> 0; size
--, old_bucket
++) {
275 while (old_bucket
->count
!= 0) {
276 hash_elem
= (hash_element
*) ubi_dlRemHead(old_bucket
);
277 ubi_dlRemove(&lru_chain
, &(hash_elem
->lru_link
.lru_link
));
278 hash_value
= string_hash(table
->size
, (char *) hash_elem
->key
);
279 bucket
= &(table
->buckets
[hash_value
]);
280 ubi_dlAddHead(bucket
, hash_elem
);
281 ubi_dlAddHead(&(table
->lru_chain
), &(hash_elem
->lru_link
.lru_link
));
282 hash_elem
->bucket
= bucket
;
283 hash_elem
->lru_link
.hash_elem
= hash_elem
;
284 table
->num_elements
++;
292 /* **********************************************************************
294 * Remove everything from a hash table and free up the memory it
297 * table -- the hash table to be cleared.
299 *************************************************************************
302 void hash_clear(hash_table
*table
)
305 ubi_dlList
*bucket
= table
->buckets
;
306 hash_element
*hash_elem
;
307 for (i
= 0; i
< table
->size
; bucket
++, i
++) {
308 while (bucket
->count
!= 0) {
309 hash_elem
= (hash_element
*) ubi_dlRemHead(bucket
);
310 SAFE_FREE(hash_elem
->value
);
311 SAFE_FREE(hash_elem
);
315 SAFE_FREE(table
->buckets
);
316 table
->buckets
= NULL
;