Line data Source code
1 : /* crypto/lhash/lhash.c */
2 : /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 : * All rights reserved.
4 : *
5 : * This package is an SSL implementation written
6 : * by Eric Young (eay@cryptsoft.com).
7 : * The implementation was written so as to conform with Netscapes SSL.
8 : *
9 : * This library is free for commercial and non-commercial use as long as
10 : * the following conditions are aheared to. The following conditions
11 : * apply to all code found in this distribution, be it the RC4, RSA,
12 : * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 : * included with this distribution is covered by the same copyright terms
14 : * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 : *
16 : * Copyright remains Eric Young's, and as such any Copyright notices in
17 : * the code are not to be removed.
18 : * If this package is used in a product, Eric Young should be given attribution
19 : * as the author of the parts of the library used.
20 : * This can be in the form of a textual message at program startup or
21 : * in documentation (online or textual) provided with the package.
22 : *
23 : * Redistribution and use in source and binary forms, with or without
24 : * modification, are permitted provided that the following conditions
25 : * are met:
26 : * 1. Redistributions of source code must retain the copyright
27 : * notice, this list of conditions and the following disclaimer.
28 : * 2. Redistributions in binary form must reproduce the above copyright
29 : * notice, this list of conditions and the following disclaimer in the
30 : * documentation and/or other materials provided with the distribution.
31 : * 3. All advertising materials mentioning features or use of this software
32 : * must display the following acknowledgement:
33 : * "This product includes cryptographic software written by
34 : * Eric Young (eay@cryptsoft.com)"
35 : * The word 'cryptographic' can be left out if the rouines from the library
36 : * being used are not cryptographic related :-).
37 : * 4. If you include any Windows specific code (or a derivative thereof) from
38 : * the apps directory (application code) you must include an acknowledgement:
39 : * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 : *
41 : * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 : * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 : * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 : * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 : * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 : * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 : * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 : * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 : * SUCH DAMAGE.
52 : *
53 : * The licence and distribution terms for any publically available version or
54 : * derivative of this code cannot be changed. i.e. this code cannot simply be
55 : * copied and put under another distribution licence
56 : * [including the GNU Public Licence.]
57 : */
58 :
59 : /*-
60 : * Code for dynamic hash table routines
61 : * Author - Eric Young v 2.0
62 : *
63 : * 2.2 eay - added #include "crypto.h" so the memory leak checking code is
64 : * present. eay 18-Jun-98
65 : *
66 : * 2.1 eay - Added an 'error in last operation' flag. eay 6-May-98
67 : *
68 : * 2.0 eay - Fixed a bug that occurred when using lh_delete
69 : * from inside lh_doall(). As entries were deleted,
70 : * the 'table' was 'contract()ed', making some entries
71 : * jump from the end of the table to the start, there by
72 : * skipping the lh_doall() processing. eay - 4/12/95
73 : *
74 : * 1.9 eay - Fixed a memory leak in lh_free, the LHASH_NODEs
75 : * were not being free()ed. 21/11/95
76 : *
77 : * 1.8 eay - Put the stats routines into a separate file, lh_stats.c
78 : * 19/09/95
79 : *
80 : * 1.7 eay - Removed the fputs() for realloc failures - the code
81 : * should silently tolerate them. I have also fixed things
82 : * lint complained about 04/05/95
83 : *
84 : * 1.6 eay - Fixed an invalid pointers in contract/expand 27/07/92
85 : *
86 : * 1.5 eay - Fixed a misuse of realloc in expand 02/03/1992
87 : *
88 : * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
89 : *
90 : * 1.3 eay - Fixed a few lint problems 19/3/1991
91 : *
92 : * 1.2 eay - Fixed lh_doall problem 13/3/1991
93 : *
94 : * 1.1 eay - Added lh_doall
95 : *
96 : * 1.0 eay - First version
97 : */
98 : #include <stdio.h>
99 : #include <string.h>
100 : #include <stdlib.h>
101 : #include <openssl/crypto.h>
102 : #include <openssl/lhash.h>
103 :
104 : const char lh_version[] = "lhash" OPENSSL_VERSION_PTEXT;
105 :
106 : #undef MIN_NODES
107 : #define MIN_NODES 16
108 : #define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */
109 : #define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */
110 :
111 : static void expand(_LHASH *lh);
112 : static void contract(_LHASH *lh);
113 : static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash);
114 :
115 1360 : _LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
116 : {
117 : _LHASH *ret;
118 : int i;
119 :
120 1360 : if ((ret = OPENSSL_malloc(sizeof(_LHASH))) == NULL)
121 : goto err0;
122 1360 : if ((ret->b = OPENSSL_malloc(sizeof(LHASH_NODE *) * MIN_NODES)) == NULL)
123 : goto err1;
124 21760 : for (i = 0; i < MIN_NODES; i++)
125 21760 : ret->b[i] = NULL;
126 1360 : ret->comp = ((c == NULL) ? (LHASH_COMP_FN_TYPE)strcmp : c);
127 1360 : ret->hash = ((h == NULL) ? (LHASH_HASH_FN_TYPE)lh_strhash : h);
128 1360 : ret->num_nodes = MIN_NODES / 2;
129 1360 : ret->num_alloc_nodes = MIN_NODES;
130 1360 : ret->p = 0;
131 1360 : ret->pmax = MIN_NODES / 2;
132 1360 : ret->up_load = UP_LOAD;
133 1360 : ret->down_load = DOWN_LOAD;
134 1360 : ret->num_items = 0;
135 :
136 1360 : ret->num_expands = 0;
137 1360 : ret->num_expand_reallocs = 0;
138 1360 : ret->num_contracts = 0;
139 1360 : ret->num_contract_reallocs = 0;
140 1360 : ret->num_hash_calls = 0;
141 1360 : ret->num_comp_calls = 0;
142 1360 : ret->num_insert = 0;
143 1360 : ret->num_replace = 0;
144 1360 : ret->num_delete = 0;
145 1360 : ret->num_no_delete = 0;
146 1360 : ret->num_retrieve = 0;
147 1360 : ret->num_retrieve_miss = 0;
148 1360 : ret->num_hash_comps = 0;
149 :
150 1360 : ret->error = 0;
151 1360 : return (ret);
152 : err1:
153 0 : OPENSSL_free(ret);
154 : err0:
155 : return (NULL);
156 : }
157 :
158 872 : void lh_free(_LHASH *lh)
159 : {
160 : unsigned int i;
161 : LHASH_NODE *n, *nn;
162 :
163 872 : if (lh == NULL)
164 872 : return;
165 :
166 6976 : for (i = 0; i < lh->num_nodes; i++) {
167 6976 : n = lh->b[i];
168 13952 : while (n != NULL) {
169 0 : nn = n->next;
170 0 : OPENSSL_free(n);
171 : n = nn;
172 : }
173 : }
174 872 : OPENSSL_free(lh->b);
175 872 : OPENSSL_free(lh);
176 : }
177 :
178 1727036 : void *lh_insert(_LHASH *lh, void *data)
179 : {
180 : unsigned long hash;
181 : LHASH_NODE *nn, **rn;
182 : void *ret;
183 :
184 1727036 : lh->error = 0;
185 1727036 : if (lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))
186 175700 : expand(lh);
187 :
188 1727036 : rn = getrn(lh, data, &hash);
189 :
190 1727036 : if (*rn == NULL) {
191 356227 : if ((nn = (LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL) {
192 0 : lh->error++;
193 0 : return (NULL);
194 : }
195 356227 : nn->data = data;
196 356227 : nn->next = NULL;
197 : #ifndef OPENSSL_NO_HASH_COMP
198 356227 : nn->hash = hash;
199 : #endif
200 356227 : *rn = nn;
201 : ret = NULL;
202 356227 : lh->num_insert++;
203 356227 : lh->num_items++;
204 : } else { /* replace same key */
205 :
206 1370809 : ret = (*rn)->data;
207 1370809 : (*rn)->data = data;
208 1370809 : lh->num_replace++;
209 : }
210 1727036 : return (ret);
211 : }
212 :
213 0 : void *lh_delete(_LHASH *lh, const void *data)
214 : {
215 : unsigned long hash;
216 : LHASH_NODE *nn, **rn;
217 : void *ret;
218 :
219 0 : lh->error = 0;
220 0 : rn = getrn(lh, data, &hash);
221 :
222 0 : if (*rn == NULL) {
223 0 : lh->num_no_delete++;
224 0 : return (NULL);
225 : } else {
226 : nn = *rn;
227 0 : *rn = nn->next;
228 0 : ret = nn->data;
229 0 : OPENSSL_free(nn);
230 0 : lh->num_delete++;
231 : }
232 :
233 0 : lh->num_items--;
234 0 : if ((lh->num_nodes > MIN_NODES) &&
235 0 : (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
236 0 : contract(lh);
237 :
238 0 : return (ret);
239 : }
240 :
241 59704 : void *lh_retrieve(_LHASH *lh, const void *data)
242 : {
243 : unsigned long hash;
244 : LHASH_NODE **rn;
245 : void *ret;
246 :
247 59704 : lh->error = 0;
248 59704 : rn = getrn(lh, data, &hash);
249 :
250 59704 : if (*rn == NULL) {
251 5207 : lh->num_retrieve_miss++;
252 5207 : return (NULL);
253 : } else {
254 54497 : ret = (*rn)->data;
255 54497 : lh->num_retrieve++;
256 : }
257 54497 : return (ret);
258 : }
259 :
260 872 : static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
261 : LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
262 : {
263 : int i;
264 : LHASH_NODE *a, *n;
265 :
266 872 : if (lh == NULL)
267 872 : return;
268 :
269 : /*
270 : * reverse the order so we search from 'top to bottom' We were having
271 : * memory leaks otherwise
272 : */
273 7848 : for (i = lh->num_nodes - 1; i >= 0; i--) {
274 6976 : a = lh->b[i];
275 13952 : while (a != NULL) {
276 : /*
277 : * 28/05/91 - eay - n added so items can be deleted via lh_doall
278 : */
279 : /*
280 : * 22/05/08 - ben - eh? since a is not passed, this should not be
281 : * needed
282 : */
283 0 : n = a->next;
284 0 : if (use_arg)
285 0 : func_arg(a->data, arg);
286 : else
287 0 : func(a->data);
288 : a = n;
289 : }
290 : }
291 : }
292 :
293 0 : void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
294 : {
295 0 : doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
296 0 : }
297 :
298 872 : void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
299 : {
300 872 : doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
301 872 : }
302 :
303 175700 : static void expand(_LHASH *lh)
304 : {
305 : LHASH_NODE **n, **n1, **n2, *np;
306 : unsigned int p, i, j;
307 : unsigned long hash, nni;
308 :
309 175700 : lh->num_nodes++;
310 175700 : lh->num_expands++;
311 175700 : p = (int)lh->p++;
312 175700 : n1 = &(lh->b[p]);
313 175700 : n2 = &(lh->b[p + (int)lh->pmax]);
314 175700 : *n2 = NULL; /* 27/07/92 - eay - undefined pointer bug */
315 175700 : nni = lh->num_alloc_nodes;
316 :
317 1009051 : for (np = *n1; np != NULL;) {
318 : #ifndef OPENSSL_NO_HASH_COMP
319 657651 : hash = np->hash;
320 : #else
321 : hash = lh->hash(np->data);
322 : lh->num_hash_calls++;
323 : #endif
324 657651 : if ((hash % nni) != p) { /* move it */
325 64372 : *n1 = (*n1)->next;
326 64372 : np->next = *n2;
327 64372 : *n2 = np;
328 : } else
329 593279 : n1 = &((*n1)->next);
330 657651 : np = *n1;
331 : }
332 :
333 175700 : if ((lh->p) >= lh->pmax) {
334 1332 : j = (int)lh->num_alloc_nodes * 2;
335 1332 : n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
336 : (int)(sizeof(LHASH_NODE *) * j));
337 1332 : if (n == NULL) {
338 : /* fputs("realloc error in lhash",stderr); */
339 0 : lh->error++;
340 0 : lh->p = 0;
341 175700 : return;
342 : }
343 : /* else */
344 276260 : for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */
345 274928 : n[i] = NULL; /* 02/03/92 eay */
346 1332 : lh->pmax = lh->num_alloc_nodes;
347 1332 : lh->num_alloc_nodes = j;
348 1332 : lh->num_expand_reallocs++;
349 1332 : lh->p = 0;
350 1332 : lh->b = n;
351 : }
352 : }
353 :
354 0 : static void contract(_LHASH *lh)
355 : {
356 : LHASH_NODE **n, *n1, *np;
357 :
358 0 : np = lh->b[lh->p + lh->pmax - 1];
359 0 : lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
360 0 : if (lh->p == 0) {
361 0 : n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
362 : (unsigned int)(sizeof(LHASH_NODE *)
363 : * lh->pmax));
364 0 : if (n == NULL) {
365 : /* fputs("realloc error in lhash",stderr); */
366 0 : lh->error++;
367 0 : return;
368 : }
369 0 : lh->num_contract_reallocs++;
370 0 : lh->num_alloc_nodes /= 2;
371 0 : lh->pmax /= 2;
372 0 : lh->p = lh->pmax - 1;
373 0 : lh->b = n;
374 : } else
375 0 : lh->p--;
376 :
377 0 : lh->num_nodes--;
378 0 : lh->num_contracts++;
379 :
380 0 : n1 = lh->b[(int)lh->p];
381 0 : if (n1 == NULL)
382 0 : lh->b[(int)lh->p] = np;
383 : else {
384 0 : while (n1->next != NULL)
385 : n1 = n1->next;
386 0 : n1->next = np;
387 : }
388 : }
389 :
390 1786740 : static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash)
391 : {
392 : LHASH_NODE **ret, *n1;
393 : unsigned long hash, nn;
394 : LHASH_COMP_FN_TYPE cf;
395 :
396 1786740 : hash = (*(lh->hash)) (data);
397 1786740 : lh->num_hash_calls++;
398 1786740 : *rhash = hash;
399 :
400 1786740 : nn = hash % lh->pmax;
401 1786740 : if (nn < lh->p)
402 1001674 : nn = hash % lh->num_alloc_nodes;
403 :
404 1786740 : cf = lh->comp;
405 1786740 : ret = &(lh->b[(int)nn]);
406 4211037 : for (n1 = *ret; n1 != NULL; n1 = n1->next) {
407 : #ifndef OPENSSL_NO_HASH_COMP
408 3849603 : lh->num_hash_comps++;
409 3849603 : if (n1->hash != hash) {
410 2331006 : ret = &(n1->next);
411 2331006 : continue;
412 : }
413 : #endif
414 1518597 : lh->num_comp_calls++;
415 1518597 : if (cf(n1->data, data) == 0)
416 : break;
417 93291 : ret = &(n1->next);
418 : }
419 1786740 : return (ret);
420 : }
421 :
422 : /*
423 : * The following hash seems to work very well on normal text strings no
424 : * collisions on /usr/dict/words and it distributes on %2^n quite well, not
425 : * as good as MD5, but still good.
426 : */
427 49404 : unsigned long lh_strhash(const char *c)
428 : {
429 : unsigned long ret = 0;
430 : long n;
431 : unsigned long v;
432 : int r;
433 :
434 49404 : if ((c == NULL) || (*c == '\0'))
435 : return (ret);
436 : /*-
437 : unsigned char b[16];
438 : MD5(c,strlen(c),b);
439 : return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
440 : */
441 :
442 : n = 0x100;
443 527168 : while (*c) {
444 477764 : v = n | (*c);
445 477764 : n += 0x100;
446 477764 : r = (int)((v >> 2) ^ v) & 0x0f;
447 477764 : ret = (ret << r) | (ret >> (32 - r));
448 477764 : ret &= 0xFFFFFFFFL;
449 477764 : ret ^= v * v;
450 477764 : c++;
451 : }
452 49404 : return ((ret >> 16) ^ ret);
453 : }
454 :
455 0 : unsigned long lh_num_items(const _LHASH *lh)
456 : {
457 0 : return lh ? lh->num_items : 0;
458 : }
|
