flat_tree.hpp

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

////////////////////////////////////////////////////////////////////////////////
//
// (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.
//
////////////////////////////////////////////////////////////////////////////////
// The Loki Library
// Copyright (c) 2001 by Andrei Alexandrescu
// This code accompanies the book:
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
// Permission to use, copy, modify, distribute and sell this software 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.
// The author or Addison-Welsey Longman make no representations about the 
//     suitability of this software for any purpose. It is provided "as is" 
//     without express or implied warranty.
///////////////////////////////////////////////////////////////////////////////
//
// Parts of this file come from AssocVector.h file from Loki library
//
////////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTERPROCESS_FLAT_TREE_HPP
#define BOOST_INTERPROCESS_FLAT_TREE_HPP

#if (defined _MSC_VER) && (_MSC_VER >= 1200)
#  pragma once
#endif

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

#include <boost/interprocess/containers/vector.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/move.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <algorithm>
#include <functional>
#include <utility>

namespace boost {

namespace interprocess {

namespace detail {

template <class Key, class Value, class KeyOfValue, 
          class Compare, class Alloc>
class flat_tree
{
   typedef boost::interprocess::vector<Value, Alloc>  vector_t;
   typedef Alloc                                      allocator_t;

   public:
   class value_compare
      : private Compare
   {
      typedef Value              first_argument_type;
      typedef Value              second_argument_type;
      typedef bool               return_type;
    public:     
      value_compare(const Compare &pred) 
         : Compare(pred)
      {}

      bool operator()(const Value& lhs, const Value& rhs) const
      { 
         KeyOfValue key_extract;
         return Compare::operator()(key_extract(lhs), key_extract(rhs)); 
      }

      const Compare &get_comp() const
         {  return *this;  }
      
      Compare &get_comp()
         {  return *this;  }
   };

 private:
   struct Data 
      //Inherit from value_compare to do EBO
      : public value_compare
   {
     public:
      Data(const Compare &comp,
           const vector_t &vect) 
         : value_compare(comp), m_vect(vect){}

      Data(const value_compare &comp,
           const vector_t &vect) 
         : value_compare(comp), m_vect(vect){}

      Data(const Compare &comp,
           const allocator_t &alloc) 
         : value_compare(comp), m_vect(alloc){}
     public:
      vector_t m_vect;
   };

   Data m_data;

   public:

   typedef typename vector_t::value_type              value_type;
   typedef typename vector_t::pointer                 pointer;
   typedef typename vector_t::const_pointer           const_pointer;
   typedef typename vector_t::reference               reference;
   typedef typename vector_t::const_reference         const_reference;
   typedef Key                                        key_type;
   typedef Compare                                    key_compare;
   typedef typename vector_t::allocator_type          allocator_type;
   typedef allocator_type                             stored_allocator_type;
   typedef typename allocator_type::size_type         size_type;
   typedef typename allocator_type::difference_type   difference_type;
   typedef typename vector_t::iterator                iterator;
   typedef typename vector_t::const_iterator          const_iterator;
   typedef std::reverse_iterator<iterator>            reverse_iterator;
   typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
   

   // allocation/deallocation
   flat_tree(const Compare& comp     = Compare(), 
             const allocator_type& a = allocator_type())
      : m_data(comp, a)
   { }

   flat_tree(const flat_tree& x) 
      :  m_data(x.m_data, x.m_data.m_vect)
   { }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   flat_tree(const detail::moved_object<flat_tree> &x)
      :  m_data(detail::move_impl(x.get().m_data))
   { }
   #else
   flat_tree(flat_tree &&x)
      :  m_data(detail::move_impl(x.m_data))
   { }
   #endif

   ~flat_tree()
   { }

   flat_tree&  operator=(const flat_tree& x)
   {  m_data = x.m_data;   return *this;  }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   flat_tree&  operator=(const detail::moved_object<flat_tree>& mx)
   {  m_data = detail::move_impl(mx.get().m_data); return *this;  }
   #else
   flat_tree&  operator=(flat_tree &&mx)
   {  m_data = detail::move_impl(mx.m_data); return *this;  }
   #endif

   public:    
   // accessors:
   Compare key_comp() const 
   { return this->m_data.get_comp(); }

   allocator_type get_allocator() const 
   { return this->m_data.m_vect.get_allocator(); }

   const stored_allocator_type &get_stored_allocator() const 
   {  return this->m_data.m_vect.get_stored_allocator(); }

   stored_allocator_type &get_stored_allocator()
   {  return this->m_data.m_vect.get_stored_allocator(); }

   iterator begin() 
   { return this->m_data.m_vect.begin(); }

   const_iterator begin() const 
   { return this->cbegin(); }

   const_iterator cbegin() const 
   { return this->m_data.m_vect.begin(); }

   iterator end() 
   { return this->m_data.m_vect.end(); }

   const_iterator end() const 
   { return this->cend(); }

   const_iterator cend() const 
   { return this->m_data.m_vect.end(); }

   reverse_iterator rbegin() 
   { return reverse_iterator(this->end()); }

   const_reverse_iterator rbegin() const 
   {  return this->crbegin();  }

   const_reverse_iterator crbegin() const 
   {  return const_reverse_iterator(this->cend());  }

   reverse_iterator rend() 
   { return reverse_iterator(this->begin()); }

   const_reverse_iterator rend() const 
   { return this->crend(); } 

   const_reverse_iterator crend() const 
   { return const_reverse_iterator(this->cbegin()); } 

   bool empty() const 
   { return this->m_data.m_vect.empty(); }

   size_type size() const 
   { return this->m_data.m_vect.size(); }

   size_type max_size() const 
   { return this->m_data.m_vect.max_size(); }

   void swap(flat_tree& other) 
   {
      value_compare& mycomp    = this->m_data;
      value_compare& othercomp = other.m_data;
      detail::do_swap(mycomp, othercomp);
      vector_t & myvect    = this->m_data.m_vect;
      vector_t & othervect = other.m_data.m_vect;
      myvect.swap(othervect);
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   void swap(const detail::moved_object<flat_tree>& other) 
   {  this->swap(other.get());   }
   #else
   void swap(flat_tree &&other) 
   {  this->swap(other);   }
   #endif

   public:
   // insert/erase
   std::pair<iterator,bool> insert_unique(const value_type& val)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, val);
      }
      return ret;
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   std::pair<iterator,bool> insert_unique(const detail::moved_object<value_type>& mval)
   {
      value_type &val = mval.get();
   #else
   std::pair<iterator,bool> insert_unique(value_type && val)
   {
   #endif
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl(val));
      }
      return ret;
   }


   iterator insert_equal(const value_type& val)
   {
      iterator i = this->upper_bound(KeyOfValue()(val));
      i = this->m_data.m_vect.insert(i, val);
      return i;
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   iterator insert_equal(const detail::moved_object<value_type>& mval)
   {
      iterator i = this->upper_bound(KeyOfValue()(mval.get()));
      i = this->m_data.m_vect.insert(i, mval);
      return i;
   }
   #else
   iterator insert_equal(value_type && mval)
   {
      iterator i = this->upper_bound(KeyOfValue()(mval));
      i = this->m_data.m_vect.insert(i, detail::move_impl(mval));
      return i;
   }
   #endif

   iterator insert_unique(const_iterator pos, const value_type& val)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, val);
      }
      return ret.first;
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   iterator insert_unique(const_iterator pos, const detail::moved_object<value_type>& mval)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, mval.get(), data);
      if(ret.second){
         ret.first = priv_insert_commit(data, mval);
      }
      return ret.first;
   }
   #else
   iterator insert_unique(const_iterator pos, value_type&&mval)
   {
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, mval, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl(mval));
      }
      return ret.first;
   }
   #endif

   iterator insert_equal(const_iterator pos, const value_type& val)
   {
      insert_commit_data data;
      priv_insert_equal_prepare(pos, val, data);
      return priv_insert_commit(data, val);
   }

   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   iterator insert_equal(const_iterator pos, const detail::moved_object<value_type>& mval)
   {
      insert_commit_data data;
      priv_insert_equal_prepare(pos, mval.get(), data);
      return priv_insert_commit(data, mval);
   }
   #else
   iterator insert_equal(const_iterator pos, value_type && mval)
   {
      insert_commit_data data;
      priv_insert_equal_prepare(pos, mval, data);
      return priv_insert_commit(data, detail::move_impl(mval));
   }
   #endif

   template <class InIt>
   void insert_unique(InIt first, InIt last)
   {
      for ( ; first != last; ++first)
         this->insert_unique(*first);
   }

   template <class InIt>
   void insert_equal(InIt first, InIt last)
   {
      typedef typename 
         std::iterator_traits<InIt>::iterator_category ItCat;
      priv_insert_equal(first, last, ItCat());
   }

   #ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   template <class... Args>
   iterator emplace_unique(Args&&... args)
   {
      value_type val(detail::forward_impl<Args>(args)...);
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         priv_insert_unique_prepare(val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl<value_type>(val));
      }
      return ret.first;
   }

   template <class... Args>
   iterator emplace_hint_unique(const_iterator hint, Args&&... args)
   {
      value_type val(detail::forward_impl<Args>(args)...);
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl<value_type>(val));
      }
      return ret.first;
   }

   template <class... Args>
   iterator emplace_equal(Args&&... args)
   {
      value_type val(detail::forward_impl<Args>(args)...);
      iterator i = this->upper_bound(KeyOfValue()(val));
      i = this->m_data.m_vect.insert(i, detail::move_impl<value_type>(val));
      return i;
   }

   template <class... Args>
   iterator emplace_hint_equal(const_iterator hint, Args&&... args)
   {
      value_type val(detail::forward_impl<Args>(args)...);
      insert_commit_data data;
      priv_insert_equal_prepare(hint, val, data);
      return priv_insert_commit(data, detail::move_impl<value_type>(val));
   }

   #else //#ifdef BOOST_INTERPROCESS_PERFECT_FORWARDING

   iterator emplace_unique()
   {
      detail::value_init<value_type> vval;
      value_type &val = vval.m_t;
      insert_commit_data data;
      std::pair<iterator,bool> ret =
         priv_insert_unique_prepare(val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl<value_type>(val));
      }
      return ret.first;
   }

   iterator emplace_hint_unique(const_iterator hint)
   {
      detail::value_init<value_type> vval;
      value_type &val = vval.m_t;
      insert_commit_data data;
      std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data);
      if(ret.second){
         ret.first = priv_insert_commit(data, detail::move_impl<value_type>(val));
      }
      return ret.first;
   }

   iterator emplace_equal()
   {
      detail::value_init<value_type> vval;
      value_type &val = vval.m_t;
      iterator i = this->upper_bound(KeyOfValue()(val));
      i = this->m_data.m_vect.insert(i, detail::move_impl<value_type>(val));
      return i;
   }

   iterator emplace_hint_equal(const_iterator hint)
   {
      detail::value_init<value_type> vval;
      value_type &val = vval.m_t;
      insert_commit_data data;