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 51 of file trie.hh.

Member Function Documentation

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 386 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 166 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 147 of file trie.hh.

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

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 181 of file trie.hh.

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

Member Data Documentation

head

template<class Key , class Value >

Node Trie< Key, Value >::head

protected

Definition at line 116 of file trie.hh.

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

---

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

• base/trie.hh