ycpp_slist.hpp

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

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

 * 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_YOUNG_LIBRARY_SLIST_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_SLIST_HEADER_FILE__
//------------------------------------------------------------------------------
#include <memory>
#include <iterator>
#include <stdexcept>
#include "../youngc/yc_sglnklst.h"
#include "../youngc/yc_memory.h"
#include "ycpp_memory.hpp"
#include "ycpp_function.hpp"
#include "ycpp_algorithm.hpp"
//------------------------------------------------------------------------------
namespace youngcpp {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T, typename A >
class slist;

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

template< typename T, typename A >
struct move_traits< slist<T, A> >
{
    typedef  true_type  move_ability;
};



template< typename T, typename Ref, typename Ptr, typename Alloc >
class slist_iterator
{
private:
    typedef  typename primal_traits<Ref>::contrary_const_ref  ccRef;
    typedef  typename primal_traits<Ptr>::contrary_const_ptr  ccPtr;

    friend class slist<T, Alloc>;
    friend class slist_iterator<T, ccRef, ccPtr, Alloc>;

    youngc::sglnklst_iterator itr;

public:
    typedef  std::forward_iterator_tag  iterator_category;
    typedef  size_t                     size_type;
    typedef  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;

    slist_iterator() : itr(0)  {}
    slist_iterator( const iterator& src ) : itr(src.itr)  {}
    slist_iterator( const youngc::sglnklst_iterator& src ) : itr(src)  {}

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

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

    self& operator++()
        {  sglnklst_itr_inc(&itr);  return *this;  }
    self operator++(int)
        {  self old = *this;  sglnklst_itr_inc(&itr);  return old;  }
    self& operator+=( size_type n )
        {  sglnklst_itr_inc_n(&itr, n);  return *this;  }
};

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, ptrdiff_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+( ptrdiff_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 Allocator = std::allocator<T> >
class slist
{
public:
    typedef  slist<T, Allocator>    self;
    typedef  Allocator              allocator_type;
    typedef  size_t                 size_type;
    typedef  ptrdiff_t              difference_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  slist_iterator<T, T&, T*, Allocator>              iterator;
    typedef  slist_iterator<T, const T&, const T*, Allocator>  const_iterator;

    typedef  std::reverse_iterator<iterator>        reverse_iterator;
    typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;

    slist()  {  init();  }

    explicit slist( size_type n, const T& value = T() )
        {  init_fill( n, value );  }
    explicit slist( int n, const T& value = T() )
        {  init_fill( static_cast<size_type>(n), value );  }
    explicit slist( long n, const T& value = T() )
        {  init_fill( static_cast<size_type>(n), value );  }

    template< typename InputIterator >
    slist( InputIterator first, InputIterator last )
    {
        init();
        youngc::sglnklst_iterator itr = sglnklst_header( &m_sli );
        for( ; first != last; ++first )
        {
            if( !sglnklst_insert_node( &m_sli, itr, &(*first) ) )
            {
                sglnklst_destroy( &m_sli );
                throw std::bad_alloc();
            }
            sglnklst_itr_inc( &itr );
        }
    }

    slist( const self& rhs )
    {
        if( sglnklst_init_copy( &m_sli, &(rhs.m_sli) ) == 0 )
            throw std::bad_alloc();
    }

    self& operator=( const self& rhs )
    {
        if( sglnklst_assign_copy( &m_sli, &(rhs.m_sli) ) == 0 )
            throw std::bad_alloc();
        return *this;
    }

    ~slist()  {  sglnklst_destroy( &m_sli );  }

    static void init_move( void* uninit_dst, void* src )
    {
        sglnklst_init_move( &( static_cast<self*>(uninit_dst)->m_sli ),
                            &( static_cast<self*>(src)->m_sli ) );
    }

    static void assign_move( void* dst, void* src )
    {
        sglnklst_assign_move( &( static_cast<self*>(dst)->m_sli ),
                              &( static_cast<self*>(src)->m_sli ) );
    }

    iterator previous( iterator position )
        {  return sglnklst_itr_prev( sglnklst_header(&m_sli), position.itr );  }
    const_iterator previous( const_iterator position ) const
        {  return sglnklst_itr_prev( sglnklst_header(&m_sli), position.itr );  }

    iterator header()
        {  return iterator( sglnklst_header(&m_sli) );  }
    iterator begin()
        {  return iterator( sglnklst_begin(&m_sli) );  }
    iterator end()
        {  return iterator( 0 );  }
    const_iterator header() const
       {  return const_iterator( sglnklst_header(&m_sli) );  }
    const_iterator begin() const
        {  return const_iterator( sglnklst_begin(&m_sli) );  }
    const_iterator end() const
        {  return const_iterator( 0 );  }

    reference back()
        {  return *((pointer)sglnklst_back(&m_sli));  }
    const_reference back() const
        {  return *((const_pointer)sglnklst_back(&m_sli));  }
    reference front()
        {  return *((pointer)sglnklst_front(&m_sli));  }
    const_reference front() const
        {  return *((const_pointer)sglnklst_front(&m_sli));  }

    void reverse()              {  sglnklst_reverse(&m_sli);  }
    bool empty() const          {  return sglnklst_empty(&m_sli);  }
    size_type size() const      {  return sglnklst_size(&m_sli);  }
    size_type max_size() const  {  return youngc::sglnklst_max_size();  }

    void pop_back()   {  sglnklst_pop_back(&m_sli);  }
    void pop_front()  {  sglnklst_pop_front(&m_sli);  }

    void push_back( const T& value )
    {
        if( !sglnklst_push_back(&m_sli, &value) )
            throw std::bad_alloc();
    }

    void push_front( const T& value )
    {
        if( !sglnklst_push_front(&m_sli, &value) )
            throw std::bad_alloc();
    }

    void clear()
    {
        sglnklst_erase_after_range( &m_sli, sglnklst_header(&m_sli), 0 );
    }

    void swap( self& rhs )
    {
        if( &rhs != this )
            std::swap( m_sli, rhs.m_sli );
    }

    reference operator[]( size_type index )
        {  return *((pointer)sglnklst_index(&m_sli, index));  }
    const_reference operator[]( size_type index ) const
        {  return *((const_pointer)sglnklst_index(&m_sli, index));  }