AppleCSP/open_ssl/lhash/lhash.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, 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
 121 const 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
 128 static void expand(LHASH *lh);
 129 static void contract(LHASH *lh);
 130 static LHASH_NODE **getrn(LHASH *lh, void *data, unsigned long *rhash);
 131
 132 LHASH *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);
 169 err1:
 170         Free(ret);
 171 err0:
 172         return(NULL);
 173         }
 174
 175 void 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
 197 void *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
 235 void *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
 266 void *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
 288 void lh_doall(LHASH *lh, void (*func)())
 289         {
 290         lh_doall_arg(lh,func,NULL);
 291         }
 292
 293 void 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
 314 static 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
 370 static 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
 409 static 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  */
 447 unsigned 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
 476 unsigned long lh_num_items(LHASH *lh)
 477         {
 478         return lh ? lh->num_items : 0;
 479         }