ceph/src/boost/libs/unordered/test/unordered/find_tests.cpp

   1
   2 // Copyright 2006-2009 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_set.hpp>
   9 #include <boost/unordered_map.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include "../helpers/test.hpp"
  14 #include "../objects/test.hpp"
  15 #include "../helpers/random_values.hpp"
  16 #include "../helpers/tracker.hpp"
  17 #include "../helpers/helpers.hpp"
  18
  19 namespace find_tests {
  20
  21   test::seed_t initialize_seed(78937);
  22
  23   template <class X> void find_tests1(X*, test::random_generator generator)
  24   {
  25     typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
  26
  27     {
  28       test::check_instances check_;
  29
  30       test::random_values<X> v(500, generator);
  31       X x(v.begin(), v.end());
  32       X const& x_const = x;
  33       test::ordered<X> tracker = test::create_ordered(x);
  34       tracker.insert_range(v.begin(), v.end());
  35
  36       for (BOOST_DEDUCED_TYPENAME test::ordered<X>::const_iterator it1 =
  37              tracker.begin();
  38            it1 != tracker.end(); ++it1) {
  39         BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it1);
  40         BOOST_DEDUCED_TYPENAME X::const_iterator const_pos = x_const.find(key);
  41         iterator pos = x.find(key);
  42         BOOST_TEST(const_pos != x_const.end());
  43         BOOST_TEST(const_pos != x_const.end() &&
  44                    x_const.key_eq()(key, test::get_key<X>(*const_pos)));
  45         BOOST_TEST(pos != x.end());
  46         BOOST_TEST(pos != x.end() && x.key_eq()(key, test::get_key<X>(*pos)));
  47
  48         BOOST_TEST(x.count(key) == tracker.count(key));
  49
  50         test::compare_pairs(x.equal_range(key), tracker.equal_range(key),
  51           (BOOST_DEDUCED_TYPENAME X::value_type*)0);
  52         test::compare_pairs(x_const.equal_range(key), tracker.equal_range(key),
  53           (BOOST_DEDUCED_TYPENAME X::value_type*)0);
  54       }
  55
  56       test::random_values<X> v2(500, generator);
  57       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::const_iterator it2 =
  58              v2.begin();
  59            it2 != v2.end(); ++it2) {
  60         BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it2);
  61         if (tracker.find(test::get_key<X>(key)) == tracker.end()) {
  62           BOOST_TEST(x.find(key) == x.end());
  63           BOOST_TEST(x_const.find(key) == x_const.end());
  64           BOOST_TEST(x.count(key) == 0);
  65           std::pair<iterator, iterator> range = x.equal_range(key);
  66           BOOST_TEST(range.first == range.second);
  67         }
  68       }
  69     }
  70
  71     {
  72       test::check_instances check_;
  73
  74       X x;
  75
  76       test::random_values<X> v2(5, generator);
  77       for (BOOST_DEDUCED_TYPENAME test::random_values<X>::const_iterator it3 =
  78              v2.begin();
  79            it3 != v2.end(); ++it3) {
  80         BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it3);
  81         BOOST_TEST(x.find(key) == x.end());
  82         BOOST_TEST(x.count(key) == 0);
  83         std::pair<iterator, iterator> range = x.equal_range(key);
  84         BOOST_TEST(range.first == range.second);
  85       }
  86     }
  87   }
  88
  89   struct compatible_key
  90   {
  91     test::object o_;
  92
  93     compatible_key(test::object const& o) : o_(o) {}
  94   };
  95
  96   struct compatible_hash
  97   {
  98     test::hash hash_;
  99
 100     std::size_t operator()(compatible_key const& k) const
 101     {
 102       return hash_(k.o_);
 103     }
 104   };
 105
 106   struct compatible_predicate
 107   {
 108     test::equal_to equal_;
 109
 110     bool operator()(compatible_key const& k1, compatible_key const& k2) const
 111     {
 112       return equal_(k1.o_, k2.o_);
 113     }
 114   };
 115
 116   template <class X>
 117   void find_compatible_keys_test(X*, test::random_generator generator)
 118   {
 119     typedef BOOST_DEDUCED_TYPENAME test::random_values<X>::iterator
 120       value_iterator;
 121     test::random_values<X> v(500, generator);
 122     X x(v.begin(), v.end());
 123
 124     compatible_hash h;
 125     compatible_predicate eq;
 126
 127     for (value_iterator it = v.begin(), end = v.end(); it != end; ++it) {
 128       BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it);
 129       BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq));
 130     }
 131
 132     test::random_values<X> v2(20, generator);
 133
 134     for (value_iterator it = v2.begin(), end = v2.end(); it != end; ++it) {
 135       BOOST_DEDUCED_TYPENAME X::key_type key = test::get_key<X>(*it);
 136       BOOST_TEST(x.find(key) == x.find(compatible_key(key), h, eq));
 137     }
 138   }
 139
 140   boost::unordered_set<test::object, test::hash, test::equal_to,
 141     test::allocator2<test::object> >* test_set;
 142   boost::unordered_multiset<test::object, test::hash, test::equal_to,
 143     test::allocator1<test::object> >* test_multiset;
 144   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 145     test::allocator2<test::object> >* test_map;
 146   boost::unordered_multimap<test::object, test::object, test::hash,
 147     test::equal_to, test::allocator1<test::object> >* test_multimap;
 148
 149   using test::default_generator;
 150   using test::generate_collisions;
 151   using test::limited_range;
 152
 153   UNORDERED_TEST(
 154     find_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
 155                    (default_generator)(generate_collisions)(limited_range)))
 156   UNORDERED_TEST(find_compatible_keys_test,
 157     ((test_set)(test_multiset)(test_map)(test_multimap))(
 158       (default_generator)(generate_collisions)(limited_range)))
 159 }
 160
 161 RUN_TESTS()