slist.hpp

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

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2004-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_slist.h file. Modified by Ion Gaztanaga 2004-2008
// 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_SLIST_HPP
#define BOOST_INTERPROCESS_SLIST_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/interprocess_fwd.hpp>
#include <boost/interprocess/detail/move.hpp>
#include <boost/interprocess/detail/utilities.hpp>
#include <boost/interprocess/detail/mpl.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/slist.hpp>


#ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING
//Preprocessor library to emulate perfect forwarding
#include <boost/interprocess/detail/preprocessor.hpp> 
#endif

#include <iterator>
#include <utility>
#include <memory>
#include <functional>
#include <algorithm>

namespace boost{  namespace interprocess{

/// @cond

namespace detail {

template<class VoidPointer>
struct slist_hook
{
   typedef typename bi::make_slist_base_hook
      <bi::void_pointer<VoidPointer>, bi::link_mode<bi::normal_link> >::type type;
};

template <class T, class VoidPointer>
struct slist_node
   :  public slist_hook<VoidPointer>::type
{
   #ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING

   slist_node()
      : m_data()
   {}

   #define BOOST_PP_LOCAL_MACRO(n)                                                           \
   template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
   slist_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>
   slist_node(Args &&...args)
      : m_data(detail::forward_impl<Args>(args)...)
   {}
   #endif//#ifndef BOOST_INTERPROCESS_PERFECT_FORWARDING

   T m_data;
};

template<class A>
struct intrusive_slist_type
{
   typedef typename A::value_type               value_type;
   typedef typename detail::pointer_to_other
      <typename A::pointer, void>::type         void_pointer;
   typedef typename detail::slist_node
         <value_type, void_pointer>             node_type;

   typedef typename bi::make_slist
      <node_type
      ,bi::base_hook<typename slist_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 {

/// @endcond

//! An slist is a singly linked list: a list where each element is linked to the next 
//! element, but not to the previous element. That is, it is a Sequence that 
//! supports forward but not backward traversal, and (amortized) constant time 
//! insertion and removal of elements. Slists, like lists, have the important 
//! property that insertion and splicing do not invalidate iterators to list elements, 
//! and that even removal invalidates only the iterators that point to the elements 
//! that are removed. The ordering of iterators may be changed (that is, 
//! slist<T>::iterator might have a different predecessor or successor after a list 
//! operation than it did before), but the iterators themselves will not be invalidated 
//! or made to point to different elements unless that invalidation or mutation is explicit.
//!
//! The main difference between slist and list is that list's iterators are bidirectional 
//! iterators, while slist's iterators are forward iterators. This means that slist is 
//! less versatile than list; frequently, however, bidirectional iterators are 
//! unnecessary. You should usually use slist unless you actually need the extra 
//! functionality of list, because singly linked lists are smaller and faster than double 
//! linked lists. 
//! 
//! Important performance note: like every other Sequence, slist defines the member 
//! functions insert and erase. Using these member functions carelessly, however, can 
//! result in disastrously slow programs. The problem is that insert's first argument is 
//! an iterator p, and that it inserts the new element(s) before p. This means that 
//! insert must find the iterator just before p; this is a constant-time operation 
//! for list, since list has bidirectional iterators, but for slist it must find that 
//! iterator by traversing the list from the beginning up to p. In other words: 
//! insert and erase are slow operations anywhere but near the beginning of the slist.
//! 
//! Slist provides the member functions insert_after and erase_after, which are constant 
//! time operations: you should always use insert_after and erase_after whenever 
//! possible. If you find that insert_after and erase_after aren't adequate for your 
//! needs, and that you often need to use insert and erase in the middle of the list, 
//! then you should probably use list instead of slist.
template <class T, class A>
class slist 
   : protected detail::node_alloc_holder
      <A, typename detail::intrusive_slist_type<A>::type>
{
   /// @cond
   typedef typename 
      detail::intrusive_slist_type<A>::type           Icont;
   typedef detail::node_alloc_holder<A, Icont>        AllocHolder;
   typedef typename AllocHolder::NodePtr              NodePtr;
   typedef list <T, A>                                ThisType;
   typedef typename AllocHolder::NodeAlloc            NodeAlloc;
   typedef typename AllocHolder::ValAlloc             ValAlloc;
   typedef typename AllocHolder::Node                 Node;
   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 equal_to_value
   {
      typedef typename AllocHolder::value_type value_type;
      const value_type &t_;

      public:
      equal_to_value(const value_type &t)
         :  t_(t)
      {}

      bool operator()(const value_type &t)const
      {  return t_ == t;   }
   };

   template<class Pred>
   struct ValueCompareToNodeCompare
      :  Pred
   {
      ValueCompareToNodeCompare(Pred pred)
         :  Pred(pred)
      {}

      bool operator()(const Node &a, const Node &b) const
      {  return static_cast<const Pred&>(*this)(a.m_data, b.m_data);  }

      bool operator()(const Node &a) const
      {  return static_cast<const Pred&>(*this)(a.m_data);  }
   };
   /// @endcond
   public:
   //! The type of object, T, stored in the list
   typedef T                                       value_type;
   //! Pointer to T
   typedef typename A::pointer                     pointer;
   //! Const pointer to T
   typedef typename A::const_pointer               const_pointer;
   //! Reference to T
   typedef typename A::reference                   reference;
   //! Const reference to T
   typedef typename A::const_reference             const_reference;
   //! An unsigned integral type
   typedef typename A::size_type                   size_type;
   //! A signed integral type
   typedef typename A::difference_type             difference_type;
   //! The allocator type
   typedef A                                       allocator_type;
   //! The stored allocator type
   typedef NodeAlloc                               stored_allocator_type;

   /// @cond
   private:
   typedef difference_type                         list_difference_type;
   typedef pointer                                 list_pointer;
   typedef const_pointer                           list_const_pointer;
   typedef reference                               list_reference;
   typedef const_reference                         list_const_reference;
   /// @endcond

   public:
   //! Const iterator used to iterate through a list. 
   class const_iterator
      /// @cond
      : public std::iterator<std::forward_iterator_tag, 
                                 value_type,         list_difference_type, 
                                 list_const_pointer, list_const_reference>
   {

      protected:
      typename Icont::iterator m_it;
      explicit const_iterator(typename Icont::iterator it)  : m_it(it){}
      void prot_incr(){ ++m_it; }

      private:
      typename Icont::iterator get()
      {  return this->m_it;   }

      public:
      friend class slist<T, A>;
      typedef list_difference_type        difference_type;

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

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

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

      //Increment / Decrement
      const_iterator& operator++()       
      { prot_incr();  return *this; }

      const_iterator operator++(int)      
      { typename Icont::iterator tmp = m_it; ++*this; return const_iterator(tmp);  }

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

      bool operator!=   (const const_iterator& r)  const
      {  return m_it != r.m_it;  }
   }
      /// @endcond
   ;

   //! Iterator used to iterate through a list
   class iterator
      /// @cond
   : public const_iterator
   {

      private:
      explicit iterator(typename Icont::iterator it)
         :  const_iterator(it)
      {}
   
      typename Icont::iterator get()
      {  return this->m_it;   }

      public:
      friend class slist<T, A>;
      typedef list_pointer       pointer;
      typedef list_reference     reference;

      //Constructors
      iterator(){}

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

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

      iterator operator++(int)
         { typename Icont::iterator tmp = this->m_it; ++*this; return iterator(tmp); }
   }
      /// @endcond
   ;

   public:
   //! <b>Effects</b>: Constructs a list taking the allocator as parameter.
   //! 
   //! <b>Throws</b>: If allocator_type's copy constructor throws.
   //! 
   //! <b>Complexity</b>: Constant.
   explicit slist(const allocator_type& a = allocator_type())
      :  AllocHolder(a)
   {}

//   explicit slist(size_type n)
//      :  AllocHolder(detail::move_impl(allocator_type()))
//   { this->resize(n); }

   //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
   //!   and inserts n copies of value.
   //!
   //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
   //!   throws or T's default or copy constructor throws.
   //! 
   //! <b>Complexity</b>: Linear to n.
   explicit slist(size_type n, const value_type& x = value_type(),
                  const allocator_type& a =  allocator_type())
      :  AllocHolder(a)
   { this->priv_create_and_insert_nodes(this->before_begin(), n, x); }

   //! <b>Effects</b>: Constructs a list that will use a copy of allocator a
   //!   and inserts a copy of the range [first, last) in the list.
   //!
   //! <b>Throws</b>: If allocator_type's default constructor or copy constructor
   //!   throws or T's constructor taking an dereferenced InIt throws.
   //!
   //! <b>Complexity</b>: Linear to the range [first, last).
   template <class InpIt>
   slist(InpIt first, InpIt last,
         const allocator_type& a =  allocator_type()) 
      : AllocHolder(a)
   { this->insert_after(this->before_begin(), first, last); }

   //! <b>Effects</b>: Copy constructs a list.
   //!
   //! <b>Postcondition</b>: x == *this.
   //! 
   //! <b>Throws</b>: If allocator_type's default constructor or copy constructor throws.
   //! 
   //! <b>Complexity</b>: Linear to the elements x contains.
   slist(const slist& x) 
      : AllocHolder(x)
   { this->insert_after(this->before_begin(), x.begin(), x.end()); }

   //! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
   //!
   //! <b>Throws</b>: If allocator_type's default constructor throws.
   //! 
   //! <b>Complexity</b>: Constant.
   #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE
   slist(const detail::moved_object<slist> &x)
      : AllocHolder(detail::move_impl((AllocHolder&)x.get()))
   {}
   #else
   slist(slist &&x)
      : AllocHolder(detail::move_impl((AllocHolder&)x))
   {}
   #endif

   //! <b>Effects</b>: Makes *this contain the same elements as x.
   //!
   //! <b>Postcondition</b>: this->size() == x.size(). *this contains a copy 
   //! of each of x's elements.