ceph/src/boost/libs/intrusive/test/stateful_value_traits_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/container_hash/hash.hpp>
  17 #include <boost/intrusive/pointer_traits.hpp>
  18 #include <vector>
  19
  20 using namespace boost::intrusive;
  21
  22 class MyClass
  23 {
  24    public:
  25    int int_;
  26
  27    MyClass(int i = 0)
  28       :  int_(i)
  29    {}
  30
  31    friend bool operator<(const MyClass &l, const MyClass &r)
  32    {  return l.int_ < r.int_; }
  33
  34    friend bool operator==(const MyClass &l, const MyClass &r)
  35    {  return l.int_ == r.int_; }
  36
  37    friend std::size_t hash_value(const MyClass &v)
  38    {  return boost::hash_value(v.int_); }
  39 };
  40
  41 template<class T, class NodeTraits>
  42 struct stateful_value_traits
  43 {
  44    typedef NodeTraits                                          node_traits;
  45    typedef typename node_traits::node                          node;
  46    typedef typename node_traits::node_ptr                      node_ptr;
  47    typedef typename node_traits::const_node_ptr                const_node_ptr;
  48    typedef T                                                   value_type;
  49    typedef typename pointer_traits<node_ptr>::
  50       template rebind_pointer<T>::type                         pointer;
  51    typedef typename pointer_traits<node_ptr>::
  52       template rebind_pointer<const T>::type                   const_pointer;
  53
  54    static const link_mode_type link_mode = normal_link;
  55
  56    stateful_value_traits(pointer vals, node_ptr node_array)
  57       :  values_(vals),  node_array_(node_array)
  58    {}
  59
  60    node_ptr to_node_ptr (value_type &value) const
  61    {  return node_array_ + (&value - values_); }
  62
  63    const_node_ptr to_node_ptr (const value_type &value) const
  64    {  return node_array_ + (&value - values_); }
  65
  66    pointer to_value_ptr(node_ptr n) const
  67    {  return values_ + (n - node_array_); }
  68
  69    const_pointer to_value_ptr(const_node_ptr n) const
  70    {  return values_ + (n - node_array_); }
  71
  72    pointer  values_;
  73    node_ptr node_array_;
  74 };
  75
  76 //Define a list that will store MyClass using the external hook
  77 typedef stateful_value_traits< MyClass, list_node_traits<void*> > list_traits;
  78 typedef list<MyClass, value_traits<list_traits> > List;
  79
  80 //Define a slist that will store MyClass using the external hook
  81 typedef stateful_value_traits< MyClass, slist_node_traits<void*> > slist_traits;
  82 typedef slist<MyClass, value_traits<slist_traits> > Slist;
  83
  84 //Define a set that will store MyClass using the external hook
  85 typedef stateful_value_traits< MyClass, rbtree_node_traits<void*> > rbtree_traits;
  86 typedef set<MyClass, value_traits<rbtree_traits> > Set;
  87
  88 //uset uses the same traits as slist
  89 typedef unordered_set<MyClass, value_traits<slist_traits> > Uset;
  90
  91
  92 typedef list_traits::node     list_node_t;
  93 typedef slist_traits::node    slist_node_t;
  94 typedef rbtree_traits::node   rbtree_node_t;
  95
  96 const int NumElements = 100;
  97
  98 MyClass        values    [NumElements];
  99 list_node_t    list_hook_array   [NumElements];
 100 slist_node_t   slist_hook_array  [NumElements];
 101 rbtree_node_t  rbtree_hook_array [NumElements];
 102 slist_node_t   uset_hook_array   [NumElements];
 103
 104 int main()
 105 {
 106    //Create several MyClass objects, each one with a different value
 107    for(int i = 0; i < NumElements; ++i)
 108       values[i].int_ = i;
 109
 110    Uset::bucket_type buckets[NumElements];
 111
 112    List  my_list (list_traits (values, list_hook_array));
 113    Slist my_slist(slist_traits(values, slist_hook_array));
 114    Set   my_set  (std::less<MyClass>(), rbtree_traits(values, rbtree_hook_array));
 115    Uset  my_uset ( Uset::bucket_traits(buckets, NumElements)
 116                  , boost::hash<MyClass>()
 117                  , std::equal_to<MyClass>()
 118                  , slist_traits(values, uset_hook_array)
 119                  );
 120
 121    //Now insert them in containers
 122    for(MyClass * it(&values[0]), *itend(&values[NumElements])
 123       ; it != itend
 124       ; ++it){
 125       my_list.push_front(*it);
 126       if(&*my_list.iterator_to(*it) != &my_list.front())
 127          return 1;
 128       my_slist.push_front(*it);
 129       if(&*my_slist.iterator_to(*it) != &my_slist.front())
 130          return 1;
 131       Set::iterator sit = my_set.insert(*it).first;
 132       if(&*my_set.iterator_to(*it) != &*sit)
 133          return 1;
 134       Uset::iterator uit = my_uset.insert(*it).first;
 135       my_uset.insert(*it);
 136       if(&*my_uset.iterator_to(*it) != &*uit)
 137          return 1;
 138    }
 139
 140    //Now test lists
 141    {
 142       List::const_iterator   list_it (my_list.cbegin());
 143       Slist::const_iterator  slist_it(my_slist.cbegin());
 144       Set::const_reverse_iterator set_rit(my_set.crbegin());
 145       MyClass *it_val(&values[NumElements]), *it_rbeg_val(&values[0]);
 146
 147       //Test the objects inserted in the base hook list
 148       for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++set_rit){
 149          if(&*list_it  != &it_val[-1])   return 1;
 150          if(&*slist_it != &it_val[-1])   return 1;
 151          if(&*set_rit  != &it_val[-1])   return 1;
 152          if(my_uset.find(it_val[-1]) == my_uset.cend())  return 1;
 153       }
 154    }
 155
 156    return 0;
 157 }