"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/cpp-btree/btree_test.h" (26 Sep 2015, 30150 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.h" 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 #ifndef UTIL_BTREE_BTREE_TEST_H__
   16 #define UTIL_BTREE_BTREE_TEST_H__
   17 
   18 #include <stdio.h>
   19 #include <algorithm>
   20 #include <functional>
   21 #include <type_traits>
   22 #include <iosfwd>
   23 #include <map>
   24 #include <set>
   25 #include <sstream>
   26 #include <string>
   27 #include <utility>
   28 #include <vector>
   29 
   30 #include "gtest/gtest.h"
   31 #include "gflags/gflags.h"
   32 #include "btree_container.h"
   33 
   34 DECLARE_int32(test_values);
   35 DECLARE_int32(benchmark_values);
   36 
   37 namespace std {
   38 
   39 // Provide operator<< support for std::pair<T, U>.
   40 template <typename T, typename U>
   41 ostream& operator<<(ostream &os, const std::pair<T, U> &p) {
   42   os << "(" << p.first << "," << p.second << ")";
   43   return os;
   44 }
   45 
   46 // Provide pair equality testing that works as long as x.first is comparable to
   47 // y.first and x.second is comparable to y.second. Needed in the test for
   48 // comparing std::pair<T, U> to std::pair<const T, U>.
   49 template <typename T, typename U, typename V, typename W>
   50 bool operator==(const std::pair<T, U> &x, const std::pair<V, W> &y) {
   51   return x.first == y.first && x.second == y.second;
   52 }
   53 
   54 // Partial specialization of remove_const that propagates the removal through
   55 // std::pair.
   56 template <typename T, typename U>
   57 struct remove_const<pair<T, U> > {
   58   typedef pair<typename remove_const<T>::type,
   59                typename remove_const<U>::type> type;
   60 };
   61 
   62 } // namespace std
   63 
   64 namespace btree {
   65 
   66 // Select the first member of a pair.
   67 template <class _Pair>
   68 struct select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
   69   const typename _Pair::first_type& operator()(const _Pair& __x) const {
   70     return __x.first;
   71   }
   72 };
   73 
   74 // Utility class to provide an accessor for a key given a value. The default
   75 // behavior is to treat the value as a pair and return the first element.
   76 template <typename K, typename V>
   77 struct KeyOfValue {
   78   typedef select1st<V> type;
   79 };
   80 
   81 template <typename T>
   82 struct identity {
   83   inline const T& operator()(const T& t) const { return t; }
   84 };
   85 
   86 // Partial specialization of KeyOfValue class for when the key and value are
   87 // the same type such as in set<> and btree_set<>.
   88 template <typename K>
   89 struct KeyOfValue<K, K> {
   90   typedef identity<K> type;
   91 };
   92 
   93 // Counts the number of occurances of "c" in a buffer.
   94 inline ptrdiff_t strcount(const char* buf_begin, const char* buf_end, char c) {
   95   if (buf_begin == NULL)
   96     return 0;
   97   if (buf_end <= buf_begin)
   98     return 0;
   99   ptrdiff_t num = 0;
  100   for (const char* bp = buf_begin; bp != buf_end; bp++) {
  101     if (*bp == c)
  102       num++;
  103   }
  104   return num;
  105 }
  106 
  107 // for when the string is not null-terminated.
  108 inline ptrdiff_t strcount(const char* buf, size_t len, char c) {
  109   return strcount(buf, buf + len, c);
  110 }
  111 
  112 inline ptrdiff_t strcount(const std::string& buf, char c) {
  113   return strcount(buf.c_str(), buf.size(), c);
  114 }
  115 
  116 // The base class for a sorted associative container checker. TreeType is the
  117 // container type to check and CheckerType is the container type to check
  118 // against. TreeType is expected to be btree_{set,map,multiset,multimap} and
  119 // CheckerType is expected to be {set,map,multiset,multimap}.
  120 template <typename TreeType, typename CheckerType>
  121 class base_checker {
  122   typedef base_checker<TreeType, CheckerType> self_type;
  123 
  124  public:
  125   typedef typename TreeType::key_type key_type;
  126   typedef typename TreeType::value_type value_type;
  127   typedef typename TreeType::key_compare key_compare;
  128   typedef typename TreeType::pointer pointer;
  129   typedef typename TreeType::const_pointer const_pointer;
  130   typedef typename TreeType::reference reference;
  131   typedef typename TreeType::const_reference const_reference;
  132   typedef typename TreeType::size_type size_type;
  133   typedef typename TreeType::difference_type difference_type;
  134   typedef typename TreeType::iterator iterator;
  135   typedef typename TreeType::const_iterator const_iterator;
  136   typedef typename TreeType::reverse_iterator reverse_iterator;
  137   typedef typename TreeType::const_reverse_iterator const_reverse_iterator;
  138 
  139  public:
  140   // Default constructor.
  141   base_checker()
  142       : const_tree_(tree_) {
  143   }
  144   // Copy constructor.
  145   base_checker(const self_type &x)
  146       : tree_(x.tree_),
  147         const_tree_(tree_),
  148         checker_(x.checker_) {
  149   }
  150   // Range constructor.
  151   template <typename InputIterator>
  152   base_checker(InputIterator b, InputIterator e)
  153       : tree_(b, e),
  154         const_tree_(tree_),
  155         checker_(b, e) {
  156   }
  157 
  158   // Iterator routines.
  159   iterator begin() { return tree_.begin(); }
  160   const_iterator begin() const { return tree_.begin(); }
  161   iterator end() { return tree_.end(); }
  162   const_iterator end() const { return tree_.end(); }
  163   reverse_iterator rbegin() { return tree_.rbegin(); }
  164   const_reverse_iterator rbegin() const { return tree_.rbegin(); }
  165   reverse_iterator rend() { return tree_.rend(); }
  166   const_reverse_iterator rend() const { return tree_.rend(); }
  167 
  168   // Helper routines.
  169   template <typename IterType, typename CheckerIterType>
  170   IterType iter_check(
  171       IterType tree_iter, CheckerIterType checker_iter) const {
  172     if (tree_iter == tree_.end()) {
  173       EXPECT_EQ(checker_iter, checker_.end());
  174     } else {
  175       EXPECT_EQ(*tree_iter, *checker_iter);
  176     }
  177     return tree_iter;
  178   }
  179   template <typename IterType, typename CheckerIterType>
  180   IterType riter_check(
  181       IterType tree_iter, CheckerIterType checker_iter) const {
  182     if (tree_iter == tree_.rend()) {
  183       EXPECT_EQ(checker_iter, checker_.rend());
  184     } else {
  185       EXPECT_EQ(*tree_iter, *checker_iter);
  186     }
  187     return tree_iter;
  188   }
  189   void value_check(const value_type &x) {
  190     typename KeyOfValue<typename TreeType::key_type,
  191         typename TreeType::value_type>::type key_of_value;
  192     const key_type &key = key_of_value(x);
  193     EXPECT_EQ(*find(key), x);
  194     lower_bound(key);
  195     upper_bound(key);
  196     equal_range(key);
  197     count(key);
  198   }
  199   void erase_check(const key_type &key) {
  200     EXPECT_TRUE(tree_.find(key) == const_tree_.end());
  201     EXPECT_TRUE(const_tree_.find(key) == tree_.end());
  202     EXPECT_TRUE(tree_.equal_range(key).first ==
  203                 const_tree_.equal_range(key).second);
  204   }
  205 
  206   // Lookup routines.
  207   iterator lower_bound(const key_type &key) {
  208     return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
  209   }
  210   const_iterator lower_bound(const key_type &key) const {
  211     return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
  212   }
  213   iterator upper_bound(const key_type &key) {
  214     return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
  215   }
  216   const_iterator upper_bound(const key_type &key) const {
  217     return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
  218   }
  219   std::pair<iterator,iterator> equal_range(const key_type &key) {
  220     std::pair<typename CheckerType::iterator,
  221         typename CheckerType::iterator> checker_res =
  222         checker_.equal_range(key);
  223     std::pair<iterator, iterator> tree_res = tree_.equal_range(key);
  224     iter_check(tree_res.first, checker_res.first);
  225     iter_check(tree_res.second, checker_res.second);
  226     return tree_res;
  227   }
  228   std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const {
  229     std::pair<typename CheckerType::const_iterator,
  230         typename CheckerType::const_iterator> checker_res =
  231         checker_.equal_range(key);
  232     std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key);
  233     iter_check(tree_res.first, checker_res.first);
  234     iter_check(tree_res.second, checker_res.second);
  235     return tree_res;
  236   }
  237   iterator find(const key_type &key) {
  238     return iter_check(tree_.find(key), checker_.find(key));
  239   }
  240   const_iterator find(const key_type &key) const {
  241     return iter_check(tree_.find(key), checker_.find(key));
  242   }
  243   size_type count(const key_type &key) const {
  244     size_type res = checker_.count(key);
  245     EXPECT_EQ(res, tree_.count(key));
  246     return res;
  247   }
  248 
  249   // Assignment operator.
  250   self_type& operator=(const self_type &x) {
  251     tree_ = x.tree_;
  252     checker_ = x.checker_;
  253     return *this;
  254   }
  255 
  256   // Deletion routines.
  257   int erase(const key_type &key) {
  258     int size = tree_.size();
  259     int res = checker_.erase(key);
  260     EXPECT_EQ(res, tree_.count(key));
  261     EXPECT_EQ(res, tree_.erase(key));
  262     EXPECT_EQ(tree_.count(key), 0);
  263     EXPECT_EQ(tree_.size(), size - res);
  264     erase_check(key);
  265     return res;
  266   }
  267   iterator erase(iterator iter) {
  268     key_type key = iter.key();
  269     int size = tree_.size();
  270     int count = tree_.count(key);
  271     typename CheckerType::iterator checker_iter = checker_.find(key);
  272     for (iterator tmp(tree_.find(key)); tmp != iter; ++tmp) {
  273       ++checker_iter;
  274     }
  275     typename CheckerType::iterator checker_next = checker_iter;
  276     ++checker_next;
  277     checker_.erase(checker_iter);
  278     iter = tree_.erase(iter);
  279     EXPECT_EQ(tree_.size(), checker_.size());
  280     EXPECT_EQ(tree_.size(), size - 1);
  281     EXPECT_EQ(tree_.count(key), count - 1);
  282     if (count == 1) {
  283       erase_check(key);
  284     }
  285     return iter_check(iter, checker_next);
  286   }
  287 
  288   void erase(iterator begin, iterator end) {
  289     int size = tree_.size();
  290     int count = distance(begin, end);
  291     typename CheckerType::iterator checker_begin = checker_.find(begin.key());
  292     for (iterator tmp(tree_.find(begin.key())); tmp != begin; ++tmp) {
  293       ++checker_begin;
  294     }
  295     typename CheckerType::iterator checker_end =
  296         end == tree_.end() ? checker_.end() : checker_.find(end.key());
  297     if (end != tree_.end()) {
  298       for (iterator tmp(tree_.find(end.key())); tmp != end; ++tmp) {
  299         ++checker_end;
  300       }
  301     }
  302     checker_.erase(checker_begin, checker_end);
  303     tree_.erase(begin, end);
  304     EXPECT_EQ(tree_.size(), checker_.size());
  305     EXPECT_EQ(tree_.size(), size - count);
  306   }
  307 
  308   // Utility routines.
  309   void clear() {
  310     tree_.clear();
  311     checker_.clear();
  312   }
  313   void swap(self_type &x) {
  314     tree_.swap(x.tree_);
  315     checker_.swap(x.checker_);
  316   }
  317 
  318   void verify() const {
  319     tree_.verify();
  320     EXPECT_EQ(tree_.size(), checker_.size());
  321 
  322     // Move through the forward iterators using increment.
  323     typename CheckerType::const_iterator
  324         checker_iter(checker_.begin());
  325     const_iterator tree_iter(tree_.begin());
  326     for (; tree_iter != tree_.end();
  327          ++tree_iter, ++checker_iter) {
  328       EXPECT_EQ(*tree_iter, *checker_iter);
  329     }
  330 
  331     // Move through the forward iterators using decrement.
  332     for (int n = tree_.size() - 1; n >= 0; --n) {
  333       iter_check(tree_iter, checker_iter);
  334       --tree_iter;
  335       --checker_iter;
  336     }
  337     EXPECT_TRUE(tree_iter == tree_.begin());
  338     EXPECT_TRUE(checker_iter == checker_.begin());
  339 
  340     // Move through the reverse iterators using increment.
  341     typename CheckerType::const_reverse_iterator
  342         checker_riter(checker_.rbegin());
  343     const_reverse_iterator tree_riter(tree_.rbegin());
  344     for (; tree_riter != tree_.rend();
  345          ++tree_riter, ++checker_riter) {
  346       EXPECT_EQ(*tree_riter, *checker_riter);
  347     }
  348 
  349     // Move through the reverse iterators using decrement.
  350     for (int n = tree_.size() - 1; n >= 0; --n) {
  351       riter_check(tree_riter, checker_riter);
  352       --tree_riter;
  353       --checker_riter;
  354     }
  355     EXPECT_EQ(tree_riter, tree_.rbegin());
  356     EXPECT_EQ(checker_riter, checker_.rbegin());
  357   }
  358 
  359   // Access to the underlying btree.
  360   const TreeType& tree() const { return tree_; }
  361 
  362   // Size routines.
  363   size_type size() const {
  364     EXPECT_EQ(tree_.size(), checker_.size());
  365     return tree_.size();
  366   }
  367   size_type max_size() const { return tree_.max_size(); }
  368   bool empty() const {
  369     EXPECT_EQ(tree_.empty(), checker_.empty());
  370     return tree_.empty();
  371   }
  372   size_type height() const { return tree_.height(); }
  373   size_type internal_nodes() const { return tree_.internal_nodes(); }
  374   size_type leaf_nodes() const { return tree_.leaf_nodes(); }
  375   size_type nodes() const { return tree_.nodes(); }
  376   size_type bytes_used() const { return tree_.bytes_used(); }
  377   double fullness() const { return tree_.fullness(); }
  378   double overhead() const { return tree_.overhead(); }
  379 
  380  protected:
  381   TreeType tree_;
  382   const TreeType &const_tree_;
  383   CheckerType checker_;
  384 };
  385 
  386 // A checker for unique sorted associative containers. TreeType is expected to
  387 // be btree_{set,map} and CheckerType is expected to be {set,map}.
  388 template <typename TreeType, typename CheckerType>
  389 class unique_checker : public base_checker<TreeType, CheckerType> {
  390   typedef base_checker<TreeType, CheckerType> super_type;
  391   typedef unique_checker<TreeType, CheckerType> self_type;
  392 
  393  public:
  394   typedef typename super_type::iterator iterator;
  395   typedef typename super_type::value_type value_type;
  396 
  397  public:
  398   // Default constructor.
  399   unique_checker()
  400       : super_type() {
  401   }
  402   // Copy constructor.
  403   unique_checker(const self_type &x)
  404       : super_type(x) {
  405   }
  406   // Range constructor.
  407   template <class InputIterator>
  408   unique_checker(InputIterator b, InputIterator e)
  409       : super_type(b, e) {
  410   }
  411 
  412   // Insertion routines.
  413   std::pair<iterator,bool> insert(const value_type &x) {
  414     int size = this->tree_.size();
  415     std::pair<typename CheckerType::iterator,bool> checker_res =
  416         this->checker_.insert(x);
  417     std::pair<iterator,bool> tree_res = this->tree_.insert(x);
  418     EXPECT_EQ(*tree_res.first, *checker_res.first);
  419     EXPECT_EQ(tree_res.second, checker_res.second);
  420     EXPECT_EQ(this->tree_.size(), this->checker_.size());
  421     EXPECT_EQ(this->tree_.size(), size + tree_res.second);
  422     return tree_res;
  423   }
  424   iterator insert(iterator position, const value_type &x) {
  425     int size = this->tree_.size();
  426     std::pair<typename CheckerType::iterator,bool> checker_res =
  427         this->checker_.insert(x);
  428     iterator tree_res = this->tree_.insert(position, x);
  429     EXPECT_EQ(*tree_res, *checker_res.first);
  430     EXPECT_EQ(this->tree_.size(), this->checker_.size());
  431     EXPECT_EQ(this->tree_.size(), size + checker_res.second);
  432     return tree_res;
  433   }
  434   template <typename InputIterator>
  435   void insert(InputIterator b, InputIterator e) {
  436     for (; b != e; ++b) {
  437       insert(*b);
  438     }
  439   }
  440 };
  441 
  442 // A checker for multiple sorted associative containers. TreeType is expected
  443 // to be btree_{multiset,multimap} and CheckerType is expected to be
  444 // {multiset,multimap}.
  445 template <typename TreeType, typename CheckerType>
  446 class multi_checker : public base_checker<TreeType, CheckerType> {
  447   typedef base_checker<TreeType, CheckerType> super_type;
  448   typedef multi_checker<TreeType, CheckerType> self_type;
  449 
  450  public:
  451   typedef typename super_type::iterator iterator;
  452   typedef typename super_type::value_type value_type;
  453 
  454  public:
  455   // Default constructor.
  456   multi_checker()
  457       : super_type() {
  458   }
  459   // Copy constructor.
  460   multi_checker(const self_type &x)
  461       : super_type(x) {
  462   }
  463   // Range constructor.
  464   template <class InputIterator>
  465   multi_checker(InputIterator b, InputIterator e)
  466       : super_type(b, e) {
  467   }
  468 
  469   // Insertion routines.
  470   iterator insert(const value_type &x) {
  471     int size = this->tree_.size();
  472     typename CheckerType::iterator checker_res = this->checker_.insert(x);
  473     iterator tree_res = this->tree_.insert(x);
  474     EXPECT_EQ(*tree_res, *checker_res);
  475     EXPECT_EQ(this->tree_.size(), this->checker_.size());
  476     EXPECT_EQ(this->tree_.size(), size + 1);
  477     return tree_res;
  478   }
  479   iterator insert(iterator position, const value_type &x) {
  480     int size = this->tree_.size();
  481     typename CheckerType::iterator checker_res = this->checker_.insert(x);
  482     iterator tree_res = this->tree_.insert(position, x);
  483     EXPECT_EQ(*tree_res, *checker_res);
  484     EXPECT_EQ(this->tree_.size(), this->checker_.size());
  485     EXPECT_EQ(this->tree_.size(), size + 1);
  486     return tree_res;
  487   }
  488   template <typename InputIterator>
  489   void insert(InputIterator b, InputIterator e) {
  490     for (; b != e; ++b) {
  491       insert(*b);
  492     }
  493   }
  494 };
  495 
  496 char* GenerateDigits(char buf[16], int val, int maxval) {
  497   EXPECT_LE(val, maxval);
  498   int p = 15;
  499   buf[p--] = 0;
  500   while (maxval > 0) {
  501     buf[p--] = '0' + (val % 10);
  502     val /= 10;
  503     maxval /= 10;
  504   }
  505   return buf + p + 1;
  506 }
  507 
  508 template <typename K>
  509 struct Generator {
  510   int maxval;
  511   Generator(int m)
  512       : maxval(m) {
  513   }
  514   K operator()(int i) const {
  515     EXPECT_LE(i, maxval);
  516     return i;
  517   }
  518 };
  519 
  520 template <>
  521 struct Generator<std::string> {
  522   int maxval;
  523   Generator(int m)
  524       : maxval(m) {
  525   }
  526   std::string operator()(int i) const {
  527     char buf[16];
  528     return GenerateDigits(buf, i, maxval);
  529   }
  530 };
  531 
  532 template <typename T, typename U>
  533 struct Generator<std::pair<T, U> > {
  534   Generator<typename std::remove_const<T>::type> tgen;
  535   Generator<typename std::remove_const<U>::type> ugen;
  536 
  537   Generator(int m)
  538       : tgen(m),
  539         ugen(m) {
  540   }
  541   std::pair<T, U> operator()(int i) const {
  542     return std::make_pair(tgen(i), ugen(i));
  543   }
  544 };
  545 
  546 // Generate values for our tests and benchmarks. Value range is [0, maxval].
  547 const std::vector<int>& GenerateNumbers(int n, int maxval) {
  548   static std::vector<int> values;
  549   static std::set<int> unique_values;
  550 
  551   if (values.size() < n) {
  552 
  553     for (int i = values.size(); i < n; i++) {
  554       int value;
  555       do {
  556         value = rand() % (maxval + 1);
  557       } while (unique_values.find(value) != unique_values.end());
  558 
  559       values.push_back(value);
  560       unique_values.insert(value);
  561     }
  562   }
  563 
  564   return values;
  565 }
  566 
  567 // Generates values in the range
  568 // [0, 4 * min(FLAGS_benchmark_values, FLAGS_test_values)]
  569 template <typename V>
  570 std::vector<V> GenerateValues(int n) {
  571   int two_times_max = 2 * std::max(FLAGS_benchmark_values, FLAGS_test_values);
  572   int four_times_max = 2 * two_times_max;
  573   EXPECT_LE(n, two_times_max);
  574   const std::vector<int> &nums = GenerateNumbers(n, four_times_max);
  575   Generator<V> gen(four_times_max);
  576   std::vector<V> vec;
  577 
  578   for (int i = 0; i < n; i++) {
  579     vec.push_back(gen(nums[i]));
  580   }
  581 
  582   return vec;
  583 }
  584 
  585 template <typename T, typename V>
  586 void DoTest(const char *name, T *b, const std::vector<V> &values) {
  587   typename KeyOfValue<typename T::key_type, V>::type key_of_value;
  588 
  589   T &mutable_b = *b;
  590   const T &const_b = *b;
  591 
  592   // Test insert.
  593   for (int i = 0; i < values.size(); ++i) {
  594     mutable_b.insert(values[i]);
  595     mutable_b.value_check(values[i]);
  596   }
  597   assert(mutable_b.size() == values.size());
  598 
  599   const_b.verify();
  600   printf("    %s fullness=%0.2f  overhead=%0.2f  bytes-per-value=%0.2f\n",
  601          name, const_b.fullness(), const_b.overhead(),
  602          double(const_b.bytes_used()) / const_b.size());
  603 
  604   // Test copy constructor.
  605   T b_copy(const_b);
  606   EXPECT_EQ(b_copy.size(), const_b.size());
  607   EXPECT_LE(b_copy.height(), const_b.height());
  608   EXPECT_LE(b_copy.internal_nodes(), const_b.internal_nodes());
  609   EXPECT_LE(b_copy.leaf_nodes(), const_b.leaf_nodes());
  610   for (int i = 0; i < values.size(); ++i) {
  611     EXPECT_EQ(*b_copy.find(key_of_value(values[i])), values[i]);
  612   }
  613 
  614   // Test range constructor.
  615   T b_range(const_b.begin(), const_b.end());
  616   EXPECT_EQ(b_range.size(), const_b.size());
  617   EXPECT_LE(b_range.height(), const_b.height());
  618   EXPECT_LE(b_range.internal_nodes(), const_b.internal_nodes());
  619   EXPECT_LE(b_range.leaf_nodes(), const_b.leaf_nodes());
  620   for (int i = 0; i < values.size(); ++i) {
  621     EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]);
  622   }
  623 
  624   // Test range insertion for values that already exist.
  625   b_range.insert(b_copy.begin(), b_copy.end());
  626   b_range.verify();
  627 
  628   // Test range insertion for new values.
  629   b_range.clear();
  630   b_range.insert(b_copy.begin(), b_copy.end());
  631   EXPECT_EQ(b_range.size(), b_copy.size());
  632   EXPECT_EQ(b_range.height(), b_copy.height());
  633   EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes());
  634   EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes());
  635   for (int i = 0; i < values.size(); ++i) {
  636     EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]);
  637   }
  638 
  639   // Test assignment to self. Nothing should change.
  640   b_range.operator=(b_range);
  641   EXPECT_EQ(b_range.size(), b_copy.size());
  642   EXPECT_EQ(b_range.height(), b_copy.height());
  643   EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes());
  644   EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes());
  645 
  646   // Test assignment of new values.
  647   b_range.clear();
  648   b_range = b_copy;
  649   EXPECT_EQ(b_range.size(), b_copy.size());
  650   EXPECT_EQ(b_range.height(), b_copy.height());
  651   EXPECT_EQ(b_range.internal_nodes(), b_copy.internal_nodes());
  652   EXPECT_EQ(b_range.leaf_nodes(), b_copy.leaf_nodes());
  653 
  654   // Test swap.
  655   b_range.clear();
  656   b_range.swap(b_copy);
  657   EXPECT_EQ(b_copy.size(), 0);
  658   EXPECT_EQ(b_range.size(), const_b.size());
  659   for (int i = 0; i < values.size(); ++i) {
  660     EXPECT_EQ(*b_range.find(key_of_value(values[i])), values[i]);
  661   }
  662   b_range.swap(b_copy);
  663 
  664   // Test erase via values.
  665   for (int i = 0; i < values.size(); ++i) {
  666     mutable_b.erase(key_of_value(values[i]));
  667     // Erasing a non-existent key should have no effect.
  668     EXPECT_EQ(mutable_b.erase(key_of_value(values[i])), 0);
  669   }
  670 
  671   const_b.verify();
  672   EXPECT_EQ(const_b.internal_nodes(), 0);
  673   EXPECT_EQ(const_b.leaf_nodes(), 0);
  674   EXPECT_EQ(const_b.size(), 0);
  675 
  676   // Test erase via iterators.
  677   mutable_b = b_copy;
  678   for (int i = 0; i < values.size(); ++i) {
  679     mutable_b.erase(mutable_b.find(key_of_value(values[i])));
  680   }
  681 
  682   const_b.verify();
  683   EXPECT_EQ(const_b.internal_nodes(), 0);
  684   EXPECT_EQ(const_b.leaf_nodes(), 0);
  685   EXPECT_EQ(const_b.size(), 0);
  686 
  687   // Test insert with hint.
  688   for (int i = 0; i < values.size(); i++) {
  689     mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]);
  690   }
  691 
  692   const_b.verify();
  693 
  694   // Test dumping of the btree to an ostream. There should be 1 line for each
  695   // value.
  696   std::stringstream strm;
  697   strm << mutable_b.tree();
  698   EXPECT_EQ(mutable_b.size(), strcount(strm.str(), '\n'));
  699 
  700   // Test range erase.
  701   mutable_b.erase(mutable_b.begin(), mutable_b.end());
  702   EXPECT_EQ(mutable_b.size(), 0);
  703   const_b.verify();
  704 
  705   // First half.
  706   mutable_b = b_copy;
  707   typename T::iterator mutable_iter_end = mutable_b.begin();
  708   for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_end;
  709   mutable_b.erase(mutable_b.begin(), mutable_iter_end);
  710   EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2);
  711   const_b.verify();
  712 
  713   // Second half.
  714   mutable_b = b_copy;
  715   typename T::iterator mutable_iter_begin = mutable_b.begin();
  716   for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin;
  717   mutable_b.erase(mutable_iter_begin, mutable_b.end());
  718   EXPECT_EQ(mutable_b.size(), values.size() / 2);
  719   const_b.verify();
  720 
  721   // Second quarter.
  722   mutable_b = b_copy;
  723   mutable_iter_begin = mutable_b.begin();
  724   for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin;
  725   mutable_iter_end = mutable_iter_begin;
  726   for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_end;
  727   mutable_b.erase(mutable_iter_begin, mutable_iter_end);
  728   EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4);
  729   const_b.verify();
  730 
  731   mutable_b.clear();
  732 }
  733 
  734 template <typename T>
  735 void ConstTest() {
  736   typedef typename T::value_type value_type;
  737   typename KeyOfValue<typename T::key_type, value_type>::type key_of_value;
  738 
  739   T mutable_b;
  740   const T &const_b = mutable_b;
  741 
  742   // Insert a single value into the container and test looking it up.
  743   value_type value = Generator<value_type>(2)(2);
  744   mutable_b.insert(value);
  745   EXPECT_TRUE(mutable_b.find(key_of_value(value)) != const_b.end());
  746   EXPECT_TRUE(const_b.find(key_of_value(value)) != mutable_b.end());
  747   EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value);
  748   EXPECT_TRUE(const_b.upper_bound(key_of_value(value)) == const_b.end());
  749   EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value);
  750 
  751   // We can only create a non-const iterator from a non-const container.
  752   typename T::iterator mutable_iter(mutable_b.begin());
  753   EXPECT_TRUE(mutable_iter == const_b.begin());
  754   EXPECT_TRUE(mutable_iter != const_b.end());
  755   EXPECT_TRUE(const_b.begin() == mutable_iter);
  756   EXPECT_TRUE(const_b.end() != mutable_iter);
  757   typename T::reverse_iterator mutable_riter(mutable_b.rbegin());
  758   EXPECT_TRUE(mutable_riter == const_b.rbegin());
  759   EXPECT_TRUE(mutable_riter != const_b.rend());
  760   EXPECT_TRUE(const_b.rbegin() == mutable_riter);
  761   EXPECT_TRUE(const_b.rend() != mutable_riter);
  762 
  763   // We can create a const iterator from a non-const iterator.
  764   typename T::const_iterator const_iter(mutable_iter);
  765   EXPECT_TRUE(const_iter == mutable_b.begin());
  766   EXPECT_TRUE(const_iter != mutable_b.end());
  767   EXPECT_TRUE(mutable_b.begin() == const_iter);
  768   EXPECT_TRUE(mutable_b.end() != const_iter);
  769   typename T::const_reverse_iterator const_riter(mutable_riter);
  770   EXPECT_EQ(const_riter, mutable_b.rbegin());
  771   EXPECT_TRUE(const_riter != mutable_b.rend());
  772   EXPECT_EQ(mutable_b.rbegin(), const_riter);
  773   EXPECT_TRUE(mutable_b.rend() != const_riter);
  774 
  775   // Make sure various methods can be invoked on a const container.
  776   const_b.verify();
  777   EXPECT_FALSE(const_b.empty());
  778   EXPECT_EQ(const_b.size(), 1);
  779   EXPECT_GT(const_b.max_size(), 0);
  780   EXPECT_EQ(const_b.height(), 1);
  781   EXPECT_EQ(const_b.count(key_of_value(value)), 1);
  782   EXPECT_EQ(const_b.internal_nodes(), 0);
  783   EXPECT_EQ(const_b.leaf_nodes(), 1);
  784   EXPECT_EQ(const_b.nodes(), 1);
  785   EXPECT_GT(const_b.bytes_used(), 0);
  786   EXPECT_GT(const_b.fullness(), 0);
  787   EXPECT_GT(const_b.overhead(), 0);
  788 }
  789 
  790 template <typename T, typename C>
  791 void BtreeTest() {
  792   ConstTest<T>();
  793 
  794   typedef typename std::remove_const<typename T::value_type>::type V;
  795   std::vector<V> random_values = GenerateValues<V>(FLAGS_test_values);
  796 
  797   unique_checker<T, C> container;
  798 
  799   // Test key insertion/deletion in sorted order.
  800   std::vector<V> sorted_values(random_values);
  801   sort(sorted_values.begin(), sorted_values.end());
  802   DoTest("sorted:    ", &container, sorted_values);
  803 
  804   // Test key insertion/deletion in reverse sorted order.
  805   reverse(sorted_values.begin(), sorted_values.end());
  806   DoTest("rsorted:   ", &container, sorted_values);
  807 
  808   // Test key insertion/deletion in random order.
  809   DoTest("random:    ", &container, random_values);
  810 }
  811 
  812 template <typename T, typename C>
  813 void BtreeMultiTest() {
  814   ConstTest<T>();
  815 
  816   typedef typename std::remove_const<typename T::value_type>::type V;
  817   const std::vector<V>& random_values = GenerateValues<V>(FLAGS_test_values);
  818 
  819   multi_checker<T, C> container;
  820 
  821   // Test keys in sorted order.
  822   std::vector<V> sorted_values(random_values);
  823   sort(sorted_values.begin(), sorted_values.end());
  824   DoTest("sorted:    ", &container, sorted_values);
  825 
  826   // Test keys in reverse sorted order.
  827   reverse(sorted_values.begin(), sorted_values.end());
  828   DoTest("rsorted:   ", &container, sorted_values);
  829 
  830   // Test keys in random order.
  831   DoTest("random:    ", &container, random_values);
  832 
  833   // Test keys in random order w/ duplicates.
  834   std::vector<V> duplicate_values(random_values);
  835   duplicate_values.insert(
  836       duplicate_values.end(), random_values.begin(), random_values.end());
  837   DoTest("duplicates:", &container, duplicate_values);
  838 
  839   // Test all identical keys.
  840   std::vector<V> identical_values(100);
  841   fill(identical_values.begin(), identical_values.end(), Generator<V>(2)(2));
  842   DoTest("identical: ", &container, identical_values);
  843 }
  844 
  845 template <typename T, typename Alloc = std::allocator<T> >
  846 class TestAllocator : public Alloc {
  847  public:
  848   typedef typename Alloc::pointer pointer;
  849   typedef typename Alloc::size_type size_type;
  850 
  851   TestAllocator() : bytes_used_(NULL) { }
  852   TestAllocator(int64_t *bytes_used) : bytes_used_(bytes_used) { }
  853 
  854   // Constructor used for rebinding
  855   template <class U>
  856   TestAllocator(const TestAllocator<U>& x)
  857       : Alloc(x),
  858         bytes_used_(x.bytes_used()) {
  859   }
  860 
  861   pointer allocate(size_type n, std::allocator<void>::const_pointer hint = 0) {
  862     EXPECT_TRUE(bytes_used_ != NULL);
  863     *bytes_used_ += n * sizeof(T);
  864     return Alloc::allocate(n, hint);
  865   }
  866 
  867   void deallocate(pointer p, size_type n) {
  868     Alloc::deallocate(p, n);
  869     EXPECT_TRUE(bytes_used_ != NULL);
  870     *bytes_used_ -= n * sizeof(T);
  871   }
  872 
  873   // Rebind allows an allocator<T> to be used for a different type
  874   template <class U> struct rebind {
  875     typedef TestAllocator<U, typename Alloc::template rebind<U>::other> other;
  876   };
  877 
  878   int64_t* bytes_used() const { return bytes_used_; }
  879 
  880  private:
  881   int64_t *bytes_used_;
  882 };
  883 
  884 template <typename T>
  885 void BtreeAllocatorTest() {
  886   typedef typename T::value_type value_type;
  887 
  888   int64_t alloc1 = 0;
  889   int64_t alloc2 = 0;
  890   T b1(typename T::key_compare(), &alloc1);
  891   T b2(typename T::key_compare(), &alloc2);
  892 
  893   // This should swap the allocators!
  894   swap(b1, b2);
  895 
  896   for (int i = 0; i < 1000; i++) {
  897     b1.insert(Generator<value_type>(1000)(i));
  898   }
  899 
  900   // We should have allocated out of alloc2!
  901   EXPECT_LE(b1.bytes_used(), alloc2 + sizeof(b1));
  902   EXPECT_GT(alloc2, alloc1);
  903 }
  904 
  905 template <typename T>
  906 void BtreeMapTest() {
  907   typedef typename T::value_type value_type;
  908   typedef typename T::mapped_type mapped_type;
  909 
  910   mapped_type m = Generator<mapped_type>(0)(0);
  911   (void) m;
  912 
  913   T b;
  914 
  915   // Verify we can insert using operator[].
  916   for (int i = 0; i < 1000; i++) {
  917     value_type v = Generator<value_type>(1000)(i);
  918     b[v.first] = v.second;
  919   }
  920   EXPECT_EQ(b.size(), 1000);
  921 
  922   // Test whether we can use the "->" operator on iterators and
  923   // reverse_iterators. This stresses the btree_map_params::pair_pointer
  924   // mechanism.
  925   EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first);
  926   EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second);
  927   EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first);
  928   EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second);
  929 }
  930 
  931 template <typename T>
  932 void BtreeMultiMapTest() {
  933   typedef typename T::mapped_type mapped_type;
  934   mapped_type m = Generator<mapped_type>(0)(0);
  935   (void) m;
  936 }
  937 
  938 } // namespace btree
  939 
  940 #endif  // UTIL_BTREE_BTREE_TEST_H__