/src/boringssl/crypto/lhash/lhash.c
Line | Count | Source (jump to first uncovered line) |
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 | | #include "../internal.h" |
67 | | |
68 | | |
69 | | // kMinNumBuckets is the minimum size of the buckets array in an |_LHASH|. |
70 | | static const size_t kMinNumBuckets = 16; |
71 | | |
72 | | // kMaxAverageChainLength contains the maximum, average chain length. When the |
73 | | // average chain length exceeds this value, the hash table will be resized. |
74 | | static const size_t kMaxAverageChainLength = 2; |
75 | | static const size_t kMinAverageChainLength = 1; |
76 | | |
77 | | // lhash_item_st is an element of a hash chain. It points to the opaque data |
78 | | // for this element and to the next item in the chain. The linked-list is NULL |
79 | | // terminated. |
80 | | typedef struct lhash_item_st { |
81 | | void *data; |
82 | | struct lhash_item_st *next; |
83 | | // hash contains the cached, hash value of |data|. |
84 | | uint32_t hash; |
85 | | } LHASH_ITEM; |
86 | | |
87 | | struct lhash_st { |
88 | | // num_items contains the total number of items in the hash table. |
89 | | size_t num_items; |
90 | | // buckets is an array of |num_buckets| pointers. Each points to the head of |
91 | | // a chain of LHASH_ITEM objects that have the same hash value, mod |
92 | | // |num_buckets|. |
93 | | LHASH_ITEM **buckets; |
94 | | // num_buckets contains the length of |buckets|. This value is always >= |
95 | | // kMinNumBuckets. |
96 | | size_t num_buckets; |
97 | | // callback_depth contains the current depth of |lh_doall| or |lh_doall_arg| |
98 | | // calls. If non-zero then this suppresses resizing of the |buckets| array, |
99 | | // which would otherwise disrupt the iteration. |
100 | | unsigned callback_depth; |
101 | | |
102 | | lhash_cmp_func comp; |
103 | | lhash_hash_func hash; |
104 | | }; |
105 | | |
106 | 0 | _LHASH *OPENSSL_lh_new(lhash_hash_func hash, lhash_cmp_func comp) { |
107 | 0 | _LHASH *ret = OPENSSL_zalloc(sizeof(_LHASH)); |
108 | 0 | if (ret == NULL) { |
109 | 0 | return NULL; |
110 | 0 | } |
111 | | |
112 | 0 | ret->num_buckets = kMinNumBuckets; |
113 | 0 | ret->buckets = OPENSSL_calloc(ret->num_buckets, sizeof(LHASH_ITEM *)); |
114 | 0 | if (ret->buckets == NULL) { |
115 | 0 | OPENSSL_free(ret); |
116 | 0 | return NULL; |
117 | 0 | } |
118 | | |
119 | 0 | ret->comp = comp; |
120 | 0 | ret->hash = hash; |
121 | 0 | return ret; |
122 | 0 | } |
123 | | |
124 | 0 | void OPENSSL_lh_free(_LHASH *lh) { |
125 | 0 | if (lh == NULL) { |
126 | 0 | return; |
127 | 0 | } |
128 | | |
129 | 0 | for (size_t i = 0; i < lh->num_buckets; i++) { |
130 | 0 | LHASH_ITEM *next; |
131 | 0 | for (LHASH_ITEM *n = lh->buckets[i]; n != NULL; n = next) { |
132 | 0 | next = n->next; |
133 | 0 | OPENSSL_free(n); |
134 | 0 | } |
135 | 0 | } |
136 | |
|
137 | 0 | OPENSSL_free(lh->buckets); |
138 | 0 | OPENSSL_free(lh); |
139 | 0 | } |
140 | | |
141 | 0 | size_t OPENSSL_lh_num_items(const _LHASH *lh) { return lh->num_items; } |
142 | | |
143 | | // get_next_ptr_and_hash returns a pointer to the pointer that points to the |
144 | | // item equal to |data|. In other words, it searches for an item equal to |data| |
145 | | // and, if it's at the start of a chain, then it returns a pointer to an |
146 | | // element of |lh->buckets|, otherwise it returns a pointer to the |next| |
147 | | // element of the previous item in the chain. If an element equal to |data| is |
148 | | // not found, it returns a pointer that points to a NULL pointer. If |out_hash| |
149 | | // is not NULL, then it also puts the hash value of |data| in |*out_hash|. |
150 | | static LHASH_ITEM **get_next_ptr_and_hash(const _LHASH *lh, uint32_t *out_hash, |
151 | | const void *data, |
152 | | lhash_hash_func_helper call_hash_func, |
153 | 0 | lhash_cmp_func_helper call_cmp_func) { |
154 | 0 | const uint32_t hash = call_hash_func(lh->hash, data); |
155 | 0 | if (out_hash != NULL) { |
156 | 0 | *out_hash = hash; |
157 | 0 | } |
158 | |
|
159 | 0 | LHASH_ITEM **ret = &lh->buckets[hash % lh->num_buckets]; |
160 | 0 | for (LHASH_ITEM *cur = *ret; cur != NULL; cur = *ret) { |
161 | 0 | if (call_cmp_func(lh->comp, cur->data, data) == 0) { |
162 | 0 | break; |
163 | 0 | } |
164 | 0 | ret = &cur->next; |
165 | 0 | } |
166 | |
|
167 | 0 | return ret; |
168 | 0 | } |
169 | | |
170 | | // get_next_ptr_by_key behaves like |get_next_ptr_and_hash| but takes a key |
171 | | // which may be a different type from the values stored in |lh|. |
172 | | static LHASH_ITEM **get_next_ptr_by_key(const _LHASH *lh, const void *key, |
173 | | uint32_t key_hash, |
174 | | int (*cmp_key)(const void *key, |
175 | 0 | const void *value)) { |
176 | 0 | LHASH_ITEM **ret = &lh->buckets[key_hash % lh->num_buckets]; |
177 | 0 | for (LHASH_ITEM *cur = *ret; cur != NULL; cur = *ret) { |
178 | 0 | if (cmp_key(key, cur->data) == 0) { |
179 | 0 | break; |
180 | 0 | } |
181 | 0 | ret = &cur->next; |
182 | 0 | } |
183 | |
|
184 | 0 | return ret; |
185 | 0 | } |
186 | | |
187 | | void *OPENSSL_lh_retrieve(const _LHASH *lh, const void *data, |
188 | | lhash_hash_func_helper call_hash_func, |
189 | 0 | lhash_cmp_func_helper call_cmp_func) { |
190 | 0 | LHASH_ITEM **next_ptr = |
191 | 0 | get_next_ptr_and_hash(lh, NULL, data, call_hash_func, call_cmp_func); |
192 | 0 | return *next_ptr == NULL ? NULL : (*next_ptr)->data; |
193 | 0 | } |
194 | | |
195 | | void *OPENSSL_lh_retrieve_key(const _LHASH *lh, const void *key, |
196 | | uint32_t key_hash, |
197 | | int (*cmp_key)(const void *key, |
198 | 0 | const void *value)) { |
199 | 0 | LHASH_ITEM **next_ptr = get_next_ptr_by_key(lh, key, key_hash, cmp_key); |
200 | 0 | return *next_ptr == NULL ? NULL : (*next_ptr)->data; |
201 | 0 | } |
202 | | |
203 | | // lh_rebucket allocates a new array of |new_num_buckets| pointers and |
204 | | // redistributes the existing items into it before making it |lh->buckets| and |
205 | | // freeing the old array. |
206 | 0 | static void lh_rebucket(_LHASH *lh, const size_t new_num_buckets) { |
207 | 0 | LHASH_ITEM **new_buckets, *cur, *next; |
208 | 0 | size_t i, alloc_size; |
209 | |
|
210 | 0 | alloc_size = sizeof(LHASH_ITEM *) * new_num_buckets; |
211 | 0 | if (alloc_size / sizeof(LHASH_ITEM*) != new_num_buckets) { |
212 | 0 | return; |
213 | 0 | } |
214 | | |
215 | 0 | new_buckets = OPENSSL_zalloc(alloc_size); |
216 | 0 | if (new_buckets == NULL) { |
217 | 0 | return; |
218 | 0 | } |
219 | | |
220 | 0 | for (i = 0; i < lh->num_buckets; i++) { |
221 | 0 | for (cur = lh->buckets[i]; cur != NULL; cur = next) { |
222 | 0 | const size_t new_bucket = cur->hash % new_num_buckets; |
223 | 0 | next = cur->next; |
224 | 0 | cur->next = new_buckets[new_bucket]; |
225 | 0 | new_buckets[new_bucket] = cur; |
226 | 0 | } |
227 | 0 | } |
228 | |
|
229 | 0 | OPENSSL_free(lh->buckets); |
230 | |
|
231 | 0 | lh->num_buckets = new_num_buckets; |
232 | 0 | lh->buckets = new_buckets; |
233 | 0 | } |
234 | | |
235 | | // lh_maybe_resize resizes the |buckets| array if needed. |
236 | 0 | static void lh_maybe_resize(_LHASH *lh) { |
237 | 0 | size_t avg_chain_length; |
238 | |
|
239 | 0 | if (lh->callback_depth > 0) { |
240 | | // Don't resize the hash if we are currently iterating over it. |
241 | 0 | return; |
242 | 0 | } |
243 | | |
244 | 0 | assert(lh->num_buckets >= kMinNumBuckets); |
245 | 0 | avg_chain_length = lh->num_items / lh->num_buckets; |
246 | |
|
247 | 0 | if (avg_chain_length > kMaxAverageChainLength) { |
248 | 0 | const size_t new_num_buckets = lh->num_buckets * 2; |
249 | |
|
250 | 0 | if (new_num_buckets > lh->num_buckets) { |
251 | 0 | lh_rebucket(lh, new_num_buckets); |
252 | 0 | } |
253 | 0 | } else if (avg_chain_length < kMinAverageChainLength && |
254 | 0 | lh->num_buckets > kMinNumBuckets) { |
255 | 0 | size_t new_num_buckets = lh->num_buckets / 2; |
256 | |
|
257 | 0 | if (new_num_buckets < kMinNumBuckets) { |
258 | 0 | new_num_buckets = kMinNumBuckets; |
259 | 0 | } |
260 | |
|
261 | 0 | lh_rebucket(lh, new_num_buckets); |
262 | 0 | } |
263 | 0 | } |
264 | | |
265 | | int OPENSSL_lh_insert(_LHASH *lh, void **old_data, void *data, |
266 | | lhash_hash_func_helper call_hash_func, |
267 | 0 | lhash_cmp_func_helper call_cmp_func) { |
268 | 0 | uint32_t hash; |
269 | 0 | LHASH_ITEM **next_ptr, *item; |
270 | |
|
271 | 0 | *old_data = NULL; |
272 | 0 | next_ptr = |
273 | 0 | get_next_ptr_and_hash(lh, &hash, data, call_hash_func, call_cmp_func); |
274 | | |
275 | |
|
276 | 0 | if (*next_ptr != NULL) { |
277 | | // An element equal to |data| already exists in the hash table. It will be |
278 | | // replaced. |
279 | 0 | *old_data = (*next_ptr)->data; |
280 | 0 | (*next_ptr)->data = data; |
281 | 0 | return 1; |
282 | 0 | } |
283 | | |
284 | | // An element equal to |data| doesn't exist in the hash table yet. |
285 | 0 | item = OPENSSL_malloc(sizeof(LHASH_ITEM)); |
286 | 0 | if (item == NULL) { |
287 | 0 | return 0; |
288 | 0 | } |
289 | | |
290 | 0 | item->data = data; |
291 | 0 | item->hash = hash; |
292 | 0 | item->next = NULL; |
293 | 0 | *next_ptr = item; |
294 | 0 | lh->num_items++; |
295 | 0 | lh_maybe_resize(lh); |
296 | |
|
297 | 0 | return 1; |
298 | 0 | } |
299 | | |
300 | | void *OPENSSL_lh_delete(_LHASH *lh, const void *data, |
301 | | lhash_hash_func_helper call_hash_func, |
302 | 0 | lhash_cmp_func_helper call_cmp_func) { |
303 | 0 | LHASH_ITEM **next_ptr, *item, *ret; |
304 | |
|
305 | 0 | next_ptr = |
306 | 0 | get_next_ptr_and_hash(lh, NULL, data, call_hash_func, call_cmp_func); |
307 | |
|
308 | 0 | if (*next_ptr == NULL) { |
309 | | // No such element. |
310 | 0 | return NULL; |
311 | 0 | } |
312 | | |
313 | 0 | item = *next_ptr; |
314 | 0 | *next_ptr = item->next; |
315 | 0 | ret = item->data; |
316 | 0 | OPENSSL_free(item); |
317 | |
|
318 | 0 | lh->num_items--; |
319 | 0 | lh_maybe_resize(lh); |
320 | |
|
321 | 0 | return ret; |
322 | 0 | } |
323 | | |
324 | 0 | void OPENSSL_lh_doall_arg(_LHASH *lh, void (*func)(void *, void *), void *arg) { |
325 | 0 | if (lh == NULL) { |
326 | 0 | return; |
327 | 0 | } |
328 | | |
329 | 0 | if (lh->callback_depth < UINT_MAX) { |
330 | | // |callback_depth| is a saturating counter. |
331 | 0 | lh->callback_depth++; |
332 | 0 | } |
333 | |
|
334 | 0 | for (size_t i = 0; i < lh->num_buckets; i++) { |
335 | 0 | LHASH_ITEM *next; |
336 | 0 | for (LHASH_ITEM *cur = lh->buckets[i]; cur != NULL; cur = next) { |
337 | 0 | next = cur->next; |
338 | 0 | func(cur->data, arg); |
339 | 0 | } |
340 | 0 | } |
341 | |
|
342 | 0 | if (lh->callback_depth < UINT_MAX) { |
343 | 0 | lh->callback_depth--; |
344 | 0 | } |
345 | | |
346 | | // The callback may have added or removed elements and the non-zero value of |
347 | | // |callback_depth| will have suppressed any resizing. Thus any needed |
348 | | // resizing is done here. |
349 | 0 | lh_maybe_resize(lh); |
350 | 0 | } |