#include "llvm/ADT/ImmutableSet.h"

Public Member Functions
	ImutAVLFactory ()

	ImutAVLFactory (BumpPtrAllocator &Alloc)

	~ImutAVLFactory ()

TreeTy *	add (TreeTy *T, value_type_ref V)

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 *	balanceTree (TreeTy L, value_type_ref V, TreeTy R)
	balanceTree - Used by add_internal and remove_internal to balance a newly created tree.

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)

void	markImmutable (TreeTy *T)
	markImmutable - Clears the mutable bits of a root and all of its descendants.

Static Protected Member Functions
static unsigned	maskCacheIndex (unsigned I)

static bool	compareTreeWithSection (TreeTy *T, typename TreeTy::iterator &TI, typename TreeTy::iterator &TE)

Friends
class	ImutAVLTree< ImutInfo >

Detailed Description

template<typename ImutInfo>
class llvm::ImutAVLFactory< ImutInfo >

Definition at line 359 of file ImmutableSet.h.

Constructor & Destructor Documentation

◆ ImutAVLFactory() [1/2]

template<typename ImutInfo >

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

inline

Definition at line 385 of file ImmutableSet.h.

◆ ImutAVLFactory() [2/2]

template<typename ImutInfo >

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

inline

Definition at line 388 of file ImmutableSet.h.

◆ ~ImutAVLFactory()

template<typename ImutInfo >

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

inline

Definition at line 391 of file ImmutableSet.h.

Member Function Documentation

◆ add()

template<typename ImutInfo >

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

inline

Definition at line 395 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::recoverNodes(), and T.

◆ add_internal()

template<typename ImutInfo >

TreeTy * llvm::ImutAVLFactory< ImutInfo >::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 530 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::add_internal(), assert(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::createNode(), llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::getRight(), llvm::ImutAVLFactory< ImutInfo >::getValue(), and llvm::ImutAVLFactory< ImutInfo >::isEmpty().

Referenced by llvm::ImutAVLFactory< ImutInfo >::add(), and llvm::ImutAVLFactory< ImutInfo >::add_internal().

◆ balanceTree()

template<typename ImutInfo >

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

inlineprotected

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

Definition at line 486 of file ImmutableSet.h.

References assert(), llvm::ImutAVLFactory< ImutInfo >::createNode(), llvm::ImutAVLFactory< ImutInfo >::getHeight(), llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::getRight(), and llvm::ImutAVLFactory< ImutInfo >::isEmpty().

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::combineTrees(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

◆ combineTrees()

template<typename ImutInfo >

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

inlineprotected

Definition at line 569 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::getValue(), llvm::ImutAVLFactory< ImutInfo >::isEmpty(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

Referenced by llvm::ImutAVLFactory< ImutInfo >::remove_internal().

◆ compareTreeWithSection()

template<typename ImutInfo >

static bool llvm::ImutAVLFactory< ImutInfo >::compareTreeWithSection	(	TreeTy *	T,
		typename TreeTy::iterator &	TI,
		typename TreeTy::iterator &	TE
	)

inlinestaticprotected

Definition at line 434 of file ImmutableSet.h.

References E, and I.

Referenced by llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree().

◆ createNode() [1/2]

template<typename ImutInfo >

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

inlineprotected

Definition at line 455 of file ImmutableSet.h.

References A, assert(), llvm::ImutAVLFactory< ImutInfo >::incrementHeight(), and T.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), and llvm::ImutAVLFactory< ImutInfo >::createNode().

◆ createNode() [2/2]

template<typename ImutInfo >

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

inlineprotected

Definition at line 471 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::createNode(), and llvm::ImutAVLFactory< ImutInfo >::getValue().

◆ getCanonicalTree()

template<typename ImutInfo >

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

inline

Definition at line 600 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::compareTreeWithSection(), llvm::ImutAVLTree< ImutInfo >::destroy(), llvm::ImutAVLFactory< ImutInfo >::maskCacheIndex(), and T.

◆ getEmptyTree()

template<typename ImutInfo >

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

inline

Definition at line 409 of file ImmutableSet.h.

◆ getHeight()

template<typename ImutInfo >

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

inlineprotected

Definition at line 420 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::balanceTree(), and llvm::ImutAVLFactory< ImutInfo >::incrementHeight().

◆ getLeft()

template<typename ImutInfo >

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

inlineprotected

Definition at line 421 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

◆ getRight()

template<typename ImutInfo >

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

inlineprotected

Definition at line 422 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

◆ getValue()

template<typename ImutInfo >

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

inlineprotected

Definition at line 423 of file ImmutableSet.h.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::combineTrees(), llvm::ImutAVLFactory< ImutInfo >::createNode(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

◆ incrementHeight()

template<typename ImutInfo >

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

inlineprotected

Definition at line 428 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::getHeight().

Referenced by llvm::ImutAVLFactory< ImutInfo >::createNode().

◆ isEmpty()

template<typename ImutInfo >

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

inlineprotected

Definition at line 419 of file ImmutableSet.h.

References T.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add_internal(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::combineTrees(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

◆ markImmutable()

template<typename ImutInfo >

void llvm::ImutAVLFactory< ImutInfo >::markImmutable ( TreeTy * T )

inlineprotected

markImmutable - Clears the mutable bits of a root and all of its descendants.

Definition at line 591 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::getRight(), and llvm::ImutAVLFactory< ImutInfo >::markImmutable().

Referenced by llvm::ImutAVLFactory< ImutInfo >::add(), llvm::ImutAVLFactory< ImutInfo >::markImmutable(), and llvm::ImutAVLFactory< ImutInfo >::remove().

◆ maskCacheIndex()

template<typename ImutInfo >

static unsigned llvm::ImutAVLFactory< ImutInfo >::maskCacheIndex ( unsigned I )

inlinestaticprotected

Definition at line 426 of file ImmutableSet.h.

References I.

Referenced by llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree().

◆ recoverNodes()

template<typename ImutInfo >

void llvm::ImutAVLFactory< ImutInfo >::recoverNodes ( )

inlineprotected

Definition at line 475 of file ImmutableSet.h.

References N.

Referenced by llvm::ImutAVLFactory< ImutInfo >::add(), and llvm::ImutAVLFactory< ImutInfo >::remove().

◆ remove()

template<typename ImutInfo >

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

inline

Definition at line 402 of file ImmutableSet.h.

References llvm::ImutAVLFactory< ImutInfo >::markImmutable(), llvm::ImutAVLFactory< ImutInfo >::recoverNodes(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and T.

◆ remove_internal()

template<typename ImutInfo >

TreeTy * llvm::ImutAVLFactory< ImutInfo >::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 550 of file ImmutableSet.h.

References assert(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::combineTrees(), llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::getRight(), llvm::ImutAVLFactory< ImutInfo >::getValue(), llvm::ImutAVLFactory< ImutInfo >::isEmpty(), llvm::ImutAVLFactory< ImutInfo >::remove_internal(), and T.

Referenced by llvm::ImutAVLFactory< ImutInfo >::remove(), and llvm::ImutAVLFactory< ImutInfo >::remove_internal().

◆ removeMinBinding()

template<typename ImutInfo >

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

inlineprotected

Definition at line 579 of file ImmutableSet.h.

References assert(), llvm::ImutAVLFactory< ImutInfo >::balanceTree(), llvm::ImutAVLFactory< ImutInfo >::getLeft(), llvm::ImutAVLFactory< ImutInfo >::getRight(), llvm::ImutAVLFactory< ImutInfo >::getValue(), llvm::ImutAVLFactory< ImutInfo >::isEmpty(), llvm::ImutAVLFactory< ImutInfo >::removeMinBinding(), and T.

Referenced by llvm::ImutAVLFactory< ImutInfo >::combineTrees(), and llvm::ImutAVLFactory< ImutInfo >::removeMinBinding().

Friends And Related Function Documentation

◆ ImutAVLTree< ImutInfo >

template<typename ImutInfo >

friend class ImutAVLTree< ImutInfo >

friend

Definition at line 351 of file ImmutableSet.h.

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()

◆ compareTreeWithSection()

◆ createNode() [1/2]

◆ createNode() [2/2]

◆ getCanonicalTree()

◆ getEmptyTree()

◆ getHeight()

◆ getLeft()

◆ getRight()

◆ getValue()

◆ incrementHeight()

◆ isEmpty()

◆ markImmutable()

◆ maskCacheIndex()

◆ recoverNodes()

◆ remove()

◆ remove_internal()

◆ removeMinBinding()

Friends And Related Function Documentation

◆ ImutAVLTree< ImutInfo >