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