1 /////////////////////////////////////////////////////////////////////////////
\r
3 // (C) Copyright Olaf Krzikalla 2004-2006.
\r
4 // (C) Copyright Ion GaztaƱaga 2006-2007.
\r
6 // Distributed under the Boost Software License, Version 1.0.
\r
7 // (See accompanying file LICENSE_1_0.txt or copy at
\r
8 // http://www.boost.org/LICENSE_1_0.txt)
\r
10 // See http://www.boost.org/libs/intrusive for documentation.
\r
12 /////////////////////////////////////////////////////////////////////////////
\r
13 // The internal implementation of red-black trees is based on that of SGI STL
\r
14 // stl_tree.h file:
\r
16 // Copyright (c) 1996,1997
\r
17 // Silicon Graphics Computer Systems, Inc.
\r
19 // Permission to use, copy, modify, distribute and sell this software
\r
20 // and its documentation for any purpose is hereby granted without fee,
\r
21 // provided that the above copyright notice appear in all copies and
\r
22 // that both that copyright notice and this permission notice appear
\r
23 // in supporting documentation. Silicon Graphics makes no
\r
24 // representations about the suitability of this software for any
\r
25 // purpose. It is provided "as is" without express or implied warranty.
\r
28 // Copyright (c) 1994
\r
29 // Hewlett-Packard Company
\r
31 // Permission to use, copy, modify, distribute and sell this software
\r
32 // and its documentation for any purpose is hereby granted without fee,
\r
33 // provided that the above copyright notice appear in all copies and
\r
34 // that both that copyright notice and this permission notice appear
\r
35 // in supporting documentation. Hewlett-Packard Company makes no
\r
36 // representations about the suitability of this software for any
\r
37 // purpose. It is provided "as is" without express or implied warranty.
\r
39 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP
\r
40 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP
\r
42 #include "config_begin.hpp"
\r
44 #include <boost/assert.hpp>
\r
45 #include "pointer_type.hpp"
\r
46 #include "pointer_to_other.hpp"
\r
47 #include "../rbtree_algorithms.hpp"
\r
48 #include <boost/get_pointer.hpp>
\r
49 //#include <boost/interprocess/offset_ptr.hpp>
\r
50 #include <boost/type_traits/alignment_of.hpp>
\r
52 #include <boost/detail/no_exceptions_support.hpp>
\r
55 namespace intrusive {
\r
58 /////////////////////////////////////////////////////////////////////////////
\r
60 // Generic node_traits for any pointer type //
\r
62 /////////////////////////////////////////////////////////////////////////////
\r
64 //This is the default implementation, 3 generic pointers plus an enum
\r
65 template<class VoidPointer>
\r
66 struct default_rbtree_node_traits_impl
\r
70 typedef typename boost::pointer_to_other
\r
71 <VoidPointer, node>::type node_ptr;
\r
72 typedef typename boost::pointer_to_other
\r
73 <VoidPointer, const node>::type const_node_ptr;
\r
77 enum color { red_t, black_t };
\r
79 static color black()
\r
85 node_ptr parent_, left_, right_;
\r
89 typedef typename node::color color;
\r
91 static node_ptr get_parent(const_node_ptr n)
\r
92 { return n->parent_; }
\r
94 static void set_parent(node_ptr n, node_ptr p)
\r
97 static node_ptr get_left(const_node_ptr n)
\r
98 { return n->left_; }
\r
100 static void set_left(node_ptr n, node_ptr l)
\r
103 static node_ptr get_right(const_node_ptr n)
\r
104 { return n->right_; }
\r
106 static void set_right(node_ptr n, node_ptr r)
\r
109 static color get_color(const_node_ptr n)
\r
110 { return n->color_; }
\r
112 static void set_color(node_ptr n, color c)
\r
115 static color black()
\r
116 { return node::black_t; }
\r
119 { return node::red_t; }
\r
122 //The default possibility is the generic implementation
\r
123 template<class VoidPointer>
\r
124 struct rbtree_node_traits
\r
125 : public default_rbtree_node_traits_impl<VoidPointer>
\r
128 //This is the compact representation: 3 pointers
\r
129 template<class VoidPointer>
\r
130 struct compact_node
\r
132 typedef typename boost::pointer_to_other
\r
133 <VoidPointer, compact_node>::type node_ptr;
\r
135 enum color { red_t, black_t };
\r
137 static color black()
\r
138 { return black_t; }
\r
143 node_ptr parent_, left_, right_;
\r
146 /////////////////////////////////////////////////////////////////////////////
\r
148 // Generic node_traits specialization for raw pointers //
\r
150 /////////////////////////////////////////////////////////////////////////////
\r
154 //This specialization, embeds the color in the parent pointer
\r
155 //so we save one word per node
\r
156 template <bool TwoByteAlignment>
\r
157 struct rbtree_node_traits_void_ptr
\r
159 typedef compact_node<void*> node;
\r
160 typedef node * node_ptr;
\r
161 typedef const node * const_node_ptr;
\r
162 typedef node::color color;
\r
164 static node_ptr get_parent(const_node_ptr n)
\r
165 { return (node_ptr)((std::size_t)n->parent_ & ~1); }
\r
167 static void set_parent(node_ptr n, node_ptr p)
\r
168 { n->parent_ = (node_ptr)((std::size_t)p | ((std::size_t)n->parent_ & 1)); }
\r
170 static node_ptr get_left(const_node_ptr n)
\r
171 { return n->left_; }
\r
173 static void set_left(node_ptr n, node_ptr l)
\r
176 static node_ptr get_right(const_node_ptr n)
\r
177 { return n->right_; }
\r
179 static void set_right(node_ptr n, node_ptr r)
\r
182 static color get_color(const_node_ptr n)
\r
183 { return (color)((std::size_t)n->parent_ & 1); }
\r
185 static void set_color(node_ptr n, color c)
\r
186 { n->parent_ = (node_ptr)((std::size_t)get_parent(n) | (std::size_t)c); }
\r
188 static color black()
\r
189 { return node::black_t; }
\r
192 { return node::red_t; }
\r
196 struct rbtree_node_traits_void_ptr<false>
\r
197 : public default_rbtree_node_traits_impl<void*>
\r
200 //This specialization will check if the pointer optimization is
\r
201 //possible with raw pointers
\r
203 struct rbtree_node_traits<void*>
\r
204 : public rbtree_node_traits_void_ptr
\r
205 <((boost::alignment_of< compact_node<void*> >::value % 2) == 0)>
\r
208 /////////////////////////////////////////////////////////////////////////////
\r
210 // Generic node_traits specialization for offset_ptr pointers //
\r
212 /////////////////////////////////////////////////////////////////////////////
\r
214 //This specialization, embeds the color in the parent pointer
\r
215 //so we save one word per node.
\r
216 //offset_ptr, uses the offset between the pointer and the pointee
\r
217 //as an internal member. The 1 byte offset is defined as a null pointer
\r
218 //so, unlike raw pointers, so if nodes are aligned to 4 bytes,
\r
219 //we will use the second bit as the color mark.
\r
220 template <bool FourByteAlignment>
\r
221 struct rbtree_node_traits_offset_ptr_void
\r
223 typedef compact_node<boost::interprocess::offset_ptr<void> > node;
\r
226 typedef boost::interprocess::offset_ptr<node> node_ptr;
\r
227 typedef boost::interprocess::offset_ptr<const node> const_node_ptr;
\r
231 typedef node::color color;
\r
233 static node_ptr get_parent(const_node_ptr n)
\r
234 { return node_ptr((node*)((std::size_t)n->parent_.get() & ~2)); }
\r
236 static void set_parent(node_ptr n, node_ptr p)
\r
238 n->parent_ = (node *)(((std::size_t)p.get()) | (((std::size_t)n->parent_.get()) & 2));
\r
241 static node_ptr get_left(const_node_ptr n)
\r
242 { return n->left_; }
\r
244 static void set_left(node_ptr n, node_ptr l)
\r
247 static node_ptr get_right(const_node_ptr n)
\r
248 { return n->right_; }
\r
250 static void set_right(node_ptr n, node_ptr r)
\r
253 static color get_color(const_node_ptr n)
\r
254 { return (color)(((std::size_t)n->parent_.get() & 2) >> 1); }
\r
256 static void set_color(node_ptr n, color c)
\r
257 { n->parent_ = (node *)((std::size_t)get_parent(n).get() | ((std::size_t)c << 1)); }
\r
259 static color black()
\r
260 { return node::black_t; }
\r
263 { return node::red_t; }
\r
266 //This is the specialization for nodes with no 4 byte alignment
\r
268 struct rbtree_node_traits_offset_ptr_void<false>
\r
269 : public default_rbtree_node_traits_impl< boost::interprocess::offset_ptr<void> >
\r
272 //This specialization will check if the pointer optimization is
\r
273 //possible with offset_ptr pointers
\r
275 struct rbtree_node_traits< boost::interprocess::offset_ptr<void> >
\r
276 : public rbtree_node_traits_offset_ptr_void
\r
277 <((boost::alignment_of
\r
278 < compact_node< boost::interprocess::offset_ptr<void> > >
\r
283 /////////////////////////////////////////////////////////////////////////////
\r
285 // A base class for the rbtree container //
\r
287 /////////////////////////////////////////////////////////////////////////////
\r
289 // rbtree_iterator provides some basic functions for a
\r
290 // rb tree node oriented bidirectional iterator:
\r
291 template<class T, class Self, class NodeTraits>
\r
292 class rbtree_iterator
\r
293 : public std::iterator<std::bidirectional_iterator_tag, T>
\r
295 typedef rbtree_algorithms<NodeTraits> node_algorithms;
\r
298 typedef typename NodeTraits::node node;
\r
299 typedef typename NodeTraits::node_ptr node_ptr;
\r
305 explicit rbtree_iterator (node_ptr node)
\r
309 node_ptr tree_node() const
\r
312 Self &operator=(const node_ptr &node)
\r
313 { node_ = node; return static_cast<Self&>(*this); }
\r
318 node_ = node_algorithms::next_node(node_);
\r
319 return static_cast<Self&> (*this);
\r
322 Self operator++(int)
\r
324 Self result (node_);
\r
325 node_ = node_algorithms::next_node (node_);
\r
331 node_ = node_algorithms::prev_node (node_);
\r
332 return static_cast<Self&> (*this);
\r
335 Self operator--(int)
\r
337 Self result (node_);
\r
338 node_ = node_algorithms::prev_node (node_);
\r
342 bool operator== (const Self& i) const
\r
343 { return node_ == i.tree_node(); }
\r
345 bool operator!= (const Self& i) const
\r
346 { return !operator== (i); }
\r
353 } //namespace detail
\r
354 } //namespace intrusive
\r
355 } //namespace boost
\r
357 #include "config_end.hpp"
\r
359 #endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP
\r