Classes | Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Friends
ibis::bitvector64 Class Reference

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

#include <bitvector64.h>

List of all members.

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 uint64_t word_t
 The basic unit of data storage is 64-bit.

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
 bitvector64 (const array_t< word_t > &arr)
 bitvector64 (const char *file)
 Read the content of the named file.
 bitvector64 (const bitvector64 &bv)
word_t bytes () const throw ()
 Return the number of bytes used by the bitvector object in memory.
void clear ()
 Remove the existing content of a bitvector64.
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.
bitvector64copy (const bitvector64 &bv)
void decompress ()
 Turn all fill words into literal words.
const_iterator end () const
iterator end ()
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.
word_t getSerialSize () const throw ()
 Compute the number of words in serialized version of the bitvector object.
word_t numFillWords () const
 Return the number of fill words.
bitvector64operator& (const bitvector64 &) const
 Perform bitwise AND, return the pointer to the result.
void operator&= (const bitvector64 &rhs)
 Perform bitwise AND between this bitvector64 and rhs.
bitvector64operator+= (const bitvector64 &bv)
 Append a bitvector64.
bitvector64operator+= (int b)
 Append a single bit.
bitvector64operator- (const bitvector64 &) const
 Perform bitwise subtraction and return the pointer to the result.
void operator-= (const bitvector64 &rhs)
 Perform bitwise subtraction (a & !b).
bitvector64operator= (const bitvector64 &bv)
int operator== (const bitvector64 &rhs) const
 Return 1 if two bit sequences have the same content, 0 otherwise.
bitvector64operator^ (const bitvector64 &) const
 Perform bitwise XOR, return the pointer to the result.
void operator^= (const bitvector64 &rhs)
 Perform bitwise exclusive or (XOR).
bitvector64operator| (const bitvector64 &) const
 Perform bitwise OR, return the pointer to the result.
void operator|= (const bitvector64 &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 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.
word_t size () const throw ()
 Return the total number of bits in the bit sequence.
bitvector64swap (bitvector64 &bv)
void write (array_t< word_t > &arr) const
 Write the bit vector to an array_t<word_t>.
void write (FILE *fptr) const
void write (const char *fn) const
 Write the bit vector to a file.

Static Public Member Functions

static unsigned bitsPerLiteral ()
 Return the number of bits in a literal word.
static double clusteringFactor (word_t nb, word_t nc, word_t nw)
 Estimate clustering factor based on the size.
static double markovSize (word_t nb, word_t nc, double f)
 Compute the expected size (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?
bool all1s () const
 Are all bits in regular words 1?
bool isCompressed () const

Friends

struct active_word
class const_iterator
class indexSet
class iterator
struct run

Detailed Description

A data structure to represent a sequence of bits.

The 64-bit version.

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

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


Member Function Documentation

void ibis::bitvector64::adjustSize ( word_t  nv,
word_t  nt 
)

Adjust the size of the bit sequence.

If current size is less than nv, append enough 1 bits 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. The final result always contains nt bits.

Referenced by ibis::part::evaluateJoin(), ibis::util::outerProduct(), and ibis::util::outerProductUpper().

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

Append a WAH word.

Append a WAH compressed word.

The general case, active word may not be empty.

Referenced by erase().

double ibis::bitvector64::clusteringFactor ( word_t  nb,
word_t  nc,
word_t  nw 
) [static]

Estimate clustering factor based on the size.

See also:
markovSize.

References ibis::gVerbose.

ibis::bitvector64 & ibis::bitvector64::copy ( const bitvector64 bv) [inline]
Note:
Deep copy.

Referenced by operator&(), operator&=(), operator-(), operator|(), and operator|=().

void ibis::bitvector64::decompress ( )

Turn all fill words into literal words.

References ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and ibis::array_t< T >::swap().

word_t ibis::bitvector64::getSerialSize ( ) const throw () [inline]

Compute the number of words in serialized version of the bitvector object.

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

double ibis::bitvector64::markovSize ( word_t  nb,
word_t  nc,
double  f 
) [inline, static]

Compute the expected size (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.

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

ibis::bitvector64 * ibis::bitvector64::operator& ( const bitvector64 rhs) const

Perform bitwise AND, return the pointer to the result.

See also:
ibis::bitvector::operator&

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

void ibis::bitvector64::operator&= ( const bitvector64 rhs)

Perform bitwise AND between this bitvector64 and rhs.

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

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

ibis::bitvector64 * ibis::bitvector64::operator- ( const bitvector64 rhs) const

Perform bitwise subtraction and return the pointer to the result.

See also:
ibis::bitvector::operator-

References all0s(), all1s(), copy(), flip(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().

void ibis::bitvector64::operator-= ( const bitvector64 rhs)

Perform bitwise subtraction (a & !b).

See also:
ibis::bitvector::operator-=

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

ibis::bitvector64 & ibis::bitvector64::operator= ( const bitvector64 bv) [inline]
Note:
Deep copy.
ibis::bitvector64 * ibis::bitvector64::operator^ ( const bitvector64 rhs) const

Perform bitwise XOR, return the pointer to the result.

See also:
ibis::bitvector::operator^=

References ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and size().

void ibis::bitvector64::operator^= ( const bitvector64 rhs)

Perform bitwise exclusive or (XOR).

See also:
ibis::bitvector::operator^=

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

ibis::bitvector64 * ibis::bitvector64::operator| ( const bitvector64 rhs) const

Perform bitwise OR, return the pointer to the result.

See also:
ibis::bitvector::operator|

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

void ibis::bitvector64::operator|= ( const bitvector64 rhs)

Perform bitwise OR.

See also:
ibis::bitvector::operator|=

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

double ibis::bitvector64::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.

void ibis::bitvector64::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 bitvector64().

void ibis::bitvector64::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.

Referenced by ibis::index::estimate(), ibis::bin::estimate(), ibis::part::evaluateJoin(), and ibis::query::processJoin().

void ibis::bitvector64::setBit ( const word_t  i,
int  val 
)

Replace a single bit at position i.

Note:
val must be either 0 or 1.

References ibis::gVerbose.

Referenced by ibis::part::evaluateJoin(), ibis::util::outerProduct(), and ibis::util::outerProductUpper().


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

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive