deque.hpp

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

/*
 *
 * 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.
 *
 */
//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2005-2006. 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_deque.h and stl_uninitialized.h files. 
// 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.
//
///////////////////////////////////////////////////////////////////////////////

#ifndef BOOST_INTERPROCESS_DEQUE_HPP
#define BOOST_INTERPROCESS_DEQUE_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/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/detail/mpl.hpp>
#include <boost/interprocess/interprocess_fwd.hpp>
#include <cstddef>
#include <iterator>
#include <cassert>
#include <memory>
#include <algorithm>
#include <stdexcept>
#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/move_iterator.hpp>
#include <boost/interprocess/detail/move.hpp>
#include <boost/interprocess/detail/advanced_insert_int.hpp>

namespace boost {
namespace interprocess {

/// @cond
template <class T, class Alloc>
class deque;

template <class T, class A>
struct deque_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;

};

// Note: this function is simply a kludge to work around several compilers'
//  bugs in handling constant expressions.
inline std::size_t deque_buf_size(std::size_t size) 
   {  return size < 512 ? std::size_t(512 / size) : std::size_t(1);  }

// Deque base class.  It has two purposes.  First, its constructor
//  and destructor allocate (but don't initialize) storage.  This makes
//  exception safety easier.
template <class T, class Alloc>
class deque_base
{
   public:
   typedef typename Alloc::value_type              val_alloc_val;
   typedef typename Alloc::pointer                 val_alloc_ptr;
   typedef typename Alloc::const_pointer           val_alloc_cptr;
   typedef typename Alloc::reference               val_alloc_ref;
   typedef typename Alloc::const_reference         val_alloc_cref;
   typedef typename Alloc::value_type              val_alloc_diff;
   typedef typename Alloc::template rebind
      <typename Alloc::pointer>::other             ptr_alloc_t;
   typedef typename ptr_alloc_t::value_type        ptr_alloc_val;
   typedef typename ptr_alloc_t::pointer           ptr_alloc_ptr;
   typedef typename ptr_alloc_t::const_pointer     ptr_alloc_cptr;
   typedef typename ptr_alloc_t::reference         ptr_alloc_ref;
   typedef typename ptr_alloc_t::const_reference   ptr_alloc_cref;
   typedef typename Alloc::template
      rebind<T>::other                             allocator_type;
   typedef allocator_type                          stored_allocator_type;

   protected:

   typedef deque_value_traits<T, Alloc>            traits_t;
   typedef typename Alloc::template
      rebind<typename Alloc::pointer>::other map_allocator_type;

   static std::size_t s_buffer_size() { return deque_buf_size(sizeof(T)); }

   val_alloc_ptr priv_allocate_node() 
      {  return this->alloc().allocate(s_buffer_size());  }

   void priv_deallocate_node(val_alloc_ptr p) 
      {  this->alloc().deallocate(p, s_buffer_size());  }

   ptr_alloc_ptr priv_allocate_map(std::size_t n) 
      { return this->ptr_alloc().allocate(n); }

   void priv_deallocate_map(ptr_alloc_ptr p, std::size_t n) 
      { this->ptr_alloc().deallocate(p, n); }

 public:
   // Class invariants:
   //  For any nonsingular iterator i:
   //    i.node is the address of an element in the map array.  The
   //      contents of i.node is a pointer to the beginning of a node.
   //    i.first == //(i.node) 
   //    i.last  == i.first + node_size
   //    i.cur is a pointer in the range [i.first, i.last).  NOTE:
   //      the implication of this is that i.cur is always a dereferenceable
   //      pointer, even if i is a past-the-end iterator.
   //  Start and Finish are always nonsingular iterators.  NOTE: this means
   //    that an empty deque must have one node, and that a deque
   //    with N elements, where N is the buffer size, must have two nodes.
   //  For every node other than start.node and finish.node, every element
   //    in the node is an initialized object.  If start.node == finish.node,
   //    then [start.cur, finish.cur) are initialized objects, and
   //    the elements outside that range are uninitialized storage.  Otherwise,
   //    [start.cur, start.last) and [finish.first, finish.cur) are initialized
   //    objects, and [start.first, start.cur) and [finish.cur, finish.last)
   //    are uninitialized storage.
   //  [map, map + map_size) is a valid, non-empty range.  
   //  [start.node, finish.node] is a valid range contained within 
   //    [map, map + map_size).  
   //  A pointer in the range [map, map + map_size) points to an allocated node
   //    if and only if the pointer is in the range [start.node, finish.node].
   class const_iterator 
      : public std::iterator<std::random_access_iterator_tag, 
                              val_alloc_val,  val_alloc_diff, 
                              val_alloc_cptr, val_alloc_cref>
   {
      public:
      static std::size_t s_buffer_size() { return deque_base<T, Alloc>::s_buffer_size(); }

      typedef std::random_access_iterator_tag   iterator_category;
      typedef val_alloc_val                     value_type;
      typedef val_alloc_cptr                    pointer;
      typedef val_alloc_cref                    reference;
      typedef std::size_t                       size_type;
      typedef std::ptrdiff_t                    difference_type;

      typedef ptr_alloc_ptr                     index_pointer;
      typedef const_iterator                    self_t;

      friend class deque<T, Alloc>;
      friend class deque_base<T, Alloc>;

      protected: 
      val_alloc_ptr  m_cur;
      val_alloc_ptr  m_first;
      val_alloc_ptr  m_last;
      index_pointer  m_node;

      public: 
      const_iterator(val_alloc_ptr x, index_pointer y) 
         : m_cur(x), m_first(*y),
           m_last(*y + s_buffer_size()), m_node(y) {}

      const_iterator() : m_cur(0), m_first(0), m_last(0), m_node(0) {}

      const_iterator(const const_iterator& x)
         : m_cur(x.m_cur),   m_first(x.m_first), 
           m_last(x.m_last), m_node(x.m_node) {}

      reference operator*() const 
         { return *this->m_cur; }

      pointer operator->() const 
         { return this->m_cur; }

      difference_type operator-(const self_t& x) const 
      {
         return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
            (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
      }

      self_t& operator++() 
      {
         ++this->m_cur;
         if (this->m_cur == this->m_last) {
            this->priv_set_node(this->m_node + 1);
            this->m_cur = this->m_first;
         }
         return *this; 
      }

      self_t operator++(int)  
      {
         self_t tmp = *this;
         ++*this;
         return tmp;
      }

      self_t& operator--() 
      {
         if (this->m_cur == this->m_first) {
            this->priv_set_node(this->m_node - 1);
            this->m_cur = this->m_last;
         }
         --this->m_cur;
         return *this;
      }

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

      self_t& operator+=(difference_type n)
      {
         difference_type offset = n + (this->m_cur - this->m_first);
         if (offset >= 0 && offset < difference_type(this->s_buffer_size()))
            this->m_cur += n;
         else {
            difference_type node_offset =
            offset > 0 ? offset / difference_type(this->s_buffer_size())
                        : -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
            this->priv_set_node(this->m_node + node_offset);
            this->m_cur = this->m_first + 
            (offset - node_offset * difference_type(this->s_buffer_size()));
         }
         return *this;
      }

      self_t operator+(difference_type n) const
         {  self_t tmp = *this; return tmp += n;  }

      self_t& operator-=(difference_type n) 
         { return *this += -n; }
       
      self_t operator-(difference_type n) const 
         {  self_t tmp = *this; return tmp -= n;  }

      reference operator[](difference_type n) const 
         { return *(*this + n); }

      bool operator==(const self_t& x) const 
         { return this->m_cur == x.m_cur; }

      bool operator!=(const self_t& x) const 
         { return !(*this == x); }

      bool operator<(const self_t& x) const 
      {
         return (this->m_node == x.m_node) ? 
            (this->m_cur < x.m_cur) : (this->m_node < x.m_node);
      }

      bool operator>(const self_t& x) const  
         { return x < *this; }

      bool operator<=(const self_t& x) const 
         { return !(x < *this); }

      bool operator>=(const self_t& x) const 
         { return !(*this < x); }

      void priv_set_node(index_pointer new_node) 
      {
         this->m_node = new_node;
         this->m_first = *new_node;
         this->m_last = this->m_first + difference_type(this->s_buffer_size());
      }

      friend const_iterator operator+(std::ptrdiff_t n, const const_iterator& x)
         {  return x + n;  }
   };

   //Deque iterator
   class iterator : public const_iterator
   {
      public:
      typedef std::random_access_iterator_tag   iterator_category;
      typedef val_alloc_val                     value_type;
      typedef val_alloc_ptr                     pointer;
      typedef val_alloc_ref                     reference;
      typedef std::size_t                       size_type;
      typedef std::ptrdiff_t                    difference_type;
      typedef ptr_alloc_ptr                     index_pointer;
      typedef const_iterator                    self_t;

      friend class deque<T, Alloc>;
      friend class deque_base<T, Alloc>;

      private:
      explicit iterator(const const_iterator& x) : const_iterator(x){}

      public:
      //Constructors
      iterator(val_alloc_ptr x, index_pointer y) : const_iterator(x, y){}
      iterator() : const_iterator(){}
      //iterator(const const_iterator &cit) : const_iterator(cit){}
      iterator(const iterator& x) : const_iterator(x){}

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

      reference operator[](difference_type n) const { return *(*this + n); }

      //Increment / Decrement
      iterator& operator++()  
         { this->const_iterator::operator++(); return *this;  }

      iterator operator++(int)
         { iterator tmp = *this; ++*this; return tmp; }
      
      iterator& operator--()
         {  this->const_iterator::operator--(); return *this;  }

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

      // Arithmetic
      iterator& operator+=(difference_type off)
         {  this->const_iterator::operator+=(off); return *this;  }

      iterator operator+(difference_type off) const
         {  return iterator(this->const_iterator::operator+(off));  }

      friend iterator operator+(difference_type off, const iterator& right)
         {  return iterator(off+static_cast<const const_iterator &>(right)); }

      iterator& operator-=(difference_type off)
         {  this->const_iterator::operator-=(off); return *this;   }

      iterator operator-(difference_type off) const
         {  return iterator(this->const_iterator::operator-(off));  }

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