home *** CD-ROM | disk | FTP | other *** search
/ OpenStep 4.2J (Developer) / os42jdev.iso / NextDeveloper / Source / GNU / perl / Perl / hv.c < prev    next >
C/C++ Source or Header  |  1995-01-16  |  11KB  |  550 lines
  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,flags)
  166. HV *hv;
  167. char *key;
  168. U32 klen;
  169. I32 flags;
  170. {
  171.     register XPVHV* xhv;
  172.     register char *s;
  173.     register I32 i;
  174.     register I32 hash;
  175.     register HE *entry;
  176.     register HE **oentry;
  177.     SV *sv;
  178.  
  179.     if (!hv)
  180.     return Nullsv;
  181.     if (SvRMAGICAL(hv)) {
  182.     sv = *hv_fetch(hv, key, klen, TRUE);
  183.     mg_clear(sv);
  184.     if (mg_find(sv, 'p')) {
  185.         sv_unmagic(sv, 'p');    /* No longer an element */
  186.         return sv;
  187.     }
  188.     }
  189.     xhv = (XPVHV*)SvANY(hv);
  190.     if (!xhv->xhv_array)
  191.     return Nullsv;
  192.     i = klen;
  193.     hash = 0;
  194.     s = key;
  195.     while (i--)
  196.     hash = hash * 33 + *s++;
  197.  
  198.     oentry = &((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
  199.     entry = *oentry;
  200.     i = 1;
  201.     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
  202.     if (entry->hent_hash != hash)        /* strings can't be equal */
  203.         continue;
  204.     if (entry->hent_klen != klen)
  205.         continue;
  206.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  207.         continue;
  208.     *oentry = entry->hent_next;
  209.     if (i && !*oentry)
  210.         xhv->xhv_fill--;
  211.     if (flags & G_DISCARD)
  212.         sv = Nullsv;
  213.     else
  214.         sv = sv_mortalcopy(entry->hent_val);
  215.     if (entry == xhv->xhv_eiter)
  216.         entry->hent_klen = -1;
  217.     else
  218.         he_free(entry);
  219.     --xhv->xhv_keys;
  220.     return sv;
  221.     }
  222.     return Nullsv;
  223. }
  224.  
  225. bool
  226. hv_exists(hv,key,klen)
  227. HV *hv;
  228. char *key;
  229. U32 klen;
  230. {
  231.     register XPVHV* xhv;
  232.     register char *s;
  233.     register I32 i;
  234.     register I32 hash;
  235.     register HE *entry;
  236.     SV *sv;
  237.  
  238.     if (!hv)
  239.     return 0;
  240.  
  241.     if (SvRMAGICAL(hv)) {
  242.     if (mg_find((SV*)hv,'P')) {
  243.         sv = sv_newmortal();
  244.         mg_copy((SV*)hv, sv, key, klen); 
  245.         magic_existspack(sv, mg_find(sv, 'p'));
  246.         return SvTRUE(sv);
  247.     }
  248.     }
  249.  
  250.     xhv = (XPVHV*)SvANY(hv);
  251.     if (!xhv->xhv_array)
  252.     return 0; 
  253.  
  254.     i = klen;
  255.     hash = 0;
  256.     s = key;
  257.     while (i--)
  258.     hash = hash * 33 + *s++;
  259.  
  260.     entry = ((HE**)xhv->xhv_array)[hash & (I32) xhv->xhv_max];
  261.     for (; entry; entry = entry->hent_next) {
  262.     if (entry->hent_hash != hash)        /* strings can't be equal */
  263.         continue;
  264.     if (entry->hent_klen != klen)
  265.         continue;
  266.     if (bcmp(entry->hent_key,key,klen))    /* is this it? */
  267.         continue;
  268.     return TRUE;
  269.     }
  270.     return FALSE;
  271. }
  272.  
  273. static void
  274. hsplit(hv)
  275. HV *hv;
  276. {
  277.     register XPVHV* xhv = (XPVHV*)SvANY(hv);
  278.     I32 oldsize = (I32) xhv->xhv_max + 1; /* sic(k) */
  279.     register I32 newsize = oldsize * 2;
  280.     register I32 i;
  281.     register HE **a;
  282.     register HE **b;
  283.     register HE *entry;
  284.     register HE **oentry;
  285.  
  286.     a = (HE**)xhv->xhv_array;
  287.     nomemok = TRUE;
  288.     Renew(a, newsize, HE*);
  289.     nomemok = FALSE;
  290.     Zero(&a[oldsize], oldsize, HE*);        /* zero 2nd half*/
  291.     xhv->xhv_max = --newsize;
  292.     xhv->xhv_array = (char*)a;
  293.  
  294.     for (i=0; i<oldsize; i++,a++) {
  295.     if (!*a)                /* non-existent */
  296.         continue;
  297.     b = a+oldsize;
  298.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  299.         if ((entry->hent_hash & newsize) != i) {
  300.         *oentry = entry->hent_next;
  301.         entry->hent_next = *b;
  302.         if (!*b)
  303.             xhv->xhv_fill++;
  304.         *b = entry;
  305.         continue;
  306.         }
  307.         else
  308.         oentry = &entry->hent_next;
  309.     }
  310.     if (!*a)                /* everything moved */
  311.         xhv->xhv_fill--;
  312.     }
  313. }
  314.  
  315. HV *
  316. newHV()
  317. {
  318.     register HV *hv;
  319.     register XPVHV* xhv;
  320.  
  321.     hv = (HV*)NEWSV(502,0);
  322.     sv_upgrade((SV *)hv, SVt_PVHV);
  323.     xhv = (XPVHV*)SvANY(hv);
  324.     SvPOK_off(hv);
  325.     SvNOK_off(hv);
  326.     xhv->xhv_max = 7;        /* start with 8 buckets */
  327.     xhv->xhv_fill = 0;
  328.     xhv->xhv_pmroot = 0;
  329.     (void)hv_iterinit(hv);    /* so each() will start off right */
  330.     return hv;
  331. }
  332.  
  333. void
  334. he_free(hent)
  335. register HE *hent;
  336. {
  337.     if (!hent)
  338.     return;
  339.     SvREFCNT_dec(hent->hent_val);
  340.     Safefree(hent->hent_key);
  341.     Safefree(hent);
  342. }
  343.  
  344. void
  345. he_delayfree(hent)
  346. register HE *hent;
  347. {
  348.     if (!hent)
  349.     return;
  350.     sv_2mortal(hent->hent_val);    /* free between statements */
  351.     Safefree(hent->hent_key);
  352.     Safefree(hent);
  353. }
  354.  
  355. void
  356. hv_clear(hv)
  357. HV *hv;
  358. {
  359.     register XPVHV* xhv;
  360.     if (!hv)
  361.     return;
  362.     xhv = (XPVHV*)SvANY(hv);
  363.     hfreeentries(hv);
  364.     xhv->xhv_fill = 0;
  365.     xhv->xhv_keys = 0;
  366.     if (xhv->xhv_array)
  367.     (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
  368.  
  369.     if (SvRMAGICAL(hv))
  370.     mg_clear((SV*)hv); 
  371. }
  372.  
  373. static void
  374. hfreeentries(hv)
  375. HV *hv;
  376. {
  377.     register HE **array;
  378.     register HE *hent;
  379.     register HE *ohent = Null(HE*);
  380.     I32 riter;
  381.     I32 max;
  382.  
  383.     if (!hv)
  384.     return;
  385.     if (!HvARRAY(hv))
  386.     return;
  387.  
  388.     riter = 0;
  389.     max = HvMAX(hv);
  390.     array = HvARRAY(hv);
  391.     hent = array[0];
  392.     for (;;) {
  393.     if (hent) {
  394.         ohent = hent;
  395.         hent = hent->hent_next;
  396.         he_free(ohent);
  397.     }
  398.     if (!hent) {
  399.         if (++riter > max)
  400.         break;
  401.         hent = array[riter];
  402.     } 
  403.     }
  404.     (void)hv_iterinit(hv);
  405. }
  406.  
  407. void
  408. hv_undef(hv)
  409. HV *hv;
  410. {
  411.     register XPVHV* xhv;
  412.     if (!hv)
  413.     return;
  414.     xhv = (XPVHV*)SvANY(hv);
  415.     hfreeentries(hv);
  416.     Safefree(xhv->xhv_array);
  417.     if (HvNAME(hv)) {
  418.     Safefree(HvNAME(hv));
  419.     HvNAME(hv) = 0;
  420.     }
  421.     xhv->xhv_array = 0;
  422.     xhv->xhv_max = 7;        /* it's a normal associative array */
  423.     xhv->xhv_fill = 0;
  424.     xhv->xhv_keys = 0;
  425.  
  426.     if (SvRMAGICAL(hv))
  427.     mg_clear((SV*)hv); 
  428. }
  429.  
  430. I32
  431. hv_iterinit(hv)
  432. HV *hv;
  433. {
  434.     register XPVHV* xhv = (XPVHV*)SvANY(hv);
  435.     HE *entry = xhv->xhv_eiter;
  436.     if (entry && entry->hent_klen < 0)    /* was deleted earlier? */
  437.     he_free(entry);
  438.     xhv->xhv_riter = -1;
  439.     xhv->xhv_eiter = Null(HE*);
  440.     return xhv->xhv_fill;
  441. }
  442.  
  443. HE *
  444. hv_iternext(hv)
  445. HV *hv;
  446. {
  447.     register XPVHV* xhv;
  448.     register HE *entry;
  449.     HE *oldentry;
  450.     MAGIC* mg;
  451.  
  452.     if (!hv)
  453.     croak("Bad associative array");
  454.     xhv = (XPVHV*)SvANY(hv);
  455.     oldentry = entry = xhv->xhv_eiter;
  456.  
  457.     if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
  458.     SV *key = sv_newmortal();
  459.     if (entry) {
  460.         sv_usepvn(key, entry->hent_key, entry->hent_klen);
  461.         entry->hent_key = 0;
  462.     }
  463.     else {
  464.         Newz(504,entry, 1, HE);
  465.         xhv->xhv_eiter = entry;
  466.     }
  467.     magic_nextpack((SV*) hv,mg,key);
  468.         if (SvOK(key)) {
  469.         STRLEN len;
  470.         entry->hent_key = SvPV_force(key, len);
  471.         entry->hent_klen = len;
  472.         SvPOK_off(key);
  473.         SvPVX(key) = 0;
  474.         return entry;
  475.         }
  476.     if (entry->hent_val)
  477.         SvREFCNT_dec(entry->hent_val);
  478.     Safefree(entry);
  479.     xhv->xhv_eiter = Null(HE*);
  480.     return Null(HE*);
  481.     }
  482.  
  483.     if (!xhv->xhv_array)
  484.     Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
  485.     do {
  486.     if (entry)
  487.         entry = entry->hent_next;
  488.     if (!entry) {
  489.         ++xhv->xhv_riter;
  490.         if (xhv->xhv_riter > xhv->xhv_max) {
  491.         xhv->xhv_riter = -1;
  492.         break;
  493.         }
  494.         entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
  495.     }
  496.     } while (!entry);
  497.  
  498.     if (oldentry && oldentry->hent_klen < 0)    /* was deleted earlier? */
  499.     he_free(oldentry);
  500.  
  501.     xhv->xhv_eiter = entry;
  502.     return entry;
  503. }
  504.  
  505. char *
  506. hv_iterkey(entry,retlen)
  507. register HE *entry;
  508. I32 *retlen;
  509. {
  510.     *retlen = entry->hent_klen;
  511.     return entry->hent_key;
  512. }
  513.  
  514. SV *
  515. hv_iterval(hv,entry)
  516. HV *hv;
  517. register HE *entry;
  518. {
  519.     if (SvRMAGICAL(hv)) {
  520.     if (mg_find((SV*)hv,'P')) {
  521.         SV* sv = sv_newmortal();
  522.         mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
  523.         return sv;
  524.     }
  525.     }
  526.     return entry->hent_val;
  527. }
  528.  
  529. SV *
  530. hv_iternextsv(hv, key, retlen)
  531.     HV *hv;
  532.     char **key;
  533.     I32 *retlen;
  534. {
  535.     HE *he;
  536.     if ( (he = hv_iternext(hv)) == NULL)
  537.     return NULL;
  538.     *key = hv_iterkey(he, retlen);
  539.     return hv_iterval(hv, he);
  540. }
  541.  
  542. void
  543. hv_magic(hv, gv, how)
  544. HV* hv;
  545. GV* gv;
  546. int how;
  547. {
  548.     sv_magic((SV*)hv, (SV*)gv, how, Nullch, 0);
  549. }
  550.