mstl_list.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_LIST_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_LIST_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_allocator.hpp"
#include "mstl_construct.hpp"
#include "mstl_exception.hpp"
#include "algorithm/mstl_algorithm_base.hpp"
#include "algorithm/mstl_algorithm_compare.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

static const int list_sort_array = 64;

struct list_node_base
{
    list_node_base* prev;
    list_node_base* next;
};

template< typename Value >
struct list_node : public list_node_base
{
    Value data;
};

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

inline void list_iterator_increase_n( list_node_base*& node,
                                      def_size_t n )
{
    for( ; n > 0; --n )
        node = node->next;
}

inline void list_iterator_decrease_n( list_node_base*& node,
                                       def_size_t n )
{
    for( ; n > 0; --n )
        node = node->prev;
}

inline def_size_t list_size( const list_node_base* begin,
                             const list_node_base* end )
{
    def_size_t n = 0;
    while( begin != end )
    {
        begin = begin->next;
        ++n;
    }
    return n;
}

inline void list_splice( list_node_base* position,
                         list_node_base* first,
                         list_node_base* last )
{
    if( position != last )
    {
        last->prev->next = position;
        first->prev->next = last;
        position->prev->next = first;
        list_node_base* temp = position->prev;
        position->prev = last->prev;
        last->prev = first->prev;
        first->prev = temp;
    }
}

inline list_node_base* list_insert_link( list_node_base* position,
                                         list_node_base* new_node )
{
    new_node->next = position;
    new_node->prev = position->prev;
    position->prev->next = new_node;
    position->prev = new_node;
    return new_node;
}

inline list_node_base* list_erase_node( list_node_base* position )
{
    list_node_base* prev_node = position->prev;
    list_node_base* next_node = position->next;
    prev_node->next = next_node;
    next_node->prev = prev_node;
    return next_node;
}

inline void list_reverse_not_POD( list_node_base* header )
{
    if( !header || header->next->next == header )
        return;

    list_node_base* curr_node = header->next->next;
    list_node_base* next_node = curr_node->next;
    list_node_base* curr_temp;
    list_node_base* next_temp;

    while( curr_node != header )
    {
        curr_temp = curr_node;
        curr_node = curr_node->next;
        next_temp = next_node;
        next_node = next_node->next;
        list_splice( header->next, curr_temp, next_temp );
    }
}

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

template< typename T, typename Ref, typename Ptr, typename Alloc >
class list_iterator;

template< typename T, typename Allocator >
class list;

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



template< typename T, typename Ref, typename Ptr, typename Alloc >
class list_iterator
{
public:
    typedef  bidirectional_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  list_iterator<T, Ref, Ptr, Alloc>            self;
    typedef  list_iterator<T, T&, T*, Alloc>              iterator;
    typedef  list_iterator<T, const T&, const T*, Alloc>  const_iterator;

private:
    typedef  list_node_base*  base_ptr;
    typedef  list_node<T>*    node_ptr;

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

    friend class list<T, Alloc>;
    friend class list_iterator<T, Ref_t, Ptr_t, Alloc>;
    friend iterator const_iter_cast <> ( const const_iterator& );


    base_ptr node;

public:
    list_iterator() : node(NULL_POINTER)  {}
    list_iterator( base_ptr p ) : node(p)  {}
    list_iterator( node_ptr p ) : node(p)  {}
    list_iterator( const iterator& x ) : node(x.node)  {}

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

    bool operator!() const  {  return !node;  }

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

    reference operator*() const
        {  return static_cast<node_ptr>(node)->data;  }
    pointer operator->() const
        {  return &( operator*() );  }

    self& operator++()
        {  node = node->next;  return *this;  }
    self operator++(int)
        {  self old = *this;  node = node->next;  return old;  }

    self& operator--()
        {  node = node->prev;  return *this;  }
    self operator--(int)
        {  self old = *this;  node = node->prev;  return old;  }

    self& operator+=( difference_type n )
    {
        n > 0 ? list_iterator_increase_n( node, n )
              : list_iterator_decrease_n( node, n );
        return *this;
    }

    self& operator-=( difference_type n )
    {
        n > 0 ? list_iterator_decrease_n( node, n )
              : list_iterator_increase_n( node, n );
        return *this;
    }
};  //end iterator



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

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

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



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

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

template< typename T, typename Allocator = allocator< list_node<T> > >
class list
{
public:
    typedef  list<T, Allocator>  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  list_iterator<T, T&, T*, Allocator>              iterator;
    typedef  list_iterator<T, const T&, const T*, Allocator>  const_iterator;

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

protected:
    typedef  list_node_base   base_node_type;
    typedef  list_node_base*  base_ptr;
    typedef  list_node<T>     node_type;
    typedef  list_node<T>*    node_ptr;

    typedef  typename Allocator::template rebind<base_node_type>::other
             base_node_alloc;
//    typedef  allocator<base_node_type>  base_node_alloc;

    base_ptr        m_header;
    allocator_type  m_alloc;

public:
    list()  {  init_header();  }

    explicit list( size_type size )
        {  fill_init( size, value_type() );  }

    list( size_type size, const_reference value )
        {  fill_init( size, value );  }
    list( int size, const_reference value )
        {  fill_init( static_cast<size_type>(size), value );  }
    list( long size, const_reference value )
        {  fill_init( static_cast<size_type>(size), value );  }

    template< typename InputIterator >
    list( InputIterator first, InputIterator last )
    {
        init_header();
        try
        {
            insert( end(), first, last );
        }
        catch(...)
        {
            clear();
            dealloc_header();
            throw;
        }
    }

    list( const self& rhs )
    {
        init_header();
        try
        {
            insert( end(), rhs.begin(), rhs.end() );
        }
        catch(...)
        {
            clear();
            dealloc_header();
            throw;
        }
    }

    self& operator=( const self& rhs )
    {
        if( this != &rhs )
            assign( rhs.begin(), rhs.end() );
        return *this;
    }

    ~list()  {  clear();  dealloc_header();  }

    iterator begin()              {  return m_header->next;  }
    iterator end()                {  return m_header;  }
    const_iterator begin() const  {  return m_header->next;  }
    const_iterator end() const    {  return m_header;  }

    reverse_iterator rbegin()              {  return end();  }
    reverse_iterator rend()                {  return begin();  }
    const_reverse_iterator rbegin() const  {  return end();  }
    const_reverse_iterator rend() const    {  return begin();  }

    reference front()              {  return *begin();  }
    reference back()               {  return *(--end());  }
    const_reference front() const  {  return *begin();  }
    const_reference back() const   {  return *(--end());  }

    bool empty() const          {  return ( m_header->next == m_header );  }
    size_type max_size() const  {  return size_t_max;  }
    void clear()                {  erase( begin(), end() );  }

    void push_back( const_reference value )   {  insert( end(), value );  }
    void push_front( const_reference value )  {  insert( begin(), value );  }
    void pop_back()                           {  erase( --end() );  }
    void pop_front()                          {  erase( begin() );  }

    reference at( size_type index );
    const_reference at( size_type index ) const;

    reference operator[]( size_type index )
    {
        iterator result = begin();
        return *( result += index );
    }
    const_reference operator[]( size_type index ) const
    {
        const_iterator result = begin();
        return *( result += index );
    }

    size_type size() const
    {
        return list_size( m_header->next, m_header );
    }

    void swap( self& rhs )
    {
        if( this != &rhs )
        {
            data_swap( m_header, rhs.m_header );
            data_swap( m_alloc, rhs.m_alloc );
        }
    }

    void reverse()
    {
        typedef  typename type_traits<value_type>::is_POD_type  POD;
        list_reverse( POD() );
    }

    void splice( iterator position, self& rhs )
    {
        if( !rhs.empty() )
            list_splice( position.node, rhs.begin().node, rhs.end().node );
    }
    void splice( iterator position, self& rhs, iterator first, iterator last )
    {
        if( first != last )
            list_splice( position.node, first.node, last.node );
    }
    void splice( iterator position, self& rhs, iterator new_node )
    {
        if( position != new_node )
        {
            iterator temp = new_node;  ++temp;
            if( new_node != temp )
                list_splice( position.node, new_node.node, temp.node );
        }
    }

    iterator erase( iterator position );
    iterator erase( iterator first, iterator last );

    iterator insert( iterator position, const_reference value = value_type() );
    void insert( iterator position, size_type count, const_reference value );
    void insert( iterator position, int count, const_reference value )
        {  insert( position, static_cast<size_type>(count), value );  }
    void insert( iterator position, long count, const_reference value )
        {  insert( position, static_cast<size_type>(count), value );  }
    template< typename InputIterator >
    void insert( iterator position, InputIterator first, InputIterator last );

    void assign( size_type new_size, const_reference value = value_type() );
    void assign( int new_size, const_reference value = value_type() )
        {  assign( static_cast<size_type>(new_size), value );  }
    void assign( long new_size, const_reference value = value_type() )
        {  assign( static_cast<size_type>(new_size), value );  }
    template< typename InputIterator >
    void assign( InputIterator first, InputIterator last );

    void resize( size_type new_size, const_reference value = value_type() );

    void remove( const_reference value );
    void unique();
    void merge( self& rhs );
    void sort();

    template< typename Predicate >
    void remove_if( Predicate pred );

    template< typename BinaryPredicate >
    void unique( BinaryPredicate bin_pred );

    template< typename StrictWeakOrdering >
    void merge( self& rhs, StrictWeakOrdering comp );

    template< typename StrictWeakOrdering >
    void sort( StrictWeakOrdering comp );

protected:
    void init_header()
    {
        alloc_header();
        m_header->prev = m_header;
        m_header->next = m_header;
    }

    void alloc_header()
    {
        m_header = base_node_alloc().allocate( 1 );
    }

    void dealloc_header()
    {
        base_node_alloc().deallocate( m_header, 1 );
    }

    node_ptr create_node( const_reference x )
    {
        node_ptr ptr = m_alloc.allocate( 1 );