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