Package org.infinispan.protostream.impl

Class SparseBitSet

java.lang.Object
org.infinispan.protostream.impl.SparseBitSet
All Implemented Interfaces:
Iterable<Long>, ReservedNumbers
public class SparseBitSet extends Object implements ReservedNumbers
A sparse bit set for storing occurrences of bits where a large amount of the stored bits are expected to be zero. This implementation uses a simplistic indexing scheme which provides log(n) performance for accessing individual bits. Memory usage is roughly proportional to bitCount(). The bit set can set any bit between 0 and Long.MAX_VALUE, inclusive. However, the maximum number of sparse 64-bit words in use by the set bits in the bit set is limited by the int length limit of arrays.

  • Field Details

    • words

      private long[] words

    • indices

      private long[] indices

    • size

      private int size

    • modCount

      private int modCount

  • Constructor Details

    • SparseBitSet

      public SparseBitSet()
      Construct a SparseBitSet.

    • SparseBitSet

      public SparseBitSet(long... values)
      Construct a SparseBitSet with the given values.

    • SparseBitSet

      public SparseBitSet(int capacity)
      Construct a SparseBitSet with the given initial capacity.

    • SparseBitSet

      public SparseBitSet(SparseBitSet other)

  • Method Details

    • set

      public boolean set(long i)
      Set the bit at index i.
      Returns:
      true if this bit set changed as a result of setting the bit, i.e. the bit was clear, false otherwise.

    • clear

      public boolean clear(long i)
      Clear the bit at index i.
      Returns:
      true if this bit set changed as a result of setting the bit, i.e. the bit was set, false otherwise.

    • set

      public boolean set(long i, boolean value)
      Set the bit at index i to the given value.
      Returns:
      true if this bit set changed as a result of changing the bit, false otherwise.

    • set

      public void set(long fromIndex, long toIndex)
      Sets the bits from the specified fromIndex (inclusive) to the specified toIndex (exclusive) to true. Params:
      Parameters:
      fromIndex - – index of the first bit to be set
      toIndex - – index after the last bit to be set
      Throws:
      IndexOutOfBoundsException - – if fromIndex is negative, or toIndex is negative, or fromIndex is larger than toIndex

    • get

      public boolean get(long i)
      Get the bit at index i.
      Specified by:
      get in interface ReservedNumbers
      Returns:
      true if the bit at index i is set, false otherwise.

    • bitCount

      public long bitCount()
      Returns:
      the number of set bits in this SparseBitSet.

    • size

      public int size()
      Specified by:
      size in interface ReservedNumbers
      Returns:
      the size of this SparseBitSet, i.e. the number of set bits.
      See Also:

    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface ReservedNumbers
      Returns:
      true if this SparseBitSet contains no set bits, false otherwise.

    • nextSetBit

      public int nextSetBit(int fromIndex)
      Specified by:
      nextSetBit in interface ReservedNumbers

    • adjustBase

      private int adjustBase(int fromIndex, int wordIndex)

    • nextClearBit

      public int nextClearBit(int fromIndex)
      Specified by:
      nextClearBit in interface ReservedNumbers

    • clear

      public void clear()
      Reset this SparseBitSet to the empty state, i.e. with no bits set.

    • firstLong

      public long firstLong()

    • lastLong

      public long lastLong()

    • iterator

      public PrimitiveIterator.OfLong iterator()
      Specified by:
      iterator in interface Iterable<Long>

    • descendingIterator

      public PrimitiveIterator.OfLong descendingIterator()

    • toString

      public String toString()
      Overrides:
      toString in class Object
      Returns:
      a string representation of this BitSet in the same format as BitSet.toString(), e.g. the indices of all the set bits in ascending order surrounded by curly brackets "{}".

    • findWord

      private int findWord(long x)

    • insert

      private void insert(long x, int insertionPoint)

    • removeBit

      private void removeBit(int wordIndex, long bitIndex)

    • removeWord

      private void removeWord(int index)

    • removeAll

      public void removeAll(ReservedNumbers that)