ceph/src/boost/libs/intrusive/test/default_hook_test.cpp

   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 #include <boost/intrusive/list.hpp>
  13 #include <boost/intrusive/slist.hpp>
  14 #include <boost/intrusive/set.hpp>
  15 #include <boost/intrusive/unordered_set.hpp>
  16 #include <boost/intrusive/splay_set.hpp>
  17 #include <boost/intrusive/avl_set.hpp>
  18 #include <boost/intrusive/sg_set.hpp>
  19 #include <boost/intrusive/treap_set.hpp>
  20 #include <boost/intrusive/bs_set.hpp>
  21 #include <boost/intrusive/pointer_traits.hpp>
  22 #include "smart_ptr.hpp"
  23 #include <vector>
  24
  25 using namespace boost::intrusive;
  26
  27 class MyClass
  28
  29 :  public list_base_hook
  30    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  31 ,  public slist_base_hook
  32    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  33 ,  public set_base_hook
  34    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  35 ,  public unordered_set_base_hook
  36    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  37 ,  public avl_set_base_hook
  38    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  39 ,  public bs_set_base_hook
  40    < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
  41 {
  42    int int_;
  43
  44    public:
  45    MyClass(int i)
  46       :  int_(i)
  47    {}
  48
  49    friend bool operator<(const MyClass &l, const MyClass &r)
  50    {  return l.int_ < r.int_; }
  51
  52    friend bool operator==(const MyClass &l, const MyClass &r)
  53    {  return l.int_ == r.int_; }
  54
  55    friend std::size_t hash_value(const MyClass &v)
  56    {  return boost::hash_value(v.int_); }
  57
  58    friend bool priority_order(const MyClass &l, const MyClass &r)
  59    {  return l.int_ < r.int_; }
  60 };
  61
  62 //Define a list that will store MyClass using the public base hook
  63 typedef list<MyClass>            List;
  64 typedef slist<MyClass>           Slist;
  65 typedef set<MyClass>             Set;
  66 typedef unordered_set<MyClass>   USet;
  67 typedef avl_set<MyClass>         AvlSet;
  68 typedef splay_set<MyClass>       SplaySet;
  69 typedef treap_set<MyClass>       TreapSet;
  70 typedef sg_set<MyClass>          SgSet;
  71 typedef bs_set<MyClass>          BsSet;
  72
  73 int main()
  74 {
  75    typedef std::vector<MyClass>::iterator VectIt;
  76    typedef std::vector<MyClass>::reverse_iterator VectRit;
  77
  78    //Create several MyClass objects, each one with a different value
  79    std::vector<MyClass> values;
  80    for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));
  81
  82    {
  83       List  my_list;
  84       Slist my_slist;
  85       Set   my_set;
  86       USet::bucket_type buckets[100];
  87       USet  my_uset(USet::bucket_traits(pointer_traits<USet::bucket_ptr>::pointer_to(*buckets), 100));
  88       AvlSet   my_avlset;
  89       SplaySet my_splayset;
  90
  91       //Now insert them in the reverse order
  92       //in the base hook intrusive list
  93       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
  94          my_list.push_front(*it);
  95          my_slist.push_front(*it);
  96          my_set.insert(*it);
  97          my_uset.insert(*it);
  98          my_avlset.insert(*it);
  99          my_splayset.insert(*it);
 100       }
 101
 102       //Now test lists
 103       {
 104          List::const_iterator  list_it(my_list.cbegin());
 105          Slist::const_iterator slist_it(my_slist.cbegin());
 106          Set::const_reverse_iterator set_rit(my_set.crbegin());
 107          AvlSet::const_reverse_iterator avl_set_rit(my_avlset.crbegin());
 108          SplaySet::const_reverse_iterator splay_set_rit(my_splayset.crbegin());
 109
 110          VectRit vect_it(values.rbegin()), vect_itend(values.rend());
 111
 112          //Test the objects inserted in the base hook list
 113          for(; vect_it != vect_itend
 114             ; ++vect_it, ++list_it
 115             , ++slist_it, ++set_rit
 116             , ++avl_set_rit
 117             , ++splay_set_rit
 118             ){
 119             if(&*list_it  != &*vect_it)      return 1;
 120             if(&*slist_it != &*vect_it)      return 1;
 121             if(&*set_rit       != &*vect_it)      return 1;
 122             if(&*avl_set_rit   != &*vect_it)  return 1;
 123             if(&*splay_set_rit != &*vect_it)return 1;
 124             if(my_uset.find(*set_rit) == my_uset.cend())  return 1;
 125          }
 126       }
 127    }
 128    //Since treap_set, sg_set & bs_set reuse the hook, treat them apart
 129    {
 130       TreapSet my_treapset;
 131       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
 132          my_treapset.insert(*it);
 133       }
 134
 135       TreapSet::const_reverse_iterator treap_set_rit(my_treapset.crbegin());
 136       VectRit vect_it(values.rbegin()), vect_itend(values.rend());
 137       for(; vect_it != vect_itend; ++vect_it, ++treap_set_rit){
 138          if(&*treap_set_rit    != &*vect_it)   return 1;
 139       }
 140    }
 141    {
 142       SgSet    my_sgset;
 143       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
 144          my_sgset.insert(*it);
 145       }
 146
 147       SgSet::const_reverse_iterator sg_set_rit(my_sgset.crbegin());
 148       VectRit vect_it(values.rbegin()), vect_itend(values.rend());
 149       for(; vect_it != vect_itend; ++vect_it, ++sg_set_rit){
 150          if(&*sg_set_rit    != &*vect_it)   return 1;
 151       }
 152    }
 153    {
 154       BsSet    my_bsset;
 155       for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
 156          my_bsset.insert(*it);
 157       }
 158
 159       BsSet::const_reverse_iterator bs_set_rit(my_bsset.crbegin());
 160       VectRit vect_it(values.rbegin()), vect_itend(values.rend());
 161       for(; vect_it != vect_itend; ++vect_it, ++bs_set_rit){
 162          if(&*bs_set_rit    != &*vect_it)   return 1;
 163       }
 164    }
 165    return 0;
 166 }