1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Matei David 2014
4 // (C) Copyright Ion Gaztanaga 2014
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
14 #ifndef BOOST_INTRUSIVE_BPTR_VALUE_HPP
15 #define BOOST_INTRUSIVE_BPTR_VALUE_HPP
16
17 #include <cassert>
18 #include <iostream>
19 #include "bounded_pointer.hpp"
20 #include "common_functors.hpp"
21 #include "int_holder.hpp"
22 #include <boost/intrusive/link_mode.hpp>
23
24
25 namespace boost {
26 namespace intrusive {
27
28 struct BPtr_Value
29 {
30 static const bool constant_time_size = true;
31
BPtr_Valueboost::intrusive::BPtr_Value32 explicit BPtr_Value(int value = 42)
33 : value_(value)
34 {}
35
BPtr_Valueboost::intrusive::BPtr_Value36 BPtr_Value(const BPtr_Value& rhs)
37 : value_(rhs.value_)
38 {}
39
~BPtr_Valueboost::intrusive::BPtr_Value40 ~BPtr_Value()
41 {
42 if (is_linked())
43 {
44 assert(false);
45 }
46 }
47
48 // testvalue is used in boost::container::vector and thus prev and next
49 // have to be handled appropriately when copied:
operator =boost::intrusive::BPtr_Value50 BPtr_Value& operator = (const BPtr_Value& src)
51 {
52 if (is_linked())
53 {
54 assert(false);
55 }
56 value_ = src.value_;
57 return *this;
58 }
59
60 // value
61 int_holder value_;
62
63 // list node hooks
64 bounded_pointer< BPtr_Value > m_previous;
65 bounded_pointer< BPtr_Value > m_next;
66 // tree node hooks
67 bounded_pointer< BPtr_Value > m_parent;
68 bounded_pointer< BPtr_Value > m_l_child;
69 bounded_pointer< BPtr_Value > m_r_child;
70 signed char m_extra;
71
get_int_holderboost::intrusive::BPtr_Value72 const int_holder &get_int_holder() const
73 { return value_; }
74
int_valueboost::intrusive::BPtr_Value75 int int_value() const
76 { return value_.int_value(); }
77
is_linkedboost::intrusive::BPtr_Value78 bool is_linked() const
79 { return m_previous || m_next || m_parent || m_l_child || m_r_child; }
80
operator <(const BPtr_Value & other1,const BPtr_Value & other2)81 friend bool operator< (const BPtr_Value &other1, const BPtr_Value &other2)
82 { return other1.value_ < other2.value_; }
83
operator <(int other1,const BPtr_Value & other2)84 friend bool operator< (int other1, const BPtr_Value &other2)
85 { return other1 < other2.value_; }
86
operator <(const BPtr_Value & other1,int other2)87 friend bool operator< (const BPtr_Value &other1, int other2)
88 { return other1.value_ < other2; }
89
operator >(const BPtr_Value & other1,const BPtr_Value & other2)90 friend bool operator> (const BPtr_Value &other1, const BPtr_Value &other2)
91 { return other1.value_ > other2.value_; }
92
operator >(int other1,const BPtr_Value & other2)93 friend bool operator> (int other1, const BPtr_Value &other2)
94 { return other1 > other2.value_; }
95
operator >(const BPtr_Value & other1,int other2)96 friend bool operator> (const BPtr_Value &other1, int other2)
97 { return other1.value_ > other2; }
98
operator ==(const BPtr_Value & other1,const BPtr_Value & other2)99 friend bool operator== (const BPtr_Value &other1, const BPtr_Value &other2)
100 { return other1.value_ == other2.value_; }
101
operator ==(int other1,const BPtr_Value & other2)102 friend bool operator== (int other1, const BPtr_Value &other2)
103 { return other1 == other2.value_; }
104
operator ==(const BPtr_Value & other1,int other2)105 friend bool operator== (const BPtr_Value &other1, int other2)
106 { return other1.value_ == other2; }
107
operator !=(const BPtr_Value & other1,const BPtr_Value & other2)108 friend bool operator!= (const BPtr_Value &other1, const BPtr_Value &other2)
109 { return !(other1 == other2); }
110
operator !=(int other1,const BPtr_Value & other2)111 friend bool operator!= (int other1, const BPtr_Value &other2)
112 { return !(other1 == other2.value_); }
113
operator !=(const BPtr_Value & other1,int other2)114 friend bool operator!= (const BPtr_Value &other1, int other2)
115 { return !(other1.value_ == other2); }
116
117 }; // class BPtr_Value
118
operator <<(std::ostream & s,const BPtr_Value & t)119 std::ostream& operator<<(std::ostream& s, const BPtr_Value& t)
120 { return s << t.value_.int_value(); }
121
122 template < typename Node_Algorithms >
swap_nodes(bounded_reference<BPtr_Value> lhs,bounded_reference<BPtr_Value> rhs)123 void swap_nodes(bounded_reference< BPtr_Value > lhs, bounded_reference< BPtr_Value > rhs)
124 {
125 Node_Algorithms::swap_nodes(
126 boost::intrusive::pointer_traits< bounded_pointer< BPtr_Value > >::pointer_to(lhs),
127 boost::intrusive::pointer_traits< bounded_pointer< BPtr_Value > >::pointer_to(rhs));
128 }
129
130 struct List_BPtr_Node_Traits
131 {
132 typedef BPtr_Value val_t;
133 typedef val_t node;
134 typedef bounded_pointer< val_t > node_ptr;
135 typedef bounded_pointer< const val_t > const_node_ptr;
136
get_previousboost::intrusive::List_BPtr_Node_Traits137 static node_ptr get_previous(const_node_ptr p) { return p->m_previous; }
set_previousboost::intrusive::List_BPtr_Node_Traits138 static void set_previous(node_ptr p, node_ptr prev) { p->m_previous = prev; }
get_nextboost::intrusive::List_BPtr_Node_Traits139 static node_ptr get_next(const_node_ptr p) { return p->m_next; }
set_nextboost::intrusive::List_BPtr_Node_Traits140 static void set_next(node_ptr p, node_ptr next) { p->m_next = next; }
141 };
142
143 struct Tree_BPtr_Node_Traits
144 {
145 typedef BPtr_Value val_t;
146 typedef val_t node;
147 typedef bounded_pointer< val_t > node_ptr;
148 typedef bounded_pointer< const val_t > const_node_ptr;
149
get_parentboost::intrusive::Tree_BPtr_Node_Traits150 static node_ptr get_parent(const_node_ptr p) { return p->m_parent; }
set_parentboost::intrusive::Tree_BPtr_Node_Traits151 static void set_parent(node_ptr p, node_ptr parent) { p->m_parent = parent; }
get_leftboost::intrusive::Tree_BPtr_Node_Traits152 static node_ptr get_left(const_node_ptr p) { return p->m_l_child; }
set_leftboost::intrusive::Tree_BPtr_Node_Traits153 static void set_left(node_ptr p, node_ptr l_child) { p->m_l_child = l_child; }
get_rightboost::intrusive::Tree_BPtr_Node_Traits154 static node_ptr get_right(const_node_ptr p) { return p->m_r_child; }
set_rightboost::intrusive::Tree_BPtr_Node_Traits155 static void set_right(node_ptr p, node_ptr r_child) { p->m_r_child = r_child; }
156 };
157
158 struct RBTree_BPtr_Node_Traits
159 : public Tree_BPtr_Node_Traits
160 {
161 typedef signed char color;
162 typedef Tree_BPtr_Node_Traits::node_ptr node_ptr;
163 typedef Tree_BPtr_Node_Traits::const_node_ptr const_node_ptr;
get_colorboost::intrusive::RBTree_BPtr_Node_Traits164 static color get_color(const_node_ptr p) { return p->m_extra; }
set_colorboost::intrusive::RBTree_BPtr_Node_Traits165 static void set_color(node_ptr p, color c) { p->m_extra = c; }
blackboost::intrusive::RBTree_BPtr_Node_Traits166 static color black() { return 0; }
redboost::intrusive::RBTree_BPtr_Node_Traits167 static color red() { return 1; }
168 };
169
170 struct AVLTree_BPtr_Node_Traits
171 : public Tree_BPtr_Node_Traits
172 {
173 typedef signed char balance;
174 typedef Tree_BPtr_Node_Traits::node_ptr node_ptr;
175 typedef Tree_BPtr_Node_Traits::const_node_ptr const_node_ptr;
get_balanceboost::intrusive::AVLTree_BPtr_Node_Traits176 static balance get_balance(const_node_ptr p) { return p->m_extra; }
set_balanceboost::intrusive::AVLTree_BPtr_Node_Traits177 static void set_balance(node_ptr p, balance b) { p->m_extra = b; }
negativeboost::intrusive::AVLTree_BPtr_Node_Traits178 static balance negative() { return -1; }
zeroboost::intrusive::AVLTree_BPtr_Node_Traits179 static balance zero() { return 0; }
positiveboost::intrusive::AVLTree_BPtr_Node_Traits180 static balance positive() { return 1; }
181 };
182
183 template < typename NodeTraits >
184 struct BPtr_Value_Traits
185 {
186 typedef NodeTraits node_traits;
187 typedef typename node_traits::val_t value_type;
188 typedef typename node_traits::node_ptr node_ptr;
189 typedef typename node_traits::const_node_ptr const_node_ptr;
190 typedef node_ptr pointer;
191 typedef const_node_ptr const_pointer;
192 typedef bounded_reference< value_type > reference;
193 typedef bounded_reference< const value_type > const_reference;
194 typedef BPtr_Value_Traits<NodeTraits> * value_traits_ptr;
195
196 static const boost::intrusive::link_mode_type link_mode = boost::intrusive::safe_link;
197
to_node_ptrboost::intrusive::BPtr_Value_Traits198 static const_node_ptr to_node_ptr(const_reference v) { return &v; }
to_node_ptrboost::intrusive::BPtr_Value_Traits199 static node_ptr to_node_ptr(reference v) { return &v; }
to_value_ptrboost::intrusive::BPtr_Value_Traits200 static const_pointer to_value_ptr(const_node_ptr p) { return p; }
to_value_ptrboost::intrusive::BPtr_Value_Traits201 static pointer to_value_ptr(node_ptr p) { return p; }
202 };
203
204 template < typename >
205 struct ValueContainer;
206
207 template <>
208 struct ValueContainer< BPtr_Value >
209 {
210 typedef bounded_reference_cont< BPtr_Value > type;
211 };
212
213 namespace test{
214
215 template <>
216 class new_cloner< BPtr_Value >
217 {
218 public:
219 typedef BPtr_Value value_type;
220 typedef bounded_pointer< value_type > pointer;
221 typedef bounded_reference< const value_type > const_reference;
222 typedef bounded_allocator< value_type > allocator_type;
223
operator ()(const_reference r)224 pointer operator () (const_reference r)
225 {
226 pointer p = allocator_type().allocate(1);
227 new (p.raw()) value_type(r);
228 return p;
229 }
230 };
231
232 template <>
233 class new_nonconst_cloner< BPtr_Value >
234 {
235 public:
236 typedef BPtr_Value value_type;
237 typedef bounded_pointer< value_type > pointer;
238 typedef bounded_reference< value_type > reference;
239 typedef bounded_allocator< value_type > allocator_type;
240
operator ()(reference r)241 pointer operator () (reference r)
242 {
243 pointer p = allocator_type().allocate(1);
244 new (p.raw()) value_type(r);
245 return p;
246 }
247 };
248
249 template <>
250 class delete_disposer< BPtr_Value >
251 {
252 public:
253 typedef BPtr_Value value_type;
254 typedef bounded_pointer< value_type > pointer;
255 typedef bounded_allocator< value_type > allocator_type;
256
operator ()(pointer p)257 void operator () (pointer p)
258 {
259 p->~value_type();
260 allocator_type().deallocate(p, 1);
261 }
262 };
263
264 } // namespace test
265
266 } // namespace intrusive
267 } // namespace boost
268
269
270 #endif
271