A data structure to represent a sequence of bits. More...
#include <bitvector.h>
Classes | |
struct | active_word |
The struct active_word stores the last few bits that do not fill a whole word. | |
class | const_iterator |
The const_iterator class. It iterates on the individual bits. More... | |
class | indexSet |
The indexSet stores positions of bits that are one. More... | |
class | iterator |
The iterator that allows modification of bits. More... | |
struct | run |
An internal struct used during logical operations to track the usage of fill words. | |
Public Types | |
typedef uint32_t | word_t |
The basic unit of data storage. | |
Public Member Functions | |
void | adjustSize (word_t nv, word_t nt) |
Adjust the size of the bit sequence. | |
void | appendFill (int val, word_t n) |
Append n bits of val . | |
void | appendWord (word_t w) |
Append a WAH word. | |
iterator | begin () |
const_iterator | begin () const |
bitvector () | |
Default constructor. Creates a new empty bitvector. | |
bitvector (const bitvector &bv) | |
Copy constructor. | |
bitvector (const array_t< word_t > &arr) | |
Construct a bitvector from an array. | |
bitvector (const char *file) | |
Constructor. Reconstruct a bitvector from a file. | |
uint32_t | bytes () const throw () |
Return the number of bytes used by the bitvector object in memory. | |
void | clear () |
Remove the existing content of a bitvector. | |
word_t | cnt () const |
Return the number of bits that are one. | |
void | compress () |
Merge fills into fill words. | |
word_t | compressible () const |
Return the number of word saved if the function compress is called. | |
bitvector & | copy (const bitvector &bv) |
Make a copy. Performs a deep copy. | |
word_t | count (const bitvector &mask) const |
Count the number of bits that are 1 that also marked 1. | |
word_t | count () const |
void | decompress () |
Turn all fill words into literal words. | |
bool | empty () const |
Is the bitvector empty? For efficiency reasons, this funciton only works correctly on a properly compressed bitvector. | |
iterator | end () |
const_iterator | end () const |
void | erase (word_t i, word_t j) |
Remove the bits in the range of [i, j). | |
indexSet | firstIndexSet () const |
void | flip () |
Complement all bits of a bit sequence. | |
uint32_t | getSerialSize () const throw () |
Compute the number of bytes in the serialized version of this bitvector object. | |
bool | isCompressed () const |
Does this bit vector use less space than the maximum? Return true if yes, otherwise false. | |
word_t | numFillWords () const |
Return the number of fill words. | |
bitvector * | operator& (const bitvector &) const |
Perform bitwise AND between this bitvector and rhs , return the result as a new bitvector. | |
void | operator&= (const bitvector &rhs) |
Perform bitwise AND between this bitvector and rhs . | |
bitvector & | operator+= (const bitvector &bv) |
Append a bitvector. | |
bitvector & | operator+= (int b) |
Append a single bit. | |
bitvector * | operator- (const bitvector &) const |
Perform bitwise subtraction and return the result as a new bitvector. | |
void | operator-= (const bitvector &rhs) |
Perform bitwise subtraction (a & !b). | |
const bitvector & | operator= (const bitvector &bv) |
The assignment operator. | |
int | operator== (const bitvector &rhs) const |
Return 1 if two bit sequences have the same content, 0 otherwise. | |
bitvector * | operator^ (const bitvector &) const |
Perform bitwise XOR and return the result as a new bitvector. | |
void | operator^= (const bitvector &rhs) |
Perform bitwise exclusive or (XOR). | |
bitvector * | operator| (const bitvector &) const |
Perform bitwise OR and return the result as a new bitvector. | |
void | operator|= (const bitvector &rhs) |
Perform bitwise OR. | |
std::ostream & | print (std::ostream &) const |
The print function. | |
void | read (const char *fn) |
Read a bit vector from the file. | |
void | reserve (unsigned nb, unsigned nc, double cf=0.0) |
Reserve enough space for a bit vector. | |
void | set (int val, word_t n) |
Create a vector with n bits of value val (cf. | |
void | setBit (const word_t i, int val) |
Replace a single bit at position i with val. | |
word_t | size () const throw () |
Return the total number of bits in the bit sequence. | |
word_t | sloppyCount () const |
Provide a sloppy count of the number of bits that are 1. | |
void | sloppySize (word_t n) const |
Explicitly set the size of the bitvector. | |
void | subset (const bitvector &mask, bitvector &res) const |
Select a subset of the bits. | |
bitvector & | swap (bitvector &bv) |
void | turnOnRawBit (const word_t i) |
Turn on a single bit in a uncompressed bitvector. | |
void | write (const char *fn) const |
Write the bit vector to a file. | |
void | write (int fdes) const |
Write to a file that is opened by the caller. | |
void | write (array_t< word_t > &arr) const |
Write the bit vector to an array_t<word_t>. | |
~bitvector () | |
Destructor. | |
Static Public Member Functions | |
static word_t | bitsPerLiteral () |
Return the number of bits in a literal word. | |
static double | clusteringFactor (word_t nb, word_t nc, word_t sz) |
Estimate clustering factor based on the size. | |
static double | markovSize (word_t nb, word_t nc, double f) |
Compute the expected size (number of bytes) of a random sequence generated from a Markov process. | |
static double | randomSize (word_t nb, word_t nc) |
Compute the expected number of bytes required to store a random sequence. | |
Protected Member Functions | |
bool | all0s () const |
Are all bits in regular words 0? It assumes the regular words have been properly compressed and therefore only need to check one word. | |
bool | all1s () const |
Are all bits in regular words 1? It assumes the regular words are properly compressed and therefore only need to examine one word. | |
Friends | |
struct | active_word |
class | const_iterator |
class | indexSet |
class | iterator |
struct | run |
A data structure to represent a sequence of bits.
Key features
A bitvector object stores a sequence of bits and provides fast bitwise logical operations. In addition, it supports operations to append new bits from the end, read bits at arbitrary location and set bits at arbitrary location. It also supports an iterator, a const_iterator and an indexSet.
Encoding format <http://lbl.gov/~kwu/ps/LBNL-49626.html> <http://portal.acm.org/citation.cfm?doid=1132863.1132864>
Incoming bits are organized into words (bitvector::word_t). A word is a literal word if its Most Significant Bit (MSB) is 0, it is a fill word if its MSB is 1. A literal word stores literal bit values in the bit position following the MSB and a fill word stores a sequence of consecutive bits that are of the same value, i.e., a fill. The second most significant bit of the fill word is the bit value, the remaining bits of the word is a unsigned integer that stores the length of the fill as number of equivalent literal words, i.e., how many literal words it will take if the fill is stored in literal words.
Restrictions
The number of bits must be expressible by one single bitvector::word_t. This ensures that a fill word can store a fill of any valid length without performing a bound check. If bitvector::word_t is 32-bit long, the maximum number of bits that can be represented by a bitvector object is 4 billion.
ibis::bitvector::bitvector | ( | const bitvector & | bv | ) |
Copy constructor.
The underlying storage (m_vec) is constructed through a copy constructor as well.
References ibis::gVerbose.
ibis::bitvector::bitvector | ( | const array_t< word_t > & | arr | ) | [explicit] |
Construct a bitvector from an array.
Because the array copy constructor performs shallow copy, this bitvector is not using any new space for the underlying vector.
References clear(), ibis::gVerbose, and ibis::array_t< T >::size().
void ibis::bitvector::adjustSize | ( | word_t | nv, |
word_t | nt | ||
) |
Adjust the size of the bit sequence.
If current size is less than nv
, append enough 1s so that it has nv
bits. If the resulting total number of bits is less than nt
, append 0 bits so that there are nt
total bits. If there are more than nt
bits, only the first nt
bits are kept. The final result always contains nt
bits.
References ibis::gVerbose.
Referenced by ibis::index::addBins(), ibis::tafel::append(), ibis::category::append(), ibis::blob::append(), ibis::column::append(), ibis::tafel::appendString(), ibis::column::appendStrings(), ibis::column::appendValues(), ibis::bin::binning(), ibis::bin::binningT(), ibis::bord::column::column(), ibis::egale::construct(), ibis::part::doComp(), ibis::part::doCompare(), ibis::part::doCount(), ibis::part::doScan(), ibis::countQuery::estimate(), ibis::column::estimateRange(), ibis::countQuery::evaluate(), ibis::column::evaluateRange(), ibis::bord::column::evaluateRange(), ibis::part::evaluateRIDSet(), ibis::mensa::cursor::fillBuffer(), ibis::query::getBounds(), ibis::column::getNullMask(), ibis::bord::column::keywordSearch(), ibis::roster::locate(), ibis::index::mapValues(), ibis::bak::mapValues(), ibis::bak2::mapValues(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::tafel::normalize(), ibis::part::numbersToBitvector(), operator&(), operator&=(), operator-(), operator-=(), operator^(), operator^=(), operator|(), operator|=(), ibis::part::part(), ibis::keywords::readTermDocFile(), ibis::column::searchSortedICC(), ibis::column::searchSortedICD(), ibis::column::searchSortedOOCC(), ibis::column::searchSortedOOCD(), sloppySize(), ibis::text::stringSearch(), ibis::bord::column::stringSearch(), ibis::column::truncateData(), ibis::part::writeColumn(), ibis::blob::writeData(), ibis::column::writeData(), ibis::part::writeRaw(), ibis::part::writeString(), and ibis::text::writeStrings().
bool ibis::bitvector::all0s | ( | ) | const [inline, protected] |
Are all bits in regular words 0? It assumes the regular words have been properly compressed and therefore only need to check one word.
Referenced by count(), operator&(), operator&=(), operator-(), operator-=(), operator|(), and operator|=().
bool ibis::bitvector::all1s | ( | ) | const [inline, protected] |
Are all bits in regular words 1? It assumes the regular words are properly compressed and therefore only need to examine one word.
Referenced by count(), operator&(), operator&=(), operator-(), operator-=(), operator|(), and operator|=().
void ibis::bitvector::appendFill | ( | int | val, |
word_t | n | ||
) | [inline] |
Append n
bits of val
.
The value n
may be arbitrary integer as long as the resulting size is still representable by a ibis::bitvector::word_t, however, the value val
must be either 0 or 1.
Referenced by ibis::tafel::append(), ibis::tafel::appendString(), erase(), ibis::column::evaluateRange(), ibis::mensa::cursor::fillBuffer(), ibis::index::mapValues(), ibis::bin::mergeValues(), ibis::part::numbersToBitvector(), ibis::column::searchSortedICC(), ibis::column::searchSortedOOCC(), and subset().
void ibis::bitvector::appendWord | ( | word_t | w | ) |
void ibis::bitvector::clear | ( | ) |
Remove the existing content of a bitvector.
The underlying storage is not released until the object is actual freed.
References ibis::gVerbose.
Referenced by ibis::bord::backup(), bitvector(), ibis::tafel::capacity(), ibis::bin::checkBin(), ibis::tafel::clearData(), ibis::part::doComp(), ibis::part::doCompare(), ibis::countQuery::doEstimate(), ibis::query::doEstimate(), ibis::tafel::doReserve(), ibis::part::doScan(), ibis::direkte::estimate(), ibis::relic::estimate(), ibis::bin::estimate(), ibis::slice::estimate(), ibis::range::estimate(), ibis::mesa::estimate(), ibis::ambit::estimate(), ibis::pale::estimate(), ibis::pack::estimate(), ibis::zone::estimate(), ibis::fuge::estimate(), ibis::egale::estimate(), ibis::moins::estimate(), ibis::entre::estimate(), ibis::column::estimateRange(), ibis::column::evaluateAndSelect(), ibis::column::evaluateRange(), ibis::query::getExpandedHits(), ibis::bord::column::keywordSearch(), ibis::roster::locate(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::category::patternSearch(), ibis::keywords::search(), ibis::column::searchSortedICC(), ibis::column::searchSortedICD(), ibis::column::searchSortedOOCC(), ibis::column::searchSortedOOCD(), ibis::query::sequentialScan(), ibis::keywords::setBits(), ibis::text::stringSearch(), ibis::bord::column::stringSearch(), ibis::part::stringToBitvector(), subset(), ibis::direkte::undecidable(), ibis::relic::undecidable(), and ibis::keywords::undecidable().
double ibis::bitvector::clusteringFactor | ( | word_t | nb, |
word_t | nc, | ||
word_t | sz | ||
) | [static] |
Estimate clustering factor based on the size.
The size is measured as the number of bytes.
References ibis::gVerbose.
Referenced by ibis::query::evaluate(), ibis::query::processJoin(), ibis::relic::speedTest(), and ibis::bin::speedTest().
void ibis::bitvector::compress | ( | ) |
Merge fills into fill words.
Compress the current m_vec in-place.
Referenced by ibis::index::addBits(), ibis::query::computeHits(), ibis::part::doComp(), ibis::part::doComp0(), ibis::part::doCompare(), ibis::part::doScan(), ibis::countQuery::estimate(), ibis::countQuery::evaluate(), ibis::query::getBounds(), ibis::util::intersect(), ibis::part::matchAny(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::part::recursiveQuery(), and ibis::index::sumBits().
ibis::bitvector::word_t ibis::bitvector::count | ( | const bitvector & | mask | ) | const |
Count the number of bits that are 1 that also marked 1.
A straightforward implement of this is to perform a bitwise AND and then count the number of bits that are 1. However, such an approach will generate a bitvector that is only used for counting. This is an attempt to do better.
References all0s(), all1s(), count(), and ibis::array_t< T >::size().
Referenced by count().
void ibis::bitvector::decompress | ( | ) |
Turn all fill words into literal words.
Decompress the currently compressed bitvector.
Throw an ibis::bad_alloc exception if it fails to allocate enough memory.
References ibis::gVerbose, ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and ibis::array_t< T >::swap().
Referenced by ibis::index::addBins(), ibis::index::addBits(), ibis::part::doComp(), ibis::part::doComp0(), ibis::part::doCompare(), ibis::part::doScan(), ibis::roster::locate(), ibis::part::negativeCompare(), ibis::index::sumBins(), and ibis::index::sumBits().
bool ibis::bitvector::empty | ( | ) | const [inline] |
Is the bitvector empty? For efficiency reasons, this funciton only works correctly on a properly compressed bitvector.
void ibis::bitvector::flip | ( | ) |
Complement all bits of a bit sequence.
If nbits is not set, set it while flipping the bits.
References ibis::gVerbose.
Referenced by ibis::countQuery::doEstimate(), ibis::query::doEstimate(), ibis::countQuery::doEvaluate(), ibis::query::doEvaluate(), ibis::query::doScan(), ibis::slice::estimate(), ibis::range::estimate(), ibis::ambit::estimate(), ibis::pack::estimate(), ibis::egale::estimate(), ibis::moins::estimate(), ibis::entre::estimate(), ibis::slice::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::range::evaluate(), ibis::column::evaluateRange(), operator-(), ibis::index::sumBins(), and ibis::index::sumBits().
uint32_t ibis::bitvector::getSerialSize | ( | ) | const throw () [inline] |
Compute the number of bytes in the serialized version of this bitvector object.
This would be the number of bytes this bitvector needs on disk or in an array_t<word_t>.
Referenced by ibis::fuzz::getSerialSize(), and ibis::egale::getSerialSize().
bool ibis::bitvector::isCompressed | ( | ) | const [inline] |
Does this bit vector use less space than the maximum? Return true if yes, otherwise false.
double ibis::bitvector::markovSize | ( | word_t | nb, |
word_t | nc, | ||
double | f | ||
) | [inline, static] |
Compute the expected size (number of bytes) of a random sequence generated from a Markov process.
The bit sequence is to have nb
total bits, nc
bits of one, and f
consecutive ones on the average. The argument f
is known as the clustering factor.
ibis::bitvector * ibis::bitvector::operator& | ( | const bitvector & | rhs | ) | const |
Perform bitwise AND between this bitvector and rhs
, return the result as a new bitvector.
This version of bitwise logical operator produces a new bitvector as the result and return a pointer to the new object.
References adjustSize(), all0s(), all1s(), copy(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().
void ibis::bitvector::operator&= | ( | const bitvector & | rhs | ) |
Perform bitwise AND between this bitvector and rhs
.
The in-place version of the bitwise logical AND operator.
It performs the bitwise logical AND operation between this bitvector and rhs
, then stores the result back to this bitvector.
References adjustSize(), all0s(), all1s(), bytes(), copy(), ibis::gVerbose, ibis::array_t< T >::size(), and size().
ibis::bitvector * ibis::bitvector::operator- | ( | const bitvector & | rhs | ) | const |
Perform bitwise subtraction and return the result as a new bitvector.
The operands of the bitwise minus operation are not modified, instead a new bitvector object is generated.
References adjustSize(), all0s(), all1s(), copy(), flip(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().
void ibis::bitvector::operator-= | ( | const bitvector & | rhs | ) |
Perform bitwise subtraction (a & !b).
The in-place version of the bitwise minus (-) operator.
This bitvector is modified to store the result of the operation.
References adjustSize(), all0s(), all1s(), bytes(), ibis::util::copy(), ibis::gVerbose, ibis::array_t< T >::size(), and size().
const ibis::bitvector & ibis::bitvector::operator= | ( | const bitvector & | bv | ) | [inline] |
The assignment operator.
Use deep copy. Wanted to use shallow copy for efficiency considerations, but SHALLOW copy causes unexpected problem in test program bitty.cpp.
ibis::bitvector * ibis::bitvector::operator^ | ( | const bitvector & | rhs | ) | const |
Perform bitwise XOR and return the result as a new bitvector.
This bitvector is not modified, instead a new bitvector object is generated to store the result.
References adjustSize(), copy(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().
void ibis::bitvector::operator^= | ( | const bitvector & | rhs | ) |
Perform bitwise exclusive or (XOR).
The in-place version of the bitwise XOR (^) operator.
This bitvector is modified to store the result.
References adjustSize(), bytes(), ibis::gVerbose, ibis::array_t< T >::size(), and size().
ibis::bitvector * ibis::bitvector::operator| | ( | const bitvector & | rhs | ) | const |
Perform bitwise OR and return the result as a new bitvector.
This bitvector is not modified, instead a new bitvector is generated.
References adjustSize(), all0s(), all1s(), copy(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().
void ibis::bitvector::operator|= | ( | const bitvector & | rhs | ) |
Perform bitwise OR.
The is the in-place version of the bitwise OR (|) operator.
This bitvector is modified to store the result of the operation.
References adjustSize(), all0s(), all1s(), bytes(), copy(), ibis::gVerbose, ibis::array_t< T >::size(), and size().
std::ostream & ibis::bitvector::print | ( | std::ostream & | o | ) | const |
The print function.
Print each word in bitvector on a line.
References ibis::gVerbose.
Referenced by ibis::query::sequentialScan().
double ibis::bitvector::randomSize | ( | word_t | nb, |
word_t | nc | ||
) | [inline, static] |
Compute the expected number of bytes required to store a random sequence.
The random bit sequence is to have nb
total bits and nc
bits of one.
Referenced by ibis::query::evaluate().
void ibis::bitvector::read | ( | const char * | fn | ) |
Read a bit vector from the file.
Purge current contents before read.
References ibis::fileManager::getFile(), ibis::gVerbose, and ibis::fileManager::instance().
Referenced by ibis::blob::append(), ibis::column::append(), bitvector(), ibis::part::part(), and ibis::query::readHits().
void ibis::bitvector::reserve | ( | unsigned | nb, |
unsigned | nc, | ||
double | cf = 0.0 |
||
) |
Reserve enough space for a bit vector.
The caller needs to specify the number of total bits, nb, and the number of set bits, nc. The caller may additional specify the clustering factor, cf, if there is a reasonable estimate for it.
References ibis::gVerbose.
Referenced by ibis::part::doComp(), ibis::part::doCompare(), ibis::part::doScan(), ibis::part::negativeCompare(), ibis::column::searchSortedICD(), and ibis::column::searchSortedOOCD().
void ibis::bitvector::set | ( | int | val, |
word_t | n | ||
) |
Create a vector with n
bits of value val
(cf.
memset()).
val
must be either 0 or 1. References ibis::util::clear().
Referenced by ibis::index::addBins(), ibis::index::addBits(), ibis::direkte::append(), ibis::relic::append(), ibis::category::append(), ibis::bord::append(), ibis::bord::backup(), ibis::bin::binning(), ibis::bin::binningT(), ibis::bord::bord(), ibis::bundles::bundles(), ibis::colStrings::colStrings(), ibis::bin::construct(), ibis::egale::construct(), ibis::part::doComp(), ibis::part::doComp0(), ibis::part::doCompare(), ibis::countQuery::doEstimate(), ibis::query::doEstimate(), ibis::countQuery::doEvaluate(), ibis::query::doEvaluate(), ibis::countQuery::doScan(), ibis::part::doScan(), ibis::query::doScan(), ibis::direkte::estimate(), ibis::bin::estimate(), ibis::query::estimate(), ibis::index::estimate(), ibis::slice::estimate(), ibis::range::estimate(), ibis::mesa::estimate(), ibis::ambit::estimate(), ibis::pale::estimate(), ibis::pack::estimate(), ibis::zone::estimate(), ibis::fuge::estimate(), ibis::egale::estimate(), ibis::moins::estimate(), ibis::entre::estimate(), ibis::part::estimateMatchAny(), ibis::part::estimateRange(), ibis::column::estimateRange(), ibis::direkte::evaluate(), ibis::relic::evaluate(), ibis::bin::evaluate(), ibis::slice::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::fuzz::evaluate(), ibis::range::evaluate(), ibis::bylt::evaluate(), ibis::mesa::evaluate(), ibis::zona::evaluate(), ibis::column::evaluateAndSelect(), ibis::part::evaluateRange(), ibis::column::evaluateRange(), ibis::bord::evaluateTerms(), ibis::part::get1DBins(), ibis::part::get2DBins(), ibis::part::get3DBins(), ibis::part::getDistribution(), ibis::column::getNullMask(), ibis::bord::groupbyc(), ibis::index::initBitmaps(), ibis::roster::locate(), ibis::part::lookforString(), ibis::index::mapValues(), ibis::bak::mapValues(), ibis::bak2::mapValues(), ibis::part::matchAny(), ibis::part::negativeCompare(), ibis::part::negativeScan(), ibis::tafel::normalize(), ibis::part::part(), ibis::category::patternSearch(), ibis::part::patternSearch(), ibis::keywords::readTermDocFile(), ibis::query::removeComplexConditions(), ibis::keywords::search(), ibis::column::searchSortedICC(), ibis::column::searchSortedOOCC(), ibis::text::stringSearch(), ibis::category::stringSearch(), ibis::bord::column::stringSearch(), subset(), ibis::index::sumBins(), ibis::index::sumBits(), ibis::bin::undecidable(), ibis::range::undecidable(), ibis::mesa::undecidable(), ibis::ambit::undecidable(), ibis::pale::undecidable(), ibis::pack::undecidable(), ibis::zone::undecidable(), ibis::egale::undecidable(), ibis::tafel::write(), and ibis::bord::xgroupby().
void ibis::bitvector::setBit | ( | const word_t | i, |
int | val | ||
) |
Replace a single bit at position i
with val.
If the value of val is not 0, it is assumed to be 1. This function can be used to extend the length of the bit sequence. When the given index (ind) is beyond the end of the current sequence, the unspecified bits in the range of [size(), ind) are assumed to be 0.
This function may uncompress the object if the bit to be changed is in the middle of a long bitvector. This is to improve the speed of operation at the cost of some additional space. The bitvector is considered long if the cube of the number of words is more than the number of bits in the bitvector.
References ibis::gVerbose.
Referenced by ibis::part::doComp(), ibis::part::doCompare(), ibis::part::doScan(), ibis::part::evaluateRIDSet(), ibis::bord::column::keywordSearch(), ibis::roster::locate(), ibis::index::mapValues(), ibis::bak::mapValues(), ibis::bak2::mapValues(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::part::numbersToBitvector(), ibis::keywords::parseTextFile(), ibis::column::searchSortedICD(), ibis::column::searchSortedOOCD(), ibis::keywords::setBits(), ibis::text::stringSearch(), and ibis::bord::column::stringSearch().
ibis::bitvector::word_t ibis::bitvector::sloppyCount | ( | ) | const [inline] |
Provide a sloppy count of the number of bits that are 1.
If it returns 0, this bit vector has NO bits that are 1, otherwise, there might be some bits that are 1. However, the return value not equaling to 0 does not necessarily mean there are actually no bit that is 1. It simply means that we can not determine whether all bits are 0 without additional work. This is a sloppy version of count, it only checks the active word and the first one regular word and therefore should be very cheap to run. This function is more useful for situations where one wants to detect an empty bit vector.
Referenced by ibis::bundle1::bundle1(), ibis::part::doComp(), ibis::part::doComp0(), ibis::part::doCompare(), ibis::countQuery::doEstimate(), ibis::query::doEstimate(), ibis::countQuery::doEvaluate(), ibis::query::doEvaluate(), ibis::countQuery::doScan(), ibis::part::doScan(), ibis::query::doScan(), ibis::column::estimateRange(), ibis::query::evaluate(), ibis::column::evaluateRange(), ibis::part::evaluateRIDSet(), ibis::part::matchAny(), ibis::part::negativeCompare(), ibis::part::negativeScan(), ibis::category::patternSearch(), ibis::part::patternSearch(), ibis::column::searchSorted(), ibis::column::searchSortedICC(), ibis::column::searchSortedOOCC(), and ibis::category::stringSearch().
void ibis::bitvector::sloppySize | ( | word_t | n | ) | const [inline] |
Explicitly set the size of the bitvector.
This is intended to be used by indexing functions to avoid counting the number of bits. Caller is responsible for ensuring the size assigned is actually correct. It does not affect the number of bits actually represented by this data structure. To change the number of bits represented by this data structure use the function adjustSize instead.
References adjustSize(), and ibis::gVerbose.
Referenced by ibis::index::initBitmaps().
void ibis::bitvector::subset | ( | const bitvector & | mask, |
ibis::bitvector & | res | ||
) | const |
Select a subset of the bits.
Bits whose positions are marked 1 in mask are put together to form a new bitvector res
.
References appendFill(), appendWord(), clear(), cnt(), ibis::gVerbose, set(), and size().
Referenced by ibis::column::saveSelected(), and ibis::text::writeStrings().
void ibis::bitvector::write | ( | array_t< word_t > & | arr | ) | const |
Write the bit vector to an array_t<word_t>.
The serialize version of the bit vector may be passed to another I/O function or sent through networks.
References ibis::array_t< T >::push_back(), ibis::array_t< T >::reserve(), and ibis::array_t< T >::resize().
![]() |