src/base/trie.test.cc

37 #include "base/trie.hh"
53     TrieType trie;
59         trie.dump("test trie", ss);
66     EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
71     trie.insert(0x0123456789abcdef, 40, ptr(1));
72     EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie();
73     EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(1)) << dumpTrie();
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();
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();
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();
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));
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();
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));
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();
128     trie.remove(node2);
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();
135     trie.remove(node1);
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();