tree.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2008. 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/interprocess for documentation.
//
//////////////////////////////////////////////////////////////////////////////
//
// This file comes from SGI's stl_tree file. Modified by Ion Gaztanaga 2005.
// Renaming, isolating and porting to generic algorithms. Pointer typedef 
// set to allocator::pointer to allow placing it in shared memory.
//
///////////////////////////////////////////////////////////////////////////////
/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */
#ifndef BOOST_INTERPROCESS_TREE_HPP
#define BOOST_INTERPROCESS_TREE_HPP

#include <boost/interprocess/detail/config_begin.hpp>
#include <boost/interprocess/detail/workaround.hpp>

#include <boost/interprocess/detail/move.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/algorithms.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/interprocess/containers/detail/node_alloc_holder.hpp>
#include <boost/intrusive/rbtree.hpp>
#ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING
#include <boost/interprocess/detail/preprocessor.hpp>
#endif

#include <utility>   //std::pair
#include <iterator>
#include <algorithm>

namespace boost {
namespace interprocess {
namespace detail {

template<class Key, class Value, class KeyCompare, class KeyOfValue>
struct value_compare_impl
   :  public KeyCompare
{
   typedef Value        value_type;
   typedef KeyCompare   key_compare; 
   typedef KeyOfValue   key_of_value;
   typedef Key          key_type;

   value_compare_impl(key_compare kcomp)
      :  key_compare(kcomp)
   {}

   const key_compare &key_comp() const
   {  return static_cast<const key_compare &>(*this);  }

   key_compare &key_comp()
   {  return static_cast<key_compare &>(*this);  }

   template<class A, class B>
   bool operator()(const A &a, const B &b) const
   {  return key_compare::operator()(KeyOfValue()(a), KeyOfValue()(b)); }
};

template<class VoidPointer>
struct rbtree_hook
{
   typedef typename bi::make_set_base_hook
      < bi::void_pointer<VoidPointer>
      , bi::link_mode<bi::normal_link>
      , bi::optimize_size<true>
      >::type  type;
};

template<class T>
struct rbtree_type
{
   typedef T type;
};

template<class T1, class T2>
struct rbtree_type< std::pair<T1, T2> >
{
   typedef detail::pair<T1, T2> type;
};

template <class T, class VoidPointer>
struct rbtree_node
   :  public rbtree_hook<VoidPointer>::type
{
   typedef typename rbtree_hook<VoidPointer>::type hook_type;

   typedef T value_type;
   typedef typename rbtree_type<T>::type internal_type;

   typedef rbtree_node<T, VoidPointer> node_type;

   #ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING

   rbtree_node()
      : m_data()
   {}

   #define BOOST_PP_LOCAL_MACRO(n)                                                           \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
   rbtree_node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))                        \
      : m_data(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _))                     \
   {}                                                                                        \
   //!
   #define BOOST_PP_LOCAL_LIMITS (1, BOOST_INTERPROCESS_MAX_CONSTRUCTOR_PARAMETERS)
   #include BOOST_PP_LOCAL_ITERATE()

   #else //#ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING

   template<class ...Args>
   rbtree_node(Args &&...args)
      : m_data(detail::forward_impl<Args>(args)...)
   {}
   #endif//#ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING

   rbtree_node &operator=(const rbtree_node &other)
   {  do_assign(other.m_data);   return *this;  }

   T &get_data()
   {
      T* ptr = reinterpret_cast<T*>(&this->m_data);
      return *ptr;
   }

   const T &get_data() const
   {
      const T* ptr = reinterpret_cast<const T*>(&this->m_data);
      return *ptr;
   }

   private:
   internal_type m_data;

   template<class A, class B>
   void do_assign(const std::pair<const A, B> &p)
   {
      const_cast<A&>(m_data.first) = p.first;
      m_data.second  = p.second;
   }

   template<class A, class B>
   void do_assign(const detail::pair<const A, B> &p)
   {
      const_cast<A&>(m_data.first) = p.first;
      m_data.second  = p.second;
   }

   template<class V>
   void do_assign(const V &v)
   {  m_data = v; }

   public:
   template<class Convertible>

   static void construct(node_type *ptr
   #if !defined(BOOST_INTERPROCESS_RVALUE_REFERENCE)
   , const Convertible &value)
   #else
   , Convertible &&value)
   #endif
   {  new(ptr) node_type(detail::forward_impl<Convertible>(value));  }
};

}//namespace detail {
#if !defined(BOOST_INTERPROCESS_RVALUE_REFERENCE) || !defined(BOOST_INTERPROCESS_RVALUE_PAIR)
template<class T, class VoidPointer>
struct has_own_construct_from_it
   < boost::interprocess::detail::rbtree_node<T, VoidPointer> >
{
   static const bool value = true;
};
#endif
namespace detail {

template<class A, class ValueCompare>
struct intrusive_rbtree_type
{
   typedef typename A::value_type                  value_type;
   typedef typename detail::pointer_to_other
      <typename A::pointer, void>::type            void_pointer;
   typedef typename detail::rbtree_node
         <value_type, void_pointer>                node_type;
   typedef node_compare<ValueCompare, node_type>   node_compare_type;
   typedef typename bi::make_rbtree
      <node_type
      ,bi::compare<node_compare_type>
      ,bi::base_hook<typename rbtree_hook<void_pointer>::type>
      ,bi::constant_time_size<true>
      ,bi::size_type<typename A::size_type>
      >::type                                      container_type;
   typedef container_type                          type ;
};

}  //namespace detail {

namespace detail {

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
class rbtree
   : protected detail::node_alloc_holder
      <A, typename detail::intrusive_rbtree_type
         <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue>  
         >::type
      >
{
   typedef typename detail::intrusive_rbtree_type
         <A, value_compare_impl
            <Key, Value, KeyCompare, KeyOfValue>
         >::type                                      Icont;
   typedef detail::node_alloc_holder<A, Icont>        AllocHolder;
   typedef typename AllocHolder::NodePtr              NodePtr;
   typedef rbtree < Key, Value, KeyOfValue
                  , KeyCompare, A>                    ThisType;
   typedef typename AllocHolder::NodeAlloc            NodeAlloc;
   typedef typename AllocHolder::ValAlloc             ValAlloc;
   typedef typename AllocHolder::Node                 Node;
   typedef typename Icont::iterator                   iiterator;
   typedef typename Icont::const_iterator             iconst_iterator;
   typedef detail::allocator_destroyer<NodeAlloc>     Destroyer;
   typedef typename AllocHolder::allocator_v1         allocator_v1;
   typedef typename AllocHolder::allocator_v2         allocator_v2;
   typedef typename AllocHolder::alloc_version        alloc_version;

   class RecyclingCloner;
   friend class RecyclingCloner;
   
   class RecyclingCloner
   {
      public:
      RecyclingCloner(AllocHolder &holder, Icont &irbtree)
         :  m_holder(holder), m_icont(irbtree)
      {}

      NodePtr operator()(const Node &other) const
      {
//         if(!m_icont.empty()){
         if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){
            //First recycle a node (this can't throw)
            //NodePtr p = m_icont.unlink_leftmost_without_rebalance();
            try{
               //This can throw
               *p = other;
               return p;
            }
            catch(...){
               //If there is an exception destroy the whole source
               m_holder.destroy_node(p);
               while((p = m_icont.unlink_leftmost_without_rebalance())){
                  m_holder.destroy_node(p);
               }
               throw;
            }
         }
         else{
            return m_holder.create_node(other);
         }
      }

      AllocHolder &m_holder;
      Icont &m_icont;
   };

   public:
   typedef Key                                        key_type;
   typedef Value                                      value_type;
   typedef A                                          allocator_type;
   typedef KeyCompare                                 key_compare;
   typedef value_compare_impl< Key, Value
                        , KeyCompare, KeyOfValue>     value_compare;
   typedef typename A::pointer                        pointer;
   typedef typename A::const_pointer                  const_pointer;
   typedef typename A::reference                      reference;
   typedef typename A::const_reference                const_reference;
   typedef typename A::size_type                      size_type;
   typedef typename A::difference_type                difference_type;
   typedef difference_type                            rbtree_difference_type;
   typedef pointer                                    rbtree_pointer;
   typedef const_pointer                              rbtree_const_pointer;
   typedef reference                                  rbtree_reference;
   typedef const_reference                            rbtree_const_reference;
   typedef NodeAlloc                                  stored_allocator_type;

   private:

   template<class KeyValueCompare>
   struct key_node_compare
      :  private KeyValueCompare
   {
      key_node_compare(KeyValueCompare comp)
         :  KeyValueCompare(comp)
      {}
      
      template<class KeyType>
      bool operator()(const Node &n, const KeyType &k) const
      {  return KeyValueCompare::operator()(n.get_data(), k);  }

      template<class KeyType>
      bool operator()(const KeyType &k, const Node &n) const
      {  return KeyValueCompare::operator()(k, n.get_data());  }
   };

   typedef key_node_compare<value_compare>  KeyNodeCompare;

   public:
   //rbtree const_iterator
   class const_iterator
      : public std::iterator
         < std::bidirectional_iterator_tag
         , value_type            , rbtree_difference_type
         , rbtree_const_pointer  , rbtree_const_reference>
   {
      protected:
      typedef typename Icont::iterator  iiterator;
      iiterator m_it;
      explicit const_iterator(iiterator it)  : m_it(it){}
      void prot_incr() { ++m_it; }
      void prot_decr() { --m_it; }

      private:
      iiterator get()
      {  return this->m_it;   }

      public:
      friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
      typedef rbtree_difference_type        difference_type;

      //Constructors
      const_iterator()
         :  m_it()
      {}

      //Pointer like operators
      const_reference operator*()  const 
      { return  m_it->get_data();  }

      const_pointer   operator->() const 
      { return  const_pointer(&m_it->get_data()); }

      //Increment / Decrement