Initial 3-way merge from (5.001m, thr1m, 5.003) plus fixups.
[perl.git] / 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 }