3c9d796a7c2bbccc3638d3e7a959293edd96dbbf
[perl.git] / av.c
1 /*    av.c
2  *
3  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
4  *    2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, by Larry Wall and others
5  *
6  *    You may distribute under the terms of either the GNU General Public
7  *    License or the Artistic License, as specified in the README file.
8  *
9  */
10
11 /*
12  * "...for the Entwives desired order, and plenty, and peace (by which they
13  * meant that things should remain where they had set them)." --Treebeard
14  */
15
16 /*
17 =head1 Array Manipulation Functions
18 */
19
20 #include "EXTERN.h"
21 #define PERL_IN_AV_C
22 #include "perl.h"
23
24 void
25 Perl_av_reify(pTHX_ AV *av)
26 {
27     dVAR;
28     I32 key;
29
30     PERL_ARGS_ASSERT_AV_REIFY;
31     assert(SvTYPE(av) == SVt_PVAV);
32
33     if (AvREAL(av))
34         return;
35 #ifdef DEBUGGING
36     if (SvTIED_mg((SV*)av, PERL_MAGIC_tied) && ckWARN_d(WARN_DEBUGGING))
37         Perl_warner(aTHX_ packWARN(WARN_DEBUGGING), "av_reify called on tied array");
38 #endif
39     key = AvMAX(av) + 1;
40     while (key > AvFILLp(av) + 1)
41         AvARRAY(av)[--key] = &PL_sv_undef;
42     while (key) {
43         SV * const sv = AvARRAY(av)[--key];
44         assert(sv);
45         if (sv != &PL_sv_undef)
46             SvREFCNT_inc_simple_void_NN(sv);
47     }
48     key = AvARRAY(av) - AvALLOC(av);
49     while (key)
50         AvALLOC(av)[--key] = &PL_sv_undef;
51     AvREIFY_off(av);
52     AvREAL_on(av);
53 }
54
55 /*
56 =for apidoc av_extend
57
58 Pre-extend an array.  The C<key> is the index to which the array should be
59 extended.
60
61 =cut
62 */
63
64 void
65 Perl_av_extend(pTHX_ AV *av, I32 key)
66 {
67     dVAR;
68     MAGIC *mg;
69
70     PERL_ARGS_ASSERT_AV_EXTEND;
71     assert(SvTYPE(av) == SVt_PVAV);
72
73     mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied);
74     if (mg) {
75         dSP;
76         ENTER;
77         SAVETMPS;
78         PUSHSTACKi(PERLSI_MAGIC);
79         PUSHMARK(SP);
80         EXTEND(SP,2);
81         PUSHs(SvTIED_obj((SV*)av, mg));
82         mPUSHi(key + 1);
83         PUTBACK;
84         call_method("EXTEND", G_SCALAR|G_DISCARD);
85         POPSTACK;
86         FREETMPS;
87         LEAVE;
88         return;
89     }
90     if (key > AvMAX(av)) {
91         SV** ary;
92         I32 tmp;
93         I32 newmax;
94
95         if (AvALLOC(av) != AvARRAY(av)) {
96             ary = AvALLOC(av) + AvFILLp(av) + 1;
97             tmp = AvARRAY(av) - AvALLOC(av);
98             Move(AvARRAY(av), AvALLOC(av), AvFILLp(av)+1, SV*);
99             AvMAX(av) += tmp;
100             AvARRAY(av) = AvALLOC(av);
101             if (AvREAL(av)) {
102                 while (tmp)
103                     ary[--tmp] = &PL_sv_undef;
104             }
105             if (key > AvMAX(av) - 10) {
106                 newmax = key + AvMAX(av);
107                 goto resize;
108             }
109         }
110         else {
111 #ifdef PERL_MALLOC_WRAP
112             static const char oom_array_extend[] =
113               "Out of memory during array extend"; /* Duplicated in pp_hot.c */
114 #endif
115
116             if (AvALLOC(av)) {
117 #if !defined(STRANGE_MALLOC) && !defined(MYMALLOC)
118                 MEM_SIZE bytes;
119                 IV itmp;
120 #endif
121
122 #ifdef Perl_safesysmalloc_size
123                 /* Whilst it would be quite possible to move this logic around
124                    (as I did in the SV code), so as to set AvMAX(av) early,
125                    based on calling Perl_safesysmalloc_size() immediately after
126                    allocation, I'm not convinced that it is a great idea here.
127                    In an array we have to loop round setting everything to
128                    &PL_sv_undef, which means writing to memory, potentially lots
129                    of it, whereas for the SV buffer case we don't touch the
130                    "bonus" memory. So there there is no cost in telling the
131                    world about it, whereas here we have to do work before we can
132                    tell the world about it, and that work involves writing to
133                    memory that might never be read. So, I feel, better to keep
134                    the current lazy system of only writing to it if our caller
135                    has a need for more space. NWC  */
136                 newmax = Perl_safesysmalloc_size((void*)AvALLOC(av)) /
137                     sizeof(SV*) - 1;
138
139                 if (key <= newmax) 
140                     goto resized;
141 #endif 
142                 newmax = key + AvMAX(av) / 5;
143               resize:
144                 MEM_WRAP_CHECK_1(newmax+1, SV*, oom_array_extend);
145 #if defined(STRANGE_MALLOC) || defined(MYMALLOC)
146                 Renew(AvALLOC(av),newmax+1, SV*);
147 #else
148                 bytes = (newmax + 1) * sizeof(SV*);
149 #define MALLOC_OVERHEAD 16
150                 itmp = MALLOC_OVERHEAD;
151                 while ((MEM_SIZE)(itmp - MALLOC_OVERHEAD) < bytes)
152                     itmp += itmp;
153                 itmp -= MALLOC_OVERHEAD;
154                 itmp /= sizeof(SV*);
155                 assert(itmp > newmax);
156                 newmax = itmp - 1;
157                 assert(newmax >= AvMAX(av));
158                 Newx(ary, newmax+1, SV*);
159                 Copy(AvALLOC(av), ary, AvMAX(av)+1, SV*);
160                 if (AvMAX(av) > 64)
161                     offer_nice_chunk(AvALLOC(av), (AvMAX(av)+1) * sizeof(SV*));
162                 else
163                     Safefree(AvALLOC(av));
164                 AvALLOC(av) = ary;
165 #endif
166 #ifdef Perl_safesysmalloc_size
167               resized:
168 #endif
169                 ary = AvALLOC(av) + AvMAX(av) + 1;
170                 tmp = newmax - AvMAX(av);
171                 if (av == PL_curstack) {        /* Oops, grew stack (via av_store()?) */
172                     PL_stack_sp = AvALLOC(av) + (PL_stack_sp - PL_stack_base);
173                     PL_stack_base = AvALLOC(av);
174                     PL_stack_max = PL_stack_base + newmax;
175                 }
176             }
177             else {
178                 newmax = key < 3 ? 3 : key;
179                 MEM_WRAP_CHECK_1(newmax+1, SV*, oom_array_extend);
180                 Newx(AvALLOC(av), newmax+1, SV*);
181                 ary = AvALLOC(av) + 1;
182                 tmp = newmax;
183                 AvALLOC(av)[0] = &PL_sv_undef;  /* For the stacks */
184             }
185             if (AvREAL(av)) {
186                 while (tmp)
187                     ary[--tmp] = &PL_sv_undef;
188             }
189             
190             AvARRAY(av) = AvALLOC(av);
191             AvMAX(av) = newmax;
192         }
193     }
194 }
195
196 /*
197 =for apidoc av_fetch
198
199 Returns the SV at the specified index in the array.  The C<key> is the
200 index.  If C<lval> is set then the fetch will be part of a store.  Check
201 that the return value is non-null before dereferencing it to a C<SV*>.
202
203 See L<perlguts/"Understanding the Magic of Tied Hashes and Arrays"> for
204 more information on how to use this function on tied arrays. 
205
206 =cut
207 */
208
209 SV**
210 Perl_av_fetch(pTHX_ register AV *av, I32 key, I32 lval)
211 {
212     dVAR;
213
214     PERL_ARGS_ASSERT_AV_FETCH;
215     assert(SvTYPE(av) == SVt_PVAV);
216
217     if (SvRMAGICAL(av)) {
218         const MAGIC * const tied_magic = mg_find((SV*)av, PERL_MAGIC_tied);
219         if (tied_magic || mg_find((SV*)av, PERL_MAGIC_regdata)) {
220             SV *sv;
221             if (key < 0) {
222                 I32 adjust_index = 1;
223                 if (tied_magic) {
224                     /* Handle negative array indices 20020222 MJD */
225                     SV * const * const negative_indices_glob =
226                         hv_fetch(SvSTASH(SvRV(SvTIED_obj((SV *)av, tied_magic))),
227                                 NEGATIVE_INDICES_VAR, 16, 0);
228
229                     if (negative_indices_glob && SvTRUE(GvSV(*negative_indices_glob)))
230                         adjust_index = 0;
231                 }
232
233                 if (adjust_index) {
234                     key += AvFILL(av) + 1;
235                     if (key < 0)
236                         return NULL;
237                 }
238             }
239
240             sv = sv_newmortal();
241             sv_upgrade(sv, SVt_PVLV);
242             mg_copy((SV*)av, sv, 0, key);
243             LvTYPE(sv) = 't';
244             LvTARG(sv) = sv; /* fake (SV**) */
245             return &(LvTARG(sv));
246         }
247     }
248
249     if (key < 0) {
250         key += AvFILL(av) + 1;
251         if (key < 0)
252             return NULL;
253     }
254
255     if (key > AvFILLp(av)) {
256         if (!lval)
257             return NULL;
258         return av_store(av,key,newSV(0));
259     }
260     if (AvARRAY(av)[key] == &PL_sv_undef) {
261     emptyness:
262         if (lval)
263             return av_store(av,key,newSV(0));
264         return NULL;
265     }
266     else if (AvREIFY(av)
267              && (!AvARRAY(av)[key]      /* eg. @_ could have freed elts */
268                  || SvIS_FREED(AvARRAY(av)[key]))) {
269         AvARRAY(av)[key] = &PL_sv_undef;        /* 1/2 reify */
270         goto emptyness;
271     }
272     return &AvARRAY(av)[key];
273 }
274
275 /*
276 =for apidoc av_store
277
278 Stores an SV in an array.  The array index is specified as C<key>.  The
279 return value will be NULL if the operation failed or if the value did not
280 need to be actually stored within the array (as in the case of tied
281 arrays). Otherwise it can be dereferenced to get the original C<SV*>.  Note
282 that the caller is responsible for suitably incrementing the reference
283 count of C<val> before the call, and decrementing it if the function
284 returned NULL.
285
286 See L<perlguts/"Understanding the Magic of Tied Hashes and Arrays"> for
287 more information on how to use this function on tied arrays.
288
289 =cut
290 */
291
292 SV**
293 Perl_av_store(pTHX_ register AV *av, I32 key, SV *val)
294 {
295     dVAR;
296     SV** ary;
297
298     PERL_ARGS_ASSERT_AV_STORE;
299     assert(SvTYPE(av) == SVt_PVAV);
300
301     /* S_regclass relies on being able to pass in a NULL sv
302        (unicode_alternate may be NULL).
303     */
304
305     if (!val)
306         val = &PL_sv_undef;
307
308     if (SvRMAGICAL(av)) {
309         const MAGIC * const tied_magic = mg_find((SV*)av, PERL_MAGIC_tied);
310         if (tied_magic) {
311             /* Handle negative array indices 20020222 MJD */
312             if (key < 0) {
313                 bool adjust_index = 1;
314                 SV * const * const negative_indices_glob =
315                     hv_fetch(SvSTASH(SvRV(SvTIED_obj((SV *)av, 
316                                                      tied_magic))), 
317                              NEGATIVE_INDICES_VAR, 16, 0);
318                 if (negative_indices_glob
319                     && SvTRUE(GvSV(*negative_indices_glob)))
320                     adjust_index = 0;
321                 if (adjust_index) {
322                     key += AvFILL(av) + 1;
323                     if (key < 0)
324                         return 0;
325                 }
326             }
327             if (val != &PL_sv_undef) {
328                 mg_copy((SV*)av, val, 0, key);
329             }
330             return NULL;
331         }
332     }
333
334
335     if (key < 0) {
336         key += AvFILL(av) + 1;
337         if (key < 0)
338             return NULL;
339     }
340
341     if (SvREADONLY(av) && key >= AvFILL(av))
342         Perl_croak(aTHX_ PL_no_modify);
343
344     if (!AvREAL(av) && AvREIFY(av))
345         av_reify(av);
346     if (key > AvMAX(av))
347         av_extend(av,key);
348     ary = AvARRAY(av);
349     if (AvFILLp(av) < key) {
350         if (!AvREAL(av)) {
351             if (av == PL_curstack && key > PL_stack_sp - PL_stack_base)
352                 PL_stack_sp = PL_stack_base + key;      /* XPUSH in disguise */
353             do {
354                 ary[++AvFILLp(av)] = &PL_sv_undef;
355             } while (AvFILLp(av) < key);
356         }
357         AvFILLp(av) = key;
358     }
359     else if (AvREAL(av))
360         SvREFCNT_dec(ary[key]);
361     ary[key] = val;
362     if (SvSMAGICAL(av)) {
363         const MAGIC* const mg = SvMAGIC(av);
364         if (val != &PL_sv_undef) {
365             sv_magic(val, (SV*)av, toLOWER(mg->mg_type), 0, key);
366         }
367         if (PL_delaymagic && mg->mg_type == PERL_MAGIC_isa)
368             PL_delaymagic |= DM_ARRAY;
369         else
370            mg_set((SV*)av);
371     }
372     return &ary[key];
373 }
374
375 /*
376 =for apidoc av_make
377
378 Creates a new AV and populates it with a list of SVs.  The SVs are copied
379 into the array, so they may be freed after the call to av_make.  The new AV
380 will have a reference count of 1.
381
382 =cut
383 */
384
385 AV *
386 Perl_av_make(pTHX_ register I32 size, register SV **strp)
387 {
388     register AV * const av = (AV*)newSV_type(SVt_PVAV);
389     /* sv_upgrade does AvREAL_only()  */
390     PERL_ARGS_ASSERT_AV_MAKE;
391     assert(SvTYPE(av) == SVt_PVAV);
392
393     if (size) {         /* "defined" was returning undef for size==0 anyway. */
394         register SV** ary;
395         register I32 i;
396         Newx(ary,size,SV*);
397         AvALLOC(av) = ary;
398         AvARRAY(av) = ary;
399         AvFILLp(av) = AvMAX(av) = size - 1;
400         for (i = 0; i < size; i++) {
401             assert (*strp);
402             ary[i] = newSV(0);
403             sv_setsv(ary[i], *strp);
404             strp++;
405         }
406     }
407     return av;
408 }
409
410 /*
411 =for apidoc av_clear
412
413 Clears an array, making it empty.  Does not free the memory used by the
414 array itself.
415
416 =cut
417 */
418
419 void
420 Perl_av_clear(pTHX_ register AV *av)
421 {
422     dVAR;
423     I32 extra;
424
425     PERL_ARGS_ASSERT_AV_CLEAR;
426     assert(SvTYPE(av) == SVt_PVAV);
427
428 #ifdef DEBUGGING
429     if (SvREFCNT(av) == 0 && ckWARN_d(WARN_DEBUGGING)) {
430         Perl_warner(aTHX_ packWARN(WARN_DEBUGGING), "Attempt to clear deleted array");
431     }
432 #endif
433
434     if (SvREADONLY(av))
435         Perl_croak(aTHX_ PL_no_modify);
436
437     /* Give any tie a chance to cleanup first */
438     if (SvRMAGICAL(av)) {
439         const MAGIC* const mg = SvMAGIC(av);
440         if (PL_delaymagic && mg && mg->mg_type == PERL_MAGIC_isa)
441             PL_delaymagic |= DM_ARRAY;
442         else
443             mg_clear((SV*)av); 
444     }
445
446     if (AvMAX(av) < 0)
447         return;
448
449     if (AvREAL(av)) {
450         SV** const ary = AvARRAY(av);
451         I32 index = AvFILLp(av) + 1;
452         while (index) {
453             SV * const sv = ary[--index];
454             /* undef the slot before freeing the value, because a
455              * destructor might try to modify this array */
456             ary[index] = &PL_sv_undef;
457             SvREFCNT_dec(sv);
458         }
459     }
460     extra = AvARRAY(av) - AvALLOC(av);
461     if (extra) {
462         AvMAX(av) += extra;
463         AvARRAY(av) = AvALLOC(av);
464     }
465     AvFILLp(av) = -1;
466
467 }
468
469 /*
470 =for apidoc av_undef
471
472 Undefines the array.  Frees the memory used by the array itself.
473
474 =cut
475 */
476
477 void
478 Perl_av_undef(pTHX_ register AV *av)
479 {
480     PERL_ARGS_ASSERT_AV_UNDEF;
481     assert(SvTYPE(av) == SVt_PVAV);
482
483     /* Give any tie a chance to cleanup first */
484     if (SvTIED_mg((SV*)av, PERL_MAGIC_tied)) 
485         av_fill(av, -1);
486
487     if (AvREAL(av)) {
488         register I32 key = AvFILLp(av) + 1;
489         while (key)
490             SvREFCNT_dec(AvARRAY(av)[--key]);
491     }
492
493     Safefree(AvALLOC(av));
494     AvALLOC(av) = NULL;
495     AvARRAY(av) = NULL;
496     AvMAX(av) = AvFILLp(av) = -1;
497
498     if(SvRMAGICAL(av)) mg_clear((SV*)av);
499 }
500
501 /*
502
503 =for apidoc av_create_and_push
504
505 Push an SV onto the end of the array, creating the array if necessary.
506 A small internal helper function to remove a commonly duplicated idiom.
507
508 =cut
509 */
510
511 void
512 Perl_av_create_and_push(pTHX_ AV **const avp, SV *const val)
513 {
514     PERL_ARGS_ASSERT_AV_CREATE_AND_PUSH;
515
516     if (!*avp)
517         *avp = newAV();
518     av_push(*avp, val);
519 }
520
521 /*
522 =for apidoc av_push
523
524 Pushes an SV onto the end of the array.  The array will grow automatically
525 to accommodate the addition.
526
527 =cut
528 */
529
530 void
531 Perl_av_push(pTHX_ register AV *av, SV *val)
532 {             
533     dVAR;
534     MAGIC *mg;
535
536     PERL_ARGS_ASSERT_AV_PUSH;
537     assert(SvTYPE(av) == SVt_PVAV);
538
539     if (SvREADONLY(av))
540         Perl_croak(aTHX_ PL_no_modify);
541
542     if ((mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied))) {
543         dSP;
544         PUSHSTACKi(PERLSI_MAGIC);
545         PUSHMARK(SP);
546         EXTEND(SP,2);
547         PUSHs(SvTIED_obj((SV*)av, mg));
548         PUSHs(val);
549         PUTBACK;
550         ENTER;
551         call_method("PUSH", G_SCALAR|G_DISCARD);
552         LEAVE;
553         POPSTACK;
554         return;
555     }
556     av_store(av,AvFILLp(av)+1,val);
557 }
558
559 /*
560 =for apidoc av_pop
561
562 Pops an SV off the end of the array.  Returns C<&PL_sv_undef> if the array
563 is empty.
564
565 =cut
566 */
567
568 SV *
569 Perl_av_pop(pTHX_ register AV *av)
570 {
571     dVAR;
572     SV *retval;
573     MAGIC* mg;
574
575     PERL_ARGS_ASSERT_AV_POP;
576     assert(SvTYPE(av) == SVt_PVAV);
577
578     if (SvREADONLY(av))
579         Perl_croak(aTHX_ PL_no_modify);
580     if ((mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied))) {
581         dSP;    
582         PUSHSTACKi(PERLSI_MAGIC);
583         PUSHMARK(SP);
584         XPUSHs(SvTIED_obj((SV*)av, mg));
585         PUTBACK;
586         ENTER;
587         if (call_method("POP", G_SCALAR)) {
588             retval = newSVsv(*PL_stack_sp--);    
589         } else {    
590             retval = &PL_sv_undef;
591         }
592         LEAVE;
593         POPSTACK;
594         return retval;
595     }
596     if (AvFILL(av) < 0)
597         return &PL_sv_undef;
598     retval = AvARRAY(av)[AvFILLp(av)];
599     AvARRAY(av)[AvFILLp(av)--] = &PL_sv_undef;
600     if (SvSMAGICAL(av))
601         mg_set((SV*)av);
602     return retval;
603 }
604
605 /*
606
607 =for apidoc av_create_and_unshift_one
608
609 Unshifts an SV onto the beginning of the array, creating the array if
610 necessary.
611 A small internal helper function to remove a commonly duplicated idiom.
612
613 =cut
614 */
615
616 SV **
617 Perl_av_create_and_unshift_one(pTHX_ AV **const avp, SV *const val)
618 {
619     PERL_ARGS_ASSERT_AV_CREATE_AND_UNSHIFT_ONE;
620
621     if (!*avp)
622         *avp = newAV();
623     av_unshift(*avp, 1);
624     return av_store(*avp, 0, val);
625 }
626
627 /*
628 =for apidoc av_unshift
629
630 Unshift the given number of C<undef> values onto the beginning of the
631 array.  The array will grow automatically to accommodate the addition.  You
632 must then use C<av_store> to assign values to these new elements.
633
634 =cut
635 */
636
637 void
638 Perl_av_unshift(pTHX_ register AV *av, register I32 num)
639 {
640     dVAR;
641     register I32 i;
642     MAGIC* mg;
643
644     PERL_ARGS_ASSERT_AV_UNSHIFT;
645     assert(SvTYPE(av) == SVt_PVAV);
646
647     if (SvREADONLY(av))
648         Perl_croak(aTHX_ PL_no_modify);
649
650     if ((mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied))) {
651         dSP;
652         PUSHSTACKi(PERLSI_MAGIC);
653         PUSHMARK(SP);
654         EXTEND(SP,1+num);
655         PUSHs(SvTIED_obj((SV*)av, mg));
656         while (num-- > 0) {
657             PUSHs(&PL_sv_undef);
658         }
659         PUTBACK;
660         ENTER;
661         call_method("UNSHIFT", G_SCALAR|G_DISCARD);
662         LEAVE;
663         POPSTACK;
664         return;
665     }
666
667     if (num <= 0)
668       return;
669     if (!AvREAL(av) && AvREIFY(av))
670         av_reify(av);
671     i = AvARRAY(av) - AvALLOC(av);
672     if (i) {
673         if (i > num)
674             i = num;
675         num -= i;
676     
677         AvMAX(av) += i;
678         AvFILLp(av) += i;
679         AvARRAY(av) = AvARRAY(av) - i;
680     }
681     if (num) {
682         register SV **ary;
683         const I32 i = AvFILLp(av);
684         /* Create extra elements */
685         const I32 slide = i > 0 ? i : 0;
686         num += slide;
687         av_extend(av, i + num);
688         AvFILLp(av) += num;
689         ary = AvARRAY(av);
690         Move(ary, ary + num, i + 1, SV*);
691         do {
692             ary[--num] = &PL_sv_undef;
693         } while (num);
694         /* Make extra elements into a buffer */
695         AvMAX(av) -= slide;
696         AvFILLp(av) -= slide;
697         AvARRAY(av) = AvARRAY(av) + slide;
698     }
699 }
700
701 /*
702 =for apidoc av_shift
703
704 Shifts an SV off the beginning of the array. Returns C<&PL_sv_undef> if the 
705 array is empty.
706
707 =cut
708 */
709
710 SV *
711 Perl_av_shift(pTHX_ register AV *av)
712 {
713     dVAR;
714     SV *retval;
715     MAGIC* mg;
716
717     PERL_ARGS_ASSERT_AV_SHIFT;
718     assert(SvTYPE(av) == SVt_PVAV);
719
720     if (SvREADONLY(av))
721         Perl_croak(aTHX_ PL_no_modify);
722     if ((mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied))) {
723         dSP;
724         PUSHSTACKi(PERLSI_MAGIC);
725         PUSHMARK(SP);
726         XPUSHs(SvTIED_obj((SV*)av, mg));
727         PUTBACK;
728         ENTER;
729         if (call_method("SHIFT", G_SCALAR)) {
730             retval = newSVsv(*PL_stack_sp--);            
731         } else {    
732             retval = &PL_sv_undef;
733         }     
734         LEAVE;
735         POPSTACK;
736         return retval;
737     }
738     if (AvFILL(av) < 0)
739       return &PL_sv_undef;
740     retval = *AvARRAY(av);
741     if (AvREAL(av))
742         *AvARRAY(av) = &PL_sv_undef;
743     AvARRAY(av) = AvARRAY(av) + 1;
744     AvMAX(av)--;
745     AvFILLp(av)--;
746     if (SvSMAGICAL(av))
747         mg_set((SV*)av);
748     return retval;
749 }
750
751 /*
752 =for apidoc av_len
753
754 Returns the highest index in the array.  The number of elements in the
755 array is C<av_len(av) + 1>.  Returns -1 if the array is empty.
756
757 =cut
758 */
759
760 I32
761 Perl_av_len(pTHX_ register const AV *av)
762 {
763     PERL_ARGS_ASSERT_AV_LEN;
764     assert(SvTYPE(av) == SVt_PVAV);
765
766     return AvFILL(av);
767 }
768
769 /*
770 =for apidoc av_fill
771
772 Set the highest index in the array to the given number, equivalent to
773 Perl's C<$#array = $fill;>.
774
775 The number of elements in the an array will be C<fill + 1> after
776 av_fill() returns.  If the array was previously shorter then the
777 additional elements appended are set to C<PL_sv_undef>.  If the array
778 was longer, then the excess elements are freed.  C<av_fill(av, -1)> is
779 the same as C<av_clear(av)>.
780
781 =cut
782 */
783 void
784 Perl_av_fill(pTHX_ register AV *av, I32 fill)
785 {
786     dVAR;
787     MAGIC *mg;
788
789     PERL_ARGS_ASSERT_AV_FILL;
790     assert(SvTYPE(av) == SVt_PVAV);
791
792     if (fill < 0)
793         fill = -1;
794     if ((mg = SvTIED_mg((SV*)av, PERL_MAGIC_tied))) {
795         dSP;            
796         ENTER;
797         SAVETMPS;
798         PUSHSTACKi(PERLSI_MAGIC);
799         PUSHMARK(SP);
800         EXTEND(SP,2);
801         PUSHs(SvTIED_obj((SV*)av, mg));
802         mPUSHi(fill + 1);
803         PUTBACK;
804         call_method("STORESIZE", G_SCALAR|G_DISCARD);
805         POPSTACK;
806         FREETMPS;
807         LEAVE;
808         return;
809     }
810     if (fill <= AvMAX(av)) {
811         I32 key = AvFILLp(av);
812         SV** const ary = AvARRAY(av);
813
814         if (AvREAL(av)) {
815             while (key > fill) {
816                 SvREFCNT_dec(ary[key]);
817                 ary[key--] = &PL_sv_undef;
818             }
819         }
820         else {
821             while (key < fill)
822                 ary[++key] = &PL_sv_undef;
823         }
824             
825         AvFILLp(av) = fill;
826         if (SvSMAGICAL(av))
827             mg_set((SV*)av);
828     }
829     else
830         (void)av_store(av,fill,&PL_sv_undef);
831 }
832
833 /*
834 =for apidoc av_delete
835
836 Deletes the element indexed by C<key> from the array.  Returns the
837 deleted element. If C<flags> equals C<G_DISCARD>, the element is freed
838 and null is returned.
839
840 =cut
841 */
842 SV *
843 Perl_av_delete(pTHX_ AV *av, I32 key, I32 flags)
844 {
845     dVAR;
846     SV *sv;
847
848     PERL_ARGS_ASSERT_AV_DELETE;
849     assert(SvTYPE(av) == SVt_PVAV);
850
851     if (SvREADONLY(av))
852         Perl_croak(aTHX_ PL_no_modify);
853
854     if (SvRMAGICAL(av)) {
855         const MAGIC * const tied_magic = mg_find((SV*)av, PERL_MAGIC_tied);
856         if ((tied_magic || mg_find((SV*)av, PERL_MAGIC_regdata))) {
857             /* Handle negative array indices 20020222 MJD */
858             SV **svp;
859             if (key < 0) {
860                 unsigned adjust_index = 1;
861                 if (tied_magic) {
862                     SV * const * const negative_indices_glob =
863                         hv_fetch(SvSTASH(SvRV(SvTIED_obj((SV *)av, 
864                                                          tied_magic))), 
865                                  NEGATIVE_INDICES_VAR, 16, 0);
866                     if (negative_indices_glob
867                         && SvTRUE(GvSV(*negative_indices_glob)))
868                         adjust_index = 0;
869                 }
870                 if (adjust_index) {
871                     key += AvFILL(av) + 1;
872                     if (key < 0)
873                         return NULL;
874                 }
875             }
876             svp = av_fetch(av, key, TRUE);
877             if (svp) {
878                 sv = *svp;
879                 mg_clear(sv);
880                 if (mg_find(sv, PERL_MAGIC_tiedelem)) {
881                     sv_unmagic(sv, PERL_MAGIC_tiedelem); /* No longer an element */
882                     return sv;
883                 }
884                 return NULL;
885             }
886         }
887     }
888
889     if (key < 0) {
890         key += AvFILL(av) + 1;
891         if (key < 0)
892             return NULL;
893     }
894
895     if (key > AvFILLp(av))
896         return NULL;
897     else {
898         if (!AvREAL(av) && AvREIFY(av))
899             av_reify(av);
900         sv = AvARRAY(av)[key];
901         if (key == AvFILLp(av)) {
902             AvARRAY(av)[key] = &PL_sv_undef;
903             do {
904                 AvFILLp(av)--;
905             } while (--key >= 0 && AvARRAY(av)[key] == &PL_sv_undef);
906         }
907         else
908             AvARRAY(av)[key] = &PL_sv_undef;
909         if (SvSMAGICAL(av))
910             mg_set((SV*)av);
911     }
912     if (flags & G_DISCARD) {
913         SvREFCNT_dec(sv);
914         sv = NULL;
915     }
916     else if (AvREAL(av))
917         sv = sv_2mortal(sv);
918     return sv;
919 }
920
921 /*
922 =for apidoc av_exists
923
924 Returns true if the element indexed by C<key> has been initialized.
925
926 This relies on the fact that uninitialized array elements are set to
927 C<&PL_sv_undef>.
928
929 =cut
930 */
931 bool
932 Perl_av_exists(pTHX_ AV *av, I32 key)
933 {
934     dVAR;
935     PERL_ARGS_ASSERT_AV_EXISTS;
936     assert(SvTYPE(av) == SVt_PVAV);
937
938     if (SvRMAGICAL(av)) {
939         const MAGIC * const tied_magic = mg_find((SV*)av, PERL_MAGIC_tied);
940         if (tied_magic || mg_find((SV*)av, PERL_MAGIC_regdata)) {
941             SV * const sv = sv_newmortal();
942             MAGIC *mg;
943             /* Handle negative array indices 20020222 MJD */
944             if (key < 0) {
945                 unsigned adjust_index = 1;
946                 if (tied_magic) {
947                     SV * const * const negative_indices_glob =
948                         hv_fetch(SvSTASH(SvRV(SvTIED_obj((SV *)av, 
949                                                          tied_magic))), 
950                                  NEGATIVE_INDICES_VAR, 16, 0);
951                     if (negative_indices_glob
952                         && SvTRUE(GvSV(*negative_indices_glob)))
953                         adjust_index = 0;
954                 }
955                 if (adjust_index) {
956                     key += AvFILL(av) + 1;
957                     if (key < 0)
958                         return FALSE;
959                 }
960             }
961
962             mg_copy((SV*)av, sv, 0, key);
963             mg = mg_find(sv, PERL_MAGIC_tiedelem);
964             if (mg) {
965                 magic_existspack(sv, mg);
966                 return (bool)SvTRUE(sv);
967             }
968
969         }
970     }
971
972     if (key < 0) {
973         key += AvFILL(av) + 1;
974         if (key < 0)
975             return FALSE;
976     }
977
978     if (key <= AvFILLp(av) && AvARRAY(av)[key] != &PL_sv_undef
979         && AvARRAY(av)[key])
980     {
981         return TRUE;
982     }
983     else
984         return FALSE;
985 }
986
987 static MAGIC *
988 S_get_aux_mg(pTHX_ AV *av) {
989     dVAR;
990     MAGIC *mg;
991
992     PERL_ARGS_ASSERT_GET_AUX_MG;
993     assert(SvTYPE(av) == SVt_PVAV);
994
995     mg = mg_find((SV*)av, PERL_MAGIC_arylen_p);
996
997     if (!mg) {
998         mg = sv_magicext((SV*)av, 0, PERL_MAGIC_arylen_p, &PL_vtbl_arylen_p,
999                          0, 0);
1000         assert(mg);
1001         /* sv_magicext won't set this for us because we pass in a NULL obj  */
1002         mg->mg_flags |= MGf_REFCOUNTED;
1003     }
1004     return mg;
1005 }
1006
1007 SV **
1008 Perl_av_arylen_p(pTHX_ AV *av) {
1009     MAGIC *const mg = get_aux_mg(av);
1010
1011     PERL_ARGS_ASSERT_AV_ARYLEN_P;
1012     assert(SvTYPE(av) == SVt_PVAV);
1013
1014     return &(mg->mg_obj);
1015 }
1016
1017 IV *
1018 Perl_av_iter_p(pTHX_ AV *av) {
1019     MAGIC *const mg = get_aux_mg(av);
1020
1021     PERL_ARGS_ASSERT_AV_ITER_P;
1022     assert(SvTYPE(av) == SVt_PVAV);
1023
1024 #if IVSIZE == I32SIZE
1025     return (IV *)&(mg->mg_len);
1026 #else
1027     if (!mg->mg_ptr) {
1028         IV *temp;
1029         mg->mg_len = IVSIZE;
1030         Newxz(temp, 1, IV);
1031         mg->mg_ptr = (char *) temp;
1032     }
1033     return (IV *)mg->mg_ptr;
1034 #endif
1035 }
1036
1037 /*
1038  * Local variables:
1039  * c-indentation-style: bsd
1040  * c-basic-offset: 4
1041  * indent-tabs-mode: t
1042  * End:
1043  *
1044  * ex: set ts=8 sts=4 sw=4 noet:
1045  */