From c4c27ded423b9beb0e361421ca83fe0eac06a0d1 Mon Sep 17 00:00:00 2001 From: Gabe Black Date: Sat, 14 Apr 2012 23:19:34 -0700 Subject: sim: A trie data structure specifically to speed up paging lookups. This change adds a trie data structure which stores an arbitrary pointer type based on an address and a number of relevant bits. Then lookups can be done against the trie where the tree is traversed and the first legitimate match found is returned. --- src/unittest/trietest.cc | 127 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 127 insertions(+) create mode 100644 src/unittest/trietest.cc (limited to 'src/unittest/trietest.cc') diff --git a/src/unittest/trietest.cc b/src/unittest/trietest.cc new file mode 100644 index 000000000..ed8a772fa --- /dev/null +++ b/src/unittest/trietest.cc @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2012 Google + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer; + * redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution; + * neither the name of the copyright holders nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * Authors: Gabe Black + */ + +#include +#include + +#include "base/cprintf.hh" +#include "base/trie.hh" +#include "base/types.hh" +#include "unittest/unittest.hh" + +using UnitTest::setCase; + +typedef Trie TestTrie; + +int +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"); + + setCase("A single entry."); + trie1.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1)); + trie1.dump("One entry"); + cprintf("\n\n"); + + setCase("Two entries, one on the way to the other."); + TestTrie trie2; + trie2.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1)); + trie2.insert(0x0123456789abcdef, 36, (uint32_t *)(uintptr_t)(2)); + trie2.dump("Two entries inline v1"); + cprintf("\n\n"); + + TestTrie trie3; + trie3.insert(0x0123456789abcdef, 36, (uint32_t *)(uintptr_t)(2)); + trie3.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1)); + trie3.dump("Two entries inline v2"); + cprintf("\n\n"); + + setCase("Two entries on different paths."); + TestTrie trie4; + trie4.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(2)); + trie4.insert(0x0123456776543210, 40, (uint32_t *)(uintptr_t)(1)); + trie4.dump("Two split entries"); + cprintf("\n\n"); + + setCase("Skipping past an entry but not two."); + TestTrie trie5; + trie5.insert(0x0123456789000000, 40, (uint32_t *)(uintptr_t)(4)); + trie5.insert(0x0123000000000000, 40, (uint32_t *)(uintptr_t)(1)); + trie5.insert(0x0123456780000000, 40, (uint32_t *)(uintptr_t)(3)); + trie5.insert(0x0123456700000000, 40, (uint32_t *)(uintptr_t)(2)); + trie5.dump("Complex insertion"); + cprintf("\n\n"); + + setCase("Looking things up."); + EXPECT_EQ((uintptr_t)trie5.lookup(0x0123000000000000), 1); + EXPECT_EQ((uintptr_t)trie5.lookup(0x0123456700000000), 2); + EXPECT_EQ((uintptr_t)trie5.lookup(0x0123456780000000), 3); + EXPECT_EQ((uintptr_t)trie5.lookup(0x0123456789000000), 4); + + setCase("Removing entries."); + TestTrie trie6; + TestTrie::Handle node1, node2; + trie6.insert(0x0123456789000000, 40, (uint32_t *)(uintptr_t)(4)); + trie6.insert(0x0123000000000000, 40, (uint32_t *)(uintptr_t)(1)); + trie6.insert(0x0123456780000000, 40, (uint32_t *)(uintptr_t)(3)); + node1 = trie6.insert(0x0123456700000000, 40, (uint32_t *)(uintptr_t)(2)); + node2 = trie6.insert(0x0123456700000000, 32, (uint32_t *)(uintptr_t)(10)); + trie6.dump("Fill before removal"); + cprintf("\n\n"); + + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123000000000000), 1); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456700000000), 10); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456780000000), 10); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456789000000), 10); + + trie6.remove(node2); + trie6.dump("One node removed"); + cprintf("\n\n"); + + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123000000000000), 1); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456700000000), 2); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456780000000), 3); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456789000000), 4); + + trie6.remove(node1); + trie6.dump("Two nodes removed"); + cprintf("\n\n"); + + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123000000000000), 1); + EXPECT_EQ(trie6.lookup(0x0123456700000000), NULL); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456780000000), 3); + EXPECT_EQ((uintptr_t)trie6.lookup(0x0123456789000000), 4); + + return UnitTest::printResults(); +} -- cgit v1.2.3