summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2021-09-24 10:32:31 -0700
committerGravatar vslashg <gfalcon@google.com>2021-09-27 12:02:32 -0400
commitb1b63f7aa8467ff5c2fc81231f6ec69fe93ca3b0 (patch)
tree8700c8b71de5d1e1beeb3a3a6415fd8253148f44 /absl
parent1ce4ceca2b2931bc4d7e470228c2dbb2f3dfea0f (diff)
Export of internal Abseil changes
-- d6f0dab708b123a5e24b98da1de0b11e36a7a86e by Evan Brown <ezb@google.com>: In STLStringResizeUninitializedAmortized, use basic_string::__append_default_init for amortized growth rather than conditionally adding reserve in STLStringReserveAmortized. This way, we can avoid extra branches, e.g. in basic_string::__shrink_or_extend. PiperOrigin-RevId: 398761382 GitOrigin-RevId: d6f0dab708b123a5e24b98da1de0b11e36a7a86e Change-Id: Ib2d99411c95d61300519c32b885ce586b410c3bf
Diffstat (limited to 'absl')
-rw-r--r--absl/strings/internal/resize_uninitialized.h31
-rw-r--r--absl/strings/internal/resize_uninitialized_test.cc40
2 files changed, 61 insertions, 10 deletions
diff --git a/absl/strings/internal/resize_uninitialized.h b/absl/strings/internal/resize_uninitialized.h
index 749c66e7..49859dcc 100644
--- a/absl/strings/internal/resize_uninitialized.h
+++ b/absl/strings/internal/resize_uninitialized.h
@@ -29,8 +29,9 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace strings_internal {
-// Is a subclass of true_type or false_type, depending on whether or not
-// T has a __resize_default_init member.
+// In this type trait, we look for a __resize_default_init member function, and
+// we use it if available, otherwise, we use resize. We provide HasMember to
+// indicate whether __resize_default_init is present.
template <typename string_type, typename = void>
struct ResizeUninitializedTraits {
using HasMember = std::false_type;
@@ -79,14 +80,36 @@ void STLStringReserveAmortized(string_type* s, size_t new_size) {
}
}
+// In this type trait, we look for an __append_default_init member function, and
+// we use it if available, otherwise, we use append.
+template <typename string_type, typename = void>
+struct AppendUninitializedTraits {
+ static void Append(string_type* s, size_t n) {
+ s->append(n, typename string_type::value_type());
+ }
+};
+
+template <typename string_type>
+struct AppendUninitializedTraits<
+ string_type, absl::void_t<decltype(std::declval<string_type&>()
+ .__append_default_init(237))> > {
+ static void Append(string_type* s, size_t n) {
+ s->__append_default_init(n);
+ }
+};
+
// Like STLStringResizeUninitialized(str, new_size), except guaranteed to use
// exponential growth so that the amortized complexity of increasing the string
// size by a small amount is O(1), in contrast to O(str->size()) in the case of
// precise growth.
template <typename string_type>
void STLStringResizeUninitializedAmortized(string_type* s, size_t new_size) {
- STLStringReserveAmortized(s, new_size);
- STLStringResizeUninitialized(s, new_size);
+ const size_t size = s->size();
+ if (new_size > size) {
+ AppendUninitializedTraits<string_type>::Append(s, new_size - size);
+ } else {
+ s->erase(new_size);
+ }
}
} // namespace strings_internal
diff --git a/absl/strings/internal/resize_uninitialized_test.cc b/absl/strings/internal/resize_uninitialized_test.cc
index 01ee476b..ad1b9c58 100644
--- a/absl/strings/internal/resize_uninitialized_test.cc
+++ b/absl/strings/internal/resize_uninitialized_test.cc
@@ -19,10 +19,12 @@
namespace {
int resize_call_count = 0;
+int append_call_count = 0;
// A mock string class whose only purpose is to track how many times its
-// resize() method has been called.
+// resize()/append() methods have been called.
struct resizable_string {
+ using value_type = char;
size_t size() const { return 0; }
size_t capacity() const { return 0; }
char& operator[](size_t) {
@@ -30,14 +32,18 @@ struct resizable_string {
return c;
}
void resize(size_t) { resize_call_count += 1; }
+ void append(size_t, value_type) { append_call_count += 1; }
void reserve(size_t) {}
+ resizable_string& erase(size_t = 0, size_t = 0) { return *this; }
};
int resize_default_init_call_count = 0;
+int append_default_init_call_count = 0;
// A mock string class whose only purpose is to track how many times its
-// resize() and __resize_default_init() methods have been called.
-struct resize_default_init_string {
+// resize()/__resize_default_init()/append()/__append_default_init() methods
+// have been called.
+struct default_init_string {
size_t size() const { return 0; }
size_t capacity() const { return 0; }
char& operator[](size_t) {
@@ -46,46 +52,68 @@ struct resize_default_init_string {
}
void resize(size_t) { resize_call_count += 1; }
void __resize_default_init(size_t) { resize_default_init_call_count += 1; }
+ void __append_default_init(size_t) { append_default_init_call_count += 1; }
void reserve(size_t) {}
+ default_init_string& erase(size_t = 0, size_t = 0) { return *this; }
};
TEST(ResizeUninit, WithAndWithout) {
resize_call_count = 0;
+ append_call_count = 0;
resize_default_init_call_count = 0;
+ append_default_init_call_count = 0;
{
resizable_string rs;
EXPECT_EQ(resize_call_count, 0);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
EXPECT_FALSE(
absl::strings_internal::STLStringSupportsNontrashingResize(&rs));
EXPECT_EQ(resize_call_count, 0);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
absl::strings_internal::STLStringResizeUninitialized(&rs, 237);
EXPECT_EQ(resize_call_count, 1);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
absl::strings_internal::STLStringResizeUninitializedAmortized(&rs, 1000);
- EXPECT_EQ(resize_call_count, 2);
+ EXPECT_EQ(resize_call_count, 1);
+ EXPECT_EQ(append_call_count, 1);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
}
resize_call_count = 0;
+ append_call_count = 0;
resize_default_init_call_count = 0;
+ append_default_init_call_count = 0;
{
- resize_default_init_string rus;
+ default_init_string rus;
EXPECT_EQ(resize_call_count, 0);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
EXPECT_TRUE(
absl::strings_internal::STLStringSupportsNontrashingResize(&rus));
EXPECT_EQ(resize_call_count, 0);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 0);
+ EXPECT_EQ(append_default_init_call_count, 0);
absl::strings_internal::STLStringResizeUninitialized(&rus, 237);
EXPECT_EQ(resize_call_count, 0);
+ EXPECT_EQ(append_call_count, 0);
EXPECT_EQ(resize_default_init_call_count, 1);
+ EXPECT_EQ(append_default_init_call_count, 0);
absl::strings_internal::STLStringResizeUninitializedAmortized(&rus, 1000);
EXPECT_EQ(resize_call_count, 0);
- EXPECT_EQ(resize_default_init_call_count, 2);
+ EXPECT_EQ(append_call_count, 0);
+ EXPECT_EQ(resize_default_init_call_count, 1);
+ EXPECT_EQ(append_default_init_call_count, 1);
}
}