hash.c

   1 /* $Header: hash.c,v 3.0.1.5 90/08/13 22:18:27 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.5  90/08/13  22:18:27  lwall
  10  * patch28: defined(@array) and defined(%array) didn't work right
  11  *
  12  * Revision 3.0.1.4  90/08/09  03:50:22  lwall
  13  * patch19: dbmopen(name, 'filename', undef) now refrains from creating
  14  *
  15  * Revision 3.0.1.3  90/03/27  15:59:09  lwall
  16  * patch16: @dbmvalues{'foo','bar'} could use the same cache entry for both values
  17  *
  18  * Revision 3.0.1.2  89/12/21  20:03:39  lwall
  19  * patch7: errno may now be a macro with an lvalue
  20  *
  21  * Revision 3.0.1.1  89/11/11  04:34:18  lwall
  22  * patch2: CX/UX needed to set the key each time in associative iterators
  23  *
  24  * Revision 3.0  89/10/18  15:18:32  lwall
  25  * 3.0 baseline
  26  *
  27  */
  28
  29 #include "EXTERN.h"
  30 #include "perl.h"
  31
  32 static char coeff[] = {
  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                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1,
  40                 61,59,53,47,43,41,37,31,29,23,17,13,11,7,3,1};
  41
  42 STR *
  43 hfetch(tb,key,klen,lval)
  44 register HASH *tb;
  45 char *key;
  46 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 Nullstr;
  61     if (!tb->tbl_array) {
  62         if (lval)
  63             Newz(503,tb->tbl_array, tb->tbl_max + 1, HENT*);
  64         else
  65             return Nullstr;
  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;
  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         dcontent = dbm_fetch(tb->tbl_dbm,dkey);
 104         if (dcontent.dptr) {                    /* found one */
 105             str = Str_new(60,dcontent.dsize);
 106             str_nset(str,dcontent.dptr,dcontent.dsize);
 107             hstore(tb,key,klen,str,hash);               /* cache it */
 108             return str;
 109         }
 110     }
 111 #endif
 112     if (lval) {         /* gonna assign to this, so it better be there */
 113         str = Str_new(61,0);
 114         hstore(tb,key,klen,str,hash);
 115         return str;
 116     }
 117     return Nullstr;
 118 }
 119
 120 bool
 121 hstore(tb,key,klen,val,hash)
 122 register HASH *tb;
 123 char *key;
 124 int klen;
 125 STR *val;
 126 register int hash;
 127 {
 128     register char *s;
 129     register int i;
 130     register HENT *entry;
 131     register HENT **oentry;
 132     register int maxi;
 133
 134     if (!tb)
 135         return FALSE;
 136
 137     if (hash)
 138         ;
 139     else if (!tb->tbl_coeffsize)
 140         hash = *key + 128 * key[1] + 128 * key[klen-1];
 141     else {      /* use normal coefficients */
 142         if (klen < tb->tbl_coeffsize)
 143             maxi = klen;
 144         else
 145             maxi = tb->tbl_coeffsize;
 146         for (s=key,             i=0,    hash = 0;
 147                             i < maxi;
 148              s++,               i++,    hash *= 5) {
 149             hash += *s * coeff[i];
 150         }
 151     }
 152
 153     if (!tb->tbl_array)
 154         Newz(505,tb->tbl_array, tb->tbl_max + 1, HENT*);
 155
 156     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 157     i = 1;
 158
 159     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
 160         if (entry->hent_hash != hash)           /* strings can't be equal */
 161             continue;
 162         if (entry->hent_klen != klen)
 163             continue;
 164         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 165             continue;
 166         Safefree(entry->hent_val);
 167         entry->hent_val = val;
 168         return TRUE;
 169     }
 170     New(501,entry, 1, HENT);
 171
 172     entry->hent_klen = klen;
 173     entry->hent_key = nsavestr(key,klen);
 174     entry->hent_val = val;
 175     entry->hent_hash = hash;
 176     entry->hent_next = *oentry;
 177     *oentry = entry;
 178
 179     /* hdbmstore not necessary here because it's called from stabset() */
 180
 181     if (i) {                            /* initial entry? */
 182         tb->tbl_fill++;
 183 #ifdef SOME_DBM
 184         if (tb->tbl_dbm && tb->tbl_max >= DBM_CACHE_MAX)
 185             return FALSE;
 186 #endif
 187         if (tb->tbl_fill > tb->tbl_dosplit)
 188             hsplit(tb);
 189     }
 190 #ifdef SOME_DBM
 191     else if (tb->tbl_dbm) {             /* is this just a cache for dbm file? */
 192         void hentdelayfree();
 193
 194         entry = tb->tbl_array[hash & tb->tbl_max];
 195         oentry = &entry->hent_next;
 196         entry = *oentry;
 197         while (entry) { /* trim chain down to 1 entry */
 198             *oentry = entry->hent_next;
 199             hentdelayfree(entry);       /* no doubt they'll want this next. */
 200             entry = *oentry;
 201         }
 202     }
 203 #endif
 204
 205     return FALSE;
 206 }
 207
 208 STR *
 209 hdelete(tb,key,klen)
 210 register HASH *tb;
 211 char *key;
 212 int klen;
 213 {
 214     register char *s;
 215     register int i;
 216     register int hash;
 217     register HENT *entry;
 218     register HENT **oentry;
 219     STR *str;
 220     int maxi;
 221 #ifdef SOME_DBM
 222     datum dkey;
 223 #endif
 224
 225     if (!tb || !tb->tbl_array)
 226         return Nullstr;
 227     if (!tb->tbl_coeffsize)
 228         hash = *key + 128 * key[1] + 128 * key[klen-1];
 229     else {      /* use normal coefficients */
 230         if (klen < tb->tbl_coeffsize)
 231             maxi = klen;
 232         else
 233             maxi = tb->tbl_coeffsize;
 234         for (s=key,             i=0,    hash = 0;
 235                             i < maxi;
 236              s++,               i++,    hash *= 5) {
 237             hash += *s * coeff[i];
 238         }
 239     }
 240
 241     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
 242     entry = *oentry;
 243     i = 1;
 244     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
 245         if (entry->hent_hash != hash)           /* strings can't be equal */
 246             continue;
 247         if (entry->hent_klen != klen)
 248             continue;
 249         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 250             continue;
 251         *oentry = entry->hent_next;
 252         str = str_static(entry->hent_val);
 253         hentfree(entry);
 254         if (i)
 255             tb->tbl_fill--;
 256 #ifdef SOME_DBM
 257       do_dbm_delete:
 258         if (tb->tbl_dbm) {
 259             dkey.dptr = key;
 260             dkey.dsize = klen;
 261             dbm_delete(tb->tbl_dbm,dkey);
 262         }
 263 #endif
 264         return str;
 265     }
 266 #ifdef SOME_DBM
 267     str = Nullstr;
 268     goto do_dbm_delete;
 269 #else
 270     return Nullstr;
 271 #endif
 272 }
 273
 274 hsplit(tb)
 275 HASH *tb;
 276 {
 277     int oldsize = tb->tbl_max + 1;
 278     register int newsize = oldsize * 2;
 279     register int i;
 280     register HENT **a;
 281     register HENT **b;
 282     register HENT *entry;
 283     register HENT **oentry;
 284
 285     a = tb->tbl_array;
 286     Renew(a, newsize, HENT*);
 287     Zero(&a[oldsize], oldsize, HENT*);          /* zero 2nd half*/
 288     tb->tbl_max = --newsize;
 289     tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
 290     tb->tbl_array = a;
 291
 292     for (i=0; i<oldsize; i++,a++) {
 293         if (!*a)                                /* non-existent */
 294             continue;
 295         b = a+oldsize;
 296         for (oentry = a, entry = *a; entry; entry = *oentry) {
 297             if ((entry->hent_hash & newsize) != i) {
 298                 *oentry = entry->hent_next;
 299                 entry->hent_next = *b;
 300                 if (!*b)
 301                     tb->tbl_fill++;
 302                 *b = entry;
 303                 continue;
 304             }
 305             else
 306                 oentry = &entry->hent_next;
 307         }
 308         if (!*a)                                /* everything moved */
 309             tb->tbl_fill--;
 310     }
 311 }
 312
 313 HASH *
 314 hnew(lookat)
 315 unsigned int lookat;
 316 {
 317     register HASH *tb;
 318
 319     Newz(502,tb, 1, HASH);
 320     if (lookat) {
 321         tb->tbl_coeffsize = lookat;
 322         tb->tbl_max = 7;                /* it's a normal associative array */
 323         tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
 324     }
 325     else {
 326         tb->tbl_max = 127;              /* it's a symbol table */
 327         tb->tbl_dosplit = 128;          /* so never split */
 328     }
 329     tb->tbl_fill = 0;
 330 #ifdef SOME_DBM
 331     tb->tbl_dbm = 0;
 332 #endif
 333     (void)hiterinit(tb);        /* so each() will start off right */
 334     return tb;
 335 }
 336
 337 void
 338 hentfree(hent)
 339 register HENT *hent;
 340 {
 341     if (!hent)
 342         return;
 343     str_free(hent->hent_val);
 344     Safefree(hent->hent_key);
 345     Safefree(hent);
 346 }
 347
 348 void
 349 hentdelayfree(hent)
 350 register HENT *hent;
 351 {
 352     if (!hent)
 353         return;
 354     str_2static(hent->hent_val);        /* free between statements */
 355     Safefree(hent->hent_key);
 356     Safefree(hent);
 357 }
 358
 359 void
 360 hclear(tb)
 361 register HASH *tb;
 362 {
 363     register HENT *hent;
 364     register HENT *ohent = Null(HENT*);
 365
 366     if (!tb || !tb->tbl_array)
 367         return;
 368     (void)hiterinit(tb);
 369     while (hent = hiternext(tb)) {      /* concise but not very efficient */
 370         hentfree(ohent);
 371         ohent = hent;
 372     }
 373     hentfree(ohent);
 374     tb->tbl_fill = 0;
 375 #ifndef lint
 376     (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
 377 #endif
 378 }
 379
 380 void
 381 hfree(tb)
 382 register HASH *tb;
 383 {
 384     register HENT *hent;
 385     register HENT *ohent = Null(HENT*);
 386
 387     if (!tb)
 388         return;
 389     (void)hiterinit(tb);
 390     while (hent = hiternext(tb)) {
 391         hentfree(ohent);
 392         ohent = hent;
 393     }
 394     hentfree(ohent);
 395     Safefree(tb->tbl_array);
 396     Safefree(tb);
 397 }
 398
 399 int
 400 hiterinit(tb)
 401 register HASH *tb;
 402 {
 403     tb->tbl_riter = -1;
 404     tb->tbl_eiter = Null(HENT*);
 405     return tb->tbl_fill;
 406 }
 407
 408 HENT *
 409 hiternext(tb)
 410 register HASH *tb;
 411 {
 412     register HENT *entry;
 413 #ifdef SOME_DBM
 414     datum key;
 415 #endif
 416
 417     entry = tb->tbl_eiter;
 418 #ifdef SOME_DBM
 419     if (tb->tbl_dbm) {
 420         if (entry) {
 421 #ifdef NDBM
 422 #ifdef _CX_UX
 423             key.dptr = entry->hent_key;
 424             key.dsize = entry->hent_klen;
 425             key = dbm_nextkey(tb->tbl_dbm, key);
 426 #else
 427             key = dbm_nextkey(tb->tbl_dbm);
 428 #endif /* _CX_UX */
 429 #else
 430             key.dptr = entry->hent_key;
 431             key.dsize = entry->hent_klen;
 432             key = nextkey(key);
 433 #endif
 434         }
 435         else {
 436             Newz(504,entry, 1, HENT);
 437             tb->tbl_eiter = entry;
 438             key = dbm_firstkey(tb->tbl_dbm);
 439         }
 440         entry->hent_key = key.dptr;
 441         entry->hent_klen = key.dsize;
 442         if (!key.dptr) {
 443             if (entry->hent_val)
 444                 str_free(entry->hent_val);
 445             Safefree(entry);
 446             tb->tbl_eiter = Null(HENT*);
 447             return Null(HENT*);
 448         }
 449         return entry;
 450     }
 451 #endif
 452     if (!tb->tbl_array)
 453         Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
 454     do {
 455         if (entry)
 456             entry = entry->hent_next;
 457         if (!entry) {
 458             tb->tbl_riter++;
 459             if (tb->tbl_riter > tb->tbl_max) {
 460                 tb->tbl_riter = -1;
 461                 break;
 462             }
 463             entry = tb->tbl_array[tb->tbl_riter];
 464         }
 465     } while (!entry);
 466
 467     tb->tbl_eiter = entry;
 468     return entry;
 469 }
 470
 471 char *
 472 hiterkey(entry,retlen)
 473 register HENT *entry;
 474 int *retlen;
 475 {
 476     *retlen = entry->hent_klen;
 477     return entry->hent_key;
 478 }
 479
 480 STR *
 481 hiterval(tb,entry)
 482 register HASH *tb;
 483 register HENT *entry;
 484 {
 485 #ifdef SOME_DBM
 486     datum key, content;
 487
 488     if (tb->tbl_dbm) {
 489         key.dptr = entry->hent_key;
 490         key.dsize = entry->hent_klen;
 491         content = dbm_fetch(tb->tbl_dbm,key);
 492         if (!entry->hent_val)
 493             entry->hent_val = Str_new(62,0);
 494         str_nset(entry->hent_val,content.dptr,content.dsize);
 495     }
 496 #endif
 497     return entry->hent_val;
 498 }
 499
 500 #ifdef SOME_DBM
 501 #if     defined(FCNTL) && ! defined(O_CREAT)
 502 #include <fcntl.h>
 503 #endif
 504
 505 #ifndef O_RDONLY
 506 #define O_RDONLY 0
 507 #endif
 508 #ifndef O_RDWR
 509 #define O_RDWR 2
 510 #endif
 511 #ifndef O_CREAT
 512 #define O_CREAT 01000
 513 #endif
 514
 515 #ifndef NDBM
 516 static int dbmrefcnt = 0;
 517 #endif
 518
 519 bool
 520 hdbmopen(tb,fname,mode)
 521 register HASH *tb;
 522 char *fname;
 523 int mode;
 524 {
 525     if (!tb)
 526         return FALSE;
 527 #ifndef NDBM
 528     if (tb->tbl_dbm)    /* never really closed it */
 529         return TRUE;
 530 #endif
 531     if (tb->tbl_dbm) {
 532         hdbmclose(tb);
 533         tb->tbl_dbm = 0;
 534     }
 535     hclear(tb);
 536 #ifdef NDBM
 537     if (mode >= 0)
 538         tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
 539     if (!tb->tbl_dbm)
 540         tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
 541 #else
 542     if (dbmrefcnt++)
 543         fatal("Old dbm can only open one database");
 544     sprintf(buf,"%s.dir",fname);
 545     if (stat(buf, &statbuf) < 0) {
 546         if (mode < 0 || close(creat(buf,mode)) < 0)
 547             return FALSE;
 548         sprintf(buf,"%s.pag",fname);
 549         if (close(creat(buf,mode)) < 0)
 550             return FALSE;
 551     }
 552     tb->tbl_dbm = dbminit(fname) >= 0;
 553 #endif
 554     return tb->tbl_dbm != 0;
 555 }
 556
 557 void
 558 hdbmclose(tb)
 559 register HASH *tb;
 560 {
 561     if (tb && tb->tbl_dbm) {
 562 #ifdef NDBM
 563         dbm_close(tb->tbl_dbm);
 564         tb->tbl_dbm = 0;
 565 #else
 566         /* dbmrefcnt--;  */     /* doesn't work, rats */
 567 #endif
 568     }
 569     else if (dowarn)
 570         warn("Close on unopened dbm file");
 571 }
 572
 573 bool
 574 hdbmstore(tb,key,klen,str)
 575 register HASH *tb;
 576 char *key;
 577 int klen;
 578 register STR *str;
 579 {
 580     datum dkey, dcontent;
 581     int error;
 582
 583     if (!tb || !tb->tbl_dbm)
 584         return FALSE;
 585     dkey.dptr = key;
 586     dkey.dsize = klen;
 587     dcontent.dptr = str_get(str);
 588     dcontent.dsize = str->str_cur;
 589     error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
 590     if (error) {
 591         if (errno == EPERM)
 592             fatal("No write permission to dbm file");
 593         warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
 594 #ifdef NDBM
 595         dbm_clearerr(tb->tbl_dbm);
 596 #endif
 597     }
 598     return !error;
 599 }
 600 #endif /* SOME_DBM */