LbmSegment Class Reference

Class implementing bitmap segments. More...

#include <LbmSegment.h>

Inheritance diagram for LbmSegment:

LbmEntry LbmRidReaderBase LbmSegmentReaderBase LbmIterableRidReader LbmRidReader LbmSegmentReader LbmSeqSegmentReader LbmTupleRidReader List of all members.

Public Member Functions

uint getZeroLengthByteCount (uint8_t segDescByte)
 Get the number of bytes to store the length of zero bytes.
LcsRid getStartRID ()
 
Returns:
startRID of this bitmap segment


Static Public Member Functions

static LcsRid roundToByteBoundary (LcsRid rid)
 Rounds a rid value down to the nearest byte boundary.
static bool setSegLength (uint8_t &segDescByte, uint segLen)
 Sets the length descriptor for a new segment with zero trailing zeros.
static bool adjustSegLength (uint8_t &segDescByte, uint segLen)
 Set segment length in an existing descriptor with the new segment length.
static uint getSegLength (uint8_t segDescByte)
 Get the segment length encoded in SegmentDescriptor.

Static Public Attributes

static const uint LbmOneByteSize = 8
 One byte in the bitmap encodes 8 RIDs.
static const uint LbmOneByteSizeBitShift = 3
static const LcsRidPrimitive LbmOneByteSizeBitMask

Protected Member Functions

uint computeSpaceForZeroBytes (uint nZeroBytes)
 Computes the number of bytes required to store a specified number of zero bytes.
uint computeSegLength (PBuffer segDesc)
 Computes the length of the remaining segments in the current bitmap segment, starting at the one specified by the input segment descriptor.
uint computeSegDescLength (PBuffer segDesc)
 Computes the length of the remaining segment descriptors in the current bitmap segment, starting at the one specified by the input segment descriptor.
uint countSegments ()
 Returns the number of segments in an entry.

Static Protected Member Functions

static uint byteArray2Value (PBuffer array, uint arraySize)
 Get value stored in a byte array.
static uint value2ByteArray (uint value, PBuffer array, uint arraySize)
 Store value in a byte array.
static void readSegDescAndAdvance (PBuffer &pSegDesc, uint &bmSegLen, uint &zeroBytes)
 Decodes the lengths stored in the descriptor for a segment, based on where the segment descriptor is currently pointing, and advances the segment descriptor to the next descriptor.

Protected Attributes

LcsRid startRID
 Starting rid in the bitmap segment (if singleton, startRID == RID column in entryTuple).
PBuffer pSegDescStart
 Increment forward from pSegDescStart.
PBuffer pSegDescEnd
PBuffer pSegStart
 Decrement backward from pSegStart.
PBuffer pSegEnd

Static Protected Attributes

static const uint LbmHalfByteSize = 4
 Use half of a byte to encode the segment length, or the zero bytes length.
static const uint8_t LbmSegLengthMask = 0xf0
 The upper 4 bits of Segment Descriptor byte is used to store the length of the corresponding segment.
static const uint8_t LbmZeroLengthMask = 0x0f
 The lower 4 bits of Segment Descriptor byte is used to store the length of the "gap" following the corresponding segment(till the next segment or the next LbmEntry).
static const uint LbmZeroLengthCompact = 12
 If the length of zero bytes(a byte composed of 8 bits of 0s) is less than 12, the length can be stored within the segment descriptor.
static const uint LbmZeroLengthExtended
 Additional bytes(maximumn is 3 bytes) in which the length is stored.
static const uint LbmMaxSegSize = 16
 Maximum size(in bytes) for a bitmap segment.

Detailed Description

Class implementing bitmap segments.

Bitmap segments consist of a starting rid value, a bitmap segment descriptor, and then the actual bitmap segments.

Definition at line 34 of file LbmSegment.h.

Member Function Documentation

uint LbmSegment::byteArray2Value ( PBuffer  array,
uint  arraySize 
) [static, protected]

Get value stored in a byte array.

The least significant bytes in the value is stored at the first location in the array.

Parameters:
array a byte array
arraySize size of the array(number of bytes)
Returns:
the value stored in this array.

Definition at line 27 of file LbmSegment.cpp.

References LbmOneByteSize.

Referenced by LbmEntry::adjustEntry(), LbmEntry::getCompressedRowCount(), and readSegDescAndAdvance().

00028 {
00029     uint value = 0;
00030     while (arraySize > 0) {
00031         value = value * (uint)(1 << LbmOneByteSize) + array[arraySize - 1];
00032         arraySize --;
00033     }
00034     return value;
00035 }

uint LbmSegment::value2ByteArray ( uint  value,
PBuffer  array,
uint  arraySize 
) [static, protected]

Store value in a byte array.

The least significant bytes in the value is stored at the first location in the array.

Parameters:
value 
array a byte array
arraySize size of the array(number of bytes)
Returns:
number of bytes used to store the value; 0 if the value requires more than arraySize bytes to store.

Definition at line 38 of file LbmSegment.cpp.

References LbmOneByteSize.

Referenced by LbmEntry::setZeroLength().

00039 {
00040     assert(value != 0);
00041 
00042     uint size = 0;
00043 
00044     while (value > 0 && size < arraySize) {
00045         array[size] = (uint8_t)(value & 0xff);
00046         value = value >> LbmOneByteSize;
00047         size ++;
00048     }
00049     /*
00050      * If value is non-zero, it means that the value cannot be encoded
00051      * within an array of arraySize. Return 0 in that case.
00052      */
00053     if (value > 0) {
00054         size = 0;
00055     }
00056 
00057     return size;
00058 }

uint LbmSegment::computeSpaceForZeroBytes ( uint  nZeroBytes  )  [protected]

Computes the number of bytes required to store a specified number of zero bytes.

Parameters:
nZeroBytes the number of zero bytes to be stored
Returns:
number of bytes required to store the zero bytes; if the length can be encoded in the segment descriptor, 0 is returned.

Definition at line 60 of file LbmSegment.cpp.

References LbmOneByteSize, and LbmZeroLengthCompact.

Referenced by LbmEntry::addNewAdjacentSegment(), LbmEntry::addNewMiddleSegment(), and computeSegDescLength().

00061 {
00062     if (nZeroBytes <= LbmZeroLengthCompact) {
00063         return 0;
00064     }
00065 
00066     uint size = 0;
00067     while (nZeroBytes > 0) {
00068         nZeroBytes = nZeroBytes >> LbmOneByteSize;
00069         size++;
00070     }
00071 
00072     return size;
00073 }

void LbmSegment::readSegDescAndAdvance ( PBuffer &  pSegDesc,
uint &  bmSegLen,
uint &  zeroBytes 
) [static, protected]

Decodes the lengths stored in the descriptor for a segment, based on where the segment descriptor is currently pointing, and advances the segment descriptor to the next descriptor.

Parameters:
pSegDesc pointer to segment descriptor
bmSegLen returns length of bitmap segment
zeroBytes returns number of trailing zeros in this segment
segment

Definition at line 75 of file LbmSegment.cpp.

References byteArray2Value(), LbmHalfByteSize, LbmZeroLengthCompact, and LbmZeroLengthMask.

Referenced by LbmSegmentReaderBase::advanceSegment(), computeSegDescLength(), computeSegLength(), LbmEntry::containsRid(), countSegments(), LbmEntry::dumpSeg(), LbmEntry::dumpSegRID(), LbmEntry::generateSegRIDs(), LbmEntry::spliceSingleton(), and LbmEntry::splitEntry().

00077 {
00078     // should only be called in the case where the bit segment has
00079     // a descriptor
00080     assert(pSegDesc != NULL);
00081     bmSegLen = (*pSegDesc >> LbmHalfByteSize) + 1;
00082     uint zeroLen = (*pSegDesc & LbmZeroLengthMask);
00083 
00084     // advance past the initial length byte
00085     pSegDesc++;
00086 
00087     if (zeroLen <= LbmZeroLengthCompact) {
00088         zeroBytes = zeroLen;
00089     } else {
00090         zeroBytes =
00091             byteArray2Value(pSegDesc, zeroLen - LbmZeroLengthCompact);
00092         pSegDesc += zeroLen - LbmZeroLengthCompact;
00093     }
00094 }

uint LbmSegment::computeSegLength ( PBuffer  segDesc  )  [protected]

Computes the length of the remaining segments in the current bitmap segment, starting at the one specified by the input segment descriptor.

Parameters:
segDesc segment descriptor of the first segment that we want to start computing the length from
Returns:
number of bytes occupied by the remaining segments in the current entry

Definition at line 110 of file LbmSegment.cpp.

References pSegDescEnd, and readSegDescAndAdvance().

Referenced by LbmEntry::addNewAdjacentSegment(), and LbmEntry::addNewMiddleSegment().

00111 {
00112     uint segLength = 0;
00113 
00114     while (segDesc < pSegDescEnd) {
00115         uint segBytes;
00116         uint zeroBytes;
00117         readSegDescAndAdvance(segDesc, segBytes, zeroBytes);
00118         segLength += segBytes;
00119     }
00120 
00121     return segLength;
00122 }

uint LbmSegment::computeSegDescLength ( PBuffer  segDesc  )  [protected]

Computes the length of the remaining segment descriptors in the current bitmap segment, starting at the one specified by the input segment descriptor.

Parameters:
segDesc segment descriptor of the first segment that we want to start computing the length from
Returns:
number of bytes occupied by the remaining segment descriptors in the current entry

Definition at line 96 of file LbmSegment.cpp.

References computeSpaceForZeroBytes(), pSegDescEnd, and readSegDescAndAdvance().

Referenced by LbmEntry::addNewAdjacentSegment(), and LbmEntry::addNewMiddleSegment().

00097 {
00098     uint segDescLength = 0;
00099 
00100     while (segDesc < pSegDescEnd) {
00101         uint segBytes;
00102         uint zeroBytes;
00103         readSegDescAndAdvance(segDesc, segBytes, zeroBytes);
00104         segDescLength += computeSpaceForZeroBytes(zeroBytes) + 1;
00105     }
00106 
00107     return segDescLength;
00108 }

uint LbmSegment::countSegments (  )  [protected]

Returns the number of segments in an entry.

Definition at line 124 of file LbmSegment.cpp.

References count(), pSegDescEnd, pSegDescStart, and readSegDescAndAdvance().

Referenced by LbmEntry::splitEntry().

00125 {
00126     uint count = 0;
00127 
00128     PBuffer segDesc = pSegDescStart;
00129     while (segDesc < pSegDescEnd) {
00130         uint segBytes;
00131         uint zeroBytes;
00132         readSegDescAndAdvance(segDesc, segBytes, zeroBytes);
00133         count++;
00134     }
00135 
00136     return count;
00137 }

LcsRid LbmSegment::roundToByteBoundary ( LcsRid  rid  )  [inline, static]

Rounds a rid value down to the nearest byte boundary.

Parameters:
rid value to be rounded
Returns:
rounded rid value

Definition at line 241 of file LbmSegment.h.

References LbmOneByteSizeBitMask, and opaqueToInt().

Referenced by LbmRidReaderBase::advanceToRid(), LbmEntry::closeCurrentSegment(), LbmEntryTest::compareExpected(), LbmSplicerExecStream::findBetterEntry(), LbmSplicerExecStream::findBTreeEntry(), LbmEntry::mergeEntry(), LbmEntry::openNewSegment(), LbmSplicerExecStream::ridOverlaps(), LbmRidReaderBase::searchForNextRid(), LbmEntry::setRIDAdjacentSegByte(), LbmEntry::singleton2Bitmap(), LbmEntryTest::testldb35(), and LbmEntryTest::testZeroBytes().

00242 {
00243     return LcsRid(opaqueToInt(rid) & LbmOneByteSizeBitMask);
00244 }

bool LbmSegment::setSegLength ( uint8_t &  segDescByte,
uint  segLen 
) [inline, static]

Sets the length descriptor for a new segment with zero trailing zeros.

Parameters:
segDescByte byte that will be set with the segment length
segLen length of the segment
Returns:
true if length can be encoded in a segment descriptor

Definition at line 246 of file LbmSegment.h.

References LbmHalfByteSize, and LbmMaxSegSize.

Referenced by LbmEntry::addNewMiddleSegment(), LbmEntry::addSegDesc(), LbmSegmentWriter::addSegment(), LbmEntry::closeCurrentSegment(), LbmEntry::openLastSegment(), LbmEntry::openNewSegment(), and LbmEntry::setRIDAdjacentSegByte().

00247 {
00248     if (segLen > LbmMaxSegSize) {
00249         return false;
00250     }
00251     segDescByte = (uint8_t) ((segLen - 1) << LbmHalfByteSize);
00252     return true;
00253 }

bool LbmSegment::adjustSegLength ( uint8_t &  segDescByte,
uint  segLen 
) [inline, static]

Set segment length in an existing descriptor with the new segment length.

Also, leaves the current zero trailing bytes count untouched

Parameters:
segDescByte segment descriptor byte to be modified
segLen new segment length
Returns:
true if length can be encoded in the segment descriptor

Definition at line 255 of file LbmSegment.h.

References LbmHalfByteSize, LbmMaxSegSize, and LbmSegLengthMask.

Referenced by LbmEntry::addNewAdjacentSegment().

00256 {
00257     if (segLen > LbmMaxSegSize) {
00258         return false;
00259     }
00260     segDescByte &= ~LbmSegLengthMask;
00261     segDescByte |= (uint8_t) ((segLen - 1) << LbmHalfByteSize);
00262     return true;
00263 }

uint LbmSegment::getSegLength ( uint8_t  segDescByte  )  [inline, static]

Get the segment length encoded in SegmentDescriptor.

Parameters:
segDescByte the seg desc byte with segment length encoded.

Definition at line 265 of file LbmSegment.h.

References LbmHalfByteSize, and LbmSegLengthMask.

Referenced by LbmEntry::addNewAdjacentSegment(), LbmEntry::getCompressedRowCount(), and LbmEntry::openLastSegment().

00266 {
00267     return (((segDescByte & LbmSegLengthMask) >> LbmHalfByteSize) + 1);
00268 }

uint LbmSegment::getZeroLengthByteCount ( uint8_t  segDescByte  )  [inline]

Get the number of bytes to store the length of zero bytes.

Parameters:
segDescByte the seg desc byte with length of zero bytes encoded.

Definition at line 270 of file LbmSegment.h.

References LbmZeroLengthCompact, and LbmZeroLengthMask.

Referenced by LbmEntry::openLastSegment(), and LbmEntry::splitEntry().

00271 {
00272     uint lengthBytes = segDescByte & LbmZeroLengthMask;
00273     if (lengthBytes > LbmZeroLengthCompact) {
00274         return (lengthBytes - LbmZeroLengthCompact);
00275     } else {
00276         return 0;
00277     }
00278 }

LcsRid LbmSegment::getStartRID (  )  [inline]

Returns:
startRID of this bitmap segment

Definition at line 280 of file LbmSegment.h.

References startRID.

00281 {
00282     return startRID;
00283 }

Member Data Documentation

LcsRid LbmSegment::startRID [protected]

Starting rid in the bitmap segment (if singleton, startRID == RID column in entryTuple).

Definition at line 42 of file LbmSegment.h.

Referenced by LbmEntry::adjustEntry(), LbmEntry::containsRid(), LbmSeqSegmentReader::getSrid(), getStartRID(), LbmEntry::growEntry(), LbmEntry::inRange(), LbmEntry::mergeEntry(), LbmEntry::mergeIntoSplitEntry(), LbmEntry::openLastSegment(), LbmEntry::produceEntryTuple(), LbmSegmentReaderBase::readBitmapSegTuple(), LbmEntry::setEntryTuple(), LbmEntry::singleton2Bitmap(), LbmEntry::spliceSingleton(), and LbmEntry::splitEntry().

PBuffer LbmSegment::pSegDescStart [protected]

Increment forward from pSegDescStart.

Definition at line 47 of file LbmSegment.h.

Referenced by LbmSegmentReaderBase::advanceSegment(), LbmSegmentReader::advanceToByte(), LbmEntry::containsRid(), countSegments(), LbmEntry::getRowCount(), LbmSegmentReaderBase::init(), LbmEntry::isSingleBitmap(), LbmEntry::LbmEntry(), LbmEntry::mergeIntoSplitEntry(), LbmEntry::produceEntryTuple(), LbmSegmentReaderBase::readBitmapSegTuple(), LbmSegmentReader::readSegment(), LbmSeqSegmentReader::readSegmentAndAdvance(), LbmEntry::setEntryTuple(), LbmEntry::singleton2Bitmap(), LbmEntry::spliceSingleton(), LbmEntry::splitEntry(), and LbmEntry::toString().

PBuffer LbmSegment::pSegDescEnd [protected]

Definition at line 48 of file LbmSegment.h.

Referenced by LbmEntry::addNewAdjacentSegment(), LbmEntry::addNewMiddleSegment(), LbmEntry::addSegDesc(), LbmSegmentReader::advanceToByte(), LbmEntry::closeCurrentSegment(), computeSegDescLength(), computeSegLength(), LbmEntry::containsRid(), LbmEntry::copyToMergeBuffer(), countSegments(), LbmEntry::getRowCount(), LbmSegmentReaderBase::init(), LbmEntry::mergeEntry(), LbmEntry::mergeIntoSplitEntry(), LbmEntry::openLastSegment(), LbmEntry::openNewSegment(), LbmEntry::produceEntryTuple(), LbmSegmentReaderBase::readBitmapSegTuple(), LbmSeqSegmentReader::readSegmentAndAdvance(), LbmEntry::setEntryTuple(), LbmEntry::spliceSingleton(), LbmEntry::splitEntry(), and LbmEntry::toString().

PBuffer LbmSegment::pSegStart [protected]

Decrement backward from pSegStart.

Definition at line 53 of file LbmSegment.h.

Referenced by LbmEntry::adjustEntry(), LbmSegmentReaderBase::advanceSegment(), LbmSegmentReader::advanceToByte(), LbmEntry::containsRid(), LbmSegmentReaderBase::init(), LbmEntry::isSingleton(), LbmEntry::LbmEntry(), LbmEntry::mergeEntry(), LbmEntry::mergeIntoSplitEntry(), LbmEntry::openNewSegment(), LbmEntry::produceEntryTuple(), LbmSegmentReaderBase::readBitmapSegTuple(), LbmSegmentReader::readCurrentByteSegment(), LbmSeqSegmentReader::readSegmentAndAdvance(), LbmEntry::setEntryTuple(), LbmEntry::setRIDAdjacentSegByte(), LbmEntry::spliceSingleton(), LbmEntry::splitEntry(), and LbmEntry::toString().

PBuffer LbmSegment::pSegEnd [protected]

Definition at line 54 of file LbmSegment.h.

Referenced by LbmEntry::addNewRid(), LbmEntry::adjustEntry(), LbmEntry::containsRid(), LbmEntry::copyToMergeBuffer(), LbmEntry::isSingleton(), LbmEntry::mergeEntry(), LbmEntry::mergeIntoSplitEntry(), LbmEntry::openLastSegment(), LbmEntry::openNewSegment(), LbmEntry::produceEntryTuple(), LbmEntry::setEntryTuple(), LbmEntry::setRIDAdjacentSegByte(), LbmEntry::splitEntry(), and LbmEntry::toString().

const uint LbmSegment::LbmHalfByteSize = 4 [static, protected]

Use half of a byte to encode the segment length, or the zero bytes length.

Definition at line 60 of file LbmSegment.h.

Referenced by LbmEntry::adjustEntry(), adjustSegLength(), getSegLength(), readSegDescAndAdvance(), and setSegLength().

const uint8_t LbmSegment::LbmSegLengthMask = 0xf0 [static, protected]

The upper 4 bits of Segment Descriptor byte is used to store the length of the corresponding segment.

Definition at line 66 of file LbmSegment.h.

Referenced by adjustSegLength(), and getSegLength().

const uint8_t LbmSegment::LbmZeroLengthMask = 0x0f [static, protected]

The lower 4 bits of Segment Descriptor byte is used to store the length of the "gap" following the corresponding segment(till the next segment or the next LbmEntry).

Definition at line 73 of file LbmSegment.h.

Referenced by LbmEntry::addNewAdjacentSegment(), LbmEntry::adjustEntry(), LbmEntry::getCompressedRowCount(), getZeroLengthByteCount(), readSegDescAndAdvance(), LbmEntry::setZeroLength(), and LbmEntry::splitEntry().

const uint LbmSegment::LbmZeroLengthCompact = 12 [static, protected]

If the length of zero bytes(a byte composed of 8 bits of 0s) is less than 12, the length can be stored within the segment descriptor.

Otherwise, the segment descriptor gives the length of additional bytes(maximumn is 3 bytes) in which the length is stored.

Definition at line 81 of file LbmSegment.h.

Referenced by LbmEntry::adjustEntry(), computeSpaceForZeroBytes(), LbmEntry::getCompressedRowCount(), getZeroLengthByteCount(), readSegDescAndAdvance(), and LbmEntry::setZeroLength().

const uint LbmSegment::LbmZeroLengthExtended [static, protected]

Initial value:

        (uint)LbmZeroLengthMask - LbmZeroLengthCompact
Additional bytes(maximumn is 3 bytes) in which the length is stored.

It is stored with an offset of LbmZeroLengthCompact. LbmZeroLengthExtended = (uint)LbmZeroLengthMask - LbmZeroLengthCompact.

Definition at line 88 of file LbmSegment.h.

Referenced by LbmEntry::getScratchBufferSize(), LbmEntry::init(), and LbmEntry::setZeroLength().

const uint LbmSegment::LbmMaxSegSize = 16 [static, protected]

Maximum size(in bytes) for a bitmap segment.

This size is limited by the number of bits(=4 bits) in SegDesc to describe the segment length.

Definition at line 95 of file LbmSegment.h.

Referenced by LbmEntry::addSegDesc(), adjustSegLength(), LbmEntry::closeCurrentSegment(), LbmEntry::getMaxBitmapSize(), LbmEntry::getMergeSpaceRequired(), LbmEntry::setRIDAdjacentSegByte(), and setSegLength().

const uint LbmSegment::LbmOneByteSize = 8 [static]

One byte in the bitmap encodes 8 RIDs.

Definition at line 235 of file LbmSegment.h.

Referenced by LbmEntry::addNewAdjacentSegment(), LbmEntry::addNewMiddleSegment(), LbmEntry::addNewRid(), LbmEntry::addNewSegment(), LbmSegmentWriter::addSegment(), LbmEntry::adjustEntry(), LbmRidReaderBase::advanceToRid(), byteArray2Value(), LbmMinusExecStream::canSkipMinus(), LbmEntry::closeCurrentSegment(), LbmUnionExecStream::computeRidLimit(), computeSpaceForZeroBytes(), LbmEntry::containsRid(), LbmEntry::dumpSegRID(), LbmMinusExecStream::execute(), LbmSplicerExecStream::findBetterEntry(), LbmEntryTest::generateBitmaps(), LbmEntryTest::generateCompressedBitmaps(), LbmEntry::generateSegRIDs(), LbmEntryTest::generateSingleBitmaps(), LbmEntry::getCompressedRowCount(), LbmEntry::getRowCount(), LbmIntersectExecStream::intersectSegments(), LbmMinusExecStream::minusSegments(), LbmEntry::openLastSegment(), LbmSegmentReaderBase::readBitmapSegTuple(), LbmSplicerExecStream::ridOverlaps(), LbmRidReaderBase::searchForNextRid(), LbmEntry::segmentContainsRid(), LbmSegmentReaderBase::setBitsRead(), LbmEntry::setEntryTuple(), LbmEntry::setRID(), LbmEntry::setRIDAdjacentSegByte(), LbmEntry::setRIDSegByte(), LbmEntry::spliceSingleton(), LbmEntry::splitEntry(), LbmEntryTest::testldb35(), LbmEntryTest::testler5920(), LbmEntryTest::testZeroBytes(), and value2ByteArray().

const uint LbmSegment::LbmOneByteSizeBitShift = 3 [static]

Definition at line 236 of file LbmSegment.h.

Referenced by byteNumberToRid(), and ridToByteNumber().

const LcsRidPrimitive LbmSegment::LbmOneByteSizeBitMask [static]

Initial value:

        0xfffffffffffffff8ULL

Definition at line 237 of file LbmSegment.h.

Referenced by roundToByteBoundary().

The documentation for this class was generated from the following files:
Generated on Mon Jun 22 04:00:35 2009 for Fennel by  doxygen 1.5.1