Array append proposal

[Sergey Gromov]

Fri, 10 Oct 2008 12:28:02 -0400,
Steven Schveighoffer wrote:
> "Steven Schveighoffer" wrote
> > "Sergey Gromov" wrote
> >> Fri, 10 Oct 2008 11:11:40 -0400,
> >> Steven Schveighoffer wrote:
> >>> First, store the allocated length of the array on the heap along with 
> >>> the
> >>> array data.  On a 32-bit system, the size will always be 4 bytes, but 
> >>> there
> >>> can be padding bytes added to keep the alignment for the first element 
> >>> in
> >>> the array correct.  The maximum padding, I am not sure about.  I 
> >>> remember
> >>> people saying that for certain operations, 16 byte alignment is 
> >>> required?
> >>> Or is it just 8?  So for instance an array of doubles, there would be an
> >>> 8-byte field storing the length in the first 4 bytes, and padding in the
> >>> second 4 bytes.
> >>>
> >>> Perhaps someone with more knowledge of alignment requirements can 
> >>> comment.
> >>> I'd also appreciate some insight on how this would look on a 64 bit 
> >>> system.
> >>>
> >>> The final detail is how to tell whether the element before an array is 
> >>> the
> >>> length or not.  I propose to use the most significant bit in the array
> >>> length field.  This prevents having arrays of > 2GB, but that's probably
> >>> impossible anyways ;)
> >>>
> >>> If this bit is set, then the array can be appended to in place if its 
> >>> length
> >>> equals the length stored in the heap (and of course, the memory block
> >>> contains enough space).  If not, then a new array is allocated, and the 
> >>> data
> >>> copied, the length stored in the heap is left alone.
> >>
> >> How do you implement a slice?  It points in the middle of another array,
> >> data around that point is arbitrary.  There is no way you can check if
> >> you are at the beginning of an array or not.
> >
> > If the first element of the slice is not the first element of the 
> > allocated array, then it does not have its 'at the beginning' bit set in 
> > its local length.
> 
> An example:
> 
> int[] array = new int[10];
> 
> array's length field is set to 0x8000_000a -> most significant bit set means 
> it can possibly be appended to.
> 
> int[] slice = array[0..$];
> 
> slice's length field is set to 0x8000_000a -> most significant bit set means 
> it can possibly be appended to.
> 
> int[] slice2 = array[1..5];
> 
> slice2's length field is set to 0x0000_0004 -> most significant bit unset. 
> Will always allocate a new array on an append.

Yes, I've got it from your first explanation, thank you.  :)