src/unittest/trietest.cc

   1 /*
   2  * Copyright (c) 2012 Google
   3  * All rights reserved.
   4  *
   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.
  15  *
  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.
  27  *
  28  * Authors: Gabe Black
  29  */
  30
  31 #include <cassert>
  32 #include <iostream>
  33
  34 #include "base/cprintf.hh"
  35 #include "base/trie.hh"
  36 #include "base/types.hh"
  37 #include "unittest/unittest.hh"
  38
  39 using UnitTest::setCase;
  40
  41 typedef Trie<Addr, uint32_t> TestTrie;
  42
  43 int
  44 main()
  45 {
  46     // Create an empty Ptr and verify it's data pointer is NULL.
  47     setCase("An empty trie.");
  48     TestTrie trie1;
  49     trie1.dump("Empty");
  50     cprintf("\n\n");
  51
  52     setCase("A single entry.");
  53     trie1.insert(0x0123456789abcdef, 40, (uint32_t *)(uintptr_t)(1));
  54     trie1.dump("One entry");
  55     cprintf("\n\n");
  56
  57     setCase("Two entries, one on the way to the other.");
  58     TestTrie trie2;
  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");
  62     cprintf("\n\n");
  63
  64     TestTrie trie3;
  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");
  68     cprintf("\n\n");
  69
  70     setCase("Two entries on different paths.");
  71     TestTrie trie4;
  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");
  75     cprintf("\n\n");
  76
  77     setCase("Skipping past an entry but not two.");
  78     TestTrie trie5;
  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");
  84     cprintf("\n\n");
  85
  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);
  91
  92     setCase("Removing entries.");
  93     TestTrie trie6;
  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");
 101     cprintf("\n\n");
 102
 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);
 107
 108     trie6.remove(node2);
 109     trie6.dump("One node removed");
 110     cprintf("\n\n");
 111
 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);
 116
 117     trie6.remove(node1);
 118     trie6.dump("Two nodes removed");
 119     cprintf("\n\n");
 120
 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);
 125
 126     return UnitTest::printResults();
 127 }