2 * Copyright (c) 2012 Google
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.
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.
34 #include "base/cprintf.hh"
35 #include "base/trie.hh"
36 #include "base/types.hh"
37 #include "unittest/unittest.hh"
39 using UnitTest::setCase
;
41 typedef Trie
<Addr
, uint32_t> TestTrie
;
46 // Create an empty Ptr and verify it's data pointer is NULL.
47 setCase("An empty trie.");
52 setCase("A single entry.");
53 trie1
.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1));
54 trie1
.dump("One entry");
57 setCase("Two entries, one on the way to the other.");
59 trie2
.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1));
60 trie2
.insert(0x0123456789abcdef, 36, (uint32_t *)(uintptr_t)(2));
61 trie2
.dump("Two entries inline v1");
65 trie3
.insert(0x0123456789abcdef, 36, (uint32_t *)(uintptr_t)(2));
66 trie3
.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1));
67 trie3
.dump("Two entries inline v2");
70 setCase("Two entries on different paths.");
72 trie4
.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(2));
73 trie4
.insert(0x0123456776543210, 40, (uint32_t *)(uintptr_t)(1));
74 trie4
.dump("Two split entries");
77 setCase("Skipping past an entry but not two.");
79 trie5
.insert(0x0123456789000000, 40, (uint32_t *)(uintptr_t)(4));
80 trie5
.insert(0x0123000000000000, 40, (uint32_t *)(uintptr_t)(1));
81 trie5
.insert(0x0123456780000000, 40, (uint32_t *)(uintptr_t)(3));
82 trie5
.insert(0x0123456700000000, 40, (uint32_t *)(uintptr_t)(2));
83 trie5
.dump("Complex insertion");
86 setCase("Looking things up.");
87 EXPECT_EQ((uintptr_t)trie5
.lookup(0x0123000000000000), 1);
88 EXPECT_EQ((uintptr_t)trie5
.lookup(0x0123456700000000), 2);
89 EXPECT_EQ((uintptr_t)trie5
.lookup(0x0123456780000000), 3);
90 EXPECT_EQ((uintptr_t)trie5
.lookup(0x0123456789000000), 4);
92 setCase("Removing entries.");
94 TestTrie::Handle node1
, node2
;
95 trie6
.insert(0x0123456789000000, 40, (uint32_t *)(uintptr_t)(4));
96 trie6
.insert(0x0123000000000000, 40, (uint32_t *)(uintptr_t)(1));
97 trie6
.insert(0x0123456780000000, 40, (uint32_t *)(uintptr_t)(3));
98 node1
= trie6
.insert(0x0123456700000000, 40, (uint32_t *)(uintptr_t)(2));
99 node2
= trie6
.insert(0x0123456700000000, 32, (uint32_t *)(uintptr_t)(10));
100 trie6
.dump("Fill before removal");
103 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123000000000000), 1);
104 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456700000000), 10);
105 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456780000000), 10);
106 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456789000000), 10);
109 trie6
.dump("One node removed");
112 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123000000000000), 1);
113 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456700000000), 2);
114 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456780000000), 3);
115 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456789000000), 4);
118 trie6
.dump("Two nodes removed");
121 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123000000000000), 1);
122 EXPECT_EQ(trie6
.lookup(0x0123456700000000), NULL
);
123 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456780000000), 3);
124 EXPECT_EQ((uintptr_t)trie6
.lookup(0x0123456789000000), 4);
126 return UnitTest::printResults();