template <typename Params>class btree_node
Defined at line 492 of file ../../third_party/abseil-cpp/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 572 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void btree_node<Params> (const btree_node<Params> & )Defined at line 573 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
btree_node<Params> & operator= (const btree_node<Params> & )Defined at line 574 of file ../../third_party/abseil-cpp/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 685 of file ../../third_party/abseil-cpp/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 688 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
field_type position ()Getter for the position of this node in its parent.
Defined at line 691 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
field_type start ()Getter for the offset of the first value in the `values` array.
Defined at line 694 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
field_type finish ()Getter for the offset after the last value in the `values` array.
Defined at line 701 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
field_type count ()Getters for the number of values stored in this node.
Defined at line 704 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
field_type max_count ()Defined at line 708 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
btree_node<Params> * parent ()Getter for the parent of this node.
Defined at line 718 of file ../../third_party/abseil-cpp/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 722 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void make_root ()Defined at line 723 of file ../../third_party/abseil-cpp/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 730 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
uint32_t generation ()Returns the generation for iterator validation.
Defined at line 738 of file ../../third_party/abseil-cpp/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 743 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void next_generation ()Updates the generation. We do this whenever the node is mutated.
Defined at line 747 of file ../../third_party/abseil-cpp/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 752 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
reference value (size_type i)Defined at line 753 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
const_reference value (size_type i)Defined at line 754 of file ../../third_party/abseil-cpp/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 759 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
btree_node<Params> * start_child ()Defined at line 760 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
btree_node<Params> *& mutable_child (field_type i)Defined at line 761 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void clear_child (field_type i)Defined at line 762 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void set_child_noupdate_position (field_type i, btree_node<Params> * c)Defined at line 765 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void set_child (field_type i, btree_node<Params> * c)Defined at line 769 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void init_child (field_type i, btree_node<Params> * c)Defined at line 773 of file ../../third_party/abseil-cpp/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 780 of file ../../third_party/abseil-cpp/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 787 of file ../../third_party/abseil-cpp/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 794 of file ../../third_party/abseil-cpp/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 801 of file ../../third_party/abseil-cpp/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 810 of file ../../third_party/abseil-cpp/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 825 of file ../../third_party/abseil-cpp/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 843 of file ../../third_party/abseil-cpp/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 860 of file ../../third_party/abseil-cpp/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 902 of file ../../third_party/abseil-cpp/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 953 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void init_internal (field_type position, btree_node<Params> * parent)Defined at line 964 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void deallocate (const size_type size, btree_node<Params> * node, allocator_type * alloc)Defined at line 973 of file ../../third_party/abseil-cpp/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 1803 of file ../../third_party/abseil-cpp/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 1827 of file ../../third_party/abseil-cpp/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 1851 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
void rebalance_left_to_right (field_type to_move, btree_node<Params> * right, allocator_type * alloc)Defined at line 1891 of file ../../third_party/abseil-cpp/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 1938 of file ../../third_party/abseil-cpp/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 1979 of file ../../third_party/abseil-cpp/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 2007 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
Protected Methods
void btree_node<Params> ()Defined at line 577 of file ../../third_party/abseil-cpp/absl/container/internal/btree.h
Friends
template <typename Params>class btree_accesstemplate <typename Params>class BtreeNodePeertemplate <typename N, typename R, typename P>class btree_iteratortemplate <typename P>class btree