This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
TIEARRAY updates - almost works ...
[perl5.git] / av.c
1 /*    av.c
2  *
3  *    Copyright (c) 1991-1997, 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  * "...for the Entwives desired order, and plenty, and peace (by which they
12  * meant that things should remain where they had set them)." --Treebeard
13  */
14
15 #include "EXTERN.h"
16 #include "perl.h"
17
18 void
19 av_reify(AV *av)
20 {
21     I32 key;
22     SV* sv;
23
24     if (AvREAL(av))                           
25         return;          
26 #ifdef DEBUGGING
27     if (SvRMAGICAL(av) && mg_find((SV*)av,'P')) 
28         warn("av_reify called on tied array");
29 #endif
30     key = AvMAX(av) + 1;
31     while (key > AvFILLp(av) + 1)
32         AvARRAY(av)[--key] = &sv_undef;
33     while (key) {
34         sv = AvARRAY(av)[--key];
35         assert(sv);
36         if (sv != &sv_undef) {
37             dTHR;
38             (void)SvREFCNT_inc(sv);
39         }
40     }
41     key = AvARRAY(av) - AvALLOC(av);
42     while (key)
43         AvALLOC(av)[--key] = &sv_undef;
44     AvREAL_on(av);
45 }
46
47 void
48 av_extend(AV *av, I32 key)
49 {
50     dTHR;                       /* only necessary if we have to extend stack */
51     MAGIC *mg;
52     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
53         dSP;
54         ENTER;
55         SAVETMPS;
56         PUSHMARK(sp);
57         EXTEND(sp,2);
58         PUSHs(mg->mg_obj);
59         PUSHs(sv_2mortal(newSViv(key+1)));
60         PUTBACK;
61         perl_call_method("EXTEND", G_SCALAR|G_DISCARD);
62         FREETMPS;
63         LEAVE;
64         return;
65     }
66     if (key > AvMAX(av)) {
67         SV** ary;
68         I32 tmp;
69         I32 newmax;
70
71         if (AvALLOC(av) != AvARRAY(av)) {
72             ary = AvALLOC(av) + AvFILLp(av) + 1;
73             tmp = AvARRAY(av) - AvALLOC(av);
74             Move(AvARRAY(av), AvALLOC(av), AvFILLp(av)+1, SV*);
75             AvMAX(av) += tmp;
76             SvPVX(av) = (char*)AvALLOC(av);
77             if (AvREAL(av)) {
78                 while (tmp)
79                     ary[--tmp] = &sv_undef;
80             }
81             
82             if (key > AvMAX(av) - 10) {
83                 newmax = key + AvMAX(av);
84                 goto resize;
85             }
86         }
87         else {
88             if (AvALLOC(av)) {
89 #ifndef STRANGE_MALLOC
90                 U32 bytes;
91 #endif
92
93                 newmax = key + AvMAX(av) / 5;
94               resize:
95 #ifdef STRANGE_MALLOC
96                 Renew(AvALLOC(av),newmax+1, SV*);
97 #else
98                 bytes = (newmax + 1) * sizeof(SV*);
99 #define MALLOC_OVERHEAD 16
100                 tmp = MALLOC_OVERHEAD;
101                 while (tmp - MALLOC_OVERHEAD < bytes)
102                     tmp += tmp;
103                 tmp -= MALLOC_OVERHEAD;
104                 tmp /= sizeof(SV*);
105                 assert(tmp > newmax);
106                 newmax = tmp - 1;
107                 New(2,ary, newmax+1, SV*);
108                 Copy(AvALLOC(av), ary, AvMAX(av)+1, SV*);
109                 if (AvMAX(av) > 64)
110                     offer_nice_chunk(AvALLOC(av), (AvMAX(av)+1) * sizeof(SV*));
111                 else
112                     Safefree(AvALLOC(av));
113                 AvALLOC(av) = ary;
114 #endif
115                 ary = AvALLOC(av) + AvMAX(av) + 1;
116                 tmp = newmax - AvMAX(av);
117                 if (av == curstack) {   /* Oops, grew stack (via av_store()?) */
118                     stack_sp = AvALLOC(av) + (stack_sp - stack_base);
119                     stack_base = AvALLOC(av);
120                     stack_max = stack_base + newmax;
121                 }
122             }
123             else {
124                 newmax = key < 4 ? 4 : key;
125                 New(2,AvALLOC(av), newmax+1, SV*);
126                 ary = AvALLOC(av) + 1;
127                 tmp = newmax;
128                 AvALLOC(av)[0] = &sv_undef;     /* For the stacks */
129             }
130             if (AvREAL(av)) {
131                 while (tmp)
132                     ary[--tmp] = &sv_undef;
133             }
134             
135             SvPVX(av) = (char*)AvALLOC(av);
136             AvMAX(av) = newmax;
137         }
138     }
139 }
140
141 SV**
142 av_fetch(register AV *av, I32 key, I32 lval)
143 {
144     SV *sv;
145
146     if (!av)
147         return 0;
148
149     if (key < 0) {
150         key += AvFILL(av) + 1;
151         if (key < 0)
152             return 0;
153     }
154
155     if (SvRMAGICAL(av)) {
156         if (mg_find((SV*)av,'P')) {
157             dTHR;
158             sv = sv_newmortal();
159             mg_copy((SV*)av, sv, 0, key);
160             Sv = sv;
161             return &Sv;
162         }
163     }
164
165     if (key > AvFILLp(av)) {
166         if (!lval)
167             return 0;
168         if (AvREALISH(av))
169             sv = NEWSV(5,0);
170         else
171             sv = sv_newmortal();
172         return av_store(av,key,sv);
173     }
174     if (AvARRAY(av)[key] == &sv_undef) {
175     emptyness:
176         if (lval) {
177             sv = NEWSV(6,0);
178             return av_store(av,key,sv);
179         }
180         return 0;
181     }
182     else if (AvREIFY(av)
183              && (!AvARRAY(av)[key]      /* eg. @_ could have freed elts */
184                  || SvTYPE(AvARRAY(av)[key]) == SVTYPEMASK)) {
185         AvARRAY(av)[key] = &sv_undef;   /* 1/2 reify */
186         goto emptyness;
187     }
188     return &AvARRAY(av)[key];
189 }
190
191 SV**
192 av_store(register AV *av, I32 key, SV *val)
193 {
194     SV** ary;
195     U32  fill;
196
197
198     if (!av)
199         return 0;
200     if (!val)
201         val = &sv_undef;
202
203     if (key < 0) {
204         key += AvFILL(av) + 1;
205         if (key < 0)
206             return 0;
207     }
208
209     if (SvREADONLY(av) && key >= AvFILL(av))
210         croak(no_modify);
211
212     if (SvRMAGICAL(av)) {
213         if (mg_find((SV*)av,'P')) {
214             if (val != &sv_undef) {
215                 mg_copy((SV*)av, val, 0, key);
216             }
217             return 0;
218         }
219     }
220
221     if (!AvREAL(av) && AvREIFY(av))
222         av_reify(av);
223     if (key > AvMAX(av))
224         av_extend(av,key);
225     ary = AvARRAY(av);
226     if (AvFILLp(av) < key) {
227         if (!AvREAL(av)) {
228             dTHR;
229             if (av == curstack && key > stack_sp - stack_base)
230                 stack_sp = stack_base + key;    /* XPUSH in disguise */
231             do
232                 ary[++AvFILLp(av)] = &sv_undef;
233             while (AvFILLp(av) < key);
234         }
235         AvFILLp(av) = key;
236     }
237     else if (AvREAL(av))
238         SvREFCNT_dec(ary[key]);
239     ary[key] = val;
240     if (SvSMAGICAL(av)) {
241         if (val != &sv_undef) {
242             MAGIC* mg = SvMAGIC(av);
243             sv_magic(val, (SV*)av, toLOWER(mg->mg_type), 0, key);
244         }
245         mg_set((SV*)av);
246     }
247     return &ary[key];
248 }
249
250 AV *
251 newAV(void)
252 {
253     register AV *av;
254
255     av = (AV*)NEWSV(3,0);
256     sv_upgrade((SV *)av, SVt_PVAV);
257     AvREAL_on(av);
258     AvALLOC(av) = 0;
259     SvPVX(av) = 0;
260     AvMAX(av) = AvFILLp(av) = -1;
261     return av;
262 }
263
264 AV *
265 av_make(register I32 size, register SV **strp)
266 {
267     register AV *av;
268     register I32 i;
269     register SV** ary;
270
271     av = (AV*)NEWSV(8,0);
272     sv_upgrade((SV *) av,SVt_PVAV);
273     AvFLAGS(av) = AVf_REAL;
274     if (size) {         /* `defined' was returning undef for size==0 anyway. */
275         New(4,ary,size,SV*);
276         AvALLOC(av) = ary;
277         SvPVX(av) = (char*)ary;
278         AvFILLp(av) = size - 1;
279         AvMAX(av) = size - 1;
280         for (i = 0; i < size; i++) {
281             assert (*strp);
282             ary[i] = NEWSV(7,0);
283             sv_setsv(ary[i], *strp);
284             strp++;
285         }
286     }
287     return av;
288 }
289
290 AV *
291 av_fake(register I32 size, register SV **strp)
292 {
293     register AV *av;
294     register SV** ary;
295
296     av = (AV*)NEWSV(9,0);
297     sv_upgrade((SV *)av, SVt_PVAV);
298     New(4,ary,size+1,SV*);
299     AvALLOC(av) = ary;
300     Copy(strp,ary,size,SV*);
301     AvFLAGS(av) = AVf_REIFY;
302     SvPVX(av) = (char*)ary;
303     AvFILLp(av) = size - 1;
304     AvMAX(av) = size - 1;
305     while (size--) {
306         assert (*strp);
307         SvTEMP_off(*strp);
308         strp++;
309     }
310     return av;
311 }
312
313 void
314 av_clear(register AV *av)
315 {
316     register I32 key;
317     SV** ary;
318
319 #ifdef DEBUGGING
320     if (SvREFCNT(av) <= 0) {
321         warn("Attempt to clear deleted array");
322     }
323 #endif
324     if (!av)
325         return;
326     /*SUPPRESS 560*/
327
328     /* Give any tie a chance to cleanup first */
329     if (SvRMAGICAL(av))
330         mg_clear((SV*)av); 
331
332     if (AvMAX(av) < 0)
333         return;
334
335     if (AvREAL(av)) {
336         ary = AvARRAY(av);
337         key = AvFILLp(av) + 1;
338         while (key) {
339             SvREFCNT_dec(ary[--key]);
340             ary[key] = &sv_undef;
341         }
342     }
343     if (key = AvARRAY(av) - AvALLOC(av)) {
344         AvMAX(av) += key;
345         SvPVX(av) = (char*)AvALLOC(av);
346     }
347     AvFILLp(av) = -1;
348
349 }
350
351 void
352 av_undef(register AV *av)
353 {
354     register I32 key;
355
356     if (!av)
357         return;
358     /*SUPPRESS 560*/
359
360     /* Give any tie a chance to cleanup first */
361     if (SvRMAGICAL(av) && mg_find((SV*)av,'P')) 
362         av_fill(av, -1);   /* mg_clear() ? */
363
364     if (AvREAL(av)) {
365         key = AvFILLp(av) + 1;
366         while (key)
367             SvREFCNT_dec(AvARRAY(av)[--key]);
368     }
369     Safefree(AvALLOC(av));
370     AvARRAY(av) = 0;
371     AvALLOC(av) = 0;
372     SvPVX(av) = 0;
373     AvMAX(av) = AvFILLp(av) = -1;
374     if (AvARYLEN(av)) {
375         SvREFCNT_dec(AvARYLEN(av));
376         AvARYLEN(av) = 0;
377     }
378 }
379
380 void
381 av_push(register AV *av, SV *val)
382 {             
383     MAGIC *mg;
384     if (!av)
385         return;
386     if (SvREADONLY(av))
387         croak(no_modify);
388
389     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
390         dSP;
391         PUSHMARK(sp);
392         EXTEND(sp,2);
393         PUSHs(mg->mg_obj);
394         PUSHs(val);
395         PUTBACK;
396         ENTER;
397         perl_call_method("PUSH", G_SCALAR|G_DISCARD);
398         LEAVE;
399         return;
400     }
401     av_store(av,AvFILLp(av)+1,val);
402 }
403
404 SV *
405 av_pop(register AV *av)
406 {
407     SV *retval;
408     MAGIC* mg;
409
410     if (!av || AvFILL(av) < 0)
411         return &sv_undef;
412     if (SvREADONLY(av))
413         croak(no_modify);
414     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
415         dSP;    
416         PUSHMARK(sp);
417         XPUSHs(mg->mg_obj);
418         PUTBACK;
419         ENTER;
420         if (perl_call_method("POP", G_SCALAR)) {
421             retval = newSVsv(*stack_sp--);    
422         } else {    
423             retval = &sv_undef;
424         }
425         LEAVE;
426         return retval;
427     }
428     retval = AvARRAY(av)[AvFILLp(av)];
429     AvARRAY(av)[AvFILLp(av)--] = &sv_undef;
430     if (SvSMAGICAL(av))
431         mg_set((SV*)av);
432     return retval;
433 }
434
435 void
436 av_unshift(register AV *av, register I32 num)
437 {
438     register I32 i;
439     register SV **sstr,**dstr;
440     MAGIC* mg;
441
442     if (!av || num <= 0)
443         return;
444     if (SvREADONLY(av))
445         croak(no_modify);
446
447     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
448         dSP;
449         PUSHMARK(sp);
450         EXTEND(sp,1+num);
451         PUSHs(mg->mg_obj);
452         while (num-- > 0) {
453             PUSHs(&sv_undef);
454         }
455         PUTBACK;
456         ENTER;
457         perl_call_method("UNSHIFT", G_SCALAR|G_DISCARD);
458         LEAVE;
459         return;
460     }
461
462     if (!AvREAL(av) && AvREIFY(av))
463         av_reify(av);
464     i = AvARRAY(av) - AvALLOC(av);
465     if (i) {
466         if (i > num)
467             i = num;
468         num -= i;
469     
470         AvMAX(av) += i;
471         AvFILLp(av) += i;
472         SvPVX(av) = (char*)(AvARRAY(av) - i);
473     }
474     if (num) {
475         av_extend(av,AvFILLp(av)+num);
476         AvFILLp(av) += num;
477         dstr = AvARRAY(av) + AvFILLp(av);
478         sstr = dstr - num;
479 #ifdef BUGGY_MSC5
480  # pragma loop_opt(off) /* don't loop-optimize the following code */
481 #endif /* BUGGY_MSC5 */
482         for (i = AvFILLp(av) - num; i >= 0; --i) {
483             *dstr-- = *sstr--;
484 #ifdef BUGGY_MSC5
485  # pragma loop_opt()    /* loop-optimization back to command-line setting */
486 #endif /* BUGGY_MSC5 */
487         }
488         while (num)
489             AvARRAY(av)[--num] = &sv_undef;
490     }
491 }
492
493 SV *
494 av_shift(register AV *av)
495 {
496     SV *retval;
497     MAGIC* mg;
498
499     if (!av || AvFILL(av) < 0)
500         return &sv_undef;
501     if (SvREADONLY(av))
502         croak(no_modify);
503     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
504         dSP;
505         PUSHMARK(sp);
506         XPUSHs(mg->mg_obj);
507         PUTBACK;
508         ENTER;
509         if (perl_call_method("SHIFT", G_SCALAR)) {
510             retval = newSVsv(*stack_sp--);            
511         } else {    
512             retval = &sv_undef;
513         }     
514         LEAVE;
515         return retval;
516     }
517     retval = *AvARRAY(av);
518     if (AvREAL(av))
519         *AvARRAY(av) = &sv_undef;
520     SvPVX(av) = (char*)(AvARRAY(av) + 1);
521     AvMAX(av)--;
522     AvFILLp(av)--;
523     if (SvSMAGICAL(av))
524         mg_set((SV*)av);
525     return retval;
526 }
527
528 I32
529 av_len(register AV *av)
530 {
531     return AvFILL(av);
532 }
533
534 void
535 av_fill(register AV *av, I32 fill)
536 {
537     MAGIC *mg;
538     if (!av)
539         croak("panic: null array");
540     if (fill < 0)
541         fill = -1;
542     if (SvRMAGICAL(av) && (mg = mg_find((SV*)av,'P'))) {
543         dSP;            
544         ENTER;
545         SAVETMPS;
546         PUSHMARK(sp);
547         EXTEND(sp,2);
548         PUSHs(mg->mg_obj);
549         PUSHs(sv_2mortal(newSViv(fill+1)));
550         PUTBACK;
551         perl_call_method("STORESIZE", G_SCALAR|G_DISCARD);
552         FREETMPS;
553         LEAVE;
554         return;
555     }
556     if (fill <= AvMAX(av)) {
557         I32 key = AvFILLp(av);
558         SV** ary = AvARRAY(av);
559
560         if (AvREAL(av)) {
561             while (key > fill) {
562                 SvREFCNT_dec(ary[key]);
563                 ary[key--] = &sv_undef;
564             }
565         }
566         else {
567             while (key < fill)
568                 ary[++key] = &sv_undef;
569         }
570             
571         AvFILLp(av) = fill;
572         if (SvSMAGICAL(av))
573             mg_set((SV*)av);
574     }
575     else
576         (void)av_store(av,fill,&sv_undef);
577 }
578
579   
580 HV*
581 avhv_keys(AV *av)
582 {
583     SV **keysp;
584     HV *keys = Nullhv;
585
586     keysp = av_fetch(av, 0, FALSE);
587     if (keysp) {
588         SV *sv = *keysp;
589         if (SvGMAGICAL(sv))
590             mg_get(sv);
591         if (SvROK(sv)) {
592             sv = SvRV(sv);
593             if (SvTYPE(sv) == SVt_PVHV)
594                 keys = (HV*)sv;
595         }
596     }
597     if (!keys)
598         croak("Can't coerce array into hash");
599     return keys;
600 }
601
602 SV**
603 avhv_fetch(AV *av, char *key, U32 klen, I32 lval)
604 {
605     SV **indsvp;
606     HV *keys = avhv_keys(av);
607     I32 ind;
608     
609     indsvp = hv_fetch(keys, key, klen, FALSE);
610     if (indsvp) {
611         ind = SvIV(*indsvp);
612         if (ind < 1)
613             croak("Bad index while coercing array into hash");
614     } else {
615         if (!lval)
616             return 0;
617         
618         ind = AvFILL(av) + 1;
619         hv_store(keys, key, klen, newSViv(ind), 0);
620     }
621     return av_fetch(av, ind, lval);
622 }
623
624 SV**
625 avhv_fetch_ent(AV *av, SV *keysv, I32 lval, U32 hash)
626 {
627     SV **indsvp;
628     HV *keys = avhv_keys(av);
629     HE *he;
630     I32 ind;
631     
632     he = hv_fetch_ent(keys, keysv, FALSE, hash);
633     if (he) {
634         ind = SvIV(HeVAL(he));
635         if (ind < 1)
636             croak("Bad index while coercing array into hash");
637     } else {
638         if (!lval)
639             return 0;
640         
641         ind = AvFILL(av) + 1;
642         hv_store_ent(keys, keysv, newSViv(ind), 0);
643     }
644     return av_fetch(av, ind, lval);
645 }
646
647 SV**
648 avhv_store(AV *av, char *key, U32 klen, SV *val, U32 hash)
649 {
650     SV **indsvp;
651     HV *keys = avhv_keys(av);
652     I32 ind;
653     
654     indsvp = hv_fetch(keys, key, klen, FALSE);
655     if (indsvp) {
656         ind = SvIV(*indsvp);
657         if (ind < 1)
658             croak("Bad index while coercing array into hash");
659     } else {
660         ind = AvFILL(av) + 1;
661         hv_store(keys, key, klen, newSViv(ind), hash);
662     }
663     return av_store(av, ind, val);
664 }
665
666 SV**
667 avhv_store_ent(AV *av, SV *keysv, SV *val, U32 hash)
668 {
669     HV *keys = avhv_keys(av);
670     HE *he;
671     I32 ind;
672     
673     he = hv_fetch_ent(keys, keysv, FALSE, hash);
674     if (he) {
675         ind = SvIV(HeVAL(he));
676         if (ind < 1)
677             croak("Bad index while coercing array into hash");
678     } else {
679         ind = AvFILL(av) + 1;
680         hv_store_ent(keys, keysv, newSViv(ind), hash);
681     }
682     return av_store(av, ind, val);
683 }
684
685 bool
686 avhv_exists_ent(AV *av, SV *keysv, U32 hash)
687 {
688     HV *keys = avhv_keys(av);
689     return hv_exists_ent(keys, keysv, hash);
690 }
691
692 bool
693 avhv_exists(AV *av, char *key, U32 klen)
694 {
695     HV *keys = avhv_keys(av);
696     return hv_exists(keys, key, klen);
697 }
698
699 /* avhv_delete leaks. Caller can re-index and compress if so desired. */
700 SV *
701 avhv_delete(AV *av, char *key, U32 klen, I32 flags)
702 {
703     HV *keys = avhv_keys(av);
704     SV *sv;
705     SV **svp;
706     I32 ind;
707     
708     sv = hv_delete(keys, key, klen, 0);
709     if (!sv)
710         return Nullsv;
711     ind = SvIV(sv);
712     if (ind < 1)
713         croak("Bad index while coercing array into hash");
714     svp = av_fetch(av, ind, FALSE);
715     if (!svp)
716         return Nullsv;
717     if (flags & G_DISCARD) {
718         sv = Nullsv;
719         SvREFCNT_dec(*svp);
720     } else {
721         sv = sv_2mortal(*svp);
722     }
723     *svp = &sv_undef;
724     return sv;
725 }
726
727 /* avhv_delete_ent leaks. Caller can re-index and compress if so desired. */
728 SV *
729 avhv_delete_ent(AV *av, SV *keysv, I32 flags, U32 hash)
730 {
731     HV *keys = avhv_keys(av);
732     SV *sv;
733     SV **svp;
734     I32 ind;
735     
736     sv = hv_delete_ent(keys, keysv, 0, hash);
737     if (!sv)
738         return Nullsv;
739     ind = SvIV(sv);
740     if (ind < 1)
741         croak("Bad index while coercing array into hash");
742     svp = av_fetch(av, ind, FALSE);
743     if (!svp)
744         return Nullsv;
745     if (flags & G_DISCARD) {
746         sv = Nullsv;
747         SvREFCNT_dec(*svp);
748     } else {
749         sv = sv_2mortal(*svp);
750     }
751     *svp = &sv_undef;
752     return sv;
753 }
754
755 I32
756 avhv_iterinit(AV *av)
757 {
758     HV *keys = avhv_keys(av);
759     return hv_iterinit(keys);
760 }
761
762 HE *
763 avhv_iternext(AV *av)
764 {
765     HV *keys = avhv_keys(av);
766     return hv_iternext(keys);
767 }
768
769 SV *
770 avhv_iterval(AV *av, register HE *entry)
771 {
772     HV *keys = avhv_keys(av);
773     SV *sv;
774     I32 ind;
775     
776     sv = hv_iterval(keys, entry);
777     ind = SvIV(sv);
778     if (ind < 1)
779         croak("Bad index while coercing array into hash");
780     return *av_fetch(av, ind, TRUE);
781 }
782
783 SV *
784 avhv_iternextsv(AV *av, char **key, I32 *retlen)
785 {
786     HV *keys = avhv_keys(av);
787     HE *he;
788     SV *sv;
789     I32 ind;
790     
791     he = hv_iternext(keys);
792     if (!he)
793         return Nullsv;
794     *key = hv_iterkey(he, retlen);
795     sv = hv_iterval(keys, he);
796     ind = SvIV(sv);
797     if (ind < 1)
798         croak("Bad index while coercing array into hash");
799     return *av_fetch(av, ind, TRUE);
800 }