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 #ifndef BOOST_INTRUSIVE_DETAIL_ITESTVALUE_HPP
14 #define BOOST_INTRUSIVE_DETAIL_ITESTVALUE_HPP
15
16 #include <iostream>
17 #include <boost/intrusive/options.hpp>
18 #include <boost/functional/hash.hpp>
19 #include <boost/intrusive/pointer_traits.hpp>
20 #include "nonhook_node.hpp"
21 #include "int_holder.hpp"
22 #include <boost/intrusive/detail/get_value_traits.hpp>
23 #include <boost/container/vector.hpp>
24
25 namespace boost{
26 namespace intrusive{
27
28 struct testvalue_filler
29 {
30 void *dummy_[3];
31 };
32
33 template<class Hooks>
34 struct testvalue
35 : testvalue_filler
36 , Hooks::base_hook_type
37 , Hooks::auto_base_hook_type
38 {
39 typename Hooks::member_hook_type node_;
40 typename Hooks::auto_member_hook_type auto_node_;
41 typename Hooks::nonhook_node_member_type nhn_member_;
42
43 int_holder value_;
44
testvalueboost::intrusive::testvalue45 testvalue()
46 {}
47
testvalueboost::intrusive::testvalue48 explicit testvalue(int i)
49 : value_(i)
50 {}
51
testvalueboost::intrusive::testvalue52 testvalue (const testvalue& src)
53 : value_(src.value_)
54 {}
55
56 // testvalue is used in boost::container::vector and thus prev and next
57 // have to be handled appropriately when copied:
operator =boost::intrusive::testvalue58 testvalue & operator= (const testvalue& src)
59 {
60 Hooks::base_hook_type::operator=(static_cast<const typename Hooks::base_hook_type&>(src));
61 Hooks::auto_base_hook_type::operator=(static_cast<const typename Hooks::auto_base_hook_type&>(src));
62 this->node_ = src.node_;
63 this->auto_node_ = src.auto_node_;
64 this->nhn_member_ = src.nhn_member_;
65 value_ = src.value_;
66 return *this;
67 }
68
swap_nodesboost::intrusive::testvalue69 void swap_nodes(testvalue &other)
70 {
71 Hooks::base_hook_type::swap_nodes(static_cast<typename Hooks::base_hook_type&>(other));
72 Hooks::auto_base_hook_type::swap_nodes(static_cast<typename Hooks::auto_base_hook_type&>(other));
73 node_.swap_nodes(other.node_);
74 auto_node_.swap_nodes(other.auto_node_);
75 nhn_member_.swap_nodes(other.nhn_member_);
76 }
77
is_linkedboost::intrusive::testvalue78 bool is_linked() const
79 {
80 return Hooks::base_hook_type::is_linked() ||
81 Hooks::auto_base_hook_type::is_linked() ||
82 node_.is_linked() ||
83 auto_node_.is_linked() ||
84 nhn_member_.is_linked();
85 }
86
get_int_holderboost::intrusive::testvalue87 const int_holder &get_int_holder() const
88 { return value_; }
89
int_valueboost::intrusive::testvalue90 int int_value() const
91 { return value_.int_value(); }
92
~testvalueboost::intrusive::testvalue93 ~testvalue()
94 {}
95
operator <boost::intrusive::testvalue96 bool operator< (const testvalue &other) const
97 { return value_ < other.value_; }
98
operator ==boost::intrusive::testvalue99 bool operator==(const testvalue &other) const
100 { return value_ == other.value_; }
101
operator !=boost::intrusive::testvalue102 bool operator!=(const testvalue &other) const
103 { return value_ != other.value_; }
104
operator <(int other1,const testvalue & other2)105 friend bool operator< (int other1, const testvalue &other2)
106 { return other1 < other2.value_.int_; }
107
operator <(const testvalue & other1,int other2)108 friend bool operator< (const testvalue &other1, int other2)
109 { return other1.value_.int_ < other2; }
110
operator ==(int other1,const testvalue & other2)111 friend bool operator== (int other1, const testvalue &other2)
112 { return other1 == other2.value_.int_; }
113
operator ==(const testvalue & other1,int other2)114 friend bool operator== (const testvalue &other1, int other2)
115 { return other1.value_.int_ == other2; }
116
operator !=(int other1,const testvalue & other2)117 friend bool operator!= (int other1, const testvalue &other2)
118 { return other1 != other2.value_.int_; }
119
operator !=(const testvalue & other1,int other2)120 friend bool operator!= (const testvalue &other1, int other2)
121 { return other1.value_.int_ != other2; }
122
hash_value(const testvalue & t)123 friend std::size_t hash_value(const testvalue&t)
124 {
125 boost::hash<int> hasher;
126 return hasher((&t)->int_value());
127 }
128 };
129
130
131 template <class Type>
priority_order(const Type & t1,const Type & t2)132 bool priority_order(const Type& t1, const Type& t2)
133 {
134 std::size_t hash1 = boost::hash<int>()((&t1)->int_value());
135 boost::hash_combine(hash1, &t1);
136 std::size_t hash2 = boost::hash<int>()((&t2)->int_value());
137 boost::hash_combine(hash2, &t2);
138 return hash1 < hash2;
139 }
140
priority_order(int t1,int t2)141 bool priority_order(int t1, int t2)
142 {
143 std::size_t hash1 = boost::hash<int>()(t1);
144 boost::hash_combine(hash1, &t1);
145 std::size_t hash2 = boost::hash<int>()(t2);
146 boost::hash_combine(hash2, &t2);
147 return hash1 < hash2;
148 }
149
150 template < typename Node_Algorithms, class Hooks>
swap_nodes(testvalue<Hooks> & lhs,testvalue<Hooks> & rhs)151 void swap_nodes(testvalue<Hooks>& lhs, testvalue<Hooks>& rhs)
152 {
153 lhs.swap_nodes(rhs);
154 }
155
156 template<class Hooks>
operator <<(std::ostream & s,const testvalue<Hooks> & t)157 std::ostream& operator<<
158 (std::ostream& s, const testvalue<Hooks>& t)
159 { return s << t.value_; }
160
161 struct even_odd
162 {
163 template < typename key_type_1, typename key_type_2 >
operator ()boost::intrusive::even_odd164 bool operator()
165 (const key_type_1& v1
166 ,const key_type_2& v2) const
167 {
168 if (((&v1)->int_value() & 1) == ((&v2)->int_value() & 1))
169 return (&v1)->int_value() < (&v2)->int_value();
170 else
171 return (&v2)->int_value() & 1;
172 }
173 };
174
175 struct is_even
176 {
177 template <typename key_type>
operator ()boost::intrusive::is_even178 bool operator()
179 (const key_type& v1) const
180 { return ((&v1)->int_value() & 1) == 0; }
181 };
182
183 struct is_odd
184 {
185 template <typename key_type>
operator ()boost::intrusive::is_odd186 bool operator()
187 (const key_type& v1) const
188 { return ((&v1)->int_value() & 1) != 0; }
189 };
190
191 template <typename>
192 struct ValueContainer;
193
194 template < class Hooks>
195 struct ValueContainer< testvalue<Hooks> >
196 {
197 typedef boost::container::vector< testvalue<Hooks> > type;
198 };
199
200 template < typename Pointer >
201 class heap_node_holder
202 {
203 typedef typename pointer_traits<Pointer>::element_type element_type;
204 typedef Pointer pointer;
205 typedef typename pointer_rebind<pointer, const element_type>::type const_pointer;
206
207 public:
heap_node_holder()208 heap_node_holder()
209 : m_ptr(pointer_traits<Pointer>::pointer_to(*new element_type))
210 {}
211
~heap_node_holder()212 ~heap_node_holder()
213 { delete &*m_ptr; }
214
get_node() const215 const_pointer get_node() const
216 { return m_ptr; }
217
get_node()218 pointer get_node()
219 { return m_ptr; }
220
221 private:
222 pointer m_ptr;
223 };
224
225 template<class Hooks>
226 struct testvalue_traits
227 : public Hooks
228 {
229 typedef testvalue< Hooks > value_type;
230
231 //base
232 typedef typename detail::get_base_value_traits
233 < value_type
234 , typename Hooks::base_hook_type
235 >::type base_value_traits;
236 //auto-base
237 typedef typename detail::get_base_value_traits
238 < value_type
239 , typename Hooks::auto_base_hook_type
240 >::type auto_base_value_traits;
241 //member
242 typedef typename detail::get_member_value_traits
243 < member_hook
244 < value_type
245 , typename Hooks::member_hook_type
246 , &value_type::node_
247 >
248 >::type member_value_traits;
249 //auto-member
250 typedef typename detail::get_member_value_traits
251 < member_hook
252 < value_type
253 , typename Hooks::auto_member_hook_type
254 , &value_type::auto_node_
255 >
256 >::type auto_member_value_traits;
257 //nonmember
258 typedef nonhook_node_member_value_traits
259 < value_type
260 , typename Hooks::nonhook_node_member_type
261 , &value_type::nhn_member_
262 , safe_link
263 > nonhook_value_traits;
264 };
265
266 } //namespace intrusive{
267 } //namespace boost{
268
priority_order(int t1,int t2)269 bool priority_order(int t1, int t2)
270 {
271 std::size_t hash1 = boost::hash<int>()(t1);
272 boost::hash_combine(hash1, &t1);
273 std::size_t hash2 = boost::hash<int>()(t2);
274 boost::hash_combine(hash2, &t2);
275 return hash1 < hash2;
276 }
277
278 #endif
279