| OLD | NEW |
|---|
| (Empty) |
| 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 <limits.h> | |
| 98 #include <stdio.h> | |
| 99 #include <string.h> | |
| 100 #include <stdlib.h> | |
| 101 #include <openssl/crypto.h> | |
| 102 #include <openssl/lhash.h> | |
| 103 | |
| 104 const char lh_version[]="lhash" OPENSSL_VERSION_PTEXT; | |
| 105 | |
| 106 #undef MIN_NODES | |
| 107 #define MIN_NODES 16 | |
| 108 #define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */ | |
| 109 #define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */ | |
| 110 | |
| 111 /* Maximum number of nodes to guarantee the load computations don't overflow */ | |
| 112 #define MAX_LOAD_ITEMS (UINT_MAX / LH_LOAD_MULT) | |
| 113 | |
| 114 /* The field 'iteration_state' is used to hold data to ensure that a hash | |
| 115 * table is not resized during an 'insert' or 'delete' operation performed | |
| 116 * within a lh_doall/lh_doall_arg call. | |
| 117 * | |
| 118 * Conceptually, this records two things: | |
| 119 * | |
| 120 * - A 'depth' count, which is incremented at the start of lh_doall*, | |
| 121 * and decremented just before it returns. | |
| 122 * | |
| 123 * - A 'mutated' boolean flag, which is set in lh_insert() or lh_delete() | |
| 124 * when the operation is performed with a non-0 depth. | |
| 125 * | |
| 126 * The following are helper macros to handle this state in a more explicit | |
| 127 * way. | |
| 128 */ | |
| 129 | |
| 130 /* Reset the iteration state to its defaults. */ | |
| 131 #define LH_ITERATION_RESET(lh) do { \ | |
| 132 (lh)->iteration_state = 0; \ | |
| 133 } while (0) | |
| 134 | |
| 135 /* Returns 1 if the hash table is currently being iterated on, 0 otherwise. */ | |
| 136 #define LH_ITERATION_IS_ACTIVE(lh) ((lh)->iteration_state >= 2) | |
| 137 | |
| 138 /* Increment iteration depth. This should always be followed by a paired call | |
| 139 * to LH_ITERATION_DECREMENT_DEPTH(). */ | |
| 140 #define LH_ITERATION_INCREMENT_DEPTH(lh) do { \ | |
| 141 (lh)->iteration_state += 2; \ | |
| 142 } while (0) | |
| 143 | |
| 144 /* Decrement iteration depth. This should always be called after a paired call | |
| 145 * to LH_ITERATION_INCREMENT_DEPTH(). */ | |
| 146 #define LH_ITERATION_DECREMENT_DEPTH(lh) do { \ | |
| 147 (lh)->iteration_state -= 2; \ | |
| 148 } while (0) | |
| 149 | |
| 150 /* Return 1 if the iteration 'mutated' flag is set, 0 otherwise. */ | |
| 151 #define LH_ITERATION_IS_MUTATED(lh) (((lh)->iteration_state & 1) != 0) | |
| 152 | |
| 153 /* Set the iteration 'mutated' flag to 1. LH_ITERATION_RESET() to reset it. */ | |
| 154 #define LH_ITERATION_SET_MUTATED(lh) do { \ | |
| 155 (lh)->iteration_state |= 1; \ | |
| 156 } while (0) | |
| 157 | |
| 158 /* This macro returns 1 if the hash table should be expanded due to its current | |
| 159 * load, or 0 otherwise. The exact comparison to be performed is expressed by | |
| 160 * the mathematical expression (where '//' denotes division over real numbers): | |
| 161 * | |
| 162 * (num_items // num_nodes) >= (up_load // LOAD_MULT) or | |
| 163 * (num_items * LOAD_MULT // num_nodes) >= up_load. | |
| 164 * | |
| 165 * Given that the C language operator '/' implements integer division, i.e: | |
| 166 * a // b == (a / b) + epsilon (with 0 <= epsilon < 1, for positive a & b) | |
| 167 * | |
| 168 * This can be rewritten as: | |
| 169 * (num_items * LOAD_MULT / num_nodes) + epsilon >= up_load | |
| 170 * (num_items * LOAD_MULT / num_nodes) - up_load >= - epsilon | |
| 171 * | |
| 172 * Let's call 'A' the left-hand side of the equation above, it is an integer | |
| 173 * and: | |
| 174 * - If A >= 0, the expression is true for any value of epsilon. | |
| 175 * - If A <= -1, the expression is also true for any value of epsilon. | |
| 176 * | |
| 177 * In other words, this is equivalent to 'A >= 0', or: | |
| 178 * (num_items * LOAD_MULT / num_nodes) >= up_load | |
| 179 */ | |
| 180 #define LH_SHOULD_EXPAND(lh) \ | |
| 181 ((lh)->num_items < MAX_LOAD_ITEMS && \ | |
| 182 (((lh)->num_items*LH_LOAD_MULT/(lh)->num_nodes) >= (lh)->up_load)) | |
| 183 | |
| 184 /* This macro returns 1 if the hash table should be contracted due to its | |
| 185 * current load, or 0 otherwise. Abbreviated computations are: | |
| 186 * | |
| 187 * (num_items // num_nodes) <= (down_load // LOAD_MULT) | |
| 188 * (num_items * LOAD_MULT // num_nodes) <= down_load | |
| 189 * (num_items * LOAD_MULT / num_nodes) + epsilon <= down_load | |
| 190 * (num_items * LOAD_MULT / num_nodes) - down_load <= -epsilon | |
| 191 * | |
| 192 * Let's call 'B' the left-hand side of the equation above: | |
| 193 * - If B <= -1, the expression is true for any value of epsilon. | |
| 194 * - If B >= 1, the expression is false for any value of epsilon. | |
| 195 * - If B == 0, the expression is true for 'epsilon == 0', and false | |
| 196 * otherwise, which is problematic. | |
| 197 * | |
| 198 * To work around this problem, while keeping the code simple, just change | |
| 199 * the initial expression to use a strict inequality, i.e.: | |
| 200 * | |
| 201 * (num_items // num_nodes) < (down_load // LOAD_MULT) | |
| 202 * | |
| 203 * Which leads to: | |
| 204 * (num_items * LOAD_MULT / num_nodes) - down_load < -epsilon | |
| 205 * | |
| 206 * Then: | |
| 207 * - If 'B <= -1', the expression is true for any value of epsilon. | |
| 208 * - If 'B' >= 0, the expression is false for any value of epsilon, | |
| 209 * | |
| 210 * In other words, this is equivalent to 'B < 0', or: | |
| 211 * (num_items * LOAD_MULT / num_nodes) < down_load | |
| 212 */ | |
| 213 #define LH_SHOULD_CONTRACT(lh) \ | |
| 214 (((lh)->num_nodes > MIN_NODES) && \ | |
| 215 ((lh)->num_items < MAX_LOAD_ITEMS && \ | |
| 216 ((lh)->num_items*LH_LOAD_MULT/(lh)->num_nodes) < (lh)->down_load)) | |
| 217 | |
| 218 static void expand(_LHASH *lh); | |
| 219 static void contract(_LHASH *lh); | |
| 220 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash); | |
| 221 | |
| 222 _LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c) | |
| 223 { | |
| 224 _LHASH *ret; | |
| 225 int i; | |
| 226 | |
| 227 if ((ret=OPENSSL_malloc(sizeof(_LHASH))) == NULL) | |
| 228 goto err0; | |
| 229 if ((ret->b=OPENSSL_malloc(sizeof(LHASH_NODE *)*MIN_NODES)) == NULL) | |
| 230 goto err1; | |
| 231 for (i=0; i<MIN_NODES; i++) | |
| 232 ret->b[i]=NULL; | |
| 233 ret->comp=((c == NULL)?(LHASH_COMP_FN_TYPE)strcmp:c); | |
| 234 ret->hash=((h == NULL)?(LHASH_HASH_FN_TYPE)lh_strhash:h); | |
| 235 ret->num_nodes=MIN_NODES/2; | |
| 236 ret->num_alloc_nodes=MIN_NODES; | |
| 237 ret->p=0; | |
| 238 ret->pmax=MIN_NODES/2; | |
| 239 ret->up_load=UP_LOAD; | |
| 240 ret->down_load=DOWN_LOAD; | |
| 241 ret->num_items=0; | |
| 242 | |
| 243 ret->num_expands=0; | |
| 244 ret->num_expand_reallocs=0; | |
| 245 ret->num_contracts=0; | |
| 246 ret->num_contract_reallocs=0; | |
| 247 ret->num_hash_calls=0; | |
| 248 ret->num_comp_calls=0; | |
| 249 ret->num_insert=0; | |
| 250 ret->num_replace=0; | |
| 251 ret->num_delete=0; | |
| 252 ret->num_no_delete=0; | |
| 253 ret->num_retrieve=0; | |
| 254 ret->num_retrieve_miss=0; | |
| 255 ret->num_hash_comps=0; | |
| 256 | |
| 257 ret->error=0; | |
| 258 LH_ITERATION_RESET(ret); | |
| 259 return(ret); | |
| 260 err1: | |
| 261 OPENSSL_free(ret); | |
| 262 err0: | |
| 263 return(NULL); | |
| 264 } | |
| 265 | |
| 266 void lh_free(_LHASH *lh) | |
| 267 { | |
| 268 unsigned int i; | |
| 269 LHASH_NODE *n,*nn; | |
| 270 | |
| 271 if (lh == NULL) | |
| 272 return; | |
| 273 | |
| 274 for (i=0; i<lh->num_nodes; i++) | |
| 275 { | |
| 276 n=lh->b[i]; | |
| 277 while (n != NULL) | |
| 278 { | |
| 279 nn=n->next; | |
| 280 OPENSSL_free(n); | |
| 281 n=nn; | |
| 282 } | |
| 283 } | |
| 284 OPENSSL_free(lh->b); | |
| 285 OPENSSL_free(lh); | |
| 286 } | |
| 287 | |
| 288 void *lh_insert(_LHASH *lh, void *data) | |
| 289 { | |
| 290 unsigned long hash; | |
| 291 LHASH_NODE *nn,**rn; | |
| 292 void *ret; | |
| 293 | |
| 294 lh->error=0; | |
| 295 /* Do not expand the array if the table is being iterated on. */ | |
| 296 if (LH_ITERATION_IS_ACTIVE(lh)) | |
| 297 LH_ITERATION_SET_MUTATED(lh); | |
| 298 else if (LH_SHOULD_EXPAND(lh)) | |
| 299 expand(lh); | |
| 300 | |
| 301 rn=getrn(lh,data,&hash); | |
| 302 | |
| 303 if (*rn == NULL) | |
| 304 { | |
| 305 if ((nn=(LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NUL
L) | |
| 306 { | |
| 307 lh->error++; | |
| 308 return(NULL); | |
| 309 } | |
| 310 nn->data=data; | |
| 311 nn->next=NULL; | |
| 312 #ifndef OPENSSL_NO_HASH_COMP | |
| 313 nn->hash=hash; | |
| 314 #endif | |
| 315 *rn=nn; | |
| 316 ret=NULL; | |
| 317 lh->num_insert++; | |
| 318 lh->num_items++; | |
| 319 } | |
| 320 else /* replace same key */ | |
| 321 { | |
| 322 ret= (*rn)->data; | |
| 323 (*rn)->data=data; | |
| 324 lh->num_replace++; | |
| 325 } | |
| 326 return(ret); | |
| 327 } | |
| 328 | |
| 329 void *lh_delete(_LHASH *lh, const void *data) | |
| 330 { | |
| 331 unsigned long hash; | |
| 332 LHASH_NODE *nn,**rn; | |
| 333 void *ret; | |
| 334 | |
| 335 lh->error=0; | |
| 336 rn=getrn(lh,data,&hash); | |
| 337 | |
| 338 if (*rn == NULL) | |
| 339 { | |
| 340 lh->num_no_delete++; | |
| 341 return(NULL); | |
| 342 } | |
| 343 else | |
| 344 { | |
| 345 nn= *rn; | |
| 346 *rn=nn->next; | |
| 347 ret=nn->data; | |
| 348 OPENSSL_free(nn); | |
| 349 lh->num_delete++; | |
| 350 } | |
| 351 | |
| 352 lh->num_items--; | |
| 353 /* Do not contract the array if the table is being iterated on. */ | |
| 354 if (LH_ITERATION_IS_ACTIVE(lh)) | |
| 355 LH_ITERATION_SET_MUTATED(lh); | |
| 356 else if (LH_SHOULD_CONTRACT(lh)) | |
| 357 contract(lh); | |
| 358 | |
| 359 return(ret); | |
| 360 } | |
| 361 | |
| 362 void *lh_retrieve(_LHASH *lh, const void *data) | |
| 363 { | |
| 364 unsigned long hash; | |
| 365 LHASH_NODE **rn; | |
| 366 void *ret; | |
| 367 | |
| 368 lh->error=0; | |
| 369 rn=getrn(lh,data,&hash); | |
| 370 | |
| 371 if (*rn == NULL) | |
| 372 { | |
| 373 lh->num_retrieve_miss++; | |
| 374 return(NULL); | |
| 375 } | |
| 376 else | |
| 377 { | |
| 378 ret= (*rn)->data; | |
| 379 lh->num_retrieve++; | |
| 380 } | |
| 381 return(ret); | |
| 382 } | |
| 383 | |
| 384 static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func, | |
| 385 LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg) | |
| 386 { | |
| 387 int i; | |
| 388 LHASH_NODE *a,*n; | |
| 389 | |
| 390 if (lh == NULL) | |
| 391 return; | |
| 392 | |
| 393 LH_ITERATION_INCREMENT_DEPTH(lh); | |
| 394 /* reverse the order so we search from 'top to bottom' | |
| 395 * We were having memory leaks otherwise */ | |
| 396 for (i=lh->num_nodes-1; i>=0; i--) | |
| 397 { | |
| 398 a=lh->b[i]; | |
| 399 while (a != NULL) | |
| 400 { | |
| 401 /* note that 'a' can be deleted by the callback */ | |
| 402 n=a->next; | |
| 403 if(use_arg) | |
| 404 func_arg(a->data,arg); | |
| 405 else | |
| 406 func(a->data); | |
| 407 a=n; | |
| 408 } | |
| 409 } | |
| 410 | |
| 411 LH_ITERATION_DECREMENT_DEPTH(lh); | |
| 412 if (!LH_ITERATION_IS_ACTIVE(lh) && LH_ITERATION_IS_MUTATED(lh)) | |
| 413 { | |
| 414 LH_ITERATION_RESET(lh); | |
| 415 /* Resize the buckets array if necessary. Each expand() or | |
| 416 * contract() call will double/halve the size of the array, | |
| 417 * respectively, so call them in a loop. */ | |
| 418 while (LH_SHOULD_EXPAND(lh)) | |
| 419 expand(lh); | |
| 420 while (LH_SHOULD_CONTRACT(lh)) | |
| 421 contract(lh); | |
| 422 } | |
| 423 } | |
| 424 | |
| 425 void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func) | |
| 426 { | |
| 427 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL); | |
| 428 } | |
| 429 | |
| 430 void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg) | |
| 431 { | |
| 432 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg); | |
| 433 } | |
| 434 | |
| 435 static void expand(_LHASH *lh) | |
| 436 { | |
| 437 LHASH_NODE **n,**n1,**n2,*np; | |
| 438 unsigned int p,i,j; | |
| 439 unsigned long hash,nni; | |
| 440 | |
| 441 lh->num_nodes++; | |
| 442 lh->num_expands++; | |
| 443 p=(int)lh->p++; | |
| 444 n1= &(lh->b[p]); | |
| 445 n2= &(lh->b[p+(int)lh->pmax]); | |
| 446 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */ | |
| 447 nni=lh->num_alloc_nodes; | |
| 448 | |
| 449 for (np= *n1; np != NULL; ) | |
| 450 { | |
| 451 #ifndef OPENSSL_NO_HASH_COMP | |
| 452 hash=np->hash; | |
| 453 #else | |
| 454 hash=lh->hash(np->data); | |
| 455 lh->num_hash_calls++; | |
| 456 #endif | |
| 457 if ((hash%nni) != p) | |
| 458 { /* move it */ | |
| 459 *n1= (*n1)->next; | |
| 460 np->next= *n2; | |
| 461 *n2=np; | |
| 462 } | |
| 463 else | |
| 464 n1= &((*n1)->next); | |
| 465 np= *n1; | |
| 466 } | |
| 467 | |
| 468 if ((lh->p) >= lh->pmax) | |
| 469 { | |
| 470 j=(int)lh->num_alloc_nodes*2; | |
| 471 n=(LHASH_NODE **)OPENSSL_realloc(lh->b, | |
| 472 (int)(sizeof(LHASH_NODE *)*j)); | |
| 473 if (n == NULL) | |
| 474 { | |
| 475 /* fputs("realloc error in lhash",stderr); */ | |
| 476 lh->error++; | |
| 477 lh->p=0; | |
| 478 return; | |
| 479 } | |
| 480 /* else */ | |
| 481 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */ | |
| 482 n[i]=NULL; /* 02/03/92 eay */ | |
| 483 lh->pmax=lh->num_alloc_nodes; | |
| 484 lh->num_alloc_nodes=j; | |
| 485 lh->num_expand_reallocs++; | |
| 486 lh->p=0; | |
| 487 lh->b=n; | |
| 488 } | |
| 489 } | |
| 490 | |
| 491 static void contract(_LHASH *lh) | |
| 492 { | |
| 493 LHASH_NODE **n,*n1,*np; | |
| 494 | |
| 495 np=lh->b[lh->p+lh->pmax-1]; | |
| 496 lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */ | |
| 497 if (lh->p == 0) | |
| 498 { | |
| 499 n=(LHASH_NODE **)OPENSSL_realloc(lh->b, | |
| 500 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax)); | |
| 501 if (n == NULL) | |
| 502 { | |
| 503 /* fputs("realloc error in lhash",stderr); */ | |
| 504 lh->error++; | |
| 505 return; | |
| 506 } | |
| 507 lh->num_contract_reallocs++; | |
| 508 lh->num_alloc_nodes/=2; | |
| 509 lh->pmax/=2; | |
| 510 lh->p=lh->pmax-1; | |
| 511 lh->b=n; | |
| 512 } | |
| 513 else | |
| 514 lh->p--; | |
| 515 | |
| 516 lh->num_nodes--; | |
| 517 lh->num_contracts++; | |
| 518 | |
| 519 n1=lh->b[(int)lh->p]; | |
| 520 if (n1 == NULL) | |
| 521 lh->b[(int)lh->p]=np; | |
| 522 else | |
| 523 { | |
| 524 while (n1->next != NULL) | |
| 525 n1=n1->next; | |
| 526 n1->next=np; | |
| 527 } | |
| 528 } | |
| 529 | |
| 530 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash) | |
| 531 { | |
| 532 LHASH_NODE **ret,*n1; | |
| 533 unsigned long hash,nn; | |
| 534 LHASH_COMP_FN_TYPE cf; | |
| 535 | |
| 536 hash=(*(lh->hash))(data); | |
| 537 lh->num_hash_calls++; | |
| 538 *rhash=hash; | |
| 539 | |
| 540 nn=hash%lh->pmax; | |
| 541 if (nn < lh->p) | |
| 542 nn=hash%lh->num_alloc_nodes; | |
| 543 | |
| 544 cf=lh->comp; | |
| 545 ret= &(lh->b[(int)nn]); | |
| 546 for (n1= *ret; n1 != NULL; n1=n1->next) | |
| 547 { | |
| 548 #ifndef OPENSSL_NO_HASH_COMP | |
| 549 lh->num_hash_comps++; | |
| 550 if (n1->hash != hash) | |
| 551 { | |
| 552 ret= &(n1->next); | |
| 553 continue; | |
| 554 } | |
| 555 #endif | |
| 556 lh->num_comp_calls++; | |
| 557 if(cf(n1->data,data) == 0) | |
| 558 break; | |
| 559 ret= &(n1->next); | |
| 560 } | |
| 561 return(ret); | |
| 562 } | |
| 563 | |
| 564 /* The following hash seems to work very well on normal text strings | |
| 565 * no collisions on /usr/dict/words and it distributes on %2^n quite | |
| 566 * well, not as good as MD5, but still good. | |
| 567 */ | |
| 568 unsigned long lh_strhash(const char *c) | |
| 569 { | |
| 570 unsigned long ret=0; | |
| 571 long n; | |
| 572 unsigned long v; | |
| 573 int r; | |
| 574 | |
| 575 if ((c == NULL) || (*c == '\0')) | |
| 576 return(ret); | |
| 577 /* | |
| 578 unsigned char b[16]; | |
| 579 MD5(c,strlen(c),b); | |
| 580 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); | |
| 581 */ | |
| 582 | |
| 583 n=0x100; | |
| 584 while (*c) | |
| 585 { | |
| 586 v=n|(*c); | |
| 587 n+=0x100; | |
| 588 r= (int)((v>>2)^v)&0x0f; | |
| 589 ret=(ret<<r)|(ret>>(32-r)); | |
| 590 ret&=0xFFFFFFFFL; | |
| 591 ret^=v*v; | |
| 592 c++; | |
| 593 } | |
| 594 return((ret>>16)^ret); | |
| 595 } | |
| 596 | |
| 597 unsigned long lh_num_items(const _LHASH *lh) | |
| 598 { | |
| 599 return lh ? lh->num_items : 0; | |
| 600 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2072073002:
Delete bundled copy of OpenSSL and replace with README. (Closed)
Base URL: https://chromium.googlesource.com/chromium/deps/openssl@master