hash.c

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