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)
 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 }