boost/intrusive/detail/any_node_and_algorithms.hpp

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