hash.c

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