orbtree::NodeAllocatorCompact< KeyValueT, NVTypeT, IndexType > Class Template Reference

Alternate node allocator with the aim to use less memory. More...

#include <orbtree_node.h>

Classes
struct	Node
	Node object. More...

Public Member Functions
size_t	capacity () const
	get the current capacity of the underlying storage
size_t	deleted_nodes () const
	get the number of deleted nodes
void	shrink_to_fit ()
	Free up memory taken up by deleted nodes by rearranging storage.
void	reserve (size_t size)
	Reserve storage for at least the requested number of elements. It can throw an exception on failure to allocate memory.

Protected Types
typedef IndexType	NodeHandle
typedef KeyValueT	KeyValue
typedef NVTypeT	NVType

Protected Member Functions
	NodeAllocatorCompact ()
	Nil sentinel.
	NodeAllocatorCompact (unsigned int nv_per_node_)
Node &	get_node (NodeHandle x)
	get reference to a modifiable node
const Node &	get_node (NodeHandle x) const
	get reference to a const node
NodeHandle	new_node ()
	get new node – note that it is the callers responsibility to store the handle in the tree
NodeHandle	new_node (const KeyValue &kv)
	get new node – note that it is the callers responsibility to store the handle in the tree
NodeHandle	new_node (KeyValue &&kv)
	get new node – note that it is the callers responsibility to store the handle in the tree
template<class... T>
NodeHandle	new_node (T &&... kv)
	get new node – note that it is the callers responsibility to store the handle in the tree
void	free_node (NodeHandle n)
	delete node – tree is not traversed, the caller must arrange to "cut" out the node in question
void	clear_tree ()
	clear tree, to be reused
unsigned int	get_nv_per_node () const
	each node has nv_per_node values calculated and stored in it
void	get_node_sum (NodeHandle n, NVType *s) const
	get the partial sum stored in node n
void	set_node_sum (NodeHandle n, const NVType *s)
	set the partial sum stored in node n

Protected Attributes
NodeHandle	root
NodeHandle	nil
	Root sentinel.

Static Protected Attributes
static constexpr NodeHandle	Invalid = max_nodes
	invalid handle

Detailed Description

template<class KeyValueT, class NVTypeT, class IndexType>
class orbtree::NodeAllocatorCompact< KeyValueT, NVTypeT, IndexType >

Alternate node allocator with the aim to use less memory.

Special node allocator that stores values in separate array + stores red/black flag in parent pointer. Note that memory is not freed automatically when nodes are deleted, use the shrink_size() function for that purpose.

Note: this uses the custom vector implementation either realloc_vector::vector if key and value are trivially copyable or stacked_vector::vector if not. The latter version will be significantly slower.

Template Parameters

KeyValueT	Type of stored data, should be either KeyOnly or KeyValue
NVTypeT	Type of extra data stored along in nodes (i.e. the return value of the function whose sum can be calculated).

Note: the actual requirement for realloc_vector::vector would be "trivially moveable" (meaning any object that can be moved to a new memory location without problems, but can still have nontrivial destructor), but as far as I know, this concept does not exist in C++.

---

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

• orbtree_node.h