lhash.c revision 296465
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 115LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c) 116{ 117 LHASH *ret; 118 int i; 119 120 if ((ret = (LHASH *)OPENSSL_malloc(sizeof(LHASH))) == NULL) 121 goto err0; 122 if ((ret->b = 123 (LHASH_NODE **)OPENSSL_malloc(sizeof(LHASH_NODE *) * MIN_NODES)) == 124 NULL) 125 goto err1; 126 for (i = 0; i < MIN_NODES; i++) 127 ret->b[i] = NULL; 128 ret->comp = ((c == NULL) ? (LHASH_COMP_FN_TYPE)strcmp : c); 129 ret->hash = ((h == NULL) ? (LHASH_HASH_FN_TYPE)lh_strhash : h); 130 ret->num_nodes = MIN_NODES / 2; 131 ret->num_alloc_nodes = MIN_NODES; 132 ret->p = 0; 133 ret->pmax = MIN_NODES / 2; 134 ret->up_load = UP_LOAD; 135 ret->down_load = DOWN_LOAD; 136 ret->num_items = 0; 137 138 ret->num_expands = 0; 139 ret->num_expand_reallocs = 0; 140 ret->num_contracts = 0; 141 ret->num_contract_reallocs = 0; 142 ret->num_hash_calls = 0; 143 ret->num_comp_calls = 0; 144 ret->num_insert = 0; 145 ret->num_replace = 0; 146 ret->num_delete = 0; 147 ret->num_no_delete = 0; 148 ret->num_retrieve = 0; 149 ret->num_retrieve_miss = 0; 150 ret->num_hash_comps = 0; 151 152 ret->error = 0; 153 return (ret); 154 err1: 155 OPENSSL_free(ret); 156 err0: 157 return (NULL); 158} 159 160void lh_free(LHASH *lh) 161{ 162 unsigned int i; 163 LHASH_NODE *n, *nn; 164 165 if (lh == NULL) 166 return; 167 168 for (i = 0; i < lh->num_nodes; i++) { 169 n = lh->b[i]; 170 while (n != NULL) { 171 nn = n->next; 172 OPENSSL_free(n); 173 n = nn; 174 } 175 } 176 OPENSSL_free(lh->b); 177 OPENSSL_free(lh); 178} 179 180void *lh_insert(LHASH *lh, void *data) 181{ 182 unsigned long hash; 183 LHASH_NODE *nn, **rn; 184 void *ret; 185 186 lh->error = 0; 187 if (lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) 188 expand(lh); 189 190 rn = getrn(lh, data, &hash); 191 192 if (*rn == NULL) { 193 if ((nn = (LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL) { 194 lh->error++; 195 return (NULL); 196 } 197 nn->data = data; 198 nn->next = NULL; 199#ifndef OPENSSL_NO_HASH_COMP 200 nn->hash = hash; 201#endif 202 *rn = nn; 203 ret = NULL; 204 lh->num_insert++; 205 lh->num_items++; 206 } else { /* replace same key */ 207 208 ret = (*rn)->data; 209 (*rn)->data = data; 210 lh->num_replace++; 211 } 212 return (ret); 213} 214 215void *lh_delete(LHASH *lh, const void *data) 216{ 217 unsigned long hash; 218 LHASH_NODE *nn, **rn; 219 void *ret; 220 221 lh->error = 0; 222 rn = getrn(lh, data, &hash); 223 224 if (*rn == NULL) { 225 lh->num_no_delete++; 226 return (NULL); 227 } else { 228 nn = *rn; 229 *rn = nn->next; 230 ret = nn->data; 231 OPENSSL_free(nn); 232 lh->num_delete++; 233 } 234 235 lh->num_items--; 236 if ((lh->num_nodes > MIN_NODES) && 237 (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))) 238 contract(lh); 239 240 return (ret); 241} 242 243void *lh_retrieve(LHASH *lh, const void *data) 244{ 245 unsigned long hash; 246 LHASH_NODE **rn; 247 void *ret; 248 249 lh->error = 0; 250 rn = getrn(lh, data, &hash); 251 252 if (*rn == NULL) { 253 lh->num_retrieve_miss++; 254 return (NULL); 255 } else { 256 ret = (*rn)->data; 257 lh->num_retrieve++; 258 } 259 return (ret); 260} 261 262static void doall_util_fn(LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func, 263 LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg) 264{ 265 int i; 266 LHASH_NODE *a, *n; 267 268 /* 269 * reverse the order so we search from 'top to bottom' We were having 270 * memory leaks otherwise 271 */ 272 for (i = lh->num_nodes - 1; i >= 0; i--) { 273 a = lh->b[i]; 274 while (a != NULL) { 275 /* 276 * 28/05/91 - eay - n added so items can be deleted via lh_doall 277 */ 278 n = a->next; 279 if (use_arg) 280 func_arg(a->data, arg); 281 else 282 func(a->data); 283 a = n; 284 } 285 } 286} 287 288void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func) 289{ 290 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL); 291} 292 293void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg) 294{ 295 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg); 296} 297 298static void expand(LHASH *lh) 299{ 300 LHASH_NODE **n, **n1, **n2, *np; 301 unsigned int p, i, j, pmax; 302 unsigned long hash, nni; 303 304 p = (int)lh->p++; 305 nni = lh->num_alloc_nodes; 306 pmax = lh->pmax; 307 308 if ((lh->p) >= lh->pmax) { 309 j = (int)lh->num_alloc_nodes * 2; 310 n = (LHASH_NODE **)OPENSSL_realloc(lh->b, 311 (int)sizeof(LHASH_NODE *) * j); 312 if (n == NULL) { 313/* fputs("realloc error in lhash",stderr); */ 314 lh->error++; 315 lh->p = 0; 316 return; 317 } 318 /* else */ 319 for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */ 320 n[i] = NULL; /* 02/03/92 eay */ 321 lh->pmax = lh->num_alloc_nodes; 322 lh->num_alloc_nodes = j; 323 lh->num_expand_reallocs++; 324 lh->p = 0; 325 lh->b = n; 326 } 327 328 lh->num_nodes++; 329 lh->num_expands++; 330 n1 = &(lh->b[p]); 331 n2 = &(lh->b[p + pmax]); 332 *n2 = NULL; /* 27/07/92 - eay - undefined pointer bug */ 333 334 for (np = *n1; np != NULL;) { 335#ifndef OPENSSL_NO_HASH_COMP 336 hash = np->hash; 337#else 338 hash = lh->hash(np->data); 339 lh->num_hash_calls++; 340#endif 341 if ((hash % nni) != p) { /* move it */ 342 *n1 = (*n1)->next; 343 np->next = *n2; 344 *n2 = np; 345 } else 346 n1 = &((*n1)->next); 347 np = *n1; 348 } 349 350} 351 352static void contract(LHASH *lh) 353{ 354 LHASH_NODE **n, *n1, *np; 355 int idx = lh->p + lh->pmax - 1; 356 357 np = lh->b[idx]; 358 if (lh->p == 0) { 359 n = (LHASH_NODE **)OPENSSL_realloc(lh->b, 360 (unsigned int)(sizeof(LHASH_NODE *) 361 * lh->pmax)); 362 if (n == NULL) { 363/* fputs("realloc error in lhash",stderr); */ 364 lh->error++; 365 return; 366 } 367 lh->num_contract_reallocs++; 368 lh->num_alloc_nodes /= 2; 369 lh->pmax /= 2; 370 lh->p = lh->pmax - 1; 371 lh->b = n; 372 } else 373 lh->p--; 374 375 lh->b[idx] = NULL; 376 lh->num_nodes--; 377 lh->num_contracts++; 378 379 n1 = lh->b[(int)lh->p]; 380 if (n1 == NULL) 381 lh->b[(int)lh->p] = np; 382 else { 383 while (n1->next != NULL) 384 n1 = n1->next; 385 n1->next = np; 386 } 387} 388 389static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash) 390{ 391 LHASH_NODE **ret, *n1; 392 unsigned long hash, nn; 393 LHASH_COMP_FN_TYPE cf; 394 395 hash = (*(lh->hash)) (data); 396 lh->num_hash_calls++; 397 *rhash = hash; 398 399 nn = hash % lh->pmax; 400 if (nn < lh->p) 401 nn = hash % lh->num_alloc_nodes; 402 403 cf = lh->comp; 404 ret = &(lh->b[(int)nn]); 405 for (n1 = *ret; n1 != NULL; n1 = n1->next) { 406#ifndef OPENSSL_NO_HASH_COMP 407 lh->num_hash_comps++; 408 if (n1->hash != hash) { 409 ret = &(n1->next); 410 continue; 411 } 412#endif 413 lh->num_comp_calls++; 414 if (cf(n1->data, data) == 0) 415 break; 416 ret = &(n1->next); 417 } 418 return (ret); 419} 420 421/* 422 * The following hash seems to work very well on normal text strings no 423 * collisions on /usr/dict/words and it distributes on %2^n quite well, not 424 * as good as MD5, but still good. 425 */ 426unsigned long lh_strhash(const char *c) 427{ 428 unsigned long ret = 0; 429 long n; 430 unsigned long v; 431 int r; 432 433 if ((c == NULL) || (*c == '\0')) 434 return (ret); 435/*- 436 unsigned char b[16]; 437 MD5(c,strlen(c),b); 438 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24)); 439*/ 440 441 n = 0x100; 442 while (*c) { 443 v = n | (*c); 444 n += 0x100; 445 r = (int)((v >> 2) ^ v) & 0x0f; 446 ret = (ret << r) | (ret >> (32 - r)); 447 ret &= 0xFFFFFFFFL; 448 ret ^= v * v; 449 c++; 450 } 451 return ((ret >> 16) ^ ret); 452} 453 454unsigned long lh_num_items(const LHASH *lh) 455{ 456 return lh ? lh->num_items : 0; 457} 458