basic_string.h (insert(__pos, __s, __n)): Optimize by avoiding temporaries and working in-place when possible.

2001-12-28  Paolo Carlini  <pcarlini@unitus.it>
            Nathan Myers  <ncm@cantrip.org>

	* include/bits/basic_string.h (insert(__pos, __s, __n)):
	Optimize by avoiding temporaries and working in-place when possible.
	(insert(__pos1, __str)): Call insert(__pos1, __str, __pos2, __n).
	(insert(__pos1, __str, __pos2, __n)): Call insert(__pos, __s, __n).
	* testsuite/21_strings/insert.cc (test02): New testcases.

Co-Authored-By: Nathan Myers <ncm@cantrip.org>

From-SVN: r48345

3 files changed, 106 insertions, 15 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 2be936a..af9d997 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,12 @@
+2001-12-28  Paolo Carlini  <pcarlini@unitus.it>
+            Nathan Myers  <ncm@cantrip.org>
+
+	* include/bits/basic_string.h (insert(__pos, __s, __n)):
+	Optimize by avoiding temporaries and working in-place when possible.
+	(insert(__pos1, __str)): Call insert(__pos1, __str, __pos2, __n).
+	(insert(__pos1, __str, __pos2, __n)): Call insert(__pos, __s, __n).
+	* testsuite/21_strings/insert.cc (test02): New testcases.
+
 2001-12-27  Phil Edwards  <pme@gcc.gnu.org>
 
 	* testsuite/testsuite_hooks.h (gnu_counting_struct):  Add.
diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h
index 170fdcd..d25d9de 100644
--- a/libstdc++-v3/include/bits/basic_string.h
+++ b/libstdc++-v3/include/bits/basic_string.h
@@ -531,29 +531,53 @@ namespace std
 
       basic_string& 
       insert(size_type __pos1, const basic_string& __str)
-      { 
-	iterator __p = _M_check(__pos1);
-	this->replace(__p, __p, __str._M_ibegin(), __str._M_iend());
-        return *this; 
-      }
+      { return this->insert(__pos1, __str, 0, __str.size()); }
 
       basic_string& 
       insert(size_type __pos1, const basic_string& __str,
 	     size_type __pos2, size_type __n)
-      { 
-	iterator __p = _M_check(__pos1);
-	this->replace(__p, __p, __str._M_check(__pos2), 
-		      __str._M_fold(__pos2, __n));
-        return *this; 
+      {
+	const size_type __strsize = __str.size();
+ 	if (__pos2 > __strsize)
+	  __throw_out_of_range("basic_string::insert");
+	const bool __testn = __n < __strsize - __pos2;
+	const size_type __newsize = __testn ? __n : __strsize - __pos2;
+	return this->insert(__pos1, __str._M_data() + __pos2, __newsize); 
       }
 
       basic_string& 
       insert(size_type __pos, const _CharT* __s, size_type __n)
-      { 
-	iterator __p = _M_check(__pos);
-	this->replace(__p, __p, __s, __s + __n);
-        return *this; 
-      }
+      {
+	const size_type __size = this->size();
+ 	if (__pos > __size)
+	  __throw_out_of_range("basic_string::insert");
+	if (__n + __size > this->max_size())
+	  __throw_length_error("basic_string::insert");
+	if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
+	    || less<const _CharT*>()(_M_data() + __size, __s))
+	  return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
+				 __s, __s + __n);
+	else
+	  {
+	    // Work in-place. If _M_mutate reallocates the string, __s
+	    // does not point anymore to valid data, therefore we save its
+	    // offset, then we restore it.
+	    const size_type __off = __s - _M_data();
+	    _M_mutate(__pos, 0, __n);
+	    __s = _M_data() + __off;
+	    _CharT* __p = _M_data() + __pos;
+	    if (__s  + __n <= __p)
+	      traits_type::copy(__p, __s, __n);
+	    else if (__s >= __p)
+	      traits_type::copy(__p, __s + __n, __n);
+	    else
+	      {
+		traits_type::copy(__p, __s, __p - __s);
+		traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s));
+	      }
+	    return *this;
+	  }
+       }
 
       basic_string&  
       insert(size_type __pos, const _CharT* __s)
diff --git a/libstdc++-v3/testsuite/21_strings/insert.cc b/libstdc++-v3/testsuite/21_strings/insert.cc
index 3c8dff0..e6140ac 100644
--- a/libstdc++-v3/testsuite/21_strings/insert.cc
+++ b/libstdc++-v3/testsuite/21_strings/insert.cc
@@ -187,9 +187,67 @@ int test01(void)
   return test;
 }
 
+// Once more
+//   string& insert(size_type __p, const char* s, size_type n);
+//   string& insert(size_type __p, const char* s);
+// but now s points inside the _Rep
+int test02(void)
+{
+  bool test = true;
+
+  std::string str01;
+  const char* title = "Everything was beautiful, and nothing hurt";
+  // Increasing size: str01 is reallocated every time.
+  str01 = title;
+  str01.insert(0, str01.c_str() + str01.size() - 4, 4);
+  VERIFY( str01 == "hurtEverything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(0, str01.c_str(), 5);
+  VERIFY( str01 == "EveryEverything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(10, str01.c_str() + 4, 6);
+  VERIFY( str01 == "Everythingything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(15, str01.c_str(), 10);
+  VERIFY( str01 == "Everything was Everythingbeautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(15, str01.c_str() + 11, 13);
+  VERIFY( str01 == "Everything was was beautifulbeautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(0, str01.c_str());
+  VERIFY( str01 == "Everything was beautiful, and nothing hurt"
+	  "Everything was beautiful, and nothing hurt");
+  // Again: no reallocations.
+  str01 = title;
+  str01.insert(0, str01.c_str() + str01.size() - 4, 4);
+  VERIFY( str01 == "hurtEverything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(0, str01.c_str(), 5);
+  VERIFY( str01 == "EveryEverything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(10, str01.c_str() + 4, 6);
+  VERIFY( str01 == "Everythingything was beautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(15, str01.c_str(), 10);
+  VERIFY( str01 == "Everything was Everythingbeautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(15, str01.c_str() + 11, 13);
+  VERIFY( str01 == "Everything was was beautifulbeautiful, and nothing hurt" );
+  str01 = title;
+  str01.insert(0, str01.c_str());
+  VERIFY( str01 == "Everything was beautiful, and nothing hurt"
+	  "Everything was beautiful, and nothing hurt");
+
+#ifdef DEBUG_ASSERT
+  assert(test);
+#endif
+  return test;
+}
+
 int main()
 { 
   __set_testsuite_memlimit();
   test01();
+  test02();
   return 0;
 }