class Node

template <typename NodeSizeParams, TreeValidation Validator>

class Node

Defined at line 35 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 0 (or more generally, the minimum possible key value). This 0 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 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<NodeSizeParams, Validator> (uint32_t size_class, 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 39 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void Node<NodeSizeParams, Validator> (uint32_t size_class, Node<NodeSizeParams, Validator> && node, Item item, uint32_t index)

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

void Node<NodeSizeParams, Validator> (uint32_t size_class, bool leaf, Item item)

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

void Node<NodeSizeParams, Validator> (uint32_t size_class, bool leaf, Item item1, Item item2)

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

void ~Node<NodeSizeParams, Validator> ()

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

void Node<NodeSizeParams, Validator> ()

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

void Node<NodeSizeParams, Validator> (const Node<NodeSizeParams, Validator> & )

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

void Node<NodeSizeParams, Validator> (Node<NodeSizeParams, Validator> && )

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

Node<NodeSizeParams, Validator> & operator= (const Node<NodeSizeParams, Validator> & )

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

Node<NodeSizeParams, Validator> & operator= (Node<NodeSizeParams, Validator> && )

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

bool is_full ()

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

bool is_empty ()

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

bool valid_index (uint32_t index)

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

Item get (uint32_t index)

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

void update_key (uint32_t index, uint64_t key)

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

a valid tree.

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

void update_value (uint32_t index, uint64_t value)

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

uint32_t upper_bound (uint64_t 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 88 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void insert (uint32_t index, Item 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 100 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 110 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

void insert_rebalance_right (Node<NodeSizeParams, Validator> *__restrict right, uint32_t node_insert_index, Item item, iterator_base<Node<NodeSizeParams, Validator>> * fixup)

Rebalance this node with the right sibling by shifting items to the right to make space for

an insertion at node_insert_index.

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

void insert_rebalance_left (Node<NodeSizeParams, Validator> *__restrict left, uint32_t node_insert_index, Item item, iterator_base<Node<NodeSizeParams, Validator>> * fixup)

Rebalance this node with the left sibling by shifting items to the left to make space for

an insertion at node_insert_index.

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

void push (Item item)

Pushes a single item onto the end of the node.

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

void merge_from (Node<NodeSizeParams, Validator> &__restrict other)

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

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

void rotate_left (Node<NodeSizeParams, Validator> *__restrict left, uint32_t num)

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

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

void rotate_left_max (Node<NodeSizeParams, Validator> *__restrict left)

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

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

void rotate_right (Node<NodeSizeParams, Validator> *__restrict right, uint32_t num)

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

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

Node<NodeSizeParams, Validator> * prev ()

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

Node<NodeSizeParams, Validator> * next ()

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

void set_next (Node<NodeSizeParams, Validator> * next)

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

void set_prev (Node<NodeSizeParams, Validator> * prev)

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

size_t size_bytes ()

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

uint32_t size_class ()

Defined at line 261 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 277 of file ../../zircon/kernel/lib/btree/include/lib/btree_node.h

uint32_t MaxCountFromClass (uint32_t size_class)

Given a size class (index into kSizeClasses) returns the maximum count.

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

bool is_leaf ()

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

uint32_t max_count ()

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

uint32_t count ()

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

void set_count (uint32_t count)

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