hv.c

   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 }