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_ 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_ 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_ I32 size, 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_ 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_ 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_ 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 Removes one SV from the end of the array, reducing its size by one and
596 returning the SV (transferring control of one reference count) to the
597 caller. Returns C<&PL_sv_undef> if the array is empty.
599 Perl equivalent: C<pop(@myarray);>
605 Perl_av_pop(pTHX_ AV *av)
611 PERL_ARGS_ASSERT_AV_POP;
612 assert(SvTYPE(av) == SVt_PVAV);
615 Perl_croak_no_modify();
616 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
617 retval = Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "POP", 0, 0);
619 retval = newSVsv(retval);
624 retval = AvARRAY(av)[AvFILLp(av)];
625 AvARRAY(av)[AvFILLp(av)--] = &PL_sv_undef;
627 mg_set(MUTABLE_SV(av));
633 =for apidoc av_create_and_unshift_one
635 Unshifts an SV onto the beginning of the array, creating the array if
637 A small internal helper function to remove a commonly duplicated idiom.
643 Perl_av_create_and_unshift_one(pTHX_ AV **const avp, SV *const val)
645 PERL_ARGS_ASSERT_AV_CREATE_AND_UNSHIFT_ONE;
650 return av_store(*avp, 0, val);
654 =for apidoc av_unshift
656 Unshift the given number of C<undef> values onto the beginning of the
657 array. The array will grow automatically to accommodate the addition. You
658 must then use C<av_store> to assign values to these new elements.
660 Perl equivalent: C<unshift @myarray, ( (undef) x $n );>
666 Perl_av_unshift(pTHX_ AV *av, I32 num)
672 PERL_ARGS_ASSERT_AV_UNSHIFT;
673 assert(SvTYPE(av) == SVt_PVAV);
676 Perl_croak_no_modify();
678 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
679 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "UNSHIFT",
680 G_DISCARD | G_UNDEF_FILL, num);
686 if (!AvREAL(av) && AvREIFY(av))
688 i = AvARRAY(av) - AvALLOC(av);
696 AvARRAY(av) = AvARRAY(av) - i;
700 const I32 i = AvFILLp(av);
701 /* Create extra elements */
702 const I32 slide = i > 0 ? i : 0;
704 av_extend(av, i + num);
707 Move(ary, ary + num, i + 1, SV*);
709 ary[--num] = &PL_sv_undef;
711 /* Make extra elements into a buffer */
713 AvFILLp(av) -= slide;
714 AvARRAY(av) = AvARRAY(av) + slide;
721 Shifts an SV off the beginning of the
722 array. Returns C<&PL_sv_undef> if the
725 Perl equivalent: C<shift(@myarray);>
731 Perl_av_shift(pTHX_ AV *av)
737 PERL_ARGS_ASSERT_AV_SHIFT;
738 assert(SvTYPE(av) == SVt_PVAV);
741 Perl_croak_no_modify();
742 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
743 retval = Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "SHIFT", 0, 0);
745 retval = newSVsv(retval);
750 retval = *AvARRAY(av);
752 *AvARRAY(av) = &PL_sv_undef;
753 AvARRAY(av) = AvARRAY(av) + 1;
757 mg_set(MUTABLE_SV(av));
762 =for apidoc av_top_index
764 Returns the highest index in the array. The number of elements in the
765 array is C<av_top_index(av) + 1>. Returns -1 if the array is empty.
767 The Perl equivalent for this is C<$#myarray>.
769 (A slightly shorter form is C<av_tindex>.)
773 Same as L</av_top_index>. Returns the highest index in the array. Note that the
774 return value is +1 what its name implies it returns; and hence differs in
775 meaning from what the similarly named L</sv_len> returns.
781 Perl_av_len(pTHX_ AV *av)
783 PERL_ARGS_ASSERT_AV_LEN;
785 return av_top_index(av);
791 Set the highest index in the array to the given number, equivalent to
792 Perl's C<$#array = $fill;>.
794 The number of elements in the an array will be C<fill + 1> after
795 av_fill() returns. If the array was previously shorter, then the
796 additional elements appended are set to C<PL_sv_undef>. If the array
797 was longer, then the excess elements are freed. C<av_fill(av, -1)> is
798 the same as C<av_clear(av)>.
803 Perl_av_fill(pTHX_ AV *av, I32 fill)
808 PERL_ARGS_ASSERT_AV_FILL;
809 assert(SvTYPE(av) == SVt_PVAV);
813 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
814 SV *arg1 = sv_newmortal();
815 sv_setiv(arg1, (IV)(fill + 1));
816 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "STORESIZE", G_DISCARD,
820 if (fill <= AvMAX(av)) {
821 I32 key = AvFILLp(av);
822 SV** const ary = AvARRAY(av);
826 SvREFCNT_dec(ary[key]);
827 ary[key--] = &PL_sv_undef;
832 ary[++key] = &PL_sv_undef;
837 mg_set(MUTABLE_SV(av));
840 (void)av_store(av,fill,&PL_sv_undef);
844 =for apidoc av_delete
846 Deletes the element indexed by C<key> from the array, makes the element mortal,
847 and returns it. If C<flags> equals C<G_DISCARD>, the element is freed and null
848 is returned. Perl equivalent: C<my $elem = delete($myarray[$idx]);> for the
849 non-C<G_DISCARD> version and a void-context C<delete($myarray[$idx]);> for the
850 C<G_DISCARD> version.
855 Perl_av_delete(pTHX_ AV *av, I32 key, I32 flags)
860 PERL_ARGS_ASSERT_AV_DELETE;
861 assert(SvTYPE(av) == SVt_PVAV);
864 Perl_croak_no_modify();
866 if (SvRMAGICAL(av)) {
867 const MAGIC * const tied_magic
868 = mg_find((const SV *)av, PERL_MAGIC_tied);
869 if ((tied_magic || mg_find((const SV *)av, PERL_MAGIC_regdata))) {
872 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
875 svp = av_fetch(av, key, TRUE);
879 if (mg_find(sv, PERL_MAGIC_tiedelem)) {
880 sv_unmagic(sv, PERL_MAGIC_tiedelem); /* No longer an element */
889 key += AvFILL(av) + 1;
894 if (key > AvFILLp(av))
897 if (!AvREAL(av) && AvREIFY(av))
899 sv = AvARRAY(av)[key];
900 if (key == AvFILLp(av)) {
901 AvARRAY(av)[key] = &PL_sv_undef;
904 } while (--key >= 0 && AvARRAY(av)[key] == &PL_sv_undef);
907 AvARRAY(av)[key] = &PL_sv_undef;
909 mg_set(MUTABLE_SV(av));
911 if (flags & G_DISCARD) {
921 =for apidoc av_exists
923 Returns true if the element indexed by C<key> has been initialized.
925 This relies on the fact that uninitialized array elements are set to
928 Perl equivalent: C<exists($myarray[$key])>.
933 Perl_av_exists(pTHX_ AV *av, I32 key)
936 PERL_ARGS_ASSERT_AV_EXISTS;
937 assert(SvTYPE(av) == SVt_PVAV);
939 if (SvRMAGICAL(av)) {
940 const MAGIC * const tied_magic
941 = mg_find((const SV *)av, PERL_MAGIC_tied);
942 const MAGIC * const regdata_magic
943 = mg_find((const SV *)av, PERL_MAGIC_regdata);
944 if (tied_magic || regdata_magic) {
946 /* Handle negative array indices 20020222 MJD */
948 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
952 if(key >= 0 && regdata_magic) {
953 if (key <= AvFILL(av))
959 SV * const sv = sv_newmortal();
960 mg_copy(MUTABLE_SV(av), sv, 0, key);
961 mg = mg_find(sv, PERL_MAGIC_tiedelem);
963 magic_existspack(sv, mg);
965 I32 retbool = SvTRUE_nomg_NN(sv);
966 return cBOOL(retbool);
974 key += AvFILL(av) + 1;
979 if (key <= AvFILLp(av) && AvARRAY(av)[key] != &PL_sv_undef
989 S_get_aux_mg(pTHX_ AV *av) {
993 PERL_ARGS_ASSERT_GET_AUX_MG;
994 assert(SvTYPE(av) == SVt_PVAV);
996 mg = mg_find((const SV *)av, PERL_MAGIC_arylen_p);
999 mg = sv_magicext(MUTABLE_SV(av), 0, PERL_MAGIC_arylen_p,
1000 &PL_vtbl_arylen_p, 0, 0);
1002 /* sv_magicext won't set this for us because we pass in a NULL obj */
1003 mg->mg_flags |= MGf_REFCOUNTED;
1009 Perl_av_arylen_p(pTHX_ AV *av) {
1010 MAGIC *const mg = get_aux_mg(av);
1012 PERL_ARGS_ASSERT_AV_ARYLEN_P;
1013 assert(SvTYPE(av) == SVt_PVAV);
1015 return &(mg->mg_obj);
1019 Perl_av_iter_p(pTHX_ AV *av) {
1020 MAGIC *const mg = get_aux_mg(av);
1022 PERL_ARGS_ASSERT_AV_ITER_P;
1023 assert(SvTYPE(av) == SVt_PVAV);
1025 #if IVSIZE == I32SIZE
1026 return (IV *)&(mg->mg_len);
1030 mg->mg_len = IVSIZE;
1032 mg->mg_ptr = (char *) temp;
1034 return (IV *)mg->mg_ptr;
1040 * c-indentation-style: bsd
1042 * indent-tabs-mode: nil
1045 * ex: set ts=8 sts=4 sw=4 et: