home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / language / perl / Source / C / Hash < prev    next >
Encoding:
Text File  |  1990-11-08  |  14.4 KB  |  676 lines
  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 PROTO((HASH *, int));
  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.     entry = tb->tbl_array[hash & tb->tbl_max];
  204.     oentry = &entry->hent_next;
  205.     entry = *oentry;
  206.     while (entry) {    /* trim chain down to 1 entry */
  207.         *oentry = entry->hent_next;
  208.         hentdelayfree(entry);    /* no doubt they'll want this next. */
  209.         entry = *oentry;
  210.     }
  211.     }
  212. #endif
  213.  
  214.     return FALSE;
  215. }
  216.  
  217. STR *
  218. hdelete(tb,key,klen)
  219. register HASH *tb;
  220. char *key;
  221. unsigned int klen;
  222. {
  223.     register char *s;
  224.     register int i;
  225.     register int hash;
  226.     register HENT *entry;
  227.     register HENT **oentry;
  228.     STR *str;
  229.     int maxi;
  230. #ifdef SOME_DBM
  231.     datum dkey;
  232. #endif
  233.  
  234.     if (!tb || !tb->tbl_array)
  235.     return Nullstr;
  236.     if (!tb->tbl_coeffsize)
  237.     hash = *key + 128 * key[1] + 128 * key[klen-1];
  238.     else {    /* use normal coefficients */
  239.     if (klen < tb->tbl_coeffsize)
  240.         maxi = klen;
  241.     else
  242.         maxi = tb->tbl_coeffsize;
  243.     for (s=key,        i=0,    hash = 0;
  244.                 i < maxi;
  245.          s++,        i++,    hash *= 5) {
  246.         hash += *s * coeff[i];
  247.     }
  248.     }
  249.  
  250.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  251.     entry = *oentry;
  252.     i = 1;
  253.     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
  254.     if (entry->hent_hash != hash)        /* strings can't be equal */
  255.         continue;
  256.     if (entry->hent_klen != klen)
  257.         continue;
  258.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  259.         continue;
  260.     *oentry = entry->hent_next;
  261.     str = str_static(entry->hent_val);
  262.     hentfree(entry);
  263.     if (i)
  264.         tb->tbl_fill--;
  265. #ifdef SOME_DBM
  266.       do_dbm_delete:
  267.     if (tb->tbl_dbm) {
  268.         dkey.dptr = key;
  269.         dkey.dsize = klen;
  270.         dbm_delete(tb->tbl_dbm,dkey);
  271.     }
  272. #endif
  273.     return str;
  274.     }
  275. #ifdef SOME_DBM
  276.     str = Nullstr;
  277.     goto do_dbm_delete;
  278. #else
  279.     return Nullstr;
  280. #endif
  281. }
  282.  
  283. void
  284. hsplit(tb)
  285. HASH *tb;
  286. {
  287.     int oldsize = tb->tbl_max + 1;
  288.     register int newsize = oldsize * 2;
  289.     register int i;
  290.     register HENT **a;
  291.     register HENT **b;
  292.     register HENT *entry;
  293.     register HENT **oentry;
  294.  
  295.     a = tb->tbl_array;
  296.     Renew(a, newsize, HENT*);
  297.     Zero(&a[oldsize], oldsize, HENT*);        /* zero 2nd half*/
  298.     tb->tbl_max = --newsize;
  299.     tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
  300.     tb->tbl_array = a;
  301.  
  302.     for (i=0; i<oldsize; i++,a++) {
  303.     if (!*a)                /* non-existent */
  304.         continue;
  305.     b = a+oldsize;
  306.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  307.         if ((entry->hent_hash & newsize) != i) {
  308.         *oentry = entry->hent_next;
  309.         entry->hent_next = *b;
  310.         if (!*b)
  311.             tb->tbl_fill++;
  312.         *b = entry;
  313.         continue;
  314.         }
  315.         else
  316.         oentry = &entry->hent_next;
  317.     }
  318.     if (!*a)                /* everything moved */
  319.         tb->tbl_fill--;
  320.     }
  321. }
  322.  
  323. HASH *
  324. hnew(lookat)
  325. unsigned int lookat;
  326. {
  327.     register HASH *tb;
  328.  
  329.     Newz(502,tb, 1, HASH);
  330.     if (lookat) {
  331.     tb->tbl_coeffsize = lookat;
  332.     tb->tbl_max = 7;        /* it's a normal associative array */
  333.     tb->tbl_dosplit = tb->tbl_max * FILLPCT / 100;
  334.     }
  335.     else {
  336.     tb->tbl_max = 127;        /* it's a symbol table */
  337.     tb->tbl_dosplit = 128;        /* so never split */
  338.     }
  339.     tb->tbl_fill = 0;
  340. #ifdef SOME_DBM
  341.     tb->tbl_dbm = 0;
  342. #endif
  343.     (void)hiterinit(tb);    /* so each() will start off right */
  344.     return tb;
  345. }
  346.  
  347. void
  348. hentfree(hent)
  349. register HENT *hent;
  350. {
  351.     if (!hent)
  352.     return;
  353.     str_free(hent->hent_val);
  354.     Safefree(hent->hent_key);
  355.     Safefree(hent);
  356. }
  357.  
  358. void
  359. hentdelayfree(hent)
  360. register HENT *hent;
  361. {
  362.     if (!hent)
  363.     return;
  364.     str_2static(hent->hent_val);    /* free between statements */
  365.     Safefree(hent->hent_key);
  366.     Safefree(hent);
  367. }
  368.  
  369. void
  370. hclear(tb,dodbm)
  371. register HASH *tb;
  372. int dodbm;
  373. {
  374.     if (!tb)
  375.     return;
  376.     hfreeentries(tb,dodbm);
  377.     tb->tbl_fill = 0;
  378. #ifndef lint
  379.     if (tb->tbl_array)
  380.     (void)bzero((char*)tb->tbl_array, (tb->tbl_max + 1) * sizeof(HENT*));
  381. #endif
  382. }
  383.  
  384. static void
  385. hfreeentries(tb,dodbm)
  386. register HASH *tb;
  387. int dodbm;
  388. {
  389.     register HENT *hent;
  390.     register HENT *ohent = Null(HENT*);
  391. #ifdef SOME_DBM
  392.     datum dkey;
  393.     datum nextdkey;
  394. #ifdef GDBM
  395.     DBM *old_dbm;
  396. #else
  397. #ifdef NDBM
  398.     DBM *old_dbm;
  399. #else
  400.     int old_dbm;
  401. #endif
  402. #endif
  403. #endif
  404.  
  405.     if (!tb || !tb->tbl_array)
  406.     return;
  407. #ifdef SOME_DBM
  408.     if ((old_dbm = tb->tbl_dbm) != Null(DBM*) && dodbm) {
  409.     while (dkey = dbm_firstkey(tb->tbl_dbm), dkey.dptr) {
  410.         do {
  411. #if defined(GDBM) || defined(NDBM)
  412.         nextdkey = dbm_nextkey(tb->tbl_dbm, dkey);
  413. #else
  414.         nextdkey = dbm_nextkey(tb->tbl_dbm);
  415. #endif
  416.         dbm_delete(tb->tbl_dbm,dkey);
  417.         dkey = nextdkey;
  418.         } while (dkey.dptr);    /* one way or another, this works */
  419.     }
  420.     }
  421.     tb->tbl_dbm = 0;            /* now clear just cache */
  422. #endif
  423.     (void)hiterinit(tb);
  424.     while ((hent = hiternext(tb)) != Null(HENT*)) {    /* concise but not very efficient */
  425.     hentfree(ohent);
  426.     ohent = hent;
  427.     }
  428.     hentfree(ohent);
  429.  
  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 GDBM
  470.         key.dptr = entry->hent_key;
  471.         key.dsize = entry->hent_klen;
  472.         key = dbm_nextkey(tb->tbl_dbm, key);
  473. #else /* GDBM */
  474. #ifdef NDBM
  475. #ifdef _CX_UX
  476.         key.dptr = entry->hent_key;
  477.         key.dsize = entry->hent_klen;
  478.         key = dbm_nextkey(tb->tbl_dbm, key);
  479. #else
  480.         key = dbm_nextkey(tb->tbl_dbm);
  481. #endif /* _CX_UX */
  482. #else /* NDBM */
  483.         key.dptr = entry->hent_key;
  484.         key.dsize = entry->hent_klen;
  485.         key = nextkey(key);
  486. #endif /* NDBM */
  487. #endif /* GDBM */
  488.     }
  489.     else {
  490.         Newz(504,entry, 1, HENT);
  491.         tb->tbl_eiter = entry;
  492.         key = dbm_firstkey(tb->tbl_dbm);
  493.     }
  494.     entry->hent_key = key.dptr;
  495.     entry->hent_klen = key.dsize;
  496.     if (!key.dptr) {
  497.         if (entry->hent_val)
  498.         str_free(entry->hent_val);
  499.         Safefree(entry);
  500.         tb->tbl_eiter = Null(HENT*);
  501.         return Null(HENT*);
  502.     }
  503.     return entry;
  504.     }
  505. #endif
  506.     if (!tb->tbl_array)
  507.     Newz(506,tb->tbl_array, tb->tbl_max + 1, HENT*);
  508.     do {
  509.     if (entry)
  510.         entry = entry->hent_next;
  511.     if (!entry) {
  512.         tb->tbl_riter++;
  513.         if (tb->tbl_riter > tb->tbl_max) {
  514.         tb->tbl_riter = -1;
  515.         break;
  516.         }
  517.         entry = tb->tbl_array[tb->tbl_riter];
  518.     }
  519.     } while (!entry);
  520.  
  521.     tb->tbl_eiter = entry;
  522.     return entry;
  523. }
  524.  
  525. char *
  526. hiterkey(entry,retlen)
  527. register HENT *entry;
  528. int *retlen;
  529. {
  530.     *retlen = entry->hent_klen;
  531.     return entry->hent_key;
  532. }
  533.  
  534. STR *
  535. hiterval(tb,entry)
  536. register HASH *tb;
  537. register HENT *entry;
  538. {
  539. #ifdef SOME_DBM
  540.     datum key, content;
  541.  
  542.     if (tb->tbl_dbm) {
  543.     key.dptr = entry->hent_key;
  544.     key.dsize = entry->hent_klen;
  545.     content = dbm_fetch(tb->tbl_dbm,key);
  546.     if (!entry->hent_val)
  547.         entry->hent_val = Str_new(62,0);
  548.     str_nset(entry->hent_val,content.dptr,content.dsize);
  549.     }
  550. #endif
  551.     return entry->hent_val;
  552. }
  553.  
  554. #ifdef SOME_DBM
  555. #if    defined(FCNTL) && ! defined(O_CREAT)
  556. #include <fcntl.h>
  557. #endif
  558.  
  559. #ifndef O_RDONLY
  560. #define O_RDONLY 0
  561. #endif
  562. #ifndef O_RDWR
  563. #define O_RDWR 2
  564. #endif
  565. #ifndef O_CREAT
  566. #define O_CREAT 01000
  567. #endif
  568.  
  569. #ifndef GDBM
  570. #ifndef NDBM
  571. static int dbmrefcnt = 0;
  572. #endif
  573. #endif
  574.  
  575. bool
  576. hdbmopen(tb,fname,mode)
  577. register HASH *tb;
  578. char *fname;
  579. int mode;
  580. {
  581. #ifdef GDBM
  582.     USE(mode);
  583. #endif
  584.  
  585.     if (!tb)
  586.     return FALSE;
  587. #ifdef ODBM
  588.     if (tb->tbl_dbm)    /* never really closed it */
  589.     return TRUE;
  590. #endif
  591.     if (tb->tbl_dbm) {
  592.     hdbmclose(tb);
  593.     tb->tbl_dbm = 0;
  594.     }
  595.     hclear(tb, FALSE);    /* clear cache */
  596. #ifdef GDBM
  597.     if (mode >= 0)
  598.     tb->tbl_dbm = gdbm_open(fname,BUFSIZ,DBM_WRITER,fatal);
  599.     if (tb->tbl_dbm)
  600.     stamp(fname);    /* Correct duff timestamp */
  601.     else
  602.     tb->tbl_dbm = gdbm_open(fname,BUFSIZ,DBM_READER,fatal);
  603. #else /* GDBM */
  604. #ifdef NDBM
  605.     if (mode >= 0)
  606.     tb->tbl_dbm = dbm_open(fname, O_RDWR|O_CREAT, mode);
  607.     if (!tb->tbl_dbm)
  608.     tb->tbl_dbm = dbm_open(fname, O_RDWR, mode);
  609.     if (!tb->tbl_dbm)
  610.     tb->tbl_dbm = dbm_open(fname, O_RDONLY, mode);
  611. #else /* NDBM */
  612.     if (dbmrefcnt++)
  613.     fatal("Old dbm can only open one database");
  614.     sprintf(buf,"%s.dir",fname);
  615.     if (stat(buf, &statbuf) < 0) {
  616.     if (mode < 0 || close(creat(buf,mode)) < 0)
  617.         return FALSE;
  618.     sprintf(buf,"%s.pag",fname);
  619.     if (close(creat(buf,mode)) < 0)
  620.         return FALSE;
  621.     }
  622.     tb->tbl_dbm = dbminit(fname) >= 0;
  623. #endif /* NDBM */
  624. #endif /* GDBM */
  625.     if (!tb->tbl_array && tb->tbl_dbm != 0)
  626.     Newz(507,tb->tbl_array, tb->tbl_max + 1, HENT*);
  627.     return tb->tbl_dbm != 0;
  628. }
  629.  
  630. void
  631. hdbmclose(tb)
  632. register HASH *tb;
  633. {
  634.     if (tb && tb->tbl_dbm) {
  635. #ifndef ODBM
  636.     dbm_close(tb->tbl_dbm);
  637.     tb->tbl_dbm = 0;
  638. #else
  639.     /* dbmrefcnt--;  */    /* doesn't work, rats */
  640. #endif
  641.     }
  642.     else if (dowarn)
  643.     warn("Close on unopened dbm file");
  644. }
  645.  
  646. bool
  647. hdbmstore(tb,key,klen,str)
  648. register HASH *tb;
  649. char *key;
  650. unsigned int klen;
  651. register STR *str;
  652. {
  653.     datum dkey, dcontent;
  654.     int error;
  655.  
  656.     if (!tb || !tb->tbl_dbm)
  657.     return FALSE;
  658.     dkey.dptr = key;
  659.     dkey.dsize = klen;
  660.     dcontent.dptr = str_get(str);
  661.     dcontent.dsize = str->str_cur;
  662.     error = dbm_store(tb->tbl_dbm, dkey, dcontent, DBM_REPLACE);
  663.     if (error) {
  664. #ifndef ARM
  665.     if (errno == EPERM)
  666.         fatal("No write permission to dbm file");
  667. #endif
  668.     warn("dbm store returned %d, errno %d, key \"%s\"",error,errno,key);
  669. #ifdef NDBM
  670.         dbm_clearerr(tb->tbl_dbm);
  671. #endif
  672.     }
  673.     return !error;
  674. }
  675. #endif /* SOME_DBM */
  676.