Class SparseFixedBitSet

java.lang.Object
org.apache.lucene.util.BitSet
org.apache.lucene.util.SparseFixedBitSet
All Implemented Interfaces:
Accountable, Bits

public class SparseFixedBitSet extends BitSet
A bit set that only stores longs that have at least one bit which is set. The way it works is that the space of bits is divided into blocks of 4096 bits, which is 64 longs. Then for each block, we have:
  • a long[] which stores the non-zero longs for that block
  • a long so that bit i being set means that the i-th long of the block is non-null, and its offset in the array of longs is the number of one bits on the right of the i-th bit.
  • Nested Class Summary

    Nested classes/interfaces inherited from interface org.apache.lucene.util.Bits

    Bits.MatchAllBits, Bits.MatchNoBits
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static final long
     
    (package private) final long[][]
     
    (package private) final long[]
     
    (package private) final int
     
    private static final int
     
    (package private) int
     
    (package private) long
     
    private static final long
     

    Fields inherited from interface org.apache.lucene.util.Accountable

    NULL_ACCOUNTABLE

    Fields inherited from interface org.apache.lucene.util.Bits

    EMPTY_ARRAY
  • Constructor Summary

    Constructors
    Constructor
    Description
    SparseFixedBitSet(int length)
    Create a SparseFixedBitSet that can contain bits between 0 included and length excluded.
  • Method Summary

    Modifier and Type
    Method
    Description
    private void
    and(int i4096, int i64, long mask)
     
    int
    Return an approximation of the cardinality of this set.
    private static int
    blockCount(int length)
     
    int
    Return the number of bits that are set.
    void
    Clear all the bits of the set.
    void
    clear(int i)
    Clear the bit at index i.
    void
    clear(int from, int to)
    Clears a range of bits.
    private void
    clearWithinBlock(int i4096, int from, int to)
     
    private boolean
    consistent(int index)
     
    private int
    firstDoc(int i4096, int i4096upper)
    Return the first document that occurs on or after the provided block index.
    boolean
    get(int i)
    Returns the value of the bit with the specified index.
    boolean
    getAndSet(int i)
    Set the bit at i, returning true if it was previously set.
    private void
    insertBlock(int i4096, long i64bit, int i)
     
    private void
    insertLong(int i4096, long i64bit, int i, long index)
     
    private int
    lastDoc(int i4096)
    Return the last document that occurs on or before the provided block index.
    int
    Returns the number of bits in this set
    private long
    longBits(long index, long[] bits, int i64)
    Return the long bits at the given i64 index.
    private static long
    mask(int from, int to)
     
    int
    nextSetBit(int i)
    Returns the index of the first set bit starting at the index specified.
    int
    nextSetBit(int start, int upperBound)
    Returns the index of the first set bit from start (inclusive) until end (exclusive).
    private int
    nextSetBitInRange(int start, int upperBound)
    Returns the next set bit in the specified range, but treats `upperBound` as a best-effort hint rather than a hard requirement.
    private void
    or(int i4096, long index, long[] bits, int nonZeroLongCount)
     
    void
    Does in-place OR of the bits provided by the iterator.
    private void
     
    private void
    or(DocIdSetIterator) impl that works best when it is dense
    private static int
    oversize(int s)
     
    int
    prevSetBit(int i)
    Returns the index of the last set bit before or on the index specified.
    long
    Return the memory usage of this object in bytes.
    private void
    removeLong(int i4096, int i64, long index, int o)
     
    void
    set(int i)
    Set the bit at index i.
     

    Methods inherited from class org.apache.lucene.util.BitSet

    checkUnpositioned, of

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

    Methods inherited from interface org.apache.lucene.util.Accountable

    getChildResources
  • Field Details

    • BASE_RAM_BYTES_USED

      private static final long BASE_RAM_BYTES_USED
    • SINGLE_ELEMENT_ARRAY_BYTES_USED

      private static final long SINGLE_ELEMENT_ARRAY_BYTES_USED
    • MASK_4096

      private static final int MASK_4096
      See Also:
    • indices

      final long[] indices
    • bits

      final long[][] bits
    • length

      final int length
    • nonZeroLongCount

      int nonZeroLongCount
    • ramBytesUsed

      long ramBytesUsed
  • Constructor Details

    • SparseFixedBitSet

      public SparseFixedBitSet(int length)
      Create a SparseFixedBitSet that can contain bits between 0 included and length excluded.
  • Method Details

    • blockCount

      private static int blockCount(int length)
    • clear

      public void clear()
      Description copied from class: BitSet
      Clear all the bits of the set.

      Depending on the implementation, this may be significantly faster than clear(0, length).

      Overrides:
      clear in class BitSet
    • length

      public int length()
      Description copied from interface: Bits
      Returns the number of bits in this set
    • consistent

      private boolean consistent(int index)
    • cardinality

      public int cardinality()
      Description copied from class: BitSet
      Return the number of bits that are set. NOTE: this method is likely to run in linear time
      Specified by:
      cardinality in class BitSet
    • approximateCardinality

      public int approximateCardinality()
      Description copied from class: BitSet
      Return an approximation of the cardinality of this set. Some implementations may trade accuracy for speed if they have the ability to estimate the cardinality of the set without iterating over all the data. The default implementation returns BitSet.cardinality().
      Specified by:
      approximateCardinality in class BitSet
    • get

      public boolean get(int i)
      Description copied from interface: Bits
      Returns the value of the bit with the specified index.
      Parameters:
      i - index, should be non-negative and < Bits.length(). The result of passing negative or out of bounds values is undefined by this interface, just don't do it!
      Returns:
      true if the bit is set, false otherwise.
    • getAndSet

      public boolean getAndSet(int i)
      Description copied from class: BitSet
      Set the bit at i, returning true if it was previously set.
      Specified by:
      getAndSet in class BitSet
    • oversize

      private static int oversize(int s)
    • set

      public void set(int i)
      Set the bit at index i.
      Specified by:
      set in class BitSet
    • insertBlock

      private void insertBlock(int i4096, long i64bit, int i)
    • insertLong

      private void insertLong(int i4096, long i64bit, int i, long index)
    • clear

      public void clear(int i)
      Clear the bit at index i.
      Specified by:
      clear in class BitSet
    • and

      private void and(int i4096, int i64, long mask)
    • removeLong

      private void removeLong(int i4096, int i64, long index, int o)
    • clear

      public void clear(int from, int to)
      Description copied from class: BitSet
      Clears a range of bits.
      Specified by:
      clear in class BitSet
      Parameters:
      from - lower index
      to - one-past the last bit to clear
    • mask

      private static long mask(int from, int to)
    • clearWithinBlock

      private void clearWithinBlock(int i4096, int from, int to)
    • firstDoc

      private int firstDoc(int i4096, int i4096upper)
      Return the first document that occurs on or after the provided block index.
    • nextSetBit

      public int nextSetBit(int i)
      Description copied from class: BitSet
      Returns the index of the first set bit starting at the index specified. DocIdSetIterator.NO_MORE_DOCS is returned if there are no more set bits.
      Overrides:
      nextSetBit in class BitSet
    • nextSetBit

      public int nextSetBit(int start, int upperBound)
      Description copied from class: BitSet
      Returns the index of the first set bit from start (inclusive) until end (exclusive). DocIdSetIterator.NO_MORE_DOCS is returned if there are no more set bits.
      Specified by:
      nextSetBit in class BitSet
    • nextSetBitInRange

      private int nextSetBitInRange(int start, int upperBound)
      Returns the next set bit in the specified range, but treats `upperBound` as a best-effort hint rather than a hard requirement. Note that this may return a result that is >= upperBound in some cases, so callers must add their own check if `upperBound` is a hard requirement.
    • lastDoc

      private int lastDoc(int i4096)
      Return the last document that occurs on or before the provided block index.
    • prevSetBit

      public int prevSetBit(int i)
      Description copied from class: BitSet
      Returns the index of the last set bit before or on the index specified. -1 is returned if there are no more set bits.
      Specified by:
      prevSetBit in class BitSet
    • longBits

      private long longBits(long index, long[] bits, int i64)
      Return the long bits at the given i64 index.
    • or

      private void or(int i4096, long index, long[] bits, int nonZeroLongCount)
    • or

      private void or(SparseFixedBitSet other)
    • orDense

      private void orDense(DocIdSetIterator it) throws IOException
      or(DocIdSetIterator) impl that works best when it is dense
      Throws:
      IOException
    • or

      public void or(DocIdSetIterator it) throws IOException
      Description copied from class: BitSet
      Does in-place OR of the bits provided by the iterator. The state of the iterator after this operation terminates is undefined.
      Overrides:
      or in class BitSet
      Throws:
      IOException
    • ramBytesUsed

      public long ramBytesUsed()
      Description copied from interface: Accountable
      Return the memory usage of this object in bytes. Negative values are illegal.
    • toString

      public String toString()
      Overrides:
      toString in class Object