template <typename Key, typename ValueType, typename Observer = NoopObserver, typename Allocator = GlobalSlabAllocator, typename Traits = DefaultTypeTraits<ValueType>, size_t NodeSize = 256, IteratorValidation Validation = IteratorValidation::Untracked, TreeValidation Validator = TreeValidation::None>class BTree
Defined at line 153 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
Public Methods
void BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> (Allocator allocator)Defined at line 166 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> ()Defined at line 167 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void ~BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> ()Defined at line 168 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> (const BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> & )Defined at line 173 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> (BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> && other)Defined at line 174 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> & operator= (const BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> & )Defined at line 179 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> & operator= (BTree<Key, ValueType, Observer, Allocator, Traits, NodeSize, Validation, Validator> && other)Defined at line 180 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
bool is_empty ()Defined at line 192 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator begin ()Defined at line 194 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator begin ()Defined at line 195 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator end ()Defined at line 196 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator end ()Defined at line 203 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (const Key & 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 225 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (iteratorhint,const Key &key,ValueType &&value)
Defined at line 237 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (const Key & key, const ValueType & value)Defined at line 256 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator insert (iteratorhint,const Key &key,const ValueType &value)
Defined at line 259 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void update (iterator iter, ValueType && value)Updates the value of the item referenced by the iterator.
The iterator is assumed to be valid. The old value is reclaimed (if managed), and the new value
takes its place.
As this does not change the structure of the tree this does not invalidate any iterators.
Defined at line 268 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
void update (iterator iter, const ValueType & value)Defined at line 276 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 284 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
std::pair<Key, ValueType> take (iterator iter)Similar to |erase|, but returns ownership of the stored item.
Defined at line 293 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator upper_bound (const Key & key)Return an iterator to the first item whose key is strictly greater than |key|, or end() if no
such item.
Defined at line 302 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator upper_bound (const Key & key)Defined at line 312 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator lower_bound (const Key & 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 319 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator lower_bound (const Key & key)Defined at line 334 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
template <typename SubTree, typename Leaf>
zx_status_t walk (SubTree subtree, Leaf leaf)Efficiently walks the tree, leveraging the augmented state at each node to potentially prune
entire subtrees from the traversal.
|subtree| is a callable with the signature:
zx_status_t subtree(const typename Observer::AugmentedState
&
state)
It is called for each intermediate node. Returning ZX_OK will cause the walk to descend into
the node's children. Returning ZX_ERR_NEXT will skip the subtree entirely.
|leaf| is a callable with the signature:
zx_status_t leaf(const typename Observer::AugmentedState
&
state,
const_iterator begin, const_iterator end)
It is called for each leaf node. |begin| and |end| are inclusive iterators to the first and
last items in the leaf.
Both |subtree| and |leaf| can return ZX_ERR_STOP to terminate the walk early and return ZX_OK.
Any other error status will also terminate the walk and be returned to the caller.
Defined at line 356 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
const_iterator find (const Key & key)Return an iterator to the item whose key is exactly |key|, or end() if no such item.
Defined at line 419 of file ../../zircon/kernel/lib/btree/include/lib/btree.h
iterator find (const Key & key)Defined at line 428 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 459 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 839 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 1355 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 887 of file ../../zircon/kernel/lib/btree/include/lib/btree.h