Mercurial > hg > vamp-build-and-test

comparison DEPENDENCIES/generic/include/boost/intrusive/detail/rbtree_node.hpp @ 101:c530137014c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update Boost headers (1.58.0)
author Chris Cannam
date Mon, 07 Sep 2015 11:12:49 +0100
parents 2665513ce2d3
children
comparison
equal deleted inserted replaced
100:793467b5e61c 101:c530137014c0
12 ///////////////////////////////////////////////////////////////////////////// 12 /////////////////////////////////////////////////////////////////////////////
13 13
14 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP 14 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP
15 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP 15 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP
16 16
17 #ifndef BOOST_CONFIG_HPP
18 # include <boost/config.hpp>
19 #endif
20
21 #if defined(BOOST_HAS_PRAGMA_ONCE)
22 # pragma once
23 #endif
24
17 #include <boost/intrusive/detail/config_begin.hpp> 25 #include <boost/intrusive/detail/config_begin.hpp>
18 #include <iterator> 26 #include <boost/intrusive/pointer_rebind.hpp>
19 #include <boost/intrusive/pointer_traits.hpp>
20 #include <boost/intrusive/rbtree_algorithms.hpp> 27 #include <boost/intrusive/rbtree_algorithms.hpp>
21 #include <boost/intrusive/pointer_plus_bits.hpp> 28 #include <boost/intrusive/pointer_plus_bits.hpp>
22 #include <boost/intrusive/detail/mpl.hpp> 29 #include <boost/intrusive/detail/mpl.hpp>
23 #include <boost/intrusive/detail/utilities.hpp>
24 #include <boost/intrusive/detail/tree_node.hpp> 30 #include <boost/intrusive/detail/tree_node.hpp>
25 31
26 namespace boost { 32 namespace boost {
27 namespace intrusive { 33 namespace intrusive {
28 34
34 40
35 //This is the compact representation: 3 pointers 41 //This is the compact representation: 3 pointers
36 template<class VoidPointer> 42 template<class VoidPointer>
37 struct compact_rbtree_node 43 struct compact_rbtree_node
38 { 44 {
39 typedef typename pointer_traits 45 typedef compact_rbtree_node<VoidPointer> node;
40 <VoidPointer>::template rebind_pointer 46 typedef typename pointer_rebind<VoidPointer, node >::type node_ptr;
41 <compact_rbtree_node<VoidPointer> >::type node_ptr; 47 typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr;
42 enum color { red_t, black_t }; 48 enum color { red_t, black_t };
43 node_ptr parent_, left_, right_; 49 node_ptr parent_, left_, right_;
44 }; 50 };
45 51
46 //This is the normal representation: 3 pointers + enum 52 //This is the normal representation: 3 pointers + enum
47 template<class VoidPointer> 53 template<class VoidPointer>
48 struct rbtree_node 54 struct rbtree_node
49 { 55 {
50 typedef typename pointer_traits 56 typedef rbtree_node<VoidPointer> node;
51 <VoidPointer>::template rebind_pointer 57 typedef typename pointer_rebind<VoidPointer, node >::type node_ptr;
52 <rbtree_node<VoidPointer> >::type node_ptr; 58 typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr;
53 59
54 enum color { red_t, black_t }; 60 enum color { red_t, black_t };
55 node_ptr parent_, left_, right_; 61 node_ptr parent_, left_, right_;
56 color color_; 62 color color_;
57 }; 63 };
60 //using a node with 3 generic pointers plus an enum 66 //using a node with 3 generic pointers plus an enum
61 template<class VoidPointer> 67 template<class VoidPointer>
62 struct default_rbtree_node_traits_impl 68 struct default_rbtree_node_traits_impl
63 { 69 {
64 typedef rbtree_node<VoidPointer> node; 70 typedef rbtree_node<VoidPointer> node;
65 71 typedef typename node::node_ptr node_ptr;
66 typedef typename pointer_traits 72 typedef typename node::const_node_ptr const_node_ptr;
67 <VoidPointer>::template rebind_pointer<node>::type node_ptr;
68 typedef typename pointer_traits
69 <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr;
70 73
71 typedef typename node::color color; 74 typedef typename node::color color;
72 75
73 static node_ptr get_parent(const const_node_ptr & n) 76 static node_ptr get_parent(const const_node_ptr & n)
74 { return n->parent_; } 77 { return n->parent_; }
117 //using a node with 3 generic pointers 120 //using a node with 3 generic pointers
118 template<class VoidPointer> 121 template<class VoidPointer>
119 struct compact_rbtree_node_traits_impl 122 struct compact_rbtree_node_traits_impl
120 { 123 {
121 typedef compact_rbtree_node<VoidPointer> node; 124 typedef compact_rbtree_node<VoidPointer> node;
122 typedef typename pointer_traits 125 typedef typename node::node_ptr node_ptr;
123 <VoidPointer>::template rebind_pointer<node>::type node_ptr; 126 typedef typename node::const_node_ptr const_node_ptr;
124 typedef typename pointer_traits
125 <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr;
126 127
127 typedef pointer_plus_bits<node_ptr, 1> ptr_bit; 128 typedef pointer_plus_bits<node_ptr, 1> ptr_bit;
128 129
129 typedef typename node::color color; 130 typedef typename node::color color;
130 131
180 template<class VoidPointer> 181 template<class VoidPointer>
181 struct rbtree_node_traits_dispatch<VoidPointer, true> 182 struct rbtree_node_traits_dispatch<VoidPointer, true>
182 : public compact_rbtree_node_traits_impl<VoidPointer> 183 : public compact_rbtree_node_traits_impl<VoidPointer>
183 {}; 184 {};
184 185
185 //Inherit from the detail::link_dispatch depending on the embedding capabilities 186 //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
186 template<class VoidPointer, bool OptimizeSize = false> 187 template<class VoidPointer, bool OptimizeSize = false>
187 struct rbtree_node_traits 188 struct rbtree_node_traits
188 : public rbtree_node_traits_dispatch 189 : public rbtree_node_traits_dispatch
189 < VoidPointer 190 < VoidPointer
190 , OptimizeSize && 191 , OptimizeSize &&