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 gem5::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 54 of file trie.hh.

Member Function Documentation

◆ dump()

template<class Key , class Value >

void gem5::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 388 of file trie.hh.

References gem5::ccprintf(), gem5::Trie< Key, Value >::Node::dump(), gem5::Trie< Key, Value >::head, and gem5::X86ISA::os.

Referenced by TrieTestData::dumpTrie().

◆ extendMask()

template<class Key , class Value >

Key gem5::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 168 of file trie.hh.

References gem5::Trie< Key, Value >::MaxBits.

Referenced by gem5::Trie< Key, Value >::insert().

◆ goesAfter()

template<class Key , class Value >

bool gem5::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.