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