slist

symbian上STL模板库的实现

// Singly-linked list implementation -*- C++ -*-

// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 * Copyright (c) 1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * 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.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */

/** @file ext/slist
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).  You should only
 *  include this header if you are using GCC 3 or later.
 */

#ifndef _SLIST
#define _SLIST 1

#include <bits/stl_algobase.h>
#include <bits/allocator.h>
#include <bits/stl_construct.h>
#include <bits/stl_uninitialized.h>
#include <bits/concept_check.h>

namespace __gnu_cxx
{
    using std::size_t;
    using std::ptrdiff_t;
    using std::_Construct;
    using std::_Destroy;
    using std::allocator;

    struct _Slist_node_base
    {
        _Slist_node_base* _M_next;
    };

    inline _Slist_node_base*
        __slist_make_link(_Slist_node_base* __prev_node,
                _Slist_node_base* __new_node)
        {
            __new_node->_M_next = __prev_node->_M_next;
            __prev_node->_M_next = __new_node;
            return __new_node;
        }

    inline _Slist_node_base*
        __slist_previous(_Slist_node_base* __head,
                const _Slist_node_base* __node)
        {
            while (__head && __head->_M_next != __node)
                __head = __head->_M_next;
            return __head;
        }

    inline const _Slist_node_base*
        __slist_previous(const _Slist_node_base* __head,
                const _Slist_node_base* __node)
        {
            while (__head && __head->_M_next != __node)
                __head = __head->_M_next;
            return __head;
        }

    inline void __slist_splice_after(_Slist_node_base* __pos,
            _Slist_node_base* __before_first,
            _Slist_node_base* __before_last)
    {
        if (__pos != __before_first && __pos != __before_last) {
            _Slist_node_base* __first = __before_first->_M_next;
            _Slist_node_base* __after = __pos->_M_next;
            __before_first->_M_next = __before_last->_M_next;
            __pos->_M_next = __first;
            __before_last->_M_next = __after;
        }
    }

    inline void
        __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head)
        {
            _Slist_node_base* __before_last = __slist_previous(__head, 0);
            if (__before_last != __head) {
                _Slist_node_base* __after = __pos->_M_next;
                __pos->_M_next = __head->_M_next;
                __head->_M_next = 0;
                __before_last->_M_next = __after;
            }
        }

    inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node)
    {
        _Slist_node_base* __result = __node;
        __node = __node->_M_next;
        __result->_M_next = 0;
        while(__node) {
            _Slist_node_base* __next = __node->_M_next;
            __node->_M_next = __result;
            __result = __node;
            __node = __next;
        }
        return __result;
    }

    inline size_t __slist_size(_Slist_node_base* __node)
    {
        size_t __result = 0;
        for ( ; __node != 0; __node = __node->_M_next)
            ++__result;
        return __result;
    }

    template <class _Tp>
        struct _Slist_node : public _Slist_node_base
    {
        _Tp _M_data;
    };

    struct _Slist_iterator_base
    {
        typedef size_t                    size_type;
        typedef ptrdiff_t                 difference_type;
        typedef std::forward_iterator_tag iterator_category;

        _Slist_node_base* _M_node;

        _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
        void _M_incr() { _M_node = _M_node->_M_next; }

        bool operator==(const _Slist_iterator_base& __x) const {
            return _M_node == __x._M_node;
        }
        bool operator!=(const _Slist_iterator_base& __x) const {
            return _M_node != __x._M_node;
        }
    };

    template <class _Tp, class _Ref, class _Ptr>
        struct _Slist_iterator : public _Slist_iterator_base
    {
        typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
        typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
        typedef _Slist_iterator<_Tp, _Ref, _Ptr>             _Self;

        typedef _Tp              value_type;
        typedef _Ptr             pointer;
        typedef _Ref             reference;
        typedef _Slist_node<_Tp> _Node;

        _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
        _Slist_iterator() : _Slist_iterator_base(0) {}
        _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}

        reference operator*() const { return ((_Node*) _M_node)->_M_data; }
        pointer operator->() const { return &(operator*()); }

        _Self& operator++()
        {
            _M_incr();
            return *this;
        }
        _Self operator++(int)
        {
            _Self __tmp = *this;
            _M_incr();
            return __tmp;
        }
    };

    template <class _Tp, class _Alloc>
        struct _Slist_base
        : public _Alloc::template rebind<_Slist_node<_Tp> >::other
        {
            typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other _Node_alloc;
            typedef _Alloc allocator_type;
            allocator_type get_allocator() const {
                return *static_cast<const _Node_alloc*>(this);
            }

            _Slist_base(const allocator_type& __a)
                : _Node_alloc(__a) { this->_M_head._M_next = 0; }
            ~_Slist_base() { _M_erase_after(&this->_M_head, 0); }

            protected:
            _Slist_node_base _M_head;

            _Slist_node<_Tp>* _M_get_node() { return _Node_alloc::allocate(1); }
            void _M_put_node(_Slist_node<_Tp>* __p) { _Node_alloc::deallocate(__p, 1); }

            protected:
            _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
            {
                _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next);
                _Slist_node_base* __next_next = __next->_M_next;
                __pos->_M_next = __next_next;
                _Destroy(&__next->_M_data);
                _M_put_node(__next);
                return __next_next;
            }
            _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
        };

    template <class _Tp, class _Alloc>
        _Slist_node_base*
        _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first,
                _Slist_node_base* __last_node) {
            _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next);
            while (__cur != __last_node) {
                _Slist_node<_Tp>* __tmp = __cur;
                __cur = (_Slist_node<_Tp>*) __cur->_M_next;
                _Destroy(&__tmp->_M_data);
                _M_put_node(__tmp);
            }
            __before_first->_M_next = __last_node;
            return __last_node;
        }

    /**
     *  This is an SGI extension.
     *  @ingroup SGIextensions
     *  @doctodo
     */
    template <class _Tp, class _Alloc = allocator<_Tp> >
        class slist : private _Slist_base<_Tp,_Alloc>
    {
        // concept requirements
        __glibcxx_class_requires(_Tp, _SGIAssignableConcept)

        private:
            typedef _Slist_base<_Tp,_Alloc> _Base;
        public:
            typedef _Tp               value_type;
            typedef value_type*       pointer;
            typedef const value_type* const_pointer;
            typedef value_type&       reference;
            typedef const value_type& const_reference;
            typedef size_t            size_type;
            typedef ptrdiff_t         difference_type;

            typedef _Slist_iterator<_Tp, _Tp&, _Tp*>             iterator;
            typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

            typedef typename _Base::allocator_type allocator_type;
            allocator_type get_allocator() const { return _Base::get_allocator(); }

        private:
            typedef _Slist_node<_Tp>      _Node;
            typedef _Slist_node_base      _Node_base;
            typedef _Slist_iterator_base  _Iterator_base;

            _Node* _M_create_node(const value_type& __x) {
                _Node* __node = this->_M_get_node();
                try {
                    _Construct(&__node->_M_data, __x);
                    __node->_M_next = 0;
                }
                catch(...)
                {
                    this->_M_put_node(__node);
                    __throw_exception_again;
                }
                return __node;
            }

            _Node* _M_create_node() {
                _Node* __node = this->_M_get_node();
                try {
                    _Construct(&__node->_M_data);
                    __node->_M_next = 0;
                }