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

class WAVLTree

Defined at line 192 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

Public Members

static SizeOrder ListSizeOrder

static const bool SupportsConstantOrderErase

static const bool SupportsConstantOrderSize

static const bool IsAssociative

static const bool IsSequenced

Public Methods

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

Default construction gives an empty tree.

Defined at line 234 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

void WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, ListSizeOrder_, NodeTraits_, Observer_> (WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, ListSizeOrder_, 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 250 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, ListSizeOrder_, NodeTraits_, Observer_> & operator= (WAVLTree<KeyType_, PtrType_, KeyTraits_, TagType_, ListSizeOrder_, 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 255 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

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

Defined at line 264 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator begin ()

Standard begin/end, cbegin/cend iterator accessors.

Defined at line 273 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator begin ()

Defined at line 274 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator cbegin ()

Defined at line 275 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator end ()

Defined at line 277 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator end ()

Defined at line 278 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator cend ()

Defined at line 279 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator root ()

Iterator accessors to the root node.

Defined at line 282 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator root ()

Defined at line 283 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator croot ()

Defined at line 284 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator make_iterator (ValueType & obj)

make_iterator : Construct an iterator out of a pointer to an object.

Defined at line 287 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator make_iterator (const ValueType & obj)

Defined at line 291 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator materialize_iterator (ValueType & obj)

materialize_iterator : Construct an iterator out of a pointer to an object,

without a reference to the container.

USE WITH CAUTION: The caller is responsible for ensuring it is safe to

access the container when using this iterator. In particular, static lock

analysis will not detect access without holding the required locks guarding

the container.

Defined at line 303 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

const_iterator materialize_iterator (const ValueType & obj)

Defined at line 307 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

bool is_empty ()

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

Defined at line 313 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 319 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

typename PtrTraits::ConstRefType front ()

Defined at line 324 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 333 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

typename PtrTraits::ConstRefType back ()

Defined at line 338 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

void insert (const PtrType & ptr)

Defined at line 343 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

void insert (PtrType && ptr)

Defined at line 344 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 359 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

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

Defined at line 363 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 387 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

PtrType insert_or_replace (PtrType && ptr)

Defined at line 389 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 412 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

PtrType pop_back ()

Defined at line 413 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 420 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator find (const KeyType & key)

Defined at line 436 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 445 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator upper_bound (const KeyType & key)

Defined at line 449 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 458 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

iterator lower_bound (const KeyType & key)

Defined at line 462 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 472 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 482 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

PtrType erase (ValueType & obj)

Defined at line 489 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 496 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

void clear_unsafe ()

clear_unsafe

See comments in fbl/intrusive_single_list.h

Think carefully before calling this!

Defined at line 566 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

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

swap : swaps the contents of two trees.

Defined at line 580 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

size_t size_slow ()

size_slow

count the elements in the list in O(n) fashion

Defined at line 594 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

size_t size ()

size : Only allowed when the user has selected an SizeOrder::Constant for this list.

Defined at line 611 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 624 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_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 638 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

template <typename UnaryFn>

iterator find_if (UnaryFn fn)

Defined at line 647 of file ../../zircon/system/ulib/fbl/include/fbl/intrusive_wavl_tree.h

Records

```
class iterator_impl
```

Friends

template <typenametypenametypenametypenameSizeOrdertypenametypename>

class WAVLTreeChecker