TLA Line data Source code
1 : //
2 : // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3 : // Copyright (c) 2020 Krystian Stasiowski (sdkrystian@gmail.com)
4 : //
5 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
6 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 : //
8 : // Official repository: https://github.com/boostorg/json
9 : //
10 :
11 : #ifndef BOOST_JSON_DETAIL_IMPL_STRING_IMPL_IPP
12 : #define BOOST_JSON_DETAIL_IMPL_STRING_IMPL_IPP
13 :
14 : #include <boost/json/detail/string_impl.hpp>
15 : #include <boost/json/detail/except.hpp>
16 : #include <cstring>
17 : #include <functional>
18 :
19 : namespace boost {
20 : namespace json {
21 : namespace detail {
22 :
23 HIT 30961 : string_impl::
24 30961 : string_impl() noexcept
25 : {
26 30961 : s_.k = short_string_;
27 30961 : s_.buf[sbo_chars_] =
28 : static_cast<char>(
29 : sbo_chars_);
30 30961 : s_.buf[0] = 0;
31 30961 : }
32 :
33 26932 : string_impl::
34 : string_impl(
35 : std::size_t size,
36 26932 : storage_ptr const& sp)
37 : {
38 26932 : if(size <= sbo_chars_)
39 : {
40 41 : s_.k = short_string_;
41 41 : s_.buf[sbo_chars_] =
42 : static_cast<char>(
43 41 : sbo_chars_ - size);
44 41 : s_.buf[size] = 0;
45 : }
46 : else
47 : {
48 26891 : s_.k = kind::string;
49 26891 : auto const n = growth(
50 : size, sbo_chars_ + 1);
51 26891 : p_.t = ::new(sp->allocate(
52 : sizeof(table) +
53 26891 : n + 1,
54 : alignof(table))) table{
55 : static_cast<
56 : std::uint32_t>(size),
57 : static_cast<
58 26696 : std::uint32_t>(n)};
59 26696 : data()[n] = 0;
60 : }
61 26737 : }
62 :
63 : // construct a key, unchecked
64 30296 : string_impl::
65 : string_impl(
66 : key_t,
67 : string_view s,
68 30296 : storage_ptr const& sp)
69 : {
70 30296 : BOOST_ASSERT(
71 : s.size() <= max_size());
72 30296 : k_.k = key_string_;
73 30296 : k_.n = static_cast<
74 30296 : std::uint32_t>(s.size());
75 30236 : k_.s = reinterpret_cast<char*>(
76 30296 : sp->allocate(s.size() + 1,
77 : alignof(char)));
78 30236 : k_.s[s.size()] = 0; // null term
79 30236 : std::memcpy(&k_.s[0],
80 30236 : s.data(), s.size());
81 30236 : }
82 :
83 : // construct a key, unchecked
84 8060 : string_impl::
85 : string_impl(
86 : key_t,
87 : string_view s1,
88 : string_view s2,
89 8060 : storage_ptr const& sp)
90 : {
91 8060 : auto len = s1.size() + s2.size();
92 8060 : BOOST_ASSERT(len <= max_size());
93 8060 : k_.k = key_string_;
94 8060 : k_.n = static_cast<
95 : std::uint32_t>(len);
96 8060 : k_.s = reinterpret_cast<char*>(
97 8060 : sp->allocate(len + 1,
98 : alignof(char)));
99 8060 : k_.s[len] = 0; // null term
100 8060 : std::memcpy(&k_.s[0],
101 8060 : s1.data(), s1.size());
102 16120 : std::memcpy(&k_.s[s1.size()],
103 8060 : s2.data(), s2.size());
104 8060 : }
105 :
106 : std::uint32_t
107 53776 : string_impl::
108 : growth(
109 : std::size_t new_size,
110 : std::size_t capacity)
111 : {
112 53776 : if(new_size > max_size())
113 : {
114 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
115 1 : detail::throw_system_error( error::string_too_large, &loc );
116 : }
117 : // growth factor 2
118 53775 : if( capacity >
119 53775 : max_size() - capacity)
120 : return static_cast<
121 MIS 0 : std::uint32_t>(max_size()); // overflow
122 : return static_cast<std::uint32_t>(
123 HIT 53775 : (std::max)(capacity * 2, new_size));
124 : }
125 :
126 : char*
127 18470 : string_impl::
128 : assign(
129 : std::size_t new_size,
130 : storage_ptr const& sp)
131 : {
132 18470 : if(new_size > capacity())
133 : {
134 17111 : string_impl tmp(growth(
135 : new_size,
136 17111 : capacity()), sp);
137 16967 : destroy(sp);
138 16967 : *this = tmp;
139 : }
140 18326 : term(new_size);
141 18326 : return data();
142 : }
143 :
144 : char*
145 224 : string_impl::
146 : append(
147 : std::size_t n,
148 : storage_ptr const& sp)
149 : {
150 224 : if(n > max_size() - size())
151 : {
152 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
153 1 : detail::throw_system_error( error::string_too_large, &loc );
154 : }
155 223 : if(n <= capacity() - size())
156 : {
157 167 : term(size() + n);
158 167 : return end() - n;
159 : }
160 112 : string_impl tmp(growth(
161 112 : size() + n, capacity()), sp);
162 33 : std::memcpy(
163 33 : tmp.data(), data(), size());
164 33 : tmp.term(size() + n);
165 33 : destroy(sp);
166 33 : *this = tmp;
167 33 : return end() - n;
168 : }
169 :
170 : void
171 27 : string_impl::
172 : insert(
173 : std::size_t pos,
174 : const char* s,
175 : std::size_t n,
176 : storage_ptr const& sp)
177 : {
178 27 : const auto curr_size = size();
179 27 : if(pos > curr_size)
180 : {
181 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
182 2 : detail::throw_system_error( error::out_of_range, &loc );
183 : }
184 25 : const auto curr_data = data();
185 25 : if(n <= capacity() - curr_size)
186 : {
187 10 : const bool inside = detail::ptr_in_range(curr_data, curr_data + curr_size, s);
188 10 : if (!inside || (inside && ((s - curr_data) + n <= pos)))
189 : {
190 8 : std::memmove(&curr_data[pos + n], &curr_data[pos], curr_size - pos + 1);
191 8 : std::memcpy(&curr_data[pos], s, n);
192 : }
193 : else
194 : {
195 2 : const std::size_t offset = s - curr_data;
196 2 : std::memmove(&curr_data[pos + n], &curr_data[pos], curr_size - pos + 1);
197 2 : if (offset < pos)
198 : {
199 1 : const std::size_t diff = pos - offset;
200 1 : std::memcpy(&curr_data[pos], &curr_data[offset], diff);
201 1 : std::memcpy(&curr_data[pos + diff], &curr_data[pos + n], n - diff);
202 : }
203 : else
204 : {
205 1 : std::memcpy(&curr_data[pos], &curr_data[offset + n], n);
206 : }
207 : }
208 10 : size(curr_size + n);
209 : }
210 : else
211 : {
212 15 : if(n > max_size() - curr_size)
213 : {
214 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
215 1 : detail::throw_system_error( error::string_too_large, &loc );
216 : }
217 14 : string_impl tmp(growth(
218 14 : curr_size + n, capacity()), sp);
219 7 : tmp.size(curr_size + n);
220 7 : std::memcpy(
221 7 : tmp.data(),
222 : curr_data,
223 : pos);
224 14 : std::memcpy(
225 14 : tmp.data() + pos + n,
226 : curr_data + pos,
227 7 : curr_size + 1 - pos);
228 7 : std::memcpy(
229 7 : tmp.data() + pos,
230 : s,
231 : n);
232 7 : destroy(sp);
233 7 : *this = tmp;
234 : }
235 17 : }
236 :
237 : char*
238 17 : string_impl::
239 : insert_unchecked(
240 : std::size_t pos,
241 : std::size_t n,
242 : storage_ptr const& sp)
243 : {
244 17 : const auto curr_size = size();
245 17 : if(pos > curr_size)
246 : {
247 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
248 1 : detail::throw_system_error( error::out_of_range, &loc );
249 : }
250 16 : const auto curr_data = data();
251 16 : if(n <= capacity() - size())
252 : {
253 5 : auto const dest =
254 : curr_data + pos;
255 5 : std::memmove(
256 : dest + n,
257 : dest,
258 5 : curr_size + 1 - pos);
259 5 : size(curr_size + n);
260 5 : return dest;
261 : }
262 11 : if(n > max_size() - curr_size)
263 : {
264 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
265 1 : detail::throw_system_error( error::string_too_large, &loc );
266 : }
267 10 : string_impl tmp(growth(
268 10 : curr_size + n, capacity()), sp);
269 5 : tmp.size(curr_size + n);
270 5 : std::memcpy(
271 5 : tmp.data(),
272 : curr_data,
273 : pos);
274 10 : std::memcpy(
275 10 : tmp.data() + pos + n,
276 : curr_data + pos,
277 5 : curr_size + 1 - pos);
278 5 : destroy(sp);
279 5 : *this = tmp;
280 5 : return data() + pos;
281 : }
282 :
283 : void
284 19 : string_impl::
285 : replace(
286 : std::size_t pos,
287 : std::size_t n1,
288 : const char* s,
289 : std::size_t n2,
290 : storage_ptr const& sp)
291 : {
292 19 : const auto curr_size = size();
293 19 : if (pos > curr_size)
294 : {
295 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
296 1 : detail::throw_system_error( error::out_of_range, &loc );
297 : }
298 18 : const auto curr_data = data();
299 18 : n1 = (std::min)(n1, curr_size - pos);
300 18 : const auto delta = (std::max)(n1, n2) -
301 18 : (std::min)(n1, n2);
302 : // if we are shrinking in size or we have enough
303 : // capacity, dont reallocate
304 18 : if (n1 > n2 || delta <= capacity() - curr_size)
305 : {
306 13 : const bool inside = detail::ptr_in_range(curr_data, curr_data + curr_size, s);
307 : // there is nothing to replace; return
308 13 : if (inside && s == curr_data + pos && n1 == n2)
309 1 : return;
310 12 : if (!inside || (inside && ((s - curr_data) + n2 <= pos)))
311 : {
312 : // source outside
313 6 : std::memmove(&curr_data[pos + n2], &curr_data[pos + n1], curr_size - pos - n1 + 1);
314 6 : std::memcpy(&curr_data[pos], s, n2);
315 : }
316 : else
317 : {
318 : // source inside
319 6 : const std::size_t offset = s - curr_data;
320 6 : if (n2 >= n1)
321 : {
322 : // grow/unchanged
323 4 : const std::size_t diff = offset <= pos + n1 ? (std::min)((pos + n1) - offset, n2) : 0;
324 : // shift all right of splice point by n2 - n1 to the right
325 4 : std::memmove(&curr_data[pos + n2], &curr_data[pos + n1], curr_size - pos - n1 + 1);
326 : // copy all before splice point
327 4 : std::memmove(&curr_data[pos], &curr_data[offset], diff);
328 : // copy all after splice point
329 4 : std::memmove(&curr_data[pos + diff], &curr_data[(offset - n1) + n2 + diff], n2 - diff);
330 : }
331 : else
332 : {
333 : // shrink
334 : // copy all elements into place
335 2 : std::memmove(&curr_data[pos], &curr_data[offset], n2);
336 : // shift all elements after splice point left
337 2 : std::memmove(&curr_data[pos + n2], &curr_data[pos + n1], curr_size - pos - n1 + 1);
338 : }
339 : }
340 12 : size((curr_size - n1) + n2);
341 : }
342 : else
343 : {
344 5 : if (delta > max_size() - curr_size)
345 : {
346 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
347 1 : detail::throw_system_error( error::string_too_large, &loc );
348 : }
349 : // would exceed capacity, reallocate
350 4 : string_impl tmp(growth(
351 4 : curr_size + delta, capacity()), sp);
352 2 : tmp.size(curr_size + delta);
353 2 : std::memcpy(
354 2 : tmp.data(),
355 : curr_data,
356 : pos);
357 4 : std::memcpy(
358 4 : tmp.data() + pos + n2,
359 2 : curr_data + pos + n1,
360 2 : curr_size - pos - n1 + 1);
361 4 : std::memcpy(
362 2 : tmp.data() + pos,
363 : s,
364 : n2);
365 2 : destroy(sp);
366 2 : *this = tmp;
367 : }
368 : }
369 :
370 : // unlike the replace overload, this function does
371 : // not move any characters
372 : char*
373 11 : string_impl::
374 : replace_unchecked(
375 : std::size_t pos,
376 : std::size_t n1,
377 : std::size_t n2,
378 : storage_ptr const& sp)
379 : {
380 11 : const auto curr_size = size();
381 11 : if(pos > curr_size)
382 : {
383 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
384 1 : detail::throw_system_error( error::out_of_range, &loc );
385 : }
386 10 : const auto curr_data = data();
387 10 : n1 = (std::min)(n1, curr_size - pos);
388 10 : const auto delta = (std::max)(n1, n2) -
389 10 : (std::min)(n1, n2);
390 : // if the size doesn't change, we don't need to
391 : // do anything
392 10 : if (!delta)
393 1 : return curr_data + pos;
394 : // if we are shrinking in size or we have enough
395 : // capacity, dont reallocate
396 9 : if(n1 > n2 || delta <= capacity() - curr_size)
397 : {
398 4 : auto const replace_pos = curr_data + pos;
399 4 : std::memmove(
400 4 : replace_pos + n2,
401 4 : replace_pos + n1,
402 4 : curr_size - pos - n1 + 1);
403 4 : size((curr_size - n1) + n2);
404 4 : return replace_pos;
405 : }
406 5 : if(delta > max_size() - curr_size)
407 : {
408 : BOOST_STATIC_CONSTEXPR source_location loc = BOOST_CURRENT_LOCATION;
409 1 : detail::throw_system_error( error::string_too_large, &loc );
410 : }
411 : // would exceed capacity, reallocate
412 4 : string_impl tmp(growth(
413 4 : curr_size + delta, capacity()), sp);
414 2 : tmp.size(curr_size + delta);
415 2 : std::memcpy(
416 2 : tmp.data(),
417 : curr_data,
418 : pos);
419 4 : std::memcpy(
420 4 : tmp.data() + pos + n2,
421 2 : curr_data + pos + n1,
422 2 : curr_size - pos - n1 + 1);
423 2 : destroy(sp);
424 2 : *this = tmp;
425 2 : return data() + pos;
426 : }
427 :
428 : void
429 7 : string_impl::
430 : shrink_to_fit(
431 : storage_ptr const& sp) noexcept
432 : {
433 7 : if(s_.k == short_string_)
434 3 : return;
435 4 : auto const t = p_.t;
436 4 : if(t->size <= sbo_chars_)
437 : {
438 2 : s_.k = short_string_;
439 4 : std::memcpy(
440 2 : s_.buf, data(), t->size);
441 2 : s_.buf[sbo_chars_] =
442 : static_cast<char>(
443 2 : sbo_chars_ - t->size);
444 2 : s_.buf[t->size] = 0;
445 2 : sp->deallocate(t,
446 : sizeof(table) +
447 2 : t->capacity + 1,
448 : alignof(table));
449 2 : return;
450 : }
451 2 : if(t->size >= t->capacity)
452 MIS 0 : return;
453 : #ifndef BOOST_NO_EXCEPTIONS
454 : try
455 : {
456 : #endif
457 HIT 2 : string_impl tmp(t->size, sp);
458 1 : std::memcpy(
459 1 : tmp.data(),
460 1 : data(),
461 : size());
462 1 : destroy(sp);
463 1 : *this = tmp;
464 : #ifndef BOOST_NO_EXCEPTIONS
465 : }
466 1 : catch(std::exception const&)
467 : {
468 : // eat the exception
469 1 : }
470 : #endif
471 : }
472 :
473 : } // detail
474 : } // namespace json
475 : } // namespace boost
476 :
477 : #endif
|
