hash.c

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