gem5  v21.2.1.1
trie.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012 Google
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met: redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer;
9  * redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution;
12  * neither the name of the copyright holders nor the names of its
13  * contributors may be used to endorse or promote products derived from
14  * this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 
29 #ifndef __BASE_TRIE_HH__
30 #define __BASE_TRIE_HH__
31 
32 #include <cassert>
33 #include <iostream>
34 #include <type_traits>
35 
36 #include "base/cprintf.hh"
37 #include "base/logging.hh"
38 #include "base/types.hh"
39 
40 namespace gem5
41 {
42 
53 template <class Key, class Value>
54 class Trie
55 {
56  protected:
57  static_assert(std::is_integral_v<Key>, "Key has to be an integral type");
58 
59  struct Node
60  {
61  Key key;
62  Key mask;
63 
64  bool
66  {
67  return (test & mask) == key;
68  }
69 
71 
73  Node *kids[2];
74 
75  Node(Key _key, Key _mask, Value *_val) :
76  key(_key & _mask), mask(_mask), value(_val),
77  parent(NULL)
78  {
79  kids[0] = NULL;
80  kids[1] = NULL;
81  }
82 
83  void
85  {
86  if (kids[1]) {
87  kids[1]->clear();
88  delete kids[1];
89  kids[1] = NULL;
90  }
91  if (kids[0]) {
92  kids[0]->clear();
93  delete kids[0];
94  kids[0] = NULL;
95  }
96  }
97 
98  void
99  dump(std::ostream &os, int level)
100  {
101  for (int i = 1; i < level; i++) {
102  ccprintf(os, "|");
103  }
104  if (level == 0)
105  ccprintf(os, "Root ");
106  else
107  ccprintf(os, "+ ");
108  ccprintf(os, "(%p, %p, %#X, %#X, %p)\n",
109  parent, this, key, mask, value);
110  if (kids[0])
111  kids[0]->dump(os, level + 1);
112  if (kids[1])
113  kids[1]->dump(os, level + 1);
114  }
115  };
116 
117  protected:
119 
120  public:
124  typedef Node *Handle;
125 
129  Trie() : head(0, 0, NULL)
130  {}
131 
135  static const unsigned MaxBits = sizeof(Key) * 8;
136 
137  private:
148  bool
149  goesAfter(Node **parent, Node *kid, Key key, Key new_mask)
150  {
151  if (kid && kid->matches(key) && (kid->mask & new_mask) == kid->mask) {
152  *parent = kid;
153  return true;
154  } else {
155  return false;
156  }
157  }
158 
167  Key
168  extendMask(Key orig)
169  {
170  // Just in case orig was 0.
171  const Key msb = 1ULL << (MaxBits - 1);
172  return orig | (orig >> 1) | msb;
173  }
174 
182  Handle
183  lookupHandle(Key key)
184  {
185  Node *node = &head;
186  while (node) {
187  if (node->value)
188  return node;
189 
190  if (node->kids[0] && node->kids[0]->matches(key))
191  node = node->kids[0];
192  else if (node->kids[1] && node->kids[1]->matches(key))
193  node = node->kids[1];
194  else
195  node = NULL;
196  }
197 
198  return NULL;
199  }
200 
201  public:
211  Handle
212  insert(Key key, unsigned width, Value *val)
213  {
214  // We use NULL value pointers to mark internal nodes of the trie, so
215  // we don't allow inserting them as real values.
216  assert(val);
217 
218  // Build a mask which masks off all the bits we don't care about.
219  Key new_mask = ~(Key)0;
220  if (width < MaxBits)
221  new_mask <<= (MaxBits - width);
222  // Use it to tidy up the key.
223  key &= new_mask;
224 
225  // Walk past all the nodes this new node will be inserted after. They
226  // can be ignored for the purposes of this function.
227  Node *node = &head;
228  while (goesAfter(&node, node->kids[0], key, new_mask) ||
229  goesAfter(&node, node->kids[1], key, new_mask))
230  {}
231  assert(node);
232 
233  Key cur_mask = node->mask;
234  // If we're already where the value needs to be...
235  if (cur_mask == new_mask) {
236  assert(!node->value);
237  node->value = val;
238  return node;
239  }
240 
241  for (unsigned int i = 0; i < 2; i++) {
242  Node *&kid = node->kids[i];
243  Node *new_node;
244  if (!kid) {
245  // No kid. Add a new one.
246  new_node = new Node(key, new_mask, val);
247  new_node->parent = node;
248  kid = new_node;
249  return new_node;
250  }
251 
252  // Walk down the leg until something doesn't match or we run out
253  // of bits.
254  Key last_mask;
255  bool done;
256  do {
257  last_mask = cur_mask;
258  cur_mask = extendMask(cur_mask);
259  done = ((key & cur_mask) != (kid->key & cur_mask)) ||
260  last_mask == new_mask;
261  } while (!done);
262  cur_mask = last_mask;
263 
264  // If this isn't the right leg to go down at all, skip it.
265  if (cur_mask == node->mask)
266  continue;
267 
268  // At the point we walked to above, add a new node.
269  new_node = new Node(key, cur_mask, NULL);
270  new_node->parent = node;
271  kid->parent = new_node;
272  new_node->kids[0] = kid;
273  kid = new_node;
274 
275  // If we ran out of bits, the value goes right here.
276  if (cur_mask == new_mask) {
277  new_node->value = val;
278  return new_node;
279  }
280 
281  // Still more bits to deal with, so add a new node for that path.
282  new_node = new Node(key, new_mask, val);
283  new_node->parent = kid;
284  kid->kids[1] = new_node;
285  return new_node;
286  }
287 
288  panic("Reached the end of the Trie insert function!\n");
289  return NULL;
290  }
291 
299  Value *
300  lookup(Key key)
301  {
302  Node *node = lookupHandle(key);
303  if (node)
304  return node->value;
305  else
306  return NULL;
307  }
308 
316  Value *
317  remove(Handle handle)
318  {
319  Node *node = handle;
320  Value *val = node->value;
321  if (node->kids[1]) {
322  assert(node->value);
323  node->value = NULL;
324  return val;
325  }
326  if (!node->parent)
327  panic("Trie: Can't remove root node.\n");
328 
329  Node *parent = node->parent;
330 
331  // If there's a kid, fix up it's parent pointer.
332  if (node->kids[0])
333  node->kids[0]->parent = parent;
334  // Figure out which kid we are, and update our parent's pointers.
335  if (parent->kids[0] == node)
336  parent->kids[0] = node->kids[0];
337  else if (parent->kids[1] == node)
338  parent->kids[1] = node->kids[0];
339  else
340  panic("Trie: Inconsistent parent/kid relationship.\n");
341  // Make sure if the parent only has one kid, it's kid[0].
342  if (parent->kids[1] && !parent->kids[0]) {
343  parent->kids[0] = parent->kids[1];
344  parent->kids[1] = NULL;
345  }
346 
347  // If the parent has less than two kids and no cargo and isn't the
348  // root, delete it too.
349  if (!parent->kids[1] && !parent->value && parent->parent)
350  remove(parent);
351  delete node;
352  return val;
353  }
354 
362  Value *
363  remove(Key key)
364  {
365  Handle handle = lookupHandle(key);
366  if (!handle)
367  return NULL;
368  return remove(handle);
369  }
370 
377  void
379  {
380  head.clear();
381  }
382 
387  void
388  dump(const char *title, std::ostream &os=std::cout)
389  {
390  ccprintf(os, "**************************************************\n");
391  ccprintf(os, "*** Start of Trie: %s\n", title);
392  ccprintf(os, "*** (parent, me, key, mask, value pointer)\n");
393  ccprintf(os, "**************************************************\n");
394  head.dump(os, 0);
395  }
396 };
397 
398 } // namespace gem5
399 
400 #endif
gem5::X86ISA::level
Bitfield< 20 > level
Definition: intmessage.hh:51
gem5::Trie::Node::kids
Node * kids[2]
Definition: trie.hh:73
gem5::Trie::Trie
Trie()
Definition: trie.hh:129
gem5::Trie::Node::Node
Node(Key _key, Key _mask, Value *_val)
Definition: trie.hh:75
gem5::Trie::Node::matches
bool matches(Key test)
Definition: trie.hh:65
test
Definition: test.h:38
gem5::Trie::Node::mask
Key mask
Definition: trie.hh:62
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:775
gem5::Trie::lookup
Value * lookup(Key key)
Method which looks up the Value corresponding to a particular key.
Definition: trie.hh:300
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:67
gem5::ccprintf
void ccprintf(cp::Print &print)
Definition: cprintf.hh:130
gem5::Trie::dump
void dump(const char *title, std::ostream &os=std::cout)
A debugging method which prints the contents of this trie.
Definition: trie.hh:388
gem5::Trie::head
Node head
Definition: trie.hh:118
gem5::Trie
A trie is a tree-based data structure used for data retrieval.
Definition: trie.hh:54
gem5::Trie::Node::dump
void dump(std::ostream &os, int level)
Definition: trie.hh:99
gem5::statistics::Node
Base class for formula statistic node.
Definition: statistics.hh:1523
gem5::Trie::remove
Value * remove(Handle handle)
Method to delete a value from the trie.
Definition: trie.hh:317
gem5::Trie::lookupHandle
Handle lookupHandle(Key key)
Method which looks up the Handle corresponding to a particular key.
Definition: trie.hh:183
gem5::ArmISA::width
Bitfield< 4 > width
Definition: misc_types.hh:72
gem5::Trie::Handle
Node * Handle
Definition: trie.hh:124
cprintf.hh
gem5::Trie::goesAfter
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.
Definition: trie.hh:149
gem5::Trie::MaxBits
static const unsigned MaxBits
Definition: trie.hh:135
gem5::Trie::remove
Value * remove(Key key)
Method to lookup a value from the trie and then delete it.
Definition: trie.hh:363
types.hh
gem5::X86ISA::os
Bitfield< 17 > os
Definition: misc.hh:809
gem5::statistics::Value
Definition: statistics.hh:1982
gem5::Trie::Node::parent
Node * parent
Definition: trie.hh:72
logging.hh
gem5::Trie::insert
Handle insert(Key key, unsigned width, Value *val)
Method which inserts a key/value pair into the trie.
Definition: trie.hh:212
gem5::Trie::Node::clear
void clear()
Definition: trie.hh:84
gem5::Trie::clear
void clear()
A method which removes all key/value pairs from the trie.
Definition: trie.hh:378
gem5::Trie::Node::key
Key key
Definition: trie.hh:61
gem5::Trie::Node
Definition: trie.hh:59
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: tlb.cc:60
gem5::Trie::extendMask
Key extendMask(Key orig)
A utility method which extends a mask value one more bit towards the lsb.
Definition: trie.hh:168
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:178
gem5::Trie::Node::value
Value * value
Definition: trie.hh:70

Generated on Wed May 4 2022 12:13:52 for gem5 by doxygen 1.8.17