gem5  v21.1.0.2
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 using namespace gem5;
39 
40 namespace {
41 
42 static inline uint32_t *ptr(uintptr_t val)
43 {
44  return (uint32_t *)val;
45 }
46 
47 } // anonymous namespace
48 
49 class TrieTestData : public testing::Test
50 {
51  protected:
54 
55  std::string
57  {
58  std::stringstream ss;
59  trie.dump("test trie", ss);
60  return ss.str();
61  }
62 };
63 
65 {
66  EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
67 }
68 
69 TEST_F(TrieTestData, SingleEntry)
70 {
71  trie.insert(0x0123456789abcdef, 40, ptr(1));
72  EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
73  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(1)) << dumpTrie();
74 }
75 
76 TEST_F(TrieTestData, TwoOverlappingEntries)
77 {
78  trie.insert(0x0123456789abcdef, 40, ptr(1));
79  trie.insert(0x0123456789abcdef, 36, ptr(2));
80  EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie();
81  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie();
82 }
83 
84 TEST_F(TrieTestData, TwoOverlappingEntriesReversed)
85 {
86  trie.insert(0x0123456789abcdef, 36, ptr(2));
87  trie.insert(0x0123456789abcdef, 40, ptr(1));
88  EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie();
89  EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie();
90 }
91 
92 TEST_F(TrieTestData, TwoIndependentEntries)
93 {
94  trie.insert(0x0123456789abcdef, 40, ptr(2));
95  trie.insert(0x0123456776543210, 40, ptr(1));
96  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(2)) << dumpTrie();
97  EXPECT_EQ(trie.lookup(0x0123456776000000), ptr(1)) << dumpTrie();
98  EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie();
99 }
100 
101 TEST_F(TrieTestData, TwoEntries)
102 {
103  trie.insert(0x0123456789000000, 40, ptr(4));
104  trie.insert(0x0123000000000000, 40, ptr(1));
105  trie.insert(0x0123456780000000, 40, ptr(3));
106  trie.insert(0x0123456700000000, 40, ptr(2));
107 
108  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
109  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie();
110  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
111  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
112 }
113 
114 TEST_F(TrieTestData, RemovingEntries)
115 {
116  TrieType::Handle node1, node2;
117  trie.insert(0x0123456789000000, 40, ptr(4));
118  trie.insert(0x0123000000000000, 40, ptr(1));
119  trie.insert(0x0123456780000000, 40, ptr(3));
120  node1 = trie.insert(0x0123456700000000, 40, ptr(2));
121  node2 = trie.insert(0x0123456700000000, 32, ptr(10));
122 
123  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
124  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(10)) << dumpTrie();
125  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(10)) << dumpTrie();
126  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(10)) << dumpTrie();
127 
128  trie.remove(node2);
129 
130  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
131  EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie();
132  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
133  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
134 
135  trie.remove(node1);
136 
137  EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie();
138  EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie();
139  EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie();
140  EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie();
141 }
TrieTestData::trie
TrieType trie
Definition: trie.test.cc:53
TEST_F
TEST_F(TrieTestData, Empty)
Definition: trie.test.cc:64
gem5::X86ISA::val
Bitfield< 63 > val
Definition: misc.hh:775
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< Addr, uint32_t >
TrieTestData::dumpTrie
std::string dumpTrie()
Definition: trie.test.cc:56
TrieTestData
Definition: trie.test.cc:49
TrieTestData::TrieType
Trie< Addr, uint32_t > TrieType
Definition: trie.test.cc:52
ss
std::stringstream ss
Definition: trace.test.cc:45
types.hh
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
trie.hh

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