Trie< Key, Value > Class Template Reference

#include <trie.hh>

Classes
struct	Node

Public Types
typedef Node *	Handle

Public Member Functions
	Trie ()
Handle	insert (Key key, unsigned width, Value *val)
	Method which inserts a key/value pair into the trie. More...
Value *	lookup (Key key)
	Method which looks up the Value corresponding to a particular key. More...
Value *	remove (Handle handle)
	Method to delete a value from the trie. More...
Value *	remove (Key key)
	Method to lookup a value from the trie and then delete it. More...
void	clear ()
	A method which removes all key/value pairs from the trie. More...
void	dump (const char *title, std::ostream &os=std::cout)
	A debugging method which prints the contents of this trie. More...

Static Public Attributes
static const unsigned	MaxBits = sizeof(Key) * 8

Protected Attributes
Node	head

Private Member Functions
bool	goesAfter (Node **parent, Node *kid, Key key, Key new_mask)
	A utility method which checks whether the key being looked up lies beyond the Node being examined. More...
Key	extendMask (Key orig)
	A utility method which extends a mask value one more bit towards the lsb. More...
Handle	lookupHandle (Key key)
	Method which looks up the Handle corresponding to a particular key. More...

Detailed Description

template<class Key, class Value>
class Trie< Key, Value >

Definition at line 43 of file trie.hh.

Member Typedef Documentation

Handle

template<class Key, class Value>

typedef Node* Trie< Key, Value >::Handle

Definition at line 108 of file trie.hh.

Constructor & Destructor Documentation

Trie()

template<class Key, class Value>

Trie< Key, Value >::Trie ( )

inline

Definition at line 110 of file trie.hh.

Member Function Documentation

clear()

template<class Key, class Value>

void Trie< Key, Value >::clear ( )

inline

A method which removes all key/value pairs from the trie.

This is more efficient than trying to remove elements individually.

Definition at line 346 of file trie.hh.

dump()

template<class Key, class Value>

void Trie< Key, Value >::dump ( const char *  title, std::ostream &  os = std::cout  )

inline

A debugging method which prints the contents of this trie.

Parameters

title

An identifying title to put in the dump header.

Definition at line 356 of file trie.hh.

Referenced by TrieTestData::dumpTrie().

extendMask()

template<class Key, class Value>

Key Trie< Key, Value >::extendMask ( Key  orig )

inlineprivate

A utility method which extends a mask value one more bit towards the lsb.

This is almost just a signed right shift, except that the shifted in bits are technically undefined. This is also slightly complicated by the zero case.

Parameters

orig	The original mask to extend.

Returns

The extended mask.

Definition at line 146 of file trie.hh.

Referenced by Trie< Addr, uint32_t >::insert().

goesAfter()

template<class Key, class Value>

bool Trie< Key, Value >::goesAfter ( Node **  parent, Node *  kid, Key  key, Key  new_mask  )

inlineprivate

A utility method which checks whether the key being looked up lies beyond the Node being examined.

If so, it returns true and advances the node being examined.

Parameters

parent	The node we're currently "at", which can be updated.
kid	The node we may want to move to.
key	The key we're looking for.
new_mask	The mask to use when matching against the key.

Returns

Whether the current Node was advanced.

Definition at line 127 of file trie.hh.

Referenced by Trie< Addr, uint32_t >::insert().

insert()

template<class Key, class Value>

Handle Trie< Key, Value >::insert ( Key  key, unsigned  width, Value *  val  )

inline

Method which inserts a key/value pair into the trie.

Parameters

key	The key which can later be used to look up this value.
width	How many bits of the key (from msb) should be used.
val	A pointer to the value to store in the trie.

Returns

A Handle corresponding to this value.

Definition at line 188 of file trie.hh.

Referenced by X86ISA::TLB::insert(), TEST_F(), and X86ISA::TLB::unserialize().

lookup()

template<class Key, class Value>

Value* Trie< Key, Value >::lookup ( Key  key )

inline

Method which looks up the Value corresponding to a particular key.

Parameters

key	The key to look up.

Returns

The first Value matching this key, or NULL if none was found.

Definition at line 274 of file trie.hh.

Referenced by X86ISA::TLB::demapPage(), X86ISA::TLB::insert(), X86ISA::TLB::lookup(), and TEST_F().

lookupHandle()

template<class Key, class Value>

Handle Trie< Key, Value >::lookupHandle ( Key  key )

inlineprivate

Method which looks up the Handle corresponding to a particular key.

This is useful if you want to delete the Handle corresponding to a key since the "remove" function takes a Handle as its argument.

Parameters

key	The key to look up.

Returns

The first Handle matching this key, or NULL if none was found.

Definition at line 161 of file trie.hh.

Referenced by Trie< Addr, uint32_t >::lookup(), and Trie< Addr, uint32_t >::remove().

remove() [1/2]

template<class Key, class Value>

Value* Trie< Key, Value >::remove ( Handle  handle )

inline

Method to delete a value from the trie.

Parameters

node	A Handle to remove.

Returns

The Value pointer from the removed entry.

Definition at line 289 of file trie.hh.

Referenced by X86ISA::TLB::demapPage(), X86ISA::TLB::evictLRU(), X86ISA::TLB::flushAll(), X86ISA::TLB::flushNonGlobal(), and TEST_F().

remove() [2/2]

template<class Key, class Value>

Value* Trie< Key, Value >::remove ( Key  key )

inline

Method to lookup a value from the trie and then delete it.

Parameters

key	The key to look up and then remove.

Returns

The Value pointer from the removed entry, if any.

Definition at line 333 of file trie.hh.

Member Data Documentation

head

template<class Key, class Value>

Node Trie< Key, Value >::head

protected

Definition at line 105 of file trie.hh.

Referenced by Trie< Addr, uint32_t >::insert(), and Trie< Addr, uint32_t >::lookupHandle().

MaxBits

template<class Key, class Value>

const unsigned Trie< Key, Value >::MaxBits = sizeof(Key) * 8

static

Definition at line 113 of file trie.hh.

---

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

• base/trie.hh