template <typename Params>

class btree_node

Defined at line 493 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

A node in the btree holding. The same node type is used for both internal

and leaf nodes in the btree, though the nodes are allocated in such a way

that the children array is only valid in internal nodes.

Public Methods

void ~btree_node<Params> ()

This class is organized by absl::container_internal::Layout as if it had

the following structure:

// A pointer to the node's parent.

btree_node *parent;

// When ABSL_BTREE_ENABLE_GENERATIONS is defined, we also have a

// generation integer in order to check that when iterators are

// used, they haven't been invalidated already. Only the generation on

// the root is used, but we have one on each node because whether a node

// is root or not can change.

uint32_t generation;

// The position of the node in the node's parent.

field_type position;

// The index of the first populated value in `values`.

// TODO(ezb): right now, `start` is always 0. Update insertion/merge

// logic to allow for floating storage within nodes.

field_type start;

// The index after the last populated value in `values`. Currently, this

// is the same as the count of values.

field_type finish;

// The maximum number of values the node can hold. This is an integer in

// [1, kNodeSlots] for root leaf nodes, kNodeSlots for non-root leaf

// nodes, and kInternalNodeMaxCount (as a sentinel value) for internal

// nodes (even though there are still kNodeSlots values in the node).

// TODO(ezb): make max_count use only 4 bits and record log2(capacity)

// to free extra bits for is_root, etc.

field_type max_count;

// The array of values. The capacity is `max_count` for leaf nodes and

// kNodeSlots for internal nodes. Only the values in

// [start, finish) have been initialized and are valid.

slot_type values[max_count];

// The array of child pointers. The keys in children[i] are all less

// than key(i). The keys in children[i + 1] are all greater than key(i).

// There are 0 children for leaf nodes and kNodeSlots + 1 children for

// internal nodes.

btree_node *children[kNodeSlots + 1];

This class is only constructed by EmptyNodeType. Normally, pointers to the

layout above are allocated, cast to btree_node*, and de-allocated within

the btree implementation.

Defined at line 573 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void btree_node<Params> (const btree_node<Params> & )

Defined at line 574 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

btree_node<Params> & operator= (const btree_node<Params> & )

Defined at line 575 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

bool is_leaf ()

Whether this is a leaf node or not. This value doesn't change after the

node is created.

Defined at line 679 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

bool is_internal ()

Whether this is an internal node or not. This value doesn't change after

the node is created.

Defined at line 682 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

field_type position ()

Getter for the position of this node in its parent.

Defined at line 685 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

field_type start ()

Getter for the offset of the first value in the `values` array.

Defined at line 688 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

field_type finish ()

Getter for the offset after the last value in the `values` array.

Defined at line 695 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

field_type count ()

Getters for the number of values stored in this node.

Defined at line 698 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

field_type max_count ()

Defined at line 702 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

btree_node<Params> * parent ()

Getter for the parent of this node.

TODO(ezb): assert that the child of the returned node at position

`node_->position()` maps to the current node.

Defined at line 714 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

bool is_root ()

Getter for whether the node is the root of the tree. The parent of the

root of the tree is the leftmost node in the tree which is guaranteed to

be a leaf.

Defined at line 718 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void make_root ()

Defined at line 719 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

uint32_t * get_root_generation ()

Gets the root node's generation integer, which is the one used by the tree.

Defined at line 726 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

uint32_t generation ()

Returns the generation for iterator validation.

Defined at line 734 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void set_generation (uint32_t generation)

Updates generation. Should only be called on a root node or during node

initialization.

Defined at line 739 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void next_generation ()

Updates the generation. We do this whenever the node is mutated.

Defined at line 743 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

const key_type & key (size_type i)

Getters for the key/value at position i in the node.

Defined at line 748 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

reference value (size_type i)

Defined at line 749 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

const_reference value (size_type i)

Defined at line 750 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

btree_node<Params> * child (field_type i)

Getters/setter for the child at position i in the node.

Defined at line 755 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

btree_node<Params> * start_child ()

Defined at line 756 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

btree_node<Params> *& mutable_child (field_type i)

Defined at line 757 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void clear_child (field_type i)

Defined at line 758 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void set_child_noupdate_position (field_type i, btree_node<Params> * c)

Defined at line 761 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void set_child (field_type i, btree_node<Params> * c)

Defined at line 765 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void init_child (field_type i, btree_node<Params> * c)

Defined at line 769 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K>

SearchResult<size_type, is_key_compare_to::value> lower_bound (const K & k, const key_compare & comp)

Returns the position of the first value whose key is not less than k.

Defined at line 776 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K>

size_type upper_bound (const K & k, const key_compare & comp)

Returns the position of the first value whose key is greater than k.

Defined at line 783 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename Compare>

SearchResult<size_type, btree_is_key_compare_to<Compare, key_type>::value> linear_search (const K & k, const Compare & comp)

Defined at line 790 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename Compare>

SearchResult<size_type, btree_is_key_compare_to<Compare, key_type>::value> binary_search (const K & k, const Compare & comp)

Defined at line 797 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename Compare>

SearchResult<size_type, false> linear_search_impl (const K & k, size_type s, const size_type e, const Compare & comp, std::false_type )

Returns the position of the first value whose key is not less than k using

linear search performed using plain compare.

Defined at line 806 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename Compare>

SearchResult<size_type, true> linear_search_impl (const K & k, size_type s, const size_type e, const Compare & comp, std::true_type )

Returns the position of the first value whose key is not less than k using

linear search performed using compare-to.

Defined at line 821 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename Compare>

SearchResult<size_type, false> binary_search_impl (const K & k, size_type s, size_type e, const Compare & comp, std::false_type )

Returns the position of the first value whose key is not less than k using

binary search performed using plain compare.

Defined at line 839 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename K, typename CompareTo>

SearchResult<size_type, true> binary_search_impl (const K & k, size_type s, size_type e, const CompareTo & comp, std::true_type )

Returns the position of the first value whose key is not less than k using

binary search performed using compare-to.

Defined at line 856 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename Compare>

bool is_ordered_correctly (field_type i, const Compare & comp)

Returns whether key i is ordered correctly with respect to the other keys

in the node. The motivation here is to detect comparators that violate

transitivity. Note: we only do comparisons of keys on this node rather than

the whole tree so that this is constant time.

Defined at line 898 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void init_leaf (field_type position, field_type max_count, btree_node<Params> * parent)

Node allocation/deletion routines.

Defined at line 949 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void init_internal (field_type position, btree_node<Params> * parent)

Defined at line 960 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void deallocate (const size_type size, btree_node<Params> * node, allocator_type * alloc)

Defined at line 969 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

template <typename... Args>

void emplace_value (field_type i, allocator_type * alloc, Args &&... args)

Emplaces a value at position i, shifting all existing values and

children at positions >= i to the right by 1.

Defined at line 1821 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void remove_values (field_type i, field_type to_erase, allocator_type * alloc)

Removes the values at positions [i, i + to_erase), shifting all existing

values and children after that range to the left by to_erase. Clears all

children between [i, i + to_erase).

Defined at line 1845 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void rebalance_right_to_left (field_type to_move, btree_node<Params> * right, allocator_type * alloc)

Rebalances a node with its right sibling.

Defined at line 1869 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void rebalance_left_to_right (field_type to_move, btree_node<Params> * right, allocator_type * alloc)

Defined at line 1909 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void split (int insert_position, btree_node<Params> * dest, allocator_type * alloc)

Splits a node, moving a portion of the node's values to its right sibling.

Defined at line 1956 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void merge (btree_node<Params> * src, allocator_type * alloc)

Merges a node with its right sibling, moving all of the values and the

delimiting key in the parent node onto itself, and deleting the src node.

Defined at line 1997 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

void clear_and_delete (btree_node<Params> * node, allocator_type * alloc)

Deletes a node and all of its children.

Defined at line 2025 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

Protected Methods

void btree_node<Params> ()

Defined at line 578 of file ../../third_party/abseil-cpp/src/absl/container/internal/btree.h

Friends

template <typename Params>

class btree_access

template <typename Params>

class BtreeNodePeer

template <typename N, typename R, typename P>

class btree_iterator

template <typename P>

class btree