Skip to content
Find file
Fetching contributors…
Cannot retrieve contributors at this time
616 lines (414 sloc) 11.3 KB
/*
Copyright (C) 2010-2014, Parrot Foundation.
=head1 NAME
src/pmc/pmclist.pmc - PMCList PMC
=head1 DESCRIPTION
A doubly linked list of PMCs, for when push, pop, shift, and unshift
all want to be O(1).
=head2 Vtable Functions
=over 4
=cut
*/
BEGIN_PMC_HEADER_PREAMBLE
PARROT_EXPORT
void
Parrot_pmc_list_insert_by_number(PARROT_INTERP, PMC *list, PMC *value);
END_PMC_HEADER_PREAMBLE
/* HEADERIZER HFILE: none */
/* HEADERIZER BEGIN: static */
/* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
PARROT_DOES_NOT_RETURN
static void throw_pop_empty(PARROT_INTERP)
__attribute__nonnull__(1);
PARROT_DOES_NOT_RETURN
static void throw_shift_empty(PARROT_INTERP)
__attribute__nonnull__(1);
#define ASSERT_ARGS_throw_pop_empty __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp))
#define ASSERT_ARGS_throw_shift_empty __attribute__unused__ int _ASSERT_ARGS_CHECK = (\
PARROT_ASSERT_ARG(interp))
/* Don't modify between HEADERIZER BEGIN / HEADERIZER END. Your changes will be lost. */
/* HEADERIZER END: static */
/* It's a doubly linked list */
typedef struct PMC_List_Item {
PMC *data;
struct PMC_List_Item *prev;
struct PMC_List_Item *next;
} PMC_List_Item;
pmclass PMCList auto_attrs {
ATTR void *head;
ATTR void *foot;
ATTR INTVAL size;
/*
=item C<void init()>
Initializes the list.
=cut
*/
VTABLE void init() {
PObj_custom_mark_SET(SELF);
PObj_custom_destroy_SET(SELF);
SET_ATTR_head(INTERP, SELF, NULL);
SET_ATTR_foot(INTERP, SELF, NULL);
SET_ATTR_size(INTERP, SELF, 0);
}
/*
=item C<void destroy()>
Free all the list cells.
=cut
*/
VTABLE void destroy() :no_wb {
void *tmp;
PMC_List_Item *aa;
GET_ATTR_head(INTERP, SELF, tmp);
aa = (PMC_List_Item*) tmp;
while (aa != NULL) {
PMC_List_Item * const bb = aa;
aa = aa->next;
free(bb);
}
}
/*
=item C<INTVAL get_integer()>
Returns the size of the list.
=cut
*/
VTABLE INTVAL get_integer() :no_wb {
INTVAL size;
GET_ATTR_size(INTERP, SELF, size);
return size;
}
VTABLE INTVAL elements() :no_wb {
INTVAL size;
GET_ATTR_size(INTERP, SELF, size);
return size;
}
/*
=item C<PMC *shift_pmc()>
Removes and returns an item from the start of the array.
=cut
*/
VTABLE PMC *shift_pmc() {
INTVAL size;
void *tmp;
PMC_List_Item *head;
PMC_List_Item *item;
PMC *data;
GET_ATTR_size(INTERP, SELF, size);
if (0 >= size)
throw_shift_empty(INTERP);
GET_ATTR_head(INTERP, SELF, tmp);
item = (PMC_List_Item*) tmp;
data = item->data;
size -= 1;
SET_ATTR_size(INTERP, SELF, size);
head = item->next;
SET_ATTR_head(INTERP, SELF, head);
if (head == NULL) {
/* size == 0 */
SET_ATTR_foot(INTERP, SELF, NULL);
}
else {
head->prev = NULL;
}
if (size == 1) {
head->next = NULL;
SET_ATTR_foot(INTERP, SELF, head);
}
free(item);
return data;
}
/*
=item C<void push_pmc(PMC *value)>
Extends the array by adding an element of value C<*value> to the end of
the array.
=cut
*/
VTABLE void push_pmc(PMC *value) {
INTVAL size;
void *tmp;
PMC_List_Item *foot;
PMC_List_Item *item;
GET_ATTR_size(INTERP, SELF, size);
GET_ATTR_foot(INTERP, SELF, tmp);
foot = (PMC_List_Item*) tmp;
item = (PMC_List_Item*) malloc(sizeof (PMC_List_Item));
item->next = NULL;
item->prev = foot;
item->data = value;
if (foot)
foot->next = item;
size += 1;
SET_ATTR_foot(INTERP, SELF, item);
SET_ATTR_size(INTERP, SELF, size);
if (size == 1)
SET_ATTR_head(INTERP, SELF, item);
return;
}
/*
=item C<PMC *pop_pmc()>
Removes and returns the last element in the array.
=cut
*/
VTABLE PMC *pop_pmc() {
INTVAL size;
void *tmp;
PMC_List_Item *foot;
PMC_List_Item *item;
PMC *data;
GET_ATTR_size(INTERP, SELF, size);
if (0 >= size)
throw_pop_empty(INTERP);
GET_ATTR_foot(INTERP, SELF, tmp);
item = (PMC_List_Item*) tmp;
data = item->data;
size -= 1;
SET_ATTR_size(INTERP, SELF, size);
foot = item->prev;
SET_ATTR_foot(INTERP, SELF, foot);
if (foot == NULL) {
/* size == 0 */
SET_ATTR_head(INTERP, SELF, NULL);
}
else {
foot->next = NULL;
}
if (size == 1) {
foot->prev = NULL;
SET_ATTR_head(INTERP, SELF, foot);
}
free(item);
return data;
}
/*
=item C<void unshift_pmc(PMC *value)>
Extends the array by adding an element of value C<*value> to the begin of
the array.
=cut
*/
VTABLE void unshift_pmc(PMC *value) {
INTVAL size;
void *tmp;
PMC_List_Item *head;
PMC_List_Item *item;
GET_ATTR_size(INTERP, SELF, size);
GET_ATTR_head(INTERP, SELF, tmp);
head = (PMC_List_Item*) tmp;
item = (PMC_List_Item*) malloc(sizeof (PMC_List_Item));
item->prev = NULL;
item->next = head;
item->data = value;
if (head)
head->prev = item;
size += 1;
SET_ATTR_head(INTERP, SELF, item);
SET_ATTR_size(INTERP, SELF, size);
if (size == 1)
SET_ATTR_foot(INTERP, SELF, item);
return;
}
/*
=item C<PMC *clone()>
Creates and returns a copy of the list.
=cut
*/
VTABLE PMC *clone() :no_wb {
PMC * const copy = Parrot_pmc_new(INTERP, SELF->vtable->base_type);
void* tmp;
PMC_List_Item *it;
GET_ATTR_head(INTERP, SELF, tmp);
it = (PMC_List_Item*) tmp;
while (it != NULL) {
VTABLE_push_pmc(INTERP, copy, it->data);
it = it->next;
}
return copy;
}
/*
=item C<STRING *get_repr()>
=item C<STRING *get_string()>
Returns the Parrot string representation C<ResizablePMCArray>.
=cut
*/
VTABLE STRING *get_repr() :no_wb {
PMC_List_Item *it;
void* tmp;
STRING *res = CONST_STRING(INTERP, "[ ");
STRING * const space = CONST_STRING(INTERP, " ");
GET_ATTR_head(INTERP, SELF, tmp);
it = (PMC_List_Item*) tmp;
while (it != NULL) {
res = Parrot_str_concat(INTERP, res, VTABLE_get_repr(INTERP, it->data));
res = Parrot_str_concat(INTERP, res, space);
it = it->next;
}
return Parrot_str_concat(INTERP, res, CONST_STRING(INTERP, "]"));
}
VTABLE STRING *get_string() :no_wb {
return VTABLE_get_repr(INTERP, SELF);
}
/*
=item C<void visit(PMC *info)>
This is used by freeze/thaw to visit the contents of the array.
C<*info> is the visit info, (see F<include/parrot/pmc_freeze.h>).
=item C<void freeze(PMC *info)>
Used to archive the array.
=item C<void thaw(PMC *info)>
Used to unarchive the array.
=cut
*/
VTABLE void visit(PMC *info) :no_wb {
void* tmp;
PMC_List_Item *it;
GET_ATTR_head(INTERP, SELF, tmp);
it = (PMC_List_Item*) tmp;
while (it != NULL) {
VISIT_PMC(INTERP, info, it->data);
it = it->next;
}
SUPER(info);
}
VTABLE void freeze(PMC *info) :no_wb {
SUPER(info);
VTABLE_push_integer(INTERP, info, VTABLE_get_integer(INTERP, SELF));
}
VTABLE void thaw(PMC *info) :manual_wb {
int n, i;
SUPER(info);
n = VTABLE_shift_integer(INTERP, info);
SET_ATTR_size(INTERP, SELF, n);
for (i = 0; i < n; ++i)
VTABLE_push_pmc(INTERP, SELF, PMCNULL);
}
/*
=item C<void mark()>
Mark the stuff.
=cut
*/
VTABLE void mark() :no_wb {
void* tmp;
PMC_List_Item *it;
GET_ATTR_head(INTERP, SELF, tmp);
it = (PMC_List_Item*) tmp;
while (it != NULL) {
if (!PObj_is_PMC_TEST(it->data))
PANIC(INTERP, "PMCList: Pointer is not a valid PMC");
Parrot_gc_mark_PMC_alive(INTERP, it->data);
it = it->next;
}
}
/*
=item METHOD PMC* shift()
=item METHOD PMC* pop()
Method forms to remove and return a PMC from the beginning or
end of the array.
=cut
*/
METHOD shift() :manual_wb {
PMC * const value = VTABLE_shift_pmc(INTERP, SELF);
RETURN(PMC *value);
}
METHOD pop() :manual_wb {
PMC * const value = VTABLE_pop_pmc(INTERP, SELF);
RETURN(PMC *value);
}
/*
=item METHOD unshift(PMC* value)
=item METHOD push(PMC* value)
Method forms to add a PMC to the beginning or end of the array.
=cut
*/
METHOD unshift(PMC* value) :manual_wb {
VTABLE_unshift_pmc(INTERP, SELF, value);
}
METHOD push(PMC* value) :manual_wb {
VTABLE_push_pmc(INTERP, SELF, value);
}
/*
=item METHOD insert_by_number(PMC* value)
Inserts an item into an ordered list by it's number value.
=cut
*/
METHOD insert_by_number(PMC* value) {
Parrot_pmc_list_insert_by_number(INTERP, SELF, value);
}
}
/*
=back
=head2 Auxiliary functions
=over 4
=item C<void Parrot_pmc_list_insert_by_number(PARROT_INTERP, PMC *list, PMC
*value)>
Insert an item into a sorted list by its num value.
=cut
*/
PARROT_EXPORT
void
Parrot_pmc_list_insert_by_number(PARROT_INTERP, PMC *list, PMC *value)
{
void *tmp;
PMC_List_Item *item;
FLOATVAL vkey;
int size;
GETATTR_PMCList_size(interp, list, size);
GETATTR_PMCList_head(interp, list, tmp);
item = (PMC_List_Item*) malloc(sizeof (PMC_List_Item));
item->data = value;
item->next = (PMC_List_Item*) tmp;
item->prev = NULL;
vkey = VTABLE_get_number(interp, value);
/* Find the list item to insert before */
while (item->next != NULL) {
const FLOATVAL ikey = VTABLE_get_number(interp, item->next->data);
if (ikey > vkey)
break;
item->prev = item->next;
item->next = item->next->next;
}
if (item->next == NULL) {
SETATTR_PMCList_foot(interp, list, item);
}
else {
item->next->prev = item;
}
if (item->prev == NULL) {
SETATTR_PMCList_head(interp, list, item);
}
else {
item->prev->next = item;
}
SETATTR_PMCList_size(interp, list, size + 1);
}
/*
=item C<static void throw_shift_empty(PARROT_INTERP)>
=item C<static void throw_pop_empty(PARROT_INTERP)>
Throws with the appropriate message.
=cut
*/
PARROT_DOES_NOT_RETURN
static void
throw_shift_empty(PARROT_INTERP)
{
ASSERT_ARGS(throw_shift_empty)
Parrot_ex_throw_from_c_noargs(interp, EXCEPTION_OUT_OF_BOUNDS,
"Can't shift from an empty list");
}
PARROT_DOES_NOT_RETURN
static void
throw_pop_empty(PARROT_INTERP)
{
ASSERT_ARGS(throw_pop_empty)
Parrot_ex_throw_from_c_noargs(interp, EXCEPTION_OUT_OF_BOUNDS,
"Can't pop from an empty list");
}
/*
=back
=head1 See also
F<docs/pdds/pdd17_basic_types.pod>.
=cut
*/
/*
* Local variables:
* c-file-style: "parrot"
* End:
* vim: expandtab shiftwidth=4 cinoptions='\:2=2' :
*/
Something went wrong with that request. Please try again.