Package edu.berkeley.cs.jqf.fuzz.util

Class FastNonCollidingCounter

  • public class FastNonCollidingCounter
extends Counter
    An implementation of Counter that uses an IntIntHashMap to store values "Fast" in that it is faster than using something that involves other HashMaps, and boxing to-and-from primitive values. There is surely a way to make it *faster* than this too, without avoiding the collisions, but given the performance improvement compared to the original (and collision-prone) coverage, I made the opinionated decision to implement it this way to avoid other concerns from high collisions rates on some particular target applications. Further experimentation with fast (non-colliding) coverage implementations might help to determine which approach is preferable.
    Author:
    Jonathan Bell

    • Field Detail

      • nonZeroKeys

        protected org.eclipse.collections.impl.list.mutable.primitive.IntArrayList nonZeroKeys

    • Constructor Detail

      • FastNonCollidingCounter

        public FastNonCollidingCounter​(int size)
        Creates a new counter

    • Method Detail

      • size

        public int size()
        Returns the size of this counter.
        Overrides:
        size in class Counter
        Returns:
        the size of this counter

      • clear

        public void clear()
        Clears the counter by setting all values to zero.
        Overrides:
        clear in class Counter

      • increment

        public int increment​(int key)
        Increments the count at the given key.
        Overrides:
        increment in class Counter
        Parameters:
        key - the key whose count to increment
        Returns:
        the new value after incrementing the count

      • increment

        public int increment​(int key,
                     int delta)
        Increments the count at the given key by a given delta.
        Overrides:
        increment in class Counter
        Parameters:
        key - the key whose count to increment
        delta - the amount to increment by
        Returns:
        the new value after incrementing the count

      • incrementAtIndex

        protected int incrementAtIndex​(int index,
                               int delta)
        Overrides:
        incrementAtIndex in class Counter

      • setAtIndex

        public void setAtIndex​(int idx,
                       int value)
        Overrides:
        setAtIndex in class Counter

      • getAtIndex

        public int getAtIndex​(int idx)
        Overrides:
        getAtIndex in class Counter

      • getNonZeroSize

        public int getNonZeroSize()
        Returns the number of indices with non-zero counts.
        Overrides:
        getNonZeroSize in class Counter
        Returns:
        the number of indices with non-zero counts

      • getNonZeroKeys

        public org.eclipse.collections.api.list.primitive.IntList getNonZeroKeys()
        Returns a set of keys at which the count is non-zero.
        Returns:
        a set of keys at which the count is non-zero

      • getNonZeroIndices

        public org.eclipse.collections.api.list.primitive.IntList getNonZeroIndices()
        Description copied from class: Counter
        Returns a set of indices at which the count is non-zero.

        Note that indices are different from keys, in that multiple keys can map to the same index due to hash collisions.

        Overrides:
        getNonZeroIndices in class Counter
        Returns:
        a set of indices at which the count is non-zero

      • getNonZeroValues

        public org.eclipse.collections.api.list.primitive.IntList getNonZeroValues()
        Returns a set of non-zero count values in this counter.
        Overrides:
        getNonZeroValues in class Counter
        Returns:
        a set of non-zero count values in this counter.

      • get

        public int get​(int key)
        Retreives a value for a given key.

        The key is first hashed to retreive a value from the counter, and hence the result is modulo collisions.

        Overrides:
        get in class Counter
        Parameters:
        key - the key to query
        Returns:
        the count for the index corresponding to this key

      • hasNonZeros

        public boolean hasNonZeros()
        Description copied from class: Counter
        Checks if all indices have zero counts and returns a boolean as result.
        Overrides:
        hasNonZeros in class Counter
        Returns:
        true if some indices have non-zero counts, otherwise false.