utilities.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 630 行 · 第 1/2 页

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2006-2007
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/intrusive for documentation.
//
/////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP
#define BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP

#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/detail/pointer_to_other.hpp>
#include <boost/intrusive/detail/parent_from_member.hpp>
#include <boost/intrusive/detail/ebo_functor_holder.hpp>
#include <boost/intrusive/link_mode.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/assert.hpp>
#include <boost/cstdint.hpp>
#include <cstddef>
#include <climits>
#include <iterator>
#include <boost/cstdint.hpp>
#include <boost/static_assert.hpp>

namespace boost {
namespace intrusive {
namespace detail {

template <class T>
struct internal_member_value_traits
{
   template <class U> static detail::one test(...);
   template <class U> static detail::two test(typename U::member_value_traits* = 0);
   static const bool value = sizeof(test<T>(0)) == sizeof(detail::two);
};

template <class T>
struct internal_base_hook_bool
{
   template<bool Add>
   struct two_or_three {one _[2 + Add];};
   template <class U> static one test(...);
   template <class U> static two_or_three<U::boost_intrusive_tags::is_base_hook>
      test (detail::bool_<U::boost_intrusive_tags::is_base_hook>* = 0);
   static const std::size_t value = sizeof(test<T>(0));
};

template <class T>
struct internal_base_hook_bool_is_true
{
   static const bool value = internal_base_hook_bool<T>::value > sizeof(one)*2;
};

template <class T>
struct internal_any_hook_bool
{
   template<bool Add>
   struct two_or_three {one _[2 + Add];};
   template <class U> static one test(...);
   template <class U> static two_or_three<U::is_any_hook>
      test (detail::bool_<U::is_any_hook>* = 0);
   static const std::size_t value = sizeof(test<T>(0));
};

template <class T>
struct internal_any_hook_bool_is_true
{
   static const bool value = internal_any_hook_bool<T>::value > sizeof(one)*2;
};


template <class T>
struct external_value_traits_bool
{
   template<bool Add>
   struct two_or_three {one _[2 + Add];};
   template <class U> static one test(...);
   template <class U> static two_or_three<U::external_value_traits>
      test (detail::bool_<U::external_value_traits>* = 0);
   static const std::size_t value = sizeof(test<T>(0));
};

template <class T>
struct external_bucket_traits_bool
{
   template<bool Add>
   struct two_or_three {one _[2 + Add];};
   template <class U> static one test(...);
   template <class U> static two_or_three<U::external_bucket_traits>
      test (detail::bool_<U::external_bucket_traits>* = 0);
   static const std::size_t value = sizeof(test<T>(0));
};

template <class T>
struct external_value_traits_is_true
{
   static const bool value = external_value_traits_bool<T>::value > sizeof(one)*2;
};

template<class Node, class Tag, link_mode_type LinkMode, int>
struct node_holder
   :  public Node
{};

template<class SmartPtr>
struct smart_ptr_type
{
   typedef typename SmartPtr::value_type value_type;
   typedef value_type *pointer;
   static pointer get (const SmartPtr &smartptr)
   {  return smartptr.get();}
};

template<class T>
struct smart_ptr_type<T*>
{
   typedef T value_type;
   typedef value_type *pointer;
   static pointer get (pointer ptr)
   {  return ptr;}
};

//!Overload for smart pointers to avoid ADL problems with get_pointer
template<class Ptr>
inline typename smart_ptr_type<Ptr>::pointer
get_pointer(const Ptr &ptr)
{  return smart_ptr_type<Ptr>::get(ptr);   }

//This functor compares a stored value
//and the one passed as an argument
template<class ConstReference>
class equal_to_value
{
   ConstReference t_;

   public:
   equal_to_value(ConstReference t)
      :  t_(t)
   {}

   bool operator()(ConstReference t)const
   {  return t_ == t;   }
};

class null_disposer
{
   public:
   template <class Pointer>
   void operator()(Pointer)
   {}
};

template<class NodeAlgorithms>
class init_disposer
{
   typedef typename NodeAlgorithms::node_ptr node_ptr;

   public:
   void operator()(node_ptr p)
   {  NodeAlgorithms::init(p);   }
};

template<bool ConstantSize, class SizeType>
struct size_holder
{
   static const bool constant_time_size = ConstantSize;
   typedef SizeType  size_type;

   SizeType get_size() const
   {  return size_;  }

   void set_size(SizeType size)
   {  size_ = size; }

   void decrement()
   {  --size_; }

   void increment()
   {  ++size_; }

   SizeType size_;
};

template<class SizeType>
struct size_holder<false, SizeType>
{
   static const bool constant_time_size = false;
   typedef SizeType  size_type;

   size_type get_size() const
   {  return 0;  }

   void set_size(size_type)
   {}

   void decrement()
   {}

   void increment()
   {}
};

template<class KeyValueCompare, class Container>
struct key_nodeptr_comp
   :  private detail::ebo_functor_holder<KeyValueCompare>
{
   typedef typename Container::real_value_traits         real_value_traits;
   typedef typename real_value_traits::node_ptr          node_ptr;
   typedef detail::ebo_functor_holder<KeyValueCompare>   base_t;
   key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont)
      :  base_t(kcomp), cont_(cont)
   {}

   template<class KeyType>
   bool operator()(node_ptr node, const KeyType &key) const
   {  return base_t::get()(*cont_->get_real_value_traits().to_value_ptr(node), key); }

   template<class KeyType>
   bool operator()(const KeyType &key, node_ptr node) const
   {  return base_t::get()(key, *cont_->get_real_value_traits().to_value_ptr(node)); }

   bool operator()(node_ptr node1, node_ptr node2) const
   {
      return base_t::get()
         ( *cont_->get_real_value_traits().to_value_ptr(node1)
         , *cont_->get_real_value_traits().to_value_ptr(node2)
         ); 
   }

   const Container *cont_;
};

template<class F, class Container>
struct node_cloner
   :  private detail::ebo_functor_holder<F>
{
   typedef typename Container::real_value_traits         real_value_traits;
   typedef typename Container::node_algorithms           node_algorithms;
   typedef typename real_value_traits::value_type        value_type;
   typedef typename real_value_traits::pointer           pointer;
   typedef typename real_value_traits::node_traits::node node;
   typedef typename real_value_traits::node_ptr          node_ptr;
   typedef typename real_value_traits::const_node_ptr    const_node_ptr;
   typedef detail::ebo_functor_holder<F>                 base_t;
   enum { safemode_or_autounlink  = 
            (int)real_value_traits::link_mode == (int)auto_unlink   ||
            (int)real_value_traits::link_mode == (int)safe_link     };

   node_cloner(F f, const Container *cont)
      :  base_t(f), cont_(cont)
   {}

   node_ptr operator()(node_ptr p)
   {  return this->operator()(*p); }

   node_ptr operator()(const node &to_clone)
   {
      const value_type &v =
         *cont_->get_real_value_traits().to_value_ptr(const_node_ptr(&to_clone));
      node_ptr n = cont_->get_real_value_traits().to_node_ptr(*base_t::get()(v));
      //Cloned node must be in default mode if the linking mode requires it
      if(safemode_or_autounlink)
         BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n));
      return n;
   }

   const Container *cont_;
};

template<class F, class Container>
struct node_disposer
   :  private detail::ebo_functor_holder<F>
{
   typedef typename Container::real_value_traits   real_value_traits;
   typedef typename real_value_traits::node_ptr    node_ptr;
   typedef detail::ebo_functor_holder<F>           base_t;
   typedef typename Container::node_algorithms     node_algorithms;
   enum { safemode_or_autounlink  = 
            (int)real_value_traits::link_mode == (int)auto_unlink   ||
            (int)real_value_traits::link_mode == (int)safe_link     };

   node_disposer(F f, const Container *cont)
      :  base_t(f), cont_(cont)
   {}

   void operator()(node_ptr p)
   {
      if(safemode_or_autounlink)
         node_algorithms::init(p);
      base_t::get()(cont_->get_real_value_traits().to_value_ptr(p));
   }
   const Container *cont_;
};

struct dummy_constptr
{
   dummy_constptr(const void *)
   {}

   const void *get_ptr() const
   {  return 0;  }
};

template<class VoidPointer>
struct constptr
{
   typedef typename boost::pointer_to_other
      <VoidPointer, const void>::type ConstVoidPtr;

   constptr(const void *ptr)