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