3 * Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
4 * 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 by Larry Wall and others
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.
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
15 * [p.476 of _The Lord of the Rings_, III/iv: "Treebeard"]
19 =head1 Array Manipulation Functions
27 Perl_av_reify(pTHX_ AV *av)
32 PERL_ARGS_ASSERT_AV_REIFY;
33 assert(SvTYPE(av) == SVt_PVAV);
38 if (SvTIED_mg((const SV *)av, PERL_MAGIC_tied))
39 Perl_ck_warner_d(aTHX_ packWARN(WARN_DEBUGGING), "av_reify called on tied array");
42 while (key > AvFILLp(av) + 1)
43 AvARRAY(av)[--key] = &PL_sv_undef;
45 SV * const sv = AvARRAY(av)[--key];
47 if (sv != &PL_sv_undef)
48 SvREFCNT_inc_simple_void_NN(sv);
50 key = AvARRAY(av) - AvALLOC(av);
52 AvALLOC(av)[--key] = &PL_sv_undef;
60 Pre-extend an array. The C<key> is the index to which the array should be
67 Perl_av_extend(pTHX_ AV *av, I32 key)
72 PERL_ARGS_ASSERT_AV_EXTEND;
73 assert(SvTYPE(av) == SVt_PVAV);
75 mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied);
77 SV *arg1 = sv_newmortal();
78 sv_setiv(arg1, (IV)(key + 1));
79 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "EXTEND", G_DISCARD, 1,
83 av_extend_guts(av,key,&AvMAX(av),&AvALLOC(av),&AvARRAY(av));
86 /* The guts of av_extend. *Not* for general use! */
88 Perl_av_extend_guts(pTHX_ AV *av, I32 key, SSize_t *maxp, SV ***allocp,
93 PERL_ARGS_ASSERT_AV_EXTEND_GUTS;
100 if (av && *allocp != *arrayp) {
101 ary = *allocp + AvFILLp(av) + 1;
102 tmp = *arrayp - *allocp;
103 Move(*arrayp, *allocp, AvFILLp(av)+1, SV*);
108 ary[--tmp] = &PL_sv_undef;
110 if (key > *maxp - 10) {
111 newmax = key + *maxp;
116 #ifdef PERL_MALLOC_WRAP
117 static const char oom_array_extend[] =
118 "Out of memory during array extend"; /* Duplicated in pp_hot.c */
122 #if !defined(STRANGE_MALLOC) && !defined(MYMALLOC)
127 #ifdef Perl_safesysmalloc_size
128 /* Whilst it would be quite possible to move this logic around
129 (as I did in the SV code), so as to set AvMAX(av) early,
130 based on calling Perl_safesysmalloc_size() immediately after
131 allocation, I'm not convinced that it is a great idea here.
132 In an array we have to loop round setting everything to
133 &PL_sv_undef, which means writing to memory, potentially lots
134 of it, whereas for the SV buffer case we don't touch the
135 "bonus" memory. So there there is no cost in telling the
136 world about it, whereas here we have to do work before we can
137 tell the world about it, and that work involves writing to
138 memory that might never be read. So, I feel, better to keep
139 the current lazy system of only writing to it if our caller
140 has a need for more space. NWC */
141 newmax = Perl_safesysmalloc_size((void*)*allocp) /
142 sizeof(const SV *) - 1;
147 newmax = key + *maxp / 5;
149 MEM_WRAP_CHECK_1(newmax+1, SV*, oom_array_extend);
150 #if defined(STRANGE_MALLOC) || defined(MYMALLOC)
151 Renew(*allocp,newmax+1, SV*);
153 bytes = (newmax + 1) * sizeof(const SV *);
154 #define MALLOC_OVERHEAD 16
155 itmp = MALLOC_OVERHEAD;
156 while ((MEM_SIZE)(itmp - MALLOC_OVERHEAD) < bytes)
158 itmp -= MALLOC_OVERHEAD;
159 itmp /= sizeof(const SV *);
160 assert(itmp > newmax);
162 assert(newmax >= *maxp);
163 Newx(ary, newmax+1, SV*);
164 Copy(*allocp, ary, *maxp+1, SV*);
168 #ifdef Perl_safesysmalloc_size
171 ary = *allocp + *maxp + 1;
172 tmp = newmax - *maxp;
173 if (av == PL_curstack) { /* Oops, grew stack (via av_store()?) */
174 PL_stack_sp = *allocp + (PL_stack_sp - PL_stack_base);
175 PL_stack_base = *allocp;
176 PL_stack_max = PL_stack_base + newmax;
180 newmax = key < 3 ? 3 : key;
181 MEM_WRAP_CHECK_1(newmax+1, SV*, oom_array_extend);
182 Newx(*allocp, newmax+1, SV*);
185 *allocp[0] = &PL_sv_undef; /* For the stacks */
187 if (av && AvREAL(av)) {
189 ary[--tmp] = &PL_sv_undef;
201 Returns the SV at the specified index in the array. The C<key> is the
202 index. If lval is true, you are guaranteed to get a real SV back (in case
203 it wasn't real before), which you can then modify. Check that the return
204 value is non-null before dereferencing it to a C<SV*>.
206 See L<perlguts/"Understanding the Magic of Tied Hashes and Arrays"> for
207 more information on how to use this function on tied arrays.
209 The rough perl equivalent is C<$myarray[$idx]>.
215 S_adjust_index(pTHX_ AV *av, const MAGIC *mg, I32 *keyp)
217 bool adjust_index = 1;
219 /* Handle negative array indices 20020222 MJD */
220 SV * const ref = SvTIED_obj(MUTABLE_SV(av), mg);
222 if (SvROK(ref) && SvOBJECT(SvRV(ref))) {
223 SV * const * const negative_indices_glob =
224 hv_fetchs(SvSTASH(SvRV(ref)), NEGATIVE_INDICES_VAR, 0);
226 if (negative_indices_glob && SvTRUE(GvSV(*negative_indices_glob)))
232 *keyp += AvFILL(av) + 1;
240 Perl_av_fetch(pTHX_ register AV *av, I32 key, I32 lval)
244 PERL_ARGS_ASSERT_AV_FETCH;
245 assert(SvTYPE(av) == SVt_PVAV);
247 if (SvRMAGICAL(av)) {
248 const MAGIC * const tied_magic
249 = mg_find((const SV *)av, PERL_MAGIC_tied);
250 if (tied_magic || mg_find((const SV *)av, PERL_MAGIC_regdata)) {
253 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
258 sv_upgrade(sv, SVt_PVLV);
259 mg_copy(MUTABLE_SV(av), sv, 0, key);
260 if (!tied_magic) /* for regdata, force leavesub to make copies */
263 LvTARG(sv) = sv; /* fake (SV**) */
264 return &(LvTARG(sv));
269 key += AvFILL(av) + 1;
274 if (key > AvFILLp(av) || AvARRAY(av)[key] == &PL_sv_undef) {
276 return lval ? av_store(av,key,newSV(0)) : NULL;
280 && (!AvARRAY(av)[key] /* eg. @_ could have freed elts */
281 || SvIS_FREED(AvARRAY(av)[key]))) {
282 AvARRAY(av)[key] = &PL_sv_undef; /* 1/2 reify */
285 return &AvARRAY(av)[key];
291 Stores an SV in an array. The array index is specified as C<key>. The
292 return value will be NULL if the operation failed or if the value did not
293 need to be actually stored within the array (as in the case of tied
294 arrays). Otherwise, it can be dereferenced
295 to get the C<SV*> that was stored
298 Note that the caller is responsible for suitably incrementing the reference
299 count of C<val> before the call, and decrementing it if the function
302 Approximate Perl equivalent: C<$myarray[$key] = $val;>.
304 See L<perlguts/"Understanding the Magic of Tied Hashes and Arrays"> for
305 more information on how to use this function on tied arrays.
311 Perl_av_store(pTHX_ register AV *av, I32 key, SV *val)
316 PERL_ARGS_ASSERT_AV_STORE;
317 assert(SvTYPE(av) == SVt_PVAV);
319 /* S_regclass relies on being able to pass in a NULL sv
320 (unicode_alternate may be NULL).
326 if (SvRMAGICAL(av)) {
327 const MAGIC * const tied_magic = mg_find((const SV *)av, PERL_MAGIC_tied);
330 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
333 if (val != &PL_sv_undef) {
334 mg_copy(MUTABLE_SV(av), val, 0, key);
342 key += AvFILL(av) + 1;
347 if (SvREADONLY(av) && key >= AvFILL(av))
348 Perl_croak_no_modify();
350 if (!AvREAL(av) && AvREIFY(av))
355 if (AvFILLp(av) < key) {
357 if (av == PL_curstack && key > PL_stack_sp - PL_stack_base)
358 PL_stack_sp = PL_stack_base + key; /* XPUSH in disguise */
360 ary[++AvFILLp(av)] = &PL_sv_undef;
361 } while (AvFILLp(av) < key);
366 SvREFCNT_dec(ary[key]);
368 if (SvSMAGICAL(av)) {
369 const MAGIC *mg = SvMAGIC(av);
371 for (; mg; mg = mg->mg_moremagic) {
372 if (!isUPPER(mg->mg_type)) continue;
373 if (val != &PL_sv_undef) {
374 sv_magic(val, MUTABLE_SV(av), toLOWER(mg->mg_type), 0, key);
376 if (PL_delaymagic && mg->mg_type == PERL_MAGIC_isa) {
377 PL_delaymagic |= DM_ARRAY_ISA;
382 mg_set(MUTABLE_SV(av));
390 Creates a new AV and populates it with a list of SVs. The SVs are copied
391 into the array, so they may be freed after the call to av_make. The new AV
392 will have a reference count of 1.
394 Perl equivalent: C<my @new_array = ($scalar1, $scalar2, $scalar3...);>
400 Perl_av_make(pTHX_ register I32 size, register SV **strp)
402 AV * const av = MUTABLE_AV(newSV_type(SVt_PVAV));
403 /* sv_upgrade does AvREAL_only() */
404 PERL_ARGS_ASSERT_AV_MAKE;
405 assert(SvTYPE(av) == SVt_PVAV);
407 if (size) { /* "defined" was returning undef for size==0 anyway. */
413 AvMAX(av) = size - 1;
417 for (i = 0; i < size; i++) {
420 /* Don't let sv_setsv swipe, since our source array might
421 have multiple references to the same temp scalar (e.g.
422 from a list slice) */
424 SvGETMAGIC(*strp); /* before newSV, in case it dies */
427 sv_setsv_flags(ary[i], *strp,
428 SV_DO_COW_SVSETSV|SV_NOSTEAL);
431 SvREFCNT_inc_simple_void_NN(av);
440 Clears an array, making it empty. Does not free the memory the av uses to
441 store its list of scalars. If any destructors are triggered as a result,
442 the av itself may be freed when this function returns.
444 Perl equivalent: C<@myarray = ();>.
450 Perl_av_clear(pTHX_ register AV *av)
456 PERL_ARGS_ASSERT_AV_CLEAR;
457 assert(SvTYPE(av) == SVt_PVAV);
460 if (SvREFCNT(av) == 0) {
461 Perl_ck_warner_d(aTHX_ packWARN(WARN_DEBUGGING), "Attempt to clear deleted array");
466 Perl_croak_no_modify();
468 /* Give any tie a chance to cleanup first */
469 if (SvRMAGICAL(av)) {
470 const MAGIC* const mg = SvMAGIC(av);
471 if (PL_delaymagic && mg && mg->mg_type == PERL_MAGIC_isa)
472 PL_delaymagic |= DM_ARRAY_ISA;
474 mg_clear(MUTABLE_SV(av));
480 if ((real = !!AvREAL(av))) {
481 SV** const ary = AvARRAY(av);
482 I32 index = AvFILLp(av) + 1;
484 SAVEFREESV(SvREFCNT_inc_simple_NN(av));
486 SV * const sv = ary[--index];
487 /* undef the slot before freeing the value, because a
488 * destructor might try to modify this array */
489 ary[index] = &PL_sv_undef;
493 extra = AvARRAY(av) - AvALLOC(av);
496 AvARRAY(av) = AvALLOC(av);
505 Undefines the array. Frees the memory used by the av to store its list of
506 scalars. If any destructors are triggered as a result, the av itself may
513 Perl_av_undef(pTHX_ register AV *av)
517 PERL_ARGS_ASSERT_AV_UNDEF;
518 assert(SvTYPE(av) == SVt_PVAV);
520 /* Give any tie a chance to cleanup first */
521 if (SvTIED_mg((const SV *)av, PERL_MAGIC_tied))
524 if ((real = !!AvREAL(av))) {
525 I32 key = AvFILLp(av) + 1;
527 SAVEFREESV(SvREFCNT_inc_simple_NN(av));
529 SvREFCNT_dec(AvARRAY(av)[--key]);
532 Safefree(AvALLOC(av));
535 AvMAX(av) = AvFILLp(av) = -1;
537 if(SvRMAGICAL(av)) mg_clear(MUTABLE_SV(av));
543 =for apidoc av_create_and_push
545 Push an SV onto the end of the array, creating the array if necessary.
546 A small internal helper function to remove a commonly duplicated idiom.
552 Perl_av_create_and_push(pTHX_ AV **const avp, SV *const val)
554 PERL_ARGS_ASSERT_AV_CREATE_AND_PUSH;
564 Pushes an SV onto the end of the array. The array will grow automatically
565 to accommodate the addition. This takes ownership of one reference count.
567 Perl equivalent: C<push @myarray, $elem;>.
573 Perl_av_push(pTHX_ register AV *av, SV *val)
578 PERL_ARGS_ASSERT_AV_PUSH;
579 assert(SvTYPE(av) == SVt_PVAV);
582 Perl_croak_no_modify();
584 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
585 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "PUSH", G_DISCARD, 1,
589 av_store(av,AvFILLp(av)+1,val);
595 Pops an SV off the end of the array. Returns C<&PL_sv_undef> if the array
598 Perl equivalent: C<pop(@myarray);>
604 Perl_av_pop(pTHX_ register AV *av)
610 PERL_ARGS_ASSERT_AV_POP;
611 assert(SvTYPE(av) == SVt_PVAV);
614 Perl_croak_no_modify();
615 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
616 retval = Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "POP", 0, 0);
618 retval = newSVsv(retval);
623 retval = AvARRAY(av)[AvFILLp(av)];
624 AvARRAY(av)[AvFILLp(av)--] = &PL_sv_undef;
626 mg_set(MUTABLE_SV(av));
632 =for apidoc av_create_and_unshift_one
634 Unshifts an SV onto the beginning of the array, creating the array if
636 A small internal helper function to remove a commonly duplicated idiom.
642 Perl_av_create_and_unshift_one(pTHX_ AV **const avp, SV *const val)
644 PERL_ARGS_ASSERT_AV_CREATE_AND_UNSHIFT_ONE;
649 return av_store(*avp, 0, val);
653 =for apidoc av_unshift
655 Unshift the given number of C<undef> values onto the beginning of the
656 array. The array will grow automatically to accommodate the addition. You
657 must then use C<av_store> to assign values to these new elements.
659 Perl equivalent: C<unshift @myarray, ( (undef) x $n );>
665 Perl_av_unshift(pTHX_ register AV *av, register I32 num)
671 PERL_ARGS_ASSERT_AV_UNSHIFT;
672 assert(SvTYPE(av) == SVt_PVAV);
675 Perl_croak_no_modify();
677 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
678 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "UNSHIFT",
679 G_DISCARD | G_UNDEF_FILL, num);
685 if (!AvREAL(av) && AvREIFY(av))
687 i = AvARRAY(av) - AvALLOC(av);
695 AvARRAY(av) = AvARRAY(av) - i;
699 const I32 i = AvFILLp(av);
700 /* Create extra elements */
701 const I32 slide = i > 0 ? i : 0;
703 av_extend(av, i + num);
706 Move(ary, ary + num, i + 1, SV*);
708 ary[--num] = &PL_sv_undef;
710 /* Make extra elements into a buffer */
712 AvFILLp(av) -= slide;
713 AvARRAY(av) = AvARRAY(av) + slide;
720 Shifts an SV off the beginning of the
721 array. Returns C<&PL_sv_undef> if the
724 Perl equivalent: C<shift(@myarray);>
730 Perl_av_shift(pTHX_ register AV *av)
736 PERL_ARGS_ASSERT_AV_SHIFT;
737 assert(SvTYPE(av) == SVt_PVAV);
740 Perl_croak_no_modify();
741 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
742 retval = Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "SHIFT", 0, 0);
744 retval = newSVsv(retval);
749 retval = *AvARRAY(av);
751 *AvARRAY(av) = &PL_sv_undef;
752 AvARRAY(av) = AvARRAY(av) + 1;
756 mg_set(MUTABLE_SV(av));
763 Returns the highest index in the array. The number of elements in the
764 array is C<av_len(av) + 1>. Returns -1 if the array is empty.
766 The Perl equivalent for this is C<$#myarray>.
772 Perl_av_len(pTHX_ AV *av)
774 PERL_ARGS_ASSERT_AV_LEN;
775 assert(SvTYPE(av) == SVt_PVAV);
783 Set the highest index in the array to the given number, equivalent to
784 Perl's C<$#array = $fill;>.
786 The number of elements in the an array will be C<fill + 1> after
787 av_fill() returns. If the array was previously shorter, then the
788 additional elements appended are set to C<PL_sv_undef>. If the array
789 was longer, then the excess elements are freed. C<av_fill(av, -1)> is
790 the same as C<av_clear(av)>.
795 Perl_av_fill(pTHX_ register AV *av, I32 fill)
800 PERL_ARGS_ASSERT_AV_FILL;
801 assert(SvTYPE(av) == SVt_PVAV);
805 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
806 SV *arg1 = sv_newmortal();
807 sv_setiv(arg1, (IV)(fill + 1));
808 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "STORESIZE", G_DISCARD,
812 if (fill <= AvMAX(av)) {
813 I32 key = AvFILLp(av);
814 SV** const ary = AvARRAY(av);
818 SvREFCNT_dec(ary[key]);
819 ary[key--] = &PL_sv_undef;
824 ary[++key] = &PL_sv_undef;
829 mg_set(MUTABLE_SV(av));
832 (void)av_store(av,fill,&PL_sv_undef);
836 =for apidoc av_delete
838 Deletes the element indexed by C<key> from the array, makes the element mortal,
839 and returns it. If C<flags> equals C<G_DISCARD>, the element is freed and null
840 is returned. Perl equivalent: C<my $elem = delete($myarray[$idx]);> for the
841 non-C<G_DISCARD> version and a void-context C<delete($myarray[$idx]);> for the
842 C<G_DISCARD> version.
847 Perl_av_delete(pTHX_ AV *av, I32 key, I32 flags)
852 PERL_ARGS_ASSERT_AV_DELETE;
853 assert(SvTYPE(av) == SVt_PVAV);
856 Perl_croak_no_modify();
858 if (SvRMAGICAL(av)) {
859 const MAGIC * const tied_magic
860 = mg_find((const SV *)av, PERL_MAGIC_tied);
861 if ((tied_magic || mg_find((const SV *)av, PERL_MAGIC_regdata))) {
864 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
867 svp = av_fetch(av, key, TRUE);
871 if (mg_find(sv, PERL_MAGIC_tiedelem)) {
872 sv_unmagic(sv, PERL_MAGIC_tiedelem); /* No longer an element */
881 key += AvFILL(av) + 1;
886 if (key > AvFILLp(av))
889 if (!AvREAL(av) && AvREIFY(av))
891 sv = AvARRAY(av)[key];
892 if (key == AvFILLp(av)) {
893 AvARRAY(av)[key] = &PL_sv_undef;
896 } while (--key >= 0 && AvARRAY(av)[key] == &PL_sv_undef);
899 AvARRAY(av)[key] = &PL_sv_undef;
901 mg_set(MUTABLE_SV(av));
903 if (flags & G_DISCARD) {
913 =for apidoc av_exists
915 Returns true if the element indexed by C<key> has been initialized.
917 This relies on the fact that uninitialized array elements are set to
920 Perl equivalent: C<exists($myarray[$key])>.
925 Perl_av_exists(pTHX_ AV *av, I32 key)
928 PERL_ARGS_ASSERT_AV_EXISTS;
929 assert(SvTYPE(av) == SVt_PVAV);
931 if (SvRMAGICAL(av)) {
932 const MAGIC * const tied_magic
933 = mg_find((const SV *)av, PERL_MAGIC_tied);
934 const MAGIC * const regdata_magic
935 = mg_find((const SV *)av, PERL_MAGIC_regdata);
936 if (tied_magic || regdata_magic) {
937 SV * const sv = sv_newmortal();
939 /* Handle negative array indices 20020222 MJD */
941 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
945 if(key >= 0 && regdata_magic) {
946 if (key <= AvFILL(av))
952 mg_copy(MUTABLE_SV(av), sv, 0, key);
953 mg = mg_find(sv, PERL_MAGIC_tiedelem);
955 magic_existspack(sv, mg);
956 return cBOOL(SvTRUE_nomg(sv));
963 key += AvFILL(av) + 1;
968 if (key <= AvFILLp(av) && AvARRAY(av)[key] != &PL_sv_undef
978 S_get_aux_mg(pTHX_ AV *av) {
982 PERL_ARGS_ASSERT_GET_AUX_MG;
983 assert(SvTYPE(av) == SVt_PVAV);
985 mg = mg_find((const SV *)av, PERL_MAGIC_arylen_p);
988 mg = sv_magicext(MUTABLE_SV(av), 0, PERL_MAGIC_arylen_p,
989 &PL_vtbl_arylen_p, 0, 0);
991 /* sv_magicext won't set this for us because we pass in a NULL obj */
992 mg->mg_flags |= MGf_REFCOUNTED;
998 Perl_av_arylen_p(pTHX_ AV *av) {
999 MAGIC *const mg = get_aux_mg(av);
1001 PERL_ARGS_ASSERT_AV_ARYLEN_P;
1002 assert(SvTYPE(av) == SVt_PVAV);
1004 return &(mg->mg_obj);
1008 Perl_av_iter_p(pTHX_ AV *av) {
1009 MAGIC *const mg = get_aux_mg(av);
1011 PERL_ARGS_ASSERT_AV_ITER_P;
1012 assert(SvTYPE(av) == SVt_PVAV);
1014 #if IVSIZE == I32SIZE
1015 return (IV *)&(mg->mg_len);
1019 mg->mg_len = IVSIZE;
1021 mg->mg_ptr = (char *) temp;
1023 return (IV *)mg->mg_ptr;
1029 * c-indentation-style: bsd
1031 * indent-tabs-mode: nil
1034 * ex: set ts=8 sts=4 sw=4 et: