1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.] */
56
57#include <openssl/lhash.h>
58
59#include <assert.h>
60#include <limits.h>
61#include <string.h>
62
63#include <openssl/mem.h>
64
65#include "../internal.h"
66
67
68// kMinNumBuckets is the minimum size of the buckets array in an |_LHASH|.
69static const size_t kMinNumBuckets = 16;
70
71// kMaxAverageChainLength contains the maximum, average chain length. When the
72// average chain length exceeds this value, the hash table will be resized.
73static const size_t kMaxAverageChainLength = 2;
74static const size_t kMinAverageChainLength = 1;
75
76struct lhash_st {
77 // num_items contains the total number of items in the hash table.
78 size_t num_items;
79 // buckets is an array of |num_buckets| pointers. Each points to the head of
80 // a chain of LHASH_ITEM objects that have the same hash value, mod
81 // |num_buckets|.
82 LHASH_ITEM **buckets;
83 // num_buckets contains the length of |buckets|. This value is always >=
84 // kMinNumBuckets.
85 size_t num_buckets;
86 // callback_depth contains the current depth of |lh_doall| or |lh_doall_arg|
87 // calls. If non-zero then this suppresses resizing of the |buckets| array,
88 // which would otherwise disrupt the iteration.
89 unsigned callback_depth;
90
91 lhash_cmp_func comp;
92 lhash_hash_func hash;
93};
94
95_LHASH *lh_new(lhash_hash_func hash, lhash_cmp_func comp) {
96 _LHASH *ret = OPENSSL_malloc(sizeof(_LHASH));
97 if (ret == NULL) {
98 return NULL;
99 }
100 OPENSSL_memset(ret, 0, sizeof(_LHASH));
101
102 ret->num_buckets = kMinNumBuckets;
103 ret->buckets = OPENSSL_malloc(sizeof(LHASH_ITEM *) * ret->num_buckets);
104 if (ret->buckets == NULL) {
105 OPENSSL_free(ret);
106 return NULL;
107 }
108 OPENSSL_memset(ret->buckets, 0, sizeof(LHASH_ITEM *) * ret->num_buckets);
109
110 ret->comp = comp;
111 ret->hash = hash;
112 return ret;
113}
114
115void lh_free(_LHASH *lh) {
116 if (lh == NULL) {
117 return;
118 }
119
120 for (size_t i = 0; i < lh->num_buckets; i++) {
121 LHASH_ITEM *next;
122 for (LHASH_ITEM *n = lh->buckets[i]; n != NULL; n = next) {
123 next = n->next;
124 OPENSSL_free(n);
125 }
126 }
127
128 OPENSSL_free(lh->buckets);
129 OPENSSL_free(lh);
130}
131
132size_t lh_num_items(const _LHASH *lh) { return lh->num_items; }
133
134// get_next_ptr_and_hash returns a pointer to the pointer that points to the
135// item equal to |data|. In other words, it searches for an item equal to |data|
136// and, if it's at the start of a chain, then it returns a pointer to an
137// element of |lh->buckets|, otherwise it returns a pointer to the |next|
138// element of the previous item in the chain. If an element equal to |data| is
139// not found, it returns a pointer that points to a NULL pointer. If |out_hash|
140// is not NULL, then it also puts the hash value of |data| in |*out_hash|.
141static LHASH_ITEM **get_next_ptr_and_hash(const _LHASH *lh, uint32_t *out_hash,
142 const void *data,
143 lhash_hash_func_helper call_hash_func,
144 lhash_cmp_func_helper call_cmp_func) {
145 const uint32_t hash = call_hash_func(lh->hash, data);
146 if (out_hash != NULL) {
147 *out_hash = hash;
148 }
149
150 LHASH_ITEM **ret = &lh->buckets[hash % lh->num_buckets];
151 for (LHASH_ITEM *cur = *ret; cur != NULL; cur = *ret) {
152 if (call_cmp_func(lh->comp, cur->data, data) == 0) {
153 break;
154 }
155 ret = &cur->next;
156 }
157
158 return ret;
159}
160
161// get_next_ptr_by_key behaves like |get_next_ptr_and_hash| but takes a key
162// which may be a different type from the values stored in |lh|.
163static LHASH_ITEM **get_next_ptr_by_key(const _LHASH *lh, const void *key,
164 uint32_t key_hash,
165 int (*cmp_key)(const void *key,
166 const void *value)) {
167 LHASH_ITEM **ret = &lh->buckets[key_hash % lh->num_buckets];
168 for (LHASH_ITEM *cur = *ret; cur != NULL; cur = *ret) {
169 if (cmp_key(key, cur->data) == 0) {
170 break;
171 }
172 ret = &cur->next;
173 }
174
175 return ret;
176}
177
178void *lh_retrieve(const _LHASH *lh, const void *data,
179 lhash_hash_func_helper call_hash_func,
180 lhash_cmp_func_helper call_cmp_func) {
181 LHASH_ITEM **next_ptr =
182 get_next_ptr_and_hash(lh, NULL, data, call_hash_func, call_cmp_func);
183 return *next_ptr == NULL ? NULL : (*next_ptr)->data;
184}
185
186void *lh_retrieve_key(const _LHASH *lh, const void *key, uint32_t key_hash,
187 int (*cmp_key)(const void *key, const void *value)) {
188 LHASH_ITEM **next_ptr = get_next_ptr_by_key(lh, key, key_hash, cmp_key);
189 return *next_ptr == NULL ? NULL : (*next_ptr)->data;
190}
191
192// lh_rebucket allocates a new array of |new_num_buckets| pointers and
193// redistributes the existing items into it before making it |lh->buckets| and
194// freeing the old array.
195static void lh_rebucket(_LHASH *lh, const size_t new_num_buckets) {
196 LHASH_ITEM **new_buckets, *cur, *next;
197 size_t i, alloc_size;
198
199 alloc_size = sizeof(LHASH_ITEM *) * new_num_buckets;
200 if (alloc_size / sizeof(LHASH_ITEM*) != new_num_buckets) {
201 return;
202 }
203
204 new_buckets = OPENSSL_malloc(alloc_size);
205 if (new_buckets == NULL) {
206 return;
207 }
208 OPENSSL_memset(new_buckets, 0, alloc_size);
209
210 for (i = 0; i < lh->num_buckets; i++) {
211 for (cur = lh->buckets[i]; cur != NULL; cur = next) {
212 const size_t new_bucket = cur->hash % new_num_buckets;
213 next = cur->next;
214 cur->next = new_buckets[new_bucket];
215 new_buckets[new_bucket] = cur;
216 }
217 }
218
219 OPENSSL_free(lh->buckets);
220
221 lh->num_buckets = new_num_buckets;
222 lh->buckets = new_buckets;
223}
224
225// lh_maybe_resize resizes the |buckets| array if needed.
226static void lh_maybe_resize(_LHASH *lh) {
227 size_t avg_chain_length;
228
229 if (lh->callback_depth > 0) {
230 // Don't resize the hash if we are currently iterating over it.
231 return;
232 }
233
234 assert(lh->num_buckets >= kMinNumBuckets);
235 avg_chain_length = lh->num_items / lh->num_buckets;
236
237 if (avg_chain_length > kMaxAverageChainLength) {
238 const size_t new_num_buckets = lh->num_buckets * 2;
239
240 if (new_num_buckets > lh->num_buckets) {
241 lh_rebucket(lh, new_num_buckets);
242 }
243 } else if (avg_chain_length < kMinAverageChainLength &&
244 lh->num_buckets > kMinNumBuckets) {
245 size_t new_num_buckets = lh->num_buckets / 2;
246
247 if (new_num_buckets < kMinNumBuckets) {
248 new_num_buckets = kMinNumBuckets;
249 }
250
251 lh_rebucket(lh, new_num_buckets);
252 }
253}
254
255int lh_insert(_LHASH *lh, void **old_data, void *data,
256 lhash_hash_func_helper call_hash_func,
257 lhash_cmp_func_helper call_cmp_func) {
258 uint32_t hash;
259 LHASH_ITEM **next_ptr, *item;
260
261 *old_data = NULL;
262 next_ptr =
263 get_next_ptr_and_hash(lh, &hash, data, call_hash_func, call_cmp_func);
264
265
266 if (*next_ptr != NULL) {
267 // An element equal to |data| already exists in the hash table. It will be
268 // replaced.
269 *old_data = (*next_ptr)->data;
270 (*next_ptr)->data = data;
271 return 1;
272 }
273
274 // An element equal to |data| doesn't exist in the hash table yet.
275 item = OPENSSL_malloc(sizeof(LHASH_ITEM));
276 if (item == NULL) {
277 return 0;
278 }
279
280 item->data = data;
281 item->hash = hash;
282 item->next = NULL;
283 *next_ptr = item;
284 lh->num_items++;
285 lh_maybe_resize(lh);
286
287 return 1;
288}
289
290void *lh_delete(_LHASH *lh, const void *data,
291 lhash_hash_func_helper call_hash_func,
292 lhash_cmp_func_helper call_cmp_func) {
293 LHASH_ITEM **next_ptr, *item, *ret;
294
295 next_ptr =
296 get_next_ptr_and_hash(lh, NULL, data, call_hash_func, call_cmp_func);
297
298 if (*next_ptr == NULL) {
299 // No such element.
300 return NULL;
301 }
302
303 item = *next_ptr;
304 *next_ptr = item->next;
305 ret = item->data;
306 OPENSSL_free(item);
307
308 lh->num_items--;
309 lh_maybe_resize(lh);
310
311 return ret;
312}
313
314void lh_doall_arg(_LHASH *lh, void (*func)(void *, void *), void *arg) {
315 if (lh == NULL) {
316 return;
317 }
318
319 if (lh->callback_depth < UINT_MAX) {
320 // |callback_depth| is a saturating counter.
321 lh->callback_depth++;
322 }
323
324 for (size_t i = 0; i < lh->num_buckets; i++) {
325 LHASH_ITEM *next;
326 for (LHASH_ITEM *cur = lh->buckets[i]; cur != NULL; cur = next) {
327 next = cur->next;
328 func(cur->data, arg);
329 }
330 }
331
332 if (lh->callback_depth < UINT_MAX) {
333 lh->callback_depth--;
334 }
335
336 // The callback may have added or removed elements and the non-zero value of
337 // |callback_depth| will have suppressed any resizing. Thus any needed
338 // resizing is done here.
339 lh_maybe_resize(lh);
340}
341
342uint32_t lh_strhash(const char *c) {
343 if (c == NULL) {
344 return 0;
345 }
346
347 return OPENSSL_hash32(c, strlen(c));
348}
349