113465Sgabeblack@google.com/* 213465Sgabeblack@google.com * Copyright (c) 2012 Google 313465Sgabeblack@google.com * All rights reserved. 413465Sgabeblack@google.com * 513465Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 613465Sgabeblack@google.com * modification, are permitted provided that the following conditions are 713465Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 813465Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 913465Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1013465Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1113465Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1213465Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1313465Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1413465Sgabeblack@google.com * this software without specific prior written permission. 1513465Sgabeblack@google.com * 1613465Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713465Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813465Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913465Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013465Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113465Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213465Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313465Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413465Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513465Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613465Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713465Sgabeblack@google.com * 2813465Sgabeblack@google.com * Authors: Gabe Black 2913465Sgabeblack@google.com */ 3013465Sgabeblack@google.com 3113465Sgabeblack@google.com#include <gtest/gtest.h> 3213465Sgabeblack@google.com 3313465Sgabeblack@google.com#include <iostream> 3413465Sgabeblack@google.com#include <sstream> 3513465Sgabeblack@google.com#include <string> 3613465Sgabeblack@google.com 3713465Sgabeblack@google.com#include "base/trie.hh" 3813465Sgabeblack@google.com#include "base/types.hh" 3913465Sgabeblack@google.com 4013465Sgabeblack@google.comnamespace { 4113465Sgabeblack@google.com 4213465Sgabeblack@google.comstatic inline uint32_t *ptr(uintptr_t val) 4313465Sgabeblack@google.com{ 4413465Sgabeblack@google.com return (uint32_t *)val; 4513465Sgabeblack@google.com} 4613465Sgabeblack@google.com 4713465Sgabeblack@google.com} // anonymous namespace 4813465Sgabeblack@google.com 4913465Sgabeblack@google.comclass TrieTestData : public testing::Test 5013465Sgabeblack@google.com{ 5113465Sgabeblack@google.com protected: 5213465Sgabeblack@google.com typedef Trie<Addr, uint32_t> TrieType; 5313465Sgabeblack@google.com TrieType trie; 5413465Sgabeblack@google.com 5513465Sgabeblack@google.com std::string 5613465Sgabeblack@google.com dumpTrie() 5713465Sgabeblack@google.com { 5813465Sgabeblack@google.com std::stringstream ss; 5913465Sgabeblack@google.com trie.dump("test trie", ss); 6013465Sgabeblack@google.com return ss.str(); 6113465Sgabeblack@google.com } 6213465Sgabeblack@google.com}; 6313465Sgabeblack@google.com 6413465Sgabeblack@google.comTEST_F(TrieTestData, Empty) 6513465Sgabeblack@google.com{ 6613465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie(); 6713465Sgabeblack@google.com} 6813465Sgabeblack@google.com 6913465Sgabeblack@google.comTEST_F(TrieTestData, SingleEntry) 7013465Sgabeblack@google.com{ 7113465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 40, ptr(1)); 7213465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456701234567), nullptr) << dumpTrie(); 7313465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(1)) << dumpTrie(); 7413465Sgabeblack@google.com} 7513465Sgabeblack@google.com 7613465Sgabeblack@google.comTEST_F(TrieTestData, TwoOverlappingEntries) 7713465Sgabeblack@google.com{ 7813465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 40, ptr(1)); 7913465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 36, ptr(2)); 8013465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie(); 8113465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie(); 8213465Sgabeblack@google.com} 8313465Sgabeblack@google.com 8413465Sgabeblack@google.comTEST_F(TrieTestData, TwoOverlappingEntriesReversed) 8513465Sgabeblack@google.com{ 8613465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 36, ptr(2)); 8713465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 40, ptr(1)); 8813465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456700000000), nullptr) << dumpTrie(); 8913465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x123456789ab0000), ptr(2)) << dumpTrie(); 9013465Sgabeblack@google.com} 9113465Sgabeblack@google.com 9213465Sgabeblack@google.comTEST_F(TrieTestData, TwoIndependentEntries) 9313465Sgabeblack@google.com{ 9413465Sgabeblack@google.com trie.insert(0x0123456789abcdef, 40, ptr(2)); 9513465Sgabeblack@google.com trie.insert(0x0123456776543210, 40, ptr(1)); 9613465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(2)) << dumpTrie(); 9713465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456776000000), ptr(1)) << dumpTrie(); 9813465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie(); 9913465Sgabeblack@google.com} 10013465Sgabeblack@google.com 10113465Sgabeblack@google.comTEST_F(TrieTestData, TwoEntries) 10213465Sgabeblack@google.com{ 10313465Sgabeblack@google.com trie.insert(0x0123456789000000, 40, ptr(4)); 10413465Sgabeblack@google.com trie.insert(0x0123000000000000, 40, ptr(1)); 10513465Sgabeblack@google.com trie.insert(0x0123456780000000, 40, ptr(3)); 10613465Sgabeblack@google.com trie.insert(0x0123456700000000, 40, ptr(2)); 10713465Sgabeblack@google.com 10813465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie(); 10913465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie(); 11013465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie(); 11113465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie(); 11213465Sgabeblack@google.com} 11313465Sgabeblack@google.com 11413465Sgabeblack@google.comTEST_F(TrieTestData, RemovingEntries) 11513465Sgabeblack@google.com{ 11613465Sgabeblack@google.com TrieType::Handle node1, node2; 11713465Sgabeblack@google.com trie.insert(0x0123456789000000, 40, ptr(4)); 11813465Sgabeblack@google.com trie.insert(0x0123000000000000, 40, ptr(1)); 11913465Sgabeblack@google.com trie.insert(0x0123456780000000, 40, ptr(3)); 12013465Sgabeblack@google.com node1 = trie.insert(0x0123456700000000, 40, ptr(2)); 12113465Sgabeblack@google.com node2 = trie.insert(0x0123456700000000, 32, ptr(10)); 12213465Sgabeblack@google.com 12313465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie(); 12413465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(10)) << dumpTrie(); 12513465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(10)) << dumpTrie(); 12613465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(10)) << dumpTrie(); 12713465Sgabeblack@google.com 12813465Sgabeblack@google.com trie.remove(node2); 12913465Sgabeblack@google.com 13013465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie(); 13113465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456700000000), ptr(2)) << dumpTrie(); 13213465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie(); 13313465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie(); 13413465Sgabeblack@google.com 13513465Sgabeblack@google.com trie.remove(node1); 13613465Sgabeblack@google.com 13713465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123000000000000), ptr(1)) << dumpTrie(); 13813465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456700000000), nullptr) << dumpTrie(); 13913465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456780000000), ptr(3)) << dumpTrie(); 14013465Sgabeblack@google.com EXPECT_EQ(trie.lookup(0x0123456789000000), ptr(4)) << dumpTrie(); 14113465Sgabeblack@google.com} 142