hash.c

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