hash.c

   1 /* $RCSfile: hash.c,v $$Revision: 4.0.1.3 $$Date: 92/06/08 13:26:29 $
   2  *
   3  *    Copyright (c) 1991, Larry Wall
   4  *
   5  *    You may distribute under the terms of either the GNU General Public
   6  *    License or the Artistic License, as specified in the README file.
   7  *
   8  * $Log:        hash.c,v $
   9  * Revision 4.0.1.3  92/06/08  13:26:29  lwall
  10  * patch20: removed implicit int declarations on functions
  11  * patch20: delete could cause %array to give too low a count of buckets filled
  12  * patch20: hash tables now split only if the memory is available to do so
  13  *
  14  * Revision 4.0.1.2  91/11/05  17:24:13  lwall
  15  * patch11: saberized perl
  16  *
  17  * Revision 4.0.1.1  91/06/07  11:10:11  lwall
  18  * patch4: new copyright notice
  19  *
  20  * Revision 4.0  91/03/20  01:22:26  lwall
  21  * 4.0 baseline.
  22  *
  23  */
  24
  25 #include "EXTERN.h"
  26 #include "perl.h"
  27
  28 static void hsplit();
  29
  30 static char coeff[] = {
  31                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  32                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  33                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  34                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  35                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  36                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  37                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  38                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
  39
  40 static void hfreeentries();
  41
  42 STR *
  43 hfetch(tb,key,klen,lval)
  44 register HASH *tb;
  45 char *key;
  46 unsigned int klen;
  47 int lval;
  48 {
  49     register char *s;
  50     register int i;
  51     register int hash;
  52     register HENT *entry;
  53     register int maxi;
  54     STR *str;
  55 #ifdef SOME_DBM
  56     datum dkey,dcontent;
  57 #endif
  58
  59     if (!tb)
  60         return &str_undef;
  61     if (!tb->tbl_array) {
  62         if (lval)
  63             Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
  64         else
  65             return &str_undef;
  66     }
  67
  68     /* The hash function we use on symbols has to be equal to the first
  69      * character when taken modulo 128, so that str_reset() can be implemented
  70      * efficiently.  We throw in the second character and the last character
  71      * (times 128) so that long chains of identifiers starting with the
  72      * same letter don't have to be strEQ'ed within hfetch(), since it
  73      * compares hash values before trying strEQ().
  74      */
  75     if (!tb->tbl_coeffsize)
  76         hash = *key + 128 * key[1] + 128 * key[klen-1]; /* assuming klen > 0 */
  77     else {      /* use normal coefficients */
  78         if (klen < tb->tbl_coeffsize)
  79             maxi = klen;
  80         else
  81             maxi = tb->tbl_coeffsize;
  82         for (s=key,             i=0,    hash = 0;
  83                             i < maxi;                   /*SUPPRESS 8*/
  84              s++,               i++,    hash *= 5) {
  85             hash += *s * coeff[i];
  86         }
  87     }
  88
  89     entry = tb->tbl_array[hash & tb->tbl_max];
  90     for (; entry; entry = entry->hent_next) {
  91         if (entry->hent_hash != hash)           /* strings can't be equal */
  92             continue;
  93         if (entry->hent_klen != klen)
  94             continue;
  95         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
  96             continue;
  97         return entry->hent_val;
  98     }
  99 #ifdef SOME_DBM
 100     if (tb->tbl_dbm) {
 101         dkey.dptr = key;
 102         dkey.dsize = klen;
 103 #ifdef HAS_GDBM
 104         dcontent = gdbm_fetch(tb->tbl_dbm,dkey);
 105 #else
 106         dcontent = dbm_fetch(tb->tbl_dbm,dkey);
 107 #endif
 108         if (dcontent.dptr) {                    /* found one */
 109             str = Str_new(60,dcontent.dsize);
 110             str_nset(str,dcontent.dptr,dcontent.dsize);
 111             hstore(tb,key,klen,str,hash);               /* cache it */
 112             return str;
 113         }
 114     }
 115 #endif
 116     if (lval) {         /* gonna assign to this, so it better be there */
 117         str = Str_new(61,0);
 118         hstore(tb,key,klen,str,hash);
 119         return str;
 120     }
 121     return &str_undef;
 122 }
 123
 124 bool
 125 hstore(tb,key,klen,val,hash)
 126 register HASH *tb;
 127 char *key;
 128 unsigned int klen;
 129 STR *val;
 130 register int hash;
 131 {
 132     register char *s;
 133     register int i;
 134     register HENT *entry;
 135     register HENT **oentry;
 136     register int maxi;
 137
 138     if (!tb)
 139         return FALSE;
 140
 141     if (hash)
 142         /*SUPPRESS 530*/
 143         ;
 144     else if (!tb->tbl_coeffsize)
 145         hash = *key + 128 * key[1] + 128 * key[klen-1];
 146     else {      /* use normal coefficients */
 147         if (klen < tb->tbl_coeffsize)
 148             maxi = klen;
 149         else
 150             maxi = tb->tbl_coeffsize;
 151         for (s=key,             i=0,    hash = 0;
 152                             i < maxi;                   /*SUPPRESS 8*/
 153              s++,               i++,    hash *= 5) {
 154             hash += *s * coeff[i];
 155         }
 156     }
 157
 158     if (!tb->tbl_array)
 159         Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);
 160
 161     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 162     i = 1;
 163
 164     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
 165         if (entry->hent_hash != hash)           /* strings can't be equal */
 166             continue;
 167         if (entry->hent_klen != klen)
 168             continue;
 169         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 170             continue;
 171         Safefree(entry->hent_val);
 172         entry->hent_val = val;
 173         return TRUE;
 174     }
 175     New(501,entry, 1, HENT);
 176
 177     entry->hent_klen = klen;
 178     entry->hent_key = nsavestr(key,klen);
 179     entry->hent_val = val;
 180     entry->hent_hash = hash;
 181     entry->hent_next = *oentry;
 182     *oentry = entry;
 183
 184     /* hdbmstore not necessary here because it's called from stabset() */
 185
 186     if (i) {                            /* initial entry? */
 187         tb->tbl_fill++;
 188 #ifdef SOME_DBM
 189         if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
 190             return FALSE;
 191 #endif
 192         if (tb->tbl_fill > tb->tbl_dosplit)
 193             hsplit(tb);
 194     }
 195 #ifdef SOME_DBM
 196     else if (tb->tbl_dbm) {             /* is this just a cache for dbm file? */
 197         void hentdelayfree();
 198
 199         entry = tb->tbl_array[hash & tb->tbl_max];
 200         oentry = &entry->hent_next;
 201         entry = *oentry;
 202         while (entry) { /* trim chain down to 1 entry */
 203             *oentry = entry->hent_next;
 204             hentdelayfree(entry);       /* no doubt they'll want this next. */
 205             entry = *oentry;
 206         }
 207     }
 208 #endif
 209
 210     return FALSE;
 211 }
 212
 213 STR *
 214 hdelete(tb,key,klen)
 215 register HASH *tb;
 216 char *key;
 217 unsigned int klen;
 218 {
 219     register char *s;
 220     register int i;
 221     register int hash;
 222     register HENT *entry;
 223     register HENT **oentry;
 224     STR *str;
 225     int maxi;
 226 #ifdef SOME_DBM
 227     datum dkey;
 228 #endif
 229
 230     if (!tb || !tb->tbl_array)
 231         return Nullstr;
 232     if (!tb->tbl_coeffsize)
 233         hash = *key + 128 * key[1] + 128 * key[klen-1];
 234     else {      /* use normal coefficients */
 235         if (klen < tb->tbl_coeffsize)
 236             maxi = klen;
 237         else
 238             maxi = tb->tbl_coeffsize;
 239         for (s=key,             i=0,    hash = 0;
 240                             i < maxi;                   /*SUPPRESS 8*/
 241              s++,               i++,    hash *= 5) {
 242             hash += *s * coeff[i];
 243         }
 244     }
 245
 246     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 247     entry = *oentry;
 248     i = 1;
 249     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
 250         if (entry->hent_hash != hash)           /* strings can't be equal */
 251             continue;
 252         if (entry->hent_klen != klen)
 253             continue;
 254         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 255             continue;
 256         *oentry = entry->hent_next;
 257         if (i && !*oentry)
 258             tb->tbl_fill--;
 259         str = str_mortal(entry->hent_val);
 260         hentfree(entry);
 261 #ifdef SOME_DBM
 262       do_dbm_delete:
 263         if (tb->tbl_dbm) {
 264             dkey.dptr = key;
 265             dkey.dsize = klen;
 266 #ifdef HAS_GDBM
 267             gdbm_delete(tb->tbl_dbm,dkey);
 268 #else
 269             dbm_delete(tb->tbl_dbm,dkey);
 270 #endif
 271         }
 272 #endif
 273         return str;
 274     }
 275 #ifdef SOME_DBM
 276     str = Nullstr;
 277     goto do_dbm_delete;
 278 #else
 279     return Nullstr;
 280 #endif
 281 }
 282
 283 static void
 284 hsplit(tb)
 285 HASH *tb;
 286 {
 287     int oldsize = tb->tbl_max + 1;
 288     register int newsize = oldsize * 2;
 289     register int i;
 290     register HENT **a;
 291     register HENT **b;
 292     register HENT *entry;
 293     register HENT **oentry;
 294
 295     a = tb->tbl_array;
 296     nomemok = TRUE;
 297     Renew(a, newsize, HENT*);
 298     nomemok = FALSE;
 299     if (!a) {
 300         tb->tbl_dosplit = tb->tbl_max + 1;      /* never split again */
 301         return;
 302     }
 303     Zero(&a[oldsize], oldsize, HENT*);          /* zero 2nd half*/
 304     tb->tbl_max = --newsize;
 305     tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
 306     tb->tbl_array = a;
 307
 308     for (i=0; i<oldsize; i++,a++) {
 309         if (!*a)                                /* non-existent */
 310             continue;
 311         b = a+oldsize;
 312         for (oentry = a, entry = *a; entry; entry = *oentry) {
 313             if ((entry->hent_hash & newsize) != i) {
 314                 *oentry = entry->hent_next;
 315                 entry->hent_next = *b;
 316                 if (!*b)
 317                     tb->tbl_fill++;
 318                 *b = entry;
 319                 continue;
 320             }
 321             else
 322                 oentry = &entry->hent_next;
 323         }
 324         if (!*a)                                /* everything moved */
 325             tb->tbl_fill--;
 326     }
 327 }
 328
 329 HASH *
 330 hnew(lookat)
 331 unsigned int lookat;
 332 {
 333     register HASH *tb;
 334
 335     Newz(502,tb, 1, HASH);
 336     if (lookat) {
 337         tb->tbl_coeffsize = lookat;
 338         tb->tbl_max = 7;                /* it's a normal associative array */
 339         tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
 340     }
 341     else {
 342         tb->tbl_max = 127;              /* it's a symbol table */
 343         tb->tbl_dosplit = 128;          /* so never split */
 344     }
 345     tb->tbl_fill = 0;
 346 #ifdef SOME_DBM
 347     tb->tbl_dbm = 0;
 348 #endif
 349     (void)hiterinit(tb);        /* so each() will start off right */
 350     return tb;
 351 }
 352
 353 void
 354 hentfree(hent)
 355 register HENT *hent;
 356 {
 357     if (!hent)
 358         return;
 359     str_free(hent->hent_val);
 360     Safefree(hent->hent_key);
 361     Safefree(hent);
 362 }
 363
 364 void
 365 hentdelayfree(hent)
 366 register HENT *hent;
 367 {
 368     if (!hent)
 369         return;
 370     str_2mortal(hent->hent_val);        /* free between statements */
 371     Safefree(hent->hent_key);
 372     Safefree(hent);
 373 }
 374
 375 void
 376 hclear(tb,dodbm)
 377 register HASH *tb;
 378 int dodbm;
 379 {
 380     if (!tb)
 381         return;
 382     hfreeentries(tb,dodbm);
 383     tb->tbl_fill = 0;
 384 #ifndef lint
 385     if (tb->tbl_array)
 386         (void)memzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
 387 #endif
 388 }
 389
 390 static void
 391 hfreeentries(tb,dodbm)
 392 register HASH *tb;
 393 int dodbm;
 394 {
 395     register HENT *hent;
 396     register HENT *ohent = Null(HENT*);
 397 #ifdef SOME_DBM
 398     datum dkey;
 399     datum nextdkey;
 400 #ifdef HAS_GDBM
 401     GDBM_FILE old_dbm;
 402 #else
 403 #ifdef HAS_NDBM
 404     DBM *old_dbm;
 405 #else
 406     int old_dbm;
 407 #endif
 408 #endif
 409 #endif
 410
 411     if (!tb || !tb->tbl_array)
 412         return;
 413 #ifdef SOME_DBM
 414     if ((old_dbm = tb->tbl_dbm) && dodbm) {
 415 #ifdef HAS_GDBM
 416         while (dkey = gdbm_firstkey(tb->tbl_dbm), dkey.dptr) {
 417 #else
 418         while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
 419 #endif
 420             do {
 421 #ifdef HAS_GDBM
 422                 nextdkey = gdbm_nextkey(tb->tbl_dbm, dkey);
 423 #else
 424 #ifdef HAS_NDBM
 425 #ifdef _CX_UX
 426                 nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
 427 #else
 428                 nextdkey = dbm_nextkey(tb->tbl_dbm);
 429 #endif
 430 #else
 431                 nextdkey = nextkey(dkey);
 432 #endif
 433 #endif
 434 #ifdef HAS_GDBM
 435                 gdbm_delete(tb->tbl_dbm,dkey);
 436 #else
 437                 dbm_delete(tb->tbl_dbm,dkey);
 438 #endif
 439                 dkey = nextdkey;
 440             } while (dkey.dptr);        /* one way or another, this works */
 441         }
 442     }
 443     tb->tbl_dbm = 0;                    /* now clear just cache */
 444 #endif
 445     (void)hiterinit(tb);
 446     /*SUPPRESS 560*/
 447     while (hent = hiternext(tb)) {      /* concise but not very efficient */
 448         hentfree(ohent);
 449         ohent = hent;
 450     }
 451     hentfree(ohent);
 452 #ifdef SOME_DBM
 453     tb->tbl_dbm = old_dbm;
 454 #endif
 455 }
 456
 457 void
 458 hfree(tb,dodbm)
 459 register HASH *tb;
 460 int dodbm;
 461 {
 462     if (!tb)
 463         return;
 464     hfreeentries(tb,dodbm);
 465     Safefree(tb->tbl_array);
 466     Safefree(tb);
 467 }
 468
 469 int
 470 hiterinit(tb)
 471 register HASH *tb;
 472 {
 473     tb->tbl_riter = -1;
 474     tb->tbl_eiter = Null(HENT*);
 475     return tb->tbl_fill;
 476 }
 477
 478 HENT *
 479 hiternext(tb)
 480 register HASH *tb;
 481 {
 482     register HENT *entry;
 483 #ifdef SOME_DBM
 484     datum key;
 485 #endif
 486
 487     entry = tb->tbl_eiter;
 488 #ifdef SOME_DBM
 489     if (tb->tbl_dbm) {
 490         if (entry) {
 491 #ifdef HAS_GDBM
 492             key.dptr = entry->hent_key;
 493             key.dsize = entry->hent_klen;
 494             key = gdbm_nextkey(tb->tbl_dbm, key);
 495 #else
 496 #ifdef HAS_NDBM
 497 #ifdef _CX_UX
 498             key.dptr = entry->hent_key;
 499             key.dsize = entry->hent_klen;
 500             key = dbm_nextkey(tb->tbl_dbm, key);
 501 #else
 502             key = dbm_nextkey(tb->tbl_dbm);
 503 #endif /* _CX_UX */
 504 #else
 505             key.dptr = entry->hent_key;
 506             key.dsize = entry->hent_klen;
 507             key = nextkey(key);
 508 #endif
 509 #endif
 510         }
 511         else {
 512             Newz(504,entry, 1, HENT);
 513             tb->tbl_eiter = entry;
 514 #ifdef HAS_GDBM
 515             key = gdbm_firstkey(tb->tbl_dbm);
 516 #else
 517             key = dbm_firstkey(tb->tbl_dbm);
 518 #endif
 519         }
 520         entry->hent_key = key.dptr;
 521         entry->hent_klen = key.dsize;
 522         if (!key.dptr) {
 523             if (entry->hent_val)
 524                 str_free(entry->hent_val);
 525             Safefree(entry);
 526             tb->tbl_eiter = Null(HENT*);
 527             return Null(HENT*);
 528         }
 529         return entry;
 530     }
 531 #endif
 532     if (!tb->tbl_array)
 533         Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
 534     do {
 535         if (entry)
 536             entry = entry->hent_next;
 537         if (!entry) {
 538             tb->tbl_riter++;
 539             if (tb->tbl_riter > tb->tbl_max) {
 540                 tb->tbl_riter = -1;
 541                 break;
 542             }
 543             entry = tb->tbl_array[tb->tbl_riter];
 544         }
 545     } while (!entry);
 546
 547     tb->tbl_eiter = entry;
 548     return entry;
 549 }
 550
 551 char *
 552 hiterkey(entry,retlen)
 553 register HENT *entry;
 554 int *retlen;
 555 {
 556     *retlen = entry->hent_klen;
 557     return entry->hent_key;
 558 }
 559
 560 STR *
 561 hiterval(tb,entry)
 562 register HASH *tb;
 563 register HENT *entry;
 564 {
 565 #ifdef SOME_DBM
 566     datum key, content;
 567
 568     if (tb->tbl_dbm) {
 569         key.dptr = entry->hent_key;
 570         key.dsize = entry->hent_klen;
 571 #ifdef HAS_GDBM
 572         content = gdbm_fetch(tb->tbl_dbm,key);
 573 #else
 574         content = dbm_fetch(tb->tbl_dbm,key);
 575 #endif
 576         if (!entry->hent_val)
 577             entry->hent_val = Str_new(62,0);
 578         str_nset(entry->hent_val,content.dptr,content.dsize);
 579     }
 580 #endif
 581     return entry->hent_val;
 582 }
 583
 584 #ifdef SOME_DBM
 585
 586 #ifndef O_CREAT
 587 #  ifdef I_FCNTL
 588 #    include <fcntl.h>
 589 #  endif
 590 #  ifdef I_SYS_FILE
 591 #    include <sys/file.h>
 592 #  endif
 593 #endif
 594
 595 #ifndef O_RDONLY
 596 #define O_RDONLY 0
 597 #endif
 598 #ifndef O_RDWR
 599 #define O_RDWR 2
 600 #endif
 601 #ifndef O_CREAT
 602 #define O_CREAT 01000
 603 #endif
 604
 605 #ifdef HAS_ODBM
 606 static int dbmrefcnt = 0;
 607 #endif
 608
 609 bool
 610 hdbmopen(tb,fname,mode)
 611 register HASH *tb;
 612 char *fname;
 613 int mode;
 614 {
 615     if (!tb)
 616         return FALSE;
 617 #ifdef HAS_ODBM
 618     if (tb->tbl_dbm)    /* never really closed it */
 619         return TRUE;
 620 #endif
 621     if (tb->tbl_dbm) {
 622         hdbmclose(tb);
 623         tb->tbl_dbm = 0;
 624     }
 625     hclear(tb, FALSE);  /* clear cache */
 626 #ifdef HAS_GDBM
 627     if (mode >= 0)
 628         tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRCREAT,mode, (void *) NULL);
 629     if (!tb->tbl_dbm)
 630         tb->tbl_dbm = gdbm_open(fname, 0, GDBM_WRITER, mode, (void *) NULL);
 631     if (!tb->tbl_dbm)
 632         tb->tbl_dbm = gdbm_open(fname, 0, GDBM_READER, mode, (void *) NULL);
 633 #else
 634 #ifdef HAS_NDBM
 635     if (mode >= 0)
 636         tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
 637     if (!tb->tbl_dbm)
 638         tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
 639     if (!tb->tbl_dbm)
 640         tb->tbl_dbm = dbm_open(fname, O_RDONLY, mode);
 641 #else
 642     if (dbmrefcnt++)
 643         fatal("Old dbm can only open one database");
 644     sprintf(buf,"%s.dir",fname);
 645     if (stat(buf, &statbuf) < 0) {
 646         if (mode < 0 || close(creat(buf,mode)) < 0)
 647             return FALSE;
 648         sprintf(buf,"%s.pag",fname);
 649         if (close(creat(buf,mode)) < 0)
 650             return FALSE;
 651     }
 652     tb->tbl_dbm = dbminit(fname) >= 0;
 653 #endif
 654 #endif
 655     if (!tb->tbl_array && tb->tbl_dbm != 0)
 656         Newz(507,tb->tbl_array, tb->tbl_max + 1, HENT*);
 657     return tb->tbl_dbm != 0;
 658 }
 659
 660 void
 661 hdbmclose(tb)
 662 register HASH *tb;
 663 {
 664     if (tb && tb->tbl_dbm) {
 665 #ifdef HAS_GDBM
 666         gdbm_close(tb->tbl_dbm);
 667         tb->tbl_dbm = 0;
 668 #else
 669 #ifdef HAS_NDBM
 670         dbm_close(tb->tbl_dbm);
 671         tb->tbl_dbm = 0;
 672 #else
 673         /* dbmrefcnt--;  */     /* doesn't work, rats */
 674 #endif
 675 #endif
 676     }
 677     else if (dowarn)
 678         warn("Close on unopened dbm file");
 679 }
 680
 681 bool
 682 hdbmstore(tb,key,klen,str)
 683 register HASH *tb;
 684 char *key;
 685 unsigned int klen;
 686 register STR *str;
 687 {
 688     datum dkey, dcontent;
 689     int error;
 690
 691     if (!tb || !tb->tbl_dbm)
 692         return FALSE;
 693     dkey.dptr = key;
 694     dkey.dsize = klen;
 695     dcontent.dptr = str_get(str);
 696     dcontent.dsize = str->str_cur;
 697 #ifdef HAS_GDBM
 698     error = gdbm_store(tb->tbl_dbm, dkey, dcontent, GDBM_REPLACE);
 699 #else
 700     error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
 701 #endif
 702     if (error) {
 703         if (errno == EPERM)
 704             fatal("No write permission to dbm file");
 705         warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
 706 #ifdef HAS_NDBM
 707         dbm_clearerr(tb->tbl_dbm);
 708 #endif
 709     }
 710     return !error;
 711 }
 712 #endif /* SOME_DBM */