Trie< Key, Value > Class Template Reference

A trie is a tree-based data structure used for data retrieval. More...

#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 >

A trie is a tree-based data structure used for data retrieval.

It uses bits masked from the msb of the key to to determine a value's location, so its lookups have their worst case time dictated by the key's size.

Template Parameters

Key	Type of the key of the tree nodes. Must be an integral type.
Value	Type of the values associated to the keys.

Definition at line 49 of file trie.hh.

Member Typedef Documentation

Handle

template<class Key, class Value>

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

Definition at line 117 of file trie.hh.

Constructor & Destructor Documentation

Trie()

template<class Key, class Value>

Trie< Key, Value >::Trie ( )

inline

Definition at line 119 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 355 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 365 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 155 of file trie.hh.

Referenced by Trie< Addr, TlbEntry >::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 136 of file trie.hh.

Referenced by Trie< Addr, TlbEntry >::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 197 of file trie.hh.

Referenced by RiscvISA::TLB::insert(), X86ISA::TLB::insert(), TEST_F(), RiscvISA::TLB::unserialize(), 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 283 of file trie.hh.

Referenced by X86ISA::TLB::demapPage(), X86ISA::TLB::insert(), X86ISA::TLB::lookup(), RiscvISA::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 170 of file trie.hh.

Referenced by Trie< Addr, TlbEntry >::lookup(), and Trie< Addr, TlbEntry >::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 298 of file trie.hh.

Referenced by X86ISA::TLB::demapPage(), X86ISA::TLB::evictLRU(), X86ISA::TLB::flushAll(), X86ISA::TLB::flushNonGlobal(), RiscvISA::TLB::remove(), 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 342 of file trie.hh.

Member Data Documentation

head

template<class Key, class Value>

Node Trie< Key, Value >::head

protected

Definition at line 114 of file trie.hh.

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

MaxBits

template<class Key, class Value>

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

static

Definition at line 122 of file trie.hh.

---

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

• base/trie.hh