Internal node for use with bit vector b-tree structures. More...

#include <node.hpp>

Public Member Functions
	node ()
	Constructor.

template<class qds >
void	generate_query_structure (qds *qs)

void	has_leaves (bool leaves)
	Set whether the children of the node are leaves or internal nodes. More...

bool	has_leaves () const
	Get the type of children for the node. More...

bool	at (dtype index) const
	Access the value of the index^th element of the logical structure. More...

int	set (dtype index, bool v)
	Set the value of the logical index^th element to v. More...

dtype	rank (dtype index) const
	Counts number of one bits up to the index^th logical element. More...

dtype	select (dtype count) const
	Calculates the index of the count^tu 1-bit. More...

template<class allocator >
void	deallocate (allocator *alloc)
	Recursively deallocates all children. More...

uint8_t	child_count () const
	Get the number of children of this node. More...

void **	children ()
	Get pointer to the children of this node. More...

branching *	child_sizes ()
	Get pointer to the cumulative child sizes. More...

branching *	child_sums ()
	Get pointer to the cumulative child sums. More...

dtype	size () const
	Logical number of elements stored in the subtree. More...

dtype	p_sum () const
	Logical number of 1-bits stored in the subtree. More...

template<class child >
void	append_child (child *new_child)
	Add child to the subtree. More...

void *	child (uint8_t i)
	Get i^th child of the node. More...

template<class allocator >
void	insert (dtype index, bool value, allocator *alloc)
	Insert "value" at "index". More...

template<class allocator >
bool	remove (dtype index, allocator *alloc)
	Remove the index^th element. More...

void	clear_first (uint8_t elems)
	Remove the first "elems" elements form this node. More...

void	transfer_append (node *other, uint8_t elems)
	Moves the fist "elems" elements from "other" to the end of "this". More...

void	clear_last (uint8_t elems)
	Remove the last "elems" elemets from the node. More...

void	transfer_prepend (node *other, uint8_t elems)
	Moves the last "elems" elements from "other" to the start of "this". More...

void	append_all (node *other)
	Copies all children from "other" to the end of this node. More...

uint64_t	bits_size () const
	Size of the subtree in "allocated" bits. More...

void	flush ()

uint64_t	validate () const
	Check that the subtree structure is internally consistent. More...

void	print (bool internal_only) const
	Outputs this subtree as json. More...

Protected Types
typedef branchless_scan< dtype, branches >	branching

Protected Member Functions
template<class allocator >
void	rebalance_leaf (uint8_t index, leaf_type leaf, allocator alloc)
	Ensure that there is space for insertion in the child leaves. More...

template<class allocator >
void	leaf_insert (dtype index, bool value, allocator *alloc)
	Insertion operation if the children are leaves. More...

template<class allocator >
void	rebalance_node (uint8_t index, allocator *alloc)
	Ensure that there is space for insertion in the child nodes. More...

template<class allocator >
void	node_insert (dtype index, bool value, allocator *alloc)
	Insertion operation if the children are internal nodes. More...

template<class allocator >
void	rebalance_leaves_right (leaf_type a, leaf_type b, allocator *alloc)
	Transfer elements from the "right" leaf to the "left" leaf. More...

template<class allocator >
void	rebalance_leaves_left (leaf_type a, leaf_type b, uint8_t idx, allocator *alloc)
	Transfer elements from the "left" leaf to the "right" leaf. More...

template<class allocator >
void	merge_leaves (leaf_type a, leaf_type b, uint8_t idx, allocator *alloc)
	Merge the right leaf into the left leaf. More...

template<class allocator >
bool	leaf_remove (dtype index, allocator *alloc)
	Removal used when the children are leaves. More...

void	rebalance_nodes_right (node a, node b, uint8_t idx)
	Transfer elements from the "right" node to the "left" node. More...

void	rebalance_nodes_left (node a, node b, uint8_t idx)
	Transfer elements from the "lef" node to the "right" node. More...

template<class allocator >
void	merge_nodes (node a, node b, uint8_t idx, allocator *alloc)
	Transfer all from the "right" node to the "left" node. More...

template<class allocator >
bool	node_remove (dtype index, allocator *alloc)
	Removal operation when children are internal nodes. More...

Protected Attributes
uint8_t	meta_data_
	Bit indicating whether the nodes children are laves or nodes.

uint8_t	child_count_
	Number of active children.

branching	child_sizes_
	Cumulative child sizes and `(~0) >> 1` for non-existing children.

branching	child_sums_
	Cumulative child sums and `(~0) >> 1` for non-existint children.

void *	children_ [branches]
	pointers to leaf_type or node children.

Detailed Description

template<class leaf_type, class dtype, uint64_t leaf_size, uint8_t branches>
class bv::node< leaf_type, dtype, leaf_size, branches >

Internal node for use with bit vector b-tree structures.

Intended for use with bv::bit_vector and bv::leaf, to support the dynamic b-tree bit vector structure.

Practical limitations

The maximum logical size of the bit vector is \(2^{b - 1} - 1\) where b is the number of bits available in dtype. This is due to the "sign bit" being used to speed up branching. So for 64-bit words the maximum data structure size is 9223372036854775807 and for 32-bot words the limit is 2147483647.

The internal nodes need to keep track of leaf sizes, since splitting, merging and balancing is done based on a top-down approach, where an insertion or removal already submitted to a leaf cannot cause any rebalancing.

The maximum leaf size practically needs to be divisible by 128 due to the practical allocation scheme allocating an even amount of 64-bit integers for leaf storage. In addition a minimum size of 128 causes edge cases in balancing that can result in undefined behaviour. Thus a minimum leaf size of 256 and divisibility of maximum leaf size by 128 is enforced by static assertions.

Buffered bv::leaf instances can not be bigger than \(2^{24} - 1\).

The branching factor for the internal nodes need to be 8, 16, 32, 64 or 128 due to how the branchless binary search is written. Further limited by the 7 bits available in the child counter.

Cache line size

Branch selection uses binary search, which significantly benefits from agressive cache prefetching. It is suggested that a definition of CACHLE_LINE is given with the value of the cache line size for the (running) architecture. Make attempts to retrieve this information and passing the correct value to the compiler with the -DCACHE_LINE flag.

If the prefetching fails significantly due to prefetching being unavailable or the wrong cache line size, the current binary search based branch selection will likely be noticeably slower than a naive linear search.

Template Parameters

leaf_type	Type of leaf to use in the tree structure (E.g. bv::leaf).
dtype	Integer type to use for indexing (uint32_t or uint64_t).
leaf_size	Maximum size of a leaf node.
branches	Maximum branching factor of internal nodes.

Member Function Documentation

◆ append_all()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::append_all ( node< leaf_type, dtype, leaf_size, branches > * other )

inline

Copies all children from "other" to the end of this node.

Internal cumulative sizes and sums will be updated for this node but not for other. This is used when merging 2 nodes, where the "right" sibling will be deallocated after copying.

Parameters

other Node to copy elements from.

◆ append_child()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class child >

void bv::node< leaf_type, dtype, leaf_size, branches >::append_child ( child * new_child )

inline

Add child to the subtree.

Mainly intended for use by bv::bit_vector for splitting root nodes.

Template Parameters

child Type of child (node or leaf_type).

Parameters

new_child Child to append.

◆ at()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

bool bv::node< leaf_type, dtype, leaf_size, branches >::at ( dtype index ) const

inline

Access the value of the index^th element of the logical structure.

Recurses to children based on cumulative sizes.

Parameters

index Index to access.

◆ bits_size()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

uint64_t bv::node< leaf_type, dtype, leaf_size, branches >::bits_size ( ) const

inline

Size of the subtree in "allocated" bits.

Reports number of bits allocated for this subtree, Does not take into account any sort of memory fragmentation or similar.

Returns: Number of allocated bits.

◆ child()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void* bv::node< leaf_type, dtype, leaf_size, branches >::child ( uint8_t i )

inline

Get i^th child of the node.

Mainly intended for use by bv::bit_vector for decreasing tree height.

Parameters

i	Index of child to return.

Returns: Pointer to the i^th child.

◆ child_count()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

uint8_t bv::node< leaf_type, dtype, leaf_size, branches >::child_count ( ) const

inline

Get the number of children of this node.

Returns: Number of children.

◆ child_sizes()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

branching* bv::node< leaf_type, dtype, leaf_size, branches >::child_sizes ( )

inline

Get pointer to the cumulative child sizes.

Intended for efficient acces when balancing nodes.

Returns: Address of the array of cumulative child sizes.

◆ child_sums()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

branching* bv::node< leaf_type, dtype, leaf_size, branches >::child_sums ( )

inline

Get pointer to the cumulative child sums.

Intended for efficient acces when balancing nodes.

Returns: Address of the array of cumulative child sums.

◆ children()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void** bv::node< leaf_type, dtype, leaf_size, branches >::children ( )

inline

Get pointer to the children of this node.

Intended for efficient acces when balancing nodes.

Returns: Address to the array of children of this node.

◆ clear_first()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::clear_first ( uint8_t elems )

inline

Remove the first "elems" elements form this node.

Internal cumulative sizes and sums will be updated, but removed nodes will not be deallocated, as it is assumed that this is triggered after copying elements to the "left" sibling.

Parameters

elems Number of elements to remove.

◆ clear_last()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::clear_last ( uint8_t elems )

inline

Remove the last "elems" elemets from the node.

Internal cumulative sizes and sums will be updated, but removed nodes will not be deallocated, as it is assumed that this is triggered after copying elements to the "right" sibling.

Parameters

elems Number of elements to remove

◆ deallocate()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::deallocate ( allocator * alloc )

inline

Recursively deallocates all children.

A separate allocator is needed in addition to ~node() since binding deallocation of children to the default destructor could lead to deallocation of nodes that are still in use with other nodes.

Template Parameters

allocator Type of alloc.

Parameters

alloc Allocator instance to use for deallocation.

◆ has_leaves() [1/2]

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

bool bv::node< leaf_type, dtype, leaf_size, branches >::has_leaves ( ) const

inline

Get the type of children for the node.

Returns: True if the children of this node are leaves.

◆ has_leaves() [2/2]

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::has_leaves ( bool leaves )

inline

Set whether the children of the node are leaves or internal nodes.

Intended to be set according to the status of siblings following allocation of the node.

Parameters

leaves Boolean value indicating if the children of this node are leaves.

◆ insert()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::insert	(	dtype	index,
		bool	value,
		allocator *	alloc
	)

inline

Insert "value" at "index".

Inserts into the logical bit vector whlie ensuring that structural invariants hold. Children will be rebalanced or split as necessary.

Template Parameters

allocator Type of alloc.

Parameters

index	Location for insertion.
value	Boolean indicating the value for the new element.
alloc	Instance of allocator to use for allocation and reallocation.

◆ leaf_insert()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::leaf_insert	(	dtype	index,
		bool	value,
		allocator *	alloc
	)

inlineprotected

Insertion operation if the children are leaves.

Reallocation and rebalancing will take place as necessary.

Template Parameters

allocator Type of alloc.

Parameters

index	Location of insertion.
value	Value to insert.
alloc	Instance of alloctor to use for allocation and reallocation.

◆ leaf_remove()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

bool bv::node< leaf_type, dtype, leaf_size, branches >::leaf_remove	(	dtype	index,
		allocator *	alloc
	)

inlineprotected

Removal used when the children are leaves.

Will maintain structural invarians by, reallocating and rebalancing as necessary.

Template Parameters

Allocator Type of alloc.

Parameters

index	Index of element to remove.
alloc	Allocator instance to use for reallocation and deallocation.

Returns: Value of removed element.

◆ merge_leaves()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::merge_leaves	(	leaf_type *	a,
		leaf_type *	b,
		uint8_t	idx,
		allocator *	alloc
	)

inlineprotected

Merge the right leaf into the left leaf.

Intended for when a removal would break structural invariant and there are not enough elements in siblings to transfer elements wilhe maintaining invariants.

Template Parameters

allocator Type of alloc

Parameters

a	"Left" leaf.
b	"Right" leaf.
idx	Index of left leaf for reallocation.
alloc	Allocator instance to use for reallocation and deallocation.

◆ merge_nodes()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::merge_nodes	(	node< leaf_type, dtype, leaf_size, branches > *	a,
		node< leaf_type, dtype, leaf_size, branches > *	b,
		uint8_t	idx,
		allocator *	alloc
	)

inlineprotected

Transfer all from the "right" node to the "left" node.

Intended for rebalancing when a removal may break structural invariants but rebalancing is impractical due to fill rate of siblings being \(\approx \frac{1}{3}\). Nodes will be merged instead.

Template Parameters

allocator Type of alloc.

Parameters

a	"Left" leaf.
b	"Right" leaf.
idx	Index of the "left" node for updating cumulative sums and sizes.
alloc	Allocator instance to use for deallocation.

◆ node_insert()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::node_insert	(	dtype	index,
		bool	value,
		allocator *	alloc
	)

inlineprotected

Insertion operation if the children are internal nodes.

Reallocation and rebalancing will take place as necessary.

Template Parameters

allocator Type of alloc.

Parameters

index	Location of insertion.
value	Value to insert.
alloc	Allocator instance to use for allocation and reallocation.

◆ node_remove()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

bool bv::node< leaf_type, dtype, leaf_size, branches >::node_remove	(	dtype	index,
		allocator *	alloc
	)

inlineprotected

Removal operation when children are internal nodes.

Recursively call the removal to children that are internal nodes. Maintains structural invariants by rebalancing and merging nodes as necessary.

Template Parameters

allocator Type of alloc.

Parameters

index	Index of element to be removed.
alloc	Allocator instanve for eallocation and deallocatioin

Returns: Value of removed element.

◆ p_sum()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

dtype bv::node< leaf_type, dtype, leaf_size, branches >::p_sum ( ) const

inline

Logical number of 1-bits stored in the subtree.

Returns: Number of 1-bits in subtree.

◆ print()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::print ( bool internal_only ) const

inline

Outputs this subtree as json.

Prints this and all subtrees recursively. A final new line will not be output, since it is assumed that this is called from another internal node or a root element like bv::bit_vector.

Parameters

internal_only If true, leaves will not output their data arrays to save space

◆ rank()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

dtype bv::node< leaf_type, dtype, leaf_size, branches >::rank ( dtype index ) const

inline

Counts number of one bits up to the index^th logical element.

Recurses to children based on cumulative sizes and returns subtree rank based on the result of the recurrence and local cumulative sums.

Parameters

index Number of elements to sum.

Returns: \(\sum_{i = 0}^{\mathrm{index - 1}} \mathrm{bv}[i]\).

◆ rebalance_leaf()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_leaf	(	uint8_t	index,
		leaf_type *	leaf,
		allocator *	alloc
	)

inlineprotected

Ensure that there is space for insertion in the child leaves.

If there is sufficient space in either sibling, elements will be transferred to the sibling with more room. If there is insufficient space in the siblings, a new leaf is allocated and elements are transferred from the target leaf to one of the siblings.

Generally delays allocation of a new leaf as long as posisble, and when reallocating, generates a new leaf that is \(\approx \frac{2}{3}\) full.

Template Parameters

allocator Type of alloc.

Parameters

index	Location of the full leaf.
leaf	Pointer to the full leaf.
alloc	Instance of allocator to use for reallocation.

◆ rebalance_leaves_left()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_leaves_left	(	leaf_type *	a,
		leaf_type *	b,
		uint8_t	idx,
		allocator *	alloc
	)

inlineprotected

Transfer elements from the "left" leaf to the "right" leaf.

Intended for rebalancing when a removal targets the "right" leaf but there are too few elements in the leaf to maintain structural invariants.

Template Parameters

allocator Type of alloc.

Parameters

a	"Left" leaf.
b	"Right" leaf.
idx	Index of the "left" leaf for use when reallocating.
alloc	Allocator instance to use for allocation and reallocation.

◆ rebalance_leaves_right()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_leaves_right	(	leaf_type *	a,
		leaf_type *	b,
		allocator *	alloc
	)

inlineprotected

Transfer elements from the "right" leaf to the "left" leaf.

Intended for rebalancing when a removal targets the "left" leaf but there are too few elements in the leaf to maintain structural invariants.

Only called when the "left" leaf has index 0. Thus no need for the target indexes for reallocation.

Template Parameters

allocator Type of alloc.

Parameters

a	"Left" leaf.
b	"Right" leaf.
alloc	Allocator to use for allocation and reallocation.

◆ rebalance_node()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_node	(	uint8_t	index,
		allocator *	alloc
	)

inlineprotected

Ensure that there is space for insertion in the child nodes.

If there is sufficient space in either sibling, elements will be transferred to the sibling with more room. If there is insufficient space in the siblings, a new node is allocated and elements are transferred from the target node to one of the siblings.

Generally delays allocation of a new node as long as possible, and when reallocating, generates a new node that is \(\approx \frac{2}{3}\) full.

Template Parameters

allocator Type of alloc.

Parameters

index	Location of the full node.
alloc	Allocator instance to use for allocation.

◆ rebalance_nodes_left()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_nodes_left	(	node< leaf_type, dtype, leaf_size, branches > *	a,
		node< leaf_type, dtype, leaf_size, branches > *	b,
		uint8_t	idx
	)

inlineprotected

Transfer elements from the "lef" node to the "right" node.

Intended for rebalancing when a removal targets the "right" node but there are too few elements in the node to ensure that structural invariants are maintained.

Template Parameters

allocator Type of allocator_.

Parameters

a	"Left" leaf.
b	"Right" leaf.
idx	Index of the Left node for use when updating cumulative sizes and sums.

◆ rebalance_nodes_right()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::rebalance_nodes_right	(	node< leaf_type, dtype, leaf_size, branches > *	a,
		node< leaf_type, dtype, leaf_size, branches > *	b,
		uint8_t	idx
	)

inlineprotected

Transfer elements from the "right" node to the "left" node.

Intended for rebalancing when a removal targets the "left" node but there are too few elements in the node to ensure that structural invariants are maintained.

Only called when the "left" node has index 0. Thus no need for the target indexes for reallocation.

Template Parameters

allocator Type of allocator_.

Parameters

a	"Left" node.
b	"Right" node.
idx	Index of "left" node for updating cumulative sizes and sums.

◆ remove()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

template<class allocator >

bool bv::node< leaf_type, dtype, leaf_size, branches >::remove	(	dtype	index,
		allocator *	alloc
	)

inline

Remove the index^th element.

Removes element at "index" while ensuring that strctural invariants hold. Children will be rebalanced and merger as necessary.

Template Parameters

allocator Type of alloc.

Parameters

index	Location for removal.
alloc	Allocator to use for reallocation and deallocation.

◆ select()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

dtype bv::node< leaf_type, dtype, leaf_size, branches >::select ( dtype count ) const

inline

Calculates the index of the count^tu 1-bit.

Recurses to children based on cumulative sums and returns subtree Select based on the results of the recurrence and local cumulative sizes.

Parameters

count Number to sum up to

Returns: \(\underset{i \in [0..n)}{\mathrm{arg min}}\left(\sum_{j = 0}^i \mathrm{bv}[j]\right) = \) count.

◆ set()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

int bv::node< leaf_type, dtype, leaf_size, branches >::set	(	dtype	index,
		bool	v
	)

inline

Set the value of the logical index^th element to v.

Recurses to children based on cumulative sizes and updates partial sums based on return value. Change is returned so parents can update partial sums as well.

Parameters

index	Index of element to set value of
v	Value to set element to.

Returns: Change to data structure sum triggered by the set operation.

◆ size()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

dtype bv::node< leaf_type, dtype, leaf_size, branches >::size ( ) const

inline

Logical number of elements stored in the subtree.

Returns: Number of elements in subtree.

◆ transfer_append()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::transfer_append	(	node< leaf_type, dtype, leaf_size, branches > *	other,
		uint8_t	elems
	)

inline

Moves the fist "elems" elements from "other" to the end of "this".

Elements are first copied to this node, after which clear_firs(elems) will be called on "other". Cumulative sizes and sums will be updated accordingly.

Parameters

other	Node to transfer elements from.
elems	Number of elements to transfer.

◆ transfer_prepend()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

void bv::node< leaf_type, dtype, leaf_size, branches >::transfer_prepend	(	node< leaf_type, dtype, leaf_size, branches > *	other,
		uint8_t	elems
	)

inline

Moves the last "elems" elements from "other" to the start of "this".

Elements are first copied to this node, after which clear_firs(elems) will be called on "other". Cumulative sizes and sums will be updated accordingly.

Parameters

other	Node to transfer elements from.
elems	Number of elements to transfer.

◆ validate()

template<class leaf_type , class dtype , uint64_t leaf_size, uint8_t branches>

uint64_t bv::node< leaf_type, dtype, leaf_size, branches >::validate ( ) const

inline

Check that the subtree structure is internally consistent.

Checks that cumulative sizes and sums agree with the reported sizes and sums of the children.

If the children are leaves, also checks the validity of capacity for the child.

If compiled with NDEBUG defined, this function will do essentially nothing since all checks are based on C assertions.

Also does not say anything about the correctness of the subtree given the sequence of operations up to this point. Only guarantees that the structure is internally consistent and "could" be the result of some valid sequence of operations.

Number of nodes are reported for verification of allocation counts.

Returns: Number of nodes in this subtree.

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

bit_vector/internal/node.hpp

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class leaf_type, class dtype, uint64_t leaf_size, uint8_t branches> class bv::node< leaf_type, dtype, leaf_size, branches >

Practical limitations

Cache line size

Member Function Documentation

◆ append_all()

◆ append_child()

◆ at()

◆ bits_size()

◆ child()

◆ child_count()

◆ child_sizes()

◆ child_sums()

◆ children()

◆ clear_first()

◆ clear_last()

◆ deallocate()

◆ has_leaves() [1/2]

◆ has_leaves() [2/2]

◆ insert()

◆ leaf_insert()

◆ leaf_remove()

◆ merge_leaves()

◆ merge_nodes()

◆ node_insert()

◆ node_remove()

◆ p_sum()

◆ print()

◆ rank()

◆ rebalance_leaf()

◆ rebalance_leaves_left()

◆ rebalance_leaves_right()

◆ rebalance_node()

◆ rebalance_nodes_left()

◆ rebalance_nodes_right()

◆ remove()

◆ select()

◆ set()

◆ size()

◆ transfer_append()

◆ transfer_prepend()

◆ validate()

template<class leaf_type, class dtype, uint64_t leaf_size, uint8_t branches>
class bv::node< leaf_type, dtype, leaf_size, branches >