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 "bounded_pointer.hpp"
19 #include "common_functors.hpp"
20
21
22 namespace boost {
23 namespace intrusive {
24
25 struct BPtr_Value
26 {
27 static const bool constant_time_size = true;
28
BPtr_Valueboost::intrusive::BPtr_Value29 explicit BPtr_Value(int value = 42)
30 : value_(value)
31 {}
32
BPtr_Valueboost::intrusive::BPtr_Value33 BPtr_Value(const BPtr_Value& rhs)
34 : value_(rhs.value_)
35 {}
36
~BPtr_Valueboost::intrusive::BPtr_Value37 ~BPtr_Value()
38 {
39 if (is_linked())
40 {
41 assert(false);
42 }
43 }
44
45 // testvalue is used in boost::container::vector and thus prev and next
46 // have to be handled appropriately when copied:
operator =boost::intrusive::BPtr_Value47 BPtr_Value& operator = (const BPtr_Value& src)
48 {
49 if (is_linked())
50 {
51 assert(false);
52 }
53 value_ = src.value_;
54 return *this;
55 }
56
57 // value
58 int_holder value_;
59
60 // list node hooks
61 bounded_pointer< BPtr_Value > m_previous;
62 bounded_pointer< BPtr_Value > m_next;
63 // tree node hooks
64 bounded_pointer< BPtr_Value > m_parent;
65 bounded_pointer< BPtr_Value > m_l_child;
66 bounded_pointer< BPtr_Value > m_r_child;
67 signed char m_extra;
68
get_int_holderboost::intrusive::BPtr_Value69 const int_holder &get_int_holder() const
70 { return value_; }
71
int_valueboost::intrusive::BPtr_Value72 int int_value() const
73 { return value_.int_value(); }
74
is_linkedboost::intrusive::BPtr_Value75 bool is_linked() const
76 { return m_previous || m_next || m_parent || m_l_child || m_r_child; }
77
operator <(const BPtr_Value & other1,const BPtr_Value & other2)78 friend bool operator< (const BPtr_Value &other1, const BPtr_Value &other2)
79 { return other1.value_ < other2.value_; }
80
operator <(int other1,const BPtr_Value & other2)81 friend bool operator< (int other1, const BPtr_Value &other2)
82 { return other1 < other2.value_; }
83
operator <(const BPtr_Value & other1,int other2)84 friend bool operator< (const BPtr_Value &other1, int other2)
85 { return other1.value_ < other2; }
86
operator ==(const BPtr_Value & other1,const BPtr_Value & other2)87 friend bool operator== (const BPtr_Value &other1, const BPtr_Value &other2)
88 { return other1.value_ == other2.value_; }
89
operator ==(int other1,const BPtr_Value & other2)90 friend bool operator== (int other1, const BPtr_Value &other2)
91 { return other1 == other2.value_; }
92
operator ==(const BPtr_Value & other1,int other2)93 friend bool operator== (const BPtr_Value &other1, int other2)
94 { return other1.value_ == other2; }
95
operator !=(const BPtr_Value & other1,const BPtr_Value & other2)96 friend bool operator!= (const BPtr_Value &other1, const BPtr_Value &other2)
97 { return !(other1 == other2); }
98
operator !=(int other1,const BPtr_Value & other2)99 friend bool operator!= (int other1, const BPtr_Value &other2)
100 { return !(other1 == other2.value_); }
101
operator !=(const BPtr_Value & other1,int other2)102 friend bool operator!= (const BPtr_Value &other1, int other2)
103 { return !(other1.value_ == other2); }
104
105 }; // class BPtr_Value
106
107 template < typename Node_Algorithms >
swap_nodes(bounded_reference<BPtr_Value> lhs,bounded_reference<BPtr_Value> rhs)108 void swap_nodes(bounded_reference< BPtr_Value > lhs, bounded_reference< BPtr_Value > rhs)
109 {
110 Node_Algorithms::swap_nodes(
111 boost::intrusive::pointer_traits< bounded_pointer< BPtr_Value > >::pointer_to(lhs),
112 boost::intrusive::pointer_traits< bounded_pointer< BPtr_Value > >::pointer_to(rhs));
113 }
114
115 struct List_BPtr_Node_Traits
116 {
117 typedef BPtr_Value val_t;
118 typedef val_t node;
119 typedef bounded_pointer< val_t > node_ptr;
120 typedef bounded_pointer< const val_t > const_node_ptr;
121
get_previousboost::intrusive::List_BPtr_Node_Traits122 static node_ptr get_previous(const_node_ptr p) { return p->m_previous; }
set_previousboost::intrusive::List_BPtr_Node_Traits123 static void set_previous(node_ptr p, node_ptr prev) { p->m_previous = prev; }
get_nextboost::intrusive::List_BPtr_Node_Traits124 static node_ptr get_next(const_node_ptr p) { return p->m_next; }
set_nextboost::intrusive::List_BPtr_Node_Traits125 static void set_next(node_ptr p, node_ptr next) { p->m_next = next; }
126 };
127
128 struct Tree_BPtr_Node_Traits
129 {
130 typedef BPtr_Value val_t;
131 typedef val_t node;
132 typedef bounded_pointer< val_t > node_ptr;
133 typedef bounded_pointer< const val_t > const_node_ptr;
134
get_parentboost::intrusive::Tree_BPtr_Node_Traits135 static node_ptr get_parent(const_node_ptr p) { return p->m_parent; }
set_parentboost::intrusive::Tree_BPtr_Node_Traits136 static void set_parent(node_ptr p, node_ptr parent) { p->m_parent = parent; }
get_leftboost::intrusive::Tree_BPtr_Node_Traits137 static node_ptr get_left(const_node_ptr p) { return p->m_l_child; }
set_leftboost::intrusive::Tree_BPtr_Node_Traits138 static void set_left(node_ptr p, node_ptr l_child) { p->m_l_child = l_child; }
get_rightboost::intrusive::Tree_BPtr_Node_Traits139 static node_ptr get_right(const_node_ptr p) { return p->m_r_child; }
set_rightboost::intrusive::Tree_BPtr_Node_Traits140 static void set_right(node_ptr p, node_ptr r_child) { p->m_r_child = r_child; }
141 };
142
143 struct RBTree_BPtr_Node_Traits
144 : public Tree_BPtr_Node_Traits
145 {
146 typedef signed char color;
147 typedef Tree_BPtr_Node_Traits::node_ptr node_ptr;
148 typedef Tree_BPtr_Node_Traits::const_node_ptr const_node_ptr;
get_colorboost::intrusive::RBTree_BPtr_Node_Traits149 static color get_color(const_node_ptr p) { return p->m_extra; }
set_colorboost::intrusive::RBTree_BPtr_Node_Traits150 static void set_color(node_ptr p, color c) { p->m_extra = c; }
blackboost::intrusive::RBTree_BPtr_Node_Traits151 static color black() { return 0; }
redboost::intrusive::RBTree_BPtr_Node_Traits152 static color red() { return 1; }
153 };
154
155 struct AVLTree_BPtr_Node_Traits
156 : public Tree_BPtr_Node_Traits
157 {
158 typedef signed char balance;
159 typedef Tree_BPtr_Node_Traits::node_ptr node_ptr;
160 typedef Tree_BPtr_Node_Traits::const_node_ptr const_node_ptr;
get_balanceboost::intrusive::AVLTree_BPtr_Node_Traits161 static balance get_balance(const_node_ptr p) { return p->m_extra; }
set_balanceboost::intrusive::AVLTree_BPtr_Node_Traits162 static void set_balance(node_ptr p, balance b) { p->m_extra = b; }
negativeboost::intrusive::AVLTree_BPtr_Node_Traits163 static balance negative() { return -1; }
zeroboost::intrusive::AVLTree_BPtr_Node_Traits164 static balance zero() { return 0; }
positiveboost::intrusive::AVLTree_BPtr_Node_Traits165 static balance positive() { return 1; }
166 };
167
168 template < typename NodeTraits >
169 struct BPtr_Value_Traits
170 {
171 typedef NodeTraits node_traits;
172 typedef typename node_traits::val_t value_type;
173 typedef typename node_traits::node_ptr node_ptr;
174 typedef typename node_traits::const_node_ptr const_node_ptr;
175 typedef node_ptr pointer;
176 typedef const_node_ptr const_pointer;
177 typedef bounded_reference< value_type > reference;
178 typedef bounded_reference< const value_type > const_reference;
179 typedef BPtr_Value_Traits<NodeTraits> * value_traits_ptr;
180
181 static const boost::intrusive::link_mode_type link_mode = boost::intrusive::safe_link;
182
to_node_ptrboost::intrusive::BPtr_Value_Traits183 static const_node_ptr to_node_ptr(const_reference v) { return &v; }
to_node_ptrboost::intrusive::BPtr_Value_Traits184 static node_ptr to_node_ptr(reference v) { return &v; }
to_value_ptrboost::intrusive::BPtr_Value_Traits185 static const_pointer to_value_ptr(const_node_ptr p) { return p; }
to_value_ptrboost::intrusive::BPtr_Value_Traits186 static pointer to_value_ptr(node_ptr p) { return p; }
187 };
188
189 template < typename >
190 struct ValueContainer;
191
192 template <>
193 struct ValueContainer< BPtr_Value >
194 {
195 typedef bounded_reference_cont< BPtr_Value > type;
196 };
197
198 namespace test{
199
200 template <>
201 class new_cloner< BPtr_Value >
202 {
203 public:
204 typedef BPtr_Value value_type;
205 typedef bounded_pointer< value_type > pointer;
206 typedef bounded_reference< const value_type > const_reference;
207 typedef bounded_allocator< value_type > allocator_type;
208
operator ()(const_reference r)209 pointer operator () (const_reference r)
210 {
211 pointer p = allocator_type().allocate(1);
212 new (p.raw()) value_type(r);
213 return p;
214 }
215 };
216
217 template <>
218 class new_nonconst_cloner< BPtr_Value >
219 {
220 public:
221 typedef BPtr_Value value_type;
222 typedef bounded_pointer< value_type > pointer;
223 typedef bounded_reference< value_type > reference;
224 typedef bounded_allocator< value_type > allocator_type;
225
operator ()(reference r)226 pointer operator () (reference r)
227 {
228 pointer p = allocator_type().allocate(1);
229 new (p.raw()) value_type(r);
230 return p;
231 }
232 };
233
234 template <>
235 class delete_disposer< BPtr_Value >
236 {
237 public:
238 typedef BPtr_Value value_type;
239 typedef bounded_pointer< value_type > pointer;
240 typedef bounded_allocator< value_type > allocator_type;
241
operator ()(pointer p)242 void operator () (pointer p)
243 {
244 p->~value_type();
245 allocator_type().deallocate(p, 1);
246 }
247 };
248
249 } // namespace test
250
251 } // namespace intrusive
252 } // namespace boost
253
254
255 #endif
256