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