A data structure to represent a sequence of bits. More...

#include <bitvector.h>

Classes
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...

class	pit
	Iterate over the positive positions one at a time. More...

Public Types
typedef uint32_t	word_t

Public Member Functions
void	adjustSize (word_t nv, word_t nt)
	Adjust the size of the bit sequence. More...

void	appendByte (unsigned char)
	Append all 8 bits of the incoming bytes as literal bits.

void	appendFill (int val, word_t n)
	Append `n` bits of `val`. More...

void	appendWord (word_t w)
	Append a WAH word. More...

iterator	begin ()

const_iterator	begin () const

	bitvector ()
	Default constructor. Creates a new empty bitvector.

	bitvector (const bitvector &bv)
	Copy constructor. More...

	bitvector (const char *file)
	Constructor. Reconstruct a bitvector from a file.

	bitvector (const array_t< word_t > &arr)
	Construct a bitvector from an array. More...

	bitvector (const array_t< word_t > &arr, const size_t begin, const size_t end)
	Construct a bitvector from an array. More...

	bitvector (word_t *, size_t)
	Construct a bitvector from an array. More...

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. More...

word_t	cnt () const
	Return the number of bits that are one.

void	compress ()
	Compress the current m_vec in-place. More...

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 as 1 in mask. More...

word_t	count () const

void	decompress ()
	Decompress the currently compressed bitvector. More...

bool	empty () const
	Is the bitvector empty? For efficiency reasons, this funciton only works correctly on a properly compressed bitvector. More...

iterator	end ()

const_iterator	end () const

void	erase (word_t i, word_t j)
	Remove the bits in the range of [i, j). More...

indexSet	firstIndexSet () const

void	flip ()
	Complement all bits of a bit sequence. More...

int	getBit (const word_t i) const
	Return the value of a bit. More...

uint32_t	getSerialSize () const throw ()
	Compute the number of bytes in the serialized version of this bitvector object. More...

bool	isCompressed () const
	Does this bit vector use less space than the maximum? Return true if yes, otherwise false. More...

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. More...

void	operator&= (const bitvector &rhs)
	Perform bitwise AND between this bitvector and `rhs`. More...

bitvector &	operator+= (const bitvector &bv)
	Append a bitvector.

bitvector &	operator+= (int b)
	Append a single bit. The incoming value must be 0 or 1.

bitvector *	operator- (const bitvector &) const
	Perform bitwise subtraction and return the result as a new bitvector. More...

void	operator-= (const bitvector &rhs)
	Perform bitwise subtraction (a & !b). More...

bool	operator< (const bitvector &) const
	Provide an ordering among the bit vectors. More...

const bitvector &	operator= (const bitvector &bv)
	The assignment operator. More...

int	operator== (const bitvector &rhs) const
	Compare two bitvectors. More...

bitvector *	operator^ (const bitvector &) const
	Perform bitwise XOR and return the result as a new bitvector. More...

void	operator^= (const bitvector &rhs)
	Perform bitwise exclusive or (XOR). More...

bitvector *	operator\| (const bitvector &) const
	Perform bitwise OR and return the result as a new bitvector. More...

void	operator\|= (const bitvector &rhs)
	Perform bitwise OR. More...

std::ostream &	print (std::ostream &) const
	The print function. More...

void	read (const char *fn)
	Read a bit vector from the file. More...

void	reserve (unsigned nb, unsigned nc, double cf=0.0)
	Reserve enough space for a bit vector. More...

void	set (int val, word_t n)
	Create a vector with `n` bits of value `val` (cf. More...

void	setBit (const word_t i, int val)
	Replace a single bit at position `i` with val. More...

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. More...

void	sloppySize (word_t n) const
	Explicitly set the size of the bitvector. More...

void	subset (const bitvector &mask, bitvector &res) const
	Select a subset of the bits. More...

bitvector &	swap (bitvector &bv)

void	turnOnRawBit (const word_t i)
	Turn on a single bit in a uncompressed bitvector. More...

void	write (const char *fn) const
	Write the bit vector to a file. More...

void	write (int fdes) const
	Write to a file that is opened by the caller. More...

void	write (array_t< word_t > &arr) const
	Write the bit vector to an array_t<word_t>. More...

	~bitvector ()
	!< The basic unit of data storage. More...

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. More...

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. More...

static double	randomSize (word_t nb, word_t nc)
	Compute the expected number of bytes required to store a random sequence. More...

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. More...

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. More...

Friends
struct	active_word

class	const_iterator

class	indexSet

class	iterator

struct	run

Detailed Description

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.
When adding a bit with bitvector::operator+=, the integer value passed in must be one of 0 or 1. Since checking whether the import value is 0 or not 0 causes pipeline bubble in CPU, we have opted for not performing the check. An input value other than 0 or 1 will cause unrelated bits to be modified and producing an incorrect bitvector.

Constructor & Destructor Documentation

ibis::bitvector::~bitvector ( )

inline

!< The basic unit of data storage.

Destructor.

References ibis::util::clear().

ibis::bitvector::bitvector ( const bitvector & bv )

Copy constructor.

The underlying storage (m_vec) is constructed through a copy constructor as well.

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::array_t< T >::pop_back(), and ibis::array_t< T >::size().

ibis::bitvector::bitvector	(	const array_t< word_t > &	arr,
		const size_t	begin,
		const size_t	end
	)

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::array_t< T >::pop_back(), and ibis::array_t< T >::size().

ibis::bitvector::bitvector	(	word_t *	buf,
		size_t	nbuf
	)

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::array_t< T >::pop_back(), and ibis::array_t< T >::size().

Member Function Documentation

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.

Referenced by ibis::index::addBins(), ibis::bin::adjustLength(), ibis::blob::append(), ibis::tafel::append(), ibis::category::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::query::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::bak2::mapValues(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::part::negativeScan(), 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::hyperslab::tobitvector(), ibis::column::truncateData(), ibis::part::writeColumn(), ibis::blob::writeData(), ibis::column::writeData(), ibis::part::writeOpaques(), ibis::part::writeRaw(), ibis::text::writeStrings(), and ibis::part::writeStrings().

bool ibis::bitvector::all0s ( ) const

inlineprotected

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

inlineprotected

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

Referenced by ibis::tafel::append(), ibis::tafel::appendString(), erase(), ibis::column::evaluateRange(), ibis::bord::column::evaluateRange(), ibis::mensa::cursor::fillBuffer(), ibis::index::mapValues(), ibis::bin::mergeValues(), ibis::part::numbersToBitvector(), ibis::column::searchSortedICC(), ibis::column::searchSortedOOCC(), subset(), and ibis::hyperslab::tobitvector().

void ibis::bitvector::appendWord ( word_t w )

Append a WAH word.

The incoming argument w is assumed to be a WAH compressed word.

Referenced by erase(), and subset().

void ibis::bitvector::clear ( )

Remove the existing content of a bitvector.

The underlying storage is not released until the object is actual freed.

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.

See also: markovSize.

Referenced by ibis::query::evaluate(), ibis::query::processJoin(), ibis::relic::speedTest(), and ibis::bin::speedTest().

void ibis::bitvector::compress ( )

Compress the current m_vec in-place.

It may reduces storage requirement by merging fills into fill words.

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(), ibis::part::reorderBitmap(), 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 as 1 in mask.

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 ( )

Decompress the currently compressed bitvector.

It turns all fill words into literal words. Throws an ibis::bad_alloc exception if it fails to allocate enough memory.

References 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::part::reorderBitmap(), 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.

Referenced by ibis::text::readStrings1().

void ibis::bitvector::erase	(	word_t	i,
		word_t	j
	)

Remove the bits in the range of [i, j).

The bit positions are counted from 0. The first position i is erased, but not the last position j.

References appendFill(), appendWord(), ibis::array_t< T >::push_back(), and size().

void ibis::bitvector::flip ( )

Complement all bits of a bit sequence.

Toggle every bit of the bit sequence

If nbits is not set, set it while flipping the bits.

Referenced by ibis::countQuery::doEstimate(), ibis::query::doEstimate(), ibis::countQuery::doEvaluate(), ibis::query::doEvaluate(), ibis::query::doScan(), ibis::skive::estimate(), ibis::range::estimate(), ibis::ambit::estimate(), ibis::pack::estimate(), ibis::egale::estimate(), ibis::moins::estimate(), ibis::entre::estimate(), ibis::skive::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::range::evaluate(), ibis::column::evaluateRange(), operator-(), ibis::index::sumBins(), and ibis::index::sumBits().

int ibis::bitvector::getBit ( const word_t i ) const

Return the value of a bit.

Note: If the incoming position is beyond the end of this bitmap, this function returns 0.

Warning: To access the ith bit, this function essentially has to determine the values of bits 0 through i-1, therefore, it is highly recommended that you don't use this function. A compressed bitmap data structure is simply not the right data structure to support random accesses!

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
	)

inlinestatic

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.

Note: The caller is responsible for deleting the bitvector returned.

See also: ibis::bitvector::operator&=

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.

Note: If the two bit vectors are not of the same length, the shorter one is implicitly padded with 0 bits so the two are of the same length.

References adjustSize(), all0s(), all1s(), bytes(), copy(), 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.

See also: ibis::bitvector::operator&

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.

See also: ibis::bitvector::operator&=

References adjustSize(), all0s(), all1s(), bytes(), ibis::util::copy(), ibis::array_t< T >::size(), and size().

bool ibis::bitvector::operator< ( const bitvector & rhs ) const

Provide an ordering among the bit vectors.

The comparison proceeds in three stages:

the bit vector with fewer total number of bits, as represented by the function size, will be declared "smaller";
for two bit vectors with the same number of bits, the one with fewer 1s is declared as "smaller";
for two bit vectors with the same number of bits and the same number of 1s, the actual bit values are compared one bit at a time, in which case, a bit of 0 is considered as smaller than a bit of 1.

Note that it is fine to compare two bit vectors that are compressed differently. However, it is generally more efficient to compare bit vectors that have been compressed properly.

References cnt(), 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.

int ibis::bitvector::operator== ( const bitvector & rhs ) const

Compare two bitvectors.

Return 1 if two bit sequences have the same content, 0 otherwise.

References ibis::array_t< T >::size().

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.

See also: ibis::bitvector::operator&

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.

See also: ibis::bitvector::operator&=

References adjustSize(), bytes(), 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.

See also: ibis::bitvector::operator&

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.

See also: ibis::bitvector::operator&=

References adjustSize(), all0s(), all1s(), bytes(), copy(), 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.

Referenced by ibis::query::sequentialScan().

double ibis::bitvector::randomSize	(	word_t	nb,
		word_t	nc
	)

inlinestatic

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. It purges the current contents first. If the name file does not exist or the reading operation fails for any reason, the existing content is lost.

References ibis::fileManager::getFile(), and ibis::fileManager::instance().

Referenced by ibis::blob::append(), ibis::column::append(), ibis::bord::backup(), 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.

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()).

Note: 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::bord::bord(), ibis::colBlobs::colBlobs(), ibis::colStrings::colStrings(), ibis::bord::column::column(), ibis::bin::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::keywords::estimate(), ibis::index::estimate(), ibis::skive::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::skive::evalEQ(), ibis::skive::evalGE(), ibis::direkte::evaluate(), ibis::relic::evaluate(), ibis::bin::evaluate(), ibis::skive::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::range::evaluate(), ibis::fuzz::evaluate(), ibis::mesa::evaluate(), ibis::bylt::evaluate(), ibis::zona::evaluate(), ibis::column::evaluateAndSelect(), ibis::part::evaluateRange(), ibis::column::evaluateRange(), ibis::bord::column::evaluateRange(), ibis::bord::evaluateTerms(), fastbit_iapi_extend_array(), ibis::part::get1DBins(), ibis::part::get2DBins(), ibis::part::get3DBins(), ibis::column::getNullMask(), ibis::bord::groupbyc(), ibis::index::initBitmaps(), ibis::part::keywordSearch(), ibis::roster::locate(), ibis::index::mapValues(), ibis::part::matchAny(), ibis::part::negativeCompare(), ibis::part::negativeScan(), ibis::tafel::normalize(), ibis::part::part(), ibis::category::patternSearch(), ibis::part::patternSearch(), ibis::query::removeComplexConditions(), ibis::part::reorderBitmap(), ibis::keywords::search(), ibis::column::searchSortedICC(), ibis::column::searchSortedOOCC(), ibis::text::stringSearch(), ibis::category::stringSearch(), ibis::part::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(), 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.

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::bak2::mapValues(), ibis::bin::mergeValues(), ibis::part::negativeCompare(), ibis::part::numbersToBitvector(), ibis::keywords::parseTextFile(), ibis::part::reorderBitmap(), 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::bord::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().

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(), set(), and size().

Referenced by ibis::column::saveSelected(), and ibis::text::writeStrings().

void ibis::bitvector::turnOnRawBit ( const word_t ind )

inline

Turn on a single bit in a uncompressed bitvector.

Warning: Use only if you are sure that the bitvector object represents a uncompressed bitmap!

Referenced by ibis::part::doComp0().

void ibis::bitvector::write ( const char * fn ) const

Write the bit vector to a file.

The existing content of the file will be overwritten.

Referenced by ibis::blob::append(), ibis::column::append(), ibis::part::deactivate(), ibis::column::getNullMask(), ibis::part::part(), ibis::part::reactivate(), ibis::part::reorder(), ibis::column::truncateData(), ibis::direkte::write(), and ibis::column::writeData().

void ibis::bitvector::write ( int out ) const

Write to a file that is opened by the caller.

It starts writing at the current file pointer position and overwrites existing content if there is any. The caller is responsible for openning the file and closing the file.

void ibis::bitvector::write ( array_t< word_t > & arr ) const

Write the bit vector to an array_t<word_t>.

The serialized version of this 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().

The documentation for this class was generated from the following files:

bitvector.h
bitvector.cpp



	Contact us Disclaimers FastBit source code FastBit mailing list archive

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation