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 |
| |
size_t | getBitsPerLeaf () const |
| |
size_t | getMaxDirectoryEntries () const |
| |
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. |
It is only intended for educational purposes, not for real use.
Definition at line 142 of file SparseBitmapTest.cpp.
SparseBitmap::SparseBitmap | ( | fennel::SegmentAccessor | segmentAccessor, | |
fennel::PageId | dirPageId = fennel::NULL_PAGE_ID | |||
) | [explicit] |
Creates a new empty sparse bitmap (or loads an existing one).
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.
00240 { 00241 segmentAccessor = segmentAccessorInit; 00242 dirPageId = dirPageIdInit; 00243 00244 if (dirPageId == fennel::NULL_PAGE_ID) { 00245 // create new empty directory 00246 SparseBitmapDirLock dirLock; 00247 dirLock.accessSegment(segmentAccessor); 00248 dirPageId = dirLock.allocatePage(fennel::ANON_PAGE_OWNER_ID); 00249 SparseBitmapDirectory &dir = dirLock.getNodeForWrite(); 00250 dir.nEntries = 0; 00251 } 00252 00253 // precompute some limits based on page and header sizes 00254 size_t cbPage = segmentAccessor.pSegment->getUsablePageSize(); 00255 size_t nBytesPerLeaf = cbPage - sizeof(SparseBitmapLeaf); 00256 nBitsPerLeaf = nBytesPerLeaf * 8; 00257 assert(nBitsPerLeaf > 0); 00258 00259 nDirEntriesMax = 00260 (cbPage - sizeof(SparseBitmapDirectory)) / sizeof(SparseBitmapDirEntry); 00261 assert(nDirEntriesMax > 0); 00262 }
SparseBitmap::~SparseBitmap | ( | ) | [virtual] |
fennel::PageId SparseBitmap::searchDirectory | ( | SparseBitmapDirLock & | dirLock, | |
SparseBitmapOffset | iLeafStartOffset | |||
) | [private] |
Looks up a leaf node (based on its start offset) in the directory.
dirLock | page guard for directory node, which must already be locked in the desired mode | |
iLeafStartOffset | leaf node start offset to search for |
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().
00271 { 00272 SparseBitmapDirectory const &dir = dirLock.getNodeForRead(); 00273 00274 SparseBitmapDirEntry const *pFirst = dir.getEntriesForRead(); 00275 SparseBitmapDirEntry const *pLast = pFirst + dir.nEntries; 00276 SparseBitmapDirEntry const *pFound = 00277 std::find_if( 00278 pFirst, 00279 pLast, 00280 boost::bind(&SparseBitmapDirEntry::iLeafStartOffset, _1) 00281 == iLeafStartOffset); 00282 if (pFound == pLast) { 00283 return fennel::NULL_PAGE_ID; 00284 } 00285 return pFound->leafId; 00286 }
bool SparseBitmap::getBit | ( | SparseBitmapOffset | iOffset | ) |
Reads a bit from the bitmap.
iOffset | address of bit to read |
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().
00289 { 00290 // Lock directory page in shared mode 00291 SparseBitmapDirLock dirLock; 00292 dirLock.accessSegment(segmentAccessor); 00293 dirLock.lockShared(dirPageId); 00294 00295 // Compute start offset of leaf page containing iOffset 00296 SparseBitmapOffset iLeafStartOffset = 00297 (iOffset / nBitsPerLeaf) * nBitsPerLeaf; 00298 00299 // Look for it in the directory 00300 fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset); 00301 if (leafId == fennel::NULL_PAGE_ID) { 00302 // Not in directory, so the bit is not set 00303 return false; 00304 } 00305 00306 // Unlock directory node early since we don't need it any more 00307 dirLock.unlock(); 00308 00309 // Lock leaf page and perform sanity check 00310 SparseBitmapLeafLock leafLock; 00311 leafLock.accessSegment(segmentAccessor); 00312 leafLock.lockShared(leafId); 00313 SparseBitmapLeaf const &leaf = leafLock.getNodeForRead(); 00314 assert(leaf.iStartOffset == iLeafStartOffset); 00315 00316 // Read bit value from leaf 00317 fennel::PConstBuffer pBytes = leaf.getBytesForRead(); 00318 size_t iBit = iOffset - iLeafStartOffset; 00319 size_t iByte = iBit / 8; 00320 size_t iBitInByte = iBit - 8 * iByte; 00321 if (pBytes[iByte] & (1 << iBitInByte)) { 00322 return true; 00323 } else { 00324 return false; 00325 } 00326 }
void SparseBitmap::setBit | ( | SparseBitmapOffset | iOffset, | |
bool | value | |||
) |
Writes a bit in the bitmap.
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().
00329 { 00330 // Lock directory page in exclusive mode 00331 SparseBitmapDirLock dirLock; 00332 dirLock.accessSegment(segmentAccessor); 00333 dirLock.lockExclusive(dirPageId); 00334 00335 // Search directory; if it already has a corresponding leaf entry, 00336 // we won't need to modify the directory 00337 SparseBitmapOffset iLeafStartOffset = 00338 (iOffset / nBitsPerLeaf) * nBitsPerLeaf; 00339 fennel::PageId leafId = searchDirectory(dirLock, iLeafStartOffset); 00340 00341 SparseBitmapLeafLock leafLock; 00342 leafLock.accessSegment(segmentAccessor); 00343 bool clearLeaf = false; 00344 if (leafId == fennel::NULL_PAGE_ID) { 00345 // Leaf doesn't exist yet: we'll need a new one 00346 SparseBitmapDirectory &dir = dirLock.getNodeForWrite(); 00347 if (dir.nEntries >= nDirEntriesMax) { 00348 // Oops, directory is full and we have no provisions 00349 // for splitting it; we haven't modified the directory yet, 00350 // so the bitmap remains intact 00351 throw std::runtime_error("SparseBitmap directory full"); 00352 } 00353 // Allocate new leaf and add it to the directory 00354 SparseBitmapDirEntry *pLast = 00355 dir.getEntriesForWrite() + dir.nEntries; 00356 leafId = leafLock.allocatePage(fennel::ANON_PAGE_OWNER_ID); 00357 pLast->iLeafStartOffset = iLeafStartOffset; 00358 pLast->leafId = leafId; 00359 dir.nEntries++; 00360 clearLeaf = true; 00361 dirLock.unlock(); 00362 } else { 00363 // Leaf already exists, so no need to modify directory; 00364 // we can unlock the directory early 00365 dirLock.unlock(); 00366 leafLock.lockExclusive(leafId); 00367 } 00368 00369 // Write bit value to leaf 00370 SparseBitmapLeaf &leaf = leafLock.getNodeForWrite(); 00371 fennel::PBuffer pBytes = leaf.getBytesForWrite(); 00372 if (clearLeaf) { 00373 // We're initializing a new leaf, so clear all the bits first 00374 leaf.iStartOffset = iLeafStartOffset; 00375 memset(pBytes, 0, nBitsPerLeaf / 8); 00376 } 00377 size_t iBit = iOffset - iLeafStartOffset; 00378 size_t iByte = iBit / 8; 00379 size_t iBitInByte = iBit - 8 * iByte; 00380 if (value) { 00381 pBytes[iByte] |= (1 << iBitInByte); 00382 } else { 00383 pBytes[iByte] &= ~(1 << iBitInByte); 00384 } 00385 }
fennel::PageId SparseBitmap::getDirPageId | ( | ) | const |
Definition at line 387 of file SparseBitmapTest.cpp.
References dirPageId.
Referenced by SparseBitmapTest::testBasic(), and SparseBitmapTest::testSpread().
00388 { 00389 return dirPageId; 00390 }
size_t SparseBitmap::getBitsPerLeaf | ( | ) | const |
Definition at line 392 of file SparseBitmapTest.cpp.
References nBitsPerLeaf.
Referenced by SparseBitmapTest::testFullDirectory(), and SparseBitmapTest::testSizes().
00393 { 00394 return nBitsPerLeaf; 00395 }
size_t SparseBitmap::getMaxDirectoryEntries | ( | ) | const |
Definition at line 397 of file SparseBitmapTest.cpp.
References nDirEntriesMax.
Referenced by SparseBitmapTest::testFullDirectory(), and SparseBitmapTest::testSizes().
00398 { 00399 return nDirEntriesMax; 00400 }
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().