boost_ext/boost/multi_index/detail/hash_index_node.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
  11
  12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <boost/detail/allocator_utilities.hpp>
  18 #include <boost/multi_index/detail/prevent_eti.hpp>
  19 #include <functional>
  20
  21 namespace boost{
  22
  23 namespace multi_index{
  24
  25 namespace detail{
  26
  27 /* singly-linked node for use by hashed_index */
  28
  29 template<typename Allocator>
  30 struct hashed_index_node_impl
  31 {
  32   typedef typename prevent_eti<
  33     Allocator,
  34     typename boost::detail::allocator::rebind_to<
  35       Allocator,hashed_index_node_impl
  36     >::type
  37   >::type::pointer                                pointer;
  38   typedef typename prevent_eti<
  39     Allocator,
  40     typename boost::detail::allocator::rebind_to<
  41       Allocator,hashed_index_node_impl
  42     >::type
  43   >::type::const_pointer                          const_pointer;
  44
  45   pointer& next(){return next_;}
  46   pointer  next()const{return next_;}
  47
  48   /* algorithmic stuff */
  49
  50   static void increment(pointer& x,pointer bbegin,pointer bbend)
  51   {
  52     std::less_equal<pointer> leq;
  53
  54     x=x->next();
  55     if(leq(bbegin,x)&&leq(x,bbend)){ /* bucket node */
  56       do{
  57         ++x;
  58       }while(x->next()==x);
  59       x=x->next();
  60     }
  61   }
  62
  63   static void link(pointer x,pointer pos)
  64   {
  65     x->next()=pos->next();
  66     pos->next()=x;
  67   };
  68
  69   static void unlink(pointer x)
  70   {
  71     pointer y=x->next();
  72     while(y->next()!=x){y=y->next();}
  73     y->next()=x->next();
  74   }
  75
  76   static pointer prev(pointer x)
  77   {
  78     pointer y=x->next();
  79     while(y->next()!=x){y=y->next();}
  80     return y;
  81   }
  82
  83   static void unlink_next(pointer x)
  84   {
  85     x->next()=x->next()->next();
  86   }
  87
  88 private:
  89   pointer next_;
  90 };
  91
  92 template<typename Super>
  93 struct hashed_index_node_trampoline:
  94   prevent_eti<
  95     Super,
  96     hashed_index_node_impl<
  97       typename boost::detail::allocator::rebind_to<
  98         typename Super::allocator_type,
  99         void
 100       >::type
 101     >
 102   >::type
 103 {
 104   typedef typename prevent_eti<
 105     Super,
 106     hashed_index_node_impl<
 107       typename boost::detail::allocator::rebind_to<
 108         typename Super::allocator_type,
 109         void
 110       >::type
 111     >
 112   >::type impl_type;
 113 };
 114
 115 template<typename Super>
 116 struct hashed_index_node:Super,hashed_index_node_trampoline<Super>
 117 {
 118 private:
 119   typedef hashed_index_node_trampoline<Super> trampoline;
 120
 121 public:
 122   typedef typename trampoline::impl_type     impl_type;
 123   typedef typename trampoline::pointer       impl_pointer;
 124   typedef typename trampoline::const_pointer const_impl_pointer;
 125
 126   impl_pointer impl()
 127   {
 128     return static_cast<impl_pointer>(
 129       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 130   }
 131
 132   const_impl_pointer impl()const
 133   {
 134     return static_cast<const_impl_pointer>(
 135       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 136   }
 137
 138   static hashed_index_node* from_impl(impl_pointer x)
 139   {
 140     return static_cast<hashed_index_node*>(
 141       static_cast<trampoline*>(&*x));
 142   }
 143
 144   static const hashed_index_node* from_impl(const_impl_pointer x)
 145   {
 146     return static_cast<const hashed_index_node*>(
 147       static_cast<const trampoline*>(&*x));
 148   }
 149
 150   static void increment(
 151     hashed_index_node*& x,impl_pointer bbegin,impl_pointer bend)
 152   {
 153     impl_pointer xi=x->impl();
 154     trampoline::increment(xi,bbegin,bend);
 155     x=from_impl(xi);
 156   }
 157 };
 158
 159 } /* namespace multi_index::detail */
 160
 161 } /* namespace multi_index */
 162
 163 } /* namespace boost */
 164
 165 #endif