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/avl_set.hpp>
17 #include <boost/intrusive/sg_set.hpp>
18 #include <boost/intrusive/splay_set.hpp>
19 #include <boost/intrusive/bs_set.hpp>
20 #include <boost/intrusive/treap_set.hpp>
21 #include <boost/intrusive/detail/mpl.hpp>
22 #include <boost/intrusive/pointer_traits.hpp>
23 #include <boost/static_assert.hpp>
24 #include "smart_ptr.hpp"
25 #include <vector>
26
27 using namespace boost::intrusive;
28
29 struct my_tag;
30 struct my_tag2;
31 struct my_tag3;
32
33 typedef make_bs_set_base_hook
34 < void_pointer<smart_ptr<void> >, link_mode<normal_link>
35 , tag<my_tag> >::type TreapHook;
36 typedef make_bs_set_base_hook
37 < void_pointer<smart_ptr<void> >, link_mode<normal_link>
38 , tag<my_tag2> >::type SplayHook;
39 typedef make_bs_set_base_hook
40 < void_pointer<smart_ptr<void> >, link_mode<normal_link>
41 , tag<my_tag3> >::type BsHook;
42
43 class MyClass
44 : public make_list_base_hook
45 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
46 , public make_slist_base_hook
47 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
48 , public make_set_base_hook
49 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
50 , public make_unordered_set_base_hook
51 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
52 , public make_avl_set_base_hook
53 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
54 , public make_bs_set_base_hook
55 < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
56 , public TreapHook
57 , public SplayHook
58 , public BsHook
59 {
60 int int_;
61
62 public:
MyClass(int i)63 MyClass(int i)
64 : int_(i)
65 {}
66
operator <(const MyClass & l,const MyClass & r)67 friend bool operator<(const MyClass &l, const MyClass &r)
68 { return l.int_ < r.int_; }
69
operator ==(const MyClass & l,const MyClass & r)70 friend bool operator==(const MyClass &l, const MyClass &r)
71 { return l.int_ == r.int_; }
72
hash_value(const MyClass & v)73 friend std::size_t hash_value(const MyClass &v)
74 { return boost::hash_value(v.int_); }
75
priority_order(const MyClass & l,const MyClass & r)76 friend bool priority_order(const MyClass &l, const MyClass &r)
77 { return l.int_ < r.int_; }
78 };
79
80 //Define a list that will store MyClass using the public base hook
81 typedef make_list<MyClass>::type List;
82 typedef make_slist<MyClass>::type Slist;
83 typedef make_set<MyClass>::type Set;
84 typedef make_unordered_set<MyClass>::type USet;
85
86 typedef make_avl_set<MyClass>::type AvlSet;
87 typedef make_sg_set<MyClass>::type SgSet;
88 typedef make_treap_set<MyClass
89 , base_hook<TreapHook> >::type TreapSet;
90 typedef make_splay_set<MyClass
91 , base_hook<SplayHook> >::type SplaySet;
92 typedef make_bs_set<MyClass
93 , base_hook<BsHook> >::type BsSet;
94
main()95 int main()
96 {
97 typedef std::vector<MyClass>::iterator VectIt;
98 typedef std::vector<MyClass>::reverse_iterator VectRit;
99
100 //Create several MyClass objects, each one with a different value
101 std::vector<MyClass> values;
102 for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
103
104 USet::bucket_type buckets[100];
105
106 List my_list;
107 Slist my_slist;
108 Set my_set;
109 USet my_uset(USet::bucket_traits
110 (pointer_traits<USet::bucket_ptr>::pointer_to(buckets[0]), 100));
111
112 AvlSet my_avlset;
113 SplaySet my_splayset;
114 BsSet my_bsset;
115 SgSet my_sgset;
116 TreapSet my_treapset;
117
118 //Now insert them in containers
119 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
120 my_list.push_front(*it);
121 my_slist.push_front(*it);
122 my_set.insert(*it);
123 my_uset.insert(*it);
124 my_avlset.insert(*it);
125 my_splayset.insert(*it);
126 my_bsset.insert(*it);
127 my_sgset.insert(*it);
128 my_treapset.insert(*it);
129 }
130
131 //Now test lists
132 {
133 List::const_iterator list_it(my_list.cbegin());
134 Slist::const_iterator slist_it(my_slist.cbegin());
135 Set::const_reverse_iterator set_rit(my_set.crbegin());
136
137 AvlSet::const_reverse_iterator avlset_rit(my_avlset.crbegin());
138 SplaySet::const_reverse_iterator splayset_rit(my_splayset.crbegin());
139 BsSet::const_reverse_iterator bsset_rit(my_bsset.crbegin());
140 SgSet::const_reverse_iterator sgset_rit(my_sgset.crbegin());
141 TreapSet::const_reverse_iterator treapset_rit(my_treapset.crbegin());
142
143 VectRit vect_it(values.rbegin()), vect_itend(values.rend());
144
145 //Test the objects inserted in the base hook list
146 for( ; vect_it != vect_itend
147 ; ++vect_it, ++list_it, ++slist_it, ++set_rit
148 , ++avlset_rit, ++splayset_rit, ++bsset_rit, ++sgset_rit, ++treapset_rit
149 ){
150 if(&*list_it != &*vect_it) return 1;
151 if(&*slist_it != &*vect_it) return 1;
152 if(&*set_rit != &*vect_it) return 1;
153 if(my_uset.find(*set_rit) == my_uset.cend()) return 1;
154 if(&*avlset_rit != &*vect_it) return 1;
155 if(&*splayset_rit != &*vect_it) return 1;
156 if(&*bsset_rit != &*vect_it) return 1;
157 if(&*sgset_rit != &*vect_it) return 1;
158 if(&*treapset_rit != &*vect_it) return 1;
159 }
160 }
161
162 //Check defined types and implicitly defined types are equal
163 BOOST_STATIC_ASSERT((detail::is_same<make_list_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
164 ,make_list_base_hook<>::type
165 >::value));
166
167 BOOST_STATIC_ASSERT((detail::is_same<make_slist_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
168 ,make_slist_base_hook<>::type
169 >::value));
170
171 BOOST_STATIC_ASSERT((detail::is_same<make_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
172 ,make_set_base_hook<>::type
173 >::value));
174
175 BOOST_STATIC_ASSERT((detail::is_same<make_unordered_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
176 ,make_unordered_set_base_hook<>::type
177 >::value));
178
179 BOOST_STATIC_ASSERT((detail::is_same<make_avl_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
180 ,make_avl_set_base_hook<>::type
181 >::value));
182
183 BOOST_STATIC_ASSERT((detail::is_same<make_bs_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
184 ,make_bs_set_base_hook<>::type
185 >::value));
186
187 //Check defined types and implicitly defined types are unequal
188 BOOST_STATIC_ASSERT(!(detail::is_same<make_list_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
189 ,make_list_base_hook<>::type
190 >::value));
191
192 BOOST_STATIC_ASSERT(!(detail::is_same<make_slist_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
193 ,make_slist_base_hook<>::type
194 >::value));
195
196 BOOST_STATIC_ASSERT(!(detail::is_same<make_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
197 ,make_set_base_hook<>::type
198 >::value));
199
200 BOOST_STATIC_ASSERT(!(detail::is_same<make_unordered_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
201 ,make_unordered_set_base_hook<>::type
202 >::value));
203
204 BOOST_STATIC_ASSERT(!(detail::is_same<make_avl_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
205 ,make_avl_set_base_hook<>::type
206 >::value));
207
208 BOOST_STATIC_ASSERT(!(detail::is_same<make_bs_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
209 ,make_bs_set_base_hook<>::type
210 >::value));
211
212 return 0;
213 }
214