--- /dev/null
+/////////////////////////////////////////////////////////////////////////////\r
+//\r
+// (C) Copyright Olaf Krzikalla 2004-2006.\r
+// (C) Copyright Ion Gaztañaga 2006-2007.\r
+//\r
+// Distributed under the Boost Software License, Version 1.0.\r
+// (See accompanying file LICENSE_1_0.txt or copy at\r
+// http://www.boost.org/LICENSE_1_0.txt)\r
+//\r
+// See http://www.boost.org/libs/intrusive for documentation.\r
+//\r
+/////////////////////////////////////////////////////////////////////////////\r
+// The internal implementation of red-black trees is based on that of SGI STL\r
+// stl_tree.h file: \r
+//\r
+// Copyright (c) 1996,1997\r
+// Silicon Graphics Computer Systems, Inc.\r
+//\r
+// Permission to use, copy, modify, distribute and sell this software\r
+// and its documentation for any purpose is hereby granted without fee,\r
+// provided that the above copyright notice appear in all copies and\r
+// that both that copyright notice and this permission notice appear\r
+// in supporting documentation. Silicon Graphics makes no\r
+// representations about the suitability of this software for any\r
+// purpose. It is provided "as is" without express or implied warranty.\r
+//\r
+//\r
+// Copyright (c) 1994\r
+// Hewlett-Packard Company\r
+//\r
+// Permission to use, copy, modify, distribute and sell this software\r
+// and its documentation for any purpose is hereby granted without fee,\r
+// provided that the above copyright notice appear in all copies and\r
+// that both that copyright notice and this permission notice appear\r
+// in supporting documentation. Hewlett-Packard Company makes no\r
+// representations about the suitability of this software for any\r
+// purpose. It is provided "as is" without express or implied warranty.\r
+\r
+#ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP\r
+#define BOOST_INTRUSIVE_RBTREE_NODE_HPP\r
+\r
+#include "config_begin.hpp"\r
+#include <iterator>\r
+#include <boost/assert.hpp>\r
+#include "pointer_type.hpp"\r
+#include "pointer_to_other.hpp"\r
+#include "../rbtree_algorithms.hpp"\r
+#include <boost/get_pointer.hpp>\r
+//#include <boost/interprocess/offset_ptr.hpp>\r
+#include <boost/type_traits/alignment_of.hpp>\r
+#include <cstddef>\r
+#include <boost/detail/no_exceptions_support.hpp>\r
+\r
+namespace boost {\r
+namespace intrusive {\r
+namespace detail {\r
+\r
+/////////////////////////////////////////////////////////////////////////////\r
+// //\r
+// Generic node_traits for any pointer type //\r
+// //\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+//This is the default implementation, 3 generic pointers plus an enum\r
+template<class VoidPointer>\r
+struct default_rbtree_node_traits_impl\r
+{\r
+ struct node;\r
+\r
+ typedef typename boost::pointer_to_other\r
+ <VoidPointer, node>::type node_ptr;\r
+ typedef typename boost::pointer_to_other\r
+ <VoidPointer, const node>::type const_node_ptr;\r
+\r
+ struct node\r
+ {\r
+ enum color { red_t, black_t };\r
+\r
+ static color black()\r
+ { return black_t; }\r
+\r
+ static color red()\r
+ { return red_t; }\r
+\r
+ node_ptr parent_, left_, right_;\r
+ color color_;\r
+ };\r
+\r
+ typedef typename node::color color;\r
+\r
+ static node_ptr get_parent(const_node_ptr n)\r
+ { return n->parent_; }\r
+\r
+ static void set_parent(node_ptr n, node_ptr p)\r
+ { n->parent_ = p; }\r
+\r
+ static node_ptr get_left(const_node_ptr n)\r
+ { return n->left_; }\r
+\r
+ static void set_left(node_ptr n, node_ptr l)\r
+ { n->left_ = l; }\r
+\r
+ static node_ptr get_right(const_node_ptr n)\r
+ { return n->right_; }\r
+\r
+ static void set_right(node_ptr n, node_ptr r)\r
+ { n->right_ = r; }\r
+\r
+ static color get_color(const_node_ptr n)\r
+ { return n->color_; }\r
+\r
+ static void set_color(node_ptr n, color c)\r
+ { n->color_ = c; }\r
+\r
+ static color black()\r
+ { return node::black_t; }\r
+\r
+ static color red()\r
+ { return node::red_t; }\r
+};\r
+\r
+//The default possibility is the generic implementation\r
+template<class VoidPointer>\r
+struct rbtree_node_traits\r
+ : public default_rbtree_node_traits_impl<VoidPointer>\r
+{};\r
+\r
+//This is the compact representation: 3 pointers\r
+template<class VoidPointer>\r
+struct compact_node\r
+{\r
+ typedef typename boost::pointer_to_other\r
+ <VoidPointer, compact_node>::type node_ptr; \r
+\r
+ enum color { red_t, black_t };\r
+\r
+ static color black()\r
+ { return black_t; }\r
+\r
+ static color red()\r
+ { return red_t; }\r
+\r
+ node_ptr parent_, left_, right_;\r
+};\r
+\r
+/////////////////////////////////////////////////////////////////////////////\r
+// //\r
+// Generic node_traits specialization for raw pointers //\r
+// //\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+\r
+\r
+//This specialization, embeds the color in the parent pointer\r
+//so we save one word per node\r
+template <bool TwoByteAlignment>\r
+struct rbtree_node_traits_void_ptr\r
+{\r
+ typedef compact_node<void*> node;\r
+ typedef node * node_ptr;\r
+ typedef const node * const_node_ptr;\r
+ typedef node::color color;\r
+\r
+ static node_ptr get_parent(const_node_ptr n)\r
+ { return (node_ptr)((std::size_t)n->parent_ & ~1); }\r
+\r
+ static void set_parent(node_ptr n, node_ptr p)\r
+ { n->parent_ = (node_ptr)((std::size_t)p | ((std::size_t)n->parent_ & 1)); }\r
+\r
+ static node_ptr get_left(const_node_ptr n)\r
+ { return n->left_; }\r
+\r
+ static void set_left(node_ptr n, node_ptr l)\r
+ { n->left_ = l; }\r
+\r
+ static node_ptr get_right(const_node_ptr n)\r
+ { return n->right_; }\r
+\r
+ static void set_right(node_ptr n, node_ptr r)\r
+ { n->right_ = r; }\r
+\r
+ static color get_color(const_node_ptr n)\r
+ { return (color)((std::size_t)n->parent_ & 1); }\r
+\r
+ static void set_color(node_ptr n, color c)\r
+ { n->parent_ = (node_ptr)((std::size_t)get_parent(n) | (std::size_t)c); }\r
+\r
+ static color black()\r
+ { return node::black_t; }\r
+\r
+ static color red()\r
+ { return node::red_t; }\r
+};\r
+\r
+template<>\r
+struct rbtree_node_traits_void_ptr<false>\r
+ : public default_rbtree_node_traits_impl<void*>\r
+{};\r
+\r
+//This specialization will check if the pointer optimization is\r
+//possible with raw pointers\r
+template<>\r
+struct rbtree_node_traits<void*>\r
+ : public rbtree_node_traits_void_ptr\r
+ <((boost::alignment_of< compact_node<void*> >::value % 2) == 0)>\r
+{};\r
+/*\r
+/////////////////////////////////////////////////////////////////////////////\r
+// //\r
+// Generic node_traits specialization for offset_ptr pointers //\r
+// //\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+//This specialization, embeds the color in the parent pointer\r
+//so we save one word per node.\r
+//offset_ptr, uses the offset between the pointer and the pointee\r
+//as an internal member. The 1 byte offset is defined as a null pointer\r
+//so, unlike raw pointers, so if nodes are aligned to 4 bytes,\r
+//we will use the second bit as the color mark.\r
+template <bool FourByteAlignment>\r
+struct rbtree_node_traits_offset_ptr_void\r
+{\r
+ typedef compact_node<boost::interprocess::offset_ptr<void> > node;\r
+\r
+ private:\r
+ typedef boost::interprocess::offset_ptr<node> node_ptr;\r
+ typedef boost::interprocess::offset_ptr<const node> const_node_ptr;\r
+\r
+ public:\r
+\r
+ typedef node::color color;\r
+\r
+ static node_ptr get_parent(const_node_ptr n)\r
+ { return node_ptr((node*)((std::size_t)n->parent_.get() & ~2)); }\r
+\r
+ static void set_parent(node_ptr n, node_ptr p)\r
+ {\r
+ n->parent_ = (node *)(((std::size_t)p.get()) | (((std::size_t)n->parent_.get()) & 2)); \r
+ }\r
+\r
+ static node_ptr get_left(const_node_ptr n)\r
+ { return n->left_; }\r
+\r
+ static void set_left(node_ptr n, node_ptr l)\r
+ { n->left_ = l; }\r
+\r
+ static node_ptr get_right(const_node_ptr n)\r
+ { return n->right_; }\r
+\r
+ static void set_right(node_ptr n, node_ptr r)\r
+ { n->right_ = r; }\r
+\r
+ static color get_color(const_node_ptr n)\r
+ { return (color)(((std::size_t)n->parent_.get() & 2) >> 1); }\r
+\r
+ static void set_color(node_ptr n, color c)\r
+ { n->parent_ = (node *)((std::size_t)get_parent(n).get() | ((std::size_t)c << 1)); }\r
+\r
+ static color black()\r
+ { return node::black_t; }\r
+\r
+ static color red()\r
+ { return node::red_t; }\r
+};\r
+\r
+//This is the specialization for nodes with no 4 byte alignment\r
+template <>\r
+struct rbtree_node_traits_offset_ptr_void<false>\r
+ : public default_rbtree_node_traits_impl< boost::interprocess::offset_ptr<void> >\r
+{};\r
+\r
+//This specialization will check if the pointer optimization is\r
+//possible with offset_ptr pointers\r
+template<>\r
+struct rbtree_node_traits< boost::interprocess::offset_ptr<void> >\r
+ : public rbtree_node_traits_offset_ptr_void\r
+ <((boost::alignment_of\r
+ < compact_node< boost::interprocess::offset_ptr<void> > > \r
+ ::value % 4) == 0)\r
+ >\r
+{};\r
+*/\r
+/////////////////////////////////////////////////////////////////////////////\r
+// //\r
+// A base class for the rbtree container //\r
+// //\r
+/////////////////////////////////////////////////////////////////////////////\r
+\r
+// rbtree_iterator provides some basic functions for a \r
+// rb tree node oriented bidirectional iterator:\r
+template<class T, class Self, class NodeTraits>\r
+class rbtree_iterator\r
+ : public std::iterator<std::bidirectional_iterator_tag, T>\r
+{\r
+ typedef rbtree_algorithms<NodeTraits> node_algorithms;\r
+\r
+ protected:\r
+ typedef typename NodeTraits::node node;\r
+ typedef typename NodeTraits::node_ptr node_ptr;\r
+\r
+ rbtree_iterator ()\r
+ : node_ (0)\r
+ {}\r
+\r
+ explicit rbtree_iterator (node_ptr node)\r
+ : node_ (node)\r
+ {}\r
+\r
+ node_ptr tree_node() const\r
+ { return node_; }\r
+\r
+ Self &operator=(const node_ptr &node)\r
+ { node_ = node; return static_cast<Self&>(*this); }\r
+\r
+ public:\r
+ Self& operator++()\r
+ {\r
+ node_ = node_algorithms::next_node(node_);\r
+ return static_cast<Self&> (*this);\r
+ }\r
+\r
+ Self operator++(int)\r
+ {\r
+ Self result (node_);\r
+ node_ = node_algorithms::next_node (node_);\r
+ return result;\r
+ }\r
+\r
+ Self& operator--()\r
+ {\r
+ node_ = node_algorithms::prev_node (node_);\r
+ return static_cast<Self&> (*this);\r
+ }\r
+\r
+ Self operator--(int)\r
+ {\r
+ Self result (node_);\r
+ node_ = node_algorithms::prev_node (node_);\r
+ return result;\r
+ }\r
+\r
+ bool operator== (const Self& i) const\r
+ { return node_ == i.tree_node(); }\r
+\r
+ bool operator!= (const Self& i) const\r
+ { return !operator== (i); }\r
+\r
+ private:\r
+ node_ptr node_;\r
+};\r
+\r
+\r
+} //namespace detail \r
+} //namespace intrusive \r
+} //namespace boost \r
+\r
+#include "config_end.hpp"\r
+\r
+#endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP\r
projects / senf.git / blobdiff