// Components for manipulating sequences of characters -*- C++ -*-
-// Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+// Copyright (C) 1997, 1998, 1999, 2000, 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
#ifndef _CPP_BITS_STRING_TCC
#define _CPP_BITS_STRING_TCC 1
+#pragma GCC system_header
+
namespace std
{
template<typename _CharT, typename _Traits, typename _Alloc>
- const _CharT
+ const typename basic_string<_CharT, _Traits, _Alloc>::size_type
basic_string<_CharT, _Traits, _Alloc>::
- _Rep::_S_terminal = _CharT();
+ _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
template<typename _CharT, typename _Traits, typename _Alloc>
- const typename basic_string<_CharT, _Traits, _Alloc>::size_type
+ const _CharT
basic_string<_CharT, _Traits, _Alloc>::
- _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
+ _Rep::_S_terminal = _CharT();
template<typename _CharT, typename _Traits, typename _Alloc>
const typename basic_string<_CharT, _Traits, _Alloc>::size_type
template<typename _CharT, typename _Traits, typename _Alloc>
template <class _InIter>
_CharT*
- basic_string<_CharT,_Traits,_Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>::
_S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
forward_iterator_tag)
{
size_type __dnew = static_cast<size_type>(distance(__beg, __end));
+ // NB: Not required, but considered best practice.
+ if (__builtin_expect(__beg == _InIter(0), 0))
+ __throw_logic_error("attempt to create string with null pointer");
+
if (__beg == __end && __a == _Alloc())
return _S_empty_rep()._M_refcopy();
template<typename _CharT, typename _Traits, typename _Alloc>
_CharT*
- basic_string<_CharT,_Traits, _Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>::
_S_construct(size_type __n, _CharT __c, const _Alloc& __a)
{
if (__n == 0 && __a == _Alloc())
template<typename _CharT, typename _Traits, typename _Alloc>
basic_string<_CharT, _Traits, _Alloc>::
basic_string(const _CharT* __s, const _Alloc& __a)
- : _M_dataplus(_S_construct(__s, __s + traits_type::length(__s), __a), __a)
+ : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 0,
+ __a), __a)
{ }
template<typename _CharT, typename _Traits, typename _Alloc>
_M_rep()->_M_set_leaked();
}
+ // _M_mutate and, below, _M_clone, include, in the same form, an exponential
+ // growth policy, necessary to meet amortized linear time requirements of
+ // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
+ // The policy is active for allocations requiring an amount of memory above
+ // system pagesize. This is consistent with the requirements of the standard:
+ // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
template<typename _CharT, typename _Traits, typename _Alloc>
void
basic_string<_CharT, _Traits, _Alloc>::
{
// Must reallocate.
allocator_type __a = get_allocator();
- _Rep* __r = _Rep::_S_create(__new_size, __a);
+ // See below (_S_create) for the meaning and value of these
+ // constants.
+ const size_type __pagesize = 4096;
+ const size_type __malloc_header_size = 4 * sizeof (void*);
+ // The biggest string which fits in a memory page
+ const size_type __page_capacity = (__pagesize - __malloc_header_size
+ - sizeof(_Rep) - sizeof(_CharT))
+ / sizeof(_CharT);
+ _Rep* __r;
+ if (__new_size > capacity() && __new_size > __page_capacity)
+ // Growing exponentially.
+ __r = _Rep::_S_create(__new_size > 2*capacity() ?
+ __new_size : 2*capacity(), __a);
+ else
+ __r = _Rep::_S_create(__new_size, __a);
try
{
if (__pos)
{
if (__res > this->max_size())
__throw_length_error("basic_string::reserve");
+ // Make sure we don't shrink below the current size
+ if (__res < this->size())
+ __res = this->size();
allocator_type __a = get_allocator();
_CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
_M_rep()->_M_dispose(__a);
}
}
-#ifdef _GLIBCPP_ALLOC_CONTROL
- template<typename _CharT, typename _Traits, typename _Alloc>
- bool (*basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_excess_slop)
- (size_t, size_t) =
- basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_default_excess;
-#endif
-
template<typename _CharT, typename _Traits, typename _Alloc>
typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
basic_string<_CharT, _Traits, _Alloc>::_Rep::
// terminating null char_type() element, plus enough for the
// _Rep data structure. Whew. Seemingly so needy, yet so elemental.
size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+
+ // The standard places no restriction on allocating more memory
+ // than is strictly needed within this layer at the moment or as
+ // requested by an explicit application call to reserve(). Many
+ // malloc implementations perform quite poorly when an
+ // application attempts to allocate memory in a stepwise fashion
+ // growing each allocation size by only 1 char. Additionally,
+ // it makes little sense to allocate less linear memory than the
+ // natural blocking size of the malloc implementation.
+ // Unfortunately, we would need a somewhat low-level calculation
+ // with tuned parameters to get this perfect for any particular
+ // malloc implementation. Fortunately, generalizations about
+ // common features seen among implementations seems to suffice.
+
+ // __pagesize need not match the actual VM page size for good
+ // results in practice, thus we pick a common value on the low
+ // side. __malloc_header_size is an estimate of the amount of
+ // overhead per memory allocation (in practice seen N * sizeof
+ // (void*) where N is 0, 2 or 4). According to folklore,
+ // picking this value on the high side is better than
+ // low-balling it (especially when this algorithm is used with
+ // malloc implementations that allocate memory blocks rounded up
+ // to a size which is a power of 2).
+ const size_t __pagesize = 4096; // must be 2^i * __subpagesize
+ const size_t __subpagesize = 128; // should be >> __malloc_header_size
+ const size_t __malloc_header_size = 4 * sizeof (void*);
+ if ((__size + __malloc_header_size) > __pagesize)
+ {
+ size_t __extra =
+ (__pagesize - ((__size + __malloc_header_size) % __pagesize))
+ % __pagesize;
+ __capacity += __extra / sizeof(_CharT);
+ __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ }
+ else if (__size > __subpagesize)
+ {
+ size_t __extra =
+ (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
+ % __subpagesize;
+ __capacity += __extra / sizeof(_CharT);
+ __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
+ }
+
// NB: Might throw, but no worries about a leak, mate: _Rep()
// does not throw.
void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
_Rep *__p = new (__place) _Rep;
__p->_M_capacity = __capacity;
- __p->_M_set_sharable(); // one reference
+ __p->_M_set_sharable(); // One reference.
__p->_M_length = 0;
return __p;
}
basic_string<_CharT, _Traits, _Alloc>::_Rep::
_M_clone(const _Alloc& __alloc, size_type __res)
{
- _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
+ // Requested capacity of the clone.
+ const size_type __requested_cap = _M_length + __res;
+ // See above (_S_create) for the meaning and value of these constants.
+ const size_type __pagesize = 4096;
+ const size_type __malloc_header_size = 4 * sizeof (void*);
+ // The biggest string which fits in a memory page.
+ const size_type __page_capacity =
+ (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
+ / sizeof(_CharT);
+ _Rep* __r;
+ if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
+ // Growing exponentially.
+ __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
+ __requested_cap : 2*_M_capacity, __alloc);
+ else
+ __r = _Rep::_S_create(__requested_cap, __alloc);
+
if (_M_length)
{
try
}
template<typename _CharT, typename _Traits, typename _Alloc>
- inline bool
-#ifdef _GLIBCPP_ALLOC_CONTROL
- basic_string<_CharT, _Traits, _Alloc>::_Rep::
- _S_default_excess(size_t __s, size_t __r)
-#else
- basic_string<_CharT, _Traits, _Alloc>::_Rep::
- _S_excess_slop(size_t __s, size_t __r)
-#endif
- {
- return 2 * (__s <= 16 ? 16 : __s) < __r;
- }
-
- template<typename _CharT, typename _Traits, typename _Alloc>
void
basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
{
this->erase(__n);
// else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
}
-
+
+ // This is the general replace helper, which currently gets instantiated both
+ // for input iterators and reverse iterators. It buffers internally and then
+ // calls _M_replace_safe.
template<typename _CharT, typename _Traits, typename _Alloc>
template<typename _InputIter>
basic_string<_CharT, _Traits, _Alloc>&
_M_replace(iterator __i1, iterator __i2, _InputIter __k1,
_InputIter __k2, input_iterator_tag)
{
+ // Save concerned source string data in a temporary.
basic_string __s(__k1, __k2);
- return this->replace(__i1, __i2, __s._M_ibegin(), __s._M_iend());
+ return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
}
+ // This is a special replace helper, which does not buffer internally
+ // and can be used in "safe" situations involving forward iterators,
+ // i.e., when source and destination ranges are known to not overlap.
template<typename _CharT, typename _Traits, typename _Alloc>
template<typename _ForwardIter>
basic_string<_CharT, _Traits, _Alloc>&
basic_string<_CharT, _Traits, _Alloc>::
- _M_replace(iterator __i1, iterator __i2, _ForwardIter __k1,
- _ForwardIter __k2, forward_iterator_tag)
+ _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
+ _ForwardIter __k2)
{
+ size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
size_type __dold = __i2 - __i1;
size_type __dmax = this->max_size();
- size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
if (__dmax <= __dnew)
__throw_length_error("basic_string::_M_replace");
size_type __off = __i1 - _M_ibegin();
_M_mutate(__off, __dold, __dnew);
+
// Invalidated __i1, __i2
- if (__dnew)
+ if (__dnew)
_S_copy_chars(_M_data() + __off, __k1, __k2);
-
+
return *this;
}
replace(size_type __pos1, size_type __n1, const basic_string& __str,
size_type __pos2, size_type __n2)
{
- return this->replace(_M_check(__pos1), _M_fold(__pos1, __n1),
- __str._M_check(__pos2),
- __str._M_fold(__pos2, __n2));
+ const size_type __strsize = __str.size();
+ if (__pos2 > __strsize)
+ __throw_out_of_range("basic_string::replace");
+ const bool __testn2 = __n2 < __strsize - __pos2;
+ const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
+ return this->replace(__pos1, __n1,
+ __str._M_data() + __pos2, __foldn2);
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>&
- basic_string<_CharT,_Traits,_Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
append(const basic_string& __str)
{
// Iff appending itself, string needs to pre-reserve the
size_type __len = __size + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __str._M_ibegin(),
- __str._M_iend());
+ return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
+ __str._M_iend());
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>&
- basic_string<_CharT,_Traits,_Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
append(const basic_string& __str, size_type __pos, size_type __n)
{
// Iff appending itself, string needs to pre-reserve the
size_type __len = min(__str.size() - __pos, __n) + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __str._M_check(__pos),
- __str._M_fold(__pos, __n));
+ return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
+ __str._M_fold(__pos, __n));
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>&
- basic_string<_CharT,_Traits,_Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
append(const _CharT* __s, size_type __n)
{
size_type __len = __n + this->size();
if (__len > this->capacity())
this->reserve(__len);
- return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
+ return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>&
- basic_string<_CharT,_Traits,_Alloc>::
+ basic_string<_CharT, _Traits, _Alloc>&
+ basic_string<_CharT, _Traits, _Alloc>::
append(size_type __n, _CharT __c)
{
size_type __len = __n + this->size();
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>
+ basic_string<_CharT, _Traits, _Alloc>
operator+(const _CharT* __lhs,
- const basic_string<_CharT,_Traits,_Alloc>& __rhs)
+ const basic_string<_CharT, _Traits, _Alloc>& __rhs)
{
- typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
+ typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
typedef typename __string_type::size_type __size_type;
__size_type __len = _Traits::length(__lhs);
__string_type __str;
}
template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT,_Traits,_Alloc>
- operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
+ basic_string<_CharT, _Traits, _Alloc>
+ operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
{
- typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
+ typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
typedef typename __string_type::size_type __size_type;
__string_type __str;
__size_type __len = __rhs.size();
size_type __size = this->size();
if (__n <= __size)
{
- __pos = std::min(__size - __n ,__pos);
+ __pos = std::min(__size - __n, __pos);
const _CharT* __data = _M_data();
do
{
template<typename _CharT, typename _Traits, typename _Alloc>
int
- basic_string <_CharT,_Traits,_Alloc>::
+ basic_string <_CharT, _Traits, _Alloc>::
compare(size_type __pos, size_type __n1, const _CharT* __s) const
{
size_type __size = this->size();
template<typename _CharT, typename _Traits, typename _Alloc>
int
- basic_string <_CharT,_Traits,_Alloc>::
+ basic_string <_CharT, _Traits, _Alloc>::
compare(size_type __pos, size_type __n1, const _CharT* __s,
size_type __n2) const
{
_Traits::copy(__buf, __str.data(), __bytes);
__buf[__bytes] = _CharT();
}
+
+ // Inhibit implicit instantiations for required instantiations,
+ // which are defined via explicit instantiations elsewhere.
+ // NB: This syntax is a GNU extension.
+ extern template class basic_string<char>;
+ extern template
+ basic_istream<char>&
+ operator>>(basic_istream<char>&, string&);
+ extern template
+ basic_ostream<char>&
+ operator<<(basic_ostream<char>&, const string&);
+ extern template
+ basic_istream<char>&
+ getline(basic_istream<char>&, string&, char);
+ extern template
+ basic_istream<char>&
+ getline(basic_istream<char>&, string&);
+
+ extern template class basic_string<wchar_t>;
+ extern template
+ basic_istream<wchar_t>&
+ operator>>(basic_istream<wchar_t>&, wstring&);
+ extern template
+ basic_ostream<wchar_t>&
+ operator<<(basic_ostream<wchar_t>&, const wstring&);
+ extern template
+ basic_istream<wchar_t>&
+ getline(basic_istream<wchar_t>&, wstring&, wchar_t);
+ extern template
+ basic_istream<wchar_t>&
+ getline(basic_istream<wchar_t>&, wstring&);
} // namespace std
#endif
OSDN Git Service
