boost/intrusive/detail/rbtree_node.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Olaf Krzikalla 2004-2006.\r
   4 // (C) Copyright Ion Gaztañaga  2006-2007.\r
   5 //\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
   9 //\r
  10 // See http://www.boost.org/libs/intrusive for documentation.\r
  11 //\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
  15 //\r
  16 // Copyright (c) 1996,1997\r
  17 // Silicon Graphics Computer Systems, Inc.\r
  18 //\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
  26 //\r
  27 //\r
  28 // Copyright (c) 1994\r
  29 // Hewlett-Packard Company\r
  30 //\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
  38 \r
  39 #ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP\r
  40 #define BOOST_INTRUSIVE_RBTREE_NODE_HPP\r
  41 \r
  42 #include "config_begin.hpp"\r
  43 #include <iterator>\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
  51 #include <cstddef>\r
  52 #include <boost/detail/no_exceptions_support.hpp>\r
  53 \r
  54 namespace boost {\r
  55 namespace intrusive {\r
  56 namespace detail {\r
  57 \r
  58 /////////////////////////////////////////////////////////////////////////////\r
  59 //                                                                         //\r
  60 //                Generic node_traits for any pointer type                 //\r
  61 //                                                                         //\r
  62 /////////////////////////////////////////////////////////////////////////////\r
  63 \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
  67 {\r
  68    struct node;\r
  69 \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
  74 \r
  75    struct node\r
  76    {\r
  77       enum color { red_t, black_t };\r
  78 \r
  79       static color black()\r
  80       {  return black_t;  }\r
  81 \r
  82       static color red()\r
  83       {  return red_t;  }\r
  84 \r
  85       node_ptr parent_, left_, right_;\r
  86       color color_;\r
  87    };\r
  88 \r
  89    typedef typename node::color color;\r
  90 \r
  91    static node_ptr get_parent(const_node_ptr n)\r
  92    {  return n->parent_;  }\r
  93 \r
  94    static void set_parent(node_ptr n, node_ptr p)\r
  95    {  n->parent_ = p;  }\r
  96 \r
  97    static node_ptr get_left(const_node_ptr n)\r
  98    {  return n->left_;  }\r
  99 \r
 100    static void set_left(node_ptr n, node_ptr l)\r
 101    {  n->left_ = l;  }\r
 102 \r
 103    static node_ptr get_right(const_node_ptr n)\r
 104    {  return n->right_;  }\r
 105 \r
 106    static void set_right(node_ptr n, node_ptr r)\r
 107    {  n->right_ = r;  }\r
 108 \r
 109    static color get_color(const_node_ptr n)\r
 110    {  return n->color_;  }\r
 111 \r
 112    static void set_color(node_ptr n, color c)\r
 113    {  n->color_ = c;  }\r
 114 \r
 115    static color black()\r
 116    {  return node::black_t;  }\r
 117 \r
 118    static color red()\r
 119    {  return node::red_t;  }\r
 120 };\r
 121 \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
 126 {};\r
 127 \r
 128 //This is the compact representation: 3 pointers\r
 129 template<class VoidPointer>\r
 130 struct compact_node\r
 131 {\r
 132    typedef typename boost::pointer_to_other\r
 133       <VoidPointer, compact_node>::type          node_ptr;   \r
 134 \r
 135    enum color { red_t, black_t };\r
 136 \r
 137    static color black()\r
 138    {  return black_t;  }\r
 139 \r
 140    static color red()\r
 141    {  return red_t;  }\r
 142 \r
 143    node_ptr parent_, left_, right_;\r
 144 };\r
 145 \r
 146 /////////////////////////////////////////////////////////////////////////////\r
 147 //                                                                         //\r
 148 //          Generic node_traits specialization for raw pointers            //\r
 149 //                                                                         //\r
 150 /////////////////////////////////////////////////////////////////////////////\r
 151 \r
 152 \r
 153 \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
 158 {\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
 163 \r
 164    static node_ptr get_parent(const_node_ptr n)\r
 165    {  return (node_ptr)((std::size_t)n->parent_ & ~1);  }\r
 166 \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
 169 \r
 170    static node_ptr get_left(const_node_ptr n)\r
 171    {  return n->left_;  }\r
 172 \r
 173    static void set_left(node_ptr n, node_ptr l)\r
 174    {  n->left_ = l;  }\r
 175 \r
 176    static node_ptr get_right(const_node_ptr n)\r
 177    {  return n->right_;  }\r
 178 \r
 179    static void set_right(node_ptr n, node_ptr r)\r
 180    {  n->right_ = r;  }\r
 181 \r
 182    static color get_color(const_node_ptr n)\r
 183    {  return (color)((std::size_t)n->parent_ & 1);  }\r
 184 \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
 187 \r
 188    static color black()\r
 189    {  return node::black_t;  }\r
 190 \r
 191    static color red()\r
 192    {  return node::red_t;  }\r
 193 };\r
 194 \r
 195 template<>\r
 196 struct rbtree_node_traits_void_ptr<false>\r
 197    :  public default_rbtree_node_traits_impl<void*>\r
 198 {};\r
 199 \r
 200 //This specialization will check if the pointer optimization is\r
 201 //possible with raw pointers\r
 202 template<>\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
 206 {};\r
 207 /*\r
 208 /////////////////////////////////////////////////////////////////////////////\r
 209 //                                                                         //\r
 210 //       Generic node_traits specialization for offset_ptr pointers        //\r
 211 //                                                                         //\r
 212 /////////////////////////////////////////////////////////////////////////////\r
 213 \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
 222 {\r
 223    typedef compact_node<boost::interprocess::offset_ptr<void> > node;\r
 224 \r
 225    private:\r
 226    typedef boost::interprocess::offset_ptr<node>         node_ptr;\r
 227    typedef boost::interprocess::offset_ptr<const node>   const_node_ptr;\r
 228 \r
 229    public:\r
 230 \r
 231    typedef node::color color;\r
 232 \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
 235 \r
 236    static void set_parent(node_ptr n, node_ptr p)\r
 237    {\r
 238       n->parent_ = (node *)(((std::size_t)p.get()) | (((std::size_t)n->parent_.get()) & 2)); \r
 239    }\r
 240 \r
 241    static node_ptr get_left(const_node_ptr n)\r
 242    {  return n->left_;  }\r
 243 \r
 244    static void set_left(node_ptr n, node_ptr l)\r
 245    {  n->left_ = l;  }\r
 246 \r
 247    static node_ptr get_right(const_node_ptr n)\r
 248    {  return n->right_;  }\r
 249 \r
 250    static void set_right(node_ptr n, node_ptr r)\r
 251    {  n->right_ = r;  }\r
 252 \r
 253    static color get_color(const_node_ptr n)\r
 254    {  return (color)(((std::size_t)n->parent_.get() & 2) >> 1);  }\r
 255 \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
 258 \r
 259    static color black()\r
 260    {  return node::black_t;  }\r
 261 \r
 262    static color red()\r
 263    {  return node::red_t;  }\r
 264 };\r
 265 \r
 266 //This is the specialization for nodes with no 4 byte alignment\r
 267 template <>\r
 268 struct rbtree_node_traits_offset_ptr_void<false>\r
 269    :  public default_rbtree_node_traits_impl< boost::interprocess::offset_ptr<void> >\r
 270 {};\r
 271 \r
 272 //This specialization will check if the pointer optimization is\r
 273 //possible with offset_ptr pointers\r
 274 template<>\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
 279             ::value % 4) == 0)\r
 280          >\r
 281 {};\r
 282 */\r
 283 /////////////////////////////////////////////////////////////////////////////\r
 284 //                                                                         //\r
 285 //                A base class for the rbtree container                    //\r
 286 //                                                                         //\r
 287 /////////////////////////////////////////////////////////////////////////////\r
 288 \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
 294 {\r
 295    typedef rbtree_algorithms<NodeTraits> node_algorithms;\r
 296 \r
 297    protected:\r
 298    typedef typename NodeTraits::node            node;\r
 299    typedef typename NodeTraits::node_ptr        node_ptr;\r
 300 \r
 301    rbtree_iterator ()\r
 302       :  node_ (0)\r
 303    {}\r
 304 \r
 305    explicit rbtree_iterator (node_ptr node)\r
 306       :  node_ (node)\r
 307    {}\r
 308 \r
 309    node_ptr tree_node() const\r
 310    { return node_; }\r
 311 \r
 312    Self &operator=(const node_ptr &node)\r
 313    {  node_ = node;  return static_cast<Self&>(*this);  }\r
 314 \r
 315    public:\r
 316    Self& operator++()\r
 317    {\r
 318       node_ = node_algorithms::next_node(node_);\r
 319       return static_cast<Self&> (*this);\r
 320    }\r
 321 \r
 322    Self operator++(int)\r
 323    {\r
 324       Self result (node_);\r
 325       node_ = node_algorithms::next_node (node_);\r
 326       return result;\r
 327    }\r
 328 \r
 329    Self& operator--()\r
 330    {\r
 331       node_ = node_algorithms::prev_node (node_);\r
 332       return static_cast<Self&> (*this);\r
 333    }\r
 334 \r
 335    Self operator--(int)\r
 336    {\r
 337       Self result (node_);\r
 338       node_ = node_algorithms::prev_node (node_);\r
 339       return result;\r
 340    }\r
 341 \r
 342    bool operator== (const Self& i) const\r
 343    { return node_ == i.tree_node(); }\r
 344 \r
 345    bool operator!= (const Self& i) const\r
 346    { return !operator== (i); }\r
 347 \r
 348    private:\r
 349    node_ptr node_;\r
 350 };\r
 351 \r
 352 \r
 353 } //namespace detail \r
 354 } //namespace intrusive \r
 355 } //namespace boost \r
 356 \r
 357 #include "config_end.hpp"\r
 358 \r
 359 #endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP\r