ceph/src/boost/libs/intrusive/test/unordered_test.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2015-2015.
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 #include <boost/intrusive/pointer_traits.hpp>
  13 #include <boost/intrusive/detail/iterator.hpp>
  14 #include "common_functors.hpp"
  15 #include <vector>
  16 #include <algorithm> //std::sort
  17 #include <set>
  18 #include <boost/detail/lightweight_test.hpp>
  19
  20 #include "test_macros.hpp"
  21 #include "test_container.hpp"
  22 #include "unordered_test_common.hpp"
  23
  24 namespace boost{
  25 namespace intrusive{
  26 namespace test{
  27
  28 static const std::size_t BucketSize = 8;
  29
  30 template<class ContainerDefiner>
  31 struct test_unordered
  32 {
  33    typedef typename ContainerDefiner::value_cont_type value_cont_type;
  34
  35    static void test_all(value_cont_type& values);
  36    private:
  37    static void test_sort(value_cont_type& values);
  38    static void test_insert(value_cont_type& values, detail::true_);
  39    static void test_insert(value_cont_type& values, detail::false_);
  40    static void test_swap(value_cont_type& values);
  41    static void test_rehash(value_cont_type& values, detail::true_);
  42    static void test_rehash(value_cont_type& values, detail::false_);
  43    static void test_find(value_cont_type& values);
  44    static void test_impl();
  45    static void test_clone(value_cont_type& values);
  46 };
  47
  48 template<class ContainerDefiner>
  49 void test_unordered<ContainerDefiner>::test_all (value_cont_type& values)
  50 {
  51    typedef typename ContainerDefiner::template container
  52       <>::type unordered_type;
  53    typedef typename unordered_type::bucket_traits bucket_traits;
  54    {
  55       typename unordered_type::bucket_type buckets [BucketSize];
  56       unordered_type testset
  57          (bucket_traits(pointer_traits<typename unordered_type::bucket_ptr>::
  58             pointer_to(buckets[0]), BucketSize));
  59       testset.insert(values.begin(), values.end());
  60       test::test_container(testset);
  61       testset.clear();
  62       testset.insert(values.begin(), values.end());
  63       test::test_common_unordered_and_associative_container(testset, values);
  64       testset.clear();
  65       testset.insert(values.begin(), values.end());
  66       test::test_unordered_associative_container(testset, values);
  67       testset.clear();
  68       testset.insert(values.begin(), values.end());
  69       typedef detail::bool_<boost::intrusive::test::is_multikey_true
  70          <unordered_type>::value> select_t;
  71       test::test_maybe_unique_container(testset, values, select_t());
  72    }
  73    {
  74       value_cont_type vals(BucketSize);
  75       for (int i = 0; i < (int)BucketSize; ++i)
  76          (&vals[i])->value_ = i;
  77       typename unordered_type::bucket_type buckets [BucketSize];
  78       unordered_type testset(bucket_traits(
  79          pointer_traits<typename unordered_type::bucket_ptr>::
  80             pointer_to(buckets[0]), BucketSize));
  81       testset.insert(vals.begin(), vals.end());
  82       test::test_iterator_forward(testset);
  83    }
  84    test_sort(values);
  85    test_insert(values, detail::bool_<boost::intrusive::test::is_multikey_true<unordered_type>::value>());
  86    test_swap(values);
  87    test_rehash(values, detail::bool_<unordered_type::incremental>());
  88    test_find(values);
  89    test_impl();
  90    test_clone(values);
  91 }
  92
  93 //test case due to an error in tree implementation:
  94 template<class ContainerDefiner>
  95 void test_unordered<ContainerDefiner>::test_impl()
  96 {
  97    typedef typename ContainerDefiner::template container
  98       <>::type unordered_type;
  99    typedef typename unordered_type::bucket_traits bucket_traits;
 100
 101    value_cont_type values (5);
 102    for (int i = 0; i < 5; ++i)
 103       values[i].value_ = i;
 104
 105    typename unordered_type::bucket_type buckets [BucketSize];
 106    unordered_type testset(bucket_traits(
 107       pointer_traits<typename unordered_type::bucket_ptr>::
 108          pointer_to(buckets[0]), BucketSize));
 109
 110    for (int i = 0; i < 5; ++i)
 111       testset.insert (values[i]);
 112
 113    testset.erase (testset.iterator_to (values[0]));
 114    testset.erase (testset.iterator_to (values[1]));
 115    testset.insert (values[1]);
 116
 117    testset.erase (testset.iterator_to (values[2]));
 118    testset.erase (testset.iterator_to (values[3]));
 119 }
 120
 121 //test: constructor, iterator, clear, reverse_iterator, front, back, size:
 122 template<class ContainerDefiner>
 123 void test_unordered<ContainerDefiner>::test_sort(value_cont_type& values)
 124 {
 125    typedef typename ContainerDefiner::template container
 126       <>::type unordered_type;
 127    typedef typename unordered_type::bucket_traits bucket_traits;
 128
 129    typename unordered_type::bucket_type buckets [BucketSize];
 130    unordered_type testset1
 131       (values.begin(), values.end(), bucket_traits
 132          (pointer_traits<typename unordered_type::bucket_ptr>::
 133             pointer_to(buckets[0]), BucketSize));
 134
 135    if(unordered_type::incremental){
 136       {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 137          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 138    }
 139    else{
 140       {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 141          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 142    }
 143    testset1.clear();
 144    BOOST_TEST (testset1.empty());
 145 }
 146
 147 //test: insert, const_iterator, const_reverse_iterator, erase, iterator_to:
 148 template<class ContainerDefiner>
 149 void test_unordered<ContainerDefiner>::test_insert(value_cont_type& values, detail::false_) //not multikey
 150 {
 151
 152    typedef typename ContainerDefiner::template container
 153       <>::type unordered_set_type;
 154    typedef typename unordered_set_type::bucket_traits bucket_traits;
 155    typedef typename unordered_set_type::key_of_value  key_of_value;
 156
 157    typename unordered_set_type::bucket_type buckets [BucketSize];
 158    unordered_set_type testset(bucket_traits(
 159       pointer_traits<typename unordered_set_type::bucket_ptr>::
 160          pointer_to(buckets[0]), BucketSize));
 161    testset.insert(&values[0] + 2, &values[0] + 5);
 162
 163    typename unordered_set_type::insert_commit_data commit_data;
 164    BOOST_TEST ((!testset.insert_check(key_of_value()(values[2]), commit_data).second));
 165    BOOST_TEST (( testset.insert_check(key_of_value()(values[0]), commit_data).second));
 166
 167    const unordered_set_type& const_testset = testset;
 168    if(unordered_set_type::incremental)
 169    {
 170       {  int init_values [] = { 4, 5, 1 };
 171          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 172       typename unordered_set_type::iterator i = testset.begin();
 173       BOOST_TEST (i->value_ == 4);
 174
 175       i = testset.insert(values[0]).first;
 176       BOOST_TEST (&*i == &values[0]);
 177
 178       i = testset.iterator_to (values[2]);
 179       BOOST_TEST (&*i == &values[2]);
 180
 181       testset.erase (i);
 182
 183       {  int init_values [] = { 5, 1, 3 };
 184          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 185    }
 186    else{
 187       {  int init_values [] = { 1, 4, 5 };
 188          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 189       typename unordered_set_type::iterator i = testset.begin();
 190       BOOST_TEST (i->value_ == 1);
 191
 192       i = testset.insert(values[0]).first;
 193       BOOST_TEST (&*i == &values[0]);
 194
 195       i = testset.iterator_to (values[2]);
 196       BOOST_TEST (&*i == &values[2]);
 197
 198       testset.erase (i);
 199
 200       {  int init_values [] = { 1, 3, 5 };
 201          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 202    }
 203 }
 204
 205 template<class ContainerDefiner>
 206 void test_unordered<ContainerDefiner>::test_insert(value_cont_type& values, detail::true_) //is multikey
 207 {
 208    typedef typename ContainerDefiner::template container
 209       <>::type unordered_type;
 210
 211    typedef typename unordered_type::bucket_traits bucket_traits;
 212    typedef typename unordered_type::iterator iterator;
 213    typedef typename unordered_type::key_type key_type;
 214    {
 215       typename unordered_type::bucket_type buckets [BucketSize];
 216       unordered_type testset(bucket_traits(
 217          pointer_traits<typename unordered_type::bucket_ptr>::
 218                pointer_to(buckets[0]), BucketSize));
 219
 220       testset.insert(&values[0] + 2, &values[0] + 5);
 221
 222       const unordered_type& const_testset = testset;
 223
 224       if(unordered_type::incremental){
 225          {
 226             {  int init_values [] = { 4, 5, 1 };
 227                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 228
 229             typename unordered_type::iterator i = testset.begin();
 230             BOOST_TEST (i->value_ == 4);
 231
 232             i = testset.insert (values[0]);
 233             BOOST_TEST (&*i == &values[0]);
 234
 235             i = testset.iterator_to (values[2]);
 236             BOOST_TEST (&*i == &values[2]);
 237             testset.erase(i);
 238
 239             {  int init_values [] = { 5, 1, 3 };
 240                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 241             testset.clear();
 242             testset.insert(&values[0], &values[0] + values.size());
 243
 244             {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 245                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 246
 247             BOOST_TEST (testset.erase(key_type(1)) == 1);
 248             BOOST_TEST (testset.erase(key_type(2)) == 2);
 249             BOOST_TEST (testset.erase(key_type(3)) == 1);
 250             BOOST_TEST (testset.erase(key_type(4)) == 1);
 251             BOOST_TEST (testset.erase(key_type(5)) == 1);
 252             BOOST_TEST (testset.empty() == true);
 253
 254             //Now with a single bucket
 255             typename unordered_type::bucket_type single_bucket[1];
 256             unordered_type testset2(bucket_traits(
 257                pointer_traits<typename unordered_type::bucket_ptr>::
 258                   pointer_to(single_bucket[0]), 1));
 259             testset2.insert(&values[0], &values[0] + values.size());
 260             BOOST_TEST (testset2.erase(key_type(5)) == 1);
 261             BOOST_TEST (testset2.erase(key_type(2)) == 2);
 262             BOOST_TEST (testset2.erase(key_type(1)) == 1);
 263             BOOST_TEST (testset2.erase(key_type(4)) == 1);
 264             BOOST_TEST (testset2.erase(key_type(3)) == 1);
 265             BOOST_TEST (testset2.empty() == true);
 266          }
 267       }
 268       else{
 269          {
 270             {  int init_values [] = { 1, 4, 5 };
 271                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 272
 273             typename unordered_type::iterator i = testset.begin();
 274             BOOST_TEST (i->value_ == 1);
 275
 276             i = testset.insert (values[0]);
 277             BOOST_TEST (&*i == &values[0]);
 278
 279             i = testset.iterator_to (values[2]);
 280             BOOST_TEST (&*i == &values[2]);
 281             testset.erase(i);
 282
 283             {  int init_values [] = { 1, 3, 5 };
 284                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 285             testset.clear();
 286             testset.insert(&values[0], &values[0] + values.size());
 287
 288             {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 289                TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, const_testset );  }
 290
 291             BOOST_TEST (testset.erase(key_type(1)) == 1);
 292             BOOST_TEST (testset.erase(key_type(2)) == 2);
 293             BOOST_TEST (testset.erase(key_type(3)) == 1);
 294             BOOST_TEST (testset.erase(key_type(4)) == 1);
 295             BOOST_TEST (testset.erase(key_type(5)) == 1);
 296             BOOST_TEST (testset.empty() == true);
 297
 298             //Now with a single bucket
 299             typename unordered_type::bucket_type single_bucket[1];
 300             unordered_type testset2(bucket_traits(
 301                pointer_traits<typename unordered_type::bucket_ptr>::
 302                   pointer_to(single_bucket[0]), 1));
 303             testset2.insert(&values[0], &values[0] + values.size());
 304             BOOST_TEST (testset2.erase(key_type(5)) == 1);
 305             BOOST_TEST (testset2.erase(key_type(2)) == 2);
 306             BOOST_TEST (testset2.erase(key_type(1)) == 1);
 307             BOOST_TEST (testset2.erase(key_type(4)) == 1);
 308             BOOST_TEST (testset2.erase(key_type(3)) == 1);
 309             BOOST_TEST (testset2.empty() == true);
 310          }
 311       }
 312       {
 313          //Now erase just one per loop
 314          const int random_init[] = { 3, 2, 4, 1, 5, 2, 2 };
 315          const unsigned int random_size = sizeof(random_init)/sizeof(random_init[0]);
 316          typename unordered_type::bucket_type single_bucket[1];
 317          for(unsigned int i = 0, max = random_size; i != max; ++i){
 318             value_cont_type data (random_size);
 319             for (unsigned int j = 0; j < random_size; ++j)
 320                data[j].value_ = random_init[j];
 321             unordered_type testset_new(bucket_traits(
 322                pointer_traits<typename unordered_type::bucket_ptr>::
 323                   pointer_to(single_bucket[0]), 1));
 324             testset_new.insert(&data[0], &data[0]+max);
 325             testset_new.erase(testset_new.iterator_to(data[i]));
 326             BOOST_TEST (testset_new.size() == (max -1));
 327          }
 328       }
 329    }
 330    {
 331       typename unordered_type::bucket_type buckets [BucketSize];
 332       const unsigned int NumBucketSize = BucketSize;
 333       const unsigned int LoadFactor    = 3;
 334       const unsigned int NumIterations = NumBucketSize*LoadFactor;
 335       value_cont_type random_init(NumIterations);//Preserve memory
 336       value_cont_type set_tester;
 337       set_tester.reserve(NumIterations);
 338
 339       //Initialize values
 340       for (unsigned int i = 0; i < NumIterations; ++i){
 341          random_init[i].value_ = i*2;//(i/LoadFactor)*LoadFactor;
 342       }
 343
 344       for(unsigned int initial_pos = 0; initial_pos != (NumIterations+1); ++initial_pos){
 345          for(unsigned int final_pos = initial_pos; final_pos != (NumIterations+1); ++final_pos){
 346
 347             //Create intrusive container inserting values
 348             unordered_type testset
 349                ( &random_init[0]
 350                , &random_init[0] + random_init.size()
 351                , bucket_traits(pointer_traits<typename unordered_type::bucket_ptr>::
 352                   pointer_to(buckets[0]), NumBucketSize));
 353
 354             BOOST_TEST (testset.size() == random_init.size());
 355
 356             //Obtain the iterator range to erase
 357             iterator it_beg_pos = testset.begin();
 358             for(unsigned int it_beg_pos_num = 0; it_beg_pos_num != initial_pos; ++it_beg_pos_num){
 359                ++it_beg_pos;
 360             }
 361             iterator it_end_pos(it_beg_pos);
 362             for(unsigned int it_end_pos_num = 0; it_end_pos_num != (final_pos - initial_pos); ++it_end_pos_num){
 363                ++it_end_pos;
 364             }
 365
 366             //Erase the same values in both the intrusive and original vector
 367             std::size_t erased_cnt = boost::intrusive::iterator_distance(it_beg_pos, it_end_pos);
 368
 369             //Erase values from the intrusive container
 370             testset.erase(it_beg_pos, it_end_pos);
 371
 372             BOOST_TEST (testset.size() == (random_init.size()-(final_pos - initial_pos)));
 373
 374             //Now test...
 375             BOOST_TEST ((random_init.size() - erased_cnt) == testset.size());
 376
 377             //Create an ordered copy of the intrusive container
 378             set_tester.insert(set_tester.end(), testset.begin(), testset.end());
 379             std::sort(set_tester.begin(), set_tester.end());
 380             {
 381                typename value_cont_type::iterator it = set_tester.begin(), itend = set_tester.end();
 382                typename value_cont_type::iterator random_init_it(random_init.begin());
 383                for( ; it != itend; ++it){
 384                   while(!random_init_it->is_linked())
 385                      ++random_init_it;
 386                   BOOST_TEST(*it == *random_init_it);
 387                   ++random_init_it;
 388                }
 389             }
 390             set_tester.clear();
 391          }
 392       }
 393    }
 394 }
 395
 396 //test: insert (seq-version), swap, erase (seq-version), size:
 397 template<class ContainerDefiner>
 398 void test_unordered<ContainerDefiner>::test_swap(value_cont_type& values)
 399 {
 400    typedef typename ContainerDefiner::template container
 401       <>::type unordered_type;
 402
 403    typedef typename unordered_type::bucket_traits bucket_traits;
 404    typename unordered_type::bucket_type buckets [BucketSize];
 405
 406    typename unordered_type::bucket_type buckets2 [BucketSize];
 407    unordered_type testset1(&values[0], &values[0] + 2,
 408       bucket_traits(pointer_traits<typename unordered_type::bucket_ptr>::
 409          pointer_to(buckets[0]), BucketSize));
 410    unordered_type testset2(bucket_traits(
 411       pointer_traits<typename unordered_type::bucket_ptr>::
 412                   pointer_to(buckets2[0]), BucketSize));
 413
 414    testset2.insert (&values[0] + 2, &values[0] + 6);
 415    testset1.swap (testset2);
 416
 417    if(unordered_type::incremental){
 418       {  int init_values [] = { 4, 5, 1, 2 };
 419          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 420
 421       {  int init_values [] = { 2, 3 };
 422          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset2 );  }
 423       testset1.erase (testset1.iterator_to(values[4]), testset1.end());
 424       BOOST_TEST (testset1.size() == 1);
 425       //  BOOST_TEST (&testset1.front() == &values[3]);
 426       BOOST_TEST (&*testset1.begin() == &values[2]);
 427    }
 428    else{
 429       {  int init_values [] = { 1, 2, 4, 5 };
 430          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 431
 432       {  int init_values [] = { 2, 3 };
 433          TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset2 );  }
 434       testset1.erase (testset1.iterator_to(values[5]), testset1.end());
 435       BOOST_TEST (testset1.size() == 1);
 436       //  BOOST_TEST (&testset1.front() == &values[3]);
 437       BOOST_TEST (&*testset1.begin() == &values[3]);
 438    }
 439 }
 440
 441
 442
 443 //test: rehash:
 444
 445 template<class ContainerDefiner>
 446 void test_unordered<ContainerDefiner>::test_rehash(value_cont_type& values, detail::true_)
 447 {
 448    typedef typename ContainerDefiner::template container
 449       <>::type unordered_type;
 450
 451    typedef typename unordered_type::bucket_traits bucket_traits;
 452    //Build a uset
 453    typename unordered_type::bucket_type buckets1 [BucketSize];
 454    typename unordered_type::bucket_type buckets2 [BucketSize*2];
 455    unordered_type testset1(&values[0], &values[0] + values.size(),
 456       bucket_traits(pointer_traits<typename unordered_type::bucket_ptr>::
 457          pointer_to(buckets1[0]), BucketSize));
 458    //Test current state
 459    BOOST_TEST(testset1.split_count() == BucketSize/2);
 460    {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 461       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 462    //Incremental rehash step
 463    BOOST_TEST (testset1.incremental_rehash() == true);
 464    BOOST_TEST(testset1.split_count() == (BucketSize/2+1));
 465    {  int init_values [] = { 5, 1, 2, 2, 3, 4 };
 466       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 467    //Rest of incremental rehashes should lead to the same sequence
 468    for(std::size_t split_bucket = testset1.split_count(); split_bucket != BucketSize; ++split_bucket){
 469       BOOST_TEST (testset1.incremental_rehash() == true);
 470       BOOST_TEST(testset1.split_count() == (split_bucket+1));
 471       {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 472       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 473    }
 474    //This incremental rehash should fail because we've reached the end of the bucket array
 475    BOOST_TEST (testset1.incremental_rehash() == false);
 476    BOOST_TEST(testset1.split_count() == BucketSize);
 477    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 478    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 479
 480    //
 481    //Try incremental hashing specifying a new bucket traits pointing to the same array
 482    //
 483    //This incremental rehash should fail because the new size is not twice the original
 484    BOOST_TEST(testset1.incremental_rehash(bucket_traits(
 485       pointer_traits<typename unordered_type::bucket_ptr>::
 486                               pointer_to(buckets1[0]), BucketSize)) == false);
 487    BOOST_TEST(testset1.split_count() == BucketSize);
 488    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 489    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 490
 491    //
 492    //Try incremental hashing specifying a new bucket traits pointing to the same array
 493    //
 494    //This incremental rehash should fail because the new size is not twice the original
 495    BOOST_TEST(testset1.incremental_rehash(bucket_traits(
 496       pointer_traits<typename unordered_type::bucket_ptr>::
 497                pointer_to(buckets2[0]), BucketSize)) == false);
 498    BOOST_TEST(testset1.split_count() == BucketSize);
 499    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 500    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 501
 502    //This incremental rehash should success because the new size is twice the original
 503    //and split_count is the same as the old bucket count
 504    BOOST_TEST(testset1.incremental_rehash(bucket_traits(
 505       pointer_traits<typename unordered_type::bucket_ptr>::
 506                      pointer_to(buckets2[0]), BucketSize*2)) == true);
 507    BOOST_TEST(testset1.split_count() == BucketSize);
 508    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 509    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 510
 511    //This incremental rehash should also success because the new size is half the original
 512    //and split_count is the same as the new bucket count
 513    BOOST_TEST(testset1.incremental_rehash(bucket_traits(
 514       pointer_traits<typename unordered_type::bucket_ptr>::
 515                            pointer_to(buckets1[0]), BucketSize)) == true);
 516    BOOST_TEST(testset1.split_count() == BucketSize);
 517    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 518    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 519
 520    //Shrink rehash
 521    testset1.rehash(bucket_traits(
 522       pointer_traits<typename unordered_type::bucket_ptr>::
 523          pointer_to(buckets1[0]), 4));
 524    BOOST_TEST (testset1.incremental_rehash() == false);
 525    {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 526       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 527
 528    //Shrink rehash again
 529    testset1.rehash(bucket_traits(
 530       pointer_traits<typename unordered_type::bucket_ptr>::
 531          pointer_to(buckets1[0]), 2));
 532    BOOST_TEST (testset1.incremental_rehash() == false);
 533    {  int init_values [] = { 2, 2, 4, 3, 5, 1 };
 534       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 535
 536    //Growing rehash
 537    testset1.rehash(bucket_traits(
 538       pointer_traits<typename unordered_type::bucket_ptr>::
 539          pointer_to(buckets1[0]), BucketSize));
 540
 541    //Full rehash (no effects)
 542    testset1.full_rehash();
 543    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 544       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 545
 546    //Incremental rehash shrinking
 547    //First incremental rehashes should lead to the same sequence
 548    for(std::size_t split_bucket = testset1.split_count(); split_bucket > 6; --split_bucket){
 549       BOOST_TEST (testset1.incremental_rehash(false) == true);
 550       BOOST_TEST(testset1.split_count() == (split_bucket-1));
 551       {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 552       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 553    }
 554
 555    //Incremental rehash step
 556    BOOST_TEST (testset1.incremental_rehash(false) == true);
 557    BOOST_TEST(testset1.split_count() == (BucketSize/2+1));
 558    {  int init_values [] = { 5, 1, 2, 2, 3, 4 };
 559       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 560
 561    //Incremental rehash step 2
 562    BOOST_TEST (testset1.incremental_rehash(false) == true);
 563    BOOST_TEST(testset1.split_count() == (BucketSize/2));
 564    {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 565       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 566
 567    //This incremental rehash should fail because we've reached the half of the bucket array
 568    BOOST_TEST(testset1.incremental_rehash(false) == false);
 569    BOOST_TEST(testset1.split_count() == BucketSize/2);
 570    {  int init_values [] = { 4, 5, 1, 2, 2, 3 };
 571    TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 572 }
 573 template<class ContainerDefiner>
 574 void test_unordered<ContainerDefiner>::test_rehash(value_cont_type& values, detail::false_)
 575 {
 576    typedef typename ContainerDefiner::template container
 577       <>::type unordered_type;
 578
 579    typedef typename unordered_type::bucket_traits bucket_traits;
 580
 581    typename unordered_type::bucket_type buckets1 [BucketSize];
 582    typename unordered_type::bucket_type buckets2 [2];
 583    typename unordered_type::bucket_type buckets3 [BucketSize*2];
 584
 585    unordered_type testset1(&values[0], &values[0] + 6, bucket_traits(
 586       pointer_traits<typename unordered_type::bucket_ptr>::
 587          pointer_to(buckets1[0]), BucketSize));
 588    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 589       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 590
 591    testset1.rehash(bucket_traits(
 592       pointer_traits<typename unordered_type::bucket_ptr>::
 593          pointer_to(buckets2[0]), 2));
 594    {  int init_values [] = { 4, 2, 2, 5, 3, 1 };
 595       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 596
 597    testset1.rehash(bucket_traits(
 598       pointer_traits<typename unordered_type::bucket_ptr>::
 599          pointer_to(buckets3[0]), BucketSize*2));
 600    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 601       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 602
 603    //Now rehash reducing the buckets
 604    testset1.rehash(bucket_traits(
 605       pointer_traits<typename unordered_type::bucket_ptr>::
 606          pointer_to(buckets3[0]), 2));
 607    {  int init_values [] = { 4, 2, 2, 5, 3, 1 };
 608       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 609
 610    //Now rehash increasing the buckets
 611    testset1.rehash(bucket_traits(
 612       pointer_traits<typename unordered_type::bucket_ptr>::
 613          pointer_to(buckets3[0]), BucketSize*2));
 614    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 615       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 616
 617    //Full rehash (no effects)
 618    testset1.full_rehash();
 619    {  int init_values [] = { 1, 2, 2, 3, 4, 5 };
 620       TEST_INTRUSIVE_SEQUENCE_MAYBEUNIQUE( init_values, testset1 );  }
 621 }
 622
 623 //test: find, equal_range (lower_bound, upper_bound):
 624 template<class ContainerDefiner>
 625 void test_unordered<ContainerDefiner>::test_find(value_cont_type& values)
 626 {
 627    typedef typename ContainerDefiner::template container
 628       <>::type unordered_type;
 629    typedef typename unordered_type::value_type value_type;
 630
 631    typedef typename unordered_type::bucket_traits  bucket_traits;
 632    typedef typename unordered_type::key_of_value   key_of_value;
 633    const bool is_multikey = boost::intrusive::test::is_multikey_true<unordered_type>::value;
 634
 635    typename unordered_type::bucket_type buckets[BucketSize];
 636    unordered_type testset(values.begin(), values.end(), bucket_traits(
 637       pointer_traits<typename unordered_type::bucket_ptr>::
 638          pointer_to(buckets[0]), BucketSize));
 639
 640    typedef typename unordered_type::iterator iterator;
 641
 642    value_type cmp_val;
 643    cmp_val.value_ = 2;
 644    BOOST_TEST (testset.count(key_of_value()(cmp_val)) == (is_multikey ? 2 : 1));
 645    iterator i = testset.find (key_of_value()(cmp_val));
 646    BOOST_TEST (i->value_ == 2);
 647    if(is_multikey)
 648       BOOST_TEST ((++i)->value_ == 2);
 649    else
 650       BOOST_TEST ((++i)->value_ != 2);
 651    std::pair<iterator,iterator> range = testset.equal_range (key_of_value()(cmp_val));
 652
 653    BOOST_TEST (range.first->value_ == 2);
 654    BOOST_TEST (range.second->value_ == 3);
 655    BOOST_TEST (boost::intrusive::iterator_distance (range.first, range.second) == (is_multikey ? 2 : 1));
 656    cmp_val.value_ = 7;
 657    BOOST_TEST (testset.find (key_of_value()(cmp_val)) == testset.end());
 658    BOOST_TEST (testset.count(key_of_value()(cmp_val)) == 0);
 659 }
 660
 661
 662 template<class ContainerDefiner>
 663 void test_unordered<ContainerDefiner>::test_clone(value_cont_type& values)
 664 {
 665    typedef typename ContainerDefiner::template container
 666       <>::type unordered_type;
 667    typedef typename unordered_type::value_type value_type;
 668    typedef std::multiset<value_type> std_multiset_t;
 669
 670    typedef typename unordered_type::bucket_traits bucket_traits;
 671    {
 672       //Test with equal bucket arrays
 673       typename unordered_type::bucket_type buckets1 [BucketSize];
 674       typename unordered_type::bucket_type buckets2 [BucketSize];
 675       unordered_type testset1 (values.begin(), values.end(), bucket_traits(
 676          pointer_traits<typename unordered_type::bucket_ptr>::
 677          pointer_to(buckets1[0]), BucketSize));
 678       unordered_type testset2 (bucket_traits(
 679          pointer_traits<typename unordered_type::bucket_ptr>::
 680          pointer_to(buckets2[0]), BucketSize));
 681
 682       testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
 683       BOOST_TEST(testset1 == testset2);
 684       //Ordering is not guarantee in the cloning so insert data in a set and test
 685       std_multiset_t src(testset1.begin(), testset1.end());
 686       std_multiset_t dst(testset2.begin(), testset2.end());
 687       BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 688       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 689       BOOST_TEST (testset2.empty());
 690
 691       testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>());
 692       BOOST_TEST(testset1 == testset2);
 693       //Ordering is not guarantee in the cloning so insert data in a set and test
 694       std_multiset_t(testset1.begin(), testset1.end()).swap(src);
 695       std_multiset_t(testset2.begin(), testset2.end()).swap(dst);
 696       BOOST_TEST(src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 697       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 698       BOOST_TEST (testset2.empty());
 699    }
 700    {
 701       //Test with bigger source bucket arrays
 702       typename unordered_type::bucket_type buckets1 [BucketSize*2];
 703       typename unordered_type::bucket_type buckets2 [BucketSize];
 704       unordered_type testset1 (values.begin(), values.end(), bucket_traits(
 705          pointer_traits<typename unordered_type::bucket_ptr>::
 706          pointer_to(buckets1[0]), BucketSize*2));
 707       unordered_type testset2 (bucket_traits(
 708          pointer_traits<typename unordered_type::bucket_ptr>::
 709          pointer_to(buckets2[0]), BucketSize));
 710
 711       testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
 712       BOOST_TEST(testset1 == testset2);
 713       //Ordering is not guarantee in the cloning so insert data in a set and test
 714       std_multiset_t src(testset1.begin(), testset1.end());
 715       std_multiset_t dst(testset2.begin(), testset2.end());
 716       BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 717       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 718       BOOST_TEST (testset2.empty());
 719
 720       testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>());
 721       BOOST_TEST(testset1 == testset2);
 722       //Ordering is not guarantee in the cloning so insert data in a set and test
 723       std_multiset_t(testset1.begin(), testset1.end()).swap(src);
 724       std_multiset_t(testset2.begin(), testset2.end()).swap(dst);
 725       BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 726       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 727       BOOST_TEST (testset2.empty());
 728    }
 729    {
 730       //Test with smaller source bucket arrays
 731       typename unordered_type::bucket_type buckets1 [BucketSize];
 732       typename unordered_type::bucket_type buckets2 [BucketSize*2];
 733       unordered_type testset1 (values.begin(), values.end(), bucket_traits(
 734          pointer_traits<typename unordered_type::bucket_ptr>::
 735          pointer_to(buckets1[0]), BucketSize));
 736       unordered_type testset2 (bucket_traits(
 737          pointer_traits<typename unordered_type::bucket_ptr>::
 738          pointer_to(buckets2[0]), BucketSize*2));
 739
 740       testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
 741       BOOST_TEST(testset1 == testset2);
 742       //Ordering is not guaranteed in the cloning so insert data in a set and test
 743       std_multiset_t src(testset1.begin(), testset1.end());
 744       std_multiset_t dst(testset2.begin(), testset2.end());
 745       BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 746       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 747       BOOST_TEST (testset2.empty());
 748
 749       testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>());
 750       BOOST_TEST(testset1 == testset2);
 751       //Ordering is not guaranteed in the cloning so insert data in a set and test
 752       std_multiset_t(testset1.begin(), testset1.end()).swap(src);
 753       std_multiset_t(testset2.begin(), testset2.end()).swap(dst);
 754       BOOST_TEST (src.size() == dst.size() && std::equal(src.begin(), src.end(), dst.begin()));
 755       testset2.clear_and_dispose(test::delete_disposer<value_type>());
 756       BOOST_TEST (testset2.empty());
 757    }
 758 }
 759
 760 }  //namespace test{
 761 }  //namespace intrusive{
 762 }  //namespace boost{