basic_string<>::_M_mutate - patch

Ryszard Kabatek rysio@rumcajs.chemie.uni-halle.de
Mon Jun 28 02:20:00 GMT 1999


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


More information about the Libstdc++ mailing list