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 114LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c) 115 { 116 LHASH *ret; 117 int i; 118 119 if ((ret=(LHASH *)OPENSSL_malloc(sizeof(LHASH))) == NULL) 120 goto err0; 121 if ((ret->b=(LHASH_NODE **)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 /* reverse the order so we search from 'top to bottom' 277 * We were having memory leaks otherwise */ 278 for (i=lh->num_nodes-1; i>=0; i--) 279 { 280 a=lh->b[i]; 281 while (a != NULL) 282 { 283 /* 28/05/91 - eay - n added so items can be deleted 284 * via lh_doall */ 285 n=a->next; 286 if(use_arg) 287 func_arg(a->data,arg); 288 else 289 func(a->data); 290 a=n; 291 } 292 } 293 } 294 295void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func) 296 { 297 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL); 298 } 299 300void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg) 301 { 302 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg); 303 } 304 305static void expand(LHASH *lh) 306 { 307 LHASH_NODE **n,**n1,**n2,*np; 308 unsigned int p,i,j,pmax; 309 unsigned long hash,nni; 310 311 p=(int)lh->p++; 312 nni=lh->num_alloc_nodes; 313 pmax=lh->pmax; 314 315 if ((lh->p) >= lh->pmax) 316 { 317 j=(int)lh->num_alloc_nodes*2; 318 n=(LHASH_NODE **)OPENSSL_realloc(lh->b, 319 (int)sizeof(LHASH_NODE *)*j); 320 if (n == NULL) 321 { 322/* fputs("realloc error in lhash",stderr); */ 323 lh->error++; 324 lh->p=0; 325 return; 326 } 327 /* else */ 328 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */ 329 n[i]=NULL; /* 02/03/92 eay */ 330 lh->pmax=lh->num_alloc_nodes; 331 lh->num_alloc_nodes=j; 332 lh->num_expand_reallocs++; 333 lh->p=0; 334 lh->b=n; 335 } 336 337 lh->num_nodes++; 338 lh->num_expands++; 339 n1= &(lh->b[p]); 340 n2= &(lh->b[p+pmax]); 341 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */ 342 343 for (np= *n1; np != NULL; ) 344 { 345#ifndef OPENSSL_NO_HASH_COMP 346 hash=np->hash; 347#else 348 hash=lh->hash(np->data); 349 lh->num_hash_calls++; 350#endif 351 if ((hash%nni) != p) 352 { /* move it */ 353 *n1= (*n1)->next; 354 np->next= *n2; 355 *n2=np; 356 } 357 else 358 n1= &((*n1)->next); 359 np= *n1; 360 } 361 362 } 363 364static void contract(LHASH *lh) 365 { 366 LHASH_NODE **n,*n1,*np; 367 int idx = lh->p+lh->pmax-1; 368 369 np=lh->b[idx]; 370 if (lh->p == 0) 371 { 372 n=(LHASH_NODE **)OPENSSL_realloc(lh->b, 373 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax)); 374 if (n == NULL) 375 { 376/* fputs("realloc error in lhash",stderr); */ 377 lh->error++; 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->b[idx] = NULL; 390 lh->num_nodes--; 391 lh->num_contracts++; 392 393 n1=lh->b[(int)lh->p]; 394 if (n1 == NULL) 395 lh->b[(int)lh->p]=np; 396 else 397 { 398 while (n1->next != NULL) 399 n1=n1->next; 400 n1->next=np; 401 } 402 } 403 404static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash) 405 { 406 LHASH_NODE **ret,*n1; 407 unsigned long hash,nn; 408 LHASH_COMP_FN_TYPE cf; 409 410 hash=(*(lh->hash))(data); 411 lh->num_hash_calls++; 412 *rhash=hash; 413 414 nn=hash%lh->pmax; 415 if (nn < lh->p) 416 nn=hash%lh->num_alloc_nodes; 417 418 cf=lh->comp; 419 ret= &(lh->b[(int)nn]); 420 for (n1= *ret; n1 != NULL; n1=n1->next) 421 { 422#ifndef OPENSSL_NO_HASH_COMP 423 lh->num_hash_comps++; 424 if (n1->hash != hash) 425 { 426 ret= &(n1->next); 427 continue; 428 } 429#endif 430 lh->num_comp_calls++; 431 if(cf(n1->data,data) == 0) 432 break; 433 ret= &(n1->next); 434 } 435 return(ret); 436 } 437 438/* The following hash seems to work very well on normal text strings 439 * no collisions on /usr/dict/words and it distributes on %2^n quite 440 * well, not as good as MD5, but still good. 441 */ 442unsigned long lh_strhash(const char *c) 443 { 444 unsigned long ret=0; 445 long n; 446 unsigned long v; 447 int r; 448 449 if ((c == NULL) || (*c == '\0')) 450 return(ret); 451/* 452 unsigned char b[16]; 453 MD5(c,strlen(c),b); 454 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); 455*/ 456 457 n=0x100; 458 while (*c) 459 { 460 v=n|(*c); 461 n+=0x100; 462 r= (int)((v>>2)^v)&0x0f; 463 ret=(ret<<r)|(ret>>(32-r)); 464 ret&=0xFFFFFFFFL; 465 ret^=v*v; 466 c++; 467 } 468 return((ret>>16)^ret); 469 } 470 471unsigned long lh_num_items(const LHASH *lh) 472 { 473 return lh ? lh->num_items : 0; 474 } 475