hv.c

   1 /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:21:48 $
   2  *
   3  *    Copyright (c) 1991, 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  * $Log:        hash.c,v $
   9  * Revision 4.1  92/08/07  18:21:48  lwall
  10  *
  11  * Revision 4.0.1.3  92/06/08  13:26:29  lwall
  12  * patch20: removed implicit int declarations on functions
  13  * patch20: delete could cause %array to give too low a count of buckets filled
  14  * patch20: hash tables now split only if the memory is available to do so
  15  *
  16  * Revision 4.0.1.2  91/11/05  17:24:13  lwall
  17  * patch11: saberized perl
  18  *
  19  * Revision 4.0.1.1  91/06/07  11:10:11  lwall
  20  * patch4: new copyright notice
  21  *
  22  * Revision 4.0  91/03/20  01:22:26  lwall
  23  * 4.0 baseline.
  24  *
  25  */
  26
  27 #include "EXTERN.h"
  28 #include "perl.h"
  29
  30 static void hsplit();
  31
  32 static void hfreeentries();
  33
  34 SV**
  35 hv_fetch(hv,key,klen,lval)
  36 HV *hv;
  37 char *key;
  38 U32 klen;
  39 I32 lval;
  40 {
  41     register XPVHV* xhv;
  42     register char *s;
  43     register I32 i;
  44     register I32 hash;
  45     register HE *entry;
  46     SV *sv;
  47
  48     if (!hv)
  49         return 0;
  50
  51     if (SvMAGICAL(hv)) {
  52         if (mg_find((SV*)hv,'P')) {
  53             sv = sv_2mortal(NEWSV(61,0));
  54             mg_copy((SV*)hv, sv, key, klen);
  55             if (!lval) {
  56                 mg_get(sv);
  57                 sv_unmagic(sv,'p');
  58             }
  59             Sv = sv;
  60             return &Sv;
  61         }
  62     }
  63
  64     xhv = (XPVHV*)SvANY(hv);
  65     if (!xhv->xhv_array) {
  66         if (lval)
  67             Newz(503,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
  68         else
  69             return 0;
  70     }
  71
  72     i = klen;
  73     hash = 0;
  74     s = key;
  75     while (i--)
  76         hash = hash * 33 + *s++;
  77
  78     entry = ((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
  79     for (; entry; entry = entry->hent_next) {
  80         if (entry->hent_hash != hash)           /* strings can't be equal */
  81             continue;
  82         if (entry->hent_klen != klen)
  83             continue;
  84         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
  85             continue;
  86         return &entry->hent_val;
  87     }
  88     if (lval) {         /* gonna assign to this, so it better be there */
  89         sv = NEWSV(61,0);
  90         return hv_store(hv,key,klen,sv,hash);
  91     }
  92     return 0;
  93 }
  94
  95 SV**
  96 hv_store(hv,key,klen,val,hash)
  97 HV *hv;
  98 char *key;
  99 U32 klen;
 100 SV *val;
 101 register U32 hash;
 102 {
 103     register XPVHV* xhv;
 104     register char *s;
 105     register I32 i;
 106     register HE *entry;
 107     register HE **oentry;
 108
 109     if (!hv)
 110         return 0;
 111
 112     xhv = (XPVHV*)SvANY(hv);
 113     if (SvMAGICAL(hv)) {
 114         MAGIC* mg = SvMAGIC(hv);
 115         mg_copy((SV*)hv, val, key, klen);
 116         if (!xhv->xhv_array)
 117             return 0;
 118     }
 119     if (!hash) {
 120     i = klen;
 121     s = key;
 122     while (i--)
 123         hash = hash * 33 + *s++;
 124     }
 125
 126     if (!xhv->xhv_array)
 127         Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
 128
 129     oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
 130     i = 1;
 131
 132     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
 133         if (entry->hent_hash != hash)           /* strings can't be equal */
 134             continue;
 135         if (entry->hent_klen != klen)
 136             continue;
 137         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 138             continue;
 139         sv_free(entry->hent_val);
 140         entry->hent_val = val;
 141         return &entry->hent_val;
 142     }
 143     New(501,entry, 1, HE);
 144
 145     entry->hent_klen = klen;
 146     entry->hent_key = nsavestr(key,klen);
 147     entry->hent_val = val;
 148     entry->hent_hash = hash;
 149     entry->hent_next = *oentry;
 150     *oentry = entry;
 151
 152     xhv->xhv_keys++;
 153     if (i) {                            /* initial entry? */
 154         ++xhv->xhv_fill;
 155         if (xhv->xhv_keys > xhv->xhv_max)
 156             hsplit(hv);
 157     }
 158
 159     return &entry->hent_val;
 160 }
 161
 162 SV *
 163 hv_delete(hv,key,klen)
 164 HV *hv;
 165 char *key;
 166 U32 klen;
 167 {
 168     register XPVHV* xhv;
 169     register char *s;
 170     register I32 i;
 171     register I32 hash;
 172     register HE *entry;
 173     register HE **oentry;
 174     SV *sv;
 175
 176     if (!hv)
 177         return Nullsv;
 178     if (SvMAGICAL(hv)) {
 179         sv = *hv_fetch(hv, key, klen, TRUE);
 180         mg_clear(sv);
 181     }
 182     xhv = (XPVHV*)SvANY(hv);
 183     if (!xhv->xhv_array)
 184         return Nullsv;
 185     i = klen;
 186     hash = 0;
 187     s = key;
 188     while (i--)
 189         hash = hash * 33 + *s++;
 190
 191     oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
 192     entry = *oentry;
 193     i = 1;
 194     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
 195         if (entry->hent_hash != hash)           /* strings can't be equal */
 196             continue;
 197         if (entry->hent_klen != klen)
 198             continue;
 199         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 200             continue;
 201         *oentry = entry->hent_next;
 202         if (i && !*oentry)
 203             xhv->xhv_fill--;
 204         sv = sv_mortalcopy(entry->hent_val);
 205         he_free(entry);
 206         --xhv->xhv_keys;
 207         return sv;
 208     }
 209     return Nullsv;
 210 }
 211
 212 static void
 213 hsplit(hv)
 214 HV *hv;
 215 {
 216     register XPVHV* xhv = (XPVHV*)SvANY(hv);
 217     I32 oldsize = xhv->xhv_max + 1;
 218     register I32 newsize = oldsize * 2;
 219     register I32 i;
 220     register HE **a;
 221     register HE **b;
 222     register HE *entry;
 223     register HE **oentry;
 224
 225     a = (HE**)xhv->xhv_array;
 226     nomemok = TRUE;
 227     Renew(a, newsize, HE*);
 228     nomemok = FALSE;
 229     Zero(&a[oldsize], oldsize, HE*);            /* zero 2nd half*/
 230     xhv->xhv_max = --newsize;
 231     xhv->xhv_array = (char*)a;
 232
 233     for (i=0; i<oldsize; i++,a++) {
 234         if (!*a)                                /* non-existent */
 235             continue;
 236         b = a+oldsize;
 237         for (oentry = a, entry = *a; entry; entry = *oentry) {
 238             if ((entry->hent_hash & newsize) != i) {
 239                 *oentry = entry->hent_next;
 240                 entry->hent_next = *b;
 241                 if (!*b)
 242                     xhv->xhv_fill++;
 243                 *b = entry;
 244                 continue;
 245             }
 246             else
 247                 oentry = &entry->hent_next;
 248         }
 249         if (!*a)                                /* everything moved */
 250             xhv->xhv_fill--;
 251     }
 252 }
 253
 254 HV *
 255 newHV()
 256 {
 257     register HV *hv;
 258     register XPVHV* xhv;
 259
 260     Newz(502,hv, 1, HV);
 261     SvREFCNT(hv) = 1;
 262     sv_upgrade(hv, SVt_PVHV);
 263     xhv = (XPVHV*)SvANY(hv);
 264     SvPOK_off(hv);
 265     SvNOK_off(hv);
 266     xhv->xhv_max = 7;           /* start with 8 buckets */
 267     xhv->xhv_fill = 0;
 268     xhv->xhv_pmroot = 0;
 269     (void)hv_iterinit(hv);      /* so each() will start off right */
 270     return hv;
 271 }
 272
 273 void
 274 he_free(hent)
 275 register HE *hent;
 276 {
 277     if (!hent)
 278         return;
 279     sv_free(hent->hent_val);
 280     Safefree(hent->hent_key);
 281     Safefree(hent);
 282 }
 283
 284 void
 285 he_delayfree(hent)
 286 register HE *hent;
 287 {
 288     if (!hent)
 289         return;
 290     sv_2mortal(hent->hent_val); /* free between statements */
 291     Safefree(hent->hent_key);
 292     Safefree(hent);
 293 }
 294
 295 void
 296 hv_clear(hv)
 297 HV *hv;
 298 {
 299     register XPVHV* xhv;
 300     if (!hv)
 301         return;
 302     xhv = (XPVHV*)SvANY(hv);
 303     hfreeentries(hv);
 304     xhv->xhv_fill = 0;
 305     if (xhv->xhv_array)
 306         (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
 307 }
 308
 309 static void
 310 hfreeentries(hv)
 311 HV *hv;
 312 {
 313     register XPVHV* xhv;
 314     register HE *hent;
 315     register HE *ohent = Null(HE*);
 316
 317     if (!hv)
 318         return;
 319     xhv = (XPVHV*)SvANY(hv);
 320     if (!xhv->xhv_array)
 321         return;
 322     (void)hv_iterinit(hv);
 323     /*SUPPRESS 560*/
 324     while (hent = hv_iternext(hv)) {    /* concise but not very efficient */
 325         he_free(ohent);
 326         ohent = hent;
 327     }
 328     he_free(ohent);
 329     if (SvMAGIC(hv))
 330         mg_clear((SV*)hv);
 331 }
 332
 333 void
 334 hv_undef(hv)
 335 HV *hv;
 336 {
 337     register XPVHV* xhv;
 338     if (!hv)
 339         return;
 340     xhv = (XPVHV*)SvANY(hv);
 341     hfreeentries(hv);
 342     Safefree(xhv->xhv_array);
 343     xhv->xhv_array = 0;
 344     xhv->xhv_max = 7;           /* it's a normal associative array */
 345     xhv->xhv_fill = 0;
 346     (void)hv_iterinit(hv);      /* so each() will start off right */
 347 }
 348
 349 void
 350 hv_free(hv)
 351 register HV *hv;
 352 {
 353     if (!hv)
 354         return;
 355     hfreeentries(hv);
 356     Safefree(HvARRAY(hv));
 357     Safefree(hv);
 358 }
 359
 360 I32
 361 hv_iterinit(hv)
 362 HV *hv;
 363 {
 364     register XPVHV* xhv = (XPVHV*)SvANY(hv);
 365     xhv->xhv_riter = -1;
 366     xhv->xhv_eiter = Null(HE*);
 367     return xhv->xhv_fill;
 368 }
 369
 370 HE *
 371 hv_iternext(hv)
 372 HV *hv;
 373 {
 374     register XPVHV* xhv;
 375     register HE *entry;
 376     MAGIC* mg;
 377
 378     if (!hv)
 379         croak("Bad associative array");
 380     xhv = (XPVHV*)SvANY(hv);
 381     entry = xhv->xhv_eiter;
 382
 383     if (SvMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
 384         SV *key = sv_2mortal(NEWSV(0,0));
 385         if (entry)
 386             sv_setpvn(key, entry->hent_key, entry->hent_klen);
 387         else {
 388             Newz(504,entry, 1, HE);
 389             xhv->xhv_eiter = entry;
 390         }
 391         magic_nextpack(hv,mg,key);
 392         if (SvOK(key)) {
 393             STRLEN len;
 394             entry->hent_key = SvPV(key, len);
 395             entry->hent_klen = len;
 396             SvPOK_off(key);
 397             SvPVX(key) = 0;
 398             return entry;
 399         }
 400         if (entry->hent_val)
 401             sv_free(entry->hent_val);
 402         Safefree(entry);
 403         xhv->xhv_eiter = Null(HE*);
 404         return Null(HE*);
 405     }
 406
 407     if (!xhv->xhv_array)
 408         Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
 409     do {
 410         if (entry)
 411             entry = entry->hent_next;
 412         if (!entry) {
 413             xhv->xhv_riter++;
 414             if (xhv->xhv_riter > xhv->xhv_max) {
 415                 xhv->xhv_riter = -1;
 416                 break;
 417             }
 418             entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
 419         }
 420     } while (!entry);
 421
 422     xhv->xhv_eiter = entry;
 423     return entry;
 424 }
 425
 426 char *
 427 hv_iterkey(entry,retlen)
 428 register HE *entry;
 429 I32 *retlen;
 430 {
 431     *retlen = entry->hent_klen;
 432     return entry->hent_key;
 433 }
 434
 435 SV *
 436 hv_iterval(hv,entry)
 437 HV *hv;
 438 register HE *entry;
 439 {
 440     if (SvMAGICAL(hv)) {
 441         if (mg_find((SV*)hv,'P')) {
 442             SV* sv = sv_2mortal(NEWSV(61,0));
 443             mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
 444             mg_get(sv);
 445             sv_unmagic(sv,'p');
 446             return sv;
 447         }
 448     }
 449     return entry->hent_val;
 450 }
 451
 452 void
 453 hv_magic(hv, gv, how)
 454 HV* hv;
 455 GV* gv;
 456 I32 how;
 457 {
 458     sv_magic((SV*)hv, (SV*)gv, how, 0, 0);
 459 }