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