gem5  v20.0.0.3
trie.test.cc
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 #include <gtest/gtest.h>
30 
31 #include <iostream>
32 #include <sstream>
33 #include <string>
34 
35 #include "base/trie.hh"
36 #include "base/types.hh"
37 
38 namespace {
39 
40 static inline uint32_t *ptr(uintptr_t val)
41 {
42  return (uint32_t *)val;
43 }
44 
45 } // anonymous namespace
46 
47 class TrieTestData : public testing::Test
48 {
49  protected:
50  typedef Trie<Addr, uint32_t> TrieType;
51  TrieType trie;
52 
53  std::string
54  dumpTrie()
55  {
56  std::stringstream ss;
57  trie.dump("test trie", ss);
58  return ss.str();
59  }
60 };
61 
62 TEST_F(TrieTestData, Empty)
63 {
64  EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
65 }
66 
67 TEST_F(TrieTestData, SingleEntry)
68 {
69  trie.insert(0x0123456789abcdef, 40, ptr(1));
70  EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
71  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(1)) << dumpTrie();
72 }
73 
74 TEST_F(TrieTestData, TwoOverlappingEntries)
75 {
76  trie.insert(0x0123456789abcdef, 40, ptr(1));
77  trie.insert(0x0123456789abcdef, 36, ptr(2));
78  EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie();
79  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie();
80 }
81 
82 TEST_F(TrieTestData, TwoOverlappingEntriesReversed)
83 {
84  trie.insert(0x0123456789abcdef, 36, ptr(2));
85  trie.insert(0x0123456789abcdef, 40, ptr(1));
86  EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie();
87  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie();
88 }
89 
90 TEST_F(TrieTestData, TwoIndependentEntries)
91 {
92  trie.insert(0x0123456789abcdef, 40, ptr(2));
93  trie.insert(0x0123456776543210, 40, ptr(1));
94  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(2)) << dumpTrie();
95  EXPECT_EQ(trie.lookup(0x0123456776000000), ptr(1)) << dumpTrie();
96  EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie();
97 }
98 
99 TEST_F(TrieTestData, TwoEntries)
100 {
101  trie.insert(0x0123456789000000, 40, ptr(4));
102  trie.insert(0x0123000000000000, 40, ptr(1));
103  trie.insert(0x0123456780000000, 40, ptr(3));
104  trie.insert(0x0123456700000000, 40, ptr(2));
105 
106  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
107  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie();
108  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
109  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
110 }
111 
112 TEST_F(TrieTestData, RemovingEntries)
113 {
114  TrieType::Handle node1, node2;
115  trie.insert(0x0123456789000000, 40, ptr(4));
116  trie.insert(0x0123000000000000, 40, ptr(1));
117  trie.insert(0x0123456780000000, 40, ptr(3));
118  node1 = trie.insert(0x0123456700000000, 40, ptr(2));
119  node2 = trie.insert(0x0123456700000000, 32, ptr(10));
120 
121  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
122  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(10)) << dumpTrie();
123  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(10)) << dumpTrie();
124  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(10)) << dumpTrie();
125 
126  trie.remove(node2);
127 
128  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
129  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie();
130  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
131  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
132 
133  trie.remove(node1);
134 
135  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
136  EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie();
137  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
138  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
139 }
Trie::insert
Handle insert(Key key, unsigned width, Value *val)
Method which inserts a key/value pair into the trie.
Definition: trie.hh:197
TEST_F
TEST_F(TrieTestData, Empty)
Definition: trie.test.cc:62
X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:769
Trie::lookup
Value * lookup(Key key)
Method which looks up the Value corresponding to a particular key.
Definition: trie.hh:283
TrieTestData::trie
TrieType trie
Definition: trie.test.cc:51
ArmISA::ss
Bitfield< 21 > ss
Definition: miscregs_types.hh:56
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:365
types.hh
Defines global host-dependent types: Counter, Tick, and (indirectly) {int,uint}{8,16,32,64}_t.
LaneSize::Empty
Trie::remove
Value * remove(Handle handle)
Method to delete a value from the trie.
Definition: trie.hh:298
EXPECT_EQ
#define EXPECT_EQ(lhs, rhs)
A macro which verifies that lhs and rhs are equal to each other.
Definition: unittest.hh:110
TrieTestData::dumpTrie
std::string dumpTrie()
Definition: trie.test.cc:54
TrieTestData::TrieType
Trie< Addr, uint32_t > TrieType
Definition: trie.test.cc:50
Generated on Fri Jul 3 2020 15:52:59 for gem5 by doxygen 1.8.13