template <typename ValueType, typename Allocator = GlobalSlabAllocator, typename Traits = DefaultTypeTraits<ValueType>, IteratorValidation Validation = IteratorValidation::Untracked, TreeValidation Validator = TreeValidation::None>class BTree
Defined at line 132 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
Public Methods
void BTree<ValueType, Allocator, Traits, Validation, Validator> (Allocator allocator)Defined at line 144 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<ValueType, Allocator, Traits, Validation, Validator> ()Defined at line 145 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void ~BTree<ValueType, Allocator, Traits, Validation, Validator> ()Defined at line 146 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<ValueType, Allocator, Traits, Validation, Validator> (const BTree<ValueType, Allocator, Traits, Validation, Validator> & )Defined at line 151 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<ValueType, Allocator, Traits, Validation, Validator> (BTree<ValueType, Allocator, Traits, Validation, Validator> && other)Defined at line 152 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
BTree<ValueType, Allocator, Traits, Validation, Validator> & operator= (const BTree<ValueType, Allocator, Traits, Validation, Validator> & )Defined at line 157 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
BTree<ValueType, Allocator, Traits, Validation, Validator> & operator= (BTree<ValueType, Allocator, Traits, Validation, Validator> && other)Defined at line 158 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
bool is_empty ()Defined at line 170 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator begin ()Defined at line 172 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator begin ()Defined at line 173 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator end ()Defined at line 174 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator end ()Defined at line 181 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (uint64_t key, ValueType && value)Inserts the provided value using the specified key. It is an error to insert a duplicate key
and attempting to do so will either cause a runtime assertion failure or datastructure
corruption.
If internal nodes needed to, but could not be, allocated then the end() iterator is returned,
otherwise an iterator to the new item is returned. If end() is returned, and tree is holding
managed pointers, then the managed pointer is released and not returned. In all cases if end()
is returned the tree is left in an unmodified state.
Insert takes an option |hint| iterator to an item to insert near. The provided iterator can be
to an invalid location (i.e. end()), but may not be invalid due to becoming stale from insert
or erase.
After an insertion all iterators, except the one returned, are stale and must not be used.
Defined at line 203 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (iterator hint, uint64_t key, ValueType && value)Defined at line 215 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (uint64_t key, const ValueType & value)Defined at line 234 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (iterator hint, uint64_t key, const ValueType & value)Defined at line 237 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator erase (iterator iter)Removes the item (key/value pair) referenced by the iterator. If storing managed pointers the
item is released.
Returns an iterator to the item following |iter|.
After an erase all iterators, except the one returned, are stale and must not be used.
Defined at line 246 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
std::pair<uint64_t, ValueType> take (iterator iter)Similar to |erase|, but returns ownership of the stored item.
Defined at line 255 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator upper_bound (uint64_t key)Return an iterator to the first item whose key is strictly greater than |key|, or end() if no
such item.
Defined at line 264 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator upper_bound (uint64_t key)Defined at line 274 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator lower_bound (uint64_t key)Return an iterator to the first item whose key is greater than or equal to |key|, or end() if
no such item.
Defined at line 281 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator lower_bound (uint64_t key)Defined at line 296 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator find (uint64_t key)Return an iterator to the item whose key is exactly |key|, or end() if no such item.
Defined at line 302 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator find (uint64_t key)Defined at line 311 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void dump ()Print a representation of the tree to stdout. Is implemented via recursion and may use
arbitrary stack.
Defined at line 348 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void clear ()Clears all content from the tree, returning it to the empty state. Any managed pointers will be
released and all iterators are invalidated.
Defined at line 626 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
Utilization calculate_utilization_slow ()Walks the tree and counts how many nodes there are and how utilized they are. This method is
essentially O(N) as all nodes must be walked.
TODO(https://fxbug.dev/494059275): Provide a template option to select between persistently
storing this utilization, at the cost of increasing the storage of the BTree class, and having
this be a slow method.
Defined at line 1051 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
bool debug_validate_tree ()Debug helper that checks if a tree is valid, intended for use in unittests and/or during
development. Is implemented using recursion and will only return false if using a
TreeValidation::None, otherwise it will trigger an assertion failure on an invalid tree.
Defined at line 674 of file ../../zircon/kernel/lib/btree/include/lib/btree.h