mstl_deque.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
The young Library
Copyright (c) 2005 by 杨桓

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 make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * 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.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_DEQUE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_DEQUE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_allocator.hpp"
#include "mstl_initialization.hpp"
#include "mstl_exception.hpp"
#include "algorithm/mstl_algorithm_base.hpp"
#include "algorithm/mstl_algorithm_copy.hpp"
#include "algorithm/mstl_algorithm_compare.hpp"
#include "algorithm/mstl_algorithm_fill.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

static const def_size_t init_map_size = 32;

inline def_size_t deque_buffer_size( def_size_t buf_size,
                                     def_size_t type_bytes )
{
    if( buf_size != 0 )
        return buf_size;
    else
        return ( type_bytes < 512 ? (512 / type_bytes) : 1 );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename T, typename Ref, typename Ptr, typename Alloc, def_size_t >
class deque_iterator;

template< typename T, typename Allocator, def_size_t >
class deque;

template< typename T, typename Alloc, def_size_t buf_size >
inline deque_iterator<T, T&, T*, Alloc, buf_size>
const_iter_cast( const deque_iterator<T, const T&, const T*,
                                      Alloc, buf_size>& citer );



template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
class deque_iterator
{
public:
    typedef  random_access_iterator_tag  iterator_category;
    typedef  def_size_t                  size_type;
    typedef  def_ptrdiff_t               difference_type;
    typedef  T                           value_type;
    typedef  Ref                         reference;
    typedef  Ptr                         pointer;
    typedef  T**                         map_pointer;

    typedef  deque_iterator<T, Ref, Ptr, Alloc, buf_size>
             self;

    typedef  deque_iterator<T, T&, T*, Alloc, buf_size>
             iterator;

    typedef  deque_iterator<T, const T&, const T*, Alloc, buf_size>
             const_iterator;

private:
    typedef  typename primal_type<Ref>::contrary_const_ref  Ref_t;
    typedef  typename primal_type<Ptr>::contrary_const_ptr  Ptr_t;

    friend class deque<T, Alloc, buf_size>;
    friend class deque_iterator<T, Ref_t, Ptr_t, Alloc, buf_size>;
    friend iterator const_iter_cast <> ( const const_iterator& );


    value_type*   current;
    value_type*   first;
    value_type*   last;
    value_type**  node;


    void set_node( map_pointer new_node )
    {
        node = new_node;
        first = *node;
        last = first + buffer_size();
    }

    static size_type buffer_size()
        {  return  deque_buffer_size( buf_size, sizeof(T) );  }

public:
    deque_iterator() : current(NULL_POINTER), first(NULL_POINTER),
                       last(NULL_POINTER), node(NULL_POINTER)  {}

    deque_iterator( T* curr, map_pointer mp )
    : current(curr), first(*mp), last(*mp + buffer_size()), node(mp)  {}

    deque_iterator( const iterator& x )
    : current(x.current), first(x.first), last(x.last), node(x.node)  {}

    self& operator=( def_nullptr_t n )
    {
        if( n == NULL_POINTER )
        {
            current = NULL_POINTER;
            first = NULL_POINTER;
            last = NULL_POINTER;
            node = NULL_POINTER;
        }
        return *this;
    }

    pointer operator->() const   {  return current;  }
    reference operator*() const  {  return *current;  }

    bool operator!() const  {  return ( !current && !first && !last && !node );  }

    bool operator==( const self& rhs ) const  {  return current == rhs.current;  }
    bool operator!=( const self& rhs ) const  {  return current != rhs.current;  }

    bool operator<( const self& rhs ) const
        {  return ( node == rhs.node ? current < rhs.current : node < rhs.node );  }

    self& operator++()
    {
        ++current;
        if( current == last )
        {
            set_node( node + 1 );
            current = first;
        }
        return *this;
    }

    self operator++(int)  {  self old = *this;  ++( *this );  return old;  }

    self& operator--()
    {
        if( current == first )
        {
            set_node( node - 1 );
            current = last;
        }
        --current;
        return *this;
    }

    self operator--(int)  {  self old = *this;  --( *this );  return old;  }

    self& operator-=( difference_type n )  {  return ( *this += -n );  }

    def_ptrdiff_t operator-( const self& rhs ) const
    {
        return ( def_ptrdiff_t( buffer_size() ) * ( node - rhs.node - 1 )
                 + ( current - first ) + ( rhs.last - rhs.current ) );
    }

    self& operator+=( difference_type n )
    {
        difference_type buf = difference_type( buffer_size() );
        difference_type offset = n + ( current - first );  //计算指针的偏移量

        if( offset >= 0 && offset < buf )
            current += n;
        else  //指针可能需要后退或者是跳到其他的内存块
        {
            difference_type node_offset;

            if( offset > 0 )
                node_offset = offset / buf;
            else
                node_offset = -( (-offset - 1) / buf ) - 1;

            set_node( node + node_offset );
            current = first + ( offset - node_offset * buf );
        }
        return *this;
    }
};  //end iterator



template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline deque_iterator<T, Ref, Ptr, Alloc, buf_size>
operator-( const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& lhs, def_ptrdiff_t n )
{
    deque_iterator<T, Ref, Ptr, Alloc, buf_size> temp( lhs );
    return ( temp -= n );
}

template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline deque_iterator<T, Ref, Ptr, Alloc, buf_size>
operator+( const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& lhs, def_ptrdiff_t n )
{
    deque_iterator<T, Ref, Ptr, Alloc, buf_size> temp( lhs );
    return ( temp += n );
}

template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline deque_iterator<T, Ref, Ptr, Alloc, buf_size>
operator+( def_ptrdiff_t n, const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& rhs )
{
    deque_iterator<T, Ref, Ptr, Alloc, buf_size> temp( rhs );
    return ( temp += n );
}

template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline bool operator>( const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& lhs,
                       const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& rhs )
{
    return ( rhs < lhs );
}

template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline bool operator<=( const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& lhs,
                        const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& rhs )
{
    return !( rhs < lhs );
}

template< typename T, typename Ref, typename Ptr, typename Alloc,
          def_size_t buf_size >
inline bool operator>=( const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& lhs,
                        const deque_iterator<T, Ref, Ptr, Alloc, buf_size>& rhs )
{
    return !( lhs < rhs );
}



template< typename T, typename Alloc, def_size_t buf_size >
inline deque_iterator<T, T&, T*, Alloc, buf_size>
const_iter_cast( const deque_iterator<T, const T&, const T*,
                                      Alloc, buf_size>& citer )
{
    return deque_iterator<T, T&, T*, Alloc,
                          buf_size>( citer.current, citer.node );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename T, typename Allocator = allocator<T>,
          def_size_t buf_size = 0 >
class deque
{
public:
    typedef  deque<T, Allocator, buf_size>  self;
    typedef  Allocator                      allocator_type;

    typedef  T                  value_type;
    typedef  value_type&        reference;
    typedef  const value_type&  const_reference;
    typedef  value_type*        pointer;
    typedef  const value_type*  const_pointer;
    typedef  def_size_t         size_type;
    typedef  def_ptrdiff_t      difference_type;

    typedef  deque_iterator<T, T&, T*, Allocator, buf_size>
             iterator;
    typedef  deque_iterator<T, const T&, const T*, Allocator, buf_size>
             const_iterator;

    typedef  Reverse_Iterator<iterator>        reverse_iterator;
    typedef  Reverse_Iterator<const_iterator>  const_reverse_iterator;

protected:
    typedef  pointer*        map_pointer;
    typedef  allocator_type  data_allocator;
    typedef  typename Allocator::template rebind<pointer>::other  map_allocator;
//    typedef  allocator<pointer>  map_allocator;

    static size_type buffer_size()
    {
        return deque_buffer_size( buf_size, sizeof(value_type) );
    }


    map_pointer  m_map;
    size_type    m_map_size;
    iterator     m_start, m_finish;
    map_allocator   m_map_alloc;
    data_allocator  m_data_alloc;

public:
    deque() : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        alloc_map_and_nodes( 0 );
    }

    explicit deque( size_type size )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        fill_init( size, value_type() );
    }

    deque( size_type size, const_reference value )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        fill_init( size, value );
    }

    deque( int size, const_reference value )
    : m_map(NULL_POINTER), m_map_size(0), m_start(), m_finish()
    {
        fill_init( static_cast<size_type>( size ), value );
    }