#include "llvm/ADT/ImmutableSet.h"

Inheritance diagram for llvm::ImutAVLFactory< ImutInfo, Canonicalize >:

Public Member Functions
	ImutAVLFactory ()
	ImutAVLFactory (BumpPtrAllocator &Alloc)
	~ImutAVLFactory ()
TreeTy *	add (TreeTy *T, value_type_ref V)
template<typename CombineFn>
TreeTy *	mergeTrees (TreeTy A, TreeTy B, CombineFn Combine, bool KeepUnmatched, bool SkipShared=false)
	Merges `A` and `B` in a single traversal, sharing every subtree that the two operands do not overlap.
TreeTy *	unionTrees (TreeTy A, TreeTy B)
	Returns the set union of `A` and `B` (keeping `A's` element on matching keys).
TreeTy *	remove (TreeTy *T, key_type_ref V)
TreeTy *	getEmptyTree () const
TreeTy *	getCanonicalTree (TreeTy *TNew)

Protected Member Functions
bool	isEmpty (TreeTy *T) const
unsigned	getHeight (TreeTy *T) const
TreeTy *	getLeft (TreeTy *T) const
TreeTy *	getRight (TreeTy *T) const
value_type_ref	getValue (TreeTy *T) const
unsigned	incrementHeight (TreeTy L, TreeTy R) const
TreeTy *	createNode (TreeTy L, value_type_ref V, TreeTy R)
TreeTy *	createNode (TreeTy newLeft, TreeTy oldTree, TreeTy *newRight)
void	recoverNodes (TreeTy *Result)
TreeTy *	balanceTree (TreeTy L, value_type_ref V, TreeTy R)
	Used by add_internal and remove_internal to balance a newly created tree.
TreeTy *	joinTrees (TreeTy L, value_type_ref V, TreeTy R)
	Combines `L` and `R` with the value `V` (every key in `L` less than `V`, every key in `R` greater) into one balanced tree.
void	splitLookup (TreeTy T, key_type_ref K, TreeTy &L, const value_type &Match, TreeTy &R)
	Splits `T` into `L` (all keys less than `K`) and `R` (all keys greater than `K`).
template<typename CombineFn>
TreeTy *	transformTree (TreeTy *T, CombineFn &Combine, bool FromB)
	Rebuilds `T` with the same shape but each element replaced by `Combine` applied to it.
template<typename CombineFn>
TreeTy *	merge_internal (TreeTy A, TreeTy B, CombineFn &Combine, bool KeepUnmatched, bool SkipShared)
	Merges `A` and `B` by recursing over `A's` structure and splitting `B` at each of `A's` keys.
TreeTy *	add_internal (value_type_ref V, TreeTy *T)
	add_internal - Creates a new tree that includes the specified data and the data from the original tree.
TreeTy *	remove_internal (key_type_ref K, TreeTy *T)
	remove_internal - Creates a new tree that includes all the data from the original tree except the specified data.
TreeTy *	combineTrees (TreeTy L, TreeTy R)
TreeTy *	removeMinBinding (TreeTy T, TreeTy &Noderemoved)

Static Protected Member Functions
static unsigned	maskCacheIndex (unsigned I)

Friends
class	ImutAVLTree< ImutInfo, Canonicalize >

Detailed Description

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

Definition at line 401 of file ImmutableSet.h.

Constructor & Destructor Documentation

◆ ImutAVLFactory() [1/2]

template<typename ImutInfo, bool Canonicalize>

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

inline

Definition at line 428 of file ImmutableSet.h.

◆ ImutAVLFactory() [2/2]

template<typename ImutInfo, bool Canonicalize>

llvm::ImutAVLFactory< ImutInfo, Canonicalize >::ImutAVLFactory ( BumpPtrAllocator & Alloc )

inline

Definition at line 431 of file ImmutableSet.h.

References llvm::Alloc.

◆ ~ImutAVLFactory()

template<typename ImutInfo, bool Canonicalize>

llvm::ImutAVLFactory< ImutInfo, Canonicalize >::~ImutAVLFactory ( )

inline

Definition at line 434 of file ImmutableSet.h.

Member Function Documentation

◆ add()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::add	(	TreeTy *	T,
		value_type_ref	V )

inline

Definition at line 438 of file ImmutableSet.h.

References add_internal(), recoverNodes(), and T.

◆ add_internal()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::add_internal	(	value_type_ref	V,
		TreeTy *	T )

inlineprotected

add_internal - Creates a new tree that includes the specified data and the data from the original tree.

If the original tree already contained the data item, the original tree is returned.

Definition at line 710 of file ImmutableSet.h.

References add_internal(), assert(), balanceTree(), createNode(), getLeft(), getRight(), getValue(), isEmpty(), and T.

Referenced by add(), and add_internal().

◆ balanceTree()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::balanceTree	(	TreeTy *	L,
		value_type_ref	V,
		TreeTy *	R )

inlineprotected

Used by add_internal and remove_internal to balance a newly created tree.

Definition at line 557 of file ImmutableSet.h.

References assert(), createNode(), getHeight(), getLeft(), getRight(), and isEmpty().

Referenced by add_internal(), combineTrees(), joinTrees(), remove_internal(), and removeMinBinding().

◆ combineTrees()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::combineTrees	(	TreeTy *	L,
		TreeTy *	R )

inlineprotected

Definition at line 770 of file ImmutableSet.h.

References balanceTree(), getValue(), isEmpty(), and removeMinBinding().

Referenced by remove_internal().

◆ createNode() [1/2]

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::createNode	(	TreeTy *	L,
		value_type_ref	V,
		TreeTy *	R )

inlineprotected

Definition at line 518 of file ImmutableSet.h.

References A(), assert(), incrementHeight(), and T.

Referenced by add_internal(), balanceTree(), createNode(), joinTrees(), and transformTree().

◆ createNode() [2/2]

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::createNode	(	TreeTy *	newLeft,
		TreeTy *	oldTree,
		TreeTy *	newRight )

inlineprotected

Definition at line 534 of file ImmutableSet.h.

References createNode(), and getValue().

◆ getCanonicalTree()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getCanonicalTree ( TreeTy * TNew )

inline

Definition at line 791 of file ImmutableSet.h.

References llvm::ImutAVLDetail::CanonicalCache< ImutAVLTree< ImutInfo, Canonicalize >, Canonicalize >::Cache, llvm::ImutAVLTree< ImutInfo, Canonicalize >::destroy(), llvm::ImutAVLTree< ImutInfo, Canonicalize >::isEqual(), maskCacheIndex(), and T.

◆ getEmptyTree()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getEmptyTree ( ) const

inline

Definition at line 483 of file ImmutableSet.h.

Referenced by splitLookup().

◆ getHeight()

template<typename ImutInfo, bool Canonicalize>

unsigned llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getHeight ( TreeTy * T ) const

inlineprotected

Definition at line 494 of file ImmutableSet.h.

References T.

Referenced by balanceTree(), incrementHeight(), and joinTrees().

◆ getLeft()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getLeft ( TreeTy * T ) const

inlineprotected

Definition at line 495 of file ImmutableSet.h.

References T.

Referenced by add_internal(), balanceTree(), joinTrees(), merge_internal(), remove_internal(), removeMinBinding(), splitLookup(), and transformTree().

◆ getRight()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getRight ( TreeTy * T ) const

inlineprotected

Definition at line 496 of file ImmutableSet.h.

References T.

Referenced by add_internal(), balanceTree(), joinTrees(), merge_internal(), remove_internal(), removeMinBinding(), splitLookup(), and transformTree().

◆ getValue()

template<typename ImutInfo, bool Canonicalize>

value_type_ref llvm::ImutAVLFactory< ImutInfo, Canonicalize >::getValue ( TreeTy * T ) const

inlineprotected

Definition at line 497 of file ImmutableSet.h.

References T.

Referenced by add_internal(), combineTrees(), createNode(), joinTrees(), merge_internal(), remove_internal(), removeMinBinding(), splitLookup(), and transformTree().

◆ incrementHeight()

template<typename ImutInfo, bool Canonicalize>

unsigned llvm::ImutAVLFactory< ImutInfo, Canonicalize >::incrementHeight	(	TreeTy *	L,
		TreeTy *	R ) const

inlineprotected

Definition at line 502 of file ImmutableSet.h.

References getHeight().

Referenced by createNode().

◆ isEmpty()

template<typename ImutInfo, bool Canonicalize>

bool llvm::ImutAVLFactory< ImutInfo, Canonicalize >::isEmpty ( TreeTy * T ) const

inlineprotected

Definition at line 493 of file ImmutableSet.h.

References T.

Referenced by add_internal(), balanceTree(), combineTrees(), merge_internal(), remove_internal(), removeMinBinding(), splitLookup(), and transformTree().

◆ joinTrees()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::joinTrees	(	TreeTy *	L,
		value_type_ref	V,
		TreeTy *	R )

inlineprotected

Combines L and R with the value V (every key in L less than V, every key in R greater) into one balanced tree.

Unlike balanceTree this tolerates an arbitrary height difference between L and R: it descends the taller side's spine and rebalances on the way back up, exactly as an insertion would.

Definition at line 603 of file ImmutableSet.h.

References balanceTree(), createNode(), getHeight(), getLeft(), getRight(), getValue(), and joinTrees().

Referenced by joinTrees(), merge_internal(), and splitLookup().

◆ maskCacheIndex()

template<typename ImutInfo, bool Canonicalize>

unsigned llvm::ImutAVLFactory< ImutInfo, Canonicalize >::maskCacheIndex ( unsigned I )

inlinestaticprotected

Definition at line 500 of file ImmutableSet.h.

References I.

Referenced by getCanonicalTree().

◆ merge_internal()

template<typename ImutInfo, bool Canonicalize>

template<typename CombineFn>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::merge_internal	(	TreeTy *	A,
		TreeTy *	B,
		CombineFn &	Combine,
		bool	KeepUnmatched,
		bool	SkipShared )

inlineprotected

Merges A and B by recursing over A's structure and splitting B at each of A's keys.

For a key in both, the stored element is Combine(AElem, BElem). KeepUnmatched controls keys unique to one side: when true, such elements (and whole non-overlapping subtrees) are taken unchanged and shared, and Combine is invoked only on keys present in both (valid when Combine is an identity for a missing side, e.g. a set union or a lattice join with an identity element); when false every key is passed through Combine with the absent side null (needed for a join that transforms unmatched keys, e.g. liveness downgrading Must to Maybe).

Definition at line 664 of file ImmutableSet.h.

References A(), B(), Combine, getLeft(), getRight(), getValue(), isEmpty(), joinTrees(), merge_internal(), splitLookup(), and transformTree().

Referenced by merge_internal(), and mergeTrees().

◆ mergeTrees()

template<typename ImutInfo, bool Canonicalize>

template<typename CombineFn>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::mergeTrees	(	TreeTy *	A,
		TreeTy *	B,
		CombineFn	Combine,
		bool	KeepUnmatched,
		bool	SkipShared = false )

inline

Merges A and B in a single traversal, sharing every subtree that the two operands do not overlap.

Combine(AElem, BElem) produces the element stored for a key present in both; KeepUnmatched governs keys unique to one side (see merge_internal). For merging |B| entries into |A| (|B| <= |A|) this costs O(|B| * log(|A|/|B| + 1)) and copies each spine node at most once, versus O(|B| * log|A|) repeated add descents. A and B must be immutable. This does not short-circuit equal or empty operands (merge_internal handles them correctly but not specially); callers that want those fast paths, or size-driven operand ordering, should apply them first (see ImmutableSet::Factory::unionSets).

Definition at line 455 of file ImmutableSet.h.

References A(), B(), Combine, merge_internal(), recoverNodes(), and T.

Referenced by unionTrees().

◆ recoverNodes()

template<typename ImutInfo, bool Canonicalize>

void llvm::ImutAVLFactory< ImutInfo, Canonicalize >::recoverNodes ( TreeTy * Result )

inlineprotected

Definition at line 538 of file ImmutableSet.h.

References N, and llvm::reverse().

Referenced by add(), mergeTrees(), and remove().

◆ remove()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::remove	(	TreeTy *	T,
		key_type_ref	V )

inline

Definition at line 477 of file ImmutableSet.h.

References recoverNodes(), remove_internal(), and T.

◆ remove_internal()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::remove_internal	(	key_type_ref	K,
		TreeTy *	T )

inlineprotected

remove_internal - Creates a new tree that includes all the data from the original tree except the specified data.

If the specified data did not exist in the original tree, the original tree is returned.

Definition at line 745 of file ImmutableSet.h.

References assert(), balanceTree(), combineTrees(), getLeft(), getRight(), getValue(), isEmpty(), remove_internal(), and T.

Referenced by remove(), and remove_internal().

◆ removeMinBinding()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::removeMinBinding	(	TreeTy *	T,
		TreeTy *&	Noderemoved )

inlineprotected

Definition at line 780 of file ImmutableSet.h.

References assert(), balanceTree(), getLeft(), getRight(), getValue(), isEmpty(), removeMinBinding(), and T.

Referenced by combineTrees(), and removeMinBinding().

◆ splitLookup()

template<typename ImutInfo, bool Canonicalize>

void llvm::ImutAVLFactory< ImutInfo, Canonicalize >::splitLookup	(	TreeTy *	T,
		key_type_ref	K,
		TreeTy *&	L,
		const value_type *&	Match,
		TreeTy *&	R )

inlineprotected

Splits T into L (all keys less than K) and R (all keys greater than K).

If K is present in T, Match is set to point at its element (which is dropped from L and R); otherwise Match is null.

Definition at line 614 of file ImmutableSet.h.

References getEmptyTree(), getLeft(), getRight(), getValue(), isEmpty(), joinTrees(), splitLookup(), and T.

Referenced by merge_internal(), and splitLookup().

◆ transformTree()

template<typename ImutInfo, bool Canonicalize>

template<typename CombineFn>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::transformTree	(	TreeTy *	T,
		CombineFn &	Combine,
		bool	FromB )

inlineprotected

Rebuilds T with the same shape but each element replaced by Combine applied to it.

FromB selects which side of Combine the element is passed on (it is the sole non-null argument).

Definition at line 644 of file ImmutableSet.h.

References Combine, createNode(), E(), getLeft(), getRight(), getValue(), isEmpty(), T, and transformTree().

Referenced by merge_internal(), and transformTree().

◆ unionTrees()

template<typename ImutInfo, bool Canonicalize>

TreeTy * llvm::ImutAVLFactory< ImutInfo, Canonicalize >::unionTrees	(	TreeTy *	A,
		TreeTy *	B )

inline

Returns the set union of A and B (keeping A's element on matching keys).

Shorthand for the fully sharing mergeTrees.

Definition at line 464 of file ImmutableSet.h.

References A(), B(), and mergeTrees().

◆ ImutAVLTree< ImutInfo, Canonicalize >

template<typename ImutInfo, bool Canonicalize>

friend class ImutAVLTree< ImutInfo, Canonicalize >

friend

Definition at line 391 of file ImmutableSet.h.

References llvm::Tree.

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

include/llvm/ADT/ImmutableSet.h

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ ImutAVLFactory() [1/2]

◆ ImutAVLFactory() [2/2]

◆ ~ImutAVLFactory()

Member Function Documentation

◆ add()

◆ add_internal()

◆ balanceTree()

◆ combineTrees()

◆ createNode() [1/2]

◆ createNode() [2/2]

◆ getCanonicalTree()

◆ getEmptyTree()

◆ getHeight()

◆ getLeft()

◆ getRight()

◆ getValue()

◆ incrementHeight()

◆ isEmpty()

◆ joinTrees()

◆ maskCacheIndex()

◆ merge_internal()

◆ mergeTrees()

◆ recoverNodes()

◆ remove()

◆ remove_internal()

◆ removeMinBinding()

◆ splitLookup()

◆ transformTree()

◆ unionTrees()

Friends And Related Symbol Documentation

◆ ImutAVLTree< ImutInfo, Canonicalize >