1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
#include "subst.h"
#include <util/generic/strbuf.h>
#include <util/generic/string.h>
#include <util/system/compiler.h>
#include <string>
#include <type_traits>
// a bit of template magic (to be fast and unreadable)
template <class TStringType, class TTo, bool Main>
static Y_FORCE_INLINE void MoveBlock(typename TStringType::value_type* ptr, size_t& srcPos, size_t& dstPos, const size_t off, const TTo to, const size_t toSize) {
const size_t unchangedSize = off - srcPos;
if (dstPos < srcPos) {
for (size_t i = 0; i < unchangedSize; ++i) {
ptr[dstPos++] = ptr[srcPos++];
}
} else {
dstPos += unchangedSize;
srcPos += unchangedSize;
}
if (Main) {
for (size_t i = 0; i < toSize; ++i) {
ptr[dstPos++] = to[i];
}
}
}
template <typename T, typename U>
static bool IsIntersect(const T& a, const U& b) noexcept {
if (b.data() < a.data()) {
return IsIntersect(b, a);
}
return !a.empty() && !b.empty() &&
((a.data() <= b.data() && b.data() < a.data() + a.size()) ||
(a.data() < b.data() + b.size() && b.data() + b.size() <= a.data() + a.size()));
}
/**
* Replaces all occurences of substring @c from in string @c s to string @c to.
* Uses two separate implementations (inplace for shrink and append for grow case)
* See IGNIETFERRO-394
**/
template <class TStringType, typename TStringViewType = TBasicStringBuf<typename TStringType::value_type>>
static inline size_t SubstGlobalImpl(TStringType& s, const TStringViewType from, const TStringViewType to, size_t fromPos = 0) {
if (from.empty()) {
return 0;
}
Y_ASSERT(!IsIntersect(s, from));
Y_ASSERT(!IsIntersect(s, to));
const size_t fromSize = from.size();
const size_t toSize = to.size();
size_t replacementsCount = 0;
size_t off = fromPos;
size_t srcPos = 0;
if (toSize > fromSize) {
// string will grow: append to another string
TStringType result;
for (; (off = TStringViewType(s).find(from, off)) != TStringType::npos; off += fromSize) {
if (!replacementsCount) {
// first replacement occured, we can prepare result string
result.reserve(s.size() + s.size() / 3);
}
result.append(s.begin() + srcPos, s.begin() + off);
result.append(to.data(), to.size());
srcPos = off + fromSize;
++replacementsCount;
}
if (replacementsCount) {
// append tail
result.append(s.begin() + srcPos, s.end());
s = std::move(result);
}
return replacementsCount;
}
// string will not grow: use inplace algo
size_t dstPos = 0;
typename TStringType::value_type* ptr = &*s.begin();
for (; (off = TStringViewType(s).find(from, off)) != TStringType::npos; off += fromSize) {
Y_ASSERT(dstPos <= srcPos);
MoveBlock<TStringType, TStringViewType, true>(ptr, srcPos, dstPos, off, to, toSize);
srcPos = off + fromSize;
++replacementsCount;
}
if (replacementsCount) {
// append tail
MoveBlock<TStringType, TStringViewType, false>(ptr, srcPos, dstPos, s.size(), to, toSize);
s.resize(dstPos);
}
return replacementsCount;
}
/// Replaces all occurences of the 'from' symbol in a string to the 'to' symbol.
template <class TStringType>
inline size_t SubstCharGlobalImpl(TStringType& s, typename TStringType::value_type from, typename TStringType::value_type to, size_t fromPos = 0) {
if (fromPos >= s.size()) {
return 0;
}
size_t result = 0;
fromPos = s.find(from, fromPos);
// s.begin() might cause memory copying, so call it only if needed
if (fromPos != TStringType::npos) {
auto* it = &*s.begin() + fromPos;
*it = to;
++result;
// at this point string is copied and it's safe to use constant s.end() to iterate
const auto* const sEnd = &*s.end();
// unrolled loop goes first because it is more likely that `it` will be properly aligned
for (const auto* const end = sEnd - (sEnd - it) % 4; it < end;) {
if (*it == from) {
*it = to;
++result;
}
++it;
if (*it == from) {
*it = to;
++result;
}
++it;
if (*it == from) {
*it = to;
++result;
}
++it;
if (*it == from) {
*it = to;
++result;
}
++it;
}
for (; it < sEnd; ++it) {
if (*it == from) {
*it = to;
++result;
}
}
}
return result;
}
/* Standard says that `char16_t` is a distinct type and has same size, signedness and alignment as
* `std::uint_least16_t`, so we check if `char16_t` has same signedness and size as `wchar16` to be
* sure that we can make safe casts between values of these types and pointers.
*/
static_assert(sizeof(wchar16) == sizeof(char16_t), "");
static_assert(sizeof(wchar32) == sizeof(char32_t), "");
static_assert(std::is_unsigned<wchar16>::value == std::is_unsigned<char16_t>::value, "");
static_assert(std::is_unsigned<wchar32>::value == std::is_unsigned<char32_t>::value, "");
size_t SubstGlobal(TString& text, const TStringBuf what, const TStringBuf with, size_t from) {
return SubstGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(std::string& text, const TStringBuf what, const TStringBuf with, size_t from) {
return SubstGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(TUtf16String& text, const TWtringBuf what, const TWtringBuf with, size_t from) {
return SubstGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(TUtf32String& text, const TUtf32StringBuf what, const TUtf32StringBuf with, size_t from) {
return SubstGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(std::u16string& text, const TWtringBuf what, const TWtringBuf with, size_t from) {
return SubstGlobalImpl(text,
std::u16string_view(reinterpret_cast<const char16_t*>(what.data()), what.size()),
std::u16string_view(reinterpret_cast<const char16_t*>(with.data()), with.size()),
from);
}
size_t SubstGlobal(TString& text, char what, char with, size_t from) {
return SubstCharGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(std::string& text, char what, char with, size_t from) {
return SubstCharGlobalImpl(text, what, with, from);
}
size_t SubstGlobal(TUtf16String& text, wchar16 what, wchar16 with, size_t from) {
return SubstCharGlobalImpl(text, (char16_t)what, (char16_t)with, from);
}
size_t SubstGlobal(std::u16string& text, wchar16 what, wchar16 with, size_t from) {
return SubstCharGlobalImpl(text, (char16_t)what, (char16_t)with, from);
}
size_t SubstGlobal(TUtf32String& text, wchar32 what, wchar32 with, size_t from) {
return SubstCharGlobalImpl(text, (char32_t)what, (char32_t)with, from);
}
|
