Module org.apache.lucene.core
Package org.apache.lucene.util

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
    BASE_RAM_BYTES_USED
     
    (package private) final long[][]
    bits
     
    (package private) final long[]
    indices
     
    (package private) final int
    length
     
    private static final int
    MASK_4096
     
    (package private) int
    nonZeroLongCount
     
    (package private) long
    ramBytesUsed
     
    private static final long
    SINGLE_ELEMENT_ARRAY_BYTES_USED
     

    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
    approximateCardinality()
    Return an approximation of the cardinality of this set.
    private static int
    blockCount(int length)
     
    int
    cardinality()
    Return the number of bits that are set.
    void
    clear()
    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)
    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
    length()
    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.
    private void
    or(int i4096, long index, long[] bits, int nonZeroLongCount)
     
    void
    or(DocIdSetIterator it)
    Does in-place OR of the bits provided by the iterator.
    private void
    or(SparseFixedBitSet other)
     
    private void
    orDense(DocIdSetIterator it)
    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
    ramBytesUsed()
    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.
    String
    toString()
     

    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)
      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.
      Specified by:
      nextSetBit in class BitSet

    • 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