mstl_slist.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.
*/

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_SLIST_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_SLIST_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 slist_sort_array = 64;

struct slist_node_base
{
    slist_node_base*  next;
};

template< typename Value >
struct slist_node : public slist_node_base
{
    Value data;
};

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

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

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

inline slist_node_base* slist_prev( slist_node_base* begin,
                                    const slist_node_base* node )
{
    if( begin != node )
    {
        while( begin && begin->next != node )
            begin = begin->next;
    }
    return begin;
}

inline slist_node_base* slist_make_link( slist_node_base* prev_node,
                                         slist_node_base* new_node )
{
    new_node->next = prev_node->next;
    prev_node->next = new_node;
    return new_node;
}

inline slist_node_base* slist_erase_after_node( slist_node_base* position )
{
    slist_node_base* erase_node = position->next;
    slist_node_base* next_node = erase_node->next;
    position->next = next_node;
    return next_node;
}

inline void slist_splice_after( slist_node_base* position,
                                slist_node_base* before_first,
                                slist_node_base* before_last )
{
    if( position != before_first && position != before_last )
    {
        slist_node_base* first = before_first->next;
        slist_node_base* pos_after = position->next;
        before_first->next = before_last->next;
        position->next = first;
        before_last->next = pos_after;
    }
}

inline slist_node_base* slist_reverse( slist_node_base* first )
{
    slist_node_base* result = first;
    slist_node_base* next;
    first = first->next;
    result->next = NULL_POINTER;

    while( first )
    {
        next = first->next;
        first->next = result;
        result = first;
        first = next;
    }

    return result;
}

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

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

template< typename T, typename Allocator >
class slist;

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



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

private:
    typedef  slist_node_base*  base_ptr;
    typedef  slist_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 slist<T, Alloc>;
    friend class slist_iterator<T, Ref_t, Ptr_t, Alloc>;
    friend iterator const_iter_cast <> ( const const_iterator& );


    base_ptr node;

public:
    slist_iterator() : node(NULL_POINTER)  {}
    slist_iterator( base_ptr p ) : node(p)  {}
    slist_iterator( node_ptr p ) : node(p)  {}
    slist_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+=( size_type n )
        {  slist_iterator_increase_n( node, n );  return *this;  }

    self next()  {  return node->next;  }
};  //end iterator



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

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



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

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

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

protected:
    typedef  slist_node_base   base_node_type;
    typedef  slist_node_base*  base_ptr;
    typedef  slist_node<T>     node_type;
    typedef  slist_node<T>*    node_ptr;

    base_node_type  m_header;
    allocator_type  m_alloc;

public:
    slist()  {  init_header();  }

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

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

    template< typename InputIterator >
    slist( InputIterator first, InputIterator last )
    {
        init_header();
        try
        {
            insert_after( header(), first, last );
        }
        catch(...)
        {
            clear();
            throw;
        }
    }

    slist( const self& rhs )
    {
        init_header();
        try
        {
            insert_after( header(), rhs.begin(), rhs.end() );
        }
        catch(...)
        {
            clear();
            throw;
        }
    }

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

    ~slist()  {  clear();  }

    iterator begin()              {  return m_header.next;  }
    iterator end()                {  return (node_ptr)NULL_POINTER;  }
    const_iterator begin() const  {  return m_header.next;  }
    const_iterator end() const    {  return (node_ptr)NULL_POINTER;  }

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

    bool empty() const          {  return ( m_header.next == NULL_POINTER );  }
    size_type max_size() const  {  return size_t_max;  }
    void clear()                {  erase_after( header(), end() );  }

    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 );
    }

    iterator previous( iterator position )
        {  return slist_prev( &m_header, position.node );  }
    const_iterator previous( const_iterator position ) const
        {  return slist_prev( const_cast<base_node_type*>( &m_header ),
                              position.node );  }

    size_type size() const
    {
        return slist_size( m_header.next, NULL_POINTER );
    }

    void push_front( const_reference value )
    {
        slist_make_link( &m_header, create_node(value) );
    }

    void pop_front()
    {
        base_ptr x = m_header.next;
        m_header.next = x->next;
        destroy_node( static_cast<node_ptr>(x) );
    }

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

    void reverse()
    {
        if( !empty() && m_header.next->next )
            m_header.next = slist_reverse( m_header.next );
    }

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

    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 insert_after( iterator position, size_type count,
                       const_reference value );
    iterator insert_after( iterator position,
                           const_reference value = value_type() )
        {  return slist_make_link( position.node, create_node(value) );  }
    void insert_after( iterator position, int count, const_reference value )
        {  insert_after( position, static_cast<size_type>(count), value );  }
    void insert_after( iterator position, long count, const_reference value )
        {  insert_after( position, static_cast<size_type>(count), value );  }
    template< typename InputIterator >
    void insert_after( iterator position,
                       InputIterator first, InputIterator last );


    void insert( iterator position, size_type count, const_reference value )
        {  insert_after( previous(position), count, 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 );  }
    iterator insert( iterator position, const_reference value = value_type() )
        {  return insert_after( previous(position), value );  }
    template< typename InputIterator >
    void insert( iterator position, InputIterator first, InputIterator last )
        {  insert_after( previous(position), first, last );  }


    iterator erase_after( iterator position );
    iterator erase_after( iterator before_first, iterator last );


    iterator erase( iterator position )
        {  return erase_after( slist_prev(&m_header, position.node) );  }
    iterator erase( iterator first, iterator last )
        {  return erase_after( slist_prev(&m_header, first.node), last.node );  }


    void splice_after( iterator position, iterator before_first,
                       iterator before_last )
    {
        if( before_first != before_last )
            slist_splice_after( position.node, before_first.node,
                                before_last.node );
    }
    void splice_after( iterator position, iterator prev )
    {
        slist_splice_after( position.node, prev.node, prev.node->next );
    }


    void splice( iterator position, self& rhs )
    {
        if( !rhs.empty() )
            slist_splice_after( slist_prev( &m_header, position.node ),
                                &rhs.m_header,
                                slist_prev( &rhs.m_header, &rhs.m_header ) );
    }
    // [ first, last ) 必须在 rhs 范围之内
    void splice( iterator position, self& rhs, iterator first, iterator last )
    {
        if( first != last )
            slist_splice_after( slist_prev( &m_header, position.node ),
                                slist_prev( &rhs.m_header, first.node ),
                                slist_prev( first.node, last.node ) );
    }
    //new_node 必须在 rhs 范围之内
    void splice( iterator position, self& rhs, iterator new_node )
    {
        if( position != new_node )
            slist_splice_after( slist_prev( &m_header, position.node ),
                                slist_prev( &rhs.m_header, new_node.node ),
                                new_node.node );
    }


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

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

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

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

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

protected: