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 /* Code for dynamic hash table routines
60 * Author - Eric Young v 2.0
61 *
62 * 2.2 eay - added #include "crypto.h" so the memory leak checking code is
63 * present. eay 18-Jun-98
64 *
65 * 2.1 eay - Added an 'error in last operation' flag. eay 6-May-98
66 *
67 * 2.0 eay - Fixed a bug that occurred when using lh_delete
68 * from inside lh_doall(). As entries were deleted,
69 * the 'table' was 'contract()ed', making some entries
70 * jump from the end of the table to the start, there by
71 * skipping the lh_doall() processing. eay - 4/12/95
72 *
73 * 1.9 eay - Fixed a memory leak in lh_free, the LHASH_NODEs
74 * were not being free()ed. 21/11/95
75 *
76 * 1.8 eay - Put the stats routines into a separate file, lh_stats.c
77 * 19/09/95
78 *
79 * 1.7 eay - Removed the fputs() for realloc failures - the code
80 * should silently tolerate them. I have also fixed things
81 * lint complained about 04/05/95
82 *
83 * 1.6 eay - Fixed an invalid pointers in contract/expand 27/07/92
84 *
85 * 1.5 eay - Fixed a misuse of realloc in expand 02/03/1992
86 *
87 * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
88 *
89 * 1.3 eay - Fixed a few lint problems 19/3/1991
90 *
91 * 1.2 eay - Fixed lh_doall problem 13/3/1991
92 *
93 * 1.1 eay - Added lh_doall
94 *
95 * 1.0 eay - First version
96 */
97 #include <stdio.h>
98 #include <string.h>
99 #include <stdlib.h>
100 #include <openssl/crypto.h>
101 #include <openssl/lhash.h>
102
103 const char lh_version[]="lhash" OPENSSL_VERSION_PTEXT;
104
105 #undef MIN_NODES
106 #define MIN_NODES 16
107 #define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */
108 #define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */
109
110 static void expand(_LHASH *lh);
111 static void contract(_LHASH *lh);
112 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash);
113
114 _LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
115 {
116 _LHASH *ret;
117 int i;
118
119 if ((ret=OPENSSL_malloc(sizeof(_LHASH))) == NULL)
120 goto err0;
121 if ((ret->b=OPENSSL_malloc(sizeof(LHASH_NODE *)*MIN_NODES)) == NULL)
122 goto err1;
123 for (i=0; i<MIN_NODES; i++)
124 ret->b[i]=NULL;
125 ret->comp=((c == NULL)?(LHASH_COMP_FN_TYPE)strcmp:c);
126 ret->hash=((h == NULL)?(LHASH_HASH_FN_TYPE)lh_strhash:h);
127 ret->num_nodes=MIN_NODES/2;
128 ret->num_alloc_nodes=MIN_NODES;
129 ret->p=0;
130 ret->pmax=MIN_NODES/2;
131 ret->up_load=UP_LOAD;
132 ret->down_load=DOWN_LOAD;
133 ret->num_items=0;
134
135 ret->num_expands=0;
136 ret->num_expand_reallocs=0;
137 ret->num_contracts=0;
138 ret->num_contract_reallocs=0;
139 ret->num_hash_calls=0;
140 ret->num_comp_calls=0;
141 ret->num_insert=0;
142 ret->num_replace=0;
143 ret->num_delete=0;
144 ret->num_no_delete=0;
145 ret->num_retrieve=0;
146 ret->num_retrieve_miss=0;
147 ret->num_hash_comps=0;
148
149 ret->error=0;
150 return(ret);
151 err1:
152 OPENSSL_free(ret);
153 err0:
154 return(NULL);
155 }
156
157 void lh_free(_LHASH *lh)
158 {
159 unsigned int i;
160 LHASH_NODE *n,*nn;
161
162 if (lh == NULL)
163 return;
164
165 for (i=0; i<lh->num_nodes; i++)
166 {
167 n=lh->b[i];
168 while (n != NULL)
169 {
170 nn=n->next;
171 OPENSSL_free(n);
172 n=nn;
173 }
174 }
175 OPENSSL_free(lh->b);
176 OPENSSL_free(lh);
177 }
178
179 void *lh_insert(_LHASH *lh, void *data)
180 {
181 unsigned long hash;
182 LHASH_NODE *nn,**rn;
183 void *ret;
184
185 lh->error=0;
186 if (lh->up_load <= (lh->num_items*LH_LOAD_MULT/lh->num_nodes))
187 expand(lh);
188
189 rn=getrn(lh,data,&hash);
190
191 if (*rn == NULL)
192 {
193 if ((nn=(LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL)
194 {
195 lh->error++;
196 return(NULL);
197 }
198 nn->data=data;
199 nn->next=NULL;
200 #ifndef OPENSSL_NO_HASH_COMP
201 nn->hash=hash;
202 #endif
203 *rn=nn;
204 ret=NULL;
205 lh->num_insert++;
206 lh->num_items++;
207 }
208 else /* replace same key */
209 {
210 ret= (*rn)->data;
211 (*rn)->data=data;
212 lh->num_replace++;
213 }
214 return(ret);
215 }
216
217 void *lh_delete(_LHASH *lh, const void *data)
218 {
219 unsigned long hash;
220 LHASH_NODE *nn,**rn;
221 void *ret;
222
223 lh->error=0;
224 rn=getrn(lh,data,&hash);
225
226 if (*rn == NULL)
227 {
228 lh->num_no_delete++;
229 return(NULL);
230 }
231 else
232 {
233 nn= *rn;
234 *rn=nn->next;
235 ret=nn->data;
236 OPENSSL_free(nn);
237 lh->num_delete++;
238 }
239
240 lh->num_items--;
241 if ((lh->num_nodes > MIN_NODES) &&
242 (lh->down_load >= (lh->num_items*LH_LOAD_MULT/lh->num_nodes)))
243 contract(lh);
244
245 return(ret);
246 }
247
248 void *lh_retrieve(_LHASH *lh, const void *data)
249 {
250 unsigned long hash;
251 LHASH_NODE **rn;
252 void *ret;
253
254 lh->error=0;
255 rn=getrn(lh,data,&hash);
256
257 if (*rn == NULL)
258 {
259 lh->num_retrieve_miss++;
260 return(NULL);
261 }
262 else
263 {
264 ret= (*rn)->data;
265 lh->num_retrieve++;
266 }
267 return(ret);
268 }
269
270 static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
271 LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
272 {
273 int i;
274 LHASH_NODE *a,*n;
275
276 if (lh == NULL)
277 return;
278
279 /* reverse the order so we search from 'top to bottom'
280 * We were having memory leaks otherwise */
281 for (i=lh->num_nodes-1; i>=0; i--)
282 {
283 a=lh->b[i];
284 while (a != NULL)
285 {
286 /* 28/05/91 - eay - n added so items can be deleted
287 * via lh_doall */
288 /* 22/05/08 - ben - eh? since a is not passed,
289 * this should not be needed */
290 n=a->next;
291 if(use_arg)
292 func_arg(a->data,arg);
293 else
294 func(a->data);
295 a=n;
296 }
297 }
298 }
299
300 void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
301 {
302 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
303 }
304
305 void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
306 {
307 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
308 }
309
310 static void expand(_LHASH *lh)
311 {
312 LHASH_NODE **n,**n1,**n2,*np;
313 unsigned int p,i,j;
314 unsigned long hash,nni;
315
316 lh->num_nodes++;
317 lh->num_expands++;
318 p=(int)lh->p++;
319 n1= &(lh->b[p]);
320 n2= &(lh->b[p+(int)lh->pmax]);
321 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
322 nni=lh->num_alloc_nodes;
323
324 for (np= *n1; np != NULL; )
325 {
326 #ifndef OPENSSL_NO_HASH_COMP
327 hash=np->hash;
328 #else
329 hash=lh->hash(np->data);
330 lh->num_hash_calls++;
331 #endif
332 if ((hash%nni) != p)
333 { /* move it */
334 *n1= (*n1)->next;
335 np->next= *n2;
336 *n2=np;
337 }
338 else
339 n1= &((*n1)->next);
340 np= *n1;
341 }
342
343 if ((lh->p) >= lh->pmax)
344 {
345 j=(int)lh->num_alloc_nodes*2;
346 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
347 (int)(sizeof(LHASH_NODE *)*j));
348 if (n == NULL)
349 {
350 /* fputs("realloc error in lhash",stderr); */
351 lh->error++;
352 lh->p=0;
353 return;
354 }
355 /* else */
356 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
357 n[i]=NULL; /* 02/03/92 eay */
358 lh->pmax=lh->num_alloc_nodes;
359 lh->num_alloc_nodes=j;
360 lh->num_expand_reallocs++;
361 lh->p=0;
362 lh->b=n;
363 }
364 }
365
366 static void contract(_LHASH *lh)
367 {
368 LHASH_NODE **n,*n1,*np;
369
370 np=lh->b[lh->p+lh->pmax-1];
371 lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */
372 if (lh->p == 0)
373 {
374 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
375 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax));
376 if (n == NULL)
377 {
378 /* fputs("realloc error in lhash",stderr); */
379 lh->error++;
380 return;
381 }
382 lh->num_contract_reallocs++;
383 lh->num_alloc_nodes/=2;
384 lh->pmax/=2;
385 lh->p=lh->pmax-1;
386 lh->b=n;
387 }
388 else
389 lh->p--;
390
391 lh->num_nodes--;
392 lh->num_contracts++;
393
394 n1=lh->b[(int)lh->p];
395 if (n1 == NULL)
396 lh->b[(int)lh->p]=np;
397 else
398 {
399 while (n1->next != NULL)
400 n1=n1->next;
401 n1->next=np;
402 }
403 }
404
405 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash)
406 {
407 LHASH_NODE **ret,*n1;
408 unsigned long hash,nn;
409 LHASH_COMP_FN_TYPE cf;
410
411 hash=(*(lh->hash))(data);
412 lh->num_hash_calls++;
413 *rhash=hash;
414
415 nn=hash%lh->pmax;
416 if (nn < lh->p)
417 nn=hash%lh->num_alloc_nodes;
418
419 cf=lh->comp;
420 ret= &(lh->b[(int)nn]);
421 for (n1= *ret; n1 != NULL; n1=n1->next)
422 {
423 #ifndef OPENSSL_NO_HASH_COMP
424 lh->num_hash_comps++;
425 if (n1->hash != hash)
426 {
427 ret= &(n1->next);
428 continue;
429 }
430 #endif
431 lh->num_comp_calls++;
432 if(cf(n1->data,data) == 0)
433 break;
434 ret= &(n1->next);
435 }
436 return(ret);
437 }
438
439 /* The following hash seems to work very well on normal text strings
440 * no collisions on /usr/dict/words and it distributes on %2^n quite
441 * well, not as good as MD5, but still good.
442 */
443 unsigned long lh_strhash(const char *c)
444 {
445 unsigned long ret=0;
446 long n;
447 unsigned long v;
448 int r;
449
450 if ((c == NULL) || (*c == '\0'))
451 return(ret);
452 /*
453 unsigned char b[16];
454 MD5(c,strlen(c),b);
455 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
456 */
457
458 n=0x100;
459 while (*c)
460 {
461 v=n|(*c);
462 n+=0x100;
463 r= (int)((v>>2)^v)&0x0f;
464 ret=(ret<<r)|(ret>>(32-r));
465 ret&=0xFFFFFFFFL;
466 ret^=v*v;
467 c++;
468 }
469 return((ret>>16)^ret);
470 }
471
472 unsigned long lh_num_items(const _LHASH *lh)
473 {
474 return lh ? lh->num_items : 0;
475 }