1/*
2Copyright (C) 2001-2014, Parrot Foundation.
3
4=head1 NAME
5
6src/pmc/resizablestringarray.pmc - ResizableStringArray PMC
7
8=head1 DESCRIPTION
9
10ResizableStringArray implements a resizeable array which stores Parrot strings
11only. Any ints or floats assigned to elements of the array will first be
12converted to String PMCs and then to native Parrot strings.  PMCs assigned to
13to elements of the array will be stringified by having their C<get_string>
14method called.
15
16=cut
17
18*/
19
20/* HEADERIZER HFILE: none */
21/* HEADERIZER BEGIN: static */
22/* HEADERIZER END: static */
23
24pmclass ResizableStringArray extends FixedStringArray auto_attrs provides array {
25    ATTR UINTVAL resize_threshold; /*max capacity before resizing */
26
27/*
28
29=head2 Functions
30
31=over 4
32
33=item C<void init_int(INTVAL size)>
34
35Initializes the array.
36
37=cut
38
39*/
40
41    VTABLE void init_int(INTVAL size) :manual_wb {
42        SUPER(size);
43        if (size) {
44            SET_ATTR_resize_threshold(INTERP, SELF, size);
45            PARROT_GC_WRITE_BARRIER(INTERP, SELF);
46        }
47    }
48
49
50/*
51
52=item C<STRING *get_string_keyed_int(INTVAL key)>
53
54Returns the Parrot string value of the element at index C<key>.
55
56=cut
57
58*/
59
60    VTABLE STRING *get_string_keyed_int(INTVAL key) :no_wb {
61
62        STRING **str_array;
63        INTVAL size;
64        GET_ATTR_size(INTERP, SELF, size);
65
66        if (key < 0)
67            key += size;
68        if (key < 0)
69                Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
70                    "index out of bounds");
71        if (key >= size)
72            return CONST_STRING(INTERP, "");
73
74        GET_ATTR_str_array(INTERP, SELF, str_array);
75
76        if (!str_array[key])
77            str_array[key] = Parrot_str_new(INTERP, NULL, 0);
78
79        return str_array[key];
80    }
81
82/*
83
84=item C<void set_string_keyed_int(INTVAL key, STRING *value)>
85
86Sets the Parrot string value of the element at index C<key> to C<value>.
87
88=cut
89
90*/
91
92    VTABLE void set_string_keyed_int(INTVAL key, STRING *value) {
93
94        STRING **str_array;
95        INTVAL   size;
96        GET_ATTR_size(INTERP, SELF, size);
97
98        if (key < 0)
99            key += size;
100        if (key < 0)
101                Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
102                    "index out of bounds");
103
104        if (key >= size)
105            SELF.set_integer_native(key+1);
106
107        GET_ATTR_str_array(INTERP, SELF, str_array);
108        str_array[key] = value;
109    }
110
111/*
112
113=item C<void push_string(STRING *value)>
114
115Extends the array by adding an element of value C<*value> to the end of
116the array.
117
118=cut
119
120*/
121
122    VTABLE void push_string(STRING *value) :manual_wb {
123        INTVAL next_idx;
124        GET_ATTR_size(INTERP, SELF, next_idx);
125        SELF.set_string_keyed_int(next_idx, value);
126    }
127
128/*
129
130=item C<STRING *pop_string()>
131
132Removes and returns the last element in the array.
133
134=cut
135
136*/
137
138    VTABLE STRING *pop_string() :manual_wb {
139        STRING *value;
140        INTVAL  size;
141        GET_ATTR_size(INTERP, SELF, size);
142
143        if (size == 0)
144            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
145                    "Can't pop from an empty array");
146
147        value = SELF.get_string_keyed_int(size - 1);
148        SELF.set_integer_native(size - 1);
149        return value;
150    }
151
152/*
153
154=item C<PMC *pop_pmc()>
155
156Removes and returns the last element in the array.
157
158=cut
159
160*/
161
162    VTABLE PMC *pop_pmc() {
163        STRING *strval = SELF.pop_string();
164        PMC    *value  = Parrot_pmc_new(INTERP, enum_class_String);
165
166        VTABLE_set_string_native(INTERP, value, strval);
167
168        return value;
169    }
170
171/*
172
173=item C<INTVAL pop_integer()>
174
175Removes and returns the last element in the array.
176
177=cut
178
179*/
180
181    VTABLE INTVAL pop_integer() :manual_wb {
182        PMC * const pmcval = SELF.pop_pmc();
183        PARROT_GC_WRITE_BARRIER(INTERP, SELF);
184        return VTABLE_get_integer(INTERP, pmcval);
185    }
186
187/*
188
189=item C<FLOATVAL pop_float()>
190
191Removes and returns the last element in the array.
192
193=cut
194
195*/
196
197    VTABLE FLOATVAL pop_float() :manual_wb {
198        PMC * const pmcval = SELF.pop_pmc();
199        PARROT_GC_WRITE_BARRIER(INTERP, SELF);
200        return VTABLE_get_number(INTERP, pmcval);
201    }
202
203/*
204
205=item C<void set_integer_native(INTVAL size)>
206
207Resizes the array to C<size> elements.
208
209=cut
210
211*/
212
213    VTABLE void set_integer_native(INTVAL new_size) :manual_wb {
214
215        STRING **str_array;
216        INTVAL   resize_threshold;
217
218        if (new_size < 0)
219            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
220                    "illegal argument");
221
222        GET_ATTR_str_array(INTERP, SELF, str_array);
223        GET_ATTR_resize_threshold(INTERP, SELF, resize_threshold);
224        if (!str_array) {
225            /* empty - used fixed routine */
226            if (new_size < 8) {
227                SUPER(8);
228                SET_ATTR_size(INTERP, SELF, new_size);
229                SET_ATTR_resize_threshold(INTERP, SELF, 8);
230            }
231            else {
232                SUPER(new_size);
233                SET_ATTR_resize_threshold(INTERP, SELF, new_size);
234            }
235        }
236        else if (new_size <= resize_threshold) {
237            /* zero out anything that was previously allocated
238             * if we're growing the array */
239            INTVAL old_size;
240            GET_ATTR_size(INTERP, SELF, old_size);
241            if (new_size > old_size) {
242                INTVAL i;
243                for (i = old_size; i < new_size; ++i)
244                    str_array[i] = NULL;
245            }
246
247            SET_ATTR_size(INTERP, SELF, new_size);
248            /* we could shrink here if necessary */
249            PARROT_GC_WRITE_BARRIER(INTERP, SELF);
250            return;
251        }
252        else {
253            INTVAL i   = resize_threshold;
254            INTVAL cur = i;
255
256            if (cur < 8192)
257                cur = (new_size < 2 * cur) ? (2 * cur) : new_size;
258            else {
259                cur = new_size + 4096;
260                cur &= ~0xfff;
261            }
262
263            SET_ATTR_str_array(INTERP, SELF,
264                    mem_gc_realloc_n_typed_zeroed(INTERP, str_array,
265                            cur, resize_threshold, STRING*));
266            GET_ATTR_str_array(INTERP, SELF, str_array);
267
268            for (; i < cur; ++i)
269                str_array[i] = NULL;
270
271            SET_ATTR_size(INTERP, SELF, new_size);
272            SET_ATTR_resize_threshold(INTERP, SELF, cur);
273        }
274        PARROT_GC_WRITE_BARRIER(INTERP, SELF);
275    }
276
277/*
278
279=item C<PMC *clone()>
280
281Creates and returns a copy of the array.
282
283=cut
284
285*/
286
287    VTABLE PMC *clone() :no_wb {
288        PMC * const copy = SUPER();
289        INTVAL size;
290        GET_ATTR_size(INTERP, SELF, size);
291        /* copy trimmed extra space */
292        SET_ATTR_resize_threshold(INTERP, copy, size);
293        return copy;
294    }
295
296/*
297
298=item C<STRING *shift_string()>
299
300Removes and returns an item from the start of the array.
301
302=cut
303
304*/
305
306    VTABLE STRING *shift_string() :manual_wb {
307        STRING *value;
308        INTVAL  size;
309        GET_ATTR_size(INTERP, SELF, size);
310
311        if (size == 0)
312            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
313                    "Can't shift from an empty array");
314
315        value = SELF.get_string_keyed_int(0);
316        SELF.delete_keyed_int(0);
317        return value;
318    }
319
320/*
321
322=item C<INTVAL shift_integer()>
323
324Removes and returns the first element in the array.
325
326=cut
327
328*/
329
330    VTABLE INTVAL shift_integer() :manual_wb {
331        PMC * const pmcval = SELF.shift_pmc();
332        PARROT_GC_WRITE_BARRIER(INTERP, SELF);
333        return VTABLE_get_integer(INTERP, pmcval);
334    }
335
336/*
337
338=item C<FLOATVAL shift_float()>
339
340Removes and returns the first element in the array.
341
342=cut
343
344*/
345
346    VTABLE FLOATVAL shift_float() :manual_wb {
347        PMC * const pmcval = SELF.shift_pmc();
348        PARROT_GC_WRITE_BARRIER(INTERP, SELF);
349        return VTABLE_get_number(INTERP, pmcval);
350    }
351
352
353/*
354
355=item C<void push_pmc(PMC *value)>
356
357Extends the array by adding an element of value C<*value> to the end of
358the array.
359
360=cut
361
362*/
363
364    VTABLE void push_pmc(PMC *value) :manual_wb {
365        STRING * const strvalue = VTABLE_get_string(INTERP, value);
366        SELF.push_string(strvalue);
367    }
368
369/*
370
371=item C<void push_integer(INTVAL value)>
372
373Extends the array by adding an element of value C<*value> to the end of
374the array.
375
376=cut
377
378*/
379
380    VTABLE void push_integer(INTVAL value) :manual_wb {
381        PMC    * const ret = Parrot_pmc_new(INTERP, enum_class_String);
382        STRING *val;
383
384        VTABLE_set_integer_native(INTERP, ret, value);
385        val = VTABLE_get_string(INTERP, ret);
386        SELF.push_string(val);
387    }
388
389/*
390
391=item C<void push_float(FLOAT value)>
392
393Extends the array by adding an element of value C<*value> to the end of
394the array.
395
396=cut
397
398*/
399
400    VTABLE void push_float(FLOATVAL value) :manual_wb {
401        PMC    * const ret = Parrot_pmc_new(INTERP, enum_class_String);
402        STRING *val;
403
404        VTABLE_set_number_native(INTERP, ret, value);
405        val = VTABLE_get_string(INTERP, ret);
406        SELF.push_string(val);
407    }
408
409/*
410
411=item C<PMC *shift_pmc()>
412
413Removes and returns a String PMC from the start of the array.
414
415=cut
416
417*/
418
419    VTABLE PMC *shift_pmc() :manual_wb {
420        UINTVAL  size;
421        PMC     *ret;
422        STRING  *value;
423        GET_ATTR_size(INTERP, SELF, size);
424
425        if (size == 0)
426            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
427                    "Can't shift from an empty array");
428
429        value = SELF.get_string_keyed_int(0);
430        ret   = Parrot_pmc_new(INTERP, enum_class_String);
431
432        VTABLE_set_string_native(INTERP, ret, value);
433        SELF.delete_keyed_int(0);
434
435        return ret;
436    }
437
438/*
439
440=item C<void unshift_string(STRING *value)>
441
442Extends the array by adding an element of value C<*value> to the start
443of the array.
444
445=cut
446
447*/
448
449    VTABLE void unshift_string(STRING *value) :manual_wb {
450        STRING  **str_array;
451        UINTVAL   size, i;
452
453        GET_ATTR_size(INTERP, SELF, size);
454        SELF.set_integer_native(size + 1);
455
456        GET_ATTR_str_array(INTERP, SELF, str_array);
457        for (i = size; i; --i)
458            str_array[i] = str_array[i - 1];
459
460        SELF.set_string_keyed_int(0, value);
461    }
462
463
464/*
465
466=item C<void unshift_pmc(PMC *value)>
467
468Extends the array by adding an element of value C<*value> to the front of
469the array.
470
471=cut
472
473*/
474
475    VTABLE void unshift_pmc(PMC *value) :manual_wb {
476        STRING * const strvalue = VTABLE_get_string(INTERP, value);
477        SELF.unshift_string(strvalue);
478    }
479
480/*
481
482=item C<void unshift_integer(INTVAL value)>
483
484Extends the array by adding an element of value C<*value> to the front of
485the array.
486
487=cut
488
489*/
490
491    VTABLE void unshift_integer(INTVAL value) :manual_wb {
492        PMC    * const ret = Parrot_pmc_new(INTERP, enum_class_String);
493        STRING *val;
494
495        VTABLE_set_integer_native(INTERP, ret, value);
496        val = VTABLE_get_string(INTERP, ret);
497        SELF.unshift_string(val);
498    }
499
500/*
501
502=item C<void unshift_float(FLOAT value)>
503
504Extends the array by adding an element of value C<*value> to the front of
505the array.
506
507=cut
508
509*/
510
511    VTABLE void unshift_float(FLOATVAL value) :manual_wb {
512        PMC    * const ret = Parrot_pmc_new(INTERP, enum_class_String);
513        STRING *val;
514
515        VTABLE_set_number_native(INTERP, ret, value);
516        val = VTABLE_get_string(INTERP, ret);
517        SELF.unshift_string(val);
518    }
519
520/*
521
522=item C<void delete_keyed_int(INTVAL key)>
523
524Converts C<key> to a PMC key and calls C<delete_keyed()> with it.
525
526=cut
527
528*/
529
530    VTABLE void delete_keyed_int(INTVAL key) :manual_wb {
531        STRING  **str_array;
532        UINTVAL   size, i;
533
534        GET_ATTR_str_array(INTERP, SELF, str_array);
535        GET_ATTR_size(INTERP, SELF, size);
536
537        for (i = key; i < size - 1; ++i)
538            str_array[i] = str_array[i + 1];
539
540        SELF.set_integer_native(size - 1);
541    }
542
543/*
544
545=item C<void delete_keyed(PMC *key)>
546
547Removes the element at C<*key>.
548
549=cut
550
551*/
552
553    VTABLE void delete_keyed(PMC *key) :manual_wb {
554        const INTVAL idx = VTABLE_get_integer(INTERP, key);
555        STRING  **str_array;
556        UINTVAL   size, i;
557
558        GET_ATTR_str_array(INTERP, SELF, str_array);
559        GET_ATTR_size(INTERP, SELF, size);
560
561        for (i = idx; i < size - 1; ++i)
562            str_array[i] = str_array[i + 1];
563
564        SELF.set_integer_native(size - 1);
565    }
566
567/*
568
569=item C<void splice(PMC *from, INTVAL offset, INTVAL count)>
570
571Replaces C<count> elements starting at C<offset> with the elements in
572C<from>.
573
574Note that the C<from> PMC can be of any of the various array types.
575
576Note that this implementation can be *VERY *inefficient as it manipulates
577everything via the VTABLE api.
578
579=cut
580
581*/
582
583    VTABLE void splice(PMC *from, INTVAL offset, INTVAL count) :manual_wb {
584
585        INTVAL length, elems, shift, i;
586
587        if (from->vtable->base_type != SELF->vtable->base_type
588         && from->vtable->base_type != enum_class_FixedStringArray)
589            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_INVALID_OPERATION,
590                    "ResizableStringArray: illegal type for splice!");
591
592        length = VTABLE_elements(INTERP, SELF);
593        elems  = VTABLE_elements(INTERP, from);
594        shift  = elems - count;
595
596        /* start from end? */
597        if (offset < 0) {
598            offset += length;
599            if (offset < 0)
600                Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
601                        "index out of bounds");
602        }
603        if (count < 0)
604            Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
605                    "illegal argument");
606
607        /* shrink the array */
608        if (shift < 0) {
609            /* start at offset so we don't overwrite values we'll need */
610            for (i = offset+count; i < length; ++i)
611                VTABLE_set_pmc_keyed_int(INTERP, SELF, i + shift,
612                    VTABLE_get_pmc_keyed_int(INTERP, SELF, i));
613
614            SELF.set_integer_native(length + shift);
615        }
616        /* grow the array */
617        else if (shift > 0) {
618            SELF.set_integer_native(length + shift);
619
620            /* move the existing values */
621            /* start at length-1 so we don't overwrite values we'll need */
622            for (i = length - 1; i >= offset; --i)
623                VTABLE_set_pmc_keyed_int(INTERP, SELF, i + shift,
624                    VTABLE_get_pmc_keyed_int(INTERP, SELF, i));
625        }
626
627        /* copy the new values */
628        for (i = 0; i < elems; ++i)
629            VTABLE_set_pmc_keyed_int(INTERP, SELF, i + offset,
630                VTABLE_get_pmc_keyed_int(INTERP, from, i));
631    }
632
633/*
634
635=item METHOD PMC* shift()
636
637=item METHOD PMC* pop()
638
639Method forms to remove and return a PMC from the beginning or
640end of the array.
641
642=cut
643
644*/
645
646    METHOD shift() :manual_wb {
647        PMC * const value = SELF.shift_pmc();
648        RETURN(PMC *value);
649    }
650
651    METHOD pop() :manual_wb {
652        PMC * const value = SELF.pop_pmc();
653        RETURN(PMC *value);
654    }
655
656/*
657
658=item METHOD unshift(PMC* value)
659
660=item METHOD push(PMC* value)
661
662Method forms to add a PMC to the beginning or end of the array.
663
664=cut
665
666*/
667
668    METHOD unshift(PMC* value) :manual_wb {
669        SELF.unshift_pmc(value);
670    }
671
672    METHOD push(PMC* value) :manual_wb {
673        SELF.push_pmc(value);
674    }
675
676}
677
678/*
679
680=back
681
682=head1 SEE ALSO
683
684F<docs/pdds/pdd17_basic_types.pod>.
685
686=cut
687
688*/
689
690/*
691 * Local variables:
692 *   c-file-style: "parrot"
693 * End:
694 * vim: expandtab shiftwidth=4 cinoptions='\:2=2' :
695 */
696