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

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2013
   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
  13 #ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP
  14 #define BOOST_INTRUSIVE_TEST_CONTAINER_HPP
  15
  16 #include <boost/detail/lightweight_test.hpp>
  17 #include <boost/intrusive/detail/mpl.hpp>
  18 #include <boost/intrusive/detail/simple_disposers.hpp>
  19 #include <boost/intrusive/detail/iterator.hpp>
  20 #include <boost/move/utility_core.hpp>
  21 #include <boost/move/adl_move_swap.hpp>
  22 #include <boost/intrusive/detail/mpl.hpp>
  23 #include <boost/static_assert.hpp>
  24 #include "iterator_test.hpp"
  25 #include <cstdlib>
  26
  27 namespace boost {
  28 namespace intrusive {
  29 namespace test {
  30
  31 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_unordered, hasher)
  32
  33 template<class Container>
  34 struct test_container_typedefs
  35 {
  36    typedef typename Container::value_type       value_type;
  37    typedef typename Container::iterator         iterator;
  38    typedef typename Container::const_iterator   const_iterator;
  39    typedef typename Container::reference        reference;
  40    typedef typename Container::const_reference  const_reference;
  41    typedef typename Container::pointer          pointer;
  42    typedef typename Container::const_pointer    const_pointer;
  43    typedef typename Container::difference_type  difference_type;
  44    typedef typename Container::size_type        size_type;
  45    typedef typename Container::value_traits     value_traits;
  46 };
  47
  48 template< class Container >
  49 void test_container( Container & c )
  50 {
  51    typedef typename Container::const_iterator   const_iterator;
  52    typedef typename Container::iterator         iterator;
  53    typedef typename Container::size_type        size_type;
  54
  55    {test_container_typedefs<Container> dummy;  (void)dummy;}
  56    const size_type num_elem = c.size();
  57    BOOST_TEST( c.empty() == (num_elem == 0) );
  58    {
  59       iterator it(c.begin()), itend(c.end());
  60       size_type i;
  61       for(i = 0; i < num_elem; ++i){
  62          ++it;
  63       }
  64       BOOST_TEST( it == itend );
  65       BOOST_TEST( c.size() == i );
  66    }
  67
  68    //Check iterator conversion
  69    BOOST_TEST(const_iterator(c.begin()) == c.cbegin() );
  70    {
  71       const_iterator it(c.cbegin()), itend(c.cend());
  72       size_type i;
  73       for(i = 0; i < num_elem; ++i){
  74          ++it;
  75       }
  76       BOOST_TEST( it == itend );
  77       BOOST_TEST( c.size() == i );
  78    }
  79    static_cast<const Container&>(c).check();
  80    //Very basic test for comparisons
  81    {
  82       BOOST_TEST(c == c);
  83       BOOST_TEST(!(c != c));
  84       BOOST_TEST(!(c < c));
  85       BOOST_TEST(c <= c);
  86       BOOST_TEST(!(c > c));
  87       BOOST_TEST(c >= c);
  88    }
  89 }
  90
  91
  92 template< class Container, class Data >
  93 void test_sequence_container(Container & c, Data & d)
  94 {
  95    assert( d.size() > 2 );
  96    {
  97       c.clear();
  98
  99       BOOST_TEST( c.size() == 0 );
 100       BOOST_TEST( c.empty() );
 101
 102
 103       {
 104       typename Data::iterator i = d.begin();
 105       c.insert( c.begin(), *i );
 106       BOOST_TEST( &*c.iterator_to(*c.begin())  == &*i );
 107       BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &*i );
 108       BOOST_TEST( &*Container::s_iterator_to(*c.begin())  == &*i );
 109       BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &*i );
 110       c.insert( c.end(), *(++i) );
 111       }
 112       BOOST_TEST( c.size() == 2 );
 113       BOOST_TEST( !c.empty() );
 114
 115       typename Container::iterator i;
 116       i = c.erase( c.begin() );
 117
 118       BOOST_TEST( c.size() == 1 );
 119       BOOST_TEST( !c.empty() );
 120
 121       i = c.erase( c.begin() );
 122
 123       BOOST_TEST( c.size() == 0 );
 124       BOOST_TEST( c.empty() );
 125
 126       c.insert( c.begin(), *d.begin() );
 127
 128       BOOST_TEST( c.size() == 1 );
 129       BOOST_TEST( !c.empty() );
 130
 131       {
 132       typename Data::iterator di = d.begin();
 133       ++++di;
 134       c.insert( c.begin(), *(di) );
 135       }
 136
 137       i = c.erase( c.begin(), c.end() );
 138       BOOST_TEST( i == c.end() );
 139
 140       BOOST_TEST( c.empty() );
 141
 142       c.insert( c.begin(), *d.begin() );
 143
 144       BOOST_TEST( c.size() == 1 );
 145
 146       BOOST_TEST( c.begin() != c.end() );
 147
 148       i = c.erase_and_dispose( c.begin(), detail::null_disposer() );
 149       BOOST_TEST( i == c.begin() );
 150
 151       c.assign(d.begin(), d.end());
 152
 153       BOOST_TEST( c.size() == d.size() );
 154
 155       c.clear();
 156
 157       BOOST_TEST( c.size() == 0 );
 158       BOOST_TEST( c.empty() );
 159    }
 160    {
 161       c.clear();
 162       c.insert( c.begin(), d.begin(), d.end() );
 163       Container move_c(::boost::move(c));
 164       BOOST_TEST( move_c.size() == d.size() );
 165       BOOST_TEST( c.empty());
 166
 167       c = ::boost::move(move_c);
 168       BOOST_TEST( c.size() == d.size() );
 169       BOOST_TEST( move_c.empty());
 170    }
 171 }
 172
 173 template< class Container, class Data >
 174 void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::true_ unordered)
 175 {
 176    (void)unordered;
 177    typedef typename Container::size_type        size_type;
 178    typedef typename Container::key_of_value     key_of_value;
 179    typedef typename Container::iterator         iterator;
 180    typedef typename Container::const_iterator   const_iterator;
 181
 182    assert( d.size() > 2 );
 183
 184    c.clear();
 185    c.insert(d.begin(), d.end());
 186
 187    {
 188       Container const &cc = c;
 189       for( typename Data::const_iterator di = d.begin(), de = d.end();
 190          di != de; ++di )
 191       {
 192          BOOST_TEST( cc.find(key_of_value()(*di), c.hash_function(), c.key_eq()) != cc.end() );
 193          std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.hash_function(), c.key_eq());
 194          BOOST_TEST(rdi.first != rdi.second);
 195          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.hash_function(), c.key_eq()));
 196       }
 197
 198       for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
 199       {
 200          BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
 201          std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.hash_function(), c.key_eq());
 202          BOOST_TEST(rci.first != rci.second);
 203          size_type const sc = c.count(key_of_value()(*ci), c.hash_function(), c.key_eq());
 204          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
 205          BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.hash_function(), c.key_eq()));
 206          ci = rci.second;
 207       }
 208       BOOST_TEST(c.empty());
 209    }
 210
 211    c.clear();
 212    c.insert(d.begin(), d.end());
 213
 214    typename Data::const_iterator db = d.begin();
 215    typename Data::const_iterator da = db++;
 216
 217    size_type old_size = c.size();
 218
 219    c.erase(key_of_value()(*da), c.hash_function(), c.key_eq());
 220    BOOST_TEST( c.size() == old_size-1 );
 221    //This should not eras anyone
 222    size_type second_erase = c.erase_and_dispose
 223       ( key_of_value()(*da), c.hash_function(), c.key_eq(), detail::null_disposer() );
 224    BOOST_TEST( second_erase == 0 );
 225
 226    BOOST_TEST( c.count(key_of_value()(*da), c.hash_function(), c.key_eq()) == 0 );
 227    BOOST_TEST( c.count(key_of_value()(*db), c.hash_function(), c.key_eq()) != 0 );
 228
 229    BOOST_TEST( c.find(key_of_value()(*da), c.hash_function(), c.key_eq()) == c.end() );
 230    BOOST_TEST( c.find(key_of_value()(*db), c.hash_function(), c.key_eq()) != c.end() );
 231
 232    BOOST_TEST( c.equal_range(key_of_value()(*db), c.hash_function(), c.key_eq()).first != c.end() );
 233
 234    c.clear();
 235
 236    BOOST_TEST( c.equal_range(key_of_value()(*da), c.hash_function(), c.key_eq()).first == c.end() );
 237
 238    //
 239    //suggested_upper_bucket_count
 240    //
 241    //Maximum fallbacks to the highest possible value
 242    typename Container::size_type sz = Container::suggested_upper_bucket_count(size_type(-1));
 243    BOOST_TEST( sz > size_type(-1)/2 );
 244    //In the rest of cases the upper bound is returned
 245    sz = Container::suggested_upper_bucket_count(size_type(-1)/2);
 246    BOOST_TEST( sz >= size_type(-1)/2 );
 247    sz = Container::suggested_upper_bucket_count(size_type(-1)/4);
 248    BOOST_TEST( sz >= size_type(-1)/4 );
 249    sz = Container::suggested_upper_bucket_count(0);
 250    BOOST_TEST( sz > 0 );
 251    //
 252    //suggested_lower_bucket_count
 253    //
 254    sz = Container::suggested_lower_bucket_count(size_type(-1));
 255    BOOST_TEST( sz <= size_type(-1) );
 256    //In the rest of cases the lower bound is returned
 257    sz = Container::suggested_lower_bucket_count(size_type(-1)/2);
 258    BOOST_TEST( sz <= size_type(-1)/2 );
 259    sz = Container::suggested_lower_bucket_count(size_type(-1)/4);
 260    BOOST_TEST( sz <= size_type(-1)/4 );
 261    //Minimum fallbacks to the lowest possible value
 262    sz = Container::suggested_upper_bucket_count(0);
 263    BOOST_TEST( sz > 0 );
 264 }
 265
 266 template< class Container, class Data >
 267 void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::false_ unordered)
 268 {
 269    (void)unordered;
 270    typedef typename Container::size_type        size_type;
 271    typedef typename Container::key_of_value     key_of_value;
 272    typedef typename Container::iterator         iterator;
 273    typedef typename Container::const_iterator   const_iterator;
 274
 275    assert( d.size() > 2 );
 276
 277    c.clear();
 278    typename Container::reference r = *d.begin();
 279    c.insert(d.begin(), ++d.begin());
 280    BOOST_TEST( &*Container::s_iterator_to(*c.begin())  == &r );
 281    BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &r );
 282
 283    c.clear();
 284    c.insert(d.begin(), d.end());
 285    {
 286       Container const &cc = c;
 287       for( typename Data::const_iterator di = d.begin(), de = d.end();
 288          di != de; ++di )
 289       {
 290          BOOST_TEST( cc.find(key_of_value()(*di), c.key_comp()) != cc.end() );
 291          std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.key_comp());
 292          BOOST_TEST(rdi.first != rdi.second);
 293          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.key_comp()));
 294       }
 295
 296       for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
 297       {
 298          BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
 299          std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.key_comp());
 300          BOOST_TEST(rci.first != rci.second);
 301          size_type const sc = c.count(key_of_value()(*ci), c.key_comp());
 302          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
 303          BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.key_comp()));
 304          ci = rci.second;
 305       }
 306       BOOST_TEST(c.empty());
 307    }
 308
 309    c.clear();
 310    c.insert(d.begin(), d.end());
 311
 312    typename Data::const_iterator db = d.begin();
 313    typename Data::const_iterator da = db++;
 314
 315    size_type old_size = c.size();
 316
 317    c.erase(key_of_value()(*da), c.key_comp());
 318    BOOST_TEST( c.size() == old_size-1 );
 319    //This should not erase any
 320    size_type second_erase = c.erase_and_dispose( key_of_value()(*da), c.key_comp(), detail::null_disposer() );
 321    BOOST_TEST( second_erase == 0 );
 322
 323    BOOST_TEST( c.count(key_of_value()(*da), c.key_comp()) == 0 );
 324    BOOST_TEST( c.count(key_of_value()(*db), c.key_comp()) != 0 );
 325    BOOST_TEST( c.find(key_of_value()(*da), c.key_comp()) == c.end() );
 326    BOOST_TEST( c.find(key_of_value()(*db), c.key_comp()) != c.end() );
 327    BOOST_TEST( c.equal_range(key_of_value()(*db), c.key_comp()).first != c.end() );
 328    c.clear();
 329    BOOST_TEST( c.equal_range(key_of_value()(*da), c.key_comp()).first == c.end() );
 330 }
 331
 332 template< class Container, class Data >
 333 void test_common_unordered_and_associative_container(Container & c, Data & d)
 334 {
 335    typedef typename Container::size_type        size_type;
 336    typedef typename Container::key_of_value     key_of_value;
 337    typedef typename Container::iterator         iterator;
 338    typedef typename Container::const_iterator   const_iterator;
 339
 340    {
 341       assert( d.size() > 2 );
 342
 343       c.clear();
 344       typename Container::reference r = *d.begin();
 345       c.insert(d.begin(), ++d.begin());
 346       BOOST_TEST( &*c.iterator_to(*c.begin())  == &r );
 347       BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &r );
 348
 349       c.clear();
 350       c.insert(d.begin(), d.end());
 351
 352       Container const &cc = c;
 353       for( typename Data::const_iterator di = d.begin(), de = d.end();
 354          di != de; ++di )
 355       {
 356          BOOST_TEST( cc.find(key_of_value()(*di)) != cc.end() );
 357          std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di));
 358          BOOST_TEST(rdi.first != rdi.second);
 359          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di)));
 360       }
 361
 362       for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
 363       {
 364          BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
 365          std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci));
 366          BOOST_TEST(rci.first != rci.second);
 367          size_type const sc = c.count(key_of_value()(*ci));
 368          BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
 369          BOOST_TEST(sc == c.erase(key_of_value()(*ci)));
 370          ci = rci.second;
 371       }
 372       BOOST_TEST(c.empty());
 373    }
 374    {
 375       c.clear();
 376       c.insert(d.begin(), d.end());
 377
 378       typename Data::const_iterator db = d.begin();
 379       typename Data::const_iterator da = db++;
 380
 381       size_type old_size = c.size();
 382
 383       c.erase(key_of_value()(*da));
 384       BOOST_TEST( c.size() == old_size-1 );
 385       //This should erase nothing
 386       size_type second_erase = c.erase_and_dispose( key_of_value()(*da), detail::null_disposer() );
 387       BOOST_TEST( second_erase == 0 );
 388
 389       BOOST_TEST( c.count(key_of_value()(*da)) == 0 );
 390       BOOST_TEST( c.count(key_of_value()(*db)) != 0 );
 391
 392       BOOST_TEST( c.find(key_of_value()(*da)) == c.end() );
 393       BOOST_TEST( c.find(key_of_value()(*db)) != c.end() );
 394
 395       BOOST_TEST( c.equal_range(key_of_value()(*db)).first != c.end() );
 396       BOOST_TEST( c.equal_range(key_of_value()(*da)).first == c.equal_range(key_of_value()(*da)).second );
 397    }
 398    {
 399       c.clear();
 400       c.insert( d.begin(), d.end() );
 401       size_type orig_size = c.size();
 402       Container move_c(::boost::move(c));
 403       BOOST_TEST(orig_size == move_c.size());
 404       BOOST_TEST( c.empty());
 405       for( typename Data::const_iterator di = d.begin(), de = d.end();
 406          di != de; ++di )
 407       {  BOOST_TEST( move_c.find(key_of_value()(*di)) != move_c.end() );   }
 408
 409       c = ::boost::move(move_c);
 410       for( typename Data::const_iterator di = d.begin(), de = d.end();
 411          di != de; ++di )
 412       {  BOOST_TEST( c.find(key_of_value()(*di)) != c.end() );   }
 413       BOOST_TEST( move_c.empty());
 414    }
 415    typedef detail::bool_<is_unordered<Container>::value> enabler;
 416    test_common_unordered_and_associative_container(c, d, enabler());
 417 }
 418
 419 template< class Container, class Data >
 420 void test_associative_container_invariants(Container & c, Data & d)
 421 {
 422    typedef typename Container::const_iterator   const_iterator;
 423    typedef typename Container::key_of_value     key_of_value;
 424    for( typename Data::const_iterator di = d.begin(), de = d.end();
 425       di != de; ++di)
 426    {
 427       const_iterator ci = c.find(key_of_value()(*di));
 428       BOOST_TEST( ci != c.end() );
 429       BOOST_TEST( ! c.value_comp()(*ci, *di) );
 430       BOOST_TEST( ! c.key_comp()(key_of_value()(*ci), key_of_value()(*di)) );
 431       const_iterator cil = c.lower_bound(key_of_value()(*di));
 432       const_iterator ciu = c.upper_bound(key_of_value()(*di));
 433       std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
 434       BOOST_TEST( cil == er.first );
 435       BOOST_TEST( ciu == er.second );
 436       if(ciu != c.end()){
 437          BOOST_TEST( c.value_comp()(*cil, *ciu) );
 438          BOOST_TEST( c.key_comp()(key_of_value()(*cil), key_of_value()(*ciu)) );
 439       }
 440       if(c.count(key_of_value()(*di)) > 1){
 441          const_iterator ci_next = cil; ++ci_next;
 442          for( ; ci_next != ciu; ++cil, ++ci_next){
 443             BOOST_TEST( !c.value_comp()(*ci_next, *cil) );
 444             BOOST_TEST( !c.key_comp()(key_of_value()(*ci_next), key_of_value()(*cil)) );
 445          }
 446       }
 447    }
 448 }
 449
 450 template< class Container, class Data >
 451 void test_associative_container(Container & c, Data & d)
 452 {
 453    assert( d.size() > 2 );
 454
 455    c.clear();
 456    c.insert(d.begin(),d.end());
 457
 458    test_associative_container_invariants(c, d);
 459
 460    const Container & cr = c;
 461
 462    test_associative_container_invariants(cr, d);
 463 }
 464
 465 template< class Container, class Data >
 466 void test_unordered_associative_container_invariants(Container & c, Data & d)
 467 {
 468    typedef typename Container::size_type        size_type;
 469    typedef typename Container::const_iterator   const_iterator;
 470    typedef typename Container::key_of_value     key_of_value;
 471
 472    for( typename Data::const_iterator di = d.begin(), de = d.end() ;
 473       di != de ; ++di ){
 474       const_iterator i = c.find(key_of_value()(*di));
 475       size_type nb = c.bucket(key_of_value()(*i));
 476       size_type bucket_elem = boost::intrusive::iterator_distance(c.begin(nb), c.end(nb));
 477       BOOST_TEST( bucket_elem ==  c.bucket_size(nb) );
 478       BOOST_TEST( &*c.local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
 479       BOOST_TEST( &*c.local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
 480       BOOST_TEST( &*Container::s_local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
 481       BOOST_TEST( &*Container::s_local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
 482       std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
 483       size_type cnt = boost::intrusive::iterator_distance(er.first, er.second);
 484       BOOST_TEST( cnt == c.count(key_of_value()(*di)));
 485       if(cnt > 1){
 486          const_iterator n = er.first;
 487          i = n++;
 488          const_iterator e = er.second;
 489          for(; n != e; ++i, ++n){
 490             BOOST_TEST( c.key_eq()(key_of_value()(*i), key_of_value()(*n)) );
 491             BOOST_TEST( (c.hash_function()(key_of_value()(*i))) == (c.hash_function()(key_of_value()(*n))) );
 492          }
 493       }
 494    }
 495
 496    size_type blen = c.bucket_count();
 497    size_type total_objects = 0;
 498    for(size_type i = 0; i < blen; ++i){
 499       total_objects += c.bucket_size(i);
 500    }
 501    BOOST_TEST( total_objects ==  c.size() );
 502 }
 503
 504 template< class Container, class Data >
 505 void test_unordered_associative_container(Container & c, Data & d)
 506 {
 507    c.clear();
 508    c.insert( d.begin(), d.end() );
 509
 510    test_unordered_associative_container_invariants(c, d);
 511
 512    const Container & cr = c;
 513
 514    test_unordered_associative_container_invariants(cr, d);
 515 }
 516
 517 template< class Container, class Data >
 518 void test_unique_container(Container & c, Data & d)
 519 {
 520    //typedef typename Container::value_type value_type;
 521    c.clear();
 522    c.insert(d.begin(),d.end());
 523    typename Container::size_type old_size = c.size();
 524    //value_type v(*d.begin());
 525    //c.insert(v);
 526    Data d2(1);
 527    (&d2.front())->value_ = (&d.front())->value_;
 528    c.insert(d2.front());
 529    BOOST_TEST( c.size() == old_size );
 530    c.clear();
 531 }
 532
 533 template< class Container, class Data >
 534 void test_non_unique_container(Container & c, Data & d)
 535 {
 536    //typedef typename Container::value_type value_type;
 537    c.clear();
 538    c.insert(d.begin(),d.end());
 539    typename Container::size_type old_size = c.size();
 540    //value_type v(*d.begin());
 541    //c.insert(v);
 542    Data d2(1);
 543    (&d2.front())->value_ = (&d.front())->value_;
 544    c.insert(d2.front());
 545    BOOST_TEST( c.size() == (old_size+1) );
 546    c.clear();
 547 }
 548
 549 template< class Container, class Data >
 550 void test_maybe_unique_container(Container & c, Data & d, detail::false_)//is_unique
 551 {  test_unique_container(c, d);  }
 552
 553 template< class Container, class Data >
 554 void test_maybe_unique_container(Container & c, Data & d, detail::true_)//!is_unique
 555 {  test_non_unique_container(c, d);  }
 556
 557 template< class RandomIt >
 558 void random_shuffle( RandomIt first, RandomIt last )
 559 {
 560    typedef typename boost::intrusive::iterator_traits<RandomIt>::difference_type difference_type;
 561    difference_type n = last - first;
 562    for (difference_type i = n-1; i > 0; --i) {
 563       difference_type j = std::rand() % (i+1);
 564       if(j != i) {
 565          boost::adl_move_swap(first[i], first[j]);
 566       }
 567    }
 568 }
 569
 570 }}}
 571
 572 #endif   //#ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP