template <typename, typename, typename, typename, typename, typename>

class WAVLTree

Defined at line 189 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

Public Members

static const bool SupportsConstantOrderErase

static const bool SupportsConstantOrderSize

static const bool IsAssociative

static const bool IsSequenced

Public Methods

void WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> ()

Default construction gives an empty tree.

Defined at line 229 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> (WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> && other_tree)

Rvalue construction is permitted, but will result in the move of the tree

contents from one instance of the list to the other (even for unmanaged

pointers)

Defined at line 245 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> & operator= (WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> && other_tree)

Rvalue assignment is permitted for managed trees, and when the target is

an empty tree of unmanaged pointers. Like Rvalue construction, it will

result in the move of the source contents to the destination.

Defined at line 250 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> (const WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> & )

move semantics only

Defined at line 260 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> & operator= (const WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> & )

Defined at line 261 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void ~WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> ()

Defined at line 263 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator begin ()

Standard begin/end, cbegin/cend iterator accessors.

Defined at line 272 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator begin ()

Defined at line 273 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator cbegin ()

Defined at line 274 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator end ()

Defined at line 276 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator end ()

Defined at line 277 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator cend ()

Defined at line 278 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator root ()

Iterator accessors to the root node.

Defined at line 281 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator croot ()

Defined at line 282 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator make_iterator (ValueType & obj)

make_iterator : construct an iterator out of a pointer to an object

Defined at line 285 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator make_iterator (const ValueType & obj)

Defined at line 286 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

bool is_empty ()

is_empty : True if the tree has at least one element in it, false otherwise.

Defined at line 291 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

typename PtrTraits::RefType front ()

front

Return a reference to the element at the front of the list without

removing it. It is an error to call front on an empty list.

Defined at line 297 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

typename PtrTraits::ConstRefType front ()

Defined at line 302 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

typename PtrTraits::RefType back ()

back

Return a reference to the element at the back of the list without

removing it. It is an error to call back on an empty list.

Defined at line 311 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

typename PtrTraits::ConstRefType back ()

Defined at line 316 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void insert (const PtrType & ptr)

Defined at line 321 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void insert (PtrType && ptr)

Defined at line 322 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

bool insert_or_find (const PtrType & ptr, iterator * iter)

insert or find

Insert the object pointed to by ptr if it is not already in the

tree, or find the object that the ptr collided with instead.

Parameters

ptr A pointer to the new object to insert.

iter An optional out parameter pointer to an iterator which will reference either the newly inserted item, or the item whose key collided with ptr.

Returns

true if there was no collision and the item was successfully

inserted. false otherwise.

Defined at line 337 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

bool insert_or_find (PtrType && ptr, iterator * iter)

Defined at line 341 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType insert_or_replace (const PtrType & ptr)

insert_or_replace

Find the element in the tree with the same key as *ptr and replace

it with ptr, then return the pointer to the element which was replaced.

If no element in the tree shares a key with *ptr, simply add ptr to

the tree and return nullptr.

Defined at line 365 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType insert_or_replace (PtrType && ptr)

Defined at line 367 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType pop_front ()

pop_front and pop_back

Removes either the left-most or right-most member of tree and transfers

the pointer to the caller. If the list is empty, return a nullptr

instance of PtrType.

Defined at line 390 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType pop_back ()

Defined at line 391 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator find (const KeyType & key)

find

Find the first node in the tree whose key matches "key" and return an

iterator to it. Return end() if no node in the tree has a key which

matches "key".

Defined at line 398 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator find (const KeyType & key)

Defined at line 414 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator upper_bound (const KeyType & key)

upper_bound

Find the first node in the tree whose key is strictly greater than the

caller provided key. Returns end() if no such node exists.

Defined at line 423 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator upper_bound (const KeyType & key)

Defined at line 427 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

const_iterator lower_bound (const KeyType & key)

lower_bound

Find the first node in the tree whose key is greater than or equal to the

caller provided key. Returns end() if no such node exists.

Defined at line 436 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

iterator lower_bound (const KeyType & key)

Defined at line 440 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType erase (const KeyType & key)

erase

Remove the first element in the tree whose key matches "key" and return a

pointer the removed object. Return a nullptr instance of PtrType if no

such element exists in the tree.

Defined at line 450 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType erase (const iterator & iter)

erase (direct)

Remove the object directly referenced either by "iter" or "obj" from the

tree and return a pointer to it. In the case of an iterator based erase,

return a nullptr instance of PtrType if the iterator is invalid. It is

an error to either use a valid iterator from a different tree instance,

or to attempt to remove an element which is not currently a member of

this tree instance.

Defined at line 460 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

PtrType erase (ValueType & obj)

Defined at line 467 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void clear ()

clear

Clear out the tree, unlinking all of the elements in the process. For

managed pointer types, this will release all references held by the tree

to the objects which were in it.

Defined at line 474 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void clear_unsafe ()

clear_unsafe

See comments in fidl::internal_wavl/intrusive_single_list.h

Think carefully before calling this!

Defined at line 536 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

void swap (WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, NodeTraits_, Observer_> & other)

swap : swaps the contents of two trees.

Defined at line 550 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

size_t size ()

size : return the current number of elements in the tree.

Defined at line 562 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

template <typename UnaryFn>

PtrType erase_if (UnaryFn fn)

erase_if

Find the first member of the list which satisfies the predicate given by

'fn' and erase it from the list, returning a referenced pointer to the

removed element. Return nullptr if no element satisfies the predicate.

Defined at line 570 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

template <typename UnaryFn>

const_iterator find_if (UnaryFn fn)

find_if

Find the first member of the list which satisfies the predicate given by

'fn' and return a const

to the PtrType in the list which refers to it.

Return nullptr if no member satisfies the predicate.

Defined at line 584 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

template <typename UnaryFn>

iterator find_if (UnaryFn fn)

Defined at line 593 of file ../../sdk/lib/fidl/cpp/wire/include/lib/fidl/cpp/wire/internal/intrusive_container/wavl_tree.h

Records

```
class iterator_impl
```

Friends

template <typenametypenametypenametypenametypenametypename>

class WAVLTreeChecker