resizablebooleanarray.pmc

/*
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' :
 */