Initial 3-way merge from (5.001m, thr1m, 5.003) plus fixups.
[perl.git] / av.c
1 /*    av.c
2  *
3  *    Copyright (c) 1991-1994, 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 static void     av_reify _((AV* av));
19
20 static void
21 av_reify(av)
22 AV* av;
23 {
24     I32 key;
25     SV* sv;
26     
27     key = AvMAX(av) + 1;
28     while (key > AvFILL(av) + 1)
29         AvARRAY(av)[--key] = &sv_undef;
30     while (key) {
31         sv = AvARRAY(av)[--key];
32         assert(sv);
33         if (sv != &sv_undef) {
34             dTHR;
35             (void)SvREFCNT_inc(sv);
36         }
37     }
38     AvREAL_on(av);
39 }
40
41 void
42 av_extend(av,key)
43 AV *av;
44 I32 key;
45 {
46     dTHR;                       /* only necessary if we have to extend stack */
47     if (key > AvMAX(av)) {
48         SV** ary;
49         I32 tmp;
50         I32 newmax;
51
52         if (AvALLOC(av) != AvARRAY(av)) {
53             ary = AvALLOC(av) + AvFILL(av) + 1;
54             tmp = AvARRAY(av) - AvALLOC(av);
55             Move(AvARRAY(av), AvALLOC(av), AvFILL(av)+1, SV*);
56             AvMAX(av) += tmp;
57             SvPVX(av) = (char*)AvALLOC(av);
58             if (AvREAL(av)) {
59                 while (tmp)
60                     ary[--tmp] = &sv_undef;
61             }
62             
63             if (key > AvMAX(av) - 10) {
64                 newmax = key + AvMAX(av);
65                 goto resize;
66             }
67         }
68         else {
69             if (AvALLOC(av)) {
70 #ifndef STRANGE_MALLOC
71                 U32 bytes;
72 #endif
73
74                 newmax = key + AvMAX(av) / 5;
75               resize:
76 #ifdef STRANGE_MALLOC
77                 Renew(AvALLOC(av),newmax+1, SV*);
78 #else
79                 bytes = (newmax + 1) * sizeof(SV*);
80 #define MALLOC_OVERHEAD 16
81                 tmp = MALLOC_OVERHEAD;
82                 while (tmp - MALLOC_OVERHEAD < bytes)
83                     tmp += tmp;
84                 tmp -= MALLOC_OVERHEAD;
85                 tmp /= sizeof(SV*);
86                 assert(tmp > newmax);
87                 newmax = tmp - 1;
88                 New(2,ary, newmax+1, SV*);
89                 Copy(AvALLOC(av), ary, AvMAX(av)+1, SV*);
90                 if (AvMAX(av) > 64 && !nice_chunk) {
91                     nice_chunk = (char*)AvALLOC(av);
92                     nice_chunk_size = (AvMAX(av) + 1) * sizeof(SV*);
93                 }
94                 else
95                     Safefree(AvALLOC(av));
96                 AvALLOC(av) = ary;
97 #endif
98                 ary = AvALLOC(av) + AvMAX(av) + 1;
99                 tmp = newmax - AvMAX(av);
100                 if (av == stack) {      /* Oops, grew stack (via av_store()?) */
101                     stack_sp = AvALLOC(av) + (stack_sp - stack_base);
102                     stack_base = AvALLOC(av);
103                     stack_max = stack_base + newmax;
104                 }
105             }
106             else {
107                 newmax = key < 4 ? 4 : key;
108                 New(2,AvALLOC(av), newmax+1, SV*);
109                 ary = AvALLOC(av) + 1;
110                 tmp = newmax;
111                 AvALLOC(av)[0] = &sv_undef;     /* For the stacks */
112             }
113             if (AvREAL(av)) {
114                 while (tmp)
115                     ary[--tmp] = &sv_undef;
116             }
117             
118             SvPVX(av) = (char*)AvALLOC(av);
119             AvMAX(av) = newmax;
120         }
121     }
122 }
123
124 SV**
125 av_fetch(av,key,lval)
126 register AV *av;
127 I32 key;
128 I32 lval;
129 {
130     SV *sv;
131
132     if (!av)
133         return 0;
134
135     if (SvRMAGICAL(av)) {
136         if (mg_find((SV*)av,'P')) {
137             dTHR;
138             sv = sv_newmortal();
139             mg_copy((SV*)av, sv, 0, key);
140             Sv = sv;
141             return &Sv;
142         }
143     }
144
145     if (key < 0) {
146         key += AvFILL(av) + 1;
147         if (key < 0)
148             return 0;
149     }
150     else if (key > AvFILL(av)) {
151         if (!lval)
152             return 0;
153         if (AvREALISH(av))
154             sv = NEWSV(5,0);
155         else
156             sv = sv_newmortal();
157         return av_store(av,key,sv);
158     }
159     if (AvARRAY(av)[key] == &sv_undef) {
160         if (lval) {
161             sv = NEWSV(6,0);
162             return av_store(av,key,sv);
163         }
164         return 0;
165     }
166     return &AvARRAY(av)[key];
167 }
168
169 SV**
170 av_store(av,key,val)
171 register AV *av;
172 I32 key;
173 SV *val;
174 {
175     SV** ary;
176
177     if (!av)
178         return 0;
179
180     if (SvRMAGICAL(av)) {
181         if (mg_find((SV*)av,'P')) {
182             mg_copy((SV*)av, val, 0, key);
183             return 0;
184         }
185     }
186
187     if (key < 0) {
188         key += AvFILL(av) + 1;
189         if (key < 0)
190             return 0;
191     }
192     if (!val)
193         val = &sv_undef;
194
195     if (key > AvMAX(av))
196         av_extend(av,key);
197     if (AvREIFY(av))
198         av_reify(av);
199
200     ary = AvARRAY(av);
201     if (AvFILL(av) < key) {
202         if (!AvREAL(av)) {
203             dTHR;
204             if (av == stack && key > stack_sp - stack_base)
205                 stack_sp = stack_base + key;    /* XPUSH in disguise */
206             do
207                 ary[++AvFILL(av)] = &sv_undef;
208             while (AvFILL(av) < key);
209         }
210         AvFILL(av) = key;
211     }
212     else if (AvREAL(av))
213         SvREFCNT_dec(ary[key]);
214     ary[key] = val;
215     if (SvSMAGICAL(av)) {
216         if (val != &sv_undef) {
217             MAGIC* mg = SvMAGIC(av);
218             sv_magic(val, (SV*)av, toLOWER(mg->mg_type), 0, key);
219         }
220         mg_set((SV*)av);
221     }
222     return &ary[key];
223 }
224
225 AV *
226 newAV()
227 {
228     register AV *av;
229
230     av = (AV*)NEWSV(3,0);
231     sv_upgrade((SV *)av, SVt_PVAV);
232     AvREAL_on(av);
233     AvALLOC(av) = 0;
234     SvPVX(av) = 0;
235     AvMAX(av) = AvFILL(av) = -1;
236     return av;
237 }
238
239 AV *
240 av_make(size,strp)
241 register I32 size;
242 register SV **strp;
243 {
244     register AV *av;
245     register I32 i;
246     register SV** ary;
247
248     av = (AV*)NEWSV(8,0);
249     sv_upgrade((SV *) av,SVt_PVAV);
250     New(4,ary,size+1,SV*);
251     AvALLOC(av) = ary;
252     AvFLAGS(av) = AVf_REAL;
253     SvPVX(av) = (char*)ary;
254     AvFILL(av) = size - 1;
255     AvMAX(av) = size - 1;
256     for (i = 0; i < size; i++) {
257         assert (*strp);
258         ary[i] = NEWSV(7,0);
259         sv_setsv(ary[i], *strp);
260         strp++;
261     }
262     return av;
263 }
264
265 AV *
266 av_fake(size,strp)
267 register I32 size;
268 register SV **strp;
269 {
270     register AV *av;
271     register SV** ary;
272
273     av = (AV*)NEWSV(9,0);
274     sv_upgrade((SV *)av, SVt_PVAV);
275     New(4,ary,size+1,SV*);
276     AvALLOC(av) = ary;
277     Copy(strp,ary,size,SV*);
278     AvFLAGS(av) = AVf_REIFY;
279     SvPVX(av) = (char*)ary;
280     AvFILL(av) = size - 1;
281     AvMAX(av) = size - 1;
282     while (size--) {
283         assert (*strp);
284         SvTEMP_off(*strp);
285         strp++;
286     }
287     return av;
288 }
289
290 void
291 av_clear(av)
292 register AV *av;
293 {
294     register I32 key;
295     SV** ary;
296
297     if (!av || AvMAX(av) < 0)
298         return;
299     /*SUPPRESS 560*/
300
301     if (AvREAL(av)) {
302         ary = AvARRAY(av);
303         key = AvFILL(av) + 1;
304         while (key) {
305             SvREFCNT_dec(ary[--key]);
306             ary[key] = &sv_undef;
307         }
308     }
309     if (key = AvARRAY(av) - AvALLOC(av)) {
310         AvMAX(av) += key;
311         SvPVX(av) = (char*)AvALLOC(av);
312     }
313     AvFILL(av) = -1;
314 }
315
316 void
317 av_undef(av)
318 register AV *av;
319 {
320     register I32 key;
321
322     if (!av)
323         return;
324     /*SUPPRESS 560*/
325     if (AvREAL(av)) {
326         key = AvFILL(av) + 1;
327         while (key)
328             SvREFCNT_dec(AvARRAY(av)[--key]);
329     }
330     if (key = AvARRAY(av) - AvALLOC(av)) {
331         AvMAX(av) += key;
332         SvPVX(av) = (char*)AvALLOC(av);
333     }
334     Safefree(AvALLOC(av));
335     AvALLOC(av) = 0;
336     SvPVX(av) = 0;
337     AvMAX(av) = AvFILL(av) = -1;
338     if (AvARYLEN(av)) {
339         SvREFCNT_dec(AvARYLEN(av));
340         AvARYLEN(av) = 0;
341     }
342 }
343
344 void
345 av_push(av,val)
346 register AV *av;
347 SV *val;
348 {
349     if (!av)
350         return;
351     av_store(av,AvFILL(av)+1,val);
352 }
353
354 SV *
355 av_pop(av)
356 register AV *av;
357 {
358     SV *retval;
359
360     if (!av || AvFILL(av) < 0)
361         return &sv_undef;
362     retval = AvARRAY(av)[AvFILL(av)];
363     AvARRAY(av)[AvFILL(av)--] = &sv_undef;
364     if (SvSMAGICAL(av))
365         mg_set((SV*)av);
366     return retval;
367 }
368
369 void
370 av_unshift(av,num)
371 register AV *av;
372 register I32 num;
373 {
374     register I32 i;
375     register SV **sstr,**dstr;
376
377     if (!av || num <= 0)
378         return;
379     if (!AvREAL(av)) {
380         if (AvREIFY(av))
381             av_reify(av);
382         else
383             croak("Can't unshift");
384     }
385     i = AvARRAY(av) - AvALLOC(av);
386     if (i) {
387         if (i > num)
388             i = num;
389         num -= i;
390     
391         AvMAX(av) += i;
392         AvFILL(av) += i;
393         SvPVX(av) = (char*)(AvARRAY(av) - i);
394     }
395     if (num) {
396         av_extend(av,AvFILL(av)+num);
397         AvFILL(av) += num;
398         dstr = AvARRAY(av) + AvFILL(av);
399         sstr = dstr - num;
400 #ifdef BUGGY_MSC5
401  # pragma loop_opt(off) /* don't loop-optimize the following code */
402 #endif /* BUGGY_MSC5 */
403         for (i = AvFILL(av) - num; i >= 0; --i) {
404             *dstr-- = *sstr--;
405 #ifdef BUGGY_MSC5
406  # pragma loop_opt()    /* loop-optimization back to command-line setting */
407 #endif /* BUGGY_MSC5 */
408         }
409         while (num)
410             AvARRAY(av)[--num] = &sv_undef;
411     }
412 }
413
414 SV *
415 av_shift(av)
416 register AV *av;
417 {
418     SV *retval;
419
420     if (!av || AvFILL(av) < 0)
421         return &sv_undef;
422     retval = *AvARRAY(av);
423     if (AvREAL(av))
424         *AvARRAY(av) = &sv_undef;
425     SvPVX(av) = (char*)(AvARRAY(av) + 1);
426     AvMAX(av)--;
427     AvFILL(av)--;
428     if (SvSMAGICAL(av))
429         mg_set((SV*)av);
430     return retval;
431 }
432
433 I32
434 av_len(av)
435 register AV *av;
436 {
437     return AvFILL(av);
438 }
439
440 void
441 av_fill(av, fill)
442 register AV *av;
443 I32 fill;
444 {
445     if (!av)
446         croak("panic: null array");
447     if (fill < 0)
448         fill = -1;
449     if (fill <= AvMAX(av)) {
450         I32 key = AvFILL(av);
451         SV** ary = AvARRAY(av);
452
453         if (AvREAL(av)) {
454             while (key > fill) {
455                 SvREFCNT_dec(ary[key]);
456                 ary[key--] = &sv_undef;
457             }
458         }
459         else {
460             while (key < fill)
461                 ary[++key] = &sv_undef;
462         }
463             
464         AvFILL(av) = fill;
465         if (SvSMAGICAL(av))
466             mg_set((SV*)av);
467     }
468     else
469         (void)av_store(av,fill,&sv_undef);
470 }