diff options
| -rw-r--r-- | src/base/trie.hh | 4 | ||||
| -rw-r--r-- | src/unittest/trietest.cc | 29 |
2 files changed, 14 insertions, 19 deletions
diff --git a/src/base/trie.hh b/src/base/trie.hh index e6b2881ab..1d110b4e1 100644 --- a/src/base/trie.hh +++ b/src/base/trie.hh @@ -185,6 +185,10 @@ class Trie Handle insert(Key key, unsigned width, Value *val) { + // We use NULL value pointers to mark internal nodes of the trie, so + // we don't allow inserting them as real values. + assert(val); + // Build a mask which masks off all the bits we don't care about. Key new_mask = ~(Key)0; if (width < MaxBits) diff --git a/src/unittest/trietest.cc b/src/unittest/trietest.cc index 7abef4ce1..12d434fe6 100644 --- a/src/unittest/trietest.cc +++ b/src/unittest/trietest.cc @@ -30,7 +30,6 @@ #include <iostream> -#include "base/cprintf.hh" #include "base/trie.hh" #include "base/types.hh" #include "unittest/unittest.hh" @@ -54,33 +53,33 @@ main() // Create an empty Ptr and verify it's data pointer is NULL. setCase("An empty trie."); TestTrie trie1; - trie1.dump("Empty"); - cprintf("\n\n"); + EXPECT_EQ(trie1.lookup(0x123456701234567), NULL); setCase("A single entry."); trie1.insert(0x0123456789abcdef, 40, ptr(1)); - trie1.dump("One entry"); - cprintf("\n\n"); + EXPECT_EQ(trie1.lookup(0x123456701234567), NULL); + EXPECT_EQ(trie1.lookup(0x123456789ab0000), ptr(1)); setCase("Two entries, one on the way to the other."); TestTrie trie2; trie2.insert(0x0123456789abcdef, 40, ptr(1)); trie2.insert(0x0123456789abcdef, 36, ptr(2)); - trie2.dump("Two entries inline v1"); - cprintf("\n\n"); + EXPECT_EQ(trie2.lookup(0x123456700000000), NULL); + EXPECT_EQ(trie2.lookup(0x123456789ab0000), ptr(2)); TestTrie trie3; trie3.insert(0x0123456789abcdef, 36, ptr(2)); trie3.insert(0x0123456789abcdef, 40, ptr(1)); - trie3.dump("Two entries inline v2"); - cprintf("\n\n"); + EXPECT_EQ(trie3.lookup(0x123456700000000), NULL); + EXPECT_EQ(trie3.lookup(0x123456789ab0000), ptr(2)); setCase("Two entries on different paths."); TestTrie trie4; trie4.insert(0x0123456789abcdef, 40, ptr(2)); trie4.insert(0x0123456776543210, 40, ptr(1)); - trie4.dump("Two split entries"); - cprintf("\n\n"); + EXPECT_EQ(trie4.lookup(0x0123456789000000), ptr(2)); + EXPECT_EQ(trie4.lookup(0x0123456776000000), ptr(1)); + EXPECT_EQ(trie4.lookup(0x0123456700000000), NULL); setCase("Skipping past an entry but not two."); TestTrie trie5; @@ -88,8 +87,6 @@ main() trie5.insert(0x0123000000000000, 40, ptr(1)); trie5.insert(0x0123456780000000, 40, ptr(3)); trie5.insert(0x0123456700000000, 40, ptr(2)); - trie5.dump("Complex insertion"); - cprintf("\n\n"); setCase("Looking things up."); EXPECT_EQ(trie5.lookup(0x0123000000000000), ptr(1)); @@ -105,8 +102,6 @@ main() trie6.insert(0x0123456780000000, 40, ptr(3)); node1 = trie6.insert(0x0123456700000000, 40, ptr(2)); node2 = trie6.insert(0x0123456700000000, 32, ptr(10)); - trie6.dump("Fill before removal"); - cprintf("\n\n"); EXPECT_EQ(trie6.lookup(0x0123000000000000), ptr(1)); EXPECT_EQ(trie6.lookup(0x0123456700000000), ptr(10)); @@ -114,8 +109,6 @@ main() EXPECT_EQ(trie6.lookup(0x0123456789000000), ptr(10)); trie6.remove(node2); - trie6.dump("One node removed"); - cprintf("\n\n"); EXPECT_EQ(trie6.lookup(0x0123000000000000), ptr(1)); EXPECT_EQ(trie6.lookup(0x0123456700000000), ptr(2)); @@ -123,8 +116,6 @@ main() EXPECT_EQ(trie6.lookup(0x0123456789000000), ptr(4)); trie6.remove(node1); - trie6.dump("Two nodes removed"); - cprintf("\n\n"); EXPECT_EQ(trie6.lookup(0x0123000000000000), ptr(1)); EXPECT_EQ(trie6.lookup(0x0123456700000000), NULL); |