ceph/src/boost/libs/unordered/test/unordered/erase_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/equivalent.hpp"
  18 #include "../helpers/helpers.hpp"
  19 #include "../helpers/invariants.hpp"
  20 #include <vector>
  21 #include <cstdlib>
  22
  23 namespace erase_tests {
  24
  25   test::seed_t initialize_seed(85638);
  26
  27   template <class Container>
  28   void erase_tests1(Container*, test::random_generator generator)
  29   {
  30     typedef typename Container::iterator iterator;
  31     typedef typename Container::const_iterator c_iterator;
  32
  33     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase by key.\n";
  34     {
  35       test::check_instances check_;
  36
  37       test::random_values<Container> v(1000, generator);
  38       Container x(v.begin(), v.end());
  39       int iterations = 0;
  40       for (typename test::random_values<Container>::iterator it = v.begin();
  41            it != v.end(); ++it) {
  42         std::size_t count = x.count(test::get_key<Container>(*it));
  43         std::size_t old_size = x.size();
  44         BOOST_TEST(count == x.erase(test::get_key<Container>(*it)));
  45         BOOST_TEST(x.size() == old_size - count);
  46         BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0);
  47         BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
  48         if (++iterations % 20 == 0)
  49           test::check_equivalent_keys(x);
  50       }
  51     }
  52
  53     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(begin()).\n";
  54     {
  55       test::check_instances check_;
  56
  57       test::random_values<Container> v(1000, generator);
  58       Container x(v.begin(), v.end());
  59       std::size_t size = x.size();
  60       int iterations = 0;
  61       while (size > 0 && !x.empty()) {
  62         typename Container::key_type key = test::get_key<Container>(*x.begin());
  63         std::size_t count = x.count(key);
  64         iterator pos = x.erase(x.begin());
  65         --size;
  66         BOOST_TEST(pos == x.begin());
  67         BOOST_TEST(x.count(key) == count - 1);
  68         BOOST_TEST(x.size() == size);
  69         if (++iterations % 20 == 0)
  70           test::check_equivalent_keys(x);
  71       }
  72       BOOST_TEST(x.empty());
  73     }
  74
  75     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random position).\n";
  76     {
  77       test::check_instances check_;
  78
  79       test::random_values<Container> v(1000, generator);
  80       Container x(v.begin(), v.end());
  81       std::size_t size = x.size();
  82       int iterations = 0;
  83       while (size > 0 && !x.empty()) {
  84         std::size_t index = test::random_value(x.size());
  85         c_iterator prev, pos, next;
  86         if (index == 0) {
  87           prev = pos = x.begin();
  88         } else {
  89           prev = test::next(x.begin(), index - 1);
  90           pos = test::next(prev);
  91         }
  92         next = test::next(pos);
  93         typename Container::key_type key = test::get_key<Container>(*pos);
  94         std::size_t count = x.count(key);
  95         BOOST_TEST(count > 0);
  96         BOOST_TEST(next == x.erase(pos));
  97         --size;
  98         if (size > 0)
  99           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
 100         BOOST_TEST(x.count(key) == count - 1);
 101         if (x.count(key) != count - 1) {
 102           BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
 103                                          << std::endl;
 104         }
 105         BOOST_TEST(x.size() == size);
 106         if (++iterations % 20 == 0)
 107           test::check_equivalent_keys(x);
 108       }
 109       BOOST_TEST(x.empty());
 110     }
 111
 112     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(ranges).\n";
 113     {
 114       test::check_instances check_;
 115
 116       test::random_values<Container> v(500, generator);
 117       Container x(v.begin(), v.end());
 118
 119       std::size_t size = x.size();
 120
 121       // I'm actually stretching it a little here, as the standard says it
 122       // returns 'the iterator immediately following the erase elements'
 123       // and if nothing is erased, then there's nothing to follow. But I
 124       // think this is the only sensible option...
 125       BOOST_TEST(x.erase(x.end(), x.end()) == x.end());
 126       BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin());
 127       BOOST_TEST(x.size() == size);
 128       test::check_equivalent_keys(x);
 129
 130       BOOST_TEST(x.erase(x.begin(), x.end()) == x.end());
 131       BOOST_TEST(x.empty());
 132       BOOST_TEST(x.begin() == x.end());
 133       test::check_equivalent_keys(x);
 134
 135       BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
 136       test::check_equivalent_keys(x);
 137     }
 138
 139     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "erase(random ranges).\n";
 140     {
 141       test::check_instances check_;
 142       Container x;
 143
 144       for (int i = 0; i < 100; ++i) {
 145         test::random_values<Container> v(1000, generator);
 146         x.insert(v.begin(), v.end());
 147
 148         // Note that erase only invalidates the erased iterators.
 149         std::vector<c_iterator> iterators;
 150         for (c_iterator it = x.cbegin(); it != x.cend(); ++it) {
 151           iterators.push_back(it);
 152         }
 153         iterators.push_back(x.cend());
 154
 155         while (iterators.size() > 1) {
 156           std::size_t start = test::random_value(iterators.size());
 157           std::size_t length = test::random_value(iterators.size() - start);
 158           x.erase(iterators[start], iterators[start + length]);
 159           iterators.erase(test::next(iterators.begin(), start),
 160             test::next(iterators.begin(), start + length));
 161
 162           BOOST_TEST(x.size() == iterators.size() - 1);
 163           typename std::vector<c_iterator>::const_iterator i2 =
 164             iterators.begin();
 165           for (c_iterator i1 = x.cbegin(); i1 != x.cend(); ++i1) {
 166             BOOST_TEST(i1 == *i2);
 167             ++i2;
 168           }
 169           BOOST_TEST(x.cend() == *i2);
 170
 171           test::check_equivalent_keys(x);
 172         }
 173         BOOST_TEST(x.empty());
 174       }
 175     }
 176
 177     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(begin()).\n";
 178     {
 179       test::check_instances check_;
 180
 181       test::random_values<Container> v(1000, generator);
 182       Container x(v.begin(), v.end());
 183       std::size_t size = x.size();
 184       int iterations = 0;
 185       while (size > 0 && !x.empty()) {
 186         typename Container::key_type key = test::get_key<Container>(*x.begin());
 187         std::size_t count = x.count(key);
 188         x.quick_erase(x.begin());
 189         --size;
 190         BOOST_TEST(x.count(key) == count - 1);
 191         BOOST_TEST(x.size() == size);
 192         if (++iterations % 20 == 0)
 193           test::check_equivalent_keys(x);
 194       }
 195       BOOST_TEST(x.empty());
 196     }
 197
 198     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "quick_erase(random position).\n";
 199     {
 200       test::check_instances check_;
 201
 202       test::random_values<Container> v(1000, generator);
 203       Container x(v.begin(), v.end());
 204       std::size_t size = x.size();
 205       int iterations = 0;
 206       while (size > 0 && !x.empty()) {
 207         std::size_t index = test::random_value(x.size());
 208         typename Container::const_iterator prev, pos, next;
 209         if (index == 0) {
 210           prev = pos = x.begin();
 211         } else {
 212           prev = test::next(x.begin(), index - 1);
 213           pos = test::next(prev);
 214         }
 215         next = test::next(pos);
 216         typename Container::key_type key = test::get_key<Container>(*pos);
 217         std::size_t count = x.count(key);
 218         BOOST_TEST(count > 0);
 219         x.quick_erase(pos);
 220         --size;
 221         if (size > 0)
 222           BOOST_TEST(index == 0 ? next == x.begin() : next == test::next(prev));
 223         BOOST_TEST(x.count(key) == count - 1);
 224         if (x.count(key) != count - 1) {
 225           BOOST_LIGHTWEIGHT_TEST_OSTREAM << count << " => " << x.count(key)
 226                                          << std::endl;
 227         }
 228         BOOST_TEST(x.size() == size);
 229         if (++iterations % 20 == 0)
 230           test::check_equivalent_keys(x);
 231       }
 232       BOOST_TEST(x.empty());
 233     }
 234
 235     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "clear().\n";
 236     {
 237       test::check_instances check_;
 238
 239       test::random_values<Container> v(500, generator);
 240       Container x(v.begin(), v.end());
 241       x.clear();
 242       BOOST_TEST(x.empty());
 243       BOOST_TEST(x.begin() == x.end());
 244     }
 245
 246     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n";
 247   }
 248
 249   boost::unordered_set<test::object, test::hash, test::equal_to,
 250     test::allocator1<test::object> >* test_set;
 251   boost::unordered_multiset<test::object, test::hash, test::equal_to,
 252     test::allocator2<test::object> >* test_multiset;
 253   boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 254     test::allocator1<test::object> >* test_map;
 255   boost::unordered_multimap<test::object, test::object, test::hash,
 256     test::equal_to, test::allocator2<test::object> >* test_multimap;
 257
 258   using test::default_generator;
 259   using test::generate_collisions;
 260   using test::limited_range;
 261
 262   UNORDERED_TEST(
 263     erase_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
 264                     (default_generator)(generate_collisions)(limited_range)))
 265 }
 266
 267 RUN_TESTS()