hash.c

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