lhash.c revision 221304ee937bc0910948a8be1320cb8cc4eb6d36
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 103const 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 110static void expand(_LHASH *lh); 111static void contract(_LHASH *lh); 112static 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); 151err1: 152 OPENSSL_free(ret); 153err0: 154 return(NULL); 155 } 156 157void 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 179void *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 217void *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 248void *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 270static 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 300void 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 305void 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 310static 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 366static 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 405static 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 */ 443unsigned 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 472unsigned long lh_num_items(const _LHASH *lh) 473 { 474 return lh ? lh->num_items : 0; 475 } 476