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 (SvRMAGICAL(hv)) {
  52         if (mg_find((SV*)hv,'P')) {
  53             sv = sv_newmortal();
  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         mg_copy((SV*)hv, val, key, klen);
 115         if (!xhv->xhv_array)
 116             return 0;
 117     }
 118     if (!hash) {
 119     i = klen;
 120     s = key;
 121     while (i--)
 122         hash = hash * 33 + *s++;
 123     }
 124
 125     if (!xhv->xhv_array)
 126         Newz(505, xhv->xhv_array, sizeof(HE**) * (xhv->xhv_max + 1), char);
 127
 128     oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
 129     i = 1;
 130
 131     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
 132         if (entry->hent_hash != hash)           /* strings can't be equal */
 133             continue;
 134         if (entry->hent_klen != klen)
 135             continue;
 136         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 137             continue;
 138         SvREFCNT_dec(entry->hent_val);
 139         entry->hent_val = val;
 140         return &entry->hent_val;
 141     }
 142     New(501,entry, 1, HE);
 143
 144     entry->hent_klen = klen;
 145     entry->hent_key = nsavestr(key,klen);
 146     entry->hent_val = val;
 147     entry->hent_hash = hash;
 148     entry->hent_next = *oentry;
 149     *oentry = entry;
 150
 151     xhv->xhv_keys++;
 152     if (i) {                            /* initial entry? */
 153         ++xhv->xhv_fill;
 154         if (xhv->xhv_keys > xhv->xhv_max)
 155             hsplit(hv);
 156     }
 157
 158     return &entry->hent_val;
 159 }
 160
 161 SV *
 162 hv_delete(hv,key,klen)
 163 HV *hv;
 164 char *key;
 165 U32 klen;
 166 {
 167     register XPVHV* xhv;
 168     register char *s;
 169     register I32 i;
 170     register I32 hash;
 171     register HE *entry;
 172     register HE **oentry;
 173     SV *sv;
 174
 175     if (!hv)
 176         return Nullsv;
 177     if (SvRMAGICAL(hv)) {
 178         sv = *hv_fetch(hv, key, klen, TRUE);
 179         mg_clear(sv);
 180     }
 181     xhv = (XPVHV*)SvANY(hv);
 182     if (!xhv->xhv_array)
 183         return Nullsv;
 184     i = klen;
 185     hash = 0;
 186     s = key;
 187     while (i--)
 188         hash = hash * 33 + *s++;
 189
 190     oentry = &((HE**)xhv->xhv_array)[hash & xhv->xhv_max];
 191     entry = *oentry;
 192     i = 1;
 193     for (; entry; i=0, oentry = &entry->hent_next, entry = *oentry) {
 194         if (entry->hent_hash != hash)           /* strings can't be equal */
 195             continue;
 196         if (entry->hent_klen != klen)
 197             continue;
 198         if (bcmp(entry->hent_key,key,klen))     /* is this it? */
 199             continue;
 200         *oentry = entry->hent_next;
 201         if (i && !*oentry)
 202             xhv->xhv_fill--;
 203         sv = sv_mortalcopy(entry->hent_val);
 204         he_free(entry);
 205         --xhv->xhv_keys;
 206         return sv;
 207     }
 208     return Nullsv;
 209 }
 210
 211 static void
 212 hsplit(hv)
 213 HV *hv;
 214 {
 215     register XPVHV* xhv = (XPVHV*)SvANY(hv);
 216     I32 oldsize = xhv->xhv_max + 1;
 217     register I32 newsize = oldsize * 2;
 218     register I32 i;
 219     register HE **a;
 220     register HE **b;
 221     register HE *entry;
 222     register HE **oentry;
 223
 224     a = (HE**)xhv->xhv_array;
 225     nomemok = TRUE;
 226     Renew(a, newsize, HE*);
 227     nomemok = FALSE;
 228     Zero(&a[oldsize], oldsize, HE*);            /* zero 2nd half*/
 229     xhv->xhv_max = --newsize;
 230     xhv->xhv_array = (char*)a;
 231
 232     for (i=0; i<oldsize; i++,a++) {
 233         if (!*a)                                /* non-existent */
 234             continue;
 235         b = a+oldsize;
 236         for (oentry = a, entry = *a; entry; entry = *oentry) {
 237             if ((entry->hent_hash & newsize) != i) {
 238                 *oentry = entry->hent_next;
 239                 entry->hent_next = *b;
 240                 if (!*b)
 241                     xhv->xhv_fill++;
 242                 *b = entry;
 243                 continue;
 244             }
 245             else
 246                 oentry = &entry->hent_next;
 247         }
 248         if (!*a)                                /* everything moved */
 249             xhv->xhv_fill--;
 250     }
 251 }
 252
 253 HV *
 254 newHV()
 255 {
 256     register HV *hv;
 257     register XPVHV* xhv;
 258
 259     Newz(502,hv, 1, HV);
 260     SvREFCNT(hv) = 1;
 261     sv_upgrade(hv, SVt_PVHV);
 262     xhv = (XPVHV*)SvANY(hv);
 263     SvPOK_off(hv);
 264     SvNOK_off(hv);
 265     xhv->xhv_max = 7;           /* start with 8 buckets */
 266     xhv->xhv_fill = 0;
 267     xhv->xhv_pmroot = 0;
 268     (void)hv_iterinit(hv);      /* so each() will start off right */
 269     return hv;
 270 }
 271
 272 void
 273 he_free(hent)
 274 register HE *hent;
 275 {
 276     if (!hent)
 277         return;
 278     SvREFCNT_dec(hent->hent_val);
 279     Safefree(hent->hent_key);
 280     Safefree(hent);
 281 }
 282
 283 void
 284 he_delayfree(hent)
 285 register HE *hent;
 286 {
 287     if (!hent)
 288         return;
 289     sv_2mortal(hent->hent_val); /* free between statements */
 290     Safefree(hent->hent_key);
 291     Safefree(hent);
 292 }
 293
 294 void
 295 hv_clear(hv)
 296 HV *hv;
 297 {
 298     register XPVHV* xhv;
 299     if (!hv)
 300         return;
 301     xhv = (XPVHV*)SvANY(hv);
 302     hfreeentries(hv);
 303     xhv->xhv_fill = 0;
 304     if (xhv->xhv_array)
 305         (void)memzero(xhv->xhv_array, (xhv->xhv_max + 1) * sizeof(HE*));
 306 }
 307
 308 static void
 309 hfreeentries(hv)
 310 HV *hv;
 311 {
 312     register XPVHV* xhv;
 313     register HE *hent;
 314     register HE *ohent = Null(HE*);
 315
 316     if (!hv)
 317         return;
 318     xhv = (XPVHV*)SvANY(hv);
 319     if (!xhv->xhv_array)
 320         return;
 321     (void)hv_iterinit(hv);
 322     /*SUPPRESS 560*/
 323     while (hent = hv_iternext(hv)) {    /* concise but not very efficient */
 324         he_free(ohent);
 325         ohent = hent;
 326     }
 327     he_free(ohent);
 328     if (SvMAGIC(hv))
 329         mg_clear((SV*)hv);
 330 }
 331
 332 void
 333 hv_undef(hv)
 334 HV *hv;
 335 {
 336     register XPVHV* xhv;
 337     if (!hv)
 338         return;
 339     xhv = (XPVHV*)SvANY(hv);
 340     hfreeentries(hv);
 341     Safefree(xhv->xhv_array);
 342     if (HvNAME(hv)) {
 343         Safefree(HvNAME(hv));
 344         HvNAME(hv) = 0;
 345     }
 346     xhv->xhv_array = 0;
 347     xhv->xhv_max = 7;           /* it's a normal associative array */
 348     xhv->xhv_fill = 0;
 349     (void)hv_iterinit(hv);      /* so each() will start off right */
 350 }
 351
 352 I32
 353 hv_iterinit(hv)
 354 HV *hv;
 355 {
 356     register XPVHV* xhv = (XPVHV*)SvANY(hv);
 357     xhv->xhv_riter = -1;
 358     xhv->xhv_eiter = Null(HE*);
 359     return xhv->xhv_fill;
 360 }
 361
 362 HE *
 363 hv_iternext(hv)
 364 HV *hv;
 365 {
 366     register XPVHV* xhv;
 367     register HE *entry;
 368     MAGIC* mg;
 369
 370     if (!hv)
 371         croak("Bad associative array");
 372     xhv = (XPVHV*)SvANY(hv);
 373     entry = xhv->xhv_eiter;
 374
 375     if (SvRMAGICAL(hv) && (mg = mg_find((SV*)hv,'P'))) {
 376         SV *key = sv_newmortal();
 377         if (entry)
 378             sv_setpvn(key, entry->hent_key, entry->hent_klen);
 379         else {
 380             Newz(504,entry, 1, HE);
 381             xhv->xhv_eiter = entry;
 382         }
 383         magic_nextpack(hv,mg,key);
 384         if (SvOK(key)) {
 385             STRLEN len;
 386             entry->hent_key = SvPV(key, len);
 387             entry->hent_klen = len;
 388             SvPOK_off(key);
 389             SvPVX(key) = 0;
 390             return entry;
 391         }
 392         if (entry->hent_val)
 393             SvREFCNT_dec(entry->hent_val);
 394         Safefree(entry);
 395         xhv->xhv_eiter = Null(HE*);
 396         return Null(HE*);
 397     }
 398
 399     if (!xhv->xhv_array)
 400         Newz(506,xhv->xhv_array, sizeof(HE*) * (xhv->xhv_max + 1), char);
 401     do {
 402         if (entry)
 403             entry = entry->hent_next;
 404         if (!entry) {
 405             xhv->xhv_riter++;
 406             if (xhv->xhv_riter > xhv->xhv_max) {
 407                 xhv->xhv_riter = -1;
 408                 break;
 409             }
 410             entry = ((HE**)xhv->xhv_array)[xhv->xhv_riter];
 411         }
 412     } while (!entry);
 413
 414     xhv->xhv_eiter = entry;
 415     return entry;
 416 }
 417
 418 char *
 419 hv_iterkey(entry,retlen)
 420 register HE *entry;
 421 I32 *retlen;
 422 {
 423     *retlen = entry->hent_klen;
 424     return entry->hent_key;
 425 }
 426
 427 SV *
 428 hv_iterval(hv,entry)
 429 HV *hv;
 430 register HE *entry;
 431 {
 432     if (SvRMAGICAL(hv)) {
 433         if (mg_find((SV*)hv,'P')) {
 434             SV* sv = sv_newmortal();
 435             mg_copy((SV*)hv, sv, entry->hent_key, entry->hent_klen);
 436             mg_get(sv);
 437             sv_unmagic(sv,'p');
 438             return sv;
 439         }
 440     }
 441     return entry->hent_val;
 442 }
 443
 444 void
 445 hv_magic(hv, gv, how)
 446 HV* hv;
 447 GV* gv;
 448 I32 how;
 449 {
 450     sv_magic((SV*)hv, (SV*)gv, how, 0, 0);
 451 }