template <typename Key, typename Value, size_t NodeSize, TreeValidation Validator, typename AugmentedState>

class Node

Defined at line 36 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

BTree node implementation.

This is a B-tree variant that resembles a B+tree in that all values are stored in the leaf

nodes. Intermediate nodes store keys that represent the *minimum* possible key for each of their

child subtrees.

A key property of this representation is that the first key (at index 0) of every non-leaf node

must be the minimum possible key value, which also must be the default initialized value of Key.

This minimum key effectively represents -infinity and ensures that any key less than the first

explicit key in the second slot will correctly traverse into the first child. This differs from

standard B-trees where keys are stored 'between' child pointers.

Because intermediate nodes store minimum keys rather than exact keys, symmetric lower_bound

operation across both leaf and intermediate nodes is not possible. Search operations therefore

always use upper_bound to find the correct subtree.

Public Members

static const size_t kHeaderSize

static const size_t kSmallestOneItemNode

static const size_t kSmallestTwoItemNode

static const size_t kNumSizeClasses

static const size_t kSizeClassSizeBits

static const size_t kSizeClassMask

static const size_t kIsLeafBit

static const size_t kIsLeafMask

static const size_t kPrevDataBits

static const uint32_t kMaxValues

static const size_t kNextDataBits

static const uint32_t kTargetMinValues

Public Methods

void Node<Key, Value, NodeSize, Validator, AugmentedState> (size_t size_bytes, bool leaf)

All node constructors need to be told what size they are and whether or not they are a leaf

type. Additional constructors also take various initial items or nodes to copy from.

Defined at line 43 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> (size_t size_bytes, Node<Key, Value, NodeSize, Validator, AugmentedState> && node, const ItemType & item, uint32_t index)

Defined at line 44 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> (size_t size_bytes, bool leaf, const ItemType & item)

Defined at line 49 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> (size_t size_bytes, bool leaf, const ItemType & item1, const ItemType & item2)

Defined at line 53 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void ~Node<Key, Value, NodeSize, Validator, AugmentedState> ()

Defined at line 59 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> ()

Defined at line 61 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> (const Node<Key, Value, NodeSize, Validator, AugmentedState> & )

Defined at line 62 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<Key, Value, NodeSize, Validator, AugmentedState> (Node<Key, Value, NodeSize, Validator, AugmentedState> && )

Defined at line 63 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

Node<Key, Value, NodeSize, Validator, AugmentedState> & operator= (const Node<Key, Value, NodeSize, Validator, AugmentedState> & )

Defined at line 64 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

Node<Key, Value, NodeSize, Validator, AugmentedState> & operator= (Node<Key, Value, NodeSize, Validator, AugmentedState> && )

Defined at line 65 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

bool is_full ()

Defined at line 67 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

bool is_empty ()

Defined at line 68 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

bool valid_index (uint32_t index)

Defined at line 70 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

const ItemType & get (uint32_t index)

Defined at line 72 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void update_key (uint32_t index, const Key & key)

Updates the key at the given index. It is the callers responsibility to ensure this results in

a valid tree.

Defined at line 79 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void update_value (uint32_t index, uint64_t value)

Defined at line 85 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

uint32_t upper_bound (const Key & key)

Returns the index of the upper bound of key, or count() if key is beyond this node. Due to how

intermediate nodes are represented there is no equivalent lower_bound operation as it does not

have a symmetric implementation for both intermediate and leaf nodes.

Defined at line 93 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void insert (uint32_t index, const ItemType & item)

Inserts an item at the specified index, which must either be a valid_index, or at the end of

the valid indexes and shifts the rest of the items up and updates the count.

Defined at line 105 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void erase (uint32_t index, uint32_t amount)

Erase the range items, shifting down the remainder and updating the count.

Defined at line 115 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void push (const ItemType & item)

Pushes a single item onto the end of the node.

Defined at line 123 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void merge_from (Node<Key, Value, NodeSize, Validator, AugmentedState> &__restrict other)

Moves all the items from |other| onto the end of |this|.

Defined at line 132 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void rotate_left (Node<Key, Value, NodeSize, Validator, AugmentedState> *__restrict left, uint32_t num)

Moves |num| items from the start of this node onto the end of |left|.

Defined at line 142 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void rotate_left_max (Node<Key, Value, NodeSize, Validator, AugmentedState> *__restrict left)

Moves as many items as possible from the start of this node onto the end of |left|.

Defined at line 150 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void rotate_right (Node<Key, Value, NodeSize, Validator, AugmentedState> *__restrict right, uint32_t num)

Moves |num| items from the end of this node into the start of |right|.

Defined at line 157 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

Node<Key, Value, NodeSize, Validator, AugmentedState> * prev ()

Defined at line 164 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

Node<Key, Value, NodeSize, Validator, AugmentedState> * next ()

Defined at line 165 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void set_next (Node<Key, Value, NodeSize, Validator, AugmentedState> * next)

Defined at line 167 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void set_prev (Node<Key, Value, NodeSize, Validator, AugmentedState> * prev)

Defined at line 168 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

size_t size_bytes ()

Defined at line 170 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

size_t SizeForCount (size_t count)

Defined at line 182 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

uint32_t MaxCountFromSize (size_t bytes)

Calculates our maximum count given a size in bytes.

Defined at line 214 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

size_t SizeBytesToClass (size_t size_bytes)

Defined at line 222 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

bool is_leaf ()

Defined at line 237 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

uint32_t max_count ()

Defined at line 238 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

uint32_t count ()

Defined at line 239 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void set_count (uint32_t count)

Defined at line 240 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

AugmentedState & aug_state ()

Defined at line 245 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

const AugmentedState & aug_state ()

Defined at line 246 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h