Author: allison
Date: Mon Apr 16 18:42:39 2007
New Revision: 18249
Modified:
trunk/src/pmc/resizablebooleanarray.pmc
trunk/t/pmc/resizablebooleanarray.t
Log:
Fix ResizableBooleanArray's shift and unshift allocation and memory copy, and
make the tests check for the contents of shifted arrays, not just the number of
elements (having the right number of elements, but with the wrong values isn't
good enough).
Modified: trunk/src/pmc/resizablebooleanarray.pmc
==============================================================================
--- trunk/src/pmc/resizablebooleanarray.pmc (original)
+++ trunk/src/pmc/resizablebooleanarray.pmc Mon Apr 16 18:42:39 2007
@@ -58,13 +58,12 @@
"ResizableBooleanArray: index out of bounds!");
}
- /* Adjust key for the current head position */
- key += PMC_int_val2(SELF);
-
- if (key >= PMC_int_val(SELF))
+ /* Check if key is greater than allocated size */
+ INTVAL offsetkey = key + PMC_int_val2(SELF);
+ if (offsetkey >= PMC_int_val(SELF))
DYNSELF.set_integer_native(key+1);
- return SUPER(key);
+ return SUPER(offsetkey);
}
/*
@@ -88,13 +87,12 @@
"ResizableBooleanArray: index out of bounds!");
}
- /* Adjust key for the current head position */
- key += PMC_int_val2(SELF);
-
- if (key >= PMC_int_val(SELF))
+ /* Check if key is greater than allocated size */
+ INTVAL offsetkey = key + PMC_int_val2(SELF);
+ if (offsetkey >= PMC_int_val(SELF))
DYNSELF.set_integer_native(key+1);
- SUPER(key, value);
+ SUPER(offsetkey, value);
}
/*
@@ -108,12 +106,15 @@
*/
void set_integer_native(INTVAL size) {
- INTVAL newallocbits, curallocbits, memsize;
- const INTVAL cursize = PMC_int_val(SELF) - PMC_int_val2(SELF);
+ INTVAL newsize, newallocbits, curallocbits, memsize;
+ const INTVAL cursize = PMC_int_val(SELF);
+
+ /* Size respects any existing head position offset from unshift */
+ newsize = size + PMC_int_val2(SELF);
/* We are already at the requested size. Yay */
- if (size == cursize)
+ if (newsize == cursize)
return;
@@ -121,7 +122,7 @@
real_exception(interp, NULL, E_IndexError,
"ResizableBooleanArray: Can't resize!");
- newallocbits = (size / MIN_ALLOC + 1) * MIN_ALLOC;
+ newallocbits = (newsize / MIN_ALLOC + 1) * MIN_ALLOC;
curallocbits = (cursize / MIN_ALLOC + 1) * MIN_ALLOC;
memsize = newallocbits / BITS_PER_CHAR;
@@ -129,14 +130,13 @@
if (! PMC_data(SELF)) {
PMC_data(SELF) = mem_sys_allocate_zeroed(memsize);
}
- /* The size is different, but and doesn't fit within the current
allocation */
+ /* The size is different, and doesn't fit within the current
allocation */
else if (newallocbits != curallocbits) {
Parrot_UInt1 * const sd = PMC_data(SELF);
PMC_data(SELF) = mem_sys_realloc(sd, memsize);
}
- PMC_int_val2(SELF) = 0;
- PMC_int_val(SELF) = size;
+ PMC_int_val(SELF) = newsize;
}
/*
@@ -191,19 +191,31 @@
*/
void unshift_integer(INTVAL value) {
- /* If int_val2 is smaller than 0, size this thing up */
+ /* If the current head position offset is 0, size this thing up by one
+ * allocation unit */
if (PMC_int_val2(SELF) <= 0) {
Parrot_UInt1 * const sdOld = PMC_data(SELF);
- Parrot_UInt1 * const sdNew = mem_sys_allocate_zeroed(
- ((PMC_int_val2(SELF) / MIN_ALLOC) * MIN_ALLOC)
- + PMC_int_val(SELF)
- + ((PMC_int_val(SELF) / MIN_ALLOC + 1) * MIN_ALLOC));
- mem_sys_memmove(sdNew, sdOld + PMC_int_val2(SELF),
- PMC_int_val(SELF));
- mem_sys_free(sdOld);
+
+ /* Allocate an extra allocation unit of space in new array */
+ INTVAL oldbitalloc, oldmemsize, newbitalloc, newmemsize;
+ newbitalloc = ((PMC_int_val(SELF) + MIN_ALLOC) / MIN_ALLOC + 1) *
MIN_ALLOC;
+ newmemsize = newbitalloc / BITS_PER_CHAR;
+ Parrot_UInt1 * const sdNew = mem_sys_allocate_zeroed(newmemsize);
+
+ /* Copy contents of old array to new array, moving the head
+ * position forward by one allocation unit (in bytes). */
+ oldbitalloc = (PMC_int_val(SELF) / MIN_ALLOC + 1) * MIN_ALLOC;
+ oldmemsize = oldbitalloc / BITS_PER_CHAR;
+ mem_sys_memmove(sdNew + (MIN_ALLOC / BITS_PER_CHAR), sdOld,
oldmemsize);
+
+ /* Replace old array with new array, and free old array */
PMC_data(SELF) = sdNew;
+ mem_sys_free(sdOld);
+
+ /* Added one allocation unit to the head position offset */
PMC_int_val2(SELF) += MIN_ALLOC;
- PMC_int_val(SELF) += MIN_ALLOC;
+ PMC_int_val(SELF) += MIN_ALLOC;
+
}
/* Move the head position */
@@ -236,18 +248,28 @@
/* Move the head position */
PMC_int_val2(SELF)++;
- /* If int_val2 is bigger than our allocation unit size, size
- this thing down */
+ /* If the head position offset is greater than our allocation unit
+ * size, size this thing down */
if (PMC_int_val2(SELF) >= MIN_ALLOC) {
+ /* Allocate one allocation unit less of space in new array */
+ INTVAL oldbitalloc, oldmemsize, newbitalloc, newmemsize;
+ newbitalloc = ((PMC_int_val(SELF) - MIN_ALLOC) / MIN_ALLOC + 1) *
MIN_ALLOC;
+ newmemsize = newbitalloc / BITS_PER_CHAR;
+ Parrot_UInt1 * const sdNew = mem_sys_allocate_zeroed(newmemsize);
+
+ /* Copy contents of old array to new array, move the head position
+ * offset back by one allocation unit (in bytes) */
Parrot_UInt1 * const sdOld = PMC_data(SELF);
- Parrot_UInt1 * const sdNew = mem_sys_allocate_zeroed(
- ((PMC_int_val2(SELF) / MIN_ALLOC) * MIN_ALLOC)
- + PMC_int_val(SELF)
- + ((PMC_int_val(SELF) / MIN_ALLOC + 1) * MIN_ALLOC));
- mem_sys_memmove(sdNew, sdOld + PMC_int_val2(SELF),
- PMC_int_val(SELF));
- mem_sys_free(sdOld);
+ mem_sys_memmove(sdNew, sdOld + (MIN_ALLOC / BITS_PER_CHAR),
newmemsize);
+
+ /* Replace old array with new array, and free old array */
PMC_data(SELF) = sdNew;
+ mem_sys_free(sdOld);
+
+ /* Removed one allocation unit from the head position offset */
+ PMC_int_val2(SELF) -= MIN_ALLOC;
+ PMC_int_val(SELF) -= MIN_ALLOC;
+
}
return value;
Modified: trunk/t/pmc/resizablebooleanarray.t
==============================================================================
--- trunk/t/pmc/resizablebooleanarray.t (original)
+++ trunk/t/pmc/resizablebooleanarray.t Mon Apr 16 18:42:39 2007
@@ -420,42 +420,72 @@
.local int elements
i= 1
- pmc_arr= new ResizableBooleanArray
+ pmc_arr = new ResizableBooleanArray
+ # No elements are set
print_num_elements( pmc_arr )
+ # Set two of the first three elements
+ pmc_arr[0] = 1
+ pmc_arr[2] = 1
+ print_num_elements( pmc_arr )
+
+ # Unshift a "1" element on
unshift pmc_arr, i
print i
print_num_elements( pmc_arr )
+ # Unshift a "0" element on
unshift pmc_arr, 0
print 0
print_num_elements( pmc_arr )
- print_num_elements( pmc_arr )
-
+ # Shift an element off
i_elem= shift pmc_arr
print i_elem
print_num_elements( pmc_arr )
+ # Shift an element off
i_elem= shift pmc_arr
print i_elem
print_num_elements( pmc_arr )
- pmc_arr = 62
- unshift pmc_arr, 0
- unshift pmc_arr, 1
- unshift pmc_arr, 0
- unshift pmc_arr, 1
- i_elem = shift pmc_arr
- i_elem = shift pmc_arr
- i_elem = shift pmc_arr
- print i_elem
- print_num_elements(pmc_arr)
-
- # Set same size array is currently
- pmc_arr = 63
- print_num_elements(pmc_arr)
+ # Resize the array
+ pmc_arr = 62
+ print_num_elements(pmc_arr)
+
+ # Unshift 4 elements on
+ unshift pmc_arr, 1
+ unshift pmc_arr, 1
+ unshift pmc_arr, 0
+ unshift pmc_arr, 1
+ print_num_elements(pmc_arr)
+
+ # Shift 3 elements off
+ i_elem = shift pmc_arr
+ i_elem = shift pmc_arr
+ i_elem = shift pmc_arr
+ print i_elem
+ print_num_elements(pmc_arr)
+
+ # Set same size array is currently
+ pmc_arr = 63
+ print_num_elements(pmc_arr)
+
+ # Set 101th element
+ pmc_arr[100] = 1
+ print_num_elements(pmc_arr)
+
+ # Shift off 99 elements
+ .local int counter
+ counter = 98
+shift_loop:
+ i_elem = shift pmc_arr
+ dec counter
+ if counter > 0 goto shift_loop
+
+ print i_elem
+ print_num_elements(pmc_arr)
.end
.sub print_num_elements
@@ -465,18 +495,43 @@
print '['
print elements
print "]\n"
+ $I0 = pmc_arr[0]
+ print $I0
+ print ', '
+ $I0 = pmc_arr[1]
+ print $I0
+ print ', '
+ $I0 = pmc_arr[2]
+ print $I0
+ print "\n"
.return()
.end
CODE
[0]
-1[1]
-0[2]
-[2]
-0[1]
-1[0]
+0, 0, 0
+[3]
+1, 0, 1
+1[4]
+1, 1, 0
+0[5]
+0, 1, 1
+0[4]
+1, 1, 0
+1[3]
+1, 0, 1
+[62]
+1, 0, 1
+[66]
+1, 0, 1
1[63]
+1, 1, 0
[63]
+1, 1, 0
+[101]
+1, 1, 0
+0[3]
+0, 0, 1
OUTPUT
pir_output_like( << 'CODE', << 'OUTPUT', "shift bounds checking" );
@@ -772,11 +827,11 @@
set I10, 100
set I0, 0
# push some values at start
-lp1:
+loop1:
mod I5, I0, 2
push P0, I5
inc I0
- lt I0, I10, lp1
+ lt I0, I10, loop1
# create sparse
set I0, 100000
@@ -785,12 +840,12 @@
#set P0[I0], I1
set P0[I0], I5
inc I1
-lp2:
+loop2:
# push some values after hole
mod I5, I1, 2
push P0, I5
inc I1
- le I1, 1100, lp2
+ le I1, 1100, loop2
dec I1
set I3, P0
