llvm::ImutAVLFactory< ImutInfo > Class Template Reference

#include <ImmutableSet.h>

List of all members.

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)
TreeTy *	add_internal (value_type_ref V, TreeTy *T)
TreeTy *	remove_internal (key_type_ref K, TreeTy *T)
TreeTy *	combineTrees (TreeTy *L, TreeTy *R)
TreeTy *	removeMinBinding (TreeTy *T, TreeTy *&Noderemoved)
void	markImmutable (TreeTy *T)
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 364 of file ImmutableSet.h.

---

Constructor & Destructor Documentation

template<typename ImutInfo >

llvm::ImutAVLFactory< ImutInfo >::ImutAVLFactory

(

)

[inline]

Definition at line 390 of file ImmutableSet.h.

template<typename ImutInfo >

llvm::ImutAVLFactory< ImutInfo >::ImutAVLFactory

(

BumpPtrAllocator &

Alloc

)

[inline]

Definition at line 393 of file ImmutableSet.h.

template<typename ImutInfo >

llvm::ImutAVLFactory< ImutInfo >::~ImutAVLFactory

(

)

[inline]

Definition at line 396 of file ImmutableSet.h.

---

Member Function Documentation

template<typename ImutInfo >

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

Definition at line 400 of file ImmutableSet.h.

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::Factory::add(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::add(), llvm::ImmutableSet< ValT, ValInfo >::Factory::add(), and llvm::ImmutableSetRef< ValT, ValInfo >::add().

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::add_internal	(	value_type_ref	V,
		TreeTy *	T
	)		[inline, protected]

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 538 of file ImmutableSet.h.

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

template<typename ImutInfo >

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

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

Definition at line 494 of file ImmutableSet.h.

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::combineTrees	(	TreeTy *	L,
		TreeTy *	R
	)		[inline, protected]

Definition at line 577 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().

template<typename ImutInfo >

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

Definition at line 442 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::begin(), llvm::ImutAVLTree< ImutInfo >::end(), I, and llvm::ImutAVLTree< ImutInfo >::isElementEqual().

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

template<typename ImutInfo >

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

Definition at line 463 of file ImmutableSet.h.

References llvm::ARM_PROC::A, llvm::BumpPtrAllocatorImpl< AllocatorT, SlabSize, SizeThreshold >::Allocate(), llvm::ImutAVLFactory< ImutInfo >::incrementHeight(), and T.

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::createNode	(	TreeTy *	newLeft,
		TreeTy *	oldTree,
		TreeTy *	newRight
	)		[inline, protected]

Definition at line 479 of file ImmutableSet.h.

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree

(

TreeTy *

TNew

)

[inline]

Definition at line 608 of file ImmutableSet.h.

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::Factory::add(), llvm::ImmutableSet< ValT, ValInfo >::Factory::add(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::asImmutableMap(), llvm::ImmutableSetRef< ValT, ValInfo >::asImmutableSet(), llvm::ImmutableMap< KeyT, ValT, ValInfo >::Factory::remove(), and llvm::ImmutableSet< ValT, ValInfo >::Factory::remove().

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::getEmptyTree

(

)

const [inline]

Definition at line 414 of file ImmutableSet.h.

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::Factory::getEmptyMap(), and llvm::ImmutableSet< ValT, ValInfo >::Factory::getEmptySet().

template<typename ImutInfo >

unsigned llvm::ImutAVLFactory< ImutInfo >::getHeight

(

TreeTy *

T

)

const [inline, protected]

Definition at line 426 of file ImmutableSet.h.

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

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::getLeft

(

TreeTy *

T

)

const [inline, protected]

Definition at line 427 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getLeft().

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::getRight

(

TreeTy *

T

)

const [inline, protected]

Definition at line 428 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::getRight().

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

template<typename ImutInfo >

value_type_ref llvm::ImutAVLFactory< ImutInfo >::getValue

(

TreeTy *

T

)

const [inline, protected]

Definition at line 429 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().

template<typename ImutInfo >

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

Definition at line 436 of file ImmutableSet.h.

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

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

template<typename ImutInfo >

bool llvm::ImutAVLFactory< ImutInfo >::isEmpty

(

TreeTy *

T

)

const [inline, protected]

Definition at line 425 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().

template<typename ImutInfo >

void llvm::ImutAVLFactory< ImutInfo >::markImmutable

(

TreeTy *

T

)

[inline, protected]

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

Definition at line 599 of file ImmutableSet.h.

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

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

template<typename ImutInfo >

static unsigned llvm::ImutAVLFactory< ImutInfo >::maskCacheIndex

(

unsigned

I

)

[inline, static, protected]

Definition at line 432 of file ImmutableSet.h.

Referenced by llvm::ImutAVLTree< ImutInfo >::destroy(), and llvm::ImutAVLFactory< ImutInfo >::getCanonicalTree().

template<typename ImutInfo >

void llvm::ImutAVLFactory< ImutInfo >::recoverNodes

(

)

[inline, protected]

Definition at line 483 of file ImmutableSet.h.

References llvm::ImutAVLTree< ImutInfo >::destroy(), and N.

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

template<typename ImutInfo >

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

Definition at line 407 of file ImmutableSet.h.

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

Referenced by llvm::ImmutableMap< KeyT, ValT, ValInfo >::Factory::remove(), llvm::ImmutableMapRef< KeyT, ValT, ValInfo >::remove(), llvm::ImmutableSet< ValT, ValInfo >::Factory::remove(), and llvm::ImmutableSetRef< ValT, ValInfo >::remove().

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::remove_internal	(	key_type_ref	K,
		TreeTy *	T
	)		[inline, protected]

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 558 of file ImmutableSet.h.

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

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

template<typename ImutInfo >

TreeTy* llvm::ImutAVLFactory< ImutInfo >::removeMinBinding	(	TreeTy *	T,
		TreeTy *&	Noderemoved
	)		[inline, protected]

Definition at line 587 of file ImmutableSet.h.

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

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

---

Friends And Related Function Documentation

template<typename ImutInfo >

friend class ImutAVLTree< ImutInfo > [friend]

Definition at line 365 of file ImmutableSet.h.

---

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

• ImmutableSet.h