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