boost/intrusive/detail/any_node_and_algorithms.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2008
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 #ifndef BOOST_INTRUSIVE_ANY_NODE_HPP
  14 #define BOOST_INTRUSIVE_ANY_NODE_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <iterator>
  18 #include <boost/intrusive/detail/assert.hpp>
  19 #include <boost/intrusive/detail/pointer_to_other.hpp>
  20 #include <cstddef>
  21 #include <boost/intrusive/detail/mpl.hpp>
  22
  23 namespace boost {
  24 namespace intrusive {
  25
  26 template<class VoidPointer>
  27 struct any_node
  28 {
  29    typedef typename boost::pointer_to_other
  30       <VoidPointer, any_node>::type   node_ptr;
  31    node_ptr    node_ptr_1;
  32    node_ptr    node_ptr_2;
  33    node_ptr    node_ptr_3;
  34    std::size_t size_t_1;
  35 };
  36
  37 template<class VoidPointer>
  38 struct any_list_node_traits
  39 {
  40    typedef any_node<VoidPointer> node;
  41    typedef typename boost::pointer_to_other
  42       <VoidPointer, node>::type          node_ptr;
  43    typedef typename boost::pointer_to_other
  44       <VoidPointer, const node>::type    const_node_ptr;
  45
  46    static node_ptr get_next(const_node_ptr n)
  47    {  return n->node_ptr_1;  }
  48
  49    static void set_next(node_ptr n, node_ptr next)
  50    {  n->node_ptr_1 = next;  }
  51
  52    static node_ptr get_previous(const_node_ptr n)
  53    {  return n->node_ptr_2;  }
  54
  55    static void set_previous(node_ptr n, node_ptr prev)
  56    {  n->node_ptr_2 = prev;  }
  57 };
  58
  59
  60 template<class VoidPointer>
  61 struct any_slist_node_traits
  62 {
  63    typedef any_node<VoidPointer> node;
  64    typedef typename boost::pointer_to_other
  65       <VoidPointer, node>::type          node_ptr;
  66    typedef typename boost::pointer_to_other
  67       <VoidPointer, const node>::type    const_node_ptr;
  68
  69    static node_ptr get_next(const_node_ptr n)
  70    {  return n->node_ptr_1;  }
  71
  72    static void set_next(node_ptr n, node_ptr next)
  73    {  n->node_ptr_1 = next;  }
  74 };
  75
  76
  77 template<class VoidPointer>
  78 struct any_unordered_node_traits
  79    :  public any_slist_node_traits<VoidPointer>
  80 {
  81    typedef any_slist_node_traits<VoidPointer>                  reduced_slist_node_traits;
  82    typedef typename reduced_slist_node_traits::node            node;
  83    typedef typename reduced_slist_node_traits::node_ptr        node_ptr;
  84    typedef typename reduced_slist_node_traits::const_node_ptr  const_node_ptr;
  85
  86    static const bool store_hash        = true;
  87    static const bool optimize_multikey = true;
  88
  89    static node_ptr get_next(const_node_ptr n)
  90    {  return node_ptr(&static_cast<node &>(*n->node_ptr_1));  }
  91
  92    static void set_next(node_ptr n, node_ptr next)
  93    {  n->node_ptr_1 = next;  }
  94
  95    static node_ptr get_prev_in_group(const_node_ptr n)
  96    {  return n->node_ptr_2;  }
  97
  98    static void set_prev_in_group(node_ptr n, node_ptr prev)
  99    {  n->node_ptr_2 = prev;  }
 100
 101    static std::size_t get_hash(const_node_ptr n)
 102    {  return n->size_t_1;  }
 103
 104    static void set_hash(node_ptr n, std::size_t h)
 105    {  n->size_t_1 = h;  }
 106 };
 107
 108
 109 template<class VoidPointer>
 110 struct any_rbtree_node_traits
 111 {
 112    typedef any_node<VoidPointer> node;
 113
 114    typedef typename boost::pointer_to_other
 115       <VoidPointer, node>::type          node_ptr;
 116    typedef typename boost::pointer_to_other
 117       <VoidPointer, const node>::type    const_node_ptr;
 118
 119    typedef std::size_t color;
 120
 121    static node_ptr get_parent(const_node_ptr n)
 122    {  return n->node_ptr_1;  }
 123
 124    static void set_parent(node_ptr n, node_ptr p)
 125    {  n->node_ptr_1 = p;  }
 126
 127    static node_ptr get_left(const_node_ptr n)
 128    {  return n->node_ptr_2;  }
 129
 130    static void set_left(node_ptr n, node_ptr l)
 131    {  n->node_ptr_2 = l;  }
 132
 133    static node_ptr get_right(const_node_ptr n)
 134    {  return n->node_ptr_3;  }
 135
 136    static void set_right(node_ptr n, node_ptr r)
 137    {  n->node_ptr_3 = r;  }
 138
 139    static color get_color(const_node_ptr n)
 140    {  return n->size_t_1;  }
 141
 142    static void set_color(node_ptr n, color c)
 143    {  n->size_t_1 = c;  }
 144
 145    static color black()
 146    {  return 0u;  }
 147
 148    static color red()
 149    {  return 1u;  }
 150 };
 151
 152
 153 template<class VoidPointer>
 154 struct any_avltree_node_traits
 155 {
 156    typedef any_node<VoidPointer> node;
 157
 158    typedef typename boost::pointer_to_other
 159       <VoidPointer, node>::type          node_ptr;
 160    typedef typename boost::pointer_to_other
 161       <VoidPointer, const node>::type    const_node_ptr;
 162    typedef std::size_t balance;
 163
 164    static node_ptr get_parent(const_node_ptr n)
 165    {  return n->node_ptr_1;  }
 166
 167    static void set_parent(node_ptr n, node_ptr p)
 168    {  n->node_ptr_1 = p;  }
 169
 170    static node_ptr get_left(const_node_ptr n)
 171    {  return n->node_ptr_2;  }
 172
 173    static void set_left(node_ptr n, node_ptr l)
 174    {  n->node_ptr_2 = l;  }
 175
 176    static node_ptr get_right(const_node_ptr n)
 177    {  return n->node_ptr_3;  }
 178
 179    static void set_right(node_ptr n, node_ptr r)
 180    {  n->node_ptr_3 = r;  }
 181
 182    static balance get_balance(const_node_ptr n)
 183    {  return n->size_t_1;  }
 184
 185    static void set_balance(node_ptr n, balance b)
 186    {  n->size_t_1 = b;  }
 187
 188    static balance negative()
 189    {  return 0u;  }
 190
 191    static balance zero()
 192    {  return 1u;  }
 193
 194    static balance positive()
 195    {  return 2u;  }
 196 };
 197
 198
 199 template<class VoidPointer>
 200 struct any_tree_node_traits
 201 {
 202    typedef any_node<VoidPointer> node;
 203
 204    typedef typename boost::pointer_to_other
 205       <VoidPointer, node>::type              node_ptr;
 206    typedef typename boost::pointer_to_other
 207       <VoidPointer, const node>::type        const_node_ptr;
 208
 209    static node_ptr get_parent(const_node_ptr n)
 210    {  return n->node_ptr_1;  }
 211
 212    static void set_parent(node_ptr n, node_ptr p)
 213    {  n->node_ptr_1 = p;  }
 214
 215    static node_ptr get_left(const_node_ptr n)
 216    {  return n->node_ptr_2;  }
 217
 218    static void set_left(node_ptr n, node_ptr l)
 219    {  n->node_ptr_2 = l;  }
 220
 221    static node_ptr get_right(const_node_ptr n)
 222    {  return n->node_ptr_3;  }
 223
 224    static void set_right(node_ptr n, node_ptr r)
 225    {  n->node_ptr_3 = r;  }
 226 };
 227
 228 template<class VoidPointer>
 229 class any_node_traits
 230 {
 231    public:
 232    typedef any_node<VoidPointer>          node;
 233    typedef typename boost::pointer_to_other
 234       <VoidPointer, node>::type          node_ptr;
 235    typedef typename boost::pointer_to_other
 236       <VoidPointer, const node>::type    const_node_ptr;
 237 };
 238
 239 template<class VoidPointer>
 240 class any_algorithms
 241 {
 242    template <class T>
 243    static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type)
 244    {}
 245
 246    public:
 247    typedef any_node<VoidPointer>             node;
 248    typedef typename boost::pointer_to_other
 249       <VoidPointer, node>::type              node_ptr;
 250    typedef typename boost::pointer_to_other
 251       <VoidPointer, const node>::type        const_node_ptr;
 252    typedef any_node_traits<VoidPointer>      node_traits;
 253
 254    //! <b>Requires</b>: node must not be part of any tree.
 255    //!
 256    //! <b>Effects</b>: After the function unique(node) == true.
 257    //!
 258    //! <b>Complexity</b>: Constant.
 259    //!
 260    //! <b>Throws</b>: Nothing.
 261    //!
 262    //! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree.
 263    static void init(node_ptr node)
 264    {  node->node_ptr_1 = 0;   };
 265
 266    //! <b>Effects</b>: Returns true if node is in the same state as if called init(node)
 267    //!
 268    //! <b>Complexity</b>: Constant.
 269    //!
 270    //! <b>Throws</b>: Nothing.
 271    static bool inited(const_node_ptr node)
 272    {  return !node->node_ptr_1;  };
 273
 274    static bool unique(const_node_ptr node)
 275    {  return 0 == node->node_ptr_1; }
 276
 277    static void unlink(node_ptr)
 278    {
 279       //Auto-unlink hooks and unlink() are not available for any hooks
 280       any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>();
 281    }
 282
 283    static void swap_nodes(node_ptr l, node_ptr r)
 284    {
 285       //Any nodes have no swap_nodes capability because they don't know
 286       //what algorithm they must use to unlink the node from the container
 287       any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>();
 288    }
 289 };
 290
 291 } //namespace intrusive
 292 } //namespace boost
 293
 294 #include <boost/intrusive/detail/config_end.hpp>
 295
 296 #endif //BOOST_INTRUSIVE_ANY_NODE_HPP