AbstractPackedLongArray.java

package org.HdrHistogram.packedarray;

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

/**
 * A Packed array of signed 64 bit values, and supports {@link #get get()}, {@link #set set()},
 * {@link #add add()} and {@link #increment increment()} operations on the logical contents of the array.
 */
abstract class AbstractPackedLongArray implements Iterable<Long>, Serializable {
    /**
     * An {@link AbstractPackedLongArray} Uses {@link AbstractPackedArrayContext} to track
     * the array's logical contents. Contexts may be switched when a context requires resizing
     * to complete logical array operations (get, set, add, increment). Contexts are
     * established and used within critical sections in order to facilitate concurrent
     * implementors.
     */

    private static final int NUMBER_OF_SETS = 8;

    private AbstractPackedArrayContext arrayContext;
    private long startTimeStampMsec = Long.MAX_VALUE;
    private long endTimeStampMsec = 0;

    AbstractPackedArrayContext getArrayContext() {
        return arrayContext;
    }

    void setArrayContext(AbstractPackedArrayContext newArrayContext) {
        arrayContext = newArrayContext;
    }

    /**
     * get the start time stamp [optionally] stored with this array
     * @return the start time stamp [optionally] stored with this array
     */
    public long getStartTimeStamp() {
        return startTimeStampMsec;
    }

    /**
     * Set the start time stamp value associated with this array to a given value.
     * @param timeStampMsec the value to set the time stamp to, [by convention] in msec since the epoch.
     */
    public void setStartTimeStamp(final long timeStampMsec) {
        this.startTimeStampMsec = timeStampMsec;
    }

    /**
     * get the end time stamp [optionally] stored with this array
     * @return the end time stamp [optionally] stored with this array
     */
    public long getEndTimeStamp() {
        return endTimeStampMsec;
    }

    /**
     * Set the end time stamp value associated with this array to a given value.
     * @param timeStampMsec the value to set the time stamp to, [by convention] in msec since the epoch.
     */
    public void setEndTimeStamp(final long timeStampMsec) {
        this.endTimeStampMsec = timeStampMsec;
    }

    /**
     * Set a new virtual length for the array.
     * @param newVirtualArrayLength the
     */
    abstract public void setVirtualLength(final int newVirtualArrayLength);

    /**
     * Create a copy of this array, complete with data and everything.
     *
     * @return A distinct copy of this array.
     */
    abstract public AbstractPackedLongArray copy();

    abstract void resizeStorageArray(int newPhysicalLengthInLongs);

    abstract void clearContents();

    abstract long criticalSectionEnter();

    abstract void criticalSectionExit(long criticalValueAtEnter);


    @Override
    public String toString() {
        String output = "PackedArray:\n";
        AbstractPackedArrayContext arrayContext = getArrayContext();
        output += arrayContext.toString();
        return output;
    }

    /**
     * Get value at virtual index in the array
     * @param index the virtual array index
     * @return the array value at the virtual index given
     */
    public long get(final int index) {
        long value = 0;
        for (int byteNum = 0; byteNum < NUMBER_OF_SETS; byteNum ++) {
            int packedIndex = 0;
            long byteValueAtPackedIndex = 0;
            do {
                int newArraySize = 0;
                long criticalValue = criticalSectionEnter();
                try {
                    // Establish context within: critical section
                    AbstractPackedArrayContext arrayContext = getArrayContext();
                    // Deal with unpacked context:
                    if (!arrayContext.isPacked()) {
                        return arrayContext.getAtUnpackedIndex(index);
                    }
                    // Context is packed:
                    packedIndex = arrayContext.getPackedIndex(byteNum, index, false);
                    if (packedIndex < 0) {
                        return value;
                    }
                    byteValueAtPackedIndex =
                            (((long)arrayContext.getAtByteIndex(packedIndex)) & 0xff) << (byteNum << 3);
                } catch (ResizeException ex) {
                    newArraySize = ex.getNewSize(); // Resize outside of critical section
                } finally {
                    criticalSectionExit(criticalValue);
                    if (newArraySize != 0) {
                        resizeStorageArray(newArraySize);
                    }
                }
            } while (packedIndex == 0);

            value += byteValueAtPackedIndex;
        }
        return value;
    }

    /**
     * Increment value at a virtual index in the array
     * @param index virtual index of value to increment
     */
    public void increment(final int index) {
        add(index, 1);
    }

    /**
     * Add to a value at a virtual index in the array
     * @param index the virtual index of the value to be added to
     * @param value the value to add
     */
    public void add(final int index, final long value) {
        if (value == 0) {
            return;
        }
        long remainingValueToAdd = value;

        do {
            try {
                long byteMask = 0xff;
                for (int byteNum = 0, byteShift = 0;
                     byteNum < NUMBER_OF_SETS;
                     byteNum++, byteShift += 8, byteMask <<= 8) {
                    final long criticalValue = criticalSectionEnter();
                    try {
                        // Establish context within: critical section
                        AbstractPackedArrayContext arrayContext = getArrayContext();
                        // Deal with unpacked context:
                        if (!arrayContext.isPacked()) {
                            arrayContext.addAndGetAtUnpackedIndex(index, remainingValueToAdd);
                            return;
                        }
                        // Context is packed:
                        int packedIndex = arrayContext.getPackedIndex(byteNum, index, true);

                        long amountToAddAtSet = remainingValueToAdd & byteMask;
                        byte byteToAdd = (byte) (amountToAddAtSet >> byteShift);
                        long afterAddByteValue = arrayContext.addAtByteIndex(packedIndex, byteToAdd);

                        // Reduce remaining value to add by amount just added:
                        remainingValueToAdd -= amountToAddAtSet;

                        // Account for carry:
                        long carryAmount = afterAddByteValue & 0x100;
                        remainingValueToAdd += carryAmount << byteShift;

                        if (remainingValueToAdd == 0) {
                            return; // nothing to add to higher magnitudes
                        }
                    } finally {
                        criticalSectionExit(criticalValue);

                    }
                }
                return;
            } catch (ResizeException ex){
                resizeStorageArray(ex.getNewSize()); // Resize outside of critical section
            }
        } while (true);
    }

    /**
     * Set the value at a virtual index in the array
     * @param index the virtual index of the value to set
     * @param value the value to set
     */
    public void set(final int index, final long value) {
        int bytesAlreadySet = 0;
        do {
            long valueForNextLevels = value;
            try {
                for (int byteNum = 0; byteNum < NUMBER_OF_SETS; byteNum++) {
                    long criticalValue = criticalSectionEnter();
                    try {
                        // Establish context within: critical section
                        AbstractPackedArrayContext arrayContext = getArrayContext();
                        // Deal with unpacked context:
                        if (!arrayContext.isPacked()) {
                            arrayContext.setAtUnpackedIndex(index, value);
                            return;
                        }
                        // Context is packed:
                        if (valueForNextLevels == 0) {
                            // Special-case zeros to avoid inflating packed array for no reason
                            int packedIndex = arrayContext.getPackedIndex(byteNum, index, false);
                            if (packedIndex < 0) {
                                return; // no need to create entries for zero values if they don't already exist
                            }
                        }
                        // Make sure byte is populated:
                        int packedIndex = arrayContext.getPackedIndex(byteNum, index, true);

                        // Determine value to write, and prepare for next levels
                        byte byteToWrite = (byte) (valueForNextLevels & 0xff);
                        valueForNextLevels >>= 8;

                        if (byteNum < bytesAlreadySet) {
                            // We want to avoid writing to the same byte twice when not doing so for the
                            // entire 64 bit value atomically, as doing so opens a race with e.g. concurrent
                            // adders. So don't actually write the byte if has been written before.
                            continue;
                        }
                        arrayContext.setAtByteIndex(packedIndex, byteToWrite);
                        bytesAlreadySet++;
                    } finally {
                        criticalSectionExit(criticalValue);
                    }
                }
                return;
            } catch (ResizeException ex) {
                resizeStorageArray(ex.getNewSize()); // Resize outside of critical section
            }
        } while (true);
    }

    /**
     * Add the contents of the other array to this one
     *
     * @param other The to add to this array
     */
    public void add(final AbstractPackedLongArray other) {
        for (IterationValue v : other.nonZeroValues()) {
            add(v.getIndex(), v.getValue());
        }
    }

    /**
     * Clear the array contents
     */
    public void clear() {
        clearContents();
    }

    /**
     * Get the current physical length (in longs) of the array's backing storage
     * @return the current physical length (in longs) of the array's current backing storage
     */
    public int getPhysicalLength() {
        return getArrayContext().length();
    }

    /**
     * Get the (virtual) length of the array
     * @return the (virtual) length of the array
     */
    public int length() {
        return getArrayContext().getVirtualLength();
    }

    // Regular array iteration (iterates over all virtual indexes, zero-value or not:

    class AllValuesIterator implements Iterator<Long> {

        int nextVirtualIndex = 0;

        @Override
        public Long next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return get(nextVirtualIndex++);
        }

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

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

    /**
     * An Iterator over all values in the array
     * @return an Iterator over all values in the array
     */
    public Iterator<Long> iterator() {
        return new AllValuesIterator();
    }

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

    /**
     * Determine if this array is equivalent to another.
     *
     * @param other the other array to compare to
     * @return True if this array are equivalent with the other.
     */
    @Override
    public boolean equals(final Object other) {
        if (this == other) {
            return true;
        }
        if (!(other instanceof AbstractPackedLongArray)) {
            return false;
        }
        AbstractPackedLongArray that = (AbstractPackedLongArray) other;
        if (length() != that.length()) {
            return false;
        }
        if (this.arrayContext.isPacked() || that.arrayContext.isPacked()) {
            // If at least one of the arrays is packed, comparing only the
            // non-zero values that exist in both arrays, using two passes,
            // will likely be more efficient than a single all-index pass:
            // - If both are packed, it will obviously be much faster.
            // - If one is packed and the other is not, we would be visiting
            //   every index in the non-packed array, in one of the passes,
            //   but would still only visit the non-zero elements in the
            //   packed one.
            for (IterationValue v : this.nonZeroValues()) {
                if (that.get(v.getIndex()) != v.getValue()) {
                    return false;
                }
            }
            for (IterationValue v : that.nonZeroValues()) {
                if (this.get(v.getIndex()) != v.getValue()) {
                    return false;
                }
            }
        } else {
            for (int i = 0; i < this.length(); i++) {
                if (this.get(i) != that.get(i)) {
                    return false;
                }
            }
        }
        return true;
    }

    static final int NUMBER_OF_NON_ZEROS_TO_HASH = 8;

    @Override
    public int hashCode() {
        int h = 0;
        h = oneAtATimeHashStep(h, length());
        int count = 0;
        // Include the first NUMBER_OF_NON_ZEROS_TO_HASH non-zeros in the hash:
        for (IterationValue v : nonZeroValues()) {
            if (++count > NUMBER_OF_NON_ZEROS_TO_HASH) {
                break;
            }
            h = oneAtATimeHashStep(h, (int) v.getIndex());
            h = oneAtATimeHashStep(h, (int) v.getValue());
        }
        h += (h << 3);
        h ^= (h >> 11);
        h += (h << 15);
        return h;
    }

    private int oneAtATimeHashStep(final int incomingHash, final int v) {
        int h = incomingHash;
        h += v;
        h += (h << 10);
        h ^= (h >> 6);
        return h;
    }
}