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/splay_set.hpp>
17 #include <boost/intrusive/avl_set.hpp>
18 #include <boost/intrusive/sg_set.hpp>
19 #include <boost/intrusive/treap_set.hpp>
20 #include <boost/intrusive/bs_set.hpp>
21 #include <boost/intrusive/pointer_traits.hpp>
22 #include "smart_ptr.hpp"
23 #include <vector>
24
25 using namespace boost::intrusive;
26
27 class MyClass
28
29 : public list_base_hook
30 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
31 , public slist_base_hook
32 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
33 , public set_base_hook
34 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
35 , public unordered_set_base_hook
36 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
37 , public avl_set_base_hook
38 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
39 , public bs_set_base_hook
40 < void_pointer<smart_ptr<void> >, link_mode<safe_link> >
41 {
42 int int_;
43
44 public:
MyClass(int i)45 MyClass(int i)
46 : int_(i)
47 {}
48
operator <(const MyClass & l,const MyClass & r)49 friend bool operator<(const MyClass &l, const MyClass &r)
50 { return l.int_ < r.int_; }
51
operator ==(const MyClass & l,const MyClass & r)52 friend bool operator==(const MyClass &l, const MyClass &r)
53 { return l.int_ == r.int_; }
54
hash_value(const MyClass & v)55 friend std::size_t hash_value(const MyClass &v)
56 { return boost::hash_value(v.int_); }
57
priority_order(const MyClass & l,const MyClass & r)58 friend bool priority_order(const MyClass &l, const MyClass &r)
59 { return l.int_ < r.int_; }
60 };
61
62 //Define a list that will store MyClass using the public base hook
63 typedef list<MyClass> List;
64 typedef slist<MyClass> Slist;
65 typedef set<MyClass> Set;
66 typedef unordered_set<MyClass> USet;
67 typedef avl_set<MyClass> AvlSet;
68 typedef splay_set<MyClass> SplaySet;
69 typedef treap_set<MyClass> TreapSet;
70 typedef sg_set<MyClass> SgSet;
71 typedef bs_set<MyClass> BsSet;
72
main()73 int main()
74 {
75 typedef std::vector<MyClass>::iterator VectIt;
76 typedef std::vector<MyClass>::reverse_iterator VectRit;
77
78 //Create several MyClass objects, each one with a different value
79 std::vector<MyClass> values;
80 for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
81
82 {
83 List my_list;
84 Slist my_slist;
85 Set my_set;
86 USet::bucket_type buckets[100];
87 USet my_uset(USet::bucket_traits(pointer_traits<USet::bucket_ptr>::pointer_to(*buckets), 100));
88 AvlSet my_avlset;
89 SplaySet my_splayset;
90
91 //Now insert them in the reverse order
92 //in the base hook intrusive list
93 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
94 my_list.push_front(*it);
95 my_slist.push_front(*it);
96 my_set.insert(*it);
97 my_uset.insert(*it);
98 my_avlset.insert(*it);
99 my_splayset.insert(*it);
100 }
101
102 //Now test lists
103 {
104 List::const_iterator list_it(my_list.cbegin());
105 Slist::const_iterator slist_it(my_slist.cbegin());
106 Set::const_reverse_iterator set_rit(my_set.crbegin());
107 AvlSet::const_reverse_iterator avl_set_rit(my_avlset.crbegin());
108 SplaySet::const_reverse_iterator splay_set_rit(my_splayset.crbegin());
109
110 VectRit vect_it(values.rbegin()), vect_itend(values.rend());
111
112 //Test the objects inserted in the base hook list
113 for(; vect_it != vect_itend
114 ; ++vect_it, ++list_it
115 , ++slist_it, ++set_rit
116 , ++avl_set_rit
117 , ++splay_set_rit
118 ){
119 if(&*list_it != &*vect_it) return 1;
120 if(&*slist_it != &*vect_it) return 1;
121 if(&*set_rit != &*vect_it) return 1;
122 if(&*avl_set_rit != &*vect_it) return 1;
123 if(&*splay_set_rit != &*vect_it)return 1;
124 if(my_uset.find(*set_rit) == my_uset.cend()) return 1;
125 }
126 }
127 }
128 //Since treap_set, sg_set & bs_set reuse the hook, treat them apart
129 {
130 TreapSet my_treapset;
131 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
132 my_treapset.insert(*it);
133 }
134
135 TreapSet::const_reverse_iterator treap_set_rit(my_treapset.crbegin());
136 VectRit vect_it(values.rbegin()), vect_itend(values.rend());
137 for(; vect_it != vect_itend; ++vect_it, ++treap_set_rit){
138 if(&*treap_set_rit != &*vect_it) return 1;
139 }
140 }
141 {
142 SgSet my_sgset;
143 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
144 my_sgset.insert(*it);
145 }
146
147 SgSet::const_reverse_iterator sg_set_rit(my_sgset.crbegin());
148 VectRit vect_it(values.rbegin()), vect_itend(values.rend());
149 for(; vect_it != vect_itend; ++vect_it, ++sg_set_rit){
150 if(&*sg_set_rit != &*vect_it) return 1;
151 }
152 }
153 {
154 BsSet my_bsset;
155 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
156 my_bsset.insert(*it);
157 }
158
159 BsSet::const_reverse_iterator bs_set_rit(my_bsset.crbegin());
160 VectRit vect_it(values.rbegin()), vect_itend(values.rend());
161 for(; vect_it != vect_itend; ++vect_it, ++bs_set_rit){
162 if(&*bs_set_rit != &*vect_it) return 1;
163 }
164 }
165 return 0;
166 }
167