home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / MacPerl 5.0.3 / MacPerl Source ƒ / Perl5 / hv.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-09-18  |  10.6 KB  |  546 lines  |  [TEXT/MPS ]
  1. /*    hv.c
  2.  *
  3.  *    Copyright (c) 1991-1994, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  */
  9.  
  10. /*
  11.  * "I sit beside the fire and think of all that I have seen."  --Bilbo
  12.  */
  13.  
  14. #include "EXTERN.h"
  15. #include "perl.h"
  16.  
  17. static void hsplit _((HV *hv));
  18. static void hfreeentries _((HV *hv));
  19.  
  20. SV**
  21. hv_fetch(hv,key,klen,lval)
  22. HV *hv;
  23. char *key;
  24. U32 klen;
  25. I32 lval;
  26. {
  27.     register XPVHV* xhv;
  28.     register char *s;
  29.     register I32 i;
  30.     register I32 hash;
  31.     register HE *entry;
  32.     SV *sv;
  33.  
  34.     if (!hv)
  35.     return 0;
  36.  
  37.     if (SvRMAGICAL(hv)) {
  38.     if (mg_find((SV*)hv,'P')) {
  39.         sv = sv_newmortal();
  40.         mg_copy((SV*)hv, sv, key, klen);
  41.         Sv = sv;
  42.         return &Sv;
  43.     }
  44.     }
  45.  
  46.     xhv = (XPVHV*)SvANY(hv);
  47.     if (!xhv->xhv_array) {
  48.     if (lval 
  49. #ifdef DYNAMIC_ENV_FETCH  /* if it's an %ENV lookup, we may get it on the fly */
  50.              || (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME))
  51. #endif
  52.                                                               )
  53.         Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
  54.     else
  55.         return 0;
  56.     }
  57.  
  58.     i = klen;
  59.     hash = 0;
  60.     s = key;
  61.     while (i--)
  62.     hash = hash * 33 + *s++;
  63.  
  64.     entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
  65.     for (; entry; entry = entry->hent_next) {
  66.     if (entry->hent_hash != hash)        /* strings can't be equal */
  67.         continue;
  68.     if (entry->hent_klen != klen)
  69.         continue;
  70.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  71.         continue;
  72.     return &entry->hent_val;
  73.     }
  74. #ifdef DYNAMIC_ENV_FETCH  /* %ENV lookup?  If so, try to fetch the value now */
  75.     if (HvNAME(hv) && strEQ(HvNAME(hv),ENV_HV_NAME)) {
  76.       char *gotenv;
  77.  
  78.       gotenv = my_getenv(key);
  79.       if (gotenv != NULL) {
  80.         sv = newSVpv(gotenv,strlen(gotenv));
  81.         return hv_store(hv,key,klen,sv,hash);
  82.       }
  83.     }
  84. #endif
  85.     if (lval) {        /* gonna assign to this, so it better be there */
  86.     sv = NEWSV(61,0);
  87.     return hv_store(hv,key,klen,sv,hash);
  88.     }
  89.     return 0;
  90. }
  91.  
  92. SV**
  93. hv_store(hv,key,klen,val,hash)
  94. HV *hv;
  95. char *key;
  96. U32 klen;
  97. SV *val;
  98. register U32 hash;
  99. {
  100.     register XPVHV* xhv;
  101.     register char *s;
  102.     register I32 i;
  103.     register HE *entry;
  104.     register HE **oentry;
  105.  
  106.     if (!hv)
  107.     return 0;
  108.  
  109.     xhv = (XPVHV*)SvANY(hv);
  110.     if (SvMAGICAL(hv)) {
  111.     mg_copy((SV*)hv, val, key, klen);
  112. #ifndef OVERLOAD
  113.     if (!xhv->xhv_array)
  114.         return 0;
  115. #else
  116.     if (!xhv->xhv_array && (SvMAGIC(hv)->mg_type != 'A'
  117.                 || SvMAGIC(hv)->mg_moremagic))
  118.       return 0;
  119. #endif /* OVERLOAD */
  120.     }
  121.     if (!hash) {
  122.     i = klen;
  123.     s = key;
  124.     while (i--)
  125.     hash = hash * 33 + *s++;
  126.     }
  127.  
  128.     if (!xhv->xhv_array)
  129.     Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
  130.  
  131.     oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_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.     SvREFCNT_dec(entry->hent_val);
  142.     entry->hent_val = val;
  143.     return &entry->hent_val;
  144.     }
  145.     New(501,entry, 1, HE);
  146.  
  147.     entry->hent_klen = klen;
  148.     entry->hent_key = savepvn(key,klen);
  149.     entry->hent_val = val;
  150.     entry->hent_hash = hash;
  151.     entry->hent_next = *oentry;
  152.     *oentry = entry;
  153.  
  154.     xhv->xhv_keys++;
  155.     if (i) {                /* initial entry? */
  156.     ++xhv->xhv_fill;
  157.     if (xhv->xhv_keys > xhv->xhv_max)
  158.         hsplit(hv);
  159.     }
  160.  
  161.     return &entry->hent_val;
  162. }
  163.  
  164. SV *
  165. hv_delete(hv,key,klen)
  166. HV *hv;
  167. char *key;
  168. U32 klen;
  169. {
  170.     register XPVHV* xhv;
  171.     register char *s;
  172.     register I32 i;
  173.     register I32 hash;
  174.     register HE *entry;
  175.     register HE **oentry;
  176.     SV *sv;
  177.  
  178.     if (!hv)
  179.     return Nullsv;
  180.     if (SvRMAGICAL(hv)) {
  181.     sv = *hv_fetch(hv, key, klen, TRUE);
  182.     mg_clear(sv);
  183.     if (mg_find(sv, 'p')) {
  184.         sv_unmagic(sv, 'p');    /* No longer an element */
  185.         return sv;
  186.     }
  187.     }
  188.     xhv = (XPVHV*)SvANY(hv);
  189.     if (!xhv->xhv_array)
  190.     return Nullsv;
  191.     i = klen;
  192.     hash = 0;
  193.     s = key;
  194.     while (i--)
  195.     hash = hash * 33 + *s++;
  196.  
  197.     oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
  198.     entry = *oentry;
  199.     i = 1;
  200.     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
  201.     if (entry->hent_hash != hash)        /* strings can't be equal */
  202.         continue;
  203.     if (entry->hent_klen != klen)
  204.         continue;
  205.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  206.         continue;
  207.     *oentry = entry->hent_next;
  208.     if (i && !*oentry)
  209.         xhv->xhv_fill--;
  210.     sv = sv_mortalcopy(entry->hent_val);
  211.     if (entry == xhv->xhv_eiter)
  212.         entry->hent_klen = -1;
  213.     else
  214.         he_free(entry);
  215.     --xhv->xhv_keys;
  216.     return sv;
  217.     }
  218.     return Nullsv;
  219. }
  220.  
  221. bool
  222. hv_exists(hv,key,klen)
  223. HV *hv;
  224. char *key;
  225. U32 klen;
  226. {
  227.     register XPVHV* xhv;
  228.     register char *s;
  229.     register I32 i;
  230.     register I32 hash;
  231.     register HE *entry;
  232.     SV *sv;
  233.  
  234.     if (!hv)
  235.     return 0;
  236.  
  237.     if (SvRMAGICAL(hv)) {
  238.     if (mg_find((SV*)hv,'P')) {
  239.         sv = sv_newmortal();
  240.         mg_copy((SV*)hv, sv, key, klen); 
  241.         magic_existspack(sv, mg_find(sv, 'p'));
  242.         return SvTRUE(sv);
  243.     }
  244.     }
  245.  
  246.     xhv = (XPVHV*)SvANY(hv);
  247.     if (!xhv->xhv_array)
  248.     return 0; 
  249.  
  250.     i = klen;
  251.     hash = 0;
  252.     s = key;
  253.     while (i--)
  254.     hash = hash * 33 + *s++;
  255.  
  256.     entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
  257.     for (; entry; entry = entry->hent_next) {
  258.     if (entry->hent_hash != hash)        /* strings can't be equal */
  259.         continue;
  260.     if (entry->hent_klen != klen)
  261.         continue;
  262.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  263.         continue;
  264.     return TRUE;
  265.     }
  266.     return FALSE;
  267. }
  268.  
  269. static void
  270. hsplit(hv)
  271. HV *hv;
  272. {
  273.     register XPVHV* xhv = (XPVHV*)SvANY(hv);
  274.     I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
  275.     register I32 newsize = oldsize * 2;
  276.     register I32 i;
  277.     register HE **a;
  278.     register HE **b;
  279.     register HE *entry;
  280.     register HE **oentry;
  281.  
  282.     a = (HE**)xhv->xhv_array;
  283.     nomemok = TRUE;
  284.     Renew(a, newsize, HE*);
  285.     nomemok = FALSE;
  286.     Zero(&a[oldsize], oldsize, HE*);        /* zero 2nd half*/
  287.     xhv->xhv_max = --newsize;
  288.     xhv->xhv_array = (char*)a;
  289.  
  290.     for (i=0; i<oldsize; i++,a++) {
  291.     if (!*a)                /* non-existent */
  292.         continue;
  293.     b = a+oldsize;
  294.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  295.         if ((entry->hent_hash & newsize) != i) {
  296.         *oentry = entry->hent_next;
  297.         entry->hent_next = *b;
  298.         if (!*b)
  299.             xhv->xhv_fill++;
  300.         *b = entry;
  301.         continue;
  302.         }
  303.         else
  304.         oentry = &entry->hent_next;
  305.     }
  306.     if (!*a)                /* everything moved */
  307.         xhv->xhv_fill--;
  308.     }
  309. }
  310.  
  311. HV *
  312. newHV()
  313. {
  314.     register HV *hv;
  315.     register XPVHV* xhv;
  316.  
  317.     hv = (HV*)NEWSV(502,0);
  318.     sv_upgrade((SV *)hv, SVt_PVHV);
  319.     xhv = (XPVHV*)SvANY(hv);
  320.     SvPOK_off(hv);
  321.     SvNOK_off(hv);
  322.     xhv->xhv_max = 7;        /* start with 8 buckets */
  323.     xhv->xhv_fill = 0;
  324.     xhv->xhv_pmroot = 0;
  325.     (void)hv_iterinit(hv);    /* so each() will start off right */
  326.     return hv;
  327. }
  328.  
  329. void
  330. he_free(hent)
  331. register HE *hent;
  332. {
  333.     if (!hent)
  334.     return;
  335.     SvREFCNT_dec(hent->hent_val);
  336.     Safefree(hent->hent_key);
  337.     Safefree(hent);
  338. }
  339.  
  340. void
  341. he_delayfree(hent)
  342. register HE *hent;
  343. {
  344.     if (!hent)
  345.     return;
  346.     sv_2mortal(hent->hent_val);    /* free between statements */
  347.     Safefree(hent->hent_key);
  348.     Safefree(hent);
  349. }
  350.  
  351. void
  352. hv_clear(hv)
  353. HV *hv;
  354. {
  355.     register XPVHV* xhv;
  356.     if (!hv)
  357.     return;
  358.     xhv = (XPVHV*)SvANY(hv);
  359.     hfreeentries(hv);
  360.     xhv->xhv_fill = 0;
  361.     xhv->xhv_keys = 0;
  362.     if (xhv->xhv_array)
  363.     (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
  364.  
  365.     if (SvRMAGICAL(hv))
  366.     mg_clear((SV*)hv); 
  367. }
  368.  
  369. static void
  370. hfreeentries(hv)
  371. HV *hv;
  372. {
  373.     register HE **array;
  374.     register HE *hent;
  375.     register HE *ohent = Null(HE*);
  376.     I32 riter;
  377.     I32 max;
  378.  
  379.     if (!hv)
  380.     return;
  381.     if (!HvARRAY(hv))
  382.     return;
  383.  
  384.     riter = 0;
  385.     max = HvMAX(hv);
  386.     array = HvARRAY(hv);
  387.     hent = array[0];
  388.     for (;;) {
  389.     if (hent) {
  390.         ohent = hent;
  391.         hent = hent->hent_next;
  392.         he_free(ohent);
  393.     }
  394.     if (!hent) {
  395.         if (++riter > max)
  396.         break;
  397.         hent = array[riter];
  398.     } 
  399.     }
  400.     (void)hv_iterinit(hv);
  401. }
  402.  
  403. void
  404. hv_undef(hv)
  405. HV *hv;
  406. {
  407.     register XPVHV* xhv;
  408.     if (!hv)
  409.     return;
  410.     xhv = (XPVHV*)SvANY(hv);
  411.     hfreeentries(hv);
  412.     Safefree(xhv->xhv_array);
  413.     if (HvNAME(hv)) {
  414.     Safefree(HvNAME(hv));
  415.     HvNAME(hv) = 0;
  416.     }
  417.     xhv->xhv_array = 0;
  418.     xhv->xhv_max = 7;        /* it's a normal associative array */
  419.     xhv->xhv_fill = 0;
  420.     xhv->xhv_keys = 0;
  421.  
  422.     if (SvRMAGICAL(hv))
  423.     mg_clear((SV*)hv); 
  424. }
  425.  
  426. I32
  427. hv_iterinit(hv)
  428. HV *hv;
  429. {
  430.     register XPVHV* xhv = (XPVHV*)SvANY(hv);
  431.     HE *entry = xhv->xhv_eiter;
  432.     if (entry && entry->hent_klen < 0)    /* was deleted earlier? */
  433.     he_free(entry);
  434.     xhv->xhv_riter = -1;
  435.     xhv->xhv_eiter = Null(HE*);
  436.     return xhv->xhv_fill;
  437. }
  438.  
  439. HE *
  440. hv_iternext(hv)
  441. HV *hv;
  442. {
  443.     register XPVHV* xhv;
  444.     register HE *entry;
  445.     HE *oldentry;
  446.     MAGIC* mg;
  447.  
  448.     if (!hv)
  449.     croak("Bad associative array");
  450.     xhv = (XPVHV*)SvANY(hv);
  451.     oldentry = entry = xhv->xhv_eiter;
  452.  
  453.     if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
  454.     SV *key = sv_newmortal();
  455.     if (entry) {
  456.         sv_usepvn(key, entry->hent_key, entry->hent_klen);
  457.         entry->hent_key = 0;
  458.     }
  459.     else {
  460.         Newz(504,entry, 1, HE);
  461.         xhv->xhv_eiter = entry;
  462.     }
  463.     magic_nextpack((SV*) hv,mg,key);
  464.         if (SvOK(key)) {
  465.         STRLEN len;
  466.         entry->hent_key = SvPV_force(key, len);
  467.         entry->hent_klen = len;
  468.         SvPOK_off(key);
  469.         SvPVX(key) = 0;
  470.         return entry;
  471.         }
  472.     if (entry->hent_val)
  473.         SvREFCNT_dec(entry->hent_val);
  474.     Safefree(entry);
  475.     xhv->xhv_eiter = Null(HE*);
  476.     return Null(HE*);
  477.     }
  478.  
  479.     if (!xhv->xhv_array)
  480.     Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
  481.     do {
  482.     if (entry)
  483.         entry = entry->hent_next;
  484.     if (!entry) {
  485.         ++xhv->xhv_riter;
  486.         if (xhv->xhv_riter > xhv->xhv_max) {
  487.         xhv->xhv_riter = -1;
  488.         break;
  489.         }
  490.         entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
  491.     }
  492.     } while (!entry);
  493.  
  494.     if (oldentry && oldentry->hent_klen < 0)    /* was deleted earlier? */
  495.     he_free(oldentry);
  496.  
  497.     xhv->xhv_eiter = entry;
  498.     return entry;
  499. }
  500.  
  501. char *
  502. hv_iterkey(entry,retlen)
  503. register HE *entry;
  504. I32 *retlen;
  505. {
  506.     *retlen = entry->hent_klen;
  507.     return entry->hent_key;
  508. }
  509.  
  510. SV *
  511. hv_iterval(hv,entry)
  512. HV *hv;
  513. register HE *entry;
  514. {
  515.     if (SvRMAGICAL(hv)) {
  516.     if (mg_find((SV*)hv,'P')) {
  517.         SV* sv = sv_newmortal();
  518.         mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
  519.         return sv;
  520.     }
  521.     }
  522.     return entry->hent_val;
  523. }
  524.  
  525. SV *
  526. hv_iternextsv(hv, key, retlen)
  527.     HV *hv;
  528.     char **key;
  529.     I32 *retlen;
  530. {
  531.     HE *he;
  532.     if ( (he = hv_iternext(hv)) == NULL)
  533.     return NULL;
  534.     *key = hv_iterkey(he, retlen);
  535.     return hv_iterval(hv, he);
  536. }
  537.  
  538. void
  539. hv_magic(hv, gv, how)
  540. HV* hv;
  541. GV* gv;
  542. int how;
  543. {
  544.     sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);
  545. }
  546.