AbstractPackedArrayContext.java

package org.HdrHistogram.packedarray;

import java.io.Serializable;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A packed-value, sparse array context used for storing 64 bit signed values.
 * <p>
 * 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.
 * <p>
 * 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 {@link #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 {@link #getPackedIndex(int, int, boolean)} may require a
 * resizing of the array, it can throw a {@link ResizeException} to indicate that the requested packed index cannot be
 * found or added without a resize of the physical storage.
 */
abstract class AbstractPackedArrayContext implements Serializable {
    /*
     *
     * 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 various 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 endianness of the underlying architecture]
     *
     * 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 there 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 Entries: 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 shortword 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 described in terms of this C-style struct:
     *
     * struct nonLeafEntry {
     *     short packedSlotIndicators;
     *     short previousVersionIndex;
     *     short[] entrySlotsIndexes;
     * }
     *
     * 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 entrySlots 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 entrySlotsIndexes[]
     * 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 entrySlotsIndexes[] array is ever initialized to a zero value. Zero values in
     *   entrySlotsIndexes[] can only appear through consolidation (see below). Once an entrySlotsIndexes[]
     *   slot is observed to contain a zero, it cannot change to a non-zero value.
     *
     * - Zero values encountered in entrySlotsIndexes[] 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 operation 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 entrySlotsIndexes array. The expansion of an entry in order to add a new
     *   next-level entry under follows the following steps:
     *
     *      - Allocate a new and larger entry structure (initializes all slots to -1)
     *
     *      - Populate the newly inserted slot with an index to a newly allocated next-level entry
     *
     *      - Link the newly expanded entry to the previous entry structure via the previousVersionIndex field
     *
     *      - Publish 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 not 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 entry, copy that index to the new associated
     *        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.
     */

    private static final int PACKED_ARRAY_GROWTH_INCREMENT = 16;
    private static final int PACKED_ARRAY_GROWTH_FRACTION_POW2 = 4;
    private static final int SET_0_START_INDEX = 0;
    private static final int NUMBER_OF_SETS = 8;
    private static final int LEAF_LEVEL_SHIFT = 3;
    private static final int NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS = 2;
    private static final int NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET = 0;
    private static final int NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET = 1;

    static final int MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY = 16;
    static final int MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH = (Short.MAX_VALUE / 4);

    private final boolean isPacked;
    private int physicalLength;
    private int virtualLength = 0;
    private int topLevelShift = Integer.MAX_VALUE; // Make it nonsensical until properly initialized.

    AbstractPackedArrayContext(final int virtualLength, final int initialPhysicalLength) {
        physicalLength = Math.max(initialPhysicalLength, MINIMUM_INITIAL_PACKED_ARRAY_CAPACITY);
        isPacked = (physicalLength <= AbstractPackedArrayContext.MAX_SUPPORTED_PACKED_COUNTS_ARRAY_LENGTH);
        if (!isPacked) {
            physicalLength = virtualLength;
        }
    }

    void init(final int virtualLength) {
        if (!isPacked()) {
            // Deal with non-packed context init:
            this.virtualLength = virtualLength;
            return;
        }
        // room for the 8 shorts root indexes:
        boolean success;
        do {
            success = casPopulatedShortLength(getPopulatedShortLength(), SET_0_START_INDEX + 8);
        } while (!success);

        // Populate empty root entries, and point to them from the root indexes:
        for (int i = 0; i < NUMBER_OF_SETS; i++) {
            setAtShortIndex(SET_0_START_INDEX + i, (short) 0);
        }
        setVirtualLength(virtualLength);
    }

    //
    //     ###    ########   ######  ######## ########     ###     ######  ########  ######
    //    ## ##   ##     ## ##    ##    ##    ##     ##   ## ##   ##    ##    ##    ##    ##
    //   ##   ##  ##     ## ##          ##    ##     ##  ##   ##  ##          ##    ##
    //  ##     ## ########   ######     ##    ########  ##     ## ##          ##     ######
    //  ######### ##     ##       ##    ##    ##   ##   ######### ##          ##          ##
    //  ##     ## ##     ## ##    ##    ##    ##    ##  ##     ## ##    ##    ##    ##    ##
    //  ##     ## ########   ######     ##    ##     ## ##     ##  ######     ##     ######
    //


    abstract int length();

    abstract int getPopulatedShortLength();

    abstract boolean casPopulatedShortLength(int expectedPopulatedShortLength, int newPopulatedShortLength);

    abstract boolean casPopulatedLongLength(int expectedPopulatedShortLength, int newPopulatedShortLength);

    abstract long getAtLongIndex(int longIndex);

    abstract boolean casAtLongIndex(int longIndex, long expectedValue, long newValue);

    abstract void lazySetAtLongIndex(int longIndex, long newValue);

    abstract void clearContents();

    abstract void resizeArray(int newLength);

    abstract long getAtUnpackedIndex(int index);

    abstract void setAtUnpackedIndex(int index, long newValue);

    abstract void lazySetAtUnpackedIndex(int index, long newValue);

    abstract long incrementAndGetAtUnpackedIndex(int index);

    abstract long addAndGetAtUnpackedIndex(int index, long valueToAdd);

    abstract String unpackedToString();

    //
    //  ########  ########  #### ##     ## #### ######## #### ##     ## ########     #######  ########   ######
    //  ##     ## ##     ##  ##  ###   ###  ##     ##     ##  ##     ## ##          ##     ## ##     ## ##    ##
    //  ##     ## ##     ##  ##  #### ####  ##     ##     ##  ##     ## ##          ##     ## ##     ## ##
    //  ########  ########   ##  ## ### ##  ##     ##     ##  ##     ## ######      ##     ## ########   ######
    //  ##        ##   ##    ##  ##     ##  ##     ##     ##   ##   ##  ##          ##     ## ##              ##
    //  ##        ##    ##   ##  ##     ##  ##     ##     ##    ## ##   ##          ##     ## ##        ##    ##
    //  ##        ##     ## #### ##     ## ####    ##    ####    ###    ########     #######  ##         ######
    //

    void setValuePart(final int longIndex,
                      final long valuePartAsLong,
                      final long valuePartMask,
                      final int valuePartShift) {
        boolean success;
        do {
            long currentLongValue = getAtLongIndex(longIndex);
            long newLongValue = (currentLongValue & ~valuePartMask) | (valuePartAsLong << valuePartShift);
            success = casAtLongIndex(longIndex, currentLongValue, newLongValue);
        }
        while (!success);
    }

    short getAtShortIndex(final int shortIndex) {
        return (short) ((getAtLongIndex(shortIndex >> 2) >> ((shortIndex & 0x3) << 4)) & 0xffff);
    }

    short getIndexAtShortIndex(final int shortIndex) {
        return (short) ((getAtLongIndex(shortIndex >> 2) >> ((shortIndex & 0x3) << 4)) & 0x7fff);
    }

    void setAtShortIndex(final int shortIndex, final short value) {
        int longIndex = shortIndex >> 2;
        int shortShift = (shortIndex & 0x3) << 4;
        long shortMask = ((long) 0xffff) << shortShift;
        long shortValueAsLong = ((long) value) & 0xffff;
        setValuePart(longIndex, shortValueAsLong, shortMask, shortShift);
    }

    boolean casAtShortIndex(final int shortIndex, final short expectedValue, final short newValue) {
        int longIndex = shortIndex >> 2;
        int shortShift = (shortIndex & 0x3) << 4;
        long shortMask = ~(((long) 0xffff) << shortShift);
        long newShortValueAsLong = ((long) newValue) & 0xffff;
        long expectedShortValueAsLong = ((long) expectedValue) & 0xffff;
        boolean success;
        do {
            long currentLongValue = getAtLongIndex(longIndex);
            long currentShortValueAsLong = (currentLongValue >> shortShift) & 0xffff;
            if (currentShortValueAsLong != expectedShortValueAsLong) {
                return false;
            }
            long newLongValue = (currentLongValue & shortMask) | (newShortValueAsLong << shortShift);
            success = casAtLongIndex(longIndex, currentLongValue, newLongValue);
        }
        while (!success);
        return true;
    }

    byte getAtByteIndex(final int byteIndex) {
        return (byte) ((getAtLongIndex(byteIndex >> 3) >> ((byteIndex & 0x7) << 3)) & 0xff);
    }

    void setAtByteIndex(final int byteIndex, final byte value) {
        int longIndex = byteIndex >> 3;
        int byteShift = (byteIndex & 0x7) << 3;
        long byteMask = ((long) 0xff) << byteShift;
        long byteValueAsLong = ((long) value) & 0xff;
        setValuePart(longIndex, byteValueAsLong, byteMask, byteShift);
    }

    /**
     * add a byte value to a current byte value in the array
     *
     * @param byteIndex  index of byte value to add to
     * @param valueToAdd byte value to add
     * @return the afterAddValue. ((afterAddValue & 0x100) != 0) indicates a carry.
     */
    long addAtByteIndex(final int byteIndex, final byte valueToAdd) {
        int longIndex = byteIndex >> 3;
        int byteShift = (byteIndex & 0x7) << 3;
        long byteMask = ((long) 0xff) << byteShift;
        boolean success;
        long newValue;
        do {
            long currentLongValue = getAtLongIndex(longIndex);
            long byteValueAsLong = (currentLongValue >> byteShift) & 0xff;
            newValue = byteValueAsLong + (((long) valueToAdd) & 0xff);
            long newByteValueAsLong = newValue & 0xff;
            long newLongValue = (currentLongValue & ~byteMask) | (newByteValueAsLong << byteShift);
            success = casAtLongIndex(longIndex, currentLongValue, newLongValue);
        }
        while (!success);
        return newValue;
    }

    //
    //  ######## ##    ## ######## ########  ##    ##    ######## #### ######## ##       ########   ######
    //  ##       ###   ##    ##    ##     ##  ##  ##     ##        ##  ##       ##       ##     ## ##    ##
    //  ##       ####  ##    ##    ##     ##   ####      ##        ##  ##       ##       ##     ## ##
    //  ######   ## ## ##    ##    ########     ##       ######    ##  ######   ##       ##     ##  ######
    //  ##       ##  ####    ##    ##   ##      ##       ##        ##  ##       ##       ##     ##       ##
    //  ##       ##   ###    ##    ##    ##     ##       ##        ##  ##       ##       ##     ## ##    ##
    //  ######## ##    ##    ##    ##     ##    ##       ##       #### ######## ######## ########   ######
    //

    private int getPackedSlotIndicators(final int entryIndex) {
        return ((int) getAtShortIndex(entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET)) & 0xffff;
    }

    private void setPackedSlotIndicators(final int entryIndex, final short newPackedSlotIndicators) {
        setAtShortIndex(entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET, newPackedSlotIndicators);
    }

    private short getPreviousVersionIndex(final int entryIndex) {
        return getAtShortIndex(entryIndex + NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET);
    }

    private void setPreviousVersionIndex(final int entryIndex, final short newPreviousVersionIndex) {
        setAtShortIndex(entryIndex + NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET, newPreviousVersionIndex);
    }

    private short getIndexAtEntrySlot(final int entryIndex, final int slot) {
        return getAtShortIndex(entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot);
    }

    private void setIndexAtEntrySlot(final int entryIndex, final int slot, final short newIndexValue) {
        setAtShortIndex(entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot, newIndexValue);
    }

    private boolean casIndexAtEntrySlot(final int entryIndex,
                                        final int slot,
                                        final short expectedIndexValue,
                                        final short newIndexValue) {
        return casAtShortIndex(entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slot,
                expectedIndexValue, newIndexValue);
    }

    private boolean casIndexAtEntrySlotIfNonZeroAndLessThan(final int entryIndex,
                                                            final int slot,
                                                            final short newIndexValue) {
        boolean success;
        do {
            short existingIndexValue = getIndexAtEntrySlot(entryIndex, slot);
            if (existingIndexValue == 0) return false;
            if (newIndexValue <= existingIndexValue) return false;
            success = casIndexAtEntrySlot(entryIndex, slot, existingIndexValue, newIndexValue);
        } while (!success);
        return true;
    }

    //
    //  ######## ##    ## ######## ########  ##    ##     #######  ########   ######
    //  ##       ###   ##    ##    ##     ##  ##  ##     ##     ## ##     ## ##    ##
    //  ##       ####  ##    ##    ##     ##   ####      ##     ## ##     ## ##
    //  ######   ## ## ##    ##    ########     ##       ##     ## ########   ######
    //  ##       ##  ####    ##    ##   ##      ##       ##     ## ##              ##
    //  ##       ##   ###    ##    ##    ##     ##       ##     ## ##        ##    ##
    //  ######## ##    ##    ##    ##     ##    ##        #######  ##         ######
    //

    private void expandArrayIfNeeded(final int entryLengthInLongs) throws ResizeException {
        final int currentLength = length();
        if (length() < getPopulatedLongLength() + entryLengthInLongs) {
            int growthIncrement = Math.max(entryLengthInLongs, PACKED_ARRAY_GROWTH_INCREMENT);
            growthIncrement = Math.max(growthIncrement, getPopulatedLongLength() >> PACKED_ARRAY_GROWTH_FRACTION_POW2);
            throw new ResizeException(currentLength + growthIncrement);
        }
    }

    private int newEntry(final int entryLengthInShorts) throws ResizeException {
        // Add entry at the end of the array:
        int newEntryIndex;
        boolean success;
        do {
            newEntryIndex = getPopulatedShortLength();
            expandArrayIfNeeded((entryLengthInShorts >> 2) + 1);
            success = casPopulatedShortLength(newEntryIndex, (newEntryIndex + entryLengthInShorts));
        } while (!success);

        for (int i = 0; i < entryLengthInShorts; i++) {
            setAtShortIndex(newEntryIndex + i, (short) -1); // Poison value -1. Must be overridden before read
        }
        return newEntryIndex;
    }

    private int newLeafEntry() throws ResizeException {
        // Add entry at the end of the array:
        int newEntryIndex;
        boolean success;
        do {
            newEntryIndex = getPopulatedLongLength();
            expandArrayIfNeeded(1);
            success = casPopulatedLongLength(newEntryIndex, (newEntryIndex + 1));
        } while (!success);

        lazySetAtLongIndex(newEntryIndex, 0);
        return newEntryIndex;
    }

    /**
     * Consolidate entry with previous entry version if one exists
     *
     * @param entryIndex The shortIndex of the entry to be consolidated
     */
    private void consolidateEntry(final int entryIndex) {
        int previousVersionIndex = getPreviousVersionIndex(entryIndex);
        if (previousVersionIndex == 0) return;
        if (getPreviousVersionIndex(previousVersionIndex) != 0) {
            throw new IllegalStateException("Encountered Previous Version Entry that is not itself consolidated.");
        }

        int previousVersionPackedSlotsIndicators = getPackedSlotIndicators(previousVersionIndex);
        // Previous version exists, needs consolidation

        int packedSlotsIndicators = getPackedSlotIndicators(entryIndex);
        int insertedSlotMask = packedSlotsIndicators ^ previousVersionPackedSlotsIndicators; // only bit that differs
        int slotsBelowBitNumber = packedSlotsIndicators & (insertedSlotMask - 1);
        int insertedSlotIndex = Integer.bitCount(slotsBelowBitNumber);
        int numberOfSlotsInEntry = Integer.bitCount(packedSlotsIndicators);

        // Copy the entry slots from previous version, skipping the newly inserted slot in the target:
        int sourceSlot = 0;
        for (int targetSlot = 0; targetSlot < numberOfSlotsInEntry; targetSlot++) {
            if (targetSlot != insertedSlotIndex) {
                boolean success = true;
                do {
                    short indexAtSlot = getIndexAtEntrySlot(previousVersionIndex, sourceSlot);
                    if (indexAtSlot != 0) {
                        // Copy observed index at slot to current entry
                        // (only copy value in if previous value is less than new one AND is non-zero)
                        casIndexAtEntrySlotIfNonZeroAndLessThan(entryIndex, targetSlot, indexAtSlot);

                        // CAS the previous version slot to 0.
                        // (Succeeds only if the index in that slot has not changed. Retry if it did).
                        success = casIndexAtEntrySlot(previousVersionIndex, sourceSlot, indexAtSlot, (short) 0);
                    }
                }
                while (!success);
                sourceSlot++;
            }
        }

        setPreviousVersionIndex(entryIndex, (short) 0);
    }

    /**
     * Expand entry as indicated.
     *
     * @param existingEntryIndex the index of the entry
     * @param entryPointerIndex  index to the slot pointing to the entry (needs to be fixed up)
     * @param insertedSlotIndex  relative [packed] index of slot being inserted into entry
     * @param insertedSlotMask   mask value fo slot being inserted
     * @param nextLevelIsLeaf    the level below this one is a leaf level
     * @return the updated index of the entry (-1 if expansion failed due to conflict)
     * @throws RetryException if expansion fails due to concurrent conflict, and caller should try again.
     */
    private int expandEntry(final int existingEntryIndex,
                            final int entryPointerIndex,
                            final int insertedSlotIndex,
                            final int insertedSlotMask,
                            final boolean nextLevelIsLeaf) throws RetryException, ResizeException {
        int packedSlotIndicators = ((int) getAtShortIndex(existingEntryIndex)) & 0xffff;
        packedSlotIndicators |= insertedSlotMask;
        int numberOfSlotsInExpandedEntry = Integer.bitCount(packedSlotIndicators);
        if (insertedSlotIndex >= numberOfSlotsInExpandedEntry) {
            throw new IllegalStateException("inserted slot index is out of range given provided masks");
        }
        int expandedEntryLength = numberOfSlotsInExpandedEntry + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS;

        // Create new next-level entry to refer to from slot at this level:
        int indexOfNewNextLevelEntry = 0;
        if (nextLevelIsLeaf) {
            indexOfNewNextLevelEntry = newLeafEntry(); // Establish long-index to new leaf entry
        } else {
            // TODO: Optimize this by creating the whole sub-tree here, rather than a step that will immediately expand
            // Create a new 1 word (empty, no slots set) entry for the next level:
            indexOfNewNextLevelEntry = newEntry(NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS); // Establish index to new entry
            setPackedSlotIndicators(indexOfNewNextLevelEntry, (short) 0);
            setPreviousVersionIndex(indexOfNewNextLevelEntry, (short) 0);
        }
        short insertedSlotValue = (short) indexOfNewNextLevelEntry;

        int expandedEntryIndex = newEntry(expandedEntryLength);

        // populate the packed indicators word:
        setPackedSlotIndicators(expandedEntryIndex, (short) packedSlotIndicators);
        setPreviousVersionIndex(expandedEntryIndex, (short) existingEntryIndex);

        // Populate the inserted slot with the index of the new next level entry:
        setIndexAtEntrySlot(expandedEntryIndex, insertedSlotIndex, insertedSlotValue);

        // Copy of previous version entries is deferred to later consolidateEntry() call.

        // Set the pointer to the updated entry index. If CAS fails, discard by throwing retry exception.
        boolean success = casAtShortIndex(entryPointerIndex, (short) existingEntryIndex, (short) expandedEntryIndex);
        if (!success) {
            throw new RetryException();
        }

        // Expanded entry is published, now consolidate it:

        consolidateEntry(expandedEntryIndex);

        return expandedEntryIndex;

    }


    //
    //   ######   ######## ########    ##     ##    ###    ##             ## #### ##    ## ########  ######## ##     ##
    //  ##    ##  ##          ##       ##     ##   ## ##   ##            ##   ##  ###   ## ##     ## ##        ##   ##
    //  ##        ##          ##       ##     ##  ##   ##  ##           ##    ##  ####  ## ##     ## ##         ## ##
    //  ##   #### ######      ##       ##     ## ##     ## ##          ##     ##  ## ## ## ##     ## ######      ###
    //  ##    ##  ##          ##        ##   ##  ######### ##         ##      ##  ##  #### ##     ## ##         ## ##
    //  ##    ##  ##          ##         ## ##   ##     ## ##        ##       ##  ##   ### ##     ## ##        ##   ##
    //   ######   ########    ##          ###    ##     ## ######## ##       #### ##    ## ########  ######## ##     ##
    //


    private int getRootEntry(final int setNumber) {
        try {
            return getRootEntry(setNumber, false);
        } catch (RetryException | ResizeException ex) {
            throw new IllegalStateException("Should not Resize or Retry exceptions on real-only read: ", ex);
        }

    }

    private int getRootEntry(final int setNumber, boolean insertAsNeeded) throws RetryException, ResizeException {
        int entryPointerIndex = SET_0_START_INDEX + setNumber;
        int entryIndex = getIndexAtShortIndex(entryPointerIndex);

        if (entryIndex == 0) {
            if (!insertAsNeeded) {
                return 0; // Index does not currently exist in packed array;
            }

            entryIndex = newEntry(NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS);
            // Create a new empty (no slots set) entry for the next level:
            setPackedSlotIndicators(entryIndex, (short) 0);
            setPreviousVersionIndex(entryIndex, (short) 0);

            boolean success = casAtShortIndex(entryPointerIndex, (short) 0, (short) entryIndex);
            if (!success) {
                throw new RetryException();
            }
        }

        if (((getTopLevelShift() != LEAF_LEVEL_SHIFT)) && getPreviousVersionIndex(entryIndex) != 0) {
            consolidateEntry(entryIndex);
        }
        return entryIndex;
    }

    /**
     * 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.
     *
     * @param setNumber      The set tree number (0-7, 0 corresponding with the LSByte set tree)
     * @param virtualIndex   The virtual index into the PackedArray
     * @param insertAsNeeded If true, will insert new set tree nodes as needed if they do not already exist
     * @return the byte-index corresponding to the given (set tree) value byte of the given virtual index
     */
    int getPackedIndex(final int setNumber, final int virtualIndex, final boolean insertAsNeeded)
            throws ResizeException {
        int byteIndex = 0; // Must be overwritten to finish. Will retry until non-zero.
        do {
            try {
                assert (setNumber >= 0 && setNumber < NUMBER_OF_SETS);
                if (virtualIndex >= getVirtualLength()) {
                    throw new ArrayIndexOutOfBoundsException(
                            String.format("Attempting access at index %d, beyond virtualLength %d",
                                    virtualIndex, getVirtualLength()));
                }
                int entryPointerIndex = SET_0_START_INDEX + setNumber;
                int entryIndex = getRootEntry(setNumber, insertAsNeeded);
                if (entryIndex == 0) {
                    return -1; // Index does not currently exist in packed array;
                }

                // Work down the levels of non-leaf entries:
                for (int indexShift = getTopLevelShift(); indexShift >= LEAF_LEVEL_SHIFT; indexShift -= 4) {
                    boolean nextLevelIsLeaf = (indexShift == LEAF_LEVEL_SHIFT);
                    // Target is a packedSlotIndicators entry
                    int packedSlotIndicators = getPackedSlotIndicators(entryIndex);
                    int slotBitNumber = (virtualIndex >>> indexShift) & 0xf;
                    int slotMask = 1 << slotBitNumber;
                    int slotsBelowBitNumber = packedSlotIndicators & (slotMask - 1);
                    int slotNumber = Integer.bitCount(slotsBelowBitNumber);

                    if ((packedSlotIndicators & slotMask) == 0) {
                        // The entryIndex slot does not have the contents we want
                        if (!insertAsNeeded) {
                            return -1; // Index does not currently exist in packed array;
                        }

                        // Expand the entry, adding the index to new entry at the proper slot:
                        entryIndex = expandEntry(entryIndex, entryPointerIndex, slotNumber, slotMask, nextLevelIsLeaf);
                    }

                    // Next level's entry pointer index is in the appropriate slot in the entries array in this entry:
                    entryPointerIndex = entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + slotNumber;

                    entryIndex = getIndexAtShortIndex(entryPointerIndex);
                    if (entryIndex == 0) {
                        throw new RetryException();
                    }
                    if ((!nextLevelIsLeaf) && getPreviousVersionIndex(entryIndex) != 0) {
                        consolidateEntry(entryIndex);
                    }

                    // entryIndex is either holds the long-index of a leaf entry, or the shorty-index of the next
                    // level entry's packed slot indicators short-word.
                }

                // entryIndex is the long-index of a leaf entry that contains the value byte for the given set

                byteIndex = (entryIndex << 3) + (virtualIndex & 0x7); // Determine byte index offset within leaf entry

            } catch (RetryException ignored) {
                // Retry will happen automatically since byteIndex was not set to non-zero value;
            }
        }
        while (byteIndex == 0);

        return byteIndex;
    }

    private long contextLocalGetValueAtIndex(final int virtualIndex) {
        long value = 0;
        for (int byteNum = 0; byteNum < NUMBER_OF_SETS; byteNum++) {
            int packedIndex = 0;
            long byteValueAtPackedIndex;
            do {
                try {
                    packedIndex = getPackedIndex(byteNum, virtualIndex, false);
                    if (packedIndex < 0) {
                        return value;
                    }
                    byteValueAtPackedIndex = (((long) getAtByteIndex(packedIndex)) & 0xff) << (byteNum << 3);
                } catch (ResizeException ex) {
                    throw new IllegalStateException("Should never encounter a resize exception without inserts");
                }
            } while (packedIndex == 0);

            value += byteValueAtPackedIndex;
        }
        return value;
    }

    //
    //  ##     ##         ########   #######  ########  ##     ## ##          ###    ######## ########
    //   ##   ##          ##     ## ##     ## ##     ## ##     ## ##         ## ##      ##    ##
    //    ## ##           ##     ## ##     ## ##     ## ##     ## ##        ##   ##     ##    ##
    //     ###    ####### ########  ##     ## ########  ##     ## ##       ##     ##    ##    ######
    //    ## ##           ##        ##     ## ##        ##     ## ##       #########    ##    ##
    //   ##   ##          ##        ##     ## ##        ##     ## ##       ##     ##    ##    ##
    //  ##     ##         ##         #######  ##         #######  ######## ##     ##    ##    ########
    //


    void populateEquivalentEntriesWithZerosFromOther(final AbstractPackedArrayContext other) {
        if (getVirtualLength() < other.getVirtualLength()) {
            throw new IllegalStateException("Cannot populate array of smaller virtual length");
        }
        for (int i = 0; i < NUMBER_OF_SETS; i++) {
            int otherEntryIndex = other.getAtShortIndex(SET_0_START_INDEX + i);
            if (otherEntryIndex == 0) continue; // No tree to duplicate
            int entryIndexPointer = SET_0_START_INDEX + i;
            for (int j = getTopLevelShift(); j > other.getTopLevelShift(); j -= 4) {
                // for each inserted level:

                // Allocate entry in other:
                int sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + 1;
                int newEntryIndex = 0;
                do {
                    try {
                        newEntryIndex = newEntry(sizeOfEntry);
                    } catch (ResizeException ex) {
                        resizeArray(ex.getNewSize());
                    }
                }
                while (newEntryIndex == 0);

                // Link new level in.
                setAtShortIndex(entryIndexPointer, (short) newEntryIndex);
                // Populate new level entry, use pointer to slot 0 as place to populate under:
                setPackedSlotIndicators(newEntryIndex, (short) 0x1); // Slot 0 populated
                setPreviousVersionIndex(newEntryIndex, (short) 0); // No previous version
                entryIndexPointer = newEntryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS; // Where slot 0 index goes.
            }
            copyEntriesAtLevelFromOther(other, otherEntryIndex,
                    entryIndexPointer, other.getTopLevelShift());
        }
    }

    private void copyEntriesAtLevelFromOther(final AbstractPackedArrayContext other,
                                             final int otherLevelEntryIndex,
                                             final int levelEntryIndexPointer,
                                             final int otherIndexShift) {
        boolean nextLevelIsLeaf = (otherIndexShift == LEAF_LEVEL_SHIFT);
        int packedSlotIndicators = other.getPackedSlotIndicators(otherLevelEntryIndex);
        int numberOfSlots = Integer.bitCount(packedSlotIndicators);
        int sizeOfEntry = NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + numberOfSlots;

        // Allocate entry:
        int entryIndex = 0;
        do {
            try {
                entryIndex = newEntry(sizeOfEntry);
            } catch (ResizeException ex) {
                resizeArray(ex.getNewSize());
            }
        }
        while (entryIndex == 0);

        setAtShortIndex(levelEntryIndexPointer, (short) entryIndex);
        setAtShortIndex(entryIndex + NON_LEAF_ENTRY_SLOT_INDICATORS_OFFSET, (short) packedSlotIndicators);
        setAtShortIndex(entryIndex + NON_LEAF_ENTRY_PREVIOUS_VERSION_OFFSET, (short) 0);
        for (int i = 0; i < numberOfSlots; i++) {
            if (nextLevelIsLeaf) {
                // Make leaf in other:
                int leafEntryIndex = 0;
                do {
                    try {
                        leafEntryIndex = newLeafEntry();
                    } catch (ResizeException ex) {
                        resizeArray(ex.getNewSize());
                    }
                }
                while (leafEntryIndex == 0);
                setIndexAtEntrySlot(entryIndex, i, (short) leafEntryIndex);
                lazySetAtLongIndex(leafEntryIndex, 0);
            } else {
                int otherNextLevelEntryIndex = other.getIndexAtEntrySlot(otherLevelEntryIndex, i);
                copyEntriesAtLevelFromOther(other, otherNextLevelEntryIndex,
                        (entryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + i),
                        otherIndexShift - 4);
            }
        }
    }

    //
    //  #### ######## ######## ########     ###    ######## ####  #######  ##    ##
    //   ##     ##    ##       ##     ##   ## ##      ##     ##  ##     ## ###   ##
    //   ##     ##    ##       ##     ##  ##   ##     ##     ##  ##     ## ####  ##
    //   ##     ##    ######   ########  ##     ##    ##     ##  ##     ## ## ## ##
    //   ##     ##    ##       ##   ##   #########    ##     ##  ##     ## ##  ####
    //   ##     ##    ##       ##    ##  ##     ##    ##     ##  ##     ## ##   ###
    //  ####    ##    ######## ##     ## ##     ##    ##    ####  #######  ##    ##
    //

    // Recorded Value iteration:

    private int seekToPopulatedVirtualIndexStartingAtLevel(final int startingVirtualIndex,
                                                           final int levelEntryIndex,
                                                           final int indexShift) throws RetryException {
        int virtualIndex = startingVirtualIndex;
        int firstVirtualIndexPastThisLevel = (((virtualIndex >>> indexShift) | 0xf) + 1) << indexShift;
        boolean nextLevelIsLeaf = (indexShift == LEAF_LEVEL_SHIFT);
        do {
            // Target is a packedSlotIndicators entry
            int packedSlotIndicators = getPackedSlotIndicators(levelEntryIndex);
            int startingSlotBitNumber = (virtualIndex >>> indexShift) & 0xf;
            int slotMask = 1 << startingSlotBitNumber;
            int slotsAtAndAboveBitNumber = packedSlotIndicators & ~(slotMask - 1);
            int nextActiveSlotBitNumber = Integer.numberOfTrailingZeros(slotsAtAndAboveBitNumber);


            if (nextActiveSlotBitNumber > 15) {
                // this level has no more set bits, pop back up a level.
                int indexShiftAbove = indexShift + 4;
                virtualIndex += 1 << indexShiftAbove;
                virtualIndex &= ~((1 << indexShiftAbove) - 1); // Start at the beginning of the next slot a level above.
                return -virtualIndex; // Negative value indicates a skip to a different index.
            }

            // Drill into bit.
            if (nextActiveSlotBitNumber != startingSlotBitNumber) {
                virtualIndex += (nextActiveSlotBitNumber - startingSlotBitNumber) << indexShift;
                virtualIndex &= ~((1 << indexShift) - 1); // Start at the beginning of the next slot of this level
            }

            if (nextLevelIsLeaf) {
                // There is recorded value here. No need to look.
                return virtualIndex;
            }

            // Next level is not a leaf. Drill into it:

            int nextSlotMask = 1 << nextActiveSlotBitNumber;
            int slotsBelowNextBitNumber = packedSlotIndicators & (nextSlotMask - 1);
            int nextSlotNumber = Integer.bitCount(slotsBelowNextBitNumber);

            if ((packedSlotIndicators & nextSlotMask) == 0) {
                throw new IllegalStateException("Unexpected 0 at slot index");
            }

            int entryPointerIndex = levelEntryIndex + NON_LEAF_ENTRY_HEADER_SIZE_IN_SHORTS + nextSlotNumber;
            int nextLevelEntryIndex = getIndexAtShortIndex(entryPointerIndex);
            if (nextLevelEntryIndex == 0) {
                throw new RetryException();
            }
            if (getPreviousVersionIndex(nextLevelEntryIndex) != 0) {
                consolidateEntry(nextLevelEntryIndex);
            }

            virtualIndex =
                    seekToPopulatedVirtualIndexStartingAtLevel(virtualIndex, nextLevelEntryIndex, indexShift - 4);
            if (virtualIndex < 0) {
                virtualIndex = -virtualIndex;
            } else {
                return virtualIndex;
            }
        } while (virtualIndex < firstVirtualIndexPastThisLevel);

        return virtualIndex;
    }

    private int findFirstPotentiallyPopulatedVirtualIndexStartingAt(final int startingVirtualIndex) {
        int nextVirtualIndex = -1;
        // Look for a populated virtual index in set 0:
        boolean retry;
        do {
            retry = false;
            try {
                int entryIndex = getRootEntry(0);
                if (entryIndex == 0) return getVirtualLength(); // Nothing under the root
                nextVirtualIndex =
                        seekToPopulatedVirtualIndexStartingAtLevel(startingVirtualIndex, entryIndex,
                                getTopLevelShift());
            } catch (RetryException ex) {
                retry = true;
            }
        } while (retry);

        // Don't drill to value if out of range:
        if ((nextVirtualIndex < 0) || (nextVirtualIndex >= getVirtualLength())) {
            return getVirtualLength();
        }

        return nextVirtualIndex;
    }

    // Recorded values iteration:

    class NonZeroValuesIterator implements Iterator<IterationValue> {

        int nextVirtualIndex = 0;
        long nextValue;

        final IterationValue currentIterationValue = new IterationValue();

        private void findFirstNonZeroValueVirtualIndexStartingAt(final int startingVirtualIndex) {
            if (!isPacked()) {
                // Look for non-zero value in unpacked context:
                for (nextVirtualIndex = startingVirtualIndex;
                     nextVirtualIndex < getVirtualLength();
                     nextVirtualIndex++) {
                    if ((nextValue = getAtUnpackedIndex(nextVirtualIndex)) != 0) {
                        return;
                    }
                }
                return;
            }
            // Context is packed:
            nextVirtualIndex = startingVirtualIndex;
            do {
                nextVirtualIndex = findFirstPotentiallyPopulatedVirtualIndexStartingAt(nextVirtualIndex);
                if (nextVirtualIndex >= getVirtualLength()) break;
                if ((nextValue = contextLocalGetValueAtIndex(nextVirtualIndex)) != 0) break;
                nextVirtualIndex++;
            } while (true);
        }

        @Override
        public IterationValue next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            currentIterationValue.set(nextVirtualIndex, nextValue);
            findFirstNonZeroValueVirtualIndexStartingAt(nextVirtualIndex + 1);
            return currentIterationValue;
        }

        @Override
        public boolean hasNext() {
            return ((nextVirtualIndex >= 0) &&
                    (nextVirtualIndex < getVirtualLength()));
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        NonZeroValuesIterator() {
            findFirstNonZeroValueVirtualIndexStartingAt(0);
        }
    }

    /**
     * An Iterator over all non-Zero values in the array
     *
     * @return an Iterator over all non-Zero values in the array
     */
    Iterable<IterationValue> nonZeroValues() {
        return new Iterable<IterationValue>() {
            public Iterator<IterationValue> iterator() {
                return new NonZeroValuesIterator();
            }
        };
    }

    //
    //   ######  #### ######## ########      ####        ######  ##     ## #### ######## ########
    //  ##    ##  ##       ##  ##           ##  ##      ##    ## ##     ##  ##  ##          ##
    //  ##        ##      ##   ##            ####       ##       ##     ##  ##  ##          ##
    //   ######   ##     ##    ######       ####         ######  #########  ##  ######      ##
    //        ##  ##    ##     ##          ##  ## ##          ## ##     ##  ##  ##          ##
    //  ##    ##  ##   ##      ##          ##   ##      ##    ## ##     ##  ##  ##          ##
    //   ######  #### ######## ########     ####  ##     ######  ##     ## #### ##          ##
    //

    boolean isPacked() {
        return isPacked;
    }

    int getPhysicalLength() {
        return physicalLength;
    }

    int getVirtualLength() {
        return virtualLength;
    }

    int determineTopLevelShiftForVirtualLength(final int virtualLength) {
        int sizeMagnitude = (int) Math.ceil(Math.log(virtualLength) / Math.log(2));
        int eightsSizeMagnitude = sizeMagnitude - 3;
        int multipleOfFourSizeMagnitude = (int) Math.ceil(eightsSizeMagnitude / 4.0) * 4;
        multipleOfFourSizeMagnitude = Math.max(multipleOfFourSizeMagnitude, 8);
        int topLevelShiftNeeded = (multipleOfFourSizeMagnitude - 4) + 3;
        return topLevelShiftNeeded;
    }

    void setVirtualLength(final int virtualLength) {
        if (!isPacked()) {
            throw new IllegalStateException("Should never be adjusting the virtual size of a non-packed context");
        }
        int newTopLevelShift = determineTopLevelShiftForVirtualLength(virtualLength);
        setTopLevelShift(newTopLevelShift);
        this.virtualLength = virtualLength;
    }

    int getTopLevelShift() {
        return topLevelShift;
    }

    private void setTopLevelShift(final int topLevelShift) {
        this.topLevelShift = topLevelShift;
    }

    int getPopulatedLongLength() {
        return (getPopulatedShortLength() + 3) >> 2; // round up
    }

    int getPopulatedByteLength() {
        return getPopulatedShortLength() << 1;
    }

    //
    //   ########  #######           ######  ######## ########  #### ##    ##  ######
    //      ##    ##     ##         ##    ##    ##    ##     ##  ##  ###   ## ##    ##
    //      ##    ##     ##         ##          ##    ##     ##  ##  ####  ## ##
    //      ##    ##     ## #######  ######     ##    ########   ##  ## ## ## ##   ####
    //      ##    ##     ##               ##    ##    ##   ##    ##  ##  #### ##    ##
    //      ##    ##     ##         ##    ##    ##    ##    ##   ##  ##   ### ##    ##
    //      ##     #######           ######     ##    ##     ## #### ##    ##  ######
    //

    private String nonLeafEntryToString(final int entryIndex,
                                        final int indexShift,
                                        final int indentLevel) {
        String output = "";
        for (int i = 0; i < indentLevel; i++) {
            output += "  ";
        }
        try {
            final int packedSlotIndicators = getPackedSlotIndicators(entryIndex);
            output += String.format("slotIndicators: 0x%02x, prevVersionIndex: %3d: [ ",
                    packedSlotIndicators,
                    getPreviousVersionIndex(entryIndex));
            final int numberOfSlotsInEntry = Integer.bitCount(packedSlotIndicators);
            for (int i = 0; i < numberOfSlotsInEntry; i++) {
                output += String.format("%d", getIndexAtEntrySlot(entryIndex, i));
                if (i < numberOfSlotsInEntry - 1) {
                    output += ", ";
                }
            }
            output += String.format(" ] (indexShift = %d)\n", indexShift);
            final boolean nextLevelIsLeaf = (indexShift == LEAF_LEVEL_SHIFT);
            for (int i = 0; i < numberOfSlotsInEntry; i++) {
                final int nextLevelEntryIndex = getIndexAtEntrySlot(entryIndex, i);
                if (nextLevelIsLeaf) {
                    output += leafEntryToString(nextLevelEntryIndex, indentLevel + 4);
                } else {
                    output += nonLeafEntryToString(nextLevelEntryIndex,
                            indexShift - 4, indentLevel + 4);
                }
            }
        } catch (Exception ex) {
            output += String.format("Exception thrown at nonLeafEntry at index %d with indexShift %d\n",
                    entryIndex, indexShift);
        }
        return output;
    }

    private String leafEntryToString(final int entryIndex, final int indentLevel) {
        String output = "";
        for (int i = 0; i < indentLevel; i++) {
            output += "  ";
        }
        try {
            output += "Leaf bytes : ";
            for (int i = 56; i >= 0; i -= 8) {
                output += String.format("0x%02x ", (getAtLongIndex(entryIndex) >>> i) & 0xff);

            }
            output += "\n";
        } catch (Exception ex) {
            output += String.format("Exception thrown at leafEntry at index %d\n", entryIndex);
        }
        return output;
    }

    private String recordedValuesToString() {
        String output = "";
        try {
            for (IterationValue v : nonZeroValues()) {
                output += String.format("[%d] : %d\n", v.getIndex(), v.getValue());
            }
            return output;
        } catch (Exception ex) {
            output += "!!! Exception thrown in value iteration...\n";
        }
        return output;
    }

    @Override
    public String toString() {
        String output = "PackedArrayContext:\n";
        if (!isPacked()) {
            return output + "Context is unpacked:\n" + unpackedToString();
        }
        for (int setNumber = 0; setNumber < NUMBER_OF_SETS; setNumber++) {
            try {
                int entryPointerIndex = SET_0_START_INDEX + setNumber;
                int entryIndex = getIndexAtShortIndex(entryPointerIndex);
                output += String.format("Set %d: root = %d \n", setNumber, entryIndex);
                if (entryIndex == 0) continue;
                output += nonLeafEntryToString(entryIndex, getTopLevelShift(), 4);
            } catch (Exception ex) {
                output += String.format("Exception thrown in set %d\n", setNumber);
            }
        }
        output += recordedValuesToString();
        return output;
    }

    private static class RetryException extends Exception {}
}