libs/intrusive/test/any_test.cpp

   1
   2 /////////////////////////////////////////////////////////////////////////////
   3 //
   4 // (C) Copyright Olaf Krzikalla 2004-2006.
   5 // (C) Copyright Ion Gaztanaga  2006-2013.
   6 //
   7 // Distributed under the Boost Software License, Version 1.0.
   8 //    (See accompanying file LICENSE_1_0.txt or copy at
   9 //          http://www.boost.org/LICENSE_1_0.txt)
  10 //
  11 // See http://www.boost.org/libs/intrusive for documentation.
  12 //
  13 /////////////////////////////////////////////////////////////////////////////
  14 #include<boost/intrusive/any_hook.hpp>
  15 #include<boost/intrusive/slist.hpp>
  16 #include<boost/intrusive/rbtree.hpp>
  17 #include<boost/intrusive/list.hpp>
  18 #include<boost/intrusive/avltree.hpp>
  19 #include<boost/intrusive/sgtree.hpp>
  20 #include<boost/intrusive/splaytree.hpp>
  21 #include<boost/intrusive/treap.hpp>
  22 #include<boost/intrusive/hashtable.hpp>
  23 #include<boost/functional/hash.hpp>
  24 #include <vector>    //std::vector
  25 #include <cstddef>   //std::size_t
  26
  27 using namespace boost::intrusive;
  28
  29 class MyClass : public any_base_hook<>
  30 {
  31    int int_;
  32
  33    public:
  34    //This is a member hook
  35    any_member_hook<> member_hook_;
  36
  37    MyClass(int i = 0)
  38       :  int_(i)
  39    {}
  40
  41    int get() const
  42    {  return this->int_;  }
  43
  44    friend bool operator  < (const MyClass &l, const MyClass &r)
  45    {  return l.int_ < r.int_; }
  46
  47    friend bool operator == (const MyClass &l, const MyClass &r)
  48    {  return l.int_ == r.int_; }
  49
  50    friend std::size_t hash_value(const MyClass &o)
  51    {  return boost::hash<int>()(o.get());  }
  52
  53    friend bool priority_order(const MyClass &a, const MyClass &b)
  54    {  return a.int_ < b.int_;  }
  55 };
  56
  57
  58 void instantiation_test()
  59 {
  60    typedef member_hook< MyClass, any_member_hook<>, &MyClass::member_hook_> MemberHook;
  61    typedef base_hook< any_base_hook<> > BaseHook;
  62
  63    MyClass myclass;
  64    {
  65       slist < MyClass, any_to_slist_hook< BaseHook > > slist_base;
  66       slist_base.push_front(myclass);
  67    }
  68    {
  69       slist < MyClass, any_to_slist_hook< MemberHook > > slist_member;
  70       slist_member.push_front(myclass);
  71    }
  72    {
  73       list < MyClass, any_to_list_hook< BaseHook > > list_base;
  74       list_base.push_front(myclass);
  75    }
  76    {
  77       list < MyClass, any_to_list_hook< MemberHook > > list_member;
  78       list_member.push_front(myclass);
  79    }
  80    {
  81       rbtree < MyClass, any_to_set_hook< BaseHook > >  rbtree_base;
  82       rbtree_base.insert_unique(myclass);
  83    }
  84    {
  85       rbtree < MyClass, any_to_set_hook< MemberHook > > rbtree_member;
  86       rbtree_member.insert_unique(myclass);
  87    }
  88    {
  89       avltree < MyClass, any_to_avl_set_hook< BaseHook > > avltree_base;
  90       avltree_base.insert_unique(myclass);
  91    }
  92    {
  93       avltree < MyClass, any_to_avl_set_hook< MemberHook > > avltree_member;
  94       avltree_member.insert_unique(myclass);
  95    }
  96    {
  97       sgtree < MyClass, any_to_bs_set_hook< BaseHook > > sgtree_base;
  98       sgtree_base.insert_unique(myclass);
  99    }
 100    {
 101       sgtree < MyClass, any_to_bs_set_hook< MemberHook > > sgtree_member;
 102       sgtree_member.insert_unique(myclass);
 103    }
 104    {
 105       treap < MyClass, any_to_bs_set_hook< BaseHook > > treap_base;
 106       treap_base.insert_unique(myclass);
 107    }
 108    {
 109       treap < MyClass, any_to_bs_set_hook< MemberHook > > treap_member;
 110       treap_member.insert_unique(myclass);
 111    }
 112    {
 113       splaytree < MyClass, any_to_bs_set_hook< BaseHook > > splaytree_base;
 114       splaytree_base.insert_unique(myclass);
 115    }
 116    {
 117       splaytree < MyClass, any_to_bs_set_hook< MemberHook > > splaytree_member;
 118       splaytree_member.insert_unique(myclass);
 119    }
 120    typedef unordered_bucket<any_to_unordered_set_hook< BaseHook > >::type bucket_type;
 121    typedef unordered_default_bucket_traits<any_to_unordered_set_hook< BaseHook > >::type bucket_traits;
 122    bucket_type buckets[2];
 123    {
 124       hashtable < MyClass, any_to_unordered_set_hook< BaseHook > >
 125          hashtable_base(bucket_traits(&buckets[0], 1));
 126       hashtable_base.insert_unique(myclass);
 127    }
 128    {
 129       hashtable < MyClass, any_to_unordered_set_hook< MemberHook > >
 130          hashtable_member(bucket_traits(&buckets[1], 1));
 131       hashtable_member.insert_unique(myclass);
 132    }
 133 }
 134
 135 bool simple_slist_test()
 136 {
 137    //Define an slist that will store MyClass using the public base hook
 138    typedef any_to_slist_hook< base_hook< any_base_hook<> > >BaseOption;
 139    typedef slist<MyClass, BaseOption, constant_time_size<false> > BaseList;
 140
 141    //Define an slist that will store MyClass using the public member hook
 142    typedef any_to_slist_hook< member_hook<MyClass, any_member_hook<>, &MyClass::member_hook_> > MemberOption;
 143    typedef slist<MyClass, MemberOption> MemberList;
 144
 145    typedef std::vector<MyClass>::iterator VectIt;
 146    typedef std::vector<MyClass>::reverse_iterator VectRit;
 147
 148    //Create several MyClass objects, each one with a different value
 149    std::vector<MyClass> values;
 150    for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));
 151
 152    BaseList baselist;
 153    MemberList memberlist;
 154
 155    //Now insert them in the reverse order in the base hook list
 156    for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
 157       baselist.push_front(*it);
 158
 159    //Now insert them in the same order as in vector in the member hook list
 160    for(BaseList::iterator it(baselist.begin()), itend(baselist.end())
 161       ; it != itend; ++it){
 162       memberlist.push_front(*it);
 163    }
 164
 165    //Now test lists
 166    {
 167       BaseList::iterator bit(baselist.begin());
 168       MemberList::iterator mit(memberlist.begin());
 169       VectRit rit(values.rbegin()), ritend(values.rend());
 170       VectIt  it(values.begin()), itend(values.end());
 171
 172       //Test the objects inserted in the base hook list
 173       for(; rit != ritend; ++rit, ++bit)
 174          if(&*bit != &*rit)   return false;
 175
 176       //Test the objects inserted in the member hook list
 177       for(; it != itend; ++it, ++mit)
 178          if(&*mit != &*it)    return false;
 179    }
 180    return true;
 181 }
 182
 183 int main()
 184 {
 185    if(!simple_slist_test())
 186       return 1;
 187    instantiation_test();
 188    return 0;
 189 }