TLA Line data Source code
1 : //
2 : // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/boostorg/json
8 : //
9 :
10 : #ifndef BOOST_JSON_IMPL_ARRAY_HPP
11 : #define BOOST_JSON_IMPL_ARRAY_HPP
12 :
13 : #include <boost/core/detail/static_assert.hpp>
14 : #include <boost/json/value.hpp>
15 : #include <boost/json/detail/except.hpp>
16 : #include <algorithm>
17 : #include <stdexcept>
18 : #include <type_traits>
19 :
20 : namespace boost {
21 : namespace json {
22 :
23 : //----------------------------------------------------------
24 :
25 : struct alignas(value)
26 : array::table
27 : {
28 : std::uint32_t size = 0;
29 : std::uint32_t capacity = 0;
30 :
31 : constexpr table();
32 :
33 : value&
34 HIT 37790 : operator[](std::size_t pos) noexcept
35 : {
36 : return (reinterpret_cast<
37 37790 : value*>(this + 1))[pos];
38 : }
39 :
40 : BOOST_JSON_DECL
41 : static
42 : table*
43 : allocate(
44 : std::size_t capacity,
45 : storage_ptr const& sp);
46 :
47 : BOOST_JSON_DECL
48 : static
49 : void
50 : deallocate(
51 : table* p,
52 : storage_ptr const& sp);
53 : };
54 :
55 : //----------------------------------------------------------
56 :
57 : class array::revert_construct
58 : {
59 : array* arr_;
60 :
61 : public:
62 : explicit
63 410 : revert_construct(
64 : array& arr) noexcept
65 410 : : arr_(&arr)
66 : {
67 410 : }
68 :
69 410 : ~revert_construct()
70 64 : {
71 410 : if(! arr_)
72 346 : return;
73 64 : arr_->destroy();
74 410 : }
75 :
76 : void
77 346 : commit() noexcept
78 : {
79 346 : arr_ = nullptr;
80 346 : }
81 : };
82 :
83 : //----------------------------------------------------------
84 :
85 : class array::revert_insert
86 : {
87 : array* arr_;
88 : std::size_t const i_;
89 : std::size_t const n_;
90 :
91 : public:
92 : value* p;
93 :
94 : BOOST_JSON_DECL
95 : revert_insert(
96 : const_iterator pos,
97 : std::size_t n,
98 : array& arr);
99 :
100 : BOOST_JSON_DECL
101 : ~revert_insert();
102 :
103 : value*
104 18 : commit() noexcept
105 : {
106 : auto it =
107 18 : arr_->data() + i_;
108 18 : arr_ = nullptr;
109 18 : return it;
110 : }
111 : };
112 :
113 : //----------------------------------------------------------
114 :
115 : void
116 797 : array::
117 : relocate(
118 : value* dest,
119 : value* src,
120 : std::size_t n) noexcept
121 : {
122 797 : if(n == 0)
123 660 : return;
124 137 : std::memmove(
125 : static_cast<void*>(dest),
126 : static_cast<void const*>(src),
127 : n * sizeof(value));
128 : }
129 :
130 : //----------------------------------------------------------
131 : //
132 : // Construction
133 : //
134 : //----------------------------------------------------------
135 :
136 : template<class InputIt, class>
137 37 : array::
138 : array(
139 : InputIt first, InputIt last,
140 : storage_ptr sp)
141 : : array(
142 : first, last,
143 37 : std::move(sp),
144 40 : iter_cat<InputIt>{})
145 : {
146 : BOOST_CORE_STATIC_ASSERT((
147 : std::is_constructible<value, decltype(*first)>::value));
148 21 : }
149 :
150 : //----------------------------------------------------------
151 : //
152 : // Modifiers
153 : //
154 : //----------------------------------------------------------
155 :
156 : template<class InputIt, class>
157 : auto
158 27 : array::
159 : insert(
160 : const_iterator pos,
161 : InputIt first, InputIt last) ->
162 : iterator
163 : {
164 : BOOST_CORE_STATIC_ASSERT((
165 : std::is_constructible<value, decltype(*first)>::value));
166 37 : return insert(pos, first, last,
167 23 : iter_cat<InputIt>{});
168 : }
169 :
170 : template<class Arg>
171 : auto
172 13 : array::
173 : emplace(
174 : const_iterator pos,
175 : Arg&& arg) ->
176 : iterator
177 : {
178 13 : BOOST_ASSERT(
179 : pos >= begin() &&
180 : pos <= end());
181 21 : value jv(
182 7 : std::forward<Arg>(arg),
183 : storage());
184 19 : return insert(pos, pilfer(jv));
185 12 : }
186 :
187 : template<class Arg>
188 : value&
189 7607 : array::
190 : emplace_back(Arg&& arg)
191 : {
192 7641 : value jv(
193 31 : std::forward<Arg>(arg),
194 : storage());
195 15203 : return push_back(pilfer(jv));
196 7604 : }
197 :
198 : //----------------------------------------------------------
199 : //
200 : // Element access
201 : //
202 : //----------------------------------------------------------
203 :
204 : value&
205 36 : array::
206 : at(std::size_t pos, source_location const& loc) &
207 : {
208 36 : auto const& self = *this;
209 36 : return const_cast< value& >( self.at(pos, loc) );
210 : }
211 :
212 : value&&
213 16 : array::
214 : at(std::size_t pos, source_location const& loc) &&
215 : {
216 16 : return std::move( at(pos, loc) );
217 : }
218 :
219 : value&
220 49 : array::
221 : operator[](std::size_t pos) & noexcept
222 : {
223 49 : BOOST_ASSERT(pos < t_->size);
224 49 : return (*t_)[pos];
225 : }
226 :
227 : value&&
228 4 : array::
229 : operator[](std::size_t pos) && noexcept
230 : {
231 4 : return std::move( (*this)[pos] );
232 : }
233 :
234 : value const&
235 6738 : array::
236 : operator[](std::size_t pos) const& noexcept
237 : {
238 6738 : BOOST_ASSERT(pos < t_->size);
239 6738 : return (*t_)[pos];
240 : }
241 :
242 : value&
243 5 : array::
244 : front() & noexcept
245 : {
246 5 : BOOST_ASSERT(t_->size > 0);
247 5 : return (*t_)[0];
248 : }
249 :
250 : value&&
251 2 : array::
252 : front() && noexcept
253 : {
254 2 : return std::move( front() );
255 : }
256 :
257 : value const&
258 1 : array::
259 : front() const& noexcept
260 : {
261 1 : BOOST_ASSERT(t_->size > 0);
262 1 : return (*t_)[0];
263 : }
264 :
265 : value&
266 7 : array::
267 : back() & noexcept
268 : {
269 7 : BOOST_ASSERT(
270 : t_->size > 0);
271 7 : return (*t_)[t_->size - 1];
272 : }
273 :
274 : value&&
275 2 : array::
276 : back() && noexcept
277 : {
278 2 : return std::move( back() );
279 : }
280 :
281 : value const&
282 1 : array::
283 : back() const& noexcept
284 : {
285 1 : BOOST_ASSERT(
286 : t_->size > 0);
287 1 : return (*t_)[t_->size - 1];
288 : }
289 :
290 : value*
291 1775 : array::
292 : data() noexcept
293 : {
294 1775 : return &(*t_)[0];
295 : }
296 :
297 : value const*
298 190 : array::
299 : data() const noexcept
300 : {
301 190 : return &(*t_)[0];
302 : }
303 :
304 : value const*
305 17 : array::
306 : if_contains(
307 : std::size_t pos) const noexcept
308 : {
309 17 : if( pos < t_->size )
310 14 : return &(*t_)[pos];
311 3 : return nullptr;
312 : }
313 :
314 : value*
315 3 : array::
316 : if_contains(
317 : std::size_t pos) noexcept
318 : {
319 3 : if( pos < t_->size )
320 2 : return &(*t_)[pos];
321 1 : return nullptr;
322 : }
323 :
324 : //----------------------------------------------------------
325 : //
326 : // Iterators
327 : //
328 : //----------------------------------------------------------
329 :
330 : auto
331 3855 : array::
332 : begin() noexcept ->
333 : iterator
334 : {
335 3855 : return &(*t_)[0];
336 : }
337 :
338 : auto
339 5663 : array::
340 : begin() const noexcept ->
341 : const_iterator
342 : {
343 5663 : return &(*t_)[0];
344 : }
345 :
346 : auto
347 3 : array::
348 : cbegin() const noexcept ->
349 : const_iterator
350 : {
351 3 : return &(*t_)[0];
352 : }
353 :
354 : auto
355 4008 : array::
356 : end() noexcept ->
357 : iterator
358 : {
359 4008 : return &(*t_)[t_->size];
360 : }
361 :
362 : auto
363 6186 : array::
364 : end() const noexcept ->
365 : const_iterator
366 : {
367 6186 : return &(*t_)[t_->size];
368 : }
369 :
370 : auto
371 3 : array::
372 : cend() const noexcept ->
373 : const_iterator
374 : {
375 3 : return &(*t_)[t_->size];
376 : }
377 :
378 : auto
379 3 : array::
380 : rbegin() noexcept ->
381 : reverse_iterator
382 : {
383 3 : return reverse_iterator(end());
384 : }
385 :
386 : auto
387 3 : array::
388 : rbegin() const noexcept ->
389 : const_reverse_iterator
390 : {
391 3 : return const_reverse_iterator(end());
392 : }
393 :
394 : auto
395 3 : array::
396 : crbegin() const noexcept ->
397 : const_reverse_iterator
398 : {
399 3 : return const_reverse_iterator(end());
400 : }
401 :
402 : auto
403 3 : array::
404 : rend() noexcept ->
405 : reverse_iterator
406 : {
407 3 : return reverse_iterator(begin());
408 : }
409 :
410 : auto
411 3 : array::
412 : rend() const noexcept ->
413 : const_reverse_iterator
414 : {
415 3 : return const_reverse_iterator(begin());
416 : }
417 :
418 : auto
419 3 : array::
420 : crend() const noexcept ->
421 : const_reverse_iterator
422 : {
423 3 : return const_reverse_iterator(begin());
424 : }
425 :
426 : //----------------------------------------------------------
427 : //
428 : // Capacity
429 : //
430 : //----------------------------------------------------------
431 :
432 : std::size_t
433 6538 : array::
434 : size() const noexcept
435 : {
436 6538 : return t_->size;
437 : }
438 :
439 : constexpr
440 : std::size_t
441 4164 : array::
442 : max_size() noexcept
443 : {
444 : // max_size depends on the address model
445 : using min = std::integral_constant<std::size_t,
446 : (std::size_t(-1) - sizeof(table)) / sizeof(value)>;
447 : return min::value < BOOST_JSON_MAX_STRUCTURED_SIZE ?
448 4164 : min::value : BOOST_JSON_MAX_STRUCTURED_SIZE;
449 : }
450 :
451 : std::size_t
452 858 : array::
453 : capacity() const noexcept
454 : {
455 858 : return t_->capacity;
456 : }
457 :
458 : bool
459 195 : array::
460 : empty() const noexcept
461 : {
462 195 : return t_->size == 0;
463 : }
464 :
465 : void
466 711 : array::
467 : reserve(
468 : std::size_t new_capacity)
469 : {
470 : // never shrink
471 711 : if(new_capacity <= t_->capacity)
472 37 : return;
473 674 : reserve_impl(new_capacity);
474 : }
475 :
476 : //----------------------------------------------------------
477 : //
478 : // private
479 : //
480 : //----------------------------------------------------------
481 :
482 : template<class InputIt>
483 19 : array::
484 : array(
485 : InputIt first, InputIt last,
486 : storage_ptr sp,
487 : std::input_iterator_tag)
488 19 : : sp_(std::move(sp))
489 19 : , t_(&empty_)
490 : {
491 19 : revert_construct r(*this);
492 86 : while(first != last)
493 : {
494 80 : reserve(size() + 1);
495 138 : ::new(end()) value(
496 136 : *first++, sp_);
497 67 : ++t_->size;
498 : }
499 6 : r.commit();
500 32 : }
501 :
502 : template<class InputIt>
503 18 : array::
504 : array(
505 : InputIt first, InputIt last,
506 : storage_ptr sp,
507 : std::forward_iterator_tag)
508 18 : : sp_(std::move(sp))
509 : {
510 18 : std::size_t n =
511 18 : std::distance(first, last);
512 18 : if( n == 0 )
513 : {
514 3 : t_ = &empty_;
515 3 : return;
516 : }
517 :
518 15 : t_ = table::allocate(n, sp_);
519 13 : t_->size = 0;
520 13 : revert_construct r(*this);
521 53 : while(n--)
522 : {
523 84 : ::new(end()) value(
524 41 : *first++, sp_);
525 40 : ++t_->size;
526 : }
527 12 : r.commit();
528 16 : }
529 :
530 : template<class InputIt>
531 : auto
532 13 : array::
533 : insert(
534 : const_iterator pos,
535 : InputIt first, InputIt last,
536 : std::input_iterator_tag) ->
537 : iterator
538 : {
539 13 : BOOST_ASSERT(
540 : pos >= begin() && pos <= end());
541 13 : if(first == last)
542 1 : return data() + (pos - data());
543 20 : array temp(first, last, sp_);
544 4 : revert_insert r(
545 : pos, temp.size(), *this);
546 2 : relocate(
547 : r.p,
548 : temp.data(),
549 : temp.size());
550 2 : temp.t_->size = 0;
551 2 : return r.commit();
552 4 : }
553 :
554 : template<class InputIt>
555 : auto
556 14 : array::
557 : insert(
558 : const_iterator pos,
559 : InputIt first, InputIt last,
560 : std::forward_iterator_tag) ->
561 : iterator
562 : {
563 14 : std::size_t n =
564 14 : std::distance(first, last);
565 14 : revert_insert r(pos, n, *this);
566 3050 : while(n--)
567 : {
568 3040 : ::new(r.p) value(*first++);
569 3040 : ++r.p;
570 : }
571 20 : return r.commit();
572 10 : }
573 :
574 : } // namespace json
575 : } // namespace boost
576 :
577 : #endif
|
