"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/cpp-btree/btree_test.cc" (26 Sep 2015, 10140 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "btree_test.cc" see the Fossies "Dox" file reference documentation.

    1 // Copyright 2013 Google Inc. All Rights Reserved.
    2 //
    3 // Licensed under the Apache License, Version 2.0 (the "License");
    4 // you may not use this file except in compliance with the License.
    5 // You may obtain a copy of the License at
    6 //
    7 //     http://www.apache.org/licenses/LICENSE-2.0
    8 //
    9 // Unless required by applicable law or agreed to in writing, software
   10 // distributed under the License is distributed on an "AS IS" BASIS,
   11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   12 // See the License for the specific language governing permissions and
   13 // limitations under the License.
   14 
   15 #include "gtest/gtest.h"
   16 #include "btree_map.h"
   17 #include "btree_set.h"
   18 #include "btree_test.h"
   19 
   20 namespace btree {
   21 namespace {
   22 
   23 template <typename K, int N>
   24 void SetTest() {
   25   typedef TestAllocator<K> TestAlloc;
   26   ASSERT_EQ(sizeof(btree_set<K>), sizeof(void*));
   27   BtreeTest<btree_set<K, std::less<K>, std::allocator<K>, N>, std::set<K> >();
   28   BtreeAllocatorTest<btree_set<K, std::less<K>, TestAlloc, N> >();
   29 }
   30 
   31 template <typename K, int N>
   32 void MapTest() {
   33   typedef TestAllocator<K> TestAlloc;
   34   ASSERT_EQ(sizeof(btree_map<K, K>), sizeof(void*));
   35   BtreeTest<btree_map<K, K, std::less<K>, std::allocator<K>, N>, std::map<K, K> >();
   36   BtreeAllocatorTest<btree_map<K, K, std::less<K>, TestAlloc, N> >();
   37   BtreeMapTest<btree_map<K, K, std::less<K>, std::allocator<K>, N> >();
   38 }
   39 
   40 TEST(Btree, set_int32_32)   { SetTest<int32_t, 32>(); }
   41 TEST(Btree, set_int32_64)   { SetTest<int32_t, 64>(); }
   42 TEST(Btree, set_int32_128)  { SetTest<int32_t, 128>(); }
   43 TEST(Btree, set_int32_256)  { SetTest<int32_t, 256>(); }
   44 TEST(Btree, set_int64_256)  { SetTest<int64_t, 256>(); }
   45 TEST(Btree, set_string_256) { SetTest<std::string, 256>(); }
   46 TEST(Btree, set_pair_256)   { SetTest<std::pair<int, int>, 256>(); }
   47 TEST(Btree, map_int32_256)  { MapTest<int32_t, 256>(); }
   48 TEST(Btree, map_int64_256)  { MapTest<int64_t, 256>(); }
   49 TEST(Btree, map_string_256) { MapTest<std::string, 256>(); }
   50 TEST(Btree, map_pair_256)   { MapTest<std::pair<int, int>, 256>(); }
   51 
   52 // Large-node tests
   53 TEST(Btree, map_int32_1024)   { MapTest<int32_t, 1024>(); }
   54 TEST(Btree, map_int32_1032)   { MapTest<int32_t, 1032>(); }
   55 TEST(Btree, map_int32_1040)   { MapTest<int32_t, 1040>(); }
   56 TEST(Btree, map_int32_1048)   { MapTest<int32_t, 1048>(); }
   57 TEST(Btree, map_int32_1056)   { MapTest<int32_t, 1056>(); }
   58 
   59 TEST(Btree, map_int32_2048)   { MapTest<int32_t, 2048>(); }
   60 TEST(Btree, map_int32_4096)   { MapTest<int32_t, 4096>(); }
   61 TEST(Btree, set_int32_1024)   { SetTest<int32_t, 1024>(); }
   62 TEST(Btree, set_int32_2048)   { SetTest<int32_t, 2048>(); }
   63 TEST(Btree, set_int32_4096)   { SetTest<int32_t, 4096>(); }
   64 TEST(Btree, map_string_1024)   { MapTest<std::string, 1024>(); }
   65 TEST(Btree, map_string_2048)   { MapTest<std::string, 2048>(); }
   66 TEST(Btree, map_string_4096)   { MapTest<std::string, 4096>(); }
   67 TEST(Btree, set_string_1024)   { SetTest<std::string, 1024>(); }
   68 TEST(Btree, set_string_2048)   { SetTest<std::string, 2048>(); }
   69 TEST(Btree, set_string_4096)   { SetTest<std::string, 4096>(); }
   70 
   71 template <typename K, int N>
   72 void MultiSetTest() {
   73   typedef TestAllocator<K> TestAlloc;
   74   ASSERT_EQ(sizeof(btree_multiset<K>), sizeof(void*));
   75   BtreeMultiTest<btree_multiset<K, std::less<K>, std::allocator<K>, N>,
   76       std::multiset<K> >();
   77   BtreeAllocatorTest<btree_multiset<K, std::less<K>, TestAlloc, N> >();
   78 }
   79 
   80 template <typename K, int N>
   81 void MultiMapTest() {
   82   typedef TestAllocator<K> TestAlloc;
   83   ASSERT_EQ(sizeof(btree_multimap<K, K>), sizeof(void*));
   84   BtreeMultiTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N>,
   85       std::multimap<K, K> >();
   86   BtreeMultiMapTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N> >();
   87   BtreeAllocatorTest<btree_multimap<K, K, std::less<K>, TestAlloc, N> >();
   88 }
   89 
   90 TEST(Btree, multiset_int32_256)  { MultiSetTest<int32_t, 256>(); }
   91 TEST(Btree, multiset_int64_256)  { MultiSetTest<int64_t, 256>(); }
   92 TEST(Btree, multiset_string_256) { MultiSetTest<std::string, 256>(); }
   93 TEST(Btree, multiset_pair_256)   { MultiSetTest<std::pair<int, int>, 256>(); }
   94 TEST(Btree, multimap_int32_256)  { MultiMapTest<int32_t, 256>(); }
   95 TEST(Btree, multimap_int64_256)  { MultiMapTest<int64_t, 256>(); }
   96 TEST(Btree, multimap_string_256) { MultiMapTest<std::string, 256>(); }
   97 TEST(Btree, multimap_pair_256)   { MultiMapTest<std::pair<int, int>, 256>(); }
   98 
   99 // Large-node tests
  100 TEST(Btree, multimap_int32_1024)   { MultiMapTest<int32_t, 1024>(); }
  101 TEST(Btree, multimap_int32_2048)   { MultiMapTest<int32_t, 2048>(); }
  102 TEST(Btree, multimap_int32_4096)   { MultiMapTest<int32_t, 4096>(); }
  103 TEST(Btree, multiset_int32_1024)   { MultiSetTest<int32_t, 1024>(); }
  104 TEST(Btree, multiset_int32_2048)   { MultiSetTest<int32_t, 2048>(); }
  105 TEST(Btree, multiset_int32_4096)   { MultiSetTest<int32_t, 4096>(); }
  106 TEST(Btree, multimap_string_1024)   { MultiMapTest<std::string, 1024>(); }
  107 TEST(Btree, multimap_string_2048)   { MultiMapTest<std::string, 2048>(); }
  108 TEST(Btree, multimap_string_4096)   { MultiMapTest<std::string, 4096>(); }
  109 TEST(Btree, multiset_string_1024)   { MultiSetTest<std::string, 1024>(); }
  110 TEST(Btree, multiset_string_2048)   { MultiSetTest<std::string, 2048>(); }
  111 TEST(Btree, multiset_string_4096)   { MultiSetTest<std::string, 4096>(); }
  112 
  113 // Verify that swapping btrees swaps the key comparision functors.
  114 struct SubstringLess {
  115   SubstringLess() : n(2) {}
  116   SubstringLess(size_t length)
  117       : n(length) {
  118   }
  119   bool operator()(const std::string &a, const std::string &b) const {
  120     std::string as(a.data(), std::min(n, a.size()));
  121     std::string bs(b.data(), std::min(n, b.size()));
  122     return as < bs;
  123   }
  124   size_t n;
  125 };
  126 
  127 TEST(Btree, SwapKeyCompare) {
  128   typedef btree_set<std::string, SubstringLess> SubstringSet;
  129   SubstringSet s1(SubstringLess(1), SubstringSet::allocator_type());
  130   SubstringSet s2(SubstringLess(2), SubstringSet::allocator_type());
  131 
  132   ASSERT_TRUE(s1.insert("a").second);
  133   ASSERT_FALSE(s1.insert("aa").second);
  134 
  135   ASSERT_TRUE(s2.insert("a").second);
  136   ASSERT_TRUE(s2.insert("aa").second);
  137   ASSERT_FALSE(s2.insert("aaa").second);
  138 
  139   swap(s1, s2);
  140 
  141   ASSERT_TRUE(s1.insert("b").second);
  142   ASSERT_TRUE(s1.insert("bb").second);
  143   ASSERT_FALSE(s1.insert("bbb").second);
  144 
  145   ASSERT_TRUE(s2.insert("b").second);
  146   ASSERT_FALSE(s2.insert("bb").second);
  147 }
  148 
  149 TEST(Btree, UpperBoundRegression) {
  150   // Regress a bug where upper_bound would default-construct a new key_compare
  151   // instead of copying the existing one.
  152   typedef btree_set<std::string, SubstringLess> SubstringSet;
  153   SubstringSet my_set(SubstringLess(3));
  154   my_set.insert("aab");
  155   my_set.insert("abb");
  156   // We call upper_bound("aaa").  If this correctly uses the length 3
  157   // comparator, aaa < aab < abb, so we should get aab as the result.
  158   // If it instead uses the default-constructed length 2 comparator,
  159   // aa == aa < ab, so we'll get abb as our result.
  160   SubstringSet::iterator it = my_set.upper_bound("aaa");
  161   ASSERT_TRUE(it != my_set.end());
  162   EXPECT_EQ("aab", *it);
  163 }
  164 
  165 
  166 TEST(Btree, IteratorIncrementBy) {
  167   // Test that increment_by returns the same position as increment.
  168   const int kSetSize = 2341;
  169   btree_set<int32_t> my_set;
  170   for (int i = 0; i < kSetSize; ++i) {
  171     my_set.insert(i);
  172   }
  173 
  174   {
  175     // Simple increment vs. increment by.
  176     btree_set<int32_t>::iterator a = my_set.begin();
  177     btree_set<int32_t>::iterator b = my_set.begin();
  178     a.increment();
  179     b.increment_by(1);
  180     EXPECT_EQ(*a, *b);
  181   }
  182 
  183   btree_set<int32_t>::iterator a = my_set.begin();
  184   for (int i = 1; i < kSetSize; ++i) {
  185     ++a;
  186     // increment_by
  187     btree_set<int32_t>::iterator b = my_set.begin();
  188     b.increment_by(i);
  189     EXPECT_EQ(*a, *b) << ": i=" << i;
  190   }
  191 }
  192 
  193 TEST(Btree, Comparison) {
  194   const int kSetSize = 1201;
  195   btree_set<int64_t> my_set;
  196   for (int i = 0; i < kSetSize; ++i) {
  197     my_set.insert(i);
  198   }
  199   btree_set<int64_t> my_set_copy(my_set);
  200   EXPECT_TRUE(my_set_copy == my_set);
  201   EXPECT_TRUE(my_set == my_set_copy);
  202   EXPECT_FALSE(my_set_copy != my_set);
  203   EXPECT_FALSE(my_set != my_set_copy);
  204 
  205   my_set.insert(kSetSize);
  206   EXPECT_FALSE(my_set_copy == my_set);
  207   EXPECT_FALSE(my_set == my_set_copy);
  208   EXPECT_TRUE(my_set_copy != my_set);
  209   EXPECT_TRUE(my_set != my_set_copy);
  210 
  211   my_set.erase(kSetSize - 1);
  212   EXPECT_FALSE(my_set_copy == my_set);
  213   EXPECT_FALSE(my_set == my_set_copy);
  214   EXPECT_TRUE(my_set_copy != my_set);
  215   EXPECT_TRUE(my_set != my_set_copy);
  216 
  217   btree_map<std::string, int64_t> my_map;
  218   for (int i = 0; i < kSetSize; ++i) {
  219     my_map[std::string(i, 'a')] = i;
  220   }
  221   btree_map<std::string, int64_t> my_map_copy(my_map);
  222   EXPECT_TRUE(my_map_copy == my_map);
  223   EXPECT_TRUE(my_map == my_map_copy);
  224   EXPECT_FALSE(my_map_copy != my_map);
  225   EXPECT_FALSE(my_map != my_map_copy);
  226 
  227   ++my_map_copy[std::string(7, 'a')];
  228   EXPECT_FALSE(my_map_copy == my_map);
  229   EXPECT_FALSE(my_map == my_map_copy);
  230   EXPECT_TRUE(my_map_copy != my_map);
  231   EXPECT_TRUE(my_map != my_map_copy);
  232 
  233   my_map_copy = my_map;
  234   my_map["hello"] = kSetSize;
  235   EXPECT_FALSE(my_map_copy == my_map);
  236   EXPECT_FALSE(my_map == my_map_copy);
  237   EXPECT_TRUE(my_map_copy != my_map);
  238   EXPECT_TRUE(my_map != my_map_copy);
  239 
  240   my_map.erase(std::string(kSetSize - 1, 'a'));
  241   EXPECT_FALSE(my_map_copy == my_map);
  242   EXPECT_FALSE(my_map == my_map_copy);
  243   EXPECT_TRUE(my_map_copy != my_map);
  244   EXPECT_TRUE(my_map != my_map_copy);
  245 }
  246 
  247 TEST(Btree, RangeCtorSanity) {
  248   typedef btree_set<int, std::less<int>, std::allocator<int>, 256> test_set;
  249   typedef btree_map<int, int, std::less<int>, std::allocator<int>, 256> 
  250       test_map;
  251   typedef btree_multiset<int, std::less<int>, std::allocator<int>, 256> 
  252       test_mset;
  253   typedef btree_multimap<int, int, std::less<int>, std::allocator<int>, 256> 
  254       test_mmap;
  255   std::vector<int> ivec;
  256   ivec.push_back(1);
  257   std::map<int, int> imap;
  258   imap.insert(std::make_pair(1, 2));
  259   test_mset tmset(ivec.begin(), ivec.end());
  260   test_mmap tmmap(imap.begin(), imap.end());
  261   test_set tset(ivec.begin(), ivec.end());
  262   test_map tmap(imap.begin(), imap.end());
  263   EXPECT_EQ(1, tmset.size());
  264   EXPECT_EQ(1, tmmap.size());
  265   EXPECT_EQ(1, tset.size());
  266   EXPECT_EQ(1, tmap.size());
  267 }
  268 
  269 } // namespace
  270 } // namespace btree