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 thei-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 thei-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 long
BASE_RAM_BYTES_USED
(package private) long[][]
bits
(package private) long[]
indices
(package private) int
length
private static int
MASK_4096
(package private) int
nonZeroLongCount
(package private) long
ramBytesUsed
private static 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)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods 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(int i)
Clear the bit at indexi
.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 specifiedindex
.boolean
getAndSet(int i)
Set the bit ati
, returningtrue
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 setprivate long
longBits(long index, long[] bits, int i64)
Return the long bits at the giveni64
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 whenit
is denseprivate 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 indexi
.java.lang.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 Detail
-
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:
- Constant Field Values
-
indices
final long[] indices
-
bits
final long[][] bits
-
length
final int length
-
nonZeroLongCount
int nonZeroLongCount
-
ramBytesUsed
long ramBytesUsed
-
-
Method Detail
-
blockCount
private static int blockCount(int length)
-
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 classBitSet
-
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 returnsBitSet.cardinality()
.- Specified by:
approximateCardinality
in classBitSet
-
get
public boolean get(int i)
Description copied from interface:Bits
Returns the value of the bit with the specifiedindex
.- 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 ati
, returningtrue
if it was previously set.
-
oversize
private static int oversize(int s)
-
insertBlock
private void insertBlock(int i4096, long i64bit, int i)
-
insertLong
private void insertLong(int i4096, long i64bit, int i, long index)
-
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.
-
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 classBitSet
-
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 classBitSet
-
longBits
private long longBits(long index, long[] bits, int i64)
Return the long bits at the giveni64
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 java.io.IOException
or(DocIdSetIterator)
impl that works best whenit
is dense- Throws:
java.io.IOException
-
or
public void or(DocIdSetIterator it) throws java.io.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.
-
ramBytesUsed
public long ramBytesUsed()
Description copied from interface:Accountable
Return the memory usage of this object in bytes. Negative values are illegal.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-