stl_deque.h

来自「symbian上STL模板库的实现」· C头文件 代码 · 共 1,143 行 · 第 1/5 页

// Deque implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004 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) 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) 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 stl_deque.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _DEQUE_H
#define _DEQUE_H 1

#include <bits/concept_check.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>

namespace _GLIBCXX_STD
{
    /**
     *  @if maint
     *  @brief This function controls the size of memory nodes.
     *  @param  size  The size of an element.
     *  @return   The number (not byte size) of elements per node.
     *
     *  This function started off as a compiler kludge from SGI, but seems to
     *  be a useful wrapper around a repeated constant expression.  The '512' is
     *  tuneable (and no other code needs to change), but no investigation has
     *  been done since inheriting the SGI code.
     *  @endif
     */
    inline size_t
        __deque_buf_size(size_t __size)
        { return __size < 512 ? size_t(512 / __size) : size_t(1); }


    /**
     *  @brief A deque::iterator.
     *
     *  Quite a bit of intelligence here.  Much of the functionality of deque is
     *  actually passed off to this class.  A deque holds two of these internally,
     *  marking its valid range.  Access to elements is done as offsets of either
     *  of those two, relying on operator overloading in this class.
     *
     *  @if maint
     *  All the functions are op overloads except for _M_set_node.
     *  @endif
     */
    template<typename _Tp, typename _Ref, typename _Ptr>
        struct _Deque_iterator
        {
            typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
            typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;

            static size_t _S_buffer_size()
            { return __deque_buf_size(sizeof(_Tp)); }

            typedef random_access_iterator_tag iterator_category;
            typedef _Tp                        value_type;
            typedef _Ptr                       pointer;
            typedef _Ref                       reference;
            typedef size_t                     size_type;
            typedef ptrdiff_t                  difference_type;
            typedef _Tp**                      _Map_pointer;
            typedef _Deque_iterator            _Self;

            _Tp* _M_cur;
            _Tp* _M_first;
            _Tp* _M_last;
            _Map_pointer _M_node;

            _Deque_iterator(_Tp* __x, _Map_pointer __y)
                : _M_cur(__x), _M_first(*__y),
                _M_last(*__y + _S_buffer_size()), _M_node(__y) {}

            _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}

            _Deque_iterator(const iterator& __x)
                : _M_cur(__x._M_cur), _M_first(__x._M_first),
                _M_last(__x._M_last), _M_node(__x._M_node) {}

            reference
                operator*() const
                { return *_M_cur; }

            pointer
                operator->() const
                { return _M_cur; }

            _Self&
                operator++()
                {
                    ++_M_cur;
                    if (_M_cur == _M_last)
                    {
                        _M_set_node(_M_node + 1);
                        _M_cur = _M_first;
                    }
                    return *this;
                }

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

            _Self&
                operator--()
                {
                    if (_M_cur == _M_first)
                    {
                        _M_set_node(_M_node - 1);
                        _M_cur = _M_last;
                    }
                    --_M_cur;
                    return *this;
                }

            _Self
                operator--(int)
                {
                    _Self __tmp = *this;
                    --*this;
                    return __tmp;
                }

            _Self&
                operator+=(difference_type __n)
                {
                    const difference_type __offset = __n + (_M_cur - _M_first);
                    if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
                        _M_cur += __n;
                    else
                    {
                        const difference_type __node_offset =
                            __offset > 0 ? __offset / difference_type(_S_buffer_size())
                            : -difference_type((-__offset - 1)
                                    / _S_buffer_size()) - 1;
                        _M_set_node(_M_node + __node_offset);
                        _M_cur = _M_first + (__offset - __node_offset
                                * difference_type(_S_buffer_size()));
                    }
                    return *this;
                }

            _Self
                operator+(difference_type __n) const
                {
                    _Self __tmp = *this;
                    return __tmp += __n;
                }

            _Self&
                operator-=(difference_type __n)
                { return *this += -__n; }

            _Self
                operator-(difference_type __n) const
                {
                    _Self __tmp = *this;
                    return __tmp -= __n;
                }

            reference
                operator[](difference_type __n) const
                { return *(*this + __n); }

            /** @if maint
             *  Prepares to traverse new_node.  Sets everything except _M_cur, which
             *  should therefore be set by the caller immediately afterwards, based on
             *  _M_first and _M_last.
             *  @endif
             */
            void
                _M_set_node(_Map_pointer __new_node)
                {