tree.hpp

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

      NodePtr p(AllocHolder::create_node());
      return iterator(this->icont().insert_equal(this->icont().end(), *p));
   }

   iterator emplace_hint_equal(const_iterator hint)
   {
      NodePtr p(AllocHolder::create_node());
      return iterator(this->icont().insert_equal(hint.get(), *p));
   }

   #define BOOST_PP_LOCAL_MACRO(n)                                                                          \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
   iterator emplace_unique(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))                           \
   {                                                                                                        \
      return this->emplace_unique_impl                                                                      \
         (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _)));              \
   }                                                                                                        \
                                                                                                            \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
   iterator emplace_hint_unique(const_iterator hint, BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _)) \
   {                                                                                                        \
      return this->emplace_unique_hint_impl                                                                 \
         (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _)));        \
   }                                                                                                        \
                                                                                                            \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
   iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))                            \
   {                                                                                                        \
      NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _)));        \
      return iterator(this->icont().insert_equal(this->icont().end(), *p));                                 \
   }                                                                                                        \
                                                                                                            \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
   iterator emplace_hint_equal(const_iterator hint, BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_LIST, _))  \
   {                                                                                                        \
      NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_INTERPROCESS_PP_PARAM_FORWARD, _)));        \
      return iterator(this->icont().insert_equal(hint.get(), *p));                                          \
   }                                                                                                        \
   //!
   #define BOOST_PP_LOCAL_LIMITS (1, BOOST_INTERPROCESS_MAX_CONSTRUCTOR_PARAMETERS)
   #include BOOST_PP_LOCAL_ITERATE()

   #endif   //#ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   iterator insert_unique(const_iterator hint, const value_type& v)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(hint, KeyOfValue()(v), data);
      if(!ret.second)
         return ret.first;
      return this->insert_unique_commit(v, data);
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   template<class MovableConvertible>
   iterator insert_unique
      (const_iterator hint, const detail::moved_object<MovableConvertible> &mv)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(hint, KeyOfValue()(mv.get()), data);
      if(!ret.second)
         return ret.first;
      return this->insert_unique_commit(mv, data);
   }
   #else
   template<class MovableConvertible>
   iterator insert_unique
      (const_iterator hint, MovableConvertible &&mv)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         this->insert_unique_check(hint, KeyOfValue()(mv), data);
      if(!ret.second)
         return ret.first;
      return this->insert_unique_commit(detail::forward_impl<MovableConvertible>(mv), data);
   }
   #endif

   template <class InputIterator>
   void insert_unique(InputIterator first, InputIterator last)
   {
      if(this->empty()){
         //Insert with end hint, to achieve linear
         //complexity if [first, last) is ordered
         const_iterator end(this->end());
         for( ; first != last; ++first)
            this->insert_unique(end, *first);
      }
      else{
         for( ; first != last; ++first)
            this->insert_unique(*first);
      }
   }

   iterator insert_equal(const value_type& v)
   {
      NodePtr p(AllocHolder::create_node(v));
      return iterator(this->icont().insert_equal(this->icont().end(), *p));
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   template<class MovableConvertible>
   iterator insert_equal(const detail::moved_object<MovableConvertible> &mv)
   {
      NodePtr p(AllocHolder::create_node(mv));
      return iterator(this->icont().insert_equal(this->icont().end(), *p));
   }
   #else
   template<class MovableConvertible>
   iterator insert_equal(MovableConvertible &&mv)
   {
      NodePtr p(AllocHolder::create_node(detail::forward_impl<MovableConvertible>(mv)));
      return iterator(this->icont().insert_equal(this->icont().end(), *p));
   }
   #endif

   iterator insert_equal(const_iterator hint, const value_type& v)
   {
      NodePtr p(AllocHolder::create_node(v));
      return iterator(this->icont().insert_equal(hint.get(), *p));
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   template<class MovableConvertible>
   iterator insert_equal(const_iterator hint, const detail::moved_object<MovableConvertible> &mv)
   {
      NodePtr p(AllocHolder::create_node(mv));
      return iterator(this->icont().insert_equal(hint.get(), *p));
   }
   #else
   template<class MovableConvertible>
   iterator insert_equal(const_iterator hint, MovableConvertible &&mv)
   {
      NodePtr p(AllocHolder::create_node(detail::move_impl(mv)));
      return iterator(this->icont().insert_equal(hint.get(), *p));
   }
   #endif

   template <class InputIterator>
   void insert_equal(InputIterator first, InputIterator last)
   {
      //Insert with end hint, to achieve linear
      //complexity if [first, last) is ordered
      const_iterator end(this->cend());
      for( ; first != last; ++first)
         this->insert_equal(end, *first);
   }

   iterator erase(const_iterator position)
   {  return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); }

   size_type erase(const key_type& k)
   {  return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); }

   iterator erase(const_iterator first, const_iterator last)
   {  return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }

   void clear() 
   {  AllocHolder::clear(alloc_version());  }

   // set operations:
   iterator find(const key_type& k)
   {  return iterator(this->icont().find(k, KeyNodeCompare(value_comp())));  }

   const_iterator find(const key_type& k) const
   {  return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp())));  }

   size_type count(const key_type& k) const
   {  return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); }

   iterator lower_bound(const key_type& k)
   {  return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp())));  }

   const_iterator lower_bound(const key_type& k) const
   {  return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp())));  }

   iterator upper_bound(const key_type& k)
   {  return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp())));   }

   const_iterator upper_bound(const key_type& k) const
   {  return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp())));  }

   std::pair<iterator,iterator> equal_range(const key_type& k)
   {  
      std::pair<iiterator, iiterator> ret =
         this->icont().equal_range(k, KeyNodeCompare(value_comp()));
      return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
   }

   std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
   {  
      std::pair<iiterator, iiterator> ret =
         this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp()));
      return std::pair<const_iterator,const_iterator>
         (const_iterator(ret.first), const_iterator(ret.second));
   }

   private:
   //Iterator range version
   template<class InpIterator>
   void priv_create_and_insert_nodes
      (InpIterator beg, InpIterator end, bool unique)
   {
      typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat;
      priv_create_and_insert_nodes(beg, end, unique, alloc_version(), ItCat());
   }

   template<class InpIterator>
   void priv_create_and_insert_nodes
      (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag)
   {
      if(unique){
         for (; beg != end; ++beg){
            this->insert_unique(*beg);
         }
      }
      else{
         for (; beg != end; ++beg){
            this->insert_equal(*beg);
         }
      }
   }

   template<class InpIterator>
   void priv_create_and_insert_nodes
      (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag)
   {  //Just forward to the default one
      priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag());
   }

   class insertion_functor;
   friend class insertion_functor;

   class insertion_functor
   {
      Icont &icont_;

      public:
      insertion_functor(Icont &icont)
         :  icont_(icont)
      {}

      void operator()(Node &n)
      {  this->icont_.insert_equal(this->icont_.cend(), n); }
   };


   template<class FwdIterator>
   void priv_create_and_insert_nodes
      (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag)
   {
      if(unique){
         priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag());
      }
      else{
         //Optimized allocation and construction
         this->allocate_many_and_construct
            (beg, std::distance(beg, end), insertion_functor(this->icont()));
      }
   }
};

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
{
  return x.size() == y.size() &&
         std::equal(x.begin(), x.end(), y.begin());
}

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
          const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
{
  return std::lexicographical_compare(x.begin(), x.end(), 
                                      y.begin(), y.end());
}

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
  return !(x == y);
}

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
          const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
  return y < x;
}

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
  return !(y < x);
}

template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline bool 
operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
  return !(x < y);
}


template <class Key, class Value, class KeyOfValue, 
          class KeyCompare, class A>
inline void 
swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, 
     rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
{
  x.swap(y);
}

} //namespace detail {

//!This class is movable
template <class T, class V, class K, class C, class A>
struct is_movable<detail::rbtree<T, V, K, C, A> >
{
   enum {   value = true };
};

//!This class is movable
template <class T, class VoidPointer>
struct is_movable<detail::rbtree_node<T, VoidPointer> >
{
   enum {   value = true };
};

//!This class is movable
/*
template <class A, class C>
struct is_movable<detail::rbtree_alloc<A, C> >
{
   enum {   value = true };
};
*/

//!has_trivial_destructor_after_move<> == true_type
//!specialization for optimizations
template <class K, class V, class KOV, 
          class C, class A>
struct has_trivial_destructor_after_move<detail::rbtree<K, V, KOV, C, A> >
{
   enum {   value = 
               has_trivial_destructor<A>::value &&
               has_trivial_destructor<C>::value  };
};


} //namespace interprocess  {
} //namespace boost  {

#include <boost/interprocess/detail/config_end.hpp>

#endif //BOOST_INTERPROCESS_TREE_HPP