1 // Copyright 2017 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 #include "base/strings/strcat.h"
6
7 namespace base {
8
9 namespace {
10
11 // Reserves an additional amount of size in the given string, growing by at
12 // least 2x. Used by StrAppend().
13 //
14 // The "at least 2x" growing rule duplicates the exponential growth of
15 // std::string. The problem is that most implementations of reserve() will grow
16 // exactly to the requested amount instead of exponentially growing like would
17 // happen when appending normally. If we didn't do this, an append after the
18 // call to StrAppend() would definitely cause a reallocation, and loops with
19 // StrAppend() calls would have O(n^2) complexity to execute. Instead, we want
20 // StrAppend() to have the same semantics as std::string::append().
21 //
22 // If the string is empty, we assume that exponential growth is not necessary.
23 template <typename String>
ReserveAdditional(String * str,typename String::size_type additional)24 void ReserveAdditional(String* str, typename String::size_type additional) {
25 str->reserve(std::max(str->size() + additional, str->size() * 2));
26 }
27
28 template <typename DestString, typename InputString>
StrAppendT(DestString * dest,span<const InputString> pieces)29 void StrAppendT(DestString* dest, span<const InputString> pieces) {
30 size_t additional_size = 0;
31 for (const auto& cur : pieces)
32 additional_size += cur.size();
33 ReserveAdditional(dest, additional_size);
34
35 for (const auto& cur : pieces)
36 dest->append(cur.data(), cur.size());
37 }
38
39 } // namespace
40
StrCat(span<const StringPiece> pieces)41 std::string StrCat(span<const StringPiece> pieces) {
42 std::string result;
43 StrAppendT(&result, pieces);
44 return result;
45 }
46
StrCat(span<const StringPiece16> pieces)47 string16 StrCat(span<const StringPiece16> pieces) {
48 string16 result;
49 StrAppendT(&result, pieces);
50 return result;
51 }
52
StrCat(span<const std::string> pieces)53 std::string StrCat(span<const std::string> pieces) {
54 std::string result;
55 StrAppendT(&result, pieces);
56 return result;
57 }
58
StrCat(span<const string16> pieces)59 string16 StrCat(span<const string16> pieces) {
60 string16 result;
61 StrAppendT(&result, pieces);
62 return result;
63 }
64
StrAppend(std::string * dest,span<const StringPiece> pieces)65 void StrAppend(std::string* dest, span<const StringPiece> pieces) {
66 StrAppendT(dest, pieces);
67 }
68
StrAppend(string16 * dest,span<const StringPiece16> pieces)69 void StrAppend(string16* dest, span<const StringPiece16> pieces) {
70 StrAppendT(dest, pieces);
71 }
72
StrAppend(std::string * dest,span<const std::string> pieces)73 void StrAppend(std::string* dest, span<const std::string> pieces) {
74 StrAppendT(dest, pieces);
75 }
76
StrAppend(string16 * dest,span<const string16> pieces)77 void StrAppend(string16* dest, span<const string16> pieces) {
78 StrAppendT(dest, pieces);
79 }
80
81 } // namespace base
82