ceph/src/boost/boost/json/impl/array.ipp

   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_IPP
  11 #define BOOST_JSON_IMPL_ARRAY_IPP
  12
  13 #include <boost/json/array.hpp>
  14 #include <boost/json/pilfer.hpp>
  15 #include <boost/json/detail/except.hpp>
  16 #include <cstdlib>
  17 #include <limits>
  18 #include <new>
  19 #include <utility>
  20
  21 BOOST_JSON_NS_BEGIN
  22
  23 //----------------------------------------------------------
  24
  25 constexpr array::table::table() = default;
  26
  27 // empty arrays point here
  28 BOOST_JSON_REQUIRE_CONST_INIT
  29 array::table array::empty_;
  30
  31 auto
  32 array::
  33 table::
  34 allocate(
  35     std::size_t capacity,
  36     storage_ptr const& sp) ->
  37         table*
  38 {
  39     BOOST_ASSERT(capacity > 0);
  40     if(capacity > array::max_size())
  41         detail::throw_length_error(
  42             "array too large",
  43             BOOST_CURRENT_LOCATION);
  44     auto p = reinterpret_cast<
  45         table*>(sp->allocate(
  46             sizeof(table) +
  47                 capacity * sizeof(value),
  48             alignof(value)));
  49     p->capacity = static_cast<
  50         std::uint32_t>(capacity);
  51     return p;
  52 }
  53
  54 void
  55 array::
  56 table::
  57 deallocate(
  58     table* p,
  59     storage_ptr const& sp)
  60 {
  61     if(p->capacity == 0)
  62         return;
  63     sp->deallocate(p,
  64         sizeof(table) +
  65             p->capacity * sizeof(value),
  66         alignof(value));
  67 }
  68
  69 //----------------------------------------------------------
  70
  71 array::
  72 revert_insert::
  73 revert_insert(
  74     const_iterator pos,
  75     std::size_t n,
  76     array& arr)
  77     : arr_(&arr)
  78     , i_(pos - arr_->data())
  79     , n_(n)
  80 {
  81     BOOST_ASSERT(
  82         pos >= arr_->begin() &&
  83         pos <= arr_->end());
  84     if( n_ <= arr_->capacity() -
  85         arr_->size())
  86     {
  87         // fast path
  88         p = arr_->data() + i_;
  89         if(n_ == 0)
  90             return;
  91         relocate(
  92             p + n_,
  93             p,
  94             arr_->size() - i_);
  95         arr_->t_->size = static_cast<
  96             std::uint32_t>(
  97                 arr_->t_->size + n_);
  98         return;
  99     }
 100     if(n_ > max_size() - arr_->size())
 101         detail::throw_length_error(
 102             "array too large",
 103             BOOST_CURRENT_LOCATION);
 104     auto t = table::allocate(
 105         arr_->growth(arr_->size() + n_),
 106             arr_->sp_);
 107     t->size = static_cast<std::uint32_t>(
 108         arr_->size() + n_);
 109     p = &(*t)[0] + i_;
 110     relocate(
 111         &(*t)[0],
 112         arr_->data(),
 113         i_);
 114     relocate(
 115         &(*t)[i_ + n_],
 116         arr_->data() + i_,
 117         arr_->size() - i_);
 118     t = detail::exchange(arr_->t_, t);
 119     table::deallocate(t, arr_->sp_);
 120 }
 121
 122 array::
 123 revert_insert::
 124 ~revert_insert()
 125 {
 126     if(! arr_)
 127         return;
 128     BOOST_ASSERT(n_ != 0);
 129     auto const pos =
 130         arr_->data() + i_;
 131     arr_->destroy(pos, p);
 132     arr_->t_->size = static_cast<
 133         std::uint32_t>(
 134             arr_->t_->size - n_);
 135     relocate(
 136         pos,
 137         pos + n_,
 138         arr_->size() - i_);
 139 }
 140
 141 //----------------------------------------------------------
 142
 143 void
 144 array::
 145 destroy(
 146     value* first, value* last) noexcept
 147 {
 148     if(sp_.is_not_shared_and_deallocate_is_trivial())
 149         return;
 150     while(last-- != first)
 151         last->~value();
 152 }
 153
 154 void
 155 array::
 156 destroy() noexcept
 157 {
 158     if(sp_.is_not_shared_and_deallocate_is_trivial())
 159         return;
 160     auto last = end();
 161     auto const first = begin();
 162     while(last-- != first)
 163         last->~value();
 164     table::deallocate(t_, sp_);
 165 }
 166
 167 //----------------------------------------------------------
 168 //
 169 // Special Members
 170 //
 171 //----------------------------------------------------------
 172
 173 array::
 174 array(detail::unchecked_array&& ua)
 175     : sp_(ua.storage())
 176 {
 177     BOOST_STATIC_ASSERT(
 178         alignof(table) == alignof(value));
 179     if(ua.size() == 0)
 180     {
 181         t_ = &empty_;
 182         return;
 183     }
 184     t_= table::allocate(
 185         ua.size(), sp_);
 186     t_->size = static_cast<
 187         std::uint32_t>(ua.size());
 188     ua.relocate(data());
 189 }
 190
 191 array::
 192 ~array()
 193 {
 194     destroy();
 195 }
 196
 197 array::
 198 array(
 199     std::size_t count,
 200     value const& v,
 201     storage_ptr sp)
 202     : sp_(std::move(sp))
 203 {
 204     if(count == 0)
 205     {
 206         t_ = &empty_;
 207         return;
 208     }
 209     t_= table::allocate(
 210         count, sp_);
 211     t_->size = 0;
 212     revert_construct r(*this);
 213     while(count--)
 214     {
 215         ::new(end()) value(v, sp_);
 216         ++t_->size;
 217     }
 218     r.commit();
 219 }
 220
 221 array::
 222 array(
 223     std::size_t count,
 224     storage_ptr sp)
 225     : sp_(std::move(sp))
 226 {
 227     if(count == 0)
 228     {
 229         t_ = &empty_;
 230         return;
 231     }
 232     t_ = table::allocate(
 233         count, sp_);
 234     t_->size = static_cast<
 235         std::uint32_t>(count);
 236     auto p = data();
 237     do
 238     {
 239         ::new(p++) value(sp_);
 240     }
 241     while(--count);
 242 }
 243
 244 array::
 245 array(array const& other)
 246     : array(other, other.sp_)
 247 {
 248 }
 249
 250 array::
 251 array(
 252     array const& other,
 253     storage_ptr sp)
 254     : sp_(std::move(sp))
 255 {
 256     if(other.empty())
 257     {
 258         t_ = &empty_;
 259         return;
 260     }
 261     t_ = table::allocate(
 262         other.size(), sp_);
 263     t_->size = 0;
 264     revert_construct r(*this);
 265     auto src = other.data();
 266     auto dest = data();
 267     auto const n = other.size();
 268     do
 269     {
 270         ::new(dest++) value(
 271             *src++, sp_);
 272         ++t_->size;
 273     }
 274     while(t_->size < n);
 275     r.commit();
 276 }
 277
 278 array::
 279 array(
 280     array&& other,
 281     storage_ptr sp)
 282     : sp_(std::move(sp))
 283 {
 284     if(*sp_ == *other.sp_)
 285     {
 286         // same resource
 287         t_ = detail::exchange(
 288             other.t_, &empty_);
 289         return;
 290     }
 291     else if(other.empty())
 292     {
 293         t_ = &empty_;
 294         return;
 295     }
 296     // copy
 297     t_ = table::allocate(
 298         other.size(), sp_);
 299     t_->size = 0;
 300     revert_construct r(*this);
 301     auto src = other.data();
 302     auto dest = data();
 303     auto const n = other.size();
 304     do
 305     {
 306         ::new(dest++) value(
 307             *src++, sp_);
 308         ++t_->size;
 309     }
 310     while(t_->size < n);
 311     r.commit();
 312 }
 313
 314 array::
 315 array(
 316     std::initializer_list<
 317         value_ref> init,
 318     storage_ptr sp)
 319     : sp_(std::move(sp))
 320 {
 321     if(init.size() == 0)
 322     {
 323         t_ = &empty_;
 324         return;
 325     }
 326     t_ = table::allocate(
 327         init.size(), sp_);
 328     t_->size = 0;
 329     revert_construct r(*this);
 330     value_ref::write_array(
 331         data(), init, sp_);
 332     t_->size = static_cast<
 333         std::uint32_t>(init.size());
 334     r.commit();
 335 }
 336
 337 //----------------------------------------------------------
 338
 339 array&
 340 array::
 341 operator=(array const& other)
 342 {
 343     array(other,
 344         storage()).swap(*this);
 345     return *this;
 346 }
 347
 348 array&
 349 array::
 350 operator=(array&& other)
 351 {
 352     array(std::move(other),
 353         storage()).swap(*this);
 354     return *this;
 355 }
 356
 357 array&
 358 array::
 359 operator=(
 360     std::initializer_list<value_ref> init)
 361 {
 362     array(init,
 363         storage()).swap(*this);
 364     return *this;
 365 }
 366
 367 //----------------------------------------------------------
 368 //
 369 // Capacity
 370 //
 371 //----------------------------------------------------------
 372
 373 void
 374 array::
 375 shrink_to_fit() noexcept
 376 {
 377     if(capacity() <= size())
 378         return;
 379     if(size() == 0)
 380     {
 381         table::deallocate(t_, sp_);
 382         t_ = &empty_;
 383         return;
 384     }
 385
 386 #ifndef BOOST_NO_EXCEPTIONS
 387     try
 388     {
 389 #endif
 390         auto t = table::allocate(
 391             size(), sp_);
 392         relocate(
 393             &(*t)[0],
 394             data(),
 395             size());
 396         t->size = static_cast<
 397             std::uint32_t>(size());
 398         t = detail::exchange(
 399             t_, t);
 400         table::deallocate(t, sp_);
 401 #ifndef BOOST_NO_EXCEPTIONS
 402     }
 403     catch(...)
 404     {
 405         // eat the exception
 406         return;
 407     }
 408 #endif
 409 }
 410
 411 //----------------------------------------------------------
 412 //
 413 // Modifiers
 414 //
 415 //----------------------------------------------------------
 416
 417 void
 418 array::
 419 clear() noexcept
 420 {
 421     if(size() == 0)
 422         return;
 423     destroy(
 424         begin(), end());
 425     t_->size = 0;
 426 }
 427
 428 auto
 429 array::
 430 insert(
 431     const_iterator pos,
 432     value const& v) ->
 433         iterator
 434 {
 435     return emplace(pos, v);
 436 }
 437
 438 auto
 439 array::
 440 insert(
 441     const_iterator pos,
 442     value&& v) ->
 443         iterator
 444 {
 445     return emplace(pos, std::move(v));
 446 }
 447
 448 auto
 449 array::
 450 insert(
 451     const_iterator pos,
 452     std::size_t count,
 453     value const& v) ->
 454         iterator
 455 {
 456     revert_insert r(
 457         pos, count, *this);
 458     while(count--)
 459     {
 460         ::new(r.p) value(v, sp_);
 461         ++r.p;
 462     }
 463     return r.commit();
 464 }
 465
 466 auto
 467 array::
 468 insert(
 469     const_iterator pos,
 470     std::initializer_list<
 471         value_ref> init) ->
 472     iterator
 473 {
 474     revert_insert r(
 475         pos, init.size(), *this);
 476     value_ref::write_array(
 477         r.p, init, sp_);
 478     return r.commit();
 479 }
 480
 481 auto
 482 array::
 483 erase(
 484     const_iterator pos) noexcept ->
 485     iterator
 486 {
 487     BOOST_ASSERT(
 488         pos >= begin() &&
 489         pos <= end());
 490     auto const p = &(*t_)[0] +
 491         (pos - &(*t_)[0]);
 492     destroy(p, p + 1);
 493     relocate(p, p + 1, 1);
 494     --t_->size;
 495     return p;
 496 }
 497
 498 auto
 499 array::
 500 erase(
 501     const_iterator first,
 502     const_iterator last) noexcept ->
 503         iterator
 504 {
 505     std::size_t const n =
 506         last - first;
 507     auto const p = &(*t_)[0] +
 508         (first - &(*t_)[0]);
 509     destroy(p, p + n);
 510     relocate(p, p + n,
 511         t_->size - (last -
 512             &(*t_)[0]));
 513     t_->size = static_cast<
 514         std::uint32_t>(t_->size - n);
 515     return p;
 516 }
 517
 518 void
 519 array::
 520 push_back(value const& v)
 521 {
 522     emplace_back(v);
 523 }
 524
 525 void
 526 array::
 527 push_back(value&& v)
 528 {
 529     emplace_back(std::move(v));
 530 }
 531
 532 void
 533 array::
 534 pop_back() noexcept
 535 {
 536     auto const p = &back();
 537     destroy(p, p + 1);
 538     --t_->size;
 539 }
 540
 541 void
 542 array::
 543 resize(std::size_t count)
 544 {
 545     if(count <= t_->size)
 546     {
 547         // shrink
 548         destroy(
 549             &(*t_)[0] + count,
 550             &(*t_)[0] + t_->size);
 551         t_->size = static_cast<
 552             std::uint32_t>(count);
 553         return;
 554     }
 555
 556     reserve(count);
 557     auto p = &(*t_)[t_->size];
 558     auto const end = &(*t_)[count];
 559     while(p != end)
 560         ::new(p++) value(sp_);
 561     t_->size = static_cast<
 562         std::uint32_t>(count);
 563 }
 564
 565 void
 566 array::
 567 resize(
 568     std::size_t count,
 569     value const& v)
 570 {
 571     if(count <= size())
 572     {
 573         // shrink
 574         destroy(
 575             data() + count,
 576             data() + size());
 577         t_->size = static_cast<
 578             std::uint32_t>(count);
 579         return;
 580     }
 581     count -= size();
 582     revert_insert r(
 583         end(), count, *this);
 584     while(count--)
 585     {
 586         ::new(r.p) value(v, sp_);
 587         ++r.p;
 588     }
 589     r.commit();
 590 }
 591
 592 void
 593 array::
 594 swap(array& other)
 595 {
 596     BOOST_ASSERT(this != &other);
 597     if(*sp_ == *other.sp_)
 598     {
 599         t_ = detail::exchange(
 600             other.t_, t_);
 601         return;
 602     }
 603     array temp1(
 604         std::move(*this),
 605         other.storage());
 606     array temp2(
 607         std::move(other),
 608         this->storage());
 609     this->~array();
 610     ::new(this) array(
 611         pilfer(temp2));
 612     other.~array();
 613     ::new(&other) array(
 614         pilfer(temp1));
 615 }
 616
 617 //----------------------------------------------------------
 618 //
 619 // Private
 620 //
 621 //----------------------------------------------------------
 622
 623 std::size_t
 624 array::
 625 growth(
 626     std::size_t new_size) const
 627 {
 628     if(new_size > max_size())
 629         detail::throw_length_error(
 630             "array too large",
 631             BOOST_CURRENT_LOCATION);
 632     std::size_t const old = capacity();
 633     if(old > max_size() - old / 2)
 634         return new_size;
 635     std::size_t const g =
 636         old + old / 2; // 1.5x
 637     if(g < new_size)
 638         return new_size;
 639     return g;
 640 }
 641
 642 // precondition: new_capacity > capacity()
 643 void
 644 array::
 645 reserve_impl(
 646     std::size_t new_capacity)
 647 {
 648     BOOST_ASSERT(
 649         new_capacity > t_->capacity);
 650     auto t = table::allocate(
 651         growth(new_capacity), sp_);
 652     relocate(
 653         &(*t)[0],
 654         &(*t_)[0],
 655         t_->size);
 656     t->size = t_->size;
 657     t = detail::exchange(t_, t);
 658     table::deallocate(t, sp_);
 659 }
 660
 661 // precondition: pv is not aliased
 662 value&
 663 array::
 664 push_back(
 665     pilfered<value> pv)
 666 {
 667     auto const n = t_->size;
 668     if(n < t_->capacity)
 669     {
 670         // fast path
 671         auto& v = *::new(
 672             &(*t_)[n]) value(pv);
 673         ++t_->size;
 674         return v;
 675     }
 676     auto const t =
 677         detail::exchange(t_,
 678             table::allocate(
 679                 growth(n + 1),
 680                     sp_));
 681     auto& v = *::new(
 682         &(*t_)[n]) value(pv);
 683     relocate(
 684         &(*t_)[0],
 685         &(*t)[0],
 686         n);
 687     t_->size = n + 1;
 688     table::deallocate(t, sp_);
 689     return v;
 690 }
 691
 692 // precondition: pv is not aliased
 693 auto
 694 array::
 695 insert(
 696     const_iterator pos,
 697     pilfered<value> pv) ->
 698         iterator
 699 {
 700     BOOST_ASSERT(
 701         pos >= begin() &&
 702         pos <= end());
 703     std::size_t const n =
 704         t_->size;
 705     std::size_t const i =
 706         pos - &(*t_)[0];
 707     if(n < t_->capacity)
 708     {
 709         // fast path
 710         auto const p =
 711             &(*t_)[i];
 712         relocate(
 713             p + 1,
 714             p,
 715             n - i);
 716         ::new(p) value(pv);
 717         ++t_->size;
 718         return p;
 719     }
 720     auto t =
 721         table::allocate(
 722             growth(n + 1), sp_);
 723     auto const p = &(*t)[i];
 724     ::new(p) value(pv);
 725     relocate(
 726         &(*t)[0],
 727         &(*t_)[0],
 728         i);
 729     relocate(
 730         p + 1,
 731         &(*t_)[i],
 732         n - i);
 733     t->size = static_cast<
 734         std::uint32_t>(size() + 1);
 735     t = detail::exchange(t_, t);
 736     table::deallocate(t, sp_);
 737     return p;
 738 }
 739
 740 //----------------------------------------------------------
 741
 742 bool
 743 array::
 744 equal(
 745     array const& other) const noexcept
 746 {
 747     if(size() != other.size())
 748         return false;
 749     for(std::size_t i = 0; i < size(); ++i)
 750         if((*this)[i] != other[i])
 751             return false;
 752     return true;
 753 }
 754
 755 BOOST_JSON_NS_END
 756
 757 #endif