hash.c

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