list

realview22.rar

// -*- C++ -*-
/***************************************************************************
 *
 * list - list declarations for the Standard Library
 *
 * $Id: list,v 1.3.4.1 2004/11/29 15:08:13 achapman Exp $
 *
 ***************************************************************************
 *
 * 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) 1994-2001 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. pursuant to a written license agreement and may be used, copied,
 * transmitted, and stored only in accordance with the terms of such
 * license and with the inclusion of the above copyright notice.  This
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  Use, duplication, or disclosure by the
 * Government is subject to restrictions as set forth in subparagraph (c)
 * (1) (ii) of The Rights in Technical Data and Computer Software clause
 * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/

#ifndef _RWSTD_LIST_INCLUDED
#define _RWSTD_LIST_INCLUDED

#include <limits>
#include <memory>

#include <rw/_algobase.h>
#include <rw/_iterator.h>
#include <rw/_defs.h>
#include <rw/_error.h>


_RWSTD_NAMESPACE_BEGIN (std)

template <class _TypeT>
struct __rw_list_node
{
    __rw_list_node*  _C_next;   // pointer to next node
    __rw_list_node*  _C_prev;   // pointer to previous node
    _TypeT           _C_data;   // client data
}; 



template <class _TypeT, class _DiffT, class _Pointer, class _Reference>
class __rw_list_iter
    : public iterator <bidirectional_iterator_tag,
                       _TypeT, _DiffT, _Pointer, _Reference>
{
    typedef iterator <bidirectional_iterator_tag,
                     _TypeT, _DiffT, _Pointer, _Reference>
              _C_iter_base;

public:

    typedef _TYPENAME _C_iter_base::value_type      value_type;
    typedef _TYPENAME _C_iter_base::difference_type difference_type;
    typedef _TYPENAME _C_iter_base::pointer         pointer;
    typedef _TYPENAME _C_iter_base::reference       reference;

    // const_pointer and const_reference must be explicity typedef'ed to
    // const value_type* and const value_type& since we don't know if
    // _Pointer and _Reference are const types (they aren't if this isn't
    // a const iterator)
    typedef const value_type*                       const_pointer; 
    typedef const value_type&                       const_reference; 

    typedef bidirectional_iterator_tag              iterator_category;

    typedef __rw_list_iter <value_type, difference_type,
                            value_type*, value_type&>      _C_mutable_iter;

    typedef  __rw_list_node<value_type>*                   _C_link_type;
    
    __rw_list_iter () { }

    __rw_list_iter (const _C_link_type& __rhs)
        : _C_node (__rhs) { }

    // no copy ctor other than the one below defined; will use
    // a compiler generated one if __rw_list_iter != _C_mutable_iter
    __rw_list_iter (const _C_mutable_iter &__rhs)
        : _C_node (__rhs._C_node) { }

    __rw_list_iter& operator++ () {
        _C_node = (_C_link_type)((*_C_node)._C_next); 
        return *this;
    }
    
    __rw_list_iter& operator-- () {
        _C_node = (_C_link_type)((*_C_node)._C_prev);
        return *this;
    }
    
    __rw_list_iter operator++ (int) {
        __rw_list_iter __tmp = *this;
        return ++*this, __tmp;
    }
    
    __rw_list_iter operator-- (int) {
        __rw_list_iter __tmp = *this;
        return --*this, __tmp;
    }
    
    reference operator* () const {
        return (*_C_node)._C_data;
    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
    
    difference_type operator- (const __rw_list_iter&) const {
        return 0;
    }

    bool operator== (const __rw_list_iter& __iter) const {
        return _C_node == __iter._C_node;
    }

    bool operator!= (const __rw_list_iter& __iter) const {
        return !(*this == __iter);
    }

// private:

    _C_link_type _C_node;
};


#define _ITER_NODE(it)   (_ITER_BASE (it)._C_node)

        
template <class _TypeT, class _DiffT, class _Ptr1, class _Ref1,
                                      class _Ptr2, class _Ref2>
inline bool
operator== (const __rw_list_iter<_TypeT, _DiffT, _Ptr1, _Ref1> &__x,
            const __rw_list_iter<_TypeT, _DiffT, _Ptr2, _Ref2> &__y)

{
    return __x._C_node == __y._C_node;
}


template <class _TypeT, class _DiffT, class _Ptr1, class _Ref1,
                                      class _Ptr2, class _Ref2>
inline bool
operator!= (const __rw_list_iter<_TypeT, _DiffT, _Ptr1, _Ref1> &__x,
            const __rw_list_iter<_TypeT, _DiffT, _Ptr2, _Ref2> &__y)
{
    return !(__x == __y);
}


template <class _TypeT, 
          class _Allocator _RWSTD_COMPLEX_DEFAULT (allocator<_TypeT>) >
class list : private _Allocator
{
public:

    typedef _TypeT                                    value_type;
    typedef _Allocator                                allocator_type;
    typedef _TYPENAME allocator_type::reference       reference;
    typedef _TYPENAME allocator_type::const_reference const_reference;
    typedef _TYPENAME allocator_type::size_type       size_type;
    typedef _TYPENAME allocator_type::difference_type difference_type;
    typedef _TYPENAME allocator_type::pointer         pointer;
    typedef _TYPENAME allocator_type::const_pointer   const_pointer;
    typedef __rw_list_node<value_type>                _C_list_node;
    typedef _C_list_node*                             _C_link_type;

    struct _C_list_node_buffer;
      
    typedef _RWSTD_REBIND (allocator_type, _C_list_node_buffer)
        _C_buf_alloc_type;

    typedef _RWSTD_REBIND (allocator_type, _C_list_node)   _C_node_alloc_type;
    typedef _RWSTD_ALLOC_TYPE (allocator_type, value_type) _C_value_alloc_type;
    typedef _TYPENAME _C_buf_alloc_type::pointer           _C_buf_pointer;

    struct _C_list_node_buffer {
        _C_buf_pointer   _C_next_buf;
        size_type        _C_bufsize;
        _C_link_type     _C_buffer;
    };


    typedef __rw_list_iter<value_type, difference_type, pointer, reference>
    _C_list_iter; 

    typedef __rw_list_iter<value_type, difference_type, const_pointer,
                           const_reference>
    _C_list_citer;


#ifndef _RWSTD_NO_DEBUG_ITER

    typedef _RW::__rw_debug_iter <list,_C_list_iter, _C_list_iter>
    iterator;
    
    typedef _RW::__rw_debug_iter <list,_C_list_citer, _C_list_iter>
    const_iterator;
    

    iterator _C_make_iter (const _C_link_type &__node) {
        return iterator (*this, _C_list_iter (__node));
    }

    const_iterator _C_make_iter (const _C_link_type &__node) const {
        return const_iterator (*this, _C_list_citer (__node));
    }

#else   // if defined (_RWSTD_NO_DEBUG_ITER)

    typedef _C_list_iter         iterator;
    typedef _C_list_citer        const_iterator;

    iterator _C_make_iter (const _C_link_type &__node) {
        return iterator (__node);
    }

    const_iterator _C_make_iter (const _C_link_type &__node) const {
        return const_iterator (__node);
    }

#endif   // _RWSTD_NO_DEBUG_ITER


#if !defined (_RWSTD_NO_CLASS_PARTIAL_SPEC) 

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

#else

    typedef _RW::__reverse_bi_iterator<const_iterator, 
        bidirectional_iterator_tag, value_type, 
        const_reference, const_pointer, difference_type>
    const_reverse_iterator;

    typedef _RW::__reverse_bi_iterator<iterator, 
        bidirectional_iterator_tag, value_type, 
        reference, pointer, difference_type>
    reverse_iterator;

#endif   // !_RWSTD_NO_CLASS_PARTIAL_SPEC

protected:
    
    _C_buf_pointer      _C_buflist;
    _C_link_type        _C_free_list;
    _C_link_type        _C_next_avail;
    _C_link_type        _C_last;
    _C_link_type        _C_node;
    size_type           _C_length;

    void _C_add_buffer (bool);

    void _C_free_buffers ();

    _C_link_type _C_get_node (bool __is_list_empty = false) {
        if (_C_free_list) {
            _C_link_type __link = _C_free_list;
            _C_free_list = _C_free_list->_C_next;
            return __link;
        }
        if (_C_next_avail == _C_last) {
            _C_add_buffer(__is_list_empty);
        }
        return _C_next_avail++;
    }

    void _C_put_node (_C_link_type __link) {
        __link->_C_next = _C_free_list;
        _C_free_list    = __link;
    }

    // here and only here is _C_node initialized
    void _C_init(bool __is_list_empty = false) {
        _C_node = _C_get_node (__is_list_empty);
        (*_C_node)._C_next = _C_node;
        (*_C_node)._C_prev = _C_node; 
    }
    
    void _C_init (size_type __n, value_type __val) {
        _C_init();
        _TRY {
            insert (begin (), __n, __val);
        }
        _CATCH (...) {
            _C_free_buffers ();
            _RETHROW;
        }
    }

public:

    _EXPLICIT
    list (const allocator_type& __alloc = allocator_type ())
        : allocator_type (__alloc), _C_buflist (0), _C_free_list (0),
          _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) {
        _C_init (true);
    }
    
    _EXPLICIT
    list (size_type             __n, 
          const_reference       __x     = value_type (),
          const allocator_type &__alloc = allocator_type ())
        : allocator_type (__alloc),  _C_buflist (0), _C_free_list (0),
          _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) {
        _C_init (__n, __x);
    }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    template<class _InputIterator>
    void _C_init (_InputIterator __first, _InputIterator __last, 
                  _RWSTD_DISPATCH_INT (false)) {
        _RWSTD_ASSERT_RANGE (__first, __last);
        _C_init();
        _TRY {
            insert (begin (), __first, __last);
        }
        _CATCH (...) {
            _C_free_buffers ();
            _RETHROW;
        }
    }

    template<class _InputIterator>
    void _C_init (_InputIterator __first, _InputIterator __last, 
                  _RWSTD_DISPATCH_INT (true)) {
        _RWSTD_ASSERT_RANGE (__first, __last);
        _C_init (__first, __last);
    }

    template<class _InputIterator>
    list (_InputIterator __first, _InputIterator __last, 
          const allocator_type& __alloc = allocator_type ())
        :  allocator_type (__alloc), _C_buflist (0), _C_free_list (0),
           _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) {
        _RWSTD_ASSERT_RANGE (__first, __last);
        _C_init (__first, __last, _RWSTD_DISPATCH (_InputIterator));
    }

#else   // if defined (_RWSTD_NO_MEMBER_TEMPLATES)

    list (const_iterator __first, const_iterator __last, 
          const allocator_type& __alloc = allocator_type ())
        : allocator_type (__alloc),  _C_buflist (0), _C_free_list (0),
          _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) {
        _RWSTD_ASSERT_RANGE (__first, __last);
        _C_init();
        _TRY {
            insert (begin (), __first, __last);
        }
        _CATCH (...) {
            _C_free_buffers ();
            _RETHROW;
        }
    }

    list (const_pointer __first, const_pointer __last, 
          const allocator_type& __alloc = allocator_type ())
        : allocator_type (__alloc), _C_buflist (0), _C_free_list (0), 
          _C_next_avail (0), _C_last (0), _C_node (0), _C_length (0) {
        _RWSTD_ASSERT_RANGE (__first, __last);
        _C_init();
        _TRY {
            insert (begin (), __first, __last);
        }
        _CATCH (...) {
            _C_free_buffers ();
            _RETHROW;
        }
    }

#endif // _RWSTD_NO_MEMBER_TEMPLATES

    list (const list &__rhs)
        : allocator_type (__rhs.get_allocator ()), _C_buflist (0),
          _C_free_list (0), _C_next_avail (0), _C_last (0), _C_node (0),
          _C_length (0) {
        _C_init();
        _TRY {
            insert (begin (), __rhs.begin (), __rhs.end ());
        }
        _CATCH (...) {
            _C_free_buffers ();
            _RETHROW;
        }
    }

    ~list () {
        if (_C_node) {
            clear ();
            _C_put_node (_C_node);
            _C_free_buffers ();
        }
    }

    list& operator= (const list&);   

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    template<class _InputIterator>
    void assign (_InputIterator __first, _InputIterator __last) {
        _RWSTD_ASSERT_RANGE (__first, __last);

        clear ();
        _C_insert (begin (), __first, __last,
                   _RWSTD_DISPATCH (_InputIterator));
    }

    void assign (size_type __n, const_reference __val) {
        clear ();
        insert (begin (), __n, __val);
    }

#else
    
    void assign (const_iterator __first, const_iterator __last) {
        _RWSTD_ASSERT_RANGE (__first, __last);

        clear ();
        insert (begin (), __first, __last);
    }

    void assign (const_pointer __first, const_pointer __last) {
        _RWSTD_ASSERT_RANGE (__first, __last);

        clear ();
        insert (begin (), __first, __last);
    }

    void assign (size_type __n, const_reference __val) {
        clear ();
        insert (begin (), __n, __val);
    }

#endif // _RWSTD_NO_MEMBER_TEMPLATES

    allocator_type get_allocator () const {
        return *this;
    }

    iterator begin () {
        return _C_make_iter ((*_C_node)._C_next);
    }

    const_iterator begin () const {
        return _C_make_iter ((*_C_node)._C_next);
    }

    iterator end () {
        return _C_make_iter (_C_node);
    }

    const_iterator end () const {
        return _C_make_iter (_C_node);
    }

    reverse_iterator rbegin () { 
        return reverse_iterator (end ());
    }

    const_reverse_iterator rbegin () const { 
        return const_reverse_iterator (end ());
    }

    reverse_iterator rend () { 
        return reverse_iterator (begin ());
    }

    const_reverse_iterator rend () const {