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