stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl Class Reference
PageCache and PageCacheImpl implement a LRU-strategy cache of B-tree pages used by CBTreeDB reader objects. More...
#include <stx-cbtreedb.h>
Classes | |
| struct | HashCell |
| Structure for each slot in the cache hash array. More... | |
Public Member Functions | |
| PageCacheImpl (unsigned int maxsize) | |
| Create a new page cache containg maxsize pages. | |
| ~PageCacheImpl () | |
| Removes all cached pages and destroys cache. | |
| void | RefInc () |
| Increment reference counter by one. | |
| unsigned int | RefDec () |
| Decrement reference counter by one and return it. | |
| void | Clear () |
| Remove all pages from the cache and reset status. | |
| void | Store (void *btreeid, uint32_t pageid, const BTreePage &page) |
| Store a page object in a cache cell identified by (btreeid,pageid). | |
| bool | Retrieve (void *btreeid, uint32_t pageid, BTreePage &outpage) |
| Retrieve a cached page identified by (btreeid,pageid). | |
| void | SetMaxSize (unsigned int maxsize) |
| Change maximum number of pages in cache, note that this does not immediately have effect. | |
| std::vector< std::pair< void *, uint32_t > > | GetPagelist () const |
| Return a vector listing all currently contained (btreeid,pageid) pairs in LRU order. | |
| bool | Verify () const |
| Verify the integrity of the LRU list and hash table. | |
Protected Member Functions | |
| unsigned int | hashfunc (void *btreeid, uint32_t pageid) |
| Simple hash function mapping (btreeid,pageid) -> bucket. | |
Protected Attributes | |
| unsigned int | m_refs |
| reference counter | |
| unsigned int | m_maxsize |
| maximum number of pages in cache | |
| unsigned int | m_size |
| current number of pages in cache | |
| uint32_t | m_lrutime |
| counter to tag pages with a virtual LRU timestamp. | |
| std::vector< struct HashCell * > | m_hasharray |
| hash cell array holding pointers to active cells | |
| struct HashCell | m_sentinel |
| sentinel hash cell for LRU double-linked list. | |
Detailed Description
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
class stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl
PageCache and PageCacheImpl implement a LRU-strategy cache of B-tree pages used by CBTreeDB reader objects.
One cache object can be shared between multiple readers. However, this page cache is not thread safe. You may have to wrap some mutex libraries if needed.
The cached pages are put into a hash table for quick lookup by (btreeid,pageid). Simultaneously the HashCells are linked into a doubly chained "LRU"-list with the most recently used page at the head. This allows O(1) algorithms for both Store() and Retrieve() functions. When the maximum number of pages is exceeded, the tail pages of the LRU-list are removed. The drawing below illustrates the data structure used by the class.
Structure of PageCache's arrays and nodes
Definition at line 924 of file stx-cbtreedb.h.
Constructor & Destructor Documentation
| stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::PageCacheImpl | ( | unsigned int | maxsize | ) | [inline, explicit] |
Create a new page cache containg maxsize pages.
Definition at line 995 of file stx-cbtreedb.h.
| stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::~PageCacheImpl | ( | ) | [inline] |
Removes all cached pages and destroys cache.
Definition at line 1008 of file stx-cbtreedb.h.
Member Function Documentation
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::Clear | ( | ) | [inline] |
Remove all pages from the cache and reset status.
Definition at line 1026 of file stx-cbtreedb.h.
| std::vector< std::pair<void*, uint32_t> > stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::GetPagelist | ( | ) | const [inline] |
Return a vector listing all currently contained (btreeid,pageid) pairs in LRU order.
Used by the test cases for verification.
Definition at line 1215 of file stx-cbtreedb.h.
| unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::hashfunc | ( | void * | btreeid, | |
| uint32_t | pageid | |||
| ) | [inline, protected] |
Simple hash function mapping (btreeid,pageid) -> bucket.
Definition at line 986 of file stx-cbtreedb.h.
| unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::RefDec | ( | ) | [inline] |
Decrement reference counter by one and return it.
Definition at line 1020 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::RefInc | ( | ) | [inline] |
Increment reference counter by one.
Definition at line 1014 of file stx-cbtreedb.h.
| bool stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::Retrieve | ( | void * | btreeid, | |
| uint32_t | pageid, | |||
| BTreePage & | outpage | |||
| ) | [inline] |
Retrieve a cached page identified by (btreeid,pageid).
Returns true if the page was found.
Definition at line 1156 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::SetMaxSize | ( | unsigned int | maxsize | ) | [inline] |
Change maximum number of pages in cache, note that this does not immediately have effect.
Definition at line 1208 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::Store | ( | void * | btreeid, | |
| uint32_t | pageid, | |||
| const BTreePage & | page | |||
| ) | [inline] |
Store a page object in a cache cell identified by (btreeid,pageid).
Definition at line 1050 of file stx-cbtreedb.h.
| bool stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::Verify | ( | ) | const [inline] |
Verify the integrity of the LRU list and hash table.
Definition at line 1231 of file stx-cbtreedb.h.
Member Data Documentation
std::vector<struct HashCell*> stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_hasharray [protected] |
hash cell array holding pointers to active cells
Definition at line 977 of file stx-cbtreedb.h.
uint32_t stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_lrutime [protected] |
counter to tag pages with a virtual LRU timestamp.
This is just for verification purposes and is only used in the testsuite as the counter may overflow in real applications.
Definition at line 943 of file stx-cbtreedb.h.
unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_maxsize [protected] |
maximum number of pages in cache
Definition at line 932 of file stx-cbtreedb.h.
unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_refs [protected] |
reference counter
Definition at line 929 of file stx-cbtreedb.h.
struct HashCell stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_sentinel [protected] |
sentinel hash cell for LRU double-linked list.
list_next is the head and list_prev is the tail of the list.
Definition at line 983 of file stx-cbtreedb.h.
unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::PageCacheImpl::m_size [protected] |
current number of pages in cache
Definition at line 935 of file stx-cbtreedb.h.
The documentation for this class was generated from the following file:
- include/stx-cbtreedb.h
