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));
764 Returns the highest index in the array. The number of elements in the
765 array is C<av_len(av) + 1>. Returns -1 if the array is empty.
767 The Perl equivalent for this is C<$#myarray>.
773 Perl_av_len(pTHX_ AV *av)
775 PERL_ARGS_ASSERT_AV_LEN;
776 assert(SvTYPE(av) == SVt_PVAV);
784 Set the highest index in the array to the given number, equivalent to
785 Perl's C<$#array = $fill;>.
787 The number of elements in the an array will be C<fill + 1> after
788 av_fill() returns. If the array was previously shorter, then the
789 additional elements appended are set to C<PL_sv_undef>. If the array
790 was longer, then the excess elements are freed. C<av_fill(av, -1)> is
791 the same as C<av_clear(av)>.
796 Perl_av_fill(pTHX_ AV *av, I32 fill)
801 PERL_ARGS_ASSERT_AV_FILL;
802 assert(SvTYPE(av) == SVt_PVAV);
806 if ((mg = SvTIED_mg((const SV *)av, PERL_MAGIC_tied))) {
807 SV *arg1 = sv_newmortal();
808 sv_setiv(arg1, (IV)(fill + 1));
809 Perl_magic_methcall(aTHX_ MUTABLE_SV(av), mg, "STORESIZE", G_DISCARD,
813 if (fill <= AvMAX(av)) {
814 I32 key = AvFILLp(av);
815 SV** const ary = AvARRAY(av);
819 SvREFCNT_dec(ary[key]);
820 ary[key--] = &PL_sv_undef;
825 ary[++key] = &PL_sv_undef;
830 mg_set(MUTABLE_SV(av));
833 (void)av_store(av,fill,&PL_sv_undef);
837 =for apidoc av_delete
839 Deletes the element indexed by C<key> from the array, makes the element mortal,
840 and returns it. If C<flags> equals C<G_DISCARD>, the element is freed and null
841 is returned. Perl equivalent: C<my $elem = delete($myarray[$idx]);> for the
842 non-C<G_DISCARD> version and a void-context C<delete($myarray[$idx]);> for the
843 C<G_DISCARD> version.
848 Perl_av_delete(pTHX_ AV *av, I32 key, I32 flags)
853 PERL_ARGS_ASSERT_AV_DELETE;
854 assert(SvTYPE(av) == SVt_PVAV);
857 Perl_croak_no_modify();
859 if (SvRMAGICAL(av)) {
860 const MAGIC * const tied_magic
861 = mg_find((const SV *)av, PERL_MAGIC_tied);
862 if ((tied_magic || mg_find((const SV *)av, PERL_MAGIC_regdata))) {
865 if (!S_adjust_index(aTHX_ av, tied_magic, &key))
868 svp = av_fetch(av, key, TRUE);
872 if (mg_find(sv, PERL_MAGIC_tiedelem)) {
873 sv_unmagic(sv, PERL_MAGIC_tiedelem); /* No longer an element */
882 key += AvFILL(av) + 1;
887 if (key > AvFILLp(av))
890 if (!AvREAL(av) && AvREIFY(av))
892 sv = AvARRAY(av)[key];
893 if (key == AvFILLp(av)) {
894 AvARRAY(av)[key] = &PL_sv_undef;
897 } while (--key >= 0 && AvARRAY(av)[key] == &PL_sv_undef);
900 AvARRAY(av)[key] = &PL_sv_undef;
902 mg_set(MUTABLE_SV(av));
904 if (flags & G_DISCARD) {
914 =for apidoc av_exists
916 Returns true if the element indexed by C<key> has been initialized.
918 This relies on the fact that uninitialized array elements are set to
921 Perl equivalent: C<exists($myarray[$key])>.
926 Perl_av_exists(pTHX_ AV *av, I32 key)
929 PERL_ARGS_ASSERT_AV_EXISTS;
930 assert(SvTYPE(av) == SVt_PVAV);
932 if (SvRMAGICAL(av)) {
933 const MAGIC * const tied_magic
934 = mg_find((const SV *)av, PERL_MAGIC_tied);
935 const MAGIC * const regdata_magic
936 = mg_find((const SV *)av, PERL_MAGIC_regdata);
937 if (tied_magic || regdata_magic) {
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 SV * const sv = sv_newmortal();
953 mg_copy(MUTABLE_SV(av), sv, 0, key);
954 mg = mg_find(sv, PERL_MAGIC_tiedelem);
956 magic_existspack(sv, mg);
958 I32 retbool = SvTRUE_nomg_NN(sv);
959 return cBOOL(retbool);
967 key += AvFILL(av) + 1;
972 if (key <= AvFILLp(av) && AvARRAY(av)[key] != &PL_sv_undef
982 S_get_aux_mg(pTHX_ AV *av) {
986 PERL_ARGS_ASSERT_GET_AUX_MG;
987 assert(SvTYPE(av) == SVt_PVAV);
989 mg = mg_find((const SV *)av, PERL_MAGIC_arylen_p);
992 mg = sv_magicext(MUTABLE_SV(av), 0, PERL_MAGIC_arylen_p,
993 &PL_vtbl_arylen_p, 0, 0);
995 /* sv_magicext won't set this for us because we pass in a NULL obj */
996 mg->mg_flags |= MGf_REFCOUNTED;
1002 Perl_av_arylen_p(pTHX_ AV *av) {
1003 MAGIC *const mg = get_aux_mg(av);
1005 PERL_ARGS_ASSERT_AV_ARYLEN_P;
1006 assert(SvTYPE(av) == SVt_PVAV);
1008 return &(mg->mg_obj);
1012 Perl_av_iter_p(pTHX_ AV *av) {
1013 MAGIC *const mg = get_aux_mg(av);
1015 PERL_ARGS_ASSERT_AV_ITER_P;
1016 assert(SvTYPE(av) == SVt_PVAV);
1018 #if IVSIZE == I32SIZE
1019 return (IV *)&(mg->mg_len);
1023 mg->mg_len = IVSIZE;
1025 mg->mg_ptr = (char *) temp;
1027 return (IV *)mg->mg_ptr;
1033 * c-indentation-style: bsd
1035 * indent-tabs-mode: nil
1038 * ex: set ts=8 sts=4 sw=4 et: