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/functional/hash.hpp>
17 #include <boost/intrusive/pointer_traits.hpp>
18 #include <vector>
19
20 using namespace boost::intrusive;
21
22 class MyClass
23 {
24 public:
25 int int_;
26
MyClass(int i=0)27 MyClass(int i = 0)
28 : int_(i)
29 {}
30
operator <(const MyClass & l,const MyClass & r)31 friend bool operator<(const MyClass &l, const MyClass &r)
32 { return l.int_ < r.int_; }
33
operator ==(const MyClass & l,const MyClass & r)34 friend bool operator==(const MyClass &l, const MyClass &r)
35 { return l.int_ == r.int_; }
36
hash_value(const MyClass & v)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 pointer_traits<node_ptr>::
50 template rebind_pointer<T>::type pointer;
51 typedef typename pointer_traits<node_ptr>::
52 template rebind_pointer<const T>::type const_pointer;
53
54 static const link_mode_type link_mode = normal_link;
55
stateful_value_traitsstateful_value_traits56 stateful_value_traits(pointer vals, node_ptr node_array)
57 : values_(vals), node_array_(node_array)
58 {}
59
to_node_ptrstateful_value_traits60 node_ptr to_node_ptr (value_type &value) const
61 { return node_array_ + (&value - values_); }
62
to_node_ptrstateful_value_traits63 const_node_ptr to_node_ptr (const value_type &value) const
64 { return node_array_ + (&value - values_); }
65
to_value_ptrstateful_value_traits66 pointer to_value_ptr(const node_ptr &n) const
67 { return values_ + (n - node_array_); }
68
to_value_ptrstateful_value_traits69 const_pointer to_value_ptr(const const_node_ptr &n) const
70 { return values_ + (n - node_array_); }
71
72 pointer values_;
73 node_ptr node_array_;
74 };
75
76 //Define a list that will store MyClass using the external hook
77 typedef stateful_value_traits< MyClass, list_node_traits<void*> > list_traits;
78 typedef list<MyClass, value_traits<list_traits> > List;
79
80 //Define a slist that will store MyClass using the external hook
81 typedef stateful_value_traits< MyClass, slist_node_traits<void*> > slist_traits;
82 typedef slist<MyClass, value_traits<slist_traits> > Slist;
83
84 //Define a set that will store MyClass using the external hook
85 typedef stateful_value_traits< MyClass, rbtree_node_traits<void*> > rbtree_traits;
86 typedef set<MyClass, value_traits<rbtree_traits> > Set;
87
88 //uset uses the same traits as slist
89 typedef unordered_set<MyClass, value_traits<slist_traits> > Uset;
90
91
92 typedef list_traits::node list_node_t;
93 typedef slist_traits::node slist_node_t;
94 typedef rbtree_traits::node rbtree_node_t;
95
96 const int NumElements = 100;
97
98 MyClass values [NumElements];
99 list_node_t list_hook_array [NumElements];
100 slist_node_t slist_hook_array [NumElements];
101 rbtree_node_t rbtree_hook_array [NumElements];
102 slist_node_t uset_hook_array [NumElements];
103
main()104 int main()
105 {
106 //Create several MyClass objects, each one with a different value
107 for(int i = 0; i < NumElements; ++i)
108 values[i].int_ = i;
109
110 Uset::bucket_type buckets[NumElements];
111
112 List my_list (list_traits (values, list_hook_array));
113 Slist my_slist(slist_traits(values, slist_hook_array));
114 Set my_set (std::less<MyClass>(), rbtree_traits(values, rbtree_hook_array));
115 Uset my_uset ( Uset::bucket_traits(buckets, NumElements)
116 , boost::hash<MyClass>()
117 , std::equal_to<MyClass>()
118 , slist_traits(values, uset_hook_array)
119 );
120
121 //Now insert them in containers
122 for(MyClass * it(&values[0]), *itend(&values[NumElements])
123 ; it != itend
124 ; ++it){
125 my_list.push_front(*it);
126 if(&*my_list.iterator_to(*it) != &my_list.front())
127 return 1;
128 my_slist.push_front(*it);
129 if(&*my_slist.iterator_to(*it) != &my_slist.front())
130 return 1;
131 Set::iterator sit = my_set.insert(*it).first;
132 if(&*my_set.iterator_to(*it) != &*sit)
133 return 1;
134 Uset::iterator uit = my_uset.insert(*it).first;
135 my_uset.insert(*it);
136 if(&*my_uset.iterator_to(*it) != &*uit)
137 return 1;
138 }
139
140 //Now test lists
141 {
142 List::const_iterator list_it (my_list.cbegin());
143 Slist::const_iterator slist_it(my_slist.cbegin());
144 Set::const_reverse_iterator set_rit(my_set.crbegin());
145 MyClass *it_val(&values[NumElements]), *it_rbeg_val(&values[0]);
146
147 //Test the objects inserted in the base hook list
148 for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++set_rit){
149 if(&*list_it != &it_val[-1]) return 1;
150 if(&*slist_it != &it_val[-1]) return 1;
151 if(&*set_rit != &it_val[-1]) return 1;
152 if(my_uset.find(it_val[-1]) == my_uset.cend()) return 1;
153 }
154 }
155
156 return 0;
157 }
158