Package org.HdrHistogram.packedarray

Class AbstractPackedArrayContext

java.lang.Object
org.HdrHistogram.packedarray.AbstractPackedArrayContext
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
PackedArrayContext
abstract class AbstractPackedArrayContext extends Object implements 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 of 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. The getPackedIndex(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 successful getPackedIndex(int, int, boolean) may require a resizing of the array, it can throw a ResizeException to indicate that the requested packed index cannot be found or added without a resize of the physical storage.

  • Field Details

    • PACKED_ARRAY_GROWTH_INCREMENT

      private static final int PACKED_ARRAY_GROWTH_INCREMENT
      See Also:

    • PACKED_ARRAY_GROWTH_FRACTION_POW2

      private static final int PACKED_ARRAY_GROWTH_FRACTION_POW2
      See Also:

    • SET_0_START_INDEX

      private static final int SET_0_START_INDEX
      See Also:

    • NUMBER_OF_SETS

      private static final int NUMBER_OF_SETS
      See Also:

    • LEAF_LEVEL_SHIFT

      private static final int LEAF_LEVEL_SHIFT
      See Also:

    • NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS

      private static final int NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS
      See Also:

    • NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET

      private static final int NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET
      See Also:

    • NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET

      private static final int NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET
      See Also:

    • MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY

      static final int MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY
      See Also:

    • MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH

      static final int MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH
      See Also:

    • isPacked

      private final boolean isPacked

    • physicalLength

      private int physicalLength

    • virtualLength

      private int virtualLength

    • topLevelShift

      private int topLevelShift

  • Constructor Details

    • AbstractPackedArrayContext

      AbstractPackedArrayContext(int virtualLength, int initialPhysicalLength)

  • Method Details

    • 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 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 to
      valueToAdd - byte value to add
      Returns:
      the afterAddValue. ((afterAddValue invalid input: '&' 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 newPreviousVersionIndex)

    • 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 version 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 entry
      entryPointerIndex - index to the slot pointing to the entry (needs to be fixed up)
      insertedSlotIndex - relative [packed] index of slot being inserted into entry
      insertedSlotMask - mask value fo slot being inserted
      nextLevelIsLeaf - the level below this one is a leaf level
      Returns:
      the updated index of the entry (-1 if expansion 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
      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 PackedArray
      insertAsNeeded - 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
      Throws:
      AbstractPackedArrayContext.RetryException

    • findFirstPotentiallyPopulatedVirtualIndexStartingAt

      private int findFirstPotentiallyPopulatedVirtualIndexStartingAt(int startingVirtualIndex)

    • nonZeroValues

      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 String nonLeafEntryToString(int entryIndex, int indexShift, int indentLevel)

    • leafEntryToString

      private String leafEntryToString(int entryIndex, int indentLevel)

    • recordedValuesToString

      private String recordedValuesToString()

    • toString

      public String toString()
      Overrides:
      toString in class Object