Package org.HdrHistogram.packedarray
Class AbstractPackedArrayContext
- java.lang.Object
-
- org.HdrHistogram.packedarray.AbstractPackedArrayContext
-
- All Implemented Interfaces:
java.io.Serializable
- Direct Known Subclasses:
PackedArrayContext
abstract class AbstractPackedArrayContext extends java.lang.Object implements java.io.Serializable
A packed-value, sparse array context used for storing 64 bit signed values. An array context is optimised for tracking sparsely set (as in mostly zeros) values that tend to not make use pof the full 64 bit value range even when they are non-zero. The array context's internal representation is such that the packed value at each virtual array index may be represented by 0-8 bytes of actual storage. An array context encodes the packed values in 8 "set trees" with each set tree representing one byte of the packed value at the virtual index in question. ThegetPackedIndex(int, int, boolean)
method is used to look up the byte-index corresponding to the given (set tree) value byte of the given virtual index, and can be used to add entries to represent that byte as needed. As a succesfulgetPackedIndex(int, int, boolean)
may require a resizing of the array, it can throw aResizeException
to indicate that the requested packed index cannot be found or added without a resize of the physical storage.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) class
AbstractPackedArrayContext.NonZeroValues
(package private) class
AbstractPackedArrayContext.NonZeroValuesIterator
private static class
AbstractPackedArrayContext.RetryException
-
Field Summary
Fields Modifier and Type Field Description private boolean
isPacked
private static int
LEAF_LEVEL_SHIFT
(package private) static int
MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH
(package private) static int
MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
private static int
NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
private static int
NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET
private static int
NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET
private static int
NUMBER_OF_SETS
private static int
PACKED_ARRAY_GROWTH_FRACTION_POW2
private static int
PACKED_ARRAY_GROWTH_INCREMENT
The physical representation uses an insert-at-the-end mechanism for adding contents to the array.private int
physicalLength
private static int
SET_0_START_INDEX
private int
topLevelShift
private int
virtualLength
-
Constructor Summary
Constructors Constructor Description AbstractPackedArrayContext(int virtualLength, int initialPhysicalLength)
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description (package private) abstract long
addAndGetAtUnpackedIndex(int index, long valueToAdd)
(package private) long
addAtByteIndex(int byteIndex, byte valueToAdd)
add a byte value to a current byte value in the array(package private) abstract boolean
casAtLongIndex(int longIndex, long expectedValue, long newValue)
(package private) boolean
casAtShortIndex(int shortIndex, short expectedValue, short newValue)
private boolean
casIndexAtEntrySlot(int entryIndex, int slot, short expectedIndexValue, short newIndexValue)
private boolean
casIndexAtEntrySlotIfNonZeroAndLessThan(int entryIndex, int slot, short newIndexValue)
(package private) abstract boolean
casPopulatedLongLength(int expectedPopulatedShortLength, int newPopulatedShortLength)
(package private) abstract boolean
casPopulatedShortLength(int expectedPopulatedShortLength, int newPopulatedShortLength)
(package private) abstract void
clearContents()
private void
consolidateEntry(int entryIndex)
Consolidate entry with previous entry verison if one existsprivate long
contextLocalGetValueAtIndex(int virtualIndex)
private void
copyEntriesAtLevelFromOther(AbstractPackedArrayContext other, int otherLevelEntryIndex, int levelEntryIndexPointer, int otherIndexShift)
(package private) int
determineTopLevelShiftForVirtualLength(int virtualLength)
private void
expandArrayIfNeeded(int entryLengthInLongs)
private int
expandEntry(int existingEntryIndex, int entryPointerIndex, int insertedSlotIndex, int insertedSlotMask, boolean nextLevelIsLeaf)
Expand entry as indicated.private int
findFirstPotentiallyPopulatedVirtualIndexStartingAt(int startingVirtualIndex)
(package private) byte
getAtByteIndex(int byteIndex)
(package private) abstract long
getAtLongIndex(int longIndex)
(package private) short
getAtShortIndex(int shortIndex)
(package private) abstract long
getAtUnpackedIndex(int index)
private short
getIndexAtEntrySlot(int entryIndex, int slot)
(package private) short
getIndexAtShortIndex(int shortIndex)
(package private) int
getPackedIndex(int setNumber, int virtualIndex, boolean insertAsNeeded)
Get the byte-index (into the packed array) corresponding to a given (set tree) value byte of given virtual index.private int
getPackedSlotIndicators(int entryIndex)
(package private) int
getPhysicalLength()
(package private) int
getPopulatedByteLength()
(package private) int
getPopulatedLongLength()
(package private) abstract int
getPopulatedShortLength()
private short
getPreviousVersionIndex(int entryIndex)
private int
getRootEntry(int setNumber)
private int
getRootEntry(int setNumber, boolean insertAsNeeded)
(package private) int
getTopLevelShift()
(package private) int
getVirtualLength()
(package private) abstract long
incrementAndGetAtUnpackedIndex(int index)
(package private) void
init(int virtualLength)
(package private) boolean
isPacked()
(package private) abstract void
lazySetAtLongIndex(int longIndex, long newValue)
(package private) abstract void
lazysetAtUnpackedIndex(int index, long newValue)
private java.lang.String
leafEntryToString(int entryIndex, int indentLevel)
(package private) abstract int
length()
private int
newEntry(int entryLengthInShorts)
private int
newLeafEntry()
private java.lang.String
nonLeafEntryToString(int entryIndex, int indexShift, int indentLevel)
(package private) java.lang.Iterable<IterationValue>
nonZeroValues()
An Iterator over all non-Zero values in the array(package private) void
populateEquivalentEntriesWithZerosFromOther(AbstractPackedArrayContext other)
private java.lang.String
recordedValuesToString()
(package private) abstract void
resizeArray(int newLength)
private int
seekToPopulatedVirtualIndexStartingAtLevel(int startingVirtualIndex, int levelEntryIndex, int indexShift)
(package private) void
setAtByteIndex(int byteIndex, byte value)
(package private) void
setAtShortIndex(int shortIndex, short value)
(package private) abstract void
setAtUnpackedIndex(int index, long newValue)
private void
setIndexAtEntrySlot(int entryIndex, int slot, short newIndexValue)
private void
setPackedSlotIndicators(int entryIndex, short newPackedSlotIndicators)
private void
setPreviousVersionIndex(int entryIndex, short newPreviosVersionIndex)
private void
setTopLevelShift(int topLevelShift)
(package private) void
setValuePart(int longIndex, long valuePartAsLong, long valuePartMask, int valuePartShift)
(package private) void
setVirtualLength(int virtualLength)
java.lang.String
toString()
(package private) abstract java.lang.String
unpackedToString()
-
-
-
Field Detail
-
PACKED_ARRAY_GROWTH_INCREMENT
private static final int PACKED_ARRAY_GROWTH_INCREMENT
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.- See Also:
- Constant Field Values
-
PACKED_ARRAY_GROWTH_FRACTION_POW2
private static final int PACKED_ARRAY_GROWTH_FRACTION_POW2
- See Also:
- Constant Field Values
-
SET_0_START_INDEX
private static final int SET_0_START_INDEX
- See Also:
- Constant Field Values
-
NUMBER_OF_SETS
private static final int NUMBER_OF_SETS
- See Also:
- Constant Field Values
-
LEAF_LEVEL_SHIFT
private static final int LEAF_LEVEL_SHIFT
- See Also:
- Constant Field Values
-
NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
private static final int NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
- See Also:
- Constant Field Values
-
NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET
private static final int NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET
- See Also:
- Constant Field Values
-
NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET
private static final int NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET
- See Also:
- Constant Field Values
-
MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
static final int MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
- See Also:
- Constant Field Values
-
MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH
static final int MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH
- See Also:
- Constant Field Values
-
isPacked
private final boolean isPacked
-
physicalLength
private int physicalLength
-
virtualLength
private int virtualLength
-
topLevelShift
private int topLevelShift
-
-
Method Detail
-
init
void init(int virtualLength)
-
length
abstract int length()
-
getPopulatedShortLength
abstract int getPopulatedShortLength()
-
casPopulatedShortLength
abstract boolean casPopulatedShortLength(int expectedPopulatedShortLength, int newPopulatedShortLength)
-
casPopulatedLongLength
abstract boolean casPopulatedLongLength(int expectedPopulatedShortLength, int newPopulatedShortLength)
-
getAtLongIndex
abstract long getAtLongIndex(int longIndex)
-
casAtLongIndex
abstract boolean casAtLongIndex(int longIndex, long expectedValue, long newValue)
-
lazySetAtLongIndex
abstract void lazySetAtLongIndex(int longIndex, long newValue)
-
clearContents
abstract void clearContents()
-
resizeArray
abstract void resizeArray(int newLength)
-
getAtUnpackedIndex
abstract long getAtUnpackedIndex(int index)
-
setAtUnpackedIndex
abstract void setAtUnpackedIndex(int index, long newValue)
-
lazysetAtUnpackedIndex
abstract void lazysetAtUnpackedIndex(int index, long newValue)
-
incrementAndGetAtUnpackedIndex
abstract long incrementAndGetAtUnpackedIndex(int index)
-
addAndGetAtUnpackedIndex
abstract long addAndGetAtUnpackedIndex(int index, long valueToAdd)
-
unpackedToString
abstract java.lang.String unpackedToString()
-
setValuePart
void setValuePart(int longIndex, long valuePartAsLong, long valuePartMask, int valuePartShift)
-
getAtShortIndex
short getAtShortIndex(int shortIndex)
-
getIndexAtShortIndex
short getIndexAtShortIndex(int shortIndex)
-
setAtShortIndex
void setAtShortIndex(int shortIndex, short value)
-
casAtShortIndex
boolean casAtShortIndex(int shortIndex, short expectedValue, short newValue)
-
getAtByteIndex
byte getAtByteIndex(int byteIndex)
-
setAtByteIndex
void setAtByteIndex(int byteIndex, byte value)
-
addAtByteIndex
long addAtByteIndex(int byteIndex, byte valueToAdd)
add a byte value to a current byte value in the array- Parameters:
byteIndex
- index of byte value to add tovalueToAdd
- byte value to add- Returns:
- the afterAddValue. ((afterAddValue & 0x100) != 0) indicates a carry.
-
getPackedSlotIndicators
private int getPackedSlotIndicators(int entryIndex)
-
setPackedSlotIndicators
private void setPackedSlotIndicators(int entryIndex, short newPackedSlotIndicators)
-
getPreviousVersionIndex
private short getPreviousVersionIndex(int entryIndex)
-
setPreviousVersionIndex
private void setPreviousVersionIndex(int entryIndex, short newPreviosVersionIndex)
-
getIndexAtEntrySlot
private short getIndexAtEntrySlot(int entryIndex, int slot)
-
setIndexAtEntrySlot
private void setIndexAtEntrySlot(int entryIndex, int slot, short newIndexValue)
-
casIndexAtEntrySlot
private boolean casIndexAtEntrySlot(int entryIndex, int slot, short expectedIndexValue, short newIndexValue)
-
casIndexAtEntrySlotIfNonZeroAndLessThan
private boolean casIndexAtEntrySlotIfNonZeroAndLessThan(int entryIndex, int slot, short newIndexValue)
-
expandArrayIfNeeded
private void expandArrayIfNeeded(int entryLengthInLongs) throws ResizeException
- Throws:
ResizeException
-
newEntry
private int newEntry(int entryLengthInShorts) throws ResizeException
- Throws:
ResizeException
-
newLeafEntry
private int newLeafEntry() throws ResizeException
- Throws:
ResizeException
-
consolidateEntry
private void consolidateEntry(int entryIndex)
Consolidate entry with previous entry verison if one exists- Parameters:
entryIndex
- The shortIndex of the entry to be consolidated
-
expandEntry
private int expandEntry(int existingEntryIndex, int entryPointerIndex, int insertedSlotIndex, int insertedSlotMask, boolean nextLevelIsLeaf) throws AbstractPackedArrayContext.RetryException, ResizeException
Expand entry as indicated.- Parameters:
existingEntryIndex
- the index of the entryentryPointerIndex
- index to the slot pointing to the entry (needs to be fixed up)insertedSlotIndex
- realtive [packed] index of slot being inserted into entryinsertedSlotMask
- mask value fo slot being insertednextLevelIsLeaf
- the level below this one is a leaf level- Returns:
- the updated index of the entry (-1 if epansion failed due to conflict)
- Throws:
AbstractPackedArrayContext.RetryException
- if expansion fails due to concurrent conflict, and caller should try again.ResizeException
-
getRootEntry
private int getRootEntry(int setNumber)
-
getRootEntry
private int getRootEntry(int setNumber, boolean insertAsNeeded) throws AbstractPackedArrayContext.RetryException, ResizeException
-
getPackedIndex
int getPackedIndex(int setNumber, int virtualIndex, boolean insertAsNeeded) throws ResizeException
Get the byte-index (into the packed array) corresponding to a given (set tree) value byte of given virtual index. Inserts new set tree nodes as needed if indicated.- Parameters:
setNumber
- The set tree number (0-7, 0 corresponding with the LSByte set tree)virtualIndex
- The virtual index into the PackedArrayinsertAsNeeded
- If true, will insert new set tree nodes as needed if they do not already exist- Returns:
- the byte-index corresponding to the given (set tree) value byte of the given virtual index
- Throws:
ResizeException
-
contextLocalGetValueAtIndex
private long contextLocalGetValueAtIndex(int virtualIndex)
-
populateEquivalentEntriesWithZerosFromOther
void populateEquivalentEntriesWithZerosFromOther(AbstractPackedArrayContext other)
-
copyEntriesAtLevelFromOther
private void copyEntriesAtLevelFromOther(AbstractPackedArrayContext other, int otherLevelEntryIndex, int levelEntryIndexPointer, int otherIndexShift)
-
seekToPopulatedVirtualIndexStartingAtLevel
private int seekToPopulatedVirtualIndexStartingAtLevel(int startingVirtualIndex, int levelEntryIndex, int indexShift) throws AbstractPackedArrayContext.RetryException
-
findFirstPotentiallyPopulatedVirtualIndexStartingAt
private int findFirstPotentiallyPopulatedVirtualIndexStartingAt(int startingVirtualIndex)
-
nonZeroValues
java.lang.Iterable<IterationValue> nonZeroValues()
An Iterator over all non-Zero values in the array- Returns:
- an Iterator over all non-Zero values in the array
-
isPacked
boolean isPacked()
-
getPhysicalLength
int getPhysicalLength()
-
getVirtualLength
int getVirtualLength()
-
determineTopLevelShiftForVirtualLength
int determineTopLevelShiftForVirtualLength(int virtualLength)
-
setVirtualLength
void setVirtualLength(int virtualLength)
-
getTopLevelShift
int getTopLevelShift()
-
setTopLevelShift
private void setTopLevelShift(int topLevelShift)
-
getPopulatedLongLength
int getPopulatedLongLength()
-
getPopulatedByteLength
int getPopulatedByteLength()
-
nonLeafEntryToString
private java.lang.String nonLeafEntryToString(int entryIndex, int indexShift, int indentLevel)
-
leafEntryToString
private java.lang.String leafEntryToString(int entryIndex, int indentLevel)
-
recordedValuesToString
private java.lang.String recordedValuesToString()
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-