gem5  v20.1.0.0
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 
50 template <class Key, class Value>
51 class Trie
52 {
53  protected:
54  static_assert(std::is_integral<Key>::value,
55  "Key has to be an integral type");
56 
57  struct Node
58  {
59  Key key;
60  Key mask;
61 
62  bool
64  {
65  return (test & mask) == key;
66  }
67 
68  Value *value;
69 
71  Node *kids[2];
72 
73  Node(Key _key, Key _mask, Value *_val) :
74  key(_key & _mask), mask(_mask), value(_val),
75  parent(NULL)
76  {
77  kids[0] = NULL;
78  kids[1] = NULL;
79  }
80 
81  void
83  {
84  if (kids[1]) {
85  kids[1]->clear();
86  delete kids[1];
87  kids[1] = NULL;
88  }
89  if (kids[0]) {
90  kids[0]->clear();
91  delete kids[0];
92  kids[0] = NULL;
93  }
94  }
95 
96  void
97  dump(std::ostream &os, int level)
98  {
99  for (int i = 1; i < level; i++) {
100  ccprintf(os, "|");
101  }
102  if (level == 0)
103  ccprintf(os, "Root ");
104  else
105  ccprintf(os, "+ ");
106  ccprintf(os, "(%p, %p, %#X, %#X, %p)\n",
107  parent, this, key, mask, value);
108  if (kids[0])
109  kids[0]->dump(os, level + 1);
110  if (kids[1])
111  kids[1]->dump(os, level + 1);
112  }
113  };
114 
115  protected:
116  Node head;
117 
118  public:
122  typedef Node *Handle;
123 
127  Trie() : head(0, 0, NULL)
128  {}
129 
133  static const unsigned MaxBits = sizeof(Key) * 8;
134 
135  private:
146  bool
147  goesAfter(Node **parent, Node *kid, Key key, Key new_mask)
148  {
149  if (kid && kid->matches(key) && (kid->mask & new_mask) == kid->mask) {
150  *parent = kid;
151  return true;
152  } else {
153  return false;
154  }
155  }
156 
165  Key
166  extendMask(Key orig)
167  {
168  // Just in case orig was 0.
169  const Key msb = ULL(1) << (MaxBits - 1);
170  return orig | (orig >> 1) | msb;
171  }
172 
180  Handle
181  lookupHandle(Key key)
182  {
183  Node *node = &head;
184  while (node) {
185  if (node->value)
186  return node;
187 
188  if (node->kids[0] && node->kids[0]->matches(key))
189  node = node->kids[0];
190  else if (node->kids[1] && node->kids[1]->matches(key))
191  node = node->kids[1];
192  else
193  node = NULL;
194  }
195 
196  return NULL;
197  }
198 
199  public:
209  Handle
210  insert(Key key, unsigned width, Value *val)
211  {
212  // We use NULL value pointers to mark internal nodes of the trie, so
213  // we don't allow inserting them as real values.
214  assert(val);
215 
216  // Build a mask which masks off all the bits we don't care about.
217  Key new_mask = ~(Key)0;
218  if (width < MaxBits)
219  new_mask <<= (MaxBits - width);
220  // Use it to tidy up the key.
221  key &= new_mask;
222 
223  // Walk past all the nodes this new node will be inserted after. They
224  // can be ignored for the purposes of this function.
225  Node *node = &head;
226  while (goesAfter(&node, node->kids[0], key, new_mask) ||
227  goesAfter(&node, node->kids[1], key, new_mask))
228  {}
229  assert(node);
230 
231  Key cur_mask = node->mask;
232  // If we're already where the value needs to be...
233  if (cur_mask == new_mask) {
234  assert(!node->value);
235  node->value = val;
236  return node;
237  }
238 
239  for (unsigned int i = 0; i < 2; i++) {
240  Node *&kid = node->kids[i];
241  Node *new_node;
242  if (!kid) {
243  // No kid. Add a new one.
244  new_node = new Node(key, new_mask, val);
245  new_node->parent = node;
246  kid = new_node;
247  return new_node;
248  }
249 
250  // Walk down the leg until something doesn't match or we run out
251  // of bits.
252  Key last_mask;
253  bool done;
254  do {
255  last_mask = cur_mask;
256  cur_mask = extendMask(cur_mask);
257  done = ((key & cur_mask) != (kid->key & cur_mask)) ||
258  last_mask == new_mask;
259  } while (!done);
260  cur_mask = last_mask;
261 
262  // If this isn't the right leg to go down at all, skip it.
263  if (cur_mask == node->mask)
264  continue;
265 
266  // At the point we walked to above, add a new node.
267  new_node = new Node(key, cur_mask, NULL);
268  new_node->parent = node;
269  kid->parent = new_node;
270  new_node->kids[0] = kid;
271  kid = new_node;
272 
273  // If we ran out of bits, the value goes right here.
274  if (cur_mask == new_mask) {
275  new_node->value = val;
276  return new_node;
277  }
278 
279  // Still more bits to deal with, so add a new node for that path.
280  new_node = new Node(key, new_mask, val);
281  new_node->parent = kid;
282  kid->kids[1] = new_node;
283  return new_node;
284  }
285 
286  panic("Reached the end of the Trie insert function!\n");
287  return NULL;
288  }
289 
297  Value *
298  lookup(Key key)
299  {
300  Node *node = lookupHandle(key);
301  if (node)
302  return node->value;
303  else
304  return NULL;
305  }
306 
314  Value *
315  remove(Handle handle)
316  {
317  Node *node = handle;
318  Value *val = node->value;
319  if (node->kids[1]) {
320  assert(node->value);
321  node->value = NULL;
322  return val;
323  }
324  if (!node->parent)
325  panic("Trie: Can't remove root node.\n");
326 
327  Node *parent = node->parent;
328 
329  // If there's a kid, fix up it's parent pointer.
330  if (node->kids[0])
331  node->kids[0]->parent = parent;
332  // Figure out which kid we are, and update our parent's pointers.
333  if (parent->kids[0] == node)
334  parent->kids[0] = node->kids[0];
335  else if (parent->kids[1] == node)
336  parent->kids[1] = node->kids[0];
337  else
338  panic("Trie: Inconsistent parent/kid relationship.\n");
339  // Make sure if the parent only has one kid, it's kid[0].
340  if (parent->kids[1] && !parent->kids[0]) {
341  parent->kids[0] = parent->kids[1];
342  parent->kids[1] = NULL;
343  }
344 
345  // If the parent has less than two kids and no cargo and isn't the
346  // root, delete it too.
347  if (!parent->kids[1] && !parent->value && parent->parent)
348  remove(parent);
349  delete node;
350  return val;
351  }
352 
360  Value *
361  remove(Key key)
362  {
363  Handle handle = lookupHandle(key);
364  if (!handle)
365  return NULL;
366  return remove(handle);
367  }
368 
375  void
377  {
378  head.clear();
379  }
380 
385  void
386  dump(const char *title, std::ostream &os=std::cout)
387  {
388  ccprintf(os, "**************************************************\n");
389  ccprintf(os, "*** Start of Trie: %s\n", title);
390  ccprintf(os, "*** (parent, me, key, mask, value pointer)\n");
391  ccprintf(os, "**************************************************\n");
392  head.dump(os, 0);
393  }
394 };
395 
396 #endif
Trie::remove
Value * remove(Key key)
Method to lookup a value from the trie and then delete it.
Definition: trie.hh:361
X86ISA::os
Bitfield< 17 > os
Definition: misc.hh:803
Trie::Node::clear
void clear()
Definition: trie.hh:82
Trie::Node::parent
Node * parent
Definition: trie.hh:70
ArmISA::i
Bitfield< 7 > i
Definition: miscregs_types.hh:63
test
Definition: test.h:38
Trie::Handle
Node * Handle
Definition: trie.hh:122
Trie::remove
Value * remove(Handle handle)
Method to delete a value from the trie.
Definition: trie.hh:315
ArmISA::width
Bitfield< 4 > width
Definition: miscregs_types.hh:68
Trie::insert
Handle insert(Key key, unsigned width, Value *val)
Method which inserts a key/value pair into the trie.
Definition: trie.hh:210
Trie
A trie is a tree-based data structure used for data retrieval.
Definition: trie.hh:51
Trie::lookup
Value * lookup(Key key)
Method which looks up the Value corresponding to a particular key.
Definition: trie.hh:298
Trie::Node::key
Key key
Definition: trie.hh:59
Trie::head
Node head
Definition: trie.hh:116
Trie::Node
Definition: trie.hh:57
Trie::extendMask
Key extendMask(Key orig)
A utility method which extends a mask value one more bit towards the lsb.
Definition: trie.hh:166
Trie::MaxBits
static const unsigned MaxBits
Definition: trie.hh:133
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:386
Trie::Trie
Trie()
Definition: trie.hh:127
Trie::Node::kids
Node * kids[2]
Definition: trie.hh:71
cprintf.hh
Trie::Node::mask
Key mask
Definition: trie.hh:60
Trie::Node::dump
void dump(std::ostream &os, int level)
Definition: trie.hh:97
X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:769
Trie::Node::matches
bool matches(Key test)
Definition: trie.hh:63
X86ISA::level
Bitfield< 20 > level
Definition: intmessage.hh:47
Trie::lookupHandle
Handle lookupHandle(Key key)
Method which looks up the Handle corresponding to a particular key.
Definition: trie.hh:181
types.hh
ccprintf
void ccprintf(cp::Print &print)
Definition: cprintf.hh:127
logging.hh
Trie::Node::Node
Node(Key _key, Key _mask, Value *_val)
Definition: trie.hh:73
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:147
Trie::Node::value
Value * value
Definition: trie.hh:68
ULL
#define ULL(N)
uint64_t constant
Definition: types.hh:50
Trie::clear
void clear()
A method which removes all key/value pairs from the trie.
Definition: trie.hh:376
panic
#define panic(...)
This implements a cprintf based panic() function.
Definition: logging.hh:171

Generated on Wed Sep 30 2020 14:02:08 for gem5 by doxygen 1.8.17