The physical representation uses an insert-at-the-end mechanism for adding contents to the array. Any insertion will occur at the very end of the array, and any expansion of an element will move it to the end, leaving an empty slot behind. Terminology: long-word: a 64-bit-aligned 64 bit word short-word: a 16-bit-aligned 16 bit word byte: an 8-bit-aligned byte long-index: an index of a 64-bit-aligned word within the overall array (i.e. in multiples of 8 bytes) short-index: an index of a 16-bit aligned short within the overall array (i.e. in multiples of 2 bytes) byte-index: an index of an 8-bit aligned byte within the overall array (i.e. in multiples of 1 byte) The storage array stores long (64 bit) words. Lookups for the variuous sizes are done as such: long getAtLongIndex(int longIndex) { return array[longIndex]; } short getAtShortIndex(int shortIndex) { return (short)((array[shortIndex >> 2] >> (shortIndex & 0x3)) & 0xffff); } byte getAtByteIndex(int byteIndex) { return (byte)((array[byteIndex >> 3] >> (byteIndex & 0x7)) & 0xff); } [Therefore there is no dependence on byte endiannes of the underlying arhcitecture] Structure: The packed array captures values at virtual indexes in a collection of striped "set trees" (also called "sets"), with each set tree representing one byte of the value at the virtual index in question. As such, there are 8 sets in the array, each corresponding to a byte in the overall value being stored. Set 0 contains the LSByte of the value, and Set 7 contains the MSByte of the value. The array contents is comprised of thre types of entries: - The root indexes: A fixed size 8 short-words array of short indexes at the start of the array, containing the short-index of the root entry of each of the 8 set trees. - Non-Leaf Entires: Variable sized, 2-18 short-words entries representing non-leaf entries in a set tree. Non-Leaf entries comprise of a 2 short-word header containing a packed slot indicators bitmask and the (optional non-zero) index of previous version of the entry, followed by an array of 0-16 shortwords. The short-word found at a given slot in this array holds an index to an entry in the next level of the set tree. - Leaf Entries: comprised of long-words. Each byte [0-7] in the longword holds an actual value. Specifically, the byte-index of that LeafEntry byte in the array is the byte-index for the given set's byte value of a virtual index. If a given virtual index for a given set has no entry in a given set tree, the byte value for that set of that virtual index interpreted as 0. If a given set tree does not have an entry for a given virtual index, it is safe to assume that no higher significance set tree have one either. Non-leaf entries structure and mutation protocols: The structure of a Non-Leaf entry in the array can be roughly desctibed in terms of this C-stylre struct: struct nonLeafEntry { short packedSlotIndicators; short previousVersionIndex; short[] enrtrySlotsIndexes; } Non-leaf entries are 2-18 short-words in length, with the length determined by the number of bits set in the packedSlotIndicators short-word in the entry. The packed slot indicators short-word is a bit mask which represents the 16 possible next-level entries below the given entry, and has a bit set (to '1') for each slot that is actually populated with a next level entry. Each of the short-words in the enrtrySlots is associated with a specific active ('1') bit in the packedSlotIndicators short-word, and holds the index to the next level's entry associated with ta given path in the tree. [Note: the values in enrtrySlotsIndexes[] are short-indexes if the next level is not a leaf level, and long-indexes if the next level is a leaf.] Summary of Non-leaf entry use and replacement protocol: - No value in any enrtrySlotsIndexes[] array is ever initialized to a zero value. Zero values in enrtrySlotsIndexes[] can only appear through consolidation (see below). Once an enrtrySlotsIndexes[] slot is observed to contain a zero, it cannot change to a non-zero value. - Zero values encountered in enrtrySlotsIndexes[] arrays are never followed. If a zero value is found when looking for the index to a lower level entry during a tree walk, the tree walking operation is restarted from the root. - A Non-Leaf entry with an active (non zero index) previous version is never followed or expanded. Instead, any thread encountering a Non-leaf entry with an active previous version will consolidate the previous version with the current one. the consolidation opeartion will clear (zero) the previousVersionIndex, which will then allow the caller to continue with whatever use the thread was attempting to make of the entry. - Expansion of entries: Since entries hold only enough storage to represent currently populated paths below them in the set tree, any addition of entries at a lower level requires the expansion of the entry to make room for a larger enrtrySlotsIndexes array. Expansion allocates a new and larger entry structure, and populates the newly inserted slot in it with an index to a newly allocated next-level entry. It then links the newly expanded entry the previous entry structure via the previousVersionIndex field, and publishes the newly expanded entry by [atomically] replacing the "pointer index" to the previous entry (located at a higher level entry's slot, or in the root indexes) with a "pointer index" to the newly expanded entry structure. A failure to atomically publish a newly expanded entry (e.g. if the "pointer index" being replaced holds a value other than that in our not-yet-published previousVersionIndex) will restart the expansion operation from the beginning. When first published, a newly-visible expanded entry is immediately "usable" because it has an active, "not yet consolidated" previous version entry, and any user of the entry will first have to consolidate it. The expansion will follow publication of the expanded entry with a consolidation of the previous entry into the new one, clearing the previousVersionIndex field in the process, and enabling normal use of the expanded entry. - Concurrent consolidation: While expansion and consolidation are ongoing, other threads can be concurrently walking the set trees. Per the protocol stated here, any tree walk encountering a Non-Leaf entry with an active previous version will consolidate the entry before using it. Consolidation can of a given entry can occur concurrently by an an expanding thread and by multiple walking threads. - Consolidation of a a previous version entry into a current one is done by: - For each non-zero index in the previous version enrty, copy that index to the new assocaited entry slot in the entry, and CAS a zero in the old entry slot. If the CAS fails, repeat (including the zero check). - Once all entry slots in the previous version entry have been consolidated and zeroed, zero the index to the previous version entry.