1 // Copyright 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_STRINGS_STRCAT_INTERNAL_H_
6 #define BASE_STRINGS_STRCAT_INTERNAL_H_
7
8 #include <string>
9
10 #include "base/containers/span.h"
11
12 namespace base {
13
14 namespace internal {
15
16 // Reserves an additional amount of capacity in the given string, growing by at
17 // least 2x if necessary. Used by StrAppendT().
18 //
19 // The "at least 2x" growing rule duplicates the exponential growth of
20 // std::string. The problem is that most implementations of reserve() will grow
21 // exactly to the requested amount instead of exponentially growing like would
22 // happen when appending normally. If we didn't do this, an append after the
23 // call to StrAppend() would definitely cause a reallocation, and loops with
24 // StrAppend() calls would have O(n^2) complexity to execute. Instead, we want
25 // StrAppend() to have the same semantics as std::string::append().
26 template <typename String>
ReserveAdditionalIfNeeded(String * str,typename String::size_type additional)27 void ReserveAdditionalIfNeeded(String* str,
28 typename String::size_type additional) {
29 const size_t required = str->size() + additional;
30 // Check whether we need to reserve additional capacity at all.
31 if (required <= str->capacity())
32 return;
33
34 str->reserve(std::max(required, str->capacity() * 2));
35 }
36
37 template <typename DestString, typename InputString>
StrAppendT(DestString * dest,span<const InputString> pieces)38 void StrAppendT(DestString* dest, span<const InputString> pieces) {
39 size_t additional_size = 0;
40 for (const auto& cur : pieces)
41 additional_size += cur.size();
42 ReserveAdditionalIfNeeded(dest, additional_size);
43
44 for (const auto& cur : pieces)
45 dest->append(cur.data(), cur.size());
46 }
47
48 template <typename StringT>
StrCatT(span<const StringT> pieces)49 auto StrCatT(span<const StringT> pieces) {
50 std::basic_string<typename StringT::value_type, typename StringT::traits_type>
51 result;
52 StrAppendT(&result, pieces);
53 return result;
54 }
55
56 } // namespace internal
57
58 } // namespace base
59
60 #endif // BASE_STRINGS_STRCAT_INTERNAL_H_
61