Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
202 lines (183 sloc) 6.13 KB
#include "parrot/parrot.h"
#define RPS_POINTERS_PER_CHUNK 16
#define RPS_ATTRS_CONST(x) Parrot_ResizablePMCStack_attributes * const (x)
#define RPS_GET_ATTRS(x) PARROT_RESIZABLEPMCSTACK(x)
#define RPS_ALLOC_CHUNK() (PMC **)mem_sys_allocate((len) * sizeof(PMC *))
#define RPS_GET_ROOT(a) ((rps_chunk *)(a)->root_chunk)
#define RPS_GET_TOP(a) ((rps_chunk *)(a)->top_chunk)
typedef struct _rps_chunk {
struct _rps_chunk * prev;
struct _rps_chunk * next;
INTVAL items;
PMC * storage[RPS_POINTERS_PER_CHUNK];
} rps_chunk;
static
rps_chunk *
rps_new_chunk(rps_chunk *prev)
{
rps_chunk * const newchunk = (rps_chunk *)mem_sys_allocate(sizeof(rps_chunk));
newchunk->prev = prev;
newchunk->next = NULL;
newchunk->items = 0;
return newchunk;
}
static
void
rps_free_chunk(rps_chunk *chunk)
{
mem_sys_free(chunk);
}
/* ResizablePMCStack is a dynamically-growing First-In-Last-Out stack structure.
It is optimized for high-throughput push/pop access. */
pmclass ResizablePMCStack dynpmc auto_attrs provides stack {
ATTR void *root_chunk;
ATTR void *top_chunk;
ATTR INTVAL items;
ATTR INTVAL numchunks;
/* Initialize the PMC and allocate the first chunk */
VTABLE void init() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk * const newchunk = rps_new_chunk(NULL);
attrs->root_chunk = newchunk;
attrs->top_chunk = newchunk;
PObj_custom_mark_destroy_SETALL(SELF);
}
/* Destroy the PMC and free all allocated storage */
VTABLE void destroy() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
while (ptr) {
rps_chunk * const next = ptr->next;
mem_sys_free(ptr);
ptr = next;
}
}
/* Mark the stack for GC */
VTABLE void mark() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
while (ptr) {
const INTVAL items = ptr->items;
INTVAL i;
PMC ** const s = ptr->storage;
for (i = 0; i < items; i++)
Parrot_gc_mark_PMC_alive(INTERP, s[i]);
ptr = ptr->next;
}
}
VTABLE void freeze(PMC *info) {
}
VTABLE void thaw(PMC *info) {
}
VTABLE void visit(PMC *info) {
}
/* Push a PMC onto the stack */
VTABLE void push_pmc(PMC *item) {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk * current = RPS_GET_TOP(attrs);
INTVAL idx;
if (current->items == RPS_POINTERS_PER_CHUNK) {
rps_chunk * const newchunk = rps_new_chunk(current);
current->next = newchunk;
attrs->top_chunk = newchunk;
current = newchunk;
}
idx = current->items;
current->storage[idx] = item;
idx++;
current->items = idx;
}
/* Pop a PMC off the stack */
VTABLE PMC* pop_pmc() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *current = RPS_GET_TOP(attrs);
INTVAL idx = current->items;
if (idx == 0)
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
"ResizablePMCStack: Pop from empty stack");
idx--;
{
PMC * const item = current->storage[idx];
rps_chunk * const last = current->prev;
/* Popped the last item off this chunk. */
if (idx == 0) {
/* We have another chunk. Pop off the current chunk and move
to the last one */
if(last != NULL) {
last->next = NULL;
rps_free_chunk(current);
current = last;
attrs->top_chunk = current;
PARROT_ASSERT(current->items == RPS_POINTERS_PER_CHUNK);
}
/* We're on the first chunk. The stack is now empty */
else
current->items = 0;
}
else
current->items = idx;
return item;
}
}
/* Get the total number of elements. WARNING: O(N) */
VTABLE INTVAL elements() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
INTVAL total = 0;
while (ptr) {
const INTVAL items = ptr->items;
total += items;
ptr = ptr->next;
}
return total;
}
VTABLE INTVAL get_bool() {
const INTVAL count = VTABLE_elements(INTERP, SELF);
const INTVAL elements = count > 0;
return(elements);
}
/* Get a ResizablePMCArray containing the contents of the stack */
METHOD to_array() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
PMC *newarray = Parrot_pmc_new(INTERP, enum_class_ResizablePMCArray);
INTVAL i = 0;
while (ptr) {
PMC ** const s = ptr->storage;
INTVAL items = ptr->items;
INTVAL j = 0;
for (j = 0; j < items; j++) {
VTABLE_set_pmc_keyed_int(INTERP, newarray, i, s[j]);
i++;
}
ptr = ptr->next;
}
RETURN(PMC *newarray);
}
/* Get the total allocated memory size, in bytes. Includes the size of the
PMC structure and attribute structure */
METHOD total_mem_size() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
INTVAL size = sizeof(PMC) + sizeof(Parrot_ResizablePMCStack_attributes);
while (ptr) {
size += sizeof(rps_chunk);
ptr = ptr->next;
}
RETURN(INTVAL size);
}
METHOD clear() {
RPS_ATTRS_CONST(attrs) = RPS_GET_ATTRS(SELF);
rps_chunk *ptr = RPS_GET_ROOT(attrs);
rps_chunk * const newchunk = rps_new_chunk(NULL);
while (ptr) {
rps_chunk * const next = ptr->next;
mem_sys_free(ptr);
ptr = next;
}
attrs->root_chunk = newchunk;
attrs->top_chunk = newchunk;
attrs->items = 0;
attrs->numchunks = 0;
}
}