gem5  v21.1.0.2
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<Key>::value,
58  "Key has to be an integral type");
59 
60  struct Node
61  {
62  Key key;
63  Key mask;
64 
65  bool
67  {
68  return (test & mask) == key;
69  }
70 
72 
74  Node *kids[2];
75 
76  Node(Key _key, Key _mask, Value *_val) :
77  key(_key & _mask), mask(_mask), value(_val),
78  parent(NULL)
79  {
80  kids[0] = NULL;
81  kids[1] = NULL;
82  }
83 
84  void
86  {
87  if (kids[1]) {
88  kids[1]->clear();
89  delete kids[1];
90  kids[1] = NULL;
91  }
92  if (kids[0]) {
93  kids[0]->clear();
94  delete kids[0];
95  kids[0] = NULL;
96  }
97  }
98 
99  void
100  dump(std::ostream &os, int level)
101  {
102  for (int i = 1; i < level; i++) {
103  ccprintf(os, "|");
104  }
105  if (level == 0)
106  ccprintf(os, "Root ");
107  else
108  ccprintf(os, "+ ");
109  ccprintf(os, "(%p, %p, %#X, %#X, %p)\n",
110  parent, this, key, mask, value);
111  if (kids[0])
112  kids[0]->dump(os, level + 1);
113  if (kids[1])
114  kids[1]->dump(os, level + 1);
115  }
116  };
117 
118  protected:
120 
121  public:
125  typedef Node *Handle;
126 
130  Trie() : head(0, 0, NULL)
131  {}
132 
136  static const unsigned MaxBits = sizeof(Key) * 8;
137 
138  private:
149  bool
150  goesAfter(Node **parent, Node *kid, Key key, Key new_mask)
151  {
152  if (kid && kid->matches(key) && (kid->mask & new_mask) == kid->mask) {
153  *parent = kid;
154  return true;
155  } else {
156  return false;
157  }
158  }
159 
168  Key
169  extendMask(Key orig)
170  {
171  // Just in case orig was 0.
172  const Key msb = 1ULL << (MaxBits - 1);
173  return orig | (orig >> 1) | msb;
174  }
175 
183  Handle
184  lookupHandle(Key key)
185  {
186  Node *node = &head;
187  while (node) {
188  if (node->value)
189  return node;
190 
191  if (node->kids[0] && node->kids[0]->matches(key))
192  node = node->kids[0];
193  else if (node->kids[1] && node->kids[1]->matches(key))
194  node = node->kids[1];
195  else
196  node = NULL;
197  }
198 
199  return NULL;
200  }
201 
202  public:
212  Handle
213  insert(Key key, unsigned width, Value *val)
214  {
215  // We use NULL value pointers to mark internal nodes of the trie, so
216  // we don't allow inserting them as real values.
217  assert(val);
218 
219  // Build a mask which masks off all the bits we don't care about.
220  Key new_mask = ~(Key)0;
221  if (width < MaxBits)
222  new_mask <<= (MaxBits - width);
223  // Use it to tidy up the key.
224  key &= new_mask;
225 
226  // Walk past all the nodes this new node will be inserted after. They
227  // can be ignored for the purposes of this function.
228  Node *node = &head;
229  while (goesAfter(&node, node->kids[0], key, new_mask) ||
230  goesAfter(&node, node->kids[1], key, new_mask))
231  {}
232  assert(node);
233 
234  Key cur_mask = node->mask;
235  // If we're already where the value needs to be...
236  if (cur_mask == new_mask) {
237  assert(!node->value);
238  node->value = val;
239  return node;
240  }
241 
242  for (unsigned int i = 0; i < 2; i++) {
243  Node *&kid = node->kids[i];
244  Node *new_node;
245  if (!kid) {
246  // No kid. Add a new one.
247  new_node = new Node(key, new_mask, val);
248  new_node->parent = node;
249  kid = new_node;
250  return new_node;
251  }
252 
253  // Walk down the leg until something doesn't match or we run out
254  // of bits.
255  Key last_mask;
256  bool done;
257  do {
258  last_mask = cur_mask;
259  cur_mask = extendMask(cur_mask);
260  done = ((key & cur_mask) != (kid->key & cur_mask)) ||
261  last_mask == new_mask;
262  } while (!done);
263  cur_mask = last_mask;
264 
265  // If this isn't the right leg to go down at all, skip it.
266  if (cur_mask == node->mask)
267  continue;
268 
269  // At the point we walked to above, add a new node.
270  new_node = new Node(key, cur_mask, NULL);
271  new_node->parent = node;
272  kid->parent = new_node;
273  new_node->kids[0] = kid;
274  kid = new_node;
275 
276  // If we ran out of bits, the value goes right here.
277  if (cur_mask == new_mask) {
278  new_node->value = val;
279  return new_node;
280  }
281 
282  // Still more bits to deal with, so add a new node for that path.
283  new_node = new Node(key, new_mask, val);
284  new_node->parent = kid;
285  kid->kids[1] = new_node;
286  return new_node;
287  }
288 
289  panic("Reached the end of the Trie insert function!\n");
290  return NULL;
291  }
292 
300  Value *
301  lookup(Key key)
302  {
303  Node *node = lookupHandle(key);
304  if (node)
305  return node->value;
306  else
307  return NULL;
308  }
309 
317  Value *
318  remove(Handle handle)
319  {
320  Node *node = handle;
321  Value *val = node->value;
322  if (node->kids[1]) {
323  assert(node->value);
324  node->value = NULL;
325  return val;
326  }
327  if (!node->parent)
328  panic("Trie: Can't remove root node.\n");
329 
330  Node *parent = node->parent;
331 
332  // If there's a kid, fix up it's parent pointer.
333  if (node->kids[0])
334  node->kids[0]->parent = parent;
335  // Figure out which kid we are, and update our parent's pointers.
336  if (parent->kids[0] == node)
337  parent->kids[0] = node->kids[0];
338  else if (parent->kids[1] == node)
339  parent->kids[1] = node->kids[0];
340  else
341  panic("Trie: Inconsistent parent/kid relationship.\n");
342  // Make sure if the parent only has one kid, it's kid[0].
343  if (parent->kids[1] && !parent->kids[0]) {
344  parent->kids[0] = parent->kids[1];
345  parent->kids[1] = NULL;
346  }
347 
348  // If the parent has less than two kids and no cargo and isn't the
349  // root, delete it too.
350  if (!parent->kids[1] && !parent->value && parent->parent)
351  remove(parent);
352  delete node;
353  return val;
354  }
355 
363  Value *
364  remove(Key key)
365  {
366  Handle handle = lookupHandle(key);
367  if (!handle)
368  return NULL;
369  return remove(handle);
370  }
371 
378  void
380  {
381  head.clear();
382  }
383 
388  void
389  dump(const char *title, std::ostream &os=std::cout)
390  {
391  ccprintf(os, "**************************************************\n");
392  ccprintf(os, "*** Start of Trie: %s\n", title);
393  ccprintf(os, "*** (parent, me, key, mask, value pointer)\n");
394  ccprintf(os, "**************************************************\n");
395  head.dump(os, 0);
396  }
397 };
398 
399 } // namespace gem5
400 
401 #endif
gem5::X86ISA::level
Bitfield< 20 > level
Definition: intmessage.hh:51
gem5::Trie::Node::kids
Node * kids[2]
Definition: trie.hh:74
gem5::Trie::Trie
Trie()
Definition: trie.hh:130
gem5::Trie::Node::Node
Node(Key _key, Key _mask, Value *_val)
Definition: trie.hh:76
gem5::Trie::Node::matches
bool matches(Key test)
Definition: trie.hh:66
test
Definition: test.h:38
gem5::Trie::Node::mask
Key mask
Definition: trie.hh:63
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:301
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
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:389
gem5::Trie::head
Node head
Definition: trie.hh:119
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:100
gem5::statistics::Node
Base class for formula statistic node.
Definition: statistics.hh:1520
gem5::Trie::remove
Value * remove(Handle handle)
Method to delete a value from the trie.
Definition: trie.hh:318
gem5::Trie::lookupHandle
Handle lookupHandle(Key key)
Method which looks up the Handle corresponding to a particular key.
Definition: trie.hh:184
gem5::ArmISA::width
Bitfield< 4 > width
Definition: misc_types.hh:71
gem5::Trie::Handle
Node * Handle
Definition: trie.hh:125
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:150
gem5::Trie::MaxBits
static const unsigned MaxBits
Definition: trie.hh:136
gem5::Trie::remove
Value * remove(Key key)
Method to lookup a value from the trie and then delete it.
Definition: trie.hh:364
types.hh
gem5::X86ISA::os
Bitfield< 17 > os
Definition: misc.hh:809
gem5::statistics::Value
Definition: statistics.hh:1979
gem5::Trie::Node::parent
Node * parent
Definition: trie.hh:73
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:213
gem5::Trie::Node::clear
void clear()
Definition: trie.hh:85
gem5::Trie::clear
void clear()
A method which removes all key/value pairs from the trie.
Definition: trie.hh:379
gem5::Trie::Node::key
Key key
Definition: trie.hh:62
gem5::Trie::Node
Definition: trie.hh:60
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::Trie::extendMask
Key extendMask(Key orig)
A utility method which extends a mask value one more bit towards the lsb.
Definition: trie.hh:169
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:177
gem5::Trie::Node::value
Value * value
Definition: trie.hh:71

Generated on Tue Sep 21 2021 12:25:00 for gem5 by doxygen 1.8.17