[v3] libstdc++/28277: collate bits

[Paolo Carlini <pcarlini at suse dot de>]

Hi,

tested x86-linux, committed to mainline.

Paolo.

///////////////////
2006-07-11  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/28277 (partial: collate bits)
	* include/bits/locale_facets.tcc (collate<>::do_transform(
	const _CharT*, const _CharT*)): Avoid __builtin_alloca with no
	limit; also avoid multiple calls (in a loop).
	* testsuite/22_locale/collate/transform/char/28277.cc: New.
	* testsuite/22_locale/collate/transform/wchar_t/28277.cc: Likewise.

Index: include/bits/locale_facets.tcc
===================================================================
--- include/bits/locale_facets.tcc	(revision 115298)
+++ include/bits/locale_facets.tcc	(working copy)
@@ -2455,43 +2455,62 @@
     collate<_CharT>::
     do_transform(const _CharT* __lo, const _CharT* __hi) const
     {
-      // strxfrm assumes zero-terminated strings so we make a copy
-      string_type __str(__lo, __hi);
+      string_type __ret;
 
-      const _CharT* __p = __str.c_str();
-      const _CharT* __pend = __str.data() + __str.length();
+      // Use alloca for an _M_transform temporary buffer up to an arbitrary,
+      // but limited, asize, to avoid abusing the stack.  Otherwise fall back
+      // to dynamic memory allocation.  This means splitting the computation
+      // itself in hunks:  a size <= 8k (thus <= 16k asize) appear sufficient
+      // for optimal performance.
+      const size_t __size = std::min(size_t(__hi - __lo), size_t(8192));
+      const size_t __asize = 2 * __size;
 
-      size_t __len = (__hi - __lo) * 2;
+      size_t __len = __asize;
 
-      string_type __ret;
+      _CharT* __c =
+	static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT) * __len));
 
-      // strxfrm stops when it sees a nul character so we break
-      // the string into zero-terminated substrings and pass those
-      // to strxfrm.
-      for (;;)
+      for (size_t __hunk = __size; __lo < __hi;
+	   __lo += __hunk, __hunk = std::min(size_t(__hi - __lo), __hunk))
 	{
-	  // First try a buffer perhaps big enough.
-	  _CharT* __c =
-	    static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT) * __len));
-	  size_t __res = _M_transform(__c, __p, __len);
-	  // If the buffer was not large enough, try again with the
-	  // correct size.
-	  if (__res >= __len)
+	  // strxfrm assumes zero-terminated strings so we make a copy
+	  const string_type __str(__lo, __lo + __hunk);
+
+	  const _CharT* __p = __str.c_str();
+	  const _CharT* __pend = __str.data() + __hunk;
+
+	  // strxfrm stops when it sees a nul character so we break
+	  // the string into zero-terminated substrings and pass those
+	  // to strxfrm.
+	  for (;;)
 	    {
-	      __len = __res + 1;
-	      __c = static_cast<_CharT*>(__builtin_alloca(sizeof(_CharT)
-							  * __len));
-	      __res = _M_transform(__c, __p, __len);
+	      // First try a buffer perhaps big enough.
+	      size_t __res = _M_transform(__c, __p, __len);
+	      // If the buffer was not large enough, try again with the
+	      // correct size.
+	      if (__res >= __len)
+		{
+		  if (__len > __asize)
+		    delete [] __c;
+		  __len = __res + 1;
+		  __c = new _CharT[__len];
+		  __res = _M_transform(__c, __p, __len);
+		}
+
+	      __ret.append(__c, __res);
+	      __p += char_traits<_CharT>::length(__p);
+	      if (__p == __pend)
+		break;
+
+	      __p++;
+	      __ret.push_back(_CharT());
 	    }
+	}
 
-	  __ret.append(__c, __res);
-	  __p += char_traits<_CharT>::length(__p);
-	  if (__p == __pend)
-	    return __ret;
+      if (__len > __asize)
+	delete [] __c;
 
-	  __p++;
-	  __ret.push_back(_CharT());
-	}
+      return __ret;
     }
 
   template<typename _CharT>
Index: testsuite/22_locale/collate/transform/wchar_t/28277.cc
===================================================================
--- testsuite/22_locale/collate/transform/wchar_t/28277.cc	(revision 0)
+++ testsuite/22_locale/collate/transform/wchar_t/28277.cc	(revision 0)
@@ -0,0 +1,52 @@
+// 2006-07-11  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2006 Free Software Foundation
+//
+// 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 22.2.4.1.1 collate members
+
+#include <locale>
+#include <testsuite_hooks.h>
+
+// libstdc++/28277
+void test01()
+{
+  using namespace std;
+  typedef collate<wchar_t>::string_type string_type;
+
+  bool test __attribute__((unused)) = true;
+
+  // basic construction
+  locale loc_c = locale::classic();
+
+  // cache the collate facets
+  const collate<wchar_t>& coll_c = use_facet<collate<wchar_t> >(loc_c); 
+
+  const string_type sstr(10000000, L'a');
+
+  const string_type dstr = coll_c.transform(sstr.data(),
+					    sstr.data() + sstr.size());
+
+  VERIFY( dstr == sstr );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/22_locale/collate/transform/char/28277.cc
===================================================================
--- testsuite/22_locale/collate/transform/char/28277.cc	(revision 0)
+++ testsuite/22_locale/collate/transform/char/28277.cc	(revision 0)
@@ -0,0 +1,52 @@
+// 2006-07-11  Paolo Carlini  <pcarlini@suse.de>
+
+// Copyright (C) 2006 Free Software Foundation
+//
+// 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 22.2.4.1.1 collate members
+
+#include <locale>
+#include <testsuite_hooks.h>
+
+// libstdc++/28277
+void test01()
+{
+  using namespace std;
+  typedef collate<char>::string_type string_type;
+
+  bool test __attribute__((unused)) = true;
+
+  // basic construction
+  locale loc_c = locale::classic();
+
+  // cache the collate facets
+  const collate<char>& coll_c = use_facet<collate<char> >(loc_c); 
+
+  const string_type sstr(10000000, 'a');
+
+  const string_type dstr = coll_c.transform(sstr.data(),
+					    sstr.data() + sstr.size());
+
+  VERIFY( dstr == sstr );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}