llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize > Class Template Reference

Bidirectional in-order iterator over the nodes of an ImutAVLTree. More...

#include "llvm/ADT/ImmutableSet.h"

Public Types
using	iterator_category = std::bidirectional_iterator_tag
using	value_type = ImutAVLTree<ImutInfo, Canonicalize>
using	difference_type = std::ptrdiff_t
using	pointer = value_type *
using	reference = value_type &
using	TreeTy = ImutAVLTree<ImutInfo, Canonicalize>

Public Member Functions
	ImutAVLTreeInOrderIterator ()=default
	ImutAVLTreeInOrderIterator (const TreeTy *Root)
bool	operator== (const ImutAVLTreeInOrderIterator &x) const
bool	operator!= (const ImutAVLTreeInOrderIterator &x) const
TreeTy &	operator* () const
TreeTy *	operator-> () const
ImutAVLTreeInOrderIterator &	operator++ ()
ImutAVLTreeInOrderIterator &	operator-- ()
void	skipSubTree ()
	Move to the in-order successor of the entire subtree rooted at the current node, i.e.

Detailed Description

template<typename ImutInfo, bool Canonicalize>
class llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >

Bidirectional in-order iterator over the nodes of an ImutAVLTree.

The iterator keeps the chain of ancestors from the root down to the current node on an explicit stack of plain node pointers, and decides which way to move next by inspecting whether it is ascending from a node's left or right child. This avoids storing any per-node visit-state: there is no need to remember "have I already visited this node's left/right subtree", because that is recovered by comparing the child we just left against the parent's left and right pointers.

A node's parent cannot be cached in the node itself, because these trees are persistent and structurally shared: a single node may appear as the child of different parents across different tree versions. The ancestor stack is therefore the per-traversal parent chain.

Definition at line 703 of file ImmutableSet.h.

Member Typedef Documentation

difference_type

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::difference_type = std::ptrdiff_t

Definition at line 707 of file ImmutableSet.h.

iterator_category

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::iterator_category = std::bidirectional_iterator_tag

Definition at line 705 of file ImmutableSet.h.

pointer

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::pointer = value_type *

Definition at line 708 of file ImmutableSet.h.

reference

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::reference = value_type &

Definition at line 709 of file ImmutableSet.h.

TreeTy

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::TreeTy = ImutAVLTree<ImutInfo, Canonicalize>

Definition at line 711 of file ImmutableSet.h.

value_type

template<typename ImutInfo, bool Canonicalize>

using llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::value_type = ImutAVLTree<ImutInfo, Canonicalize>

Definition at line 706 of file ImmutableSet.h.

Constructor & Destructor Documentation

ImutAVLTreeInOrderIterator() [1/2]

template<typename ImutInfo, bool Canonicalize>

llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::ImutAVLTreeInOrderIterator ( )

default

Referenced by operator!=(), operator++(), operator--(), and operator==().

ImutAVLTreeInOrderIterator() [2/2]

template<typename ImutInfo, bool Canonicalize>

llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::ImutAVLTreeInOrderIterator ( const TreeTy * Root )

inline

Definition at line 754 of file ImmutableSet.h.

Member Function Documentation

operator!=()

template<typename ImutInfo, bool Canonicalize>

bool llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator!= ( const ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize > & x ) const

inline

Definition at line 768 of file ImmutableSet.h.

References ImutAVLTreeInOrderIterator().

operator*()

template<typename ImutInfo, bool Canonicalize>

TreeTy & llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator* ( ) const

inline

Definition at line 772 of file ImmutableSet.h.

operator++()

template<typename ImutInfo, bool Canonicalize>

ImutAVLTreeInOrderIterator & llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator++ ( )

inline

Definition at line 775 of file ImmutableSet.h.

References assert(), and ImutAVLTreeInOrderIterator().

operator--()

template<typename ImutInfo, bool Canonicalize>

ImutAVLTreeInOrderIterator & llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator-- ( )

inline

Definition at line 787 of file ImmutableSet.h.

References assert(), and ImutAVLTreeInOrderIterator().

operator->()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator-> ( ) const

inline

Definition at line 773 of file ImmutableSet.h.

operator==()

template<typename ImutInfo, bool Canonicalize>

bool llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::operator== ( const ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize > & x ) const

inline

Definition at line 763 of file ImmutableSet.h.

References ImutAVLTreeInOrderIterator().

skipSubTree()

template<typename ImutInfo, bool Canonicalize>

void llvm::ImutAVLTreeInOrderIterator< ImutInfo, Canonicalize >::skipSubTree ( )

inline

Move to the in-order successor of the entire subtree rooted at the current node, i.e.

skip the current node together with its right subtree. This is exactly the ascent half of operator++.

Definition at line 801 of file ImmutableSet.h.

References assert().

Referenced by llvm::ImutAVLTree< ValInfo, Canonicalize >::isEqual().

---

The documentation for this class was generated from the following file:

• include/llvm/ADT/ImmutableSet.h