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 >:

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.