Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

227 lines (207 sloc) 8.197 kb
#include "parrot/parrot.h"
#define self (*attrs)
#define FPQ_DECL_ATTRS(SELF) Parrot_FixedPMCQueue3_attributes * const attrs = PARROT_FIXEDPMCQUEUE3(SELF)
#define FPQ_IDX_ADD(x, offset) (((x) + (offset)) % self.size)
#define FPQ_IDX_DIFF(x, y) (((x) + self.size - (y)) % self.size)
#define FPQ_IDX_INCR(x) (x) = FPQ_IDX_ADD((x), 1)
#define FPQ_IDXF_INCR(f) FPQ_IDX_INCR(self.f)
#define FPQ_ITEMS() (self.size > 0 ? FPQ_IDX_DIFF(self.queue_end, self.queue_start) : 0)
#define FPQ_EMPTY() (self.queue_start == self.queue_end)
#define FPQ_FULL() (self.queue_end + 1 - self.queue_start == 0 || self.queue_end + 1 - self.queue_start == self.size)
// (self.queue_start == self.queue_end+1 || self.queue_start == 0 && self.queue_end == self.size-1)
// ((self.queue_end + 1) % self.size == self.queue_start)
#define FPQ_ALLOCATE(len) mem_allocate_n_typed(len, PMC *)
#define FPQ_REALLOCATE(p, len) mem_realloc_n_typed(p, len, PMC *)
#define FPQ_ITERATE(index,func) { \
if (self.queue_start > self.queue_end) { \
INTVAL index; \
for (index = self.queue_start; index < self.size; index++) { \
func; \
} \
for (index = 0; index < self.queue_end; index++) { \
func; \
} \
} else { \
INTVAL index; \
for (index = self.queue_start; index < self.queue_end; index++) { \
func; \
} \
} \
}
/*
* FixedPMCQueue3 is a fixed-length FIFO queue structure. It is optimized for
* push/shift access. FPQ will be implemented as a ring buffer.
*
* This version omits the "items" field and computes the count as
* (queue_end-queue_start)%size
*
* It also tries to ensure thread-safety, by having an "owner" thread for
* each end of the queue.
*
* TODO: haven't implemented the thread-safety yet!!!
*/
pmclass FixedPMCQueue3 dynpmc auto_attrs provides queue {
ATTR INTVAL size;
ATTR PMC **storage;
ATTR INTVAL queue_start;
ATTR INTVAL queue_end;
ATTR INTVAL head_tid;
ATTR INTVAL tail_tid;
/* Initialize the PMC */
VTABLE void init() {
PObj_custom_mark_destroy_SETALL(SELF);
/* All fields in attrs should be null/0, so no worries about
initialization here. */
}
/* Destroy the PMC. Free allocated storage */
VTABLE void destroy() {
FPQ_DECL_ATTRS(SELF);
if (self.storage)
mem_sys_free(self.storage);
}
/* Mark the PMC for GC. */
VTABLE void mark() {
FPQ_DECL_ATTRS(SELF);
PMC ** const s = self.storage;
if (s)
FPQ_ITERATE(i, Parrot_gc_mark_PMC_alive(INTERP, s[i]));
}
VTABLE void freeze(PMC *info) {
}
VTABLE void thaw(PMC *info) {
}
VTABLE void visit(PMC *info) {
FPQ_DECL_ATTRS(SELF);
PMC ** const storage = self.storage;
if (storage)
FPQ_ITERATE(i, VISIT_PMC(INTERP, info, storage[i]));
}
/* Size the queue. Cannot shrink the queue smaller than the number of items
currently in the queue. */
VTABLE void set_integer_native(INTVAL newsize) {
FPQ_DECL_ATTRS(SELF);
const INTVAL start = self.queue_start;
const INTVAL end = self.queue_end;
const INTVAL size = self.size;
const INTVAL items = FPQ_ITEMS();
if (newsize < items)
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
"FixedPMCQueue3: Cannot shrink size with items in queue");
/* TODO: THREADSAFE */
++newsize; /* reserve one more slot than actually used, so that 0 <= items < size */
if (newsize != size) {
if (start == 0) {
FPQ_REALLOCATE(self.storage, newsize);
self.size = newsize;
} else {
PMC ** const oldstorage = self.storage;
PMC ** newstorage = FPQ_ALLOCATE(newsize);
if ( start > end ) {
mem_sys_memmove( &newstorage[0], &oldstorage[start], (size - start) * sizeof(PMC*));
mem_sys_memmove( &newstorage[size - start], &oldstorage[0], end * sizeof(PMC*));
} else {
mem_sys_memmove( &newstorage[0], &oldstorage[start], (end - start) * sizeof(PMC*));
}
if (oldstorage)
mem_sys_free(oldstorage);
self.storage = newstorage;
self.size = newsize;
self.queue_start = 0;
self.queue_end = items;
}
}
}
/* Push an item onto the queue */
VTABLE void push_pmc(PMC *item) {
FPQ_DECL_ATTRS(SELF);
/* TODO: THREADSAFE */
if (FPQ_FULL())
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
"FixedPMCQueue3: Pushed too many items");
self.storage[self.queue_end] = item;
FPQ_IDXF_INCR(queue_end);
}
/* Pull an item off the queue */
VTABLE PMC* shift_pmc() {
FPQ_DECL_ATTRS(SELF);
PMC * first_item;
/* TODO: THREADSAFE */
if (FPQ_EMPTY())
return PMCNULL;
first_item = self.storage[self.queue_start];
FPQ_IDXF_INCR(queue_start);
return first_item;
}
/* Is the queue non-empty? */
VTABLE INTVAL get_bool() {
FPQ_DECL_ATTRS(SELF);
return !FPQ_EMPTY();
}
/* Number of items in the queue */
VTABLE INTVAL elements() {
FPQ_DECL_ATTRS(SELF);
return FPQ_ITEMS();
}
VTABLE INTVAL get_integer() {
FPQ_DECL_ATTRS(SELF);
return FPQ_ITEMS();
}
/* Total amount of allocated storage slots in the queue */
METHOD capacity() {
FPQ_DECL_ATTRS(SELF);
PMC * result;
if (self.size <= 0)
result = PMCNULL;
else {
result = Parrot_pmc_new(INTERP,
Parrot_get_ctx_HLL_type(INTERP,
enum_class_Integer));
VTABLE_set_integer_native(INTERP, result, self.size-1); // available size is one less than allocate space
}
RETURN(PMC* result);
}
/* Convert the queue to a FixedPMCArray. The array will have the same
length as the queue, all additional spaces will contain PMCNULL */
METHOD to_array() {
FPQ_DECL_ATTRS(SELF);
PMC * newarray = Parrot_pmc_new(INTERP, enum_class_FixedPMCArray);
const INTVAL size = self.size;
PMC ** const s = self.storage;
INTVAL i = 0;
VTABLE_set_integer_native(INTERP, newarray, size);
FPQ_ITERATE(ptr, VTABLE_set_pmc_keyed_int(INTERP, newarray, i++, s[ptr]));
while (i < size) VTABLE_set_pmc_keyed_int(INTERP, newarray, i++, PMCNULL);
RETURN(PMC* newarray);
}
/* Get the total size of the queue in memory, in bytes, including the PMC
structure allocation size */
METHOD total_mem_size() {
FPQ_DECL_ATTRS(SELF);
INTVAL const storage_size = self.size * sizeof(PMC *);
INTVAL const struct_size = sizeof(PMC) + sizeof(Parrot_FixedPMCQueue3_attributes);
INTVAL const total_size = storage_size + struct_size;
RETURN(INTVAL total_size);
}
/* Clear the queue, optionally resizing it */
METHOD clear(INTVAL newsize :optional, INTVAL has_size :opt_flag) {
FPQ_DECL_ATTRS(SELF);
INTVAL const size = self.size;
if (has_size) {
if (newsize <= 0)
Parrot_ex_throw_from_c_args(INTERP, NULL, EXCEPTION_OUT_OF_BOUNDS,
"FixedPMCQueue3: Cannot set to zero or negative size");
if (self.storage)
mem_sys_free(self.storage);
self.storage = FPQ_ALLOCATE(newsize);
self.size = newsize;
}
self.queue_start = 0;
self.queue_end = 0;
}
}
/*
* Local variables:
* c-file-style: "parrot"
* End:
* vim: expandtab shiftwidth=4:
*/
Jump to Line
Something went wrong with that request. Please try again.