SparseBitmap Class Reference

SparseBitmap is an example of how to create a page-based persistent data structure using Fennel. More...

List of all members.

Public Member Functions
	SparseBitmap (fennel::SegmentAccessor segmentAccessor, fennel::PageId dirPageId=fennel::NULL_PAGE_ID)
	Creates a new empty sparse bitmap (or loads an existing one).
virtual	~SparseBitmap ()
	Sparse bitmap destructor.
bool	getBit (SparseBitmapOffset iOffset)
	Reads a bit from the bitmap.
void	setBit (SparseBitmapOffset iOffset, bool value)
	Writes a bit in the bitmap.
fennel::PageId	getDirPageId () const
	Returns: the location of the directory node for this bitmap
size_t	getBitsPerLeaf () const
	Returns: number of bits contained by each leaf node
size_t	getMaxDirectoryEntries () const
	Returns: maximum number of entries which can be contained by the directory node
Private Member Functions
fennel::PageId	searchDirectory (SparseBitmapDirLock &dirLock, SparseBitmapOffset iLeafStartOffset)
	Looks up a leaf node (based on its start offset) in the directory.
Private Attributes
fennel::SegmentAccessor	segmentAccessor
	Accessor for the segment storing the bitmap node pages.
fennel::PageId	dirPageId
	Location of bitmap directory node.
size_t	nBitsPerLeaf
	Number of bits contained by each leaf node; this is fixed based on segment page size after headers and footers have been subtracted off.
size_t	nDirEntriesMax
	Maximum number of entries which can be contained by the directory node; this is fixed based on segment page size after headers and footers have been subtracted off, and determines the total number of leaf pages which can be allocated.

---

Detailed Description

SparseBitmap is an example of how to create a page-based persistent data structure using Fennel.

It is only intended for educational purposes, not for real use.

Definition at line 142 of file SparseBitmapTest.cpp.

---

Constructor & Destructor Documentation

SparseBitmap::SparseBitmap	(	fennel::SegmentAccessor	segmentAccessor,
		fennel::PageId	dirPageId = fennel::NULL_PAGE_ID
	)			[explicit]

Creates a new empty sparse bitmap (or loads an existing one).

Parameters:

	segmentAccessor	accessor for the segment storing the bitmap node pages
	dirPageId	location of existing directory node to load, or NULL_PAGE_ID to create a new bitmap

Definition at line 237 of file SparseBitmapTest.cpp.

References ANON_PAGE_OWNER_ID, dirPageId, nBitsPerLeaf, nDirEntriesMax, SparseBitmapDirectory::nEntries, NULL_PAGE_ID, and segmentAccessor.

{
    segmentAccessor = segmentAccessorInit;
    dirPageId = dirPageIdInit;

    if (dirPageId == fennel::NULL_PAGE_ID) {
        // create new empty directory
        SparseBitmapDirLock dirLock;
        dirLock.accessSegment(segmentAccessor);
        dirPageId = dirLock.allocatePage(fennel::ANON_PAGE_OWNER_ID);
        SparseBitmapDirectory &dir = dirLock.getNodeForWrite();
        dir.nEntries = 0;
    }

    // precompute some limits based on page and header sizes
    size_t cbPage = segmentAccessor.pSegment->getUsablePageSize();
    size_t nBytesPerLeaf = cbPage - sizeof(SparseBitmapLeaf);
    nBitsPerLeaf = nBytesPerLeaf * 8;
    assert(nBitsPerLeaf > 0);

    nDirEntriesMax =
        (cbPage - sizeof(SparseBitmapDirectory)) / sizeof(SparseBitmapDirEntry);
    assert(nDirEntriesMax > 0);
}

SparseBitmap::~SparseBitmap

(

)

[virtual]

Sparse bitmap destructor.

Definition at line 264 of file SparseBitmapTest.cpp.

{
}

---

Member Function Documentation

fennel::PageId SparseBitmap::searchDirectory	(	SparseBitmapDirLock &	dirLock,
		SparseBitmapOffset	iLeafStartOffset
	)			[private]

Looks up a leaf node (based on its start offset) in the directory.

Parameters:

	dirLock	page guard for directory node, which must already be locked in the desired mode
	iLeafStartOffset	leaf node start offset to search for

Returns:

location of leaf node, or NULL_PAGE_ID if not found

Definition at line 268 of file SparseBitmapTest.cpp.

References SparseBitmapDirectory::getEntriesForRead(), SparseBitmapDirEntry::iLeafStartOffset, SparseBitmapDirEntry::leafId, SparseBitmapDirectory::nEntries, and NULL_PAGE_ID.

Referenced by getBit(), and setBit().

{
    SparseBitmapDirectory const &dir = dirLock.getNodeForRead();

    SparseBitmapDirEntry const *pFirst = dir.getEntriesForRead();
    SparseBitmapDirEntry const *pLast = pFirst + dir.nEntries;
    SparseBitmapDirEntry const *pFound =
        std::find_if(
            pFirst,
            pLast,
            boost::bind(&SparseBitmapDirEntry::iLeafStartOffset, _1)
            == iLeafStartOffset);
    if (pFound == pLast) {
        return fennel::NULL_PAGE_ID;
    }
    return pFound->leafId;
}

bool SparseBitmap::getBit

(

SparseBitmapOffset

iOffset

)

Reads a bit from the bitmap.

Parameters:

iOffset

address of bit to read

Returns:

true iff bit is set

Definition at line 288 of file SparseBitmapTest.cpp.

References dirPageId, SparseBitmapLeaf::getBytesForRead(), SparseBitmapLeaf::iStartOffset, nBitsPerLeaf, NULL_PAGE_ID, searchDirectory(), and segmentAccessor.

Referenced by SparseBitmapTest::testBasic(), and SparseBitmapTest::testSpread().

{
    // Lock directory page in shared mode
    SparseBitmapDirLock dirLock;
    dirLock.accessSegment(segmentAccessor);
    dirLock.lockShared(dirPageId);

    // Compute start offset of leaf page containing iOffset
    SparseBitmapOffset iLeafStartOffset =
        (iOffset / nBitsPerLeaf) * nBitsPerLeaf;

    // Look for it in the directory
    fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset);
    if (leafId == fennel::NULL_PAGE_ID) {
        // Not in directory, so the bit is not set
        return false;
    }

    // Unlock directory node early since we don't need it any more
    dirLock.unlock();

    // Lock leaf page and perform sanity check
    SparseBitmapLeafLock leafLock;
    leafLock.accessSegment(segmentAccessor);
    leafLock.lockShared(leafId);
    SparseBitmapLeaf const &leaf = leafLock.getNodeForRead();
    assert(leaf.iStartOffset == iLeafStartOffset);

    // Read bit value from leaf
    fennel::PConstBuffer pBytes = leaf.getBytesForRead();
    size_t iBit = iOffset - iLeafStartOffset;
    size_t iByte = iBit / 8;
    size_t iBitInByte = iBit - 8 * iByte;
    if (pBytes[iByte] & (1 << iBitInByte)) {
        return true;
    } else {
        return false;
    }
}

void SparseBitmap::setBit	(	SparseBitmapOffset	iOffset,
		bool	value
	)

Writes a bit in the bitmap.

Parameters:

	iOffset	address of bit to write
	value	true to set bit; false to clear bit

Definition at line 328 of file SparseBitmapTest.cpp.

References ANON_PAGE_OWNER_ID, dirPageId, SparseBitmapLeaf::getBytesForWrite(), SparseBitmapDirectory::getEntriesForWrite(), SparseBitmapDirEntry::iLeafStartOffset, SparseBitmapLeaf::iStartOffset, SparseBitmapDirEntry::leafId, nBitsPerLeaf, nDirEntriesMax, SparseBitmapDirectory::nEntries, NULL_PAGE_ID, searchDirectory(), and segmentAccessor.

Referenced by SparseBitmapTest::testBasic(), SparseBitmapTest::testFullDirectory(), and SparseBitmapTest::testSpread().

{
    // Lock directory page in exclusive mode
    SparseBitmapDirLock dirLock;
    dirLock.accessSegment(segmentAccessor);
    dirLock.lockExclusive(dirPageId);

    // Search directory; if it already has a corresponding leaf entry,
    // we won't need to modify the directory
    SparseBitmapOffset iLeafStartOffset =
        (iOffset / nBitsPerLeaf) * nBitsPerLeaf;
    fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset);

    SparseBitmapLeafLock leafLock;
    leafLock.accessSegment(segmentAccessor);
    bool clearLeaf = false;
    if (leafId == fennel::NULL_PAGE_ID) {
        // Leaf doesn't exist yet:  we'll need a new one
        SparseBitmapDirectory &dir = dirLock.getNodeForWrite();
        if (dir.nEntries >= nDirEntriesMax) {
            // Oops, directory is full and we have no provisions
            // for splitting it; we haven't modified the directory yet,
            // so the bitmap remains intact
            throw std::runtime_error("SparseBitmap directory full");
        }
        // Allocate new leaf and add it to the directory
        SparseBitmapDirEntry *pLast =
            dir.getEntriesForWrite() + dir.nEntries;
        leafId = leafLock.allocatePage(fennel::ANON_PAGE_OWNER_ID);
        pLast->iLeafStartOffset = iLeafStartOffset;
        pLast->leafId = leafId;
        dir.nEntries++;
        clearLeaf = true;
        dirLock.unlock();
    } else {
        // Leaf already exists, so no need to modify directory;
        // we can unlock the directory early
        dirLock.unlock();
        leafLock.lockExclusive(leafId);
    }

    // Write bit value to leaf
    SparseBitmapLeaf &leaf = leafLock.getNodeForWrite();
    fennel::PBuffer pBytes = leaf.getBytesForWrite();
    if (clearLeaf) {
        // We're initializing a new leaf, so clear all the bits first
        leaf.iStartOffset = iLeafStartOffset;
        memset(pBytes, 0, nBitsPerLeaf / 8);
    }
    size_t iBit = iOffset - iLeafStartOffset;
    size_t iByte = iBit / 8;
    size_t iBitInByte = iBit - 8 * iByte;
    if (value) {
        pBytes[iByte] |= (1 << iBitInByte);
    } else {
        pBytes[iByte] &= ~(1 << iBitInByte);
    }
}

fennel::PageId SparseBitmap::getDirPageId

(

)

const

Returns:

the location of the directory node for this bitmap

Definition at line 387 of file SparseBitmapTest.cpp.

References dirPageId.

Referenced by SparseBitmapTest::testBasic(), and SparseBitmapTest::testSpread().

{
    return dirPageId;
}

size_t SparseBitmap::getBitsPerLeaf

(

)

const

Returns:

number of bits contained by each leaf node

Definition at line 392 of file SparseBitmapTest.cpp.

References nBitsPerLeaf.

Referenced by SparseBitmapTest::testFullDirectory(), and SparseBitmapTest::testSizes().

{
    return nBitsPerLeaf;
}

size_t SparseBitmap::getMaxDirectoryEntries

(

)

const

Returns:

maximum number of entries which can be contained by the directory node

Definition at line 397 of file SparseBitmapTest.cpp.

References nDirEntriesMax.

Referenced by SparseBitmapTest::testFullDirectory(), and SparseBitmapTest::testSizes().

{
    return nDirEntriesMax;
}

---

Member Data Documentation

fennel::SegmentAccessor SparseBitmap::segmentAccessor [private]

Accessor for the segment storing the bitmap node pages.

Definition at line 147 of file SparseBitmapTest.cpp.

Referenced by getBit(), setBit(), and SparseBitmap().

fennel::PageId SparseBitmap::dirPageId [private]

Location of bitmap directory node.

Definition at line 152 of file SparseBitmapTest.cpp.

Referenced by getBit(), getDirPageId(), setBit(), and SparseBitmap().

size_t SparseBitmap::nBitsPerLeaf [private]

Number of bits contained by each leaf node; this is fixed based on segment page size after headers and footers have been subtracted off.

Definition at line 159 of file SparseBitmapTest.cpp.

Referenced by getBit(), getBitsPerLeaf(), setBit(), and SparseBitmap().

size_t SparseBitmap::nDirEntriesMax [private]

Maximum number of entries which can be contained by the directory node; this is fixed based on segment page size after headers and footers have been subtracted off, and determines the total number of leaf pages which can be allocated.

Definition at line 167 of file SparseBitmapTest.cpp.

Referenced by getMaxDirectoryEntries(), setBit(), and SparseBitmap().

---

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

• /home/pub/open/dev/fennel/test/SparseBitmapTest.cpp

---