Permalink
Switch branches/tags
Find file
Fetching contributors…
Cannot retrieve contributors at this time
491 lines (339 sloc) 13.5 KB
/*
Copyright (C) 2001-2014, Parrot Foundation.
=head1 NAME
src/pmc/resizablebooleanarray.pmc - ResizableBooleanArray PMC
=head1 DESCRIPTION
The C<ResizableBooleanArray PMC> implements an array of resizable size, which
stores booleans. It uses the C<Boolean PMC> for all conversions. The
C<ResizableBooleanArray PMC> extends the C<FixedBooleanArray PMC>.
=head2 Functions
=over 4
=cut
*/
#define BITS_PER_CHAR 8
/* MIN_ALLOC is 8 * BITS_PER_CHAR */
#define MIN_ALLOC 64
/* Round a given size in bits to the nearest allocation unit, then convert it
* to bytes. */
#define ROUND_BYTES(size) (((size) / MIN_ALLOC + 1) * MIN_ALLOC / BITS_PER_CHAR)
/* Convert a size in bits to a size in bytes */
#define BITS_TO_BYTES(size) ((size) / BITS_PER_CHAR)
/* HEADERIZER HFILE: none */
/* HEADERIZER BEGIN: static */
/* HEADERIZER END: static */
pmclass ResizableBooleanArray extends FixedBooleanArray auto_attrs provides array {
/* RBA uses the same attributes as FBA, but in RBA they're used as follows:
size: position of the last element (a.k.a tail_pos)
resize_threshold: position of the first element (a.k.a. head_pos) */
/*
=back
=head2 Methods
=over 4
=item C<INTVAL get_integer_keyed_int(INTVAL key)>
Returns the integer value of the element at index C<key>.
=cut
*/
VTABLE INTVAL get_integer_keyed_int(INTVAL key) :no_wb {
UINTVAL offsetkey, tail_pos, head_pos;
GET_ATTR_size(INTERP, SELF, tail_pos);
/* Try to make negative index into a real index */
if (key < 0) {
key += tail_pos;
/* If it's still negative, we have a problem */
if (key < 0)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
"index out of bounds");
}
/* Check if key is greater than allocated size */
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
offsetkey = key + head_pos;
if (offsetkey >= tail_pos)
return 0;
return SUPER(offsetkey);
}
/*
=item C<void set_integer_keyed_int(INTVAL key, INTVAL value)>
Sets the integer value of the element at index C<key> to C<value>.
=cut
*/
VTABLE void set_integer_keyed_int(INTVAL key, INTVAL value) :manual_wb {
UINTVAL offsetkey, tail_pos, head_pos;
GET_ATTR_size(INTERP, SELF, tail_pos);
/* Try to make negative index into a real index */
if (key < 0) {
key += tail_pos;
/* If it's still negative, we have a problem */
if (key < 0)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
"index out of bounds");
}
/* Check if key is greater than allocated size */
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
offsetkey = key + head_pos;
if (offsetkey >= tail_pos)
SELF.set_integer_native(key+1);
SUPER(offsetkey, value);
}
/*
=item C<void set_integer_native(INTVAL size)>
Resizes the array to C<size> elements.
=cut
*/
VTABLE void set_integer_native(INTVAL size) {
unsigned char * bit_array;
size_t old_tail_pos, new_tail_pos, new_size_in_bytes, old_size_in_bytes;
/* Size respects any existing head position offset from unshift */
GET_ATTR_resize_threshold(INTERP, SELF, new_tail_pos);
GET_ATTR_size(INTERP, SELF, old_tail_pos);
new_tail_pos += size;
/* We are already at the requested size. Yay */
if (new_tail_pos == old_tail_pos)
return;
if (size < 0)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
"illegal argument");
/* now set the new size, in bits */
SET_ATTR_size(INTERP, SELF, new_tail_pos);
/* convert sizes to bytes */
new_size_in_bytes = ROUND_BYTES(new_tail_pos);
old_size_in_bytes = ROUND_BYTES(old_tail_pos);
/* Nothing allocated yet */
GET_ATTR_bit_array(INTERP, SELF, bit_array);
if (!bit_array) {
void * const new_bit_array = Parrot_gc_allocate_memory_chunk(INTERP, new_size_in_bytes);
memset(new_bit_array, 0, new_size_in_bytes);
SET_ATTR_bit_array(INTERP, SELF, (unsigned char *)new_bit_array);
/* The size is different, and doesn't fit within the current
* allocation */
}
else if (new_size_in_bytes != old_size_in_bytes) {
unsigned char * old_store = bit_array;
unsigned char * new_store =
(unsigned char *)Parrot_gc_allocate_memory_chunk(INTERP, new_tail_pos);
size_t copy_size =
new_size_in_bytes < old_size_in_bytes ? new_size_in_bytes : old_size_in_bytes;
memset(new_store, 0, new_tail_pos);
/* Replace old array with new array, and free old array */
SET_ATTR_bit_array(INTERP, SELF,
(unsigned char *)memmove(
new_store, old_store, copy_size));
mem_gc_free(INTERP, old_store);
}
}
/*
=item C<void push_integer(INTVAL value)>
Extends the array by adding an element of value C<value> to the end.
=cut
*/
VTABLE void push_integer(INTVAL value) :manual_wb {
UINTVAL tail_pos, head_pos;
INTVAL new_size;
GET_ATTR_size(INTERP, SELF, tail_pos);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
new_size = tail_pos - head_pos;
SELF.set_integer_native(new_size + 1);
SELF.set_integer_keyed_int(new_size, value);
}
/*
=item C<void pop_integer(INTVAL value)>
Removes and returns the last element.
=cut
*/
VTABLE INTVAL pop_integer() :manual_wb {
UINTVAL new_size, tail_pos, head_pos;
INTVAL value;
GET_ATTR_size(INTERP, SELF, tail_pos);
if (tail_pos < 1)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
"Can't pop from an empty array");
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
new_size = tail_pos - head_pos;
value = SELF.get_integer_keyed_int(new_size - 1);
SELF.set_integer_native(new_size - 1);
return value;
}
/*
=item C<void unshift_integer(INTVAL value)>
Extends the array by adding an element of value C<value> to the
beginning.
=cut
*/
VTABLE void unshift_integer(INTVAL value) :manual_wb {
UINTVAL head_pos;
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
/* If the current head position offset is 0, size this thing up by one
* allocation unit */
if (head_pos <= 0) {
UINTVAL tail_pos;
unsigned char * old_bit_array;
size_t old_mem_size, new_mem_size;
unsigned char * new_bit_array;
GET_ATTR_size(INTERP, SELF, tail_pos);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
GET_ATTR_bit_array(INTERP, SELF, old_bit_array);
/* Allocate an extra allocation unit of space in new array */
new_mem_size = ROUND_BYTES(tail_pos+ MIN_ALLOC);
new_bit_array = (unsigned char *)Parrot_gc_allocate_memory_chunk(INTERP, new_mem_size);
memset(new_bit_array, 0, new_mem_size);
/* Copy contents of old array to new array, moving the head
* position forward by one allocation unit (in bytes). */
old_mem_size = ROUND_BYTES(tail_pos);
memmove(new_bit_array + (BITS_TO_BYTES(MIN_ALLOC)),
old_bit_array, old_mem_size);
/* Replace old array with new array, and free old array */
SET_ATTR_bit_array(INTERP, SELF, new_bit_array);
mem_gc_free(INTERP, old_bit_array);
/* Added one allocation unit to the head position offset */
SET_ATTR_size(INTERP, SELF, tail_pos + MIN_ALLOC);
SET_ATTR_resize_threshold(INTERP, SELF, head_pos + MIN_ALLOC);
}
/* Move the head position */
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
SET_ATTR_resize_threshold(INTERP, SELF, --head_pos);
/* Assign the new value as the first item */
SELF.set_integer_keyed_int(0, value);
}
/*
=item C<void shift_integer(INTVAL value)>
Removes and returns the first element.
=cut
*/
VTABLE INTVAL shift_integer() {
INTVAL value;
UINTVAL tail_pos, head_pos;
GET_ATTR_size(INTERP, SELF, tail_pos);
if (tail_pos < 1)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_OUT_OF_BOUNDS,
"Can't shift from an empty array");
/* Get head value */
value = SELF.get_integer_keyed_int(0);
/* Move the head position */
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
SET_ATTR_resize_threshold(INTERP, SELF, ++head_pos);
/* If the head position offset is greater than our allocation unit
* size, size this thing down */
if (head_pos >= MIN_ALLOC) {
/* Allocate one allocation unit less of space in new array */
unsigned char *new_bit_array, *old_bit_array;
size_t new_mem_size;
new_mem_size = ROUND_BYTES(tail_pos - MIN_ALLOC);
new_bit_array =
(unsigned char *)Parrot_gc_allocate_memory_chunk(INTERP, new_mem_size);
memset(new_bit_array, 0, new_mem_size);
/* Copy contents of old array to new array, move the head position
* offset back by one allocation unit (in bytes) */
GET_ATTR_bit_array(INTERP, SELF, old_bit_array);
memmove(new_bit_array, old_bit_array + (BITS_TO_BYTES(MIN_ALLOC)),
new_mem_size);
/* Replace old array with new array, and free old array */
SET_ATTR_bit_array(INTERP, SELF, new_bit_array);
mem_gc_free(INTERP, old_bit_array);
/* Removed one allocation unit from the head position offset */
SET_ATTR_size(INTERP, SELF, tail_pos - MIN_ALLOC);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
SET_ATTR_resize_threshold(INTERP, SELF, head_pos- MIN_ALLOC);
}
return value;
}
/*
=item C<INTVAL elements()>
=cut
*/
VTABLE INTVAL elements() :no_wb {
UINTVAL tail_pos, head_pos;
GET_ATTR_size(INTERP, SELF, tail_pos);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
return tail_pos - head_pos;
}
/*
=item C<INTVAL get_integer()>
Returns the number of elements in the array.
=cut
*/
VTABLE INTVAL get_integer() :no_wb {
return SELF.elements();
}
/*
=item C<PMC *clone()>
Returns a copy of the array.
=cut
*/
VTABLE PMC *clone() :no_wb {
UINTVAL tail_pos, head_pos;
unsigned char * my_bit_array, * dest_bit_array;
PMC * const dest = Parrot_pmc_new(INTERP, SELF->vtable->base_type);
GET_ATTR_bit_array(INTERP, SELF, my_bit_array);
GET_ATTR_size(INTERP, SELF, tail_pos);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
SET_ATTR_size(INTERP, dest, tail_pos);
SET_ATTR_resize_threshold(INTERP, dest, head_pos);
if (my_bit_array) {
const size_t size_in_bits = tail_pos / BITS_PER_CHAR + 1;
dest_bit_array = (unsigned char *)Parrot_gc_allocate_memory_chunk(INTERP, size_in_bits);
memcpy(dest_bit_array, my_bit_array, size_in_bits);
}
else
dest_bit_array = NULL;
SET_ATTR_bit_array(INTERP, dest, dest_bit_array);
PObj_custom_destroy_SET(dest);
return dest;
}
/*
=back
=head2 Freeze/thaw Interface
=over 4
=item C<void freeze(PMC *info)>
Used to archive the string.
=cut
*/
VTABLE void freeze(PMC *info) :no_wb {
/* XXX Dino - I'm concerned about freezing the entire
allocated block of memory, it's dependent on the
BITS_PER_CHAR value.
Maybe we need to store that during the freeze as well
and use it during thaw?
*/
STRING *s;
UINTVAL tail_pos, rounded_size, head_pos;
unsigned char *bit_array;
GET_ATTR_size(INTERP, SELF, tail_pos);
GET_ATTR_resize_threshold(INTERP, SELF, head_pos);
GET_ATTR_bit_array(INTERP, SELF, bit_array);
rounded_size = ROUND_BYTES(tail_pos);
VTABLE_push_integer(INTERP, info, head_pos);
VTABLE_push_integer(INTERP, info, tail_pos);
s = Parrot_str_new(INTERP, (char*)bit_array, rounded_size);
VTABLE_push_string(INTERP, info, s);
}
/*
=item C<void thaw(PMC *info)>
Used to unarchive the string.
=cut
*/
VTABLE void thaw(PMC *info) {
const UINTVAL head_pos = VTABLE_shift_integer(INTERP, info);
const UINTVAL tail_pos = VTABLE_shift_integer(INTERP, info);
STRING * const s = VTABLE_shift_string(INTERP, info);
const size_t size_in_bytes = ROUND_BYTES(tail_pos);
unsigned char *bit_array;
SELF.set_integer_native(tail_pos);
SET_ATTR_resize_threshold(INTERP, SELF, head_pos);
if (s->bufused < size_in_bytes)
Parrot_ex_throw_from_c_noargs(INTERP, EXCEPTION_BAD_BUFFER_SIZE,
"ResizableBooleanArray: invalid buffer size during thaw");
GET_ATTR_bit_array(INTERP, SELF, bit_array);
memcpy(bit_array, s->strstart, size_in_bytes);
}
} /* pmclass */
/*
=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' :
*/