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

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
   4 // Software License, Version 1.0. (See accompanying file
   5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6 //
   7 // See http://www.boost.org/libs/intrusive for documentation.
   8 //
   9 //////////////////////////////////////////////////////////////////////////////
  10
  11 #include <boost/intrusive/detail/iterator.hpp>
  12 #include <boost/intrusive/detail/mpl.hpp>
  13 #include <boost/static_assert.hpp>
  14
  15 namespace boost{  namespace intrusive {  namespace test{
  16
  17 //////////////////////////////////////////////
  18 //
  19 // Some traits to avoid special cases with
  20 // containers without bidirectional iterators
  21 //
  22 //////////////////////////////////////////////
  23 template<class C>
  24 struct has_member_reverse_iterator
  25 {
  26    typedef char yes_type;
  27    struct no_type{   char _[2];  };
  28
  29    template<typename D> static no_type test(...);
  30    template<typename D> static yes_type test(typename D::reverse_iterator const*);
  31    static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
  32 };
  33
  34 template<class C>
  35 struct has_member_const_reverse_iterator
  36 {
  37    typedef char yes_type;
  38    struct no_type{   char _[2];  };
  39
  40    template<typename D> static no_type test(...);
  41    template<typename D> static yes_type test(typename D::const_reverse_iterator const*);
  42    static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
  43 };
  44
  45 template<class C, bool = has_member_reverse_iterator<C>::value>
  46 struct get_reverse_iterator
  47 {
  48    typedef typename C::reverse_iterator type;
  49    static type begin(C &c) {  return c.rbegin(); }
  50    static type   end(C &c) {  return c.rend(); }
  51 };
  52
  53 template<class C>
  54 struct get_reverse_iterator<C, false>
  55 {
  56    typedef typename C::iterator type;
  57    static type begin(C &c) {  return c.begin(); }
  58    static type   end(C &c) {  return c.end(); }
  59 };
  60
  61 template<class C, bool = has_member_const_reverse_iterator<C>::value>
  62 struct get_const_reverse_iterator
  63 {
  64    typedef typename C::const_reverse_iterator type;
  65    static type begin(C &c) {  return c.crbegin(); }
  66    static type   end(C &c) {  return c.crend(); }
  67 };
  68
  69 template<class C>
  70 struct get_const_reverse_iterator<C, false>
  71 {
  72    typedef typename C::const_iterator type;
  73    static type begin(C &c) {  return c.cbegin(); }
  74    static type   end(C &c) {  return c.cend(); }
  75 };
  76
  77 //////////////////////////////////////////////
  78 //
  79 //          Iterator tests
  80 //
  81 //////////////////////////////////////////////
  82
  83 template<class I>
  84 void test_iterator_operations(I b, I e)
  85 {
  86    //Test the range is not empty
  87    BOOST_TEST(b != e);
  88    BOOST_TEST(!(b == e));
  89    {
  90       I i;
  91       I i2(b); //CopyConstructible
  92       i = i2;  //Assignable
  93       //Destructible
  94       (void)i;
  95       (void)i2;
  96    }
  97
  98    typedef typename iterator_traits<I>::reference reference;
  99    reference r = *b;
 100    (void)r;
 101    typedef typename iterator_traits<I>::pointer pointer;
 102    pointer p = (iterator_arrow_result)(b);
 103    (void)p;
 104    I &ri= ++b;
 105    (void)ri;
 106    const I &cri= b++;
 107    (void)cri;
 108 }
 109
 110 template<class C>
 111 void test_iterator_compatible(C &c)
 112 {
 113    typedef typename C::iterator        iterator;
 114    typedef typename C::const_iterator  const_iterator;
 115    typedef typename get_reverse_iterator<C>::type        reverse_iterator;
 116    typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
 117    //Basic operations
 118    test_iterator_operations(c. begin(), c. end());
 119    test_iterator_operations(c.cbegin(), c.cend());
 120    test_iterator_operations(get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
 121    test_iterator_operations(get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
 122    //Make sure dangeous conversions are not possible
 123    BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_iterator, iterator>::value));
 124    BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_reverse_iterator, reverse_iterator>::value));
 125    //Test iterator conversions
 126    {
 127       const_iterator ci;
 128       iterator i(c.begin());
 129       ci = i;
 130       (void)ci;
 131       BOOST_ASSERT(ci == i);
 132       BOOST_ASSERT(*ci == *i);
 133       const_iterator ci2(i);
 134       BOOST_ASSERT(ci2 == i);
 135       BOOST_ASSERT(*ci2 == *i);
 136       (void)ci2;
 137    }
 138    //Test reverse_iterator conversions
 139    {
 140       const_reverse_iterator cr;
 141       reverse_iterator r(get_reverse_iterator<C>::begin(c));
 142       cr = r;
 143       BOOST_ASSERT(cr == r);
 144       BOOST_ASSERT(*cr == *r);
 145       const_reverse_iterator cr2(r);
 146       BOOST_ASSERT(cr2 == r);
 147       BOOST_ASSERT(*cr2 == *r);
 148       (void)cr2;
 149    }
 150 }
 151
 152 template<class C>
 153 void test_iterator_input_and_compatible(C &c)
 154 {
 155    typedef typename C::iterator                          iterator;
 156    typedef typename C::const_iterator                    const_iterator;
 157    typedef typename get_reverse_iterator<C>::type        reverse_iterator;
 158    typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
 159    typedef iterator_traits<iterator>            nit_traits;
 160    typedef iterator_traits<const_iterator>      cit_traits;
 161    typedef iterator_traits<reverse_iterator>         rnit_traits;
 162    typedef iterator_traits<const_reverse_iterator>   crit_traits;
 163
 164    using boost::move_detail::is_same;
 165    //Trivial typedefs
 166    BOOST_STATIC_ASSERT((!is_same<iterator, const_iterator>::value));
 167    BOOST_STATIC_ASSERT((!is_same<reverse_iterator, const_reverse_iterator>::value));
 168    //difference_type
 169    typedef typename C::difference_type difference_type;
 170    BOOST_STATIC_ASSERT((is_same<difference_type, typename nit_traits::difference_type>::value));
 171    BOOST_STATIC_ASSERT((is_same<difference_type, typename cit_traits::difference_type>::value));
 172    BOOST_STATIC_ASSERT((is_same<difference_type, typename rnit_traits::difference_type>::value));
 173    BOOST_STATIC_ASSERT((is_same<difference_type, typename crit_traits::difference_type>::value));
 174    //value_type
 175    typedef typename C::value_type value_type;
 176    BOOST_STATIC_ASSERT((is_same<value_type, typename nit_traits::value_type>::value));
 177    BOOST_STATIC_ASSERT((is_same<value_type, typename cit_traits::value_type>::value));
 178    BOOST_STATIC_ASSERT((is_same<value_type, typename rnit_traits::value_type>::value));
 179    BOOST_STATIC_ASSERT((is_same<value_type, typename crit_traits::value_type>::value));
 180    //pointer
 181    typedef typename C::pointer pointer;
 182    typedef typename C::const_pointer const_pointer;
 183    BOOST_STATIC_ASSERT((is_same<pointer,        typename nit_traits::pointer>::value));
 184    BOOST_STATIC_ASSERT((is_same<const_pointer,  typename cit_traits::pointer>::value));
 185    BOOST_STATIC_ASSERT((is_same<pointer,        typename rnit_traits::pointer>::value));
 186    BOOST_STATIC_ASSERT((is_same<const_pointer,  typename crit_traits::pointer>::value));
 187    //reference
 188    typedef typename C::reference reference;
 189    typedef typename C::const_reference const_reference;
 190    BOOST_STATIC_ASSERT((is_same<reference,         typename nit_traits::reference>::value));
 191    BOOST_STATIC_ASSERT((is_same<const_reference,   typename cit_traits::reference>::value));
 192    BOOST_STATIC_ASSERT((is_same<reference,         typename rnit_traits::reference>::value));
 193    BOOST_STATIC_ASSERT((is_same<const_reference,   typename crit_traits::reference>::value));
 194    //Dynamic tests
 195    test_iterator_compatible(c);
 196 }
 197
 198 template<class C, class I>
 199 void test_iterator_forward_functions(C const &c, I const b, I const e)
 200 {
 201    typedef typename C::size_type size_type;
 202    {
 203       size_type i = 0;
 204       I it = b;
 205       for(I it2 = b; i != c.size(); ++it, ++i){
 206          BOOST_TEST(it == it2++);
 207          I ittmp(it);
 208          I *iaddr = &ittmp;
 209          BOOST_TEST(&(++ittmp) == iaddr);
 210          BOOST_TEST(ittmp == it2);
 211       }
 212       BOOST_TEST(i == c.size());
 213       BOOST_TEST(it == e);
 214    }
 215 }
 216
 217 template<class C>
 218 void test_iterator_forward_and_compatible(C &c)
 219 {
 220    test_iterator_input_and_compatible(c);
 221    test_iterator_forward_functions(c, c.begin(),   c.end());
 222    test_iterator_forward_functions(c, c.cbegin(),  c.cend());
 223    test_iterator_forward_functions(c, get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
 224    test_iterator_forward_functions(c, get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
 225 }
 226
 227 template<class C, class I>
 228 void test_iterator_bidirectional_functions(C const &c, I const b, I const e)
 229 {
 230    typedef typename C::size_type size_type;
 231    {
 232       size_type i = 0;
 233       I it = e;
 234       for(I it2 = e; i != c.size(); --it, ++i){
 235          BOOST_TEST(it == it2--);
 236          I ittmp(it);
 237          I*iaddr = &ittmp;
 238          BOOST_TEST(&(--ittmp) == iaddr);
 239          BOOST_TEST(ittmp == it2);
 240          BOOST_TEST((++ittmp) == it);
 241       }
 242       BOOST_TEST(i == c.size());
 243       BOOST_TEST(it == b);
 244    }
 245 }
 246
 247 template<class C>
 248 void test_iterator_bidirectional_and_compatible(C &c)
 249 {
 250    test_iterator_forward_and_compatible(c);
 251    test_iterator_bidirectional_functions(c, c.begin(),   c.end());
 252    test_iterator_bidirectional_functions(c, c.cbegin(),  c.cend());
 253    test_iterator_bidirectional_functions(c, c.rbegin(),  c.rend());
 254    test_iterator_bidirectional_functions(c, c.crbegin(), c.crend());
 255 }
 256
 257 template<class C, class I>
 258 void test_iterator_random_functions(C const &c, I const b, I const e)
 259 {
 260    typedef typename C::size_type size_type;
 261    {
 262       I it = b;
 263       for(size_type i = 0, m = c.size(); i != m; ++i, ++it){
 264          BOOST_TEST(i == size_type(it - b));
 265          BOOST_TEST(b[i] == *it);
 266          BOOST_TEST(&b[i] == &*it);
 267          BOOST_TEST((b + i) == it);
 268          BOOST_TEST((i + b) == it);
 269          BOOST_TEST(b == (it - i));
 270          I tmp(b);
 271          BOOST_TEST((tmp+=i) == it);
 272          tmp = it;
 273          BOOST_TEST(b == (tmp-=i));
 274       }
 275       BOOST_TEST(c.size() == size_type(e - b));
 276    }
 277    {
 278       I it(b), itb(b);
 279       if(b != e){
 280          for(++it; it != e; ++it){
 281             BOOST_TEST(itb < it);
 282             BOOST_TEST(itb <= it);
 283             BOOST_TEST(!(itb > it));
 284             BOOST_TEST(!(itb >= it));
 285             BOOST_TEST(it > itb);
 286             BOOST_TEST(it >= itb);
 287             BOOST_TEST(!(it < itb));
 288             BOOST_TEST(!(it <= itb));
 289             BOOST_TEST(it >= it);
 290             BOOST_TEST(it <= it);
 291             itb = it;
 292          }
 293       }
 294    }
 295 }
 296
 297 template<class C>
 298 void test_iterator_random_and_compatible(C &c)
 299 {
 300    test_iterator_bidirectional_and_compatible(c);
 301    test_iterator_random_functions(c, c.begin(),   c.end());
 302    test_iterator_random_functions(c, c.cbegin(),  c.cend());
 303    test_iterator_random_functions(c, c.rbegin(),  c.rend());
 304    test_iterator_random_functions(c, c.crbegin(), c.crend());
 305 }
 306
 307 ////////////////////////
 308
 309 template<class C>
 310 void test_iterator_forward(C &c)
 311 {
 312    typedef typename C::iterator                 iterator;
 313    typedef typename C::const_iterator           const_iterator;
 314    typedef typename get_reverse_iterator<C>::type        reverse_iterator;
 315    typedef typename get_const_reverse_iterator<C>::type  const_reverse_iterator;
 316    typedef iterator_traits<iterator>         nit_traits;
 317    typedef iterator_traits<const_iterator>   cit_traits;
 318    typedef iterator_traits<reverse_iterator>         rnit_traits;
 319    typedef iterator_traits<const_reverse_iterator>   crit_traits;
 320
 321    using boost::intrusive::detail::is_same;
 322    //iterator_category
 323    BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename nit_traits::iterator_category>::value));
 324    BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename cit_traits::iterator_category>::value));
 325    BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename rnit_traits::iterator_category>::value));
 326    BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename crit_traits::iterator_category>::value));
 327    //Test dynamic
 328    test_iterator_forward_and_compatible(c);
 329 }
 330
 331 template<class C>
 332 void test_iterator_bidirectional(C &c)
 333 {
 334    typedef typename C::iterator        iterator;
 335    typedef typename C::const_iterator  const_iterator;
 336    typedef typename C::reverse_iterator        reverse_iterator;
 337    typedef typename C::const_reverse_iterator  const_reverse_iterator;
 338    typedef iterator_traits<iterator>         nit_traits;
 339    typedef iterator_traits<const_iterator>   cit_traits;
 340    typedef iterator_traits<reverse_iterator>         rnit_traits;
 341    typedef iterator_traits<const_reverse_iterator>   crit_traits;
 342
 343    using boost::intrusive::detail::is_same;
 344    //iterator_category
 345    BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename nit_traits::iterator_category>::value));
 346    BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename cit_traits::iterator_category>::value));
 347    BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename rnit_traits::iterator_category>::value));
 348    BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename crit_traits::iterator_category>::value));
 349    //Test dynamic
 350    test_iterator_bidirectional_and_compatible(c);
 351 }
 352
 353 template<class C>
 354 void test_iterator_random(C &c)
 355 {
 356    typedef typename C::iterator        iterator;
 357    typedef typename C::const_iterator  const_iterator;
 358    typedef typename C::reverse_iterator        reverse_iterator;
 359    typedef typename C::const_reverse_iterator  const_reverse_iterator;
 360    typedef iterator_traits<iterator>         nit_traits;
 361    typedef iterator_traits<const_iterator>   cit_traits;
 362    typedef iterator_traits<reverse_iterator>         rnit_traits;
 363    typedef iterator_traits<const_reverse_iterator>   crit_traits;
 364
 365    using boost::intrusive::detail::is_same;
 366    //iterator_category
 367    BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename nit_traits::iterator_category>::value));
 368    BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename cit_traits::iterator_category>::value));
 369    BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename rnit_traits::iterator_category>::value));
 370    BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename crit_traits::iterator_category>::value));
 371    //Test dynamic
 372    test_iterator_random_and_compatible(c);
 373 }
 374
 375 }}}   //boost::container::test