stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId > Class Template Reference

Template super-class enclosing all classes which can operate on a constant B-tree database file. More...

#include <stx-cbtreedb.h>

Collaboration diagram for stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >:
Collaboration graph
[legend]

List of all members.

Classes

class  BTreeBuilder
 BTreeBuilder is used to construct an index very similar to a B-tree from an ordered sequence. More...
class  BTreePage
 BTreePage is a reference-counted buffer holding one page of the B-tree index. More...
class  CRC32
 CRC32 Cyclic redundancy check implementation class. More...
class  Exception
 Our own exception class derived from std::runtime_error. More...
struct  InnerNode
 Inner node structure of the B-tree inner pages. More...
struct  LeafNode
 Leaf node structure of the B-tree leaf pages. More...
class  PageCache
 PageCache and PageCacheImpl implement a LRU-strategy cache of B-tree pages used by CBTreeDB reader objects. More...
class  PageCacheImpl
 PageCache and PageCacheImpl implement a LRU-strategy cache of B-tree pages used by CBTreeDB reader objects. More...
class  Reader
 Class used to read constant B-tree database files. More...
class  ReaderImpl
 Implementation class used to read constant B-tree database files. More...
class  SHA256
 SHA-256 Message Digest implementation class. More...
struct  SignaturePage
 Signature page which heads all cbtreedb files. More...
class  Writer
 Writer is used to construct an constant B-tree database from an unsorted input sequence. More...
class  WriterSequential
 WriterSequential is used to construct a constant B-tree database from an _ordered_ input sequence. More...

Public Types

typedef _Key key_type
 first template parameter: the key type of the B-tree.
typedef _Compare key_compare
 second template parameter: key comparison function object type.

Public Member Functions

 STX_STATIC_ASSERT (LeafNodeNumKeys >=1)
 STX_STATIC_ASSERT (InnerNodeNumKeys >=2)
 STX_STATIC_ASSERT (sizeof(SignaturePage)<=BTreePageSize)

Public Attributes

struct stx::CBTreeDB::SignaturePage packed
 Signature page which heads all cbtreedb files.

Static Public Attributes

static const unsigned int BTreePageSize = _BTreePageSize
 third template parameter: B-tree page size. Usually 1024 or 2048.
static const uint32_t AppVersionId = _AppVersionId
 fourth template parameter: application-defined 32-bit identifier to mark database format or version.
static const unsigned int LeafNodeHead = 2 * sizeof(uint16_t) + sizeof(uint64_t) + sizeof(uint32_t)
 size of fields before key+offset array in LeafNode and additional offset at end.
static const unsigned int LeafNodeNumKeys = (BTreePageSize - LeafNodeHead) / (sizeof(key_type) + sizeof(uint32_t))
 number of key+offsets in each LeafNode
static const unsigned int LeafNodeFiller = BTreePageSize - LeafNodeHead - LeafNodeNumKeys * (sizeof(key_type) + sizeof(uint32_t))
 number of unused fill bytes in each LeafNode
static const unsigned int InnerNodeHead = 2 * sizeof(uint16_t) + sizeof(uint32_t)
 size of fields before key array in InnerNode
static const unsigned int InnerNodeNumKeys = (BTreePageSize - InnerNodeHead) / sizeof(key_type)
 number of keys in each InnerNode
static const unsigned int InnerNodeFiller = BTreePageSize - InnerNodeHead - InnerNodeNumKeys * sizeof(key_type)
 number of unused fill bytes in each InnerNode
static const unsigned int SignaturePageSize = BTreePageSize
 Fixed signature page size: always equal to the B-tree page.

Protected Member Functions

 STX_STATIC_ASSERT (sizeof(LeafNode)==BTreePageSize)
 STX_STATIC_ASSERT (sizeof(InnerNode)==BTreePageSize)

Protected Attributes

struct stx::CBTreeDB::LeafNode packed
 Leaf node structure of the B-tree leaf pages.
struct stx::CBTreeDB::InnerNode packed
 Inner node structure of the B-tree inner pages.

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 >

Template super-class enclosing all classes which can operate on a constant B-tree database file.

By parameterizing this class an instance of all sub-classes is created. The parameters described important database parameters and database files should be read and written using the _same_ class parameters!

The first template parameter is the key type, which must be an integral, fixed-length type like uint32_t or a struct.

The second template parameter is the order functional used to sort the keys, it must form a total order relation over the keys.

The size of B-tree pages containing nodes are defined by the third parameter. The number of key slots in each node is calculated from this number and sizeof(_Key). There are some obvious constraints on the relationship of page size and key size which are checked by compile-time assertions.

The fourth template parameter is an uint32_t version number stored in the signature page of the database. It can be used by an application to mark its own database. When opening databases this parameter must match the signature.

For more information see http://idlebox.net/2010/stx-cbtreedb/

Definition at line 90 of file stx-cbtreedb.h.


Member Typedef Documentation

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
typedef _Compare stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::key_compare

second template parameter: key comparison function object type.

Definition at line 100 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
typedef _Key stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::key_type

first template parameter: the key type of the B-tree.

This must be an integral, fixed-length type as it is used in arrays in the tree nodes.

Definition at line 97 of file stx-cbtreedb.h.


Member Function Documentation

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::STX_STATIC_ASSERT ( sizeof(InnerNode = =BTreePageSize  )  [protected]
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::STX_STATIC_ASSERT ( sizeof(LeafNode = =BTreePageSize  )  [protected]
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::STX_STATIC_ASSERT ( sizeof(SignaturePage)<=  BTreePageSize  ) 
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::STX_STATIC_ASSERT ( InnerNodeNumKeys >=  2  ) 
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::STX_STATIC_ASSERT ( LeafNodeNumKeys >=  1  ) 

Member Data Documentation

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const uint32_t stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::AppVersionId = _AppVersionId [static]

fourth template parameter: application-defined 32-bit identifier to mark database format or version.

Definition at line 107 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreePageSize = _BTreePageSize [static]

third template parameter: B-tree page size. Usually 1024 or 2048.

Definition at line 103 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::InnerNodeFiller = BTreePageSize - InnerNodeHead - InnerNodeNumKeys * sizeof(key_type) [static]

number of unused fill bytes in each InnerNode

Definition at line 132 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::InnerNodeHead = 2 * sizeof(uint16_t) + sizeof(uint32_t) [static]

size of fields before key array in InnerNode

Definition at line 124 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::InnerNodeNumKeys = (BTreePageSize - InnerNodeHead) / sizeof(key_type) [static]

number of keys in each InnerNode

Definition at line 127 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::LeafNodeFiller = BTreePageSize - LeafNodeHead - LeafNodeNumKeys * (sizeof(key_type) + sizeof(uint32_t)) [static]

number of unused fill bytes in each LeafNode

Definition at line 121 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::LeafNodeHead = 2 * sizeof(uint16_t) + sizeof(uint64_t) + sizeof(uint32_t) [static]

size of fields before key+offset array in LeafNode and additional offset at end.

Definition at line 113 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::LeafNodeNumKeys = (BTreePageSize - LeafNodeHead) / (sizeof(key_type) + sizeof(uint32_t)) [static]

number of key+offsets in each LeafNode

Definition at line 116 of file stx-cbtreedb.h.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
struct stx::CBTreeDB::InnerNode stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::packed [protected]

Inner node structure of the B-tree inner pages.

Each inner node has n+1 children nodes, where n is the number of keys in the node. The n+1 children nodes are stored consecutively starting at childrenoffset.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
struct stx::CBTreeDB::LeafNode stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::packed [protected]

Leaf node structure of the B-tree leaf pages.

Each leaf node contains a key array and an array of relative value offsets. It does not contain the size of the value elements, because these can be computed from two successive relative offsets. This works for the last offset only because of the extra offset of the successor value item in the next leaf. The value offsets are relative to a starting 64-bit offset, because all leaf's data items are stored in order.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
struct stx::CBTreeDB::SignaturePage stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::packed

Signature page which heads all cbtreedb files.

It contains a signature and many important fields to correctly access the database file. Due to disk page alignment reasons, the signature block is stored with a full B-tree page size.

template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
const unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::SignaturePageSize = BTreePageSize [static]

Fixed signature page size: always equal to the B-tree page.

Definition at line 190 of file stx-cbtreedb.h.


The documentation for this class was generated from the following file:
Generated on Wed Apr 14 13:43:41 2010 for stx-cbtreedb by  doxygen 1.6.3