Boost_1_39_0/libs/intrusive/test/stateful_value_traits_test.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2008
   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/functional/hash.hpp>
  17 #include <boost/pointer_to_other.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 boost::pointer_to_other
  50       <node_ptr, T>::type                                      pointer;
  51    typedef typename boost::pointer_to_other
  52       <node_ptr, const T>::type                                const_pointer;
  53    static const link_mode_type link_mode = normal_link;
  54
  55    stateful_value_traits(pointer values, node_ptr node_array)
  56       :  values_(values),  node_array_(node_array)
  57    {}
  58
  59    node_ptr to_node_ptr (value_type &value)
  60    {  return node_array_ + (&value - values_); }
  61
  62    const_node_ptr to_node_ptr (const value_type &value) const
  63    {  return node_array_ + (&value - values_); }
  64
  65    pointer to_value_ptr(node_ptr n)
  66    {  return values_ + (n - node_array_); }
  67
  68    const_pointer to_value_ptr(const_node_ptr n) const
  69    {  return values_ + (n - node_array_); }
  70
  71    pointer  values_;
  72    node_ptr node_array_;
  73 };
  74
  75 //Define a list that will store MyClass using the external hook
  76 typedef stateful_value_traits< MyClass, list_node_traits<void*> > list_traits;
  77 typedef list<MyClass, value_traits<list_traits> > List;
  78
  79 //Define a slist that will store MyClass using the external hook
  80 typedef stateful_value_traits< MyClass, slist_node_traits<void*> > slist_traits;
  81 typedef slist<MyClass, value_traits<slist_traits> > Slist;
  82
  83 //Define a set that will store MyClass using the external hook
  84 typedef stateful_value_traits< MyClass, rbtree_node_traits<void*> > rbtree_traits;
  85 typedef set<MyClass, value_traits<rbtree_traits> > Set;
  86
  87 //uset uses the same traits as slist
  88 typedef unordered_set<MyClass, value_traits<slist_traits> > Uset;
  89
  90
  91 typedef list_traits::node     list_node_t;
  92 typedef slist_traits::node    slist_node_t;
  93 typedef rbtree_traits::node   rbtree_node_t;
  94
  95 const int NumElements = 100;
  96
  97 MyClass        values    [NumElements];
  98 list_node_t    list_hook_array   [NumElements];
  99 slist_node_t   slist_hook_array  [NumElements];
 100 rbtree_node_t  rbtree_hook_array [NumElements];
 101 slist_node_t   uset_hook_array   [NumElements];
 102
 103 int main()
 104 {
 105    //Create several MyClass objects, each one with a different value
 106    for(int i = 0; i < NumElements; ++i)
 107       values[i].int_ = i;
 108
 109    Uset::bucket_type buckets[NumElements];
 110
 111    List  my_list (list_traits (values, list_hook_array));
 112    Slist my_slist(slist_traits(values, slist_hook_array));
 113    Set   my_set  (std::less<MyClass>(), rbtree_traits(values, rbtree_hook_array));
 114    Uset  my_uset ( Uset::bucket_traits(buckets, NumElements)
 115                  , boost::hash<MyClass>()
 116                  , std::equal_to<MyClass>()
 117                  , slist_traits(values, uset_hook_array)
 118                  );
 119
 120    //Now insert them in containers
 121    for(MyClass * it(&values[0]), *itend(&values[NumElements])
 122       ; it != itend
 123       ; ++it){
 124       my_list.push_front(*it);
 125       my_slist.push_front(*it);
 126       my_set.insert(*it);
 127       my_uset.insert(*it);
 128    }
 129
 130    //Now test lists
 131    {
 132       List::const_iterator   list_it (my_list.cbegin());
 133       Slist::const_iterator  slist_it(my_slist.cbegin());
 134       Set::const_reverse_iterator set_rit(my_set.crbegin());
 135       MyClass *it_val(&values[NumElements-1]), *it_rbeg_val(&values[0]-1);
 136
 137       //Test the objects inserted in the base hook list
 138       for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++set_rit){
 139          if(&*list_it  != &*it_val)   return 1;
 140          if(&*slist_it != &*it_val)   return 1;
 141          if(&*set_rit  != &*it_val)   return 1;
 142          if(my_uset.find(*it_val) == my_uset.cend())  return 1;
 143       }
 144    }
 145
 146    return 0;
 147 }