On 10/5/06, Leopold Toetsch <[EMAIL PROTECTED]> wrote:
Am Donnerstag, 5. Oktober 2006 01:49 schrieb Karl Forner: > > Whare the requirements/constraints of a ResizableBooleanArray ? e.g are > unshift to be less frequent that shift ? shift and unshift are both more unlikely than push/pop I presume. OTOH if a user wants a bit queue, you have to deal with both ends ;) > Should I keep the actual implementation concept : allocating by chunks of > 64 bytes ? 64 bytes is any arbitray number but probably fine. It ought to be some power of 2 though and smaller than 16 bytes doesn't make sense. The basic problem with Resizable*Array is: we'd need 3 fields for book-keeping: first_elem 0 unless shift/unshift was done last_elem_p1 elements = last_elem_p1 - first_elem allocated amount of allocated memory The latter is of course just an optimization, but we can't afford resizing on each size change. Current PMC layout only allows for 2 integer fields: PMC_int_val and PMC_int_val2.
Ok. So first maybe the best way is to use an external lib (GMP or Bit::Vector, cf previous mail in thread)... Otherwise, I have imagined two approaches : 1) in the hypothesis that shift/unshifts are more unlikely, it can be done in a way that uses only the 2 integer fields, one for the nb of elements, the other for the allocated memory. If a shift or unshift is needed, then alloc and copy. 2) in all resize ops are to be symmetrical, we can allocate a third int field : PMC_data could point to a struct holding a buffer and its size. ResizableBooleanArray tried to implement this strategy:
1) 'allocated' is always the minimal n*64 bytes (aka n*CHNUK_SIZE) 2) if there's more room than CHUNK_SIZE on either side of the array, reallocation and moving of bits happens to fullfill again constraint 1. 3) and of course, if more bits are needed, reallocation must be done.
yes that's what I had figured out. Karl
