basic_string.h

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

// Components for manipulating sequences of characters -*- C++ -*-

// Copyright (C) 1997, 1998, 1999, 2000, 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.

//
// ISO C++ 14882: 21 Strings library
//

/** @file basic_string.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef _BASIC_STRING_H
#define _BASIC_STRING_H 1

#pragma GCC system_header

#include <bits/atomicity.h>
#include <debug/debug.h>

namespace std
{
    /**
     *  @class basic_string basic_string.h <string>
     *  @brief  Managing sequences of characters and character-like objects.
     *
     *  @ingroup Containers
     *  @ingroup Sequences
     *
     *  Meets the requirements of a <a href="tables.html#65">container</a>, a
     *  <a href="tables.html#66">reversible container</a>, and a
     *  <a href="tables.html#67">sequence</a>.  Of the
     *  <a href="tables.html#68">optional sequence requirements</a>, only
     *  @c push_back, @c at, and array access are supported.
     *
     *  @doctodo
     *
     *
     *  @if maint
     *  Documentation?  What's that?
     *  Nathan Myers <[e-mail]>.
     *
     *  A string looks like this:
     *
     *  @code
     *                                        [_Rep]
     *                                        _M_length
     *   [basic_string<char_type>]            _M_capacity
     *   _M_dataplus                          _M_refcount
     *   _M_p ---------------->               unnamed array of char_type
     *  @endcode
     *
     *  Where the _M_p points to the first character in the string, and
     *  you cast it to a pointer-to-_Rep and subtract 1 to get a
     *  pointer to the header.
     *
     *  This approach has the enormous advantage that a string object
     *  requires only one allocation.  All the ugliness is confined
     *  within a single pair of inline functions, which each compile to
     *  a single "add" instruction: _Rep::_M_data(), and
     *  string::_M_rep(); and the allocation function which gets a
     *  block of raw bytes and with room enough and constructs a _Rep
     *  object at the front.
     *
     *  The reason you want _M_data pointing to the character array and
     *  not the _Rep is so that the debugger can see the string
     *  contents. (Probably we should add a non-inline member to get
     *  the _Rep for the debugger to use, so users can check the actual
     *  string length.)
     *
     *  Note that the _Rep object is a POD so that you can have a
     *  static "empty string" _Rep object already "constructed" before
     *  static constructors have run.  The reference-count encoding is
     *  chosen so that a 0 indicates one reference, so you never try to
     *  destroy the empty-string _Rep object.
     *
     *  All but the last paragraph is considered pretty conventional
     *  for a C++ string implementation.
     *  @endif
     */
    // 21.3  Template class basic_string
    template<typename _CharT, typename _Traits, typename _Alloc>
        class basic_string
        {
            // Types:
            public:
                typedef _Traits					    traits_type;
                typedef typename _Traits::char_type		    value_type;
                typedef _Alloc					    allocator_type;
                typedef typename _Alloc::size_type		    size_type;
                typedef typename _Alloc::difference_type		    difference_type;
                typedef typename _Alloc::reference		    reference;
                typedef typename _Alloc::const_reference		    const_reference;
                typedef typename _Alloc::pointer			    pointer;
                typedef typename _Alloc::const_pointer		    const_pointer;
                typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
                typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
                    const_iterator;
                typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
                typedef std::reverse_iterator<iterator>		    reverse_iterator;

            private:
                // _Rep: string representation
                //   Invariants:
                //   1. String really contains _M_length + 1 characters: due to 21.3.4
                //      must be kept null-terminated.
                //   2. _M_capacity >= _M_length
                //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
                //   3. _M_refcount has three states:
                //      -1: leaked, one reference, no ref-copies allowed, non-const.
                //       0: one reference, non-const.
                //     n>0: n + 1 references, operations require a lock, const.
                //   4. All fields==0 is an empty string, given the extra storage
                //      beyond-the-end for a null terminator; thus, the shared
                //      empty string representation needs no constructor.

                struct _Rep_base
                {
                    size_type		_M_length;
                    size_type		_M_capacity;
                    _Atomic_word		_M_refcount;
                };

                struct _Rep : _Rep_base
            {
                // Types:
                typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;

                // (Public) Data members:

                // The maximum number of individual char_type elements of an
                // individual string is determined by _S_max_size. This is the
                // value that will be returned by max_size().  (Whereas npos
                // is the maximum number of bytes the allocator can allocate.)
                // If one was to divvy up the theoretical largest size string,
                // with a terminating character and m _CharT elements, it'd
                // look like this:
                // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
                // Solving for m:
                // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
                // In addition, this implementation quarters this amount.
                static const size_type	_S_max_size;
                static const _CharT	_S_terminal;

                // The following storage is init'd to 0 by the linker, resulting
                // (carefully) in an empty string with one reference.
                static size_type _S_empty_rep_storage[];

                static _Rep&
                    _S_empty_rep()
                    { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }

                bool
                    _M_is_leaked() const
                    { return this->_M_refcount < 0; }

                bool
                    _M_is_shared() const
                    { return this->_M_refcount > 0; }

                void
                    _M_set_leaked()
                    { this->_M_refcount = -1; }

                void
                    _M_set_sharable()
                    { this->_M_refcount = 0; }

                _CharT*
                    _M_refdata() throw()
                    { return reinterpret_cast<_CharT*>(this + 1); }

                _CharT*
                    _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
                    {
                        return (!_M_is_leaked() && __alloc1 == __alloc2)
                            ? _M_refcopy() : _M_clone(__alloc1);
                    }

                // Create & Destroy
                static _Rep*
                    _S_create(size_type, size_type, const _Alloc&);

                void
                    _M_dispose(const _Alloc& __a)
                    {
                        if (__builtin_expect(this != &_S_empty_rep(), false))
                            if (__gnu_cxx::__exchange_and_add(&this->_M_refcount, -1) <= 0)
                                _M_destroy(__a);
                    }  // XXX MT

                void
                    _M_destroy(const _Alloc&) throw();

                _CharT*
                    _M_refcopy() throw()
                    {
                        if (__builtin_expect(this != &_S_empty_rep(), false))
                            __gnu_cxx::__atomic_add(&this->_M_refcount, 1);
                        return _M_refdata();
                    }  // XXX MT

                _CharT*
                    _M_clone(const _Alloc&, size_type __res = 0);
            };

                // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
                struct _Alloc_hider : _Alloc
            {
                _Alloc_hider(_CharT* __dat, const _Alloc& __a)
                    : _Alloc(__a), _M_p(__dat) { }

                _CharT* _M_p; // The actual data.
            };

            public:
                // Data Members (public):
                // NB: This is an unsigned type, and thus represents the maximum
                // size that the allocator can hold.
                /// @var
                /// Value returned by various member functions when they fail.
                static const size_type	npos = static_cast<size_type>(-1);

            private:
                // Data Members (private):
                mutable _Alloc_hider	_M_dataplus;

                _CharT*
                    _M_data() const
                    { return  _M_dataplus._M_p; }

                _CharT*
                    _M_data(_CharT* __p)
                    { return (_M_dataplus._M_p = __p); }

                _Rep*
                    _M_rep() const
                    { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

                // For the internal use we have functions similar to `begin'/`end'
                // but they do not call _M_leak.
                iterator
                    _M_ibegin() const { return iterator(_M_data()); }

                iterator
                    _M_iend() const { return iterator(_M_data() + this->size()); }

                void
                    _M_leak()    // for use in begin() & non-const op[]