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