vector.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (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_vector.h file. Modified by Ion Gaztanaga.
// 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_VECTOR_HPP
#define BOOST_INTERPROCESS_VECTOR_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 <cstddef>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <utility>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <boost/type_traits/has_trivial_copy.hpp>
#include <boost/type_traits/has_trivial_assign.hpp>
#include <boost/type_traits/has_nothrow_copy.hpp>
#include <boost/type_traits/has_nothrow_assign.hpp>
#include <boost/interprocess/detail/version_type.hpp>
#include <boost/interprocess/allocators/allocation_type.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/iterators.hpp>
#include <boost/interprocess/detail/algorithms.hpp>
#include <boost/interprocess/detail/min_max.hpp>
#include <boost/interprocess/interprocess_fwd.hpp>
#include <boost/interprocess/detail/move_iterator.hpp>
#include <boost/interprocess/detail/move.hpp>
#include <boost/interprocess/detail/mpl.hpp>
#include <boost/interprocess/detail/advanced_insert_int.hpp>

namespace boost {
namespace interprocess {

/// @cond

namespace detail {

//! Const vector_iterator used to iterate through a vector. 
template <class Pointer>
class vector_const_iterator
   : public std::iterator<std::random_access_iterator_tag
                          ,const typename std::iterator_traits<Pointer>::value_type
                          ,typename std::iterator_traits<Pointer>::difference_type
                          ,typename pointer_to_other
                              <Pointer
                              ,const typename std::iterator_traits<Pointer>::value_type
                              >::type
                          ,const typename std::iterator_traits<Pointer>::value_type &>
{
   public:
   typedef const typename std::iterator_traits<Pointer>::value_type  value_type;
   typedef typename std::iterator_traits<Pointer>::difference_type   difference_type;
   typedef typename pointer_to_other<Pointer, value_type>::type      pointer;
   typedef value_type&                                               reference;

   /// @cond
   protected:
   Pointer m_ptr;

   public:
   Pointer get_ptr() const    {  return   m_ptr;  }
   explicit vector_const_iterator(Pointer ptr)  : m_ptr(ptr){}
   /// @endcond

   public:

   //Constructors
   vector_const_iterator() : m_ptr(0){}

   //Pointer like operators
   reference operator*()   const  
   {  return *m_ptr;  }

   const value_type * operator->()  const  
   {  return  detail::get_pointer(m_ptr);  }

   reference operator[](difference_type off) const
   {  return m_ptr[off];   }

   //Increment / Decrement
   vector_const_iterator& operator++()       
   { ++m_ptr;  return *this; }

   vector_const_iterator operator++(int)      
   {  Pointer tmp = m_ptr; ++*this; return vector_const_iterator(tmp);  }

   vector_const_iterator& operator--()
   {  --m_ptr; return *this;  }

   vector_const_iterator operator--(int)
   {  Pointer tmp = m_ptr; --*this; return vector_const_iterator(tmp); }

   //Arithmetic
   vector_const_iterator& operator+=(difference_type off)
   {  m_ptr += off; return *this;   }

   vector_const_iterator operator+(difference_type off) const
   {  return vector_const_iterator(m_ptr+off);  }

   friend vector_const_iterator operator+(difference_type off, const vector_const_iterator& right)
   {  return vector_const_iterator(off + right.m_ptr); }

   vector_const_iterator& operator-=(difference_type off)
   {  m_ptr -= off; return *this;   }

   vector_const_iterator operator-(difference_type off) const
   {  return vector_const_iterator(m_ptr-off);  }

   difference_type operator-(const vector_const_iterator& right) const
   {  return m_ptr - right.m_ptr;   }

   //Comparison operators
   bool operator==   (const vector_const_iterator& r)  const
   {  return m_ptr == r.m_ptr;  }

   bool operator!=   (const vector_const_iterator& r)  const
   {  return m_ptr != r.m_ptr;  }

   bool operator<    (const vector_const_iterator& r)  const
   {  return m_ptr < r.m_ptr;  }

   bool operator<=   (const vector_const_iterator& r)  const
   {  return m_ptr <= r.m_ptr;  }

   bool operator>    (const vector_const_iterator& r)  const
   {  return m_ptr > r.m_ptr;  }

   bool operator>=   (const vector_const_iterator& r)  const
   {  return m_ptr >= r.m_ptr;  }
};

//! Iterator used to iterate through a vector
template <class Pointer>
class vector_iterator
   :  public vector_const_iterator<Pointer>
{
   public:
   explicit vector_iterator(Pointer ptr)
      : vector_const_iterator<Pointer>(ptr)
   {}

   public:
   typedef typename std::iterator_traits<Pointer>::value_type        value_type;
   typedef typename vector_const_iterator<Pointer>::difference_type  difference_type;
   typedef Pointer                                                   pointer;
   typedef value_type&                                               reference;

   //Constructors
   vector_iterator()
   {}

   //Pointer like operators
   reference operator*()  const  
   {  return *this->m_ptr;  }

   value_type* operator->() const  
   {  return  detail::get_pointer(this->m_ptr);  }

   reference operator[](difference_type off) const 
   {  return this->m_ptr[off];   }

   //Increment / Decrement
   vector_iterator& operator++()  
   {  ++this->m_ptr; return *this;  }

   vector_iterator operator++(int)
   {  pointer tmp = this->m_ptr; ++*this; return vector_iterator(tmp);  }
   
   vector_iterator& operator--()
   {  --this->m_ptr; return *this;  }

   vector_iterator operator--(int)
   {  vector_iterator tmp = *this; --*this; return vector_iterator(tmp); }

   // Arithmetic
   vector_iterator& operator+=(difference_type off)
   {  this->m_ptr += off;  return *this;  }

   vector_iterator operator+(difference_type off) const
   {  return vector_iterator(this->m_ptr+off);  }

   friend vector_iterator operator+(difference_type off, const vector_iterator& right)
   {  return vector_iterator(off + right.m_ptr); }

   vector_iterator& operator-=(difference_type off)
   {  this->m_ptr -= off; return *this;   }

   vector_iterator operator-(difference_type off) const
   {  return vector_iterator(this->m_ptr-off);  }

   difference_type operator-(const vector_const_iterator<Pointer>& right) const
   {  return static_cast<const vector_const_iterator<Pointer>&>(*this) - right;   }
};

template <class T, class A>
struct vector_value_traits
{
   typedef T value_type;
   typedef A allocator_type;
   static const bool trivial_dctr = boost::has_trivial_destructor<value_type>::value;
   static const bool trivial_dctr_after_move = 
      has_trivial_destructor_after_move<value_type>::value || trivial_dctr;
   static const bool trivial_copy = has_trivial_copy<value_type>::value;
   static const bool nothrow_copy = has_nothrow_copy<value_type>::value;
   static const bool trivial_assign = has_trivial_assign<value_type>::value;
   static const bool nothrow_assign = has_nothrow_assign<value_type>::value;

   //This is the anti-exception array destructor
   //to deallocate values already constructed
   typedef typename detail::if_c
      <trivial_dctr
      ,detail::null_scoped_destructor_n<allocator_type>
      ,detail::scoped_destructor_n<allocator_type>
      >::type   OldArrayDestructor;
   //This is the anti-exception array destructor
   //to destroy objects created with copy construction
   typedef typename detail::if_c
      <nothrow_copy
      ,detail::null_scoped_destructor_n<allocator_type>
      ,detail::scoped_destructor_n<allocator_type>
      >::type   UCopiedArrayDestructor;
   //This is the anti-exception array deallocator
   typedef typename detail::if_c
      <nothrow_copy
      ,detail::null_scoped_array_deallocator<allocator_type>
      ,detail::scoped_array_deallocator<allocator_type>
      >::type   UCopiedArrayDeallocator;

   //This is the optimized move iterator for copy constructors
   //so that std::copy and similar can use memcpy
   typedef typename detail::if_c
      <trivial_copy 
      #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
      || !is_movable<value_type>::value
      #endif
      ,const T*
      ,detail::move_iterator<T*>
      >::type   copy_move_it;

   //This is the optimized move iterator for assignments
   //so that std::uninitialized_copy and similar can use memcpy
   typedef typename detail::if_c
      <trivial_assign
      #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
      || !is_movable<value_type>::value
      #endif
      ,const T*
      ,detail::move_iterator<T*>
      >::type   assign_move_it;
};

//!This struct deallocates and allocated memory
template <class A>
struct vector_alloc_holder 
{
   typedef typename A::pointer      pointer;
   typedef typename A::size_type    size_type;
   typedef typename A::value_type   value_type;
   typedef vector_value_traits<value_type, A> value_traits;

   //Constructor, does not throw
   vector_alloc_holder(const A &a)
      : members_(a)
   {}

   //Constructor, does not throw
   vector_alloc_holder(const vector_alloc_holder<A> &h)
      : members_(h.alloc())
   {}

   //Destructor
   ~vector_alloc_holder()
   {  this->prot_deallocate(); }

   typedef detail::integral_constant<unsigned, 1>      allocator_v1;
   typedef detail::integral_constant<unsigned, 2>      allocator_v2;
   typedef detail::integral_constant<unsigned,
      boost::interprocess::detail::version<A>::value> alloc_version;
   std::pair<pointer, bool>
      allocation_command(allocation_type command,
                         size_type limit_size, 
                         size_type preferred_size,
                         size_type &received_size, const pointer &reuse = 0)
   {
      return allocation_command(command, limit_size, preferred_size,
                               received_size, reuse, alloc_version());
   }

   std::pair<pointer, bool>
      allocation_command(allocation_type command,
                         size_type limit_size, 
                         size_type preferred_size,
                         size_type &received_size,
                         const pointer &reuse,
                         allocator_v1)
   {
      (void)limit_size;
      (void)reuse;
      if(!(command & allocate_new))