1
/* QRPA is a replacment for Parrot's ResizablePMCArray (RPA) class.
2
* The key distinguishing feature of QRPA is that it's much
3
* more efficient for shift and unshift, providing a O(1)
4
* algorithm instead of the O(n) version that RPA has.
5
* It also means that splice can be performed a lot more
6
* efficiently in many common cases. */
15
ATTR INTVAL elems; /* number of elements */
16
ATTR INTVAL start; /* slot index of first element */
17
ATTR INTVAL ssize; /* size of slots array */
18
ATTR PMC **slots; /* array of PMC slots */
21
VTABLE void destroy() {
22
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
24
mem_gc_free(INTERP, qrpa->slots);
31
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
32
INTVAL elems = qrpa->elems;
33
INTVAL start = qrpa->start;
34
PMC **slots = qrpa->slots;
37
for (elems--; elems >= 0; elems--) {
38
Parrot_gc_mark_PMC_alive(INTERP, slots[elems]);
43
VTABLE PMC * clone() {
44
PMC * const dest = Parrot_pmc_new(INTERP, SELF->vtable->base_type);
45
Parrot_QRPA_attributes * const qrpa0 = PARROT_QRPA(SELF);
46
Parrot_QRPA_attributes * const qrpa1 = PARROT_QRPA(dest);
47
INTVAL elems = qrpa0->elems;
50
qrpa1->slots = mem_gc_allocate_n_typed(INTERP, elems, PMC *);
53
mem_copy_n_typed(qrpa1->slots, qrpa0->slots + qrpa0->start,
55
PObj_custom_mark_destroy_SETALL(dest);
64
=item C<void set_integer_native(INTVAL n)>
66
Resizes the array to C<n> elements.
72
VTABLE void set_integer_native(INTVAL n) {
73
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
74
INTVAL elems = qrpa->elems;
75
INTVAL start = qrpa->start;
76
INTVAL ssize = qrpa->ssize;
77
PMC **slots = qrpa->slots;
80
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
81
"QRPA: Can't resize to negative elements");
83
if (n == elems) { return; }
85
/* if there aren't enough slots at the end, shift off empty slots
86
* from the beginning first */
87
if (start > 0 && n + start > ssize) {
89
memmove(slots, slots + start, elems * sizeof (PMC *));
91
/* fill out any unused slots with PMCNULL pointers */
92
while (elems < ssize) {
93
slots[elems] = PMCNULL;
100
/* we already have n slots available, we can just return */
104
/* We need more slots. If the current slot size is less
105
* than 8K, use the larger of twice the current slot size
106
* or the actual number of elements needed. Otherwise,
107
* grow the slots to the next multiple of 4096 (0x1000). */
110
if (n > ssize) ssize = n;
111
if (ssize < 8) ssize = 8;
114
ssize = (n + 0x1000) & ~0xfff;
117
/* now allocate the new slot buffer */
119
? mem_gc_realloc_n_typed(INTERP, slots, ssize, PMC *)
120
: mem_gc_allocate_n_typed(INTERP, ssize, PMC *);
122
/* fill out any unused slots with PMCNULL pointers */
123
while (elems < ssize) {
124
slots[elems] = PMCNULL;
130
PObj_custom_mark_destroy_SETALL(SELF);
134
VTABLE INTVAL defined_keyed_int(INTVAL pos) {
135
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
141
if (pos < 0 || pos >= qrpa->elems)
144
value = qrpa->slots[qrpa->start + pos];
145
return !PMC_IS_NULL(value) && VTABLE_defined(INTERP, value);
149
VTABLE INTVAL elements() {
150
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
156
VTABLE INTVAL exists_keyed_int(INTVAL pos) {
157
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
164
if (pos < 0 || pos >= qrpa->elems)
167
return !PMC_IS_NULL(qrpa->slots[qrpa->start + pos]);
171
VTABLE INTVAL exists_keyed(PMC *key) {
172
INTVAL pos = VTABLE_get_integer(INTERP, key);
173
return SELF.exists_keyed_int(pos);
177
VTABLE INTVAL get_bool() {
178
const INTVAL elems = SELF.elements();
179
return (INTVAL)(elems != 0);
183
VTABLE INTVAL get_integer() {
184
return SELF.elements();
188
VTABLE PMC * get_iter() {
189
return Parrot_pmc_new_init(INTERP, enum_class_ArrayIterator, SELF);
193
VTABLE FLOATVAL get_number() {
194
const INTVAL e = SELF.elements();
199
VTABLE PMC * get_pmc_keyed_int(INTVAL pos) {
200
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
205
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
206
"QRPA: index out of bounds");
208
else if (pos >= qrpa->elems)
211
return qrpa->slots[qrpa->start + pos];
215
VTABLE PMC *get_pmc_keyed(PMC *key) {
216
const INTVAL pos = VTABLE_get_integer(INTERP, key);
217
PMC * const nextkey = Parrot_key_next(INTERP, key);
221
return SELF.get_pmc_keyed_int(pos);
223
box = SELF.get_pmc_keyed_int(pos);
224
if (PMC_IS_NULL(box))
227
return VTABLE_get_pmc_keyed(INTERP, box, nextkey);
231
VTABLE void set_pmc_keyed_int(INTVAL pos, PMC *value) {
232
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
237
Parrot_ex_throw_from_c_args(INTERP, NULL,
238
EXCEPTION_OUT_OF_BOUNDS, "QRPA: index out of bounds");
240
else if (pos >= qrpa->elems)
241
SELF.set_integer_native(pos + 1);
243
qrpa->slots[qrpa->start + pos] = value;
247
VTABLE void set_pmc_keyed(PMC *key, PMC *value) {
248
const INTVAL pos = VTABLE_get_integer(INTERP, key);
249
PMC * const nextkey = Parrot_key_next(INTERP, key);
252
SELF.set_pmc_keyed_int(pos, value);
255
PMC * const box = SELF.get_pmc_keyed_int(pos);
256
if (PMC_IS_NULL(box)) {
257
Parrot_ex_throw_from_c_args(interp, NULL,
258
EXCEPTION_INVALID_OPERATION,
259
"Cannot autovivify nested arrays");
261
VTABLE_set_pmc_keyed(INTERP, box, nextkey, value);
266
VTABLE PMC * pop_pmc() {
267
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
269
if (qrpa->elems < 1) {
270
Parrot_ex_throw_from_c_args(interp, NULL, EXCEPTION_OUT_OF_BOUNDS,
271
"QRPA: Can't pop from an empty array!");
275
return qrpa->slots[qrpa->start + qrpa->elems];
279
VTABLE void push_pmc(PMC *value) {
280
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
282
SELF.set_integer_native(qrpa->elems + 1);
283
qrpa->slots[qrpa->start + qrpa->elems - 1] = value;
287
VTABLE PMC * shift_pmc() {
288
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
291
if (qrpa->elems < 1) {
292
Parrot_ex_throw_from_c_args(interp, NULL, EXCEPTION_OUT_OF_BOUNDS,
293
"QRPA: Can't shift from an empty array!");
296
value = qrpa->slots[qrpa->start];
303
VTABLE void unshift_pmc(PMC *value) {
304
Parrot_QRPA_attributes * const qrpa = PARROT_QRPA(SELF);
306
/* If we don't have room at the beginning of the slots,
307
* make some room (8 slots) for unshifting */
308
if (qrpa->start < 1) {
310
INTVAL elems = qrpa->elems;
314
SELF.set_integer_native(elems + n);
315
/* move elements and set start */
316
memmove(qrpa->slots + n, qrpa->slots, elems * sizeof (PMC *));
319
/* clear out beginning elements */
320
for (i = 0; i < n; i++)
321
qrpa->slots[i] = PMCNULL;
324
/* Now do the unshift */
326
qrpa->slots[qrpa->start] = value;
330
VTABLE void splice(PMC *from, INTVAL offset, INTVAL count) {
331
/* TODO: use qrpa->foo instead of GET_ATTR_* */
332
INTVAL elems0 = VTABLE_elements(INTERP, SELF);
333
INTVAL elems1 = VTABLE_elements(INTERP, from);
338
/* start from end? */
343
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
344
"QRPA: illegal splice offset\n");
346
/* When offset == 0, then we may be able to reduce the memmove
347
* calls and reallocs by adjusting SELF's start, elems0, and
348
* count to better match the incoming splice. In particular,
349
* we're seeking to adjust C<count> to as close to C<elems1>
352
INTVAL n = elems1 - count;
353
GET_ATTR_start(INTERP, SELF, start);
354
if (n > start) n = start;
358
SET_ATTR_start(INTERP, SELF, 0);
359
SET_ATTR_elems(INTERP, SELF, elems0);
364
SET_ATTR_start(INTERP, SELF, start - n);
365
SET_ATTR_elems(INTERP, SELF, elems0);
369
/* if count == 0 and elems1 == 0, there's nothing left
370
* to copy or remove, so the splice is done! */
371
if (count == 0 && elems1 == 0)
374
/* number of elements to right of splice (the "tail") */
375
tail = elems0 - offset - count;
376
if (tail < 0) tail = 0;
378
if (tail > 0 && count > elems1) {
379
/* We're shrinking the array, so first move the tail left */
380
GET_ATTR_slots(INTERP, SELF, slots);
381
GET_ATTR_start(INTERP, SELF, start);
382
memmove(slots + start + offset + elems1,
383
slots + start + offset + count,
384
tail * sizeof (PMC *));
387
/* now resize the array */
388
SELF.set_integer_native(offset + elems1 + tail);
390
GET_ATTR_slots(INTERP, SELF, slots);
391
GET_ATTR_start(INTERP, SELF, start);
392
if (tail > 0 && count < elems1) {
393
/* The array grew, so move the tail to the right */
394
memmove(slots + start + offset + elems1,
395
slots + start + offset + count,
396
tail * sizeof (PMC *));
399
/* now copy C<from>'s elements into SELF */
401
PMC *iter = VTABLE_get_iter(INTERP, from);
403
for (i = 0; i < elems1; i++)
404
slots[start + offset + i] = VTABLE_shift_pmc(INTERP, iter);
409
VTABLE INTVAL get_integer_keyed(PMC *key) {
410
PMC * const val = SELF.get_pmc_keyed(key);
411
return VTABLE_get_integer(INTERP, val);
415
VTABLE void set_integer_keyed(PMC *key, INTVAL value) {
416
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Integer));
417
VTABLE_set_integer_native(INTERP, val, value);
418
SELF.set_pmc_keyed(key, val);
422
VTABLE void set_integer_keyed_int(INTVAL pos, INTVAL value) {
423
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Integer));
424
VTABLE_set_integer_native(INTERP, val, value);
425
SELF.set_pmc_keyed_int(pos, val);
429
VTABLE INTVAL pop_integer() {
430
PMC * const val = SELF.pop_pmc();
431
return VTABLE_get_integer(INTERP, val);
435
VTABLE void push_integer(INTVAL value) {
437
GET_ATTR_elems(INTERP, SELF, elems);
438
SELF.set_integer_keyed_int(elems, value);
442
VTABLE INTVAL shift_integer() {
443
PMC * const val = SELF.shift_pmc();
444
return VTABLE_get_integer(INTERP, val);
447
VTABLE void unshift_integer(INTVAL value) {
448
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Integer));
449
VTABLE_set_integer_native(INTERP, val, value);
450
SELF.unshift_pmc(val);
455
VTABLE FLOATVAL get_number_keyed(PMC *key) {
456
PMC * const val = SELF.get_pmc_keyed(key);
457
return VTABLE_get_number(INTERP, val);
461
VTABLE void set_number_keyed(PMC *key, FLOATVAL value) {
462
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Float));
463
VTABLE_set_number_native(INTERP, val, value);
464
SELF.set_pmc_keyed(key, val);
468
VTABLE void set_number_keyed_int(INTVAL pos, FLOATVAL value) {
469
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Float));
470
VTABLE_set_number_native(INTERP, val, value);
471
SELF.set_pmc_keyed_int(pos, val);
475
VTABLE FLOATVAL pop_float() {
476
PMC * const val = SELF.pop_pmc();
477
return VTABLE_get_number(INTERP, val);
481
VTABLE void push_float(FLOATVAL value) {
483
GET_ATTR_elems(INTERP, SELF, elems);
484
SELF.set_number_keyed_int(elems, value);
488
VTABLE FLOATVAL shift_float() {
489
PMC * const val = SELF.shift_pmc();
490
return VTABLE_get_number(INTERP, val);
494
VTABLE void unshift_float(FLOATVAL value) {
495
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_Float));
496
VTABLE_set_number_native(INTERP, val, value);
497
SELF.unshift_pmc(val);
501
VTABLE STRING * get_string_keyed(PMC *key) {
502
PMC * const val = SELF.get_pmc_keyed(key);
503
return VTABLE_get_string(INTERP, val);
507
VTABLE void set_string_keyed(PMC *key, STRING *value) {
508
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_String));
509
VTABLE_set_string_native(INTERP, val, value);
510
SELF.set_pmc_keyed(key, val);
514
VTABLE void set_string_keyed_int(INTVAL key, STRING *value) {
515
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_String));
516
VTABLE_set_string_native(INTERP, val, value);
517
SELF.set_pmc_keyed_int(key, val);
521
VTABLE STRING * pop_string() {
522
PMC * const val = SELF.pop_pmc();
523
return VTABLE_get_string(INTERP, val);
527
VTABLE void push_string(STRING *value) {
529
GET_ATTR_elems(INTERP, SELF, elems);
530
SELF.set_string_keyed_int(elems, value);
534
VTABLE STRING * shift_string() {
535
PMC * const val = SELF.shift_pmc();
536
return VTABLE_get_string(INTERP, val);
540
VTABLE void unshift_string(STRING *value) {
541
PMC * const val = Parrot_pmc_new(INTERP, Parrot_hll_get_ctx_HLL_type(INTERP, enum_class_String));
542
VTABLE_set_string_native(INTERP, val, value);
543
SELF.unshift_pmc(val);
added
removed
src/pmc/qrpa.pmc
