gem5  v21.1.0.2
Classes | Public Types | Public Member Functions | Static Public Attributes | Protected Attributes | Private Member Functions | List of all members
gem5::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 NodeHandle
 

Public Member Functions

 Trie ()
 
Handle insert (Key key, unsigned width, Value *val)
 Method which inserts a key/value pair into the trie. More...
 
Valuelookup (Key key)
 Method which looks up the Value corresponding to a particular key. More...
 
Valueremove (Handle handle)
 Method to delete a value from the trie. More...
 
Valueremove (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
KeyType of the key of the tree nodes. Must be an integral type.
ValueType 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
titleAn identifying title to put in the dump header.

Definition at line 389 of file trie.hh.

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
origThe original mask to extend.
Returns
The extended mask.

Definition at line 169 of file trie.hh.

Referenced by gem5::Trie< Addr, TlbEntry >::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
parentThe node we're currently "at", which can be updated.
kidThe node we may want to move to.
keyThe key we're looking for.
new_maskThe mask to use when matching against the key.
Returns
Whether the current Node was advanced.

Definition at line 150 of file trie.hh.

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

◆ lookupHandle()

template<class Key , class Value >
Handle gem5::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
keyThe key to look up.
Returns
The first Handle matching this key, or NULL if none was found.

Definition at line 184 of file trie.hh.

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

Member Data Documentation

◆ head

template<class Key , class Value >
Node gem5::Trie< Key, Value >::head
protected

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

Generated on Tue Sep 21 2021 12:28:19 for gem5 by doxygen 1.8.17