This is the mail archive of the
libstdc++@sourceware.cygnus.com
mailing list for the libstdc++ project.
basic_string<>::_M_mutate - patch
- To: Benjamin Kosnik <bkoz@cygnus.com>
- Subject: basic_string<>::_M_mutate - patch
- From: Ryszard Kabatek <rysio@rumcajs.chemie.uni-halle.de>
- Date: Mon, 28 Jun 1999 11:19:02 +0200 (CEST)
- cc: Nathan Myers <ncm@best.com>, libstdc++@sourceware.cygnus.com
- Reply-To: Ryszard Kabatek <kabatek@chemie.uni-halle.de>
All functions that modify the string (insert, append, assign, ...)
call replace and replace calls _M_mutate.
The current implementation of _M_mutate is a really inefficient solution.
Every call of this function that grows the string leads to a reallocation!
The storage between size() and capacity() is ignored!
-----------------------------------------------------
The current implementation goes the following way:
if (has no reference copies and the new length is less/equal than the old one)
{ do not reallocate }
else
{ reallocate }
So if we create an empty string, reserve a lot of space and then we append
only one (1) character, a reallocation occurs!
I reimplemented reserve and
I reimplemented the _M_mutate function and I modified its interface:
_M_mutate(size_type __pos, // at this position starts the change
size_type __len1, // the amount of characters to be replaced
size_type __len2) // with this amount of characters
If __len1 == __len2, _M_mutate only clones (if necessary) the _Rep.
Below the new implementation of _M_mutate.
The attachment contains the patch.
1999-06-28 Ryszard Kabatek <kabatek@chemie.uni-halle.de>
* bits/string.tcc: New implementation and interface of _M_mutate.
New implementation of reserve.
Adapt the change in all functions that call _M_mutate.
* bits/basic_string.h:
And here.
BTW 1: In the implementation of basic_string<> every call of
traits::copy is enclosed in a try block.
May traits::copy throw an exception?
BTW 2: bits/basic_string.h, 56:
__range > 0 ? __range : -1 * __range;
makes nothing.
template<typename _CharT, typename _Traits, typename _Alloc>
void
basic_string<_CharT, _Traits, _Alloc>::
_M_mutate(size_type __pos, size_type __len1, size_type __len2)
{
const size_type __old_size = size();
const size_type __new_size = __old_size + __len2 - __len1;
if (__len1 == __len2)
// clone if necessary
{
if (_M_rep()->_M_state > 0)
{
allocator_type __a = get_allocator();
_CharT* __tmp = _M_rep()->_M_clone(__a);
_M_rep()->_M_dispose(__a);
_M_data(__tmp);
}
else
_M_rep()->_M_state = 0;
}
else
{
const _CharT* __src = _M_data() + __pos + __len1;
const size_type __how_much = __old_size - __pos - __len1;
if (_M_rep()->_M_state > 0 || __new_size > capacity())
// must reallocate
{
_Rep* __r = _Rep::_S_create(__new_size, get_allocator());
try {
if (__pos)
traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
if (__how_much)
traits_type::copy(__r->_M_refdata() + __pos + __len2,
__src,
__how_much);
}
catch (...) {
__r->_M_dispose(get_allocator());
throw;
}
_M_rep()->_M_dispose(get_allocator());
_M_data(__r->_M_refdata());
}
else if (__how_much)
{
// Work in-place
_M_rep()->_M_state = 0;
traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
}
_M_rep()->_M_length = __new_size;
}
_M_data()[__new_size] = _CharT(); // grrr. (per 21.3.4)
// (you cannot leave those LWG people alone for a second.)
}
Ryszard Kabatek
Martin-Luther University Halle-Wittenberg, Department of Physical Chemistry
Geusaer Str. 88, 06217 Merseburg, Germany
Tel. +49 3461 46 2487 (2466) Fax. +49 3461 46 2129
Index: bits/basic_string.h
===================================================================
RCS file: /cvs/libstdc++/libstdc++/bits/basic_string.h,v
retrieving revision 1.38
diff -c -2 -p -r1.38 basic_string.h
*** basic_string.h 1999/06/25 03:55:24 1.38
--- basic_string.h 1999/06/28 09:08:39
*************** namespace std {
*** 280,284 ****
void
! _M_mutate(size_type __nsize, size_type __keep, size_type __keep_end);
void
--- 280,284 ----
void
! _M_mutate(size_type __pos, size_type __len1, size_type __len2);
void
*************** namespace std {
*** 396,400 ****
void
! clear() { _M_mutate(0, 0, 0); }
bool
--- 396,400 ----
void
! clear() { _M_mutate(0, this->size(), 0); }
bool
Index: bits/string.tcc
===================================================================
RCS file: /cvs/libstdc++/libstdc++/bits/string.tcc,v
retrieving revision 1.42
diff -c -2 -p -r1.42 string.tcc
*** string.tcc 1999/06/25 03:55:50 1.42
--- string.tcc 1999/06/28 09:08:41
*************** namespace std
*** 179,183 ****
{
if (_M_rep()->_M_state > 0)
! _M_mutate(this->size(), this->size(), 0);
_M_rep()->_M_state = -1;
}
--- 179,183 ----
{
if (_M_rep()->_M_state > 0)
! _M_mutate(0, 0, 0);
_M_rep()->_M_state = -1;
}
*************** namespace std
*** 186,220 ****
void
basic_string<_CharT, _Traits, _Alloc>::
! _M_mutate(size_type __nsize, size_type __keep, size_type __keep_end)
{
! size_type __old_size = this->size();
! if (_M_rep()->_M_state <= 0 && __nsize <= __old_size)
! {
! // Work in-place
! _M_rep()->_M_state = 0;
! if (__keep_end && __nsize < __old_size)
! traits_type::move(_M_data() + __nsize - __keep_end,
! _M_data() + __old_size - __keep_end, __keep_end);
! }
! else
! {
! _Rep* __r = _Rep::_S_create(__nsize, get_allocator());
! try {
! if (__keep)
! traits_type::copy(__r->_M_refdata(), _M_data(), __keep);
! if (__keep_end)
! traits_type::copy(__r->_M_refdata() + __nsize - __keep_end,
! _M_data() + __old_size - __keep_end,
! __keep_end);
! }
! catch (...) {
! __r->_M_dispose(get_allocator());
! throw;
! }
! _M_rep()->_M_dispose(get_allocator());
! _M_data(__r->_M_refdata());
! }
! _M_rep()->_M_length = __nsize;
! (_M_data())[__nsize] = _CharT(); // grrr. (per 21.3.4)
// (you cannot leave those LWG people alone for a second.)
}
--- 186,240 ----
void
basic_string<_CharT, _Traits, _Alloc>::
! _M_mutate(size_type __pos, size_type __len1, size_type __len2)
{
! const size_type __old_size = size();
! const size_type __new_size = __old_size + __len2 - __len1;
!
! if (__len1 == __len2)
! // clone if necessary
! {
! if (_M_rep()->_M_state > 0)
! {
! allocator_type __a = get_allocator();
! _CharT* __tmp = _M_rep()->_M_clone(__a);
! _M_rep()->_M_dispose(__a);
! _M_data(__tmp);
! }
! else
! _M_rep()->_M_state = 0;
! }
! else
! {
! const _CharT* __src = _M_data() + __pos + __len1;
! const size_type __how_much = __old_size - __pos - __len1;
!
! if (_M_rep()->_M_state > 0 || __new_size > capacity())
! // must reallocate
! {
! _Rep* __r = _Rep::_S_create(__new_size, get_allocator());
! try {
! if (__pos)
! traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
! if (__how_much)
! traits_type::copy(__r->_M_refdata() + __pos + __len2,
! __src,
! __how_much);
! }
! catch (...) {
! __r->_M_dispose(get_allocator());
! throw;
! }
! _M_rep()->_M_dispose(get_allocator());
! _M_data(__r->_M_refdata());
! }
! else if (__how_much)
! {
! // Work in-place
! _M_rep()->_M_state = 0;
! traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
! }
! _M_rep()->_M_length = __new_size;
! }
! _M_data()[__new_size] = _CharT(); // grrr. (per 21.3.4)
// (you cannot leave those LWG people alone for a second.)
}
*************** namespace std
*** 225,229 ****
{
if (__res_arg > this->capacity())
! _M_mutate(__res_arg, this->size(), 0);
}
--- 245,264 ----
{
if (__res_arg > this->capacity())
! {
! allocator_type __a = get_allocator();
! _Rep* __r = _Rep::_S_create(__res_arg, __a);
! size_type __old_size = this->size();
! try {
! if (__old_size)
! traits_type::copy(__r->_M_refdata(), _M_data(), __old_size);
! }
! catch (...) {
! __r->_M_dispose(__a);
! throw;
! }
! __r->_M_length = __old_size;
! _M_rep()->_M_dispose(__a);
! _M_data(__r->_M_refdata());
! }
}
*************** namespace std
*** 361,367 ****
size_type __dist_max = this->max_size();
__LENGTHERROR(__dist_max <= size_type(__dist_new));
- size_type __newlen = (this->size() - __dist_old) + __dist_new;
size_type __off = __i1 - _M_ibegin();
! _M_mutate(__newlen, __off, _M_iend() - __i2);
// Invalidated __i1, __i2
if (__dist_new)
--- 396,401 ----
size_type __dist_max = this->max_size();
__LENGTHERROR(__dist_max <= size_type(__dist_new));
size_type __off = __i1 - _M_ibegin();
! _M_mutate(__off, __dist_old, __dist_new);
// Invalidated __i1, __i2
if (__dist_new)
*************** namespace std
*** 390,395 ****
size_type __off1 = __i1 - _M_ibegin();
__LENGTHERROR(max_size() - (this->size() - __n1) <= __n2);
! size_type __newlen = (this->size() - __n1) + __n2;
! _M_mutate (__newlen, __off1, _M_iend() - __i2);
// Invalidated __i1, __i2
if (__n2)
--- 424,428 ----
size_type __off1 = __i1 - _M_ibegin();
__LENGTHERROR(max_size() - (this->size() - __n1) <= __n2);
! _M_mutate (__off1, __n1, __n2);
// Invalidated __i1, __i2
if (__n2)