ceph/src/boost/boost/json/impl/object.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_OBJECT_IPP
  11 #define BOOST_JSON_IMPL_OBJECT_IPP
  12
  13 #include <boost/json/object.hpp>
  14 #include <boost/json/detail/digest.hpp>
  15 #include <boost/json/detail/except.hpp>
  16 #include <algorithm>
  17 #include <cmath>
  18 #include <cstdlib>
  19 #include <cstring>
  20 #include <new>
  21 #include <stdexcept>
  22 #include <type_traits>
  23
  24 BOOST_JSON_NS_BEGIN
  25
  26 //----------------------------------------------------------
  27
  28 constexpr object::table::table() = default;
  29
  30 // empty objects point here
  31 BOOST_JSON_REQUIRE_CONST_INIT
  32 object::table object::empty_;
  33
  34 std::size_t
  35 object::table::
  36 digest(string_view key) const noexcept
  37 {
  38     BOOST_ASSERT(salt != 0);
  39     return detail::digest(
  40         key.data(), key.size(), salt);
  41 }
  42
  43 auto
  44 object::table::
  45 bucket(std::size_t hash) noexcept ->
  46     index_t&
  47 {
  48     return reinterpret_cast<
  49         index_t*>(&(*this)[capacity])[
  50             hash % capacity];
  51 }
  52
  53 auto
  54 object::table::
  55 bucket(string_view key) noexcept ->
  56     index_t&
  57 {
  58     return bucket(digest(key));
  59 }
  60
  61 void
  62 object::table::
  63 clear() noexcept
  64 {
  65     BOOST_ASSERT(! is_small());
  66     // initialize buckets
  67     std::memset(
  68         reinterpret_cast<index_t*>(
  69             &(*this)[capacity]),
  70         0xff, // null_index_
  71         capacity * sizeof(index_t));
  72 }
  73
  74 object::table*
  75 object::table::
  76 allocate(
  77     std::size_t capacity,
  78     std::uintptr_t salt,
  79     storage_ptr const& sp)
  80 {
  81     BOOST_STATIC_ASSERT(
  82         alignof(key_value_pair) >=
  83         alignof(index_t));
  84     BOOST_ASSERT(capacity > 0);
  85     BOOST_ASSERT(capacity <= max_size());
  86     table* p;
  87     if(capacity <= detail::small_object_size_)
  88     {
  89         p = reinterpret_cast<
  90             table*>(sp->allocate(
  91                 sizeof(table) + capacity *
  92                     sizeof(key_value_pair)));
  93         p->capacity = static_cast<
  94             std::uint32_t>(capacity);
  95     }
  96     else
  97     {
  98         p = reinterpret_cast<
  99             table*>(sp->allocate(
 100                 sizeof(table) + capacity * (
 101                     sizeof(key_value_pair) +
 102                     sizeof(index_t))));
 103         p->capacity = static_cast<
 104             std::uint32_t>(capacity);
 105         p->clear();
 106     }
 107     if(salt)
 108     {
 109         p->salt = salt;
 110     }
 111     else
 112     {
 113         // VFALCO This would be better if it
 114         //        was random, but maybe this
 115         //        is good enough.
 116         p->salt = reinterpret_cast<
 117             std::uintptr_t>(p);
 118     }
 119     return p;
 120 }
 121
 122 //----------------------------------------------------------
 123
 124 void
 125 object::
 126 revert_construct::
 127 destroy() noexcept
 128 {
 129     obj_->destroy();
 130 }
 131
 132 //----------------------------------------------------------
 133
 134 void
 135 object::
 136 revert_insert::
 137 destroy() noexcept
 138 {
 139     obj_->destroy(
 140         &(*obj_->t_)[size_],
 141         obj_->end());
 142 }
 143
 144 //----------------------------------------------------------
 145 //
 146 // Construction
 147 //
 148 //----------------------------------------------------------
 149
 150 object::
 151 object(detail::unchecked_object&& uo)
 152     : sp_(uo.storage())
 153 {
 154     if(uo.size() == 0)
 155     {
 156         t_ = &empty_;
 157         return;
 158     }
 159     // should already be checked
 160     BOOST_ASSERT(
 161         uo.size() <= max_size());
 162     t_ = table::allocate(
 163         uo.size(), 0, sp_);
 164
 165     // insert all elements, keeping
 166     // the last of any duplicate keys.
 167     auto dest = begin();
 168     auto src = uo.release();
 169     auto const end = src + 2 * uo.size();
 170     if(t_->is_small())
 171     {
 172         t_->size = 0;
 173         while(src != end)
 174         {
 175             access::construct_key_value_pair(
 176                 dest, pilfer(src[0]), pilfer(src[1]));
 177             src += 2;
 178             auto result = find_impl(dest->key());
 179             if(! result.first)
 180             {
 181                 ++dest;
 182                 ++t_->size;
 183                 continue;
 184             }
 185             // handle duplicate
 186             auto& v = *result.first;
 187             // don't bother to check if
 188             // storage deallocate is trivial
 189             v.~key_value_pair();
 190             // trivial relocate
 191             std::memcpy(
 192                 static_cast<void*>(&v),
 193                     dest, sizeof(v));
 194         }
 195         return;
 196     }
 197     while(src != end)
 198     {
 199         access::construct_key_value_pair(
 200             dest, pilfer(src[0]), pilfer(src[1]));
 201         src += 2;
 202         auto& head = t_->bucket(dest->key());
 203         auto i = head;
 204         for(;;)
 205         {
 206             if(i == null_index_)
 207             {
 208                 // end of bucket
 209                 access::next(
 210                     *dest) = head;
 211                 head = static_cast<index_t>(
 212                     dest - begin());
 213                 ++dest;
 214                 break;
 215             }
 216             auto& v = (*t_)[i];
 217             if(v.key() != dest->key())
 218             {
 219                 i = access::next(v);
 220                 continue;
 221             }
 222
 223             // handle duplicate
 224             access::next(*dest) =
 225                 access::next(v);
 226             // don't bother to check if
 227             // storage deallocate is trivial
 228             v.~key_value_pair();
 229             // trivial relocate
 230             std::memcpy(
 231                 static_cast<void*>(&v),
 232                     dest, sizeof(v));
 233             break;
 234         }
 235     }
 236     t_->size = static_cast<
 237         index_t>(dest - begin());
 238 }
 239
 240 object::
 241 ~object()
 242 {
 243     if(sp_.is_not_shared_and_deallocate_is_trivial())
 244         return;
 245     if(t_->capacity == 0)
 246         return;
 247     destroy();
 248 }
 249
 250 object::
 251 object(
 252     std::size_t min_capacity,
 253     storage_ptr sp)
 254     : sp_(std::move(sp))
 255     , t_(&empty_)
 256 {
 257     reserve(min_capacity);
 258 }
 259
 260 object::
 261 object(object&& other) noexcept
 262     : sp_(other.sp_)
 263     , t_(detail::exchange(
 264         other.t_, &empty_))
 265 {
 266 }
 267
 268 object::
 269 object(
 270     object&& other,
 271     storage_ptr sp)
 272     : sp_(std::move(sp))
 273 {
 274     if(*sp_ == *other.sp_)
 275     {
 276         t_ = detail::exchange(
 277             other.t_, &empty_);
 278         return;
 279     }
 280
 281     t_ = &empty_;
 282     object(other, sp_).swap(*this);
 283 }
 284
 285 object::
 286 object(
 287     object const& other,
 288     storage_ptr sp)
 289     : sp_(std::move(sp))
 290     , t_(&empty_)
 291 {
 292     reserve(other.size());
 293     revert_construct r(*this);
 294     if(t_->is_small())
 295     {
 296         for(auto const& v : other)
 297         {
 298             ::new(end())
 299                 key_value_pair(v, sp_);
 300             ++t_->size;
 301         }
 302         r.commit();
 303         return;
 304     }
 305     for(auto const& v : other)
 306     {
 307         // skip duplicate checking
 308         auto& head =
 309             t_->bucket(v.key());
 310         auto pv = ::new(end())
 311             key_value_pair(v, sp_);
 312         access::next(*pv) = head;
 313         head = t_->size;
 314         ++t_->size;
 315     }
 316     r.commit();
 317 }
 318
 319 object::
 320 object(
 321     std::initializer_list<std::pair<
 322         string_view, value_ref>> init,
 323     std::size_t min_capacity,
 324     storage_ptr sp)
 325     : sp_(std::move(sp))
 326     , t_(&empty_)
 327 {
 328     if( min_capacity < init.size())
 329         min_capacity = init.size();
 330     reserve(min_capacity);
 331     revert_construct r(*this);
 332     insert(init);
 333     r.commit();
 334 }
 335
 336 //----------------------------------------------------------
 337 //
 338 // Assignment
 339 //
 340 //----------------------------------------------------------
 341
 342 object&
 343 object::
 344 operator=(object const& other)
 345 {
 346     object tmp(other, sp_);
 347     this->~object();
 348     ::new(this) object(pilfer(tmp));
 349     return *this;
 350 }
 351
 352 object&
 353 object::
 354 operator=(object&& other)
 355 {
 356     object tmp(std::move(other), sp_);
 357     this->~object();
 358     ::new(this) object(pilfer(tmp));
 359     return *this;
 360 }
 361
 362 object&
 363 object::
 364 operator=(
 365     std::initializer_list<std::pair<
 366         string_view, value_ref>> init)
 367 {
 368     object tmp(init, sp_);
 369     this->~object();
 370     ::new(this) object(pilfer(tmp));
 371     return *this;
 372 }
 373
 374 //----------------------------------------------------------
 375 //
 376 // Modifiers
 377 //
 378 //----------------------------------------------------------
 379
 380 void
 381 object::
 382 clear() noexcept
 383 {
 384     if(empty())
 385         return;
 386     if(! sp_.is_not_shared_and_deallocate_is_trivial())
 387         destroy(begin(), end());
 388     if(! t_->is_small())
 389         t_->clear();
 390     t_->size = 0;
 391 }
 392
 393 void
 394 object::
 395 insert(
 396     std::initializer_list<std::pair<
 397         string_view, value_ref>> init)
 398 {
 399     auto const n0 = size();
 400     if(init.size() > max_size() - n0)
 401         detail::throw_length_error(
 402             "object too large",
 403             BOOST_CURRENT_LOCATION);
 404     reserve(n0 + init.size());
 405     revert_insert r(*this);
 406     if(t_->is_small())
 407     {
 408         for(auto& iv : init)
 409         {
 410             auto result =
 411                 find_impl(iv.first);
 412             if(result.first)
 413             {
 414                 // ignore duplicate
 415                 continue;
 416             }
 417             ::new(end()) key_value_pair(
 418                 iv.first,
 419                 iv.second.make_value(sp_));
 420             ++t_->size;
 421         }
 422         r.commit();
 423         return;
 424     }
 425     for(auto& iv : init)
 426     {
 427         auto& head = t_->bucket(iv.first);
 428         auto i = head;
 429         for(;;)
 430         {
 431             if(i == null_index_)
 432             {
 433                 // VFALCO value_ref should construct
 434                 // a key_value_pair using placement
 435                 auto& v = *::new(end())
 436                     key_value_pair(
 437                         iv.first,
 438                         iv.second.make_value(sp_));
 439                 access::next(v) = head;
 440                 head = static_cast<index_t>(
 441                     t_->size);
 442                 ++t_->size;
 443                 break;
 444             }
 445             auto& v = (*t_)[i];
 446             if(v.key() == iv.first)
 447             {
 448                 // ignore duplicate
 449                 break;
 450             }
 451             i = access::next(v);
 452         }
 453     }
 454     r.commit();
 455 }
 456
 457 auto
 458 object::
 459 erase(const_iterator pos) noexcept ->
 460     iterator
 461 {
 462     auto p = begin() + (pos - begin());
 463     if(t_->is_small())
 464     {
 465         p->~value_type();
 466         --t_->size;
 467         auto const pb = end();
 468         if(p != end())
 469         {
 470             // the casts silence warnings
 471             std::memcpy(
 472                 static_cast<void*>(p),
 473                 static_cast<void const*>(pb),
 474                 sizeof(*p));
 475         }
 476         return p;
 477     }
 478     remove(t_->bucket(p->key()), *p);
 479     p->~value_type();
 480     --t_->size;
 481     auto const pb = end();
 482     if(p != end())
 483     {
 484         auto& head = t_->bucket(pb->key());
 485         remove(head, *pb);
 486         // the casts silence warnings
 487         std::memcpy(
 488             static_cast<void*>(p),
 489             static_cast<void const*>(pb),
 490             sizeof(*p));
 491         access::next(*p) = head;
 492         head = static_cast<
 493             index_t>(p - begin());
 494     }
 495     return p;
 496 }
 497
 498 auto
 499 object::
 500 erase(string_view key) noexcept ->
 501     std::size_t
 502 {
 503     auto it = find(key);
 504     if(it == end())
 505         return 0;
 506     erase(it);
 507     return 1;
 508 }
 509
 510 void
 511 object::
 512 swap(object& other)
 513 {
 514     if(*sp_ == *other.sp_)
 515     {
 516         t_ = detail::exchange(
 517             other.t_, t_);
 518         return;
 519     }
 520     object temp1(
 521         std::move(*this),
 522         other.storage());
 523     object temp2(
 524         std::move(other),
 525         this->storage());
 526     other.~object();
 527     ::new(&other) object(pilfer(temp1));
 528     this->~object();
 529     ::new(this) object(pilfer(temp2));
 530 }
 531
 532 //----------------------------------------------------------
 533 //
 534 // Lookup
 535 //
 536 //----------------------------------------------------------
 537
 538 auto
 539 object::
 540 operator[](string_view key) ->
 541     value&
 542 {
 543     auto const result =
 544         emplace(key, nullptr);
 545     return result.first->value();
 546 }
 547
 548 auto
 549 object::
 550 count(string_view key) const noexcept ->
 551     std::size_t
 552 {
 553     if(find(key) == end())
 554         return 0;
 555     return 1;
 556 }
 557
 558 auto
 559 object::
 560 find(string_view key) noexcept ->
 561     iterator
 562 {
 563     if(empty())
 564         return end();
 565     auto const p =
 566         find_impl(key).first;
 567     if(p)
 568         return p;
 569     return end();
 570 }
 571
 572 auto
 573 object::
 574 find(string_view key) const noexcept ->
 575     const_iterator
 576 {
 577     if(empty())
 578         return end();
 579     auto const p =
 580         find_impl(key).first;
 581     if(p)
 582         return p;
 583     return end();
 584 }
 585
 586 bool
 587 object::
 588 contains(
 589     string_view key) const noexcept
 590 {
 591     if(empty())
 592         return false;
 593     return find_impl(
 594         key).first != nullptr;
 595 }
 596
 597 value const*
 598 object::
 599 if_contains(
 600     string_view key) const noexcept
 601 {
 602     auto const it = find(key);
 603     if(it != end())
 604         return &it->value();
 605     return nullptr;
 606 }
 607
 608 value*
 609 object::
 610 if_contains(
 611     string_view key) noexcept
 612 {
 613     auto const it = find(key);
 614     if(it != end())
 615         return &it->value();
 616     return nullptr;
 617 }
 618
 619 //----------------------------------------------------------
 620 //
 621 // (private)
 622 //
 623 //----------------------------------------------------------
 624
 625 auto
 626 object::
 627 find_impl(
 628     string_view key) const noexcept ->
 629         std::pair<
 630             key_value_pair*,
 631             std::size_t>
 632 {
 633     BOOST_ASSERT(t_->capacity > 0);
 634     if(t_->is_small())
 635     {
 636         auto it = &(*t_)[0];
 637         auto const last =
 638             &(*t_)[t_->size];
 639         for(;it != last; ++it)
 640             if(key == it->key())
 641                 return { it, 0 };
 642         return { nullptr, 0 };
 643     }
 644     std::pair<
 645         key_value_pair*,
 646         std::size_t> result;
 647     result.second = t_->digest(key);
 648     auto i = t_->bucket(
 649         result.second);
 650     while(i != null_index_)
 651     {
 652         auto& v = (*t_)[i];
 653         if(v.key() == key)
 654         {
 655             result.first = &v;
 656             return result;
 657         }
 658         i = access::next(v);
 659     }
 660     result.first = nullptr;
 661     return result;
 662 }
 663
 664 auto
 665 object::
 666 insert_impl(
 667     pilfered<key_value_pair> p) ->
 668         std::pair<iterator, bool>
 669 {
 670     // caller is responsible
 671     // for preventing aliasing.
 672     reserve(size() + 1);
 673     auto const result =
 674         find_impl(p.get().key());
 675     if(result.first)
 676         return { result.first, false };
 677     return { insert_impl(
 678         p, result.second), true };
 679 }
 680
 681 key_value_pair*
 682 object::
 683 insert_impl(
 684     pilfered<key_value_pair> p,
 685     std::size_t hash)
 686 {
 687     BOOST_ASSERT(
 688         capacity() > size());
 689     if(t_->is_small())
 690     {
 691         auto const pv = ::new(end())
 692             key_value_pair(p);
 693         ++t_->size;
 694         return pv;
 695     }
 696     auto& head =
 697         t_->bucket(hash);
 698     auto const pv = ::new(end())
 699         key_value_pair(p);
 700     access::next(*pv) = head;
 701     head = t_->size;
 702     ++t_->size;
 703     return pv;
 704 }
 705
 706 // rehash to at least `n` buckets
 707 void
 708 object::
 709 rehash(std::size_t new_capacity)
 710 {
 711     BOOST_ASSERT(
 712         new_capacity > t_->capacity);
 713     auto t = table::allocate(
 714         growth(new_capacity),
 715             t_->salt, sp_);
 716     if(! empty())
 717         std::memcpy(
 718             static_cast<
 719                 void*>(&(*t)[0]),
 720             begin(),
 721             size() * sizeof(
 722                 key_value_pair));
 723     t->size = t_->size;
 724     table::deallocate(t_, sp_);
 725     t_ = t;
 726
 727     if(! t_->is_small())
 728     {
 729         // rebuild hash table,
 730         // without dup checks
 731         auto p = end();
 732         index_t i = t_->size;
 733         while(i-- > 0)
 734         {
 735             --p;
 736             auto& head =
 737                 t_->bucket(p->key());
 738             access::next(*p) = head;
 739             head = i;
 740         }
 741     }
 742 }
 743
 744 bool
 745 object::
 746 equal(object const& other) const noexcept
 747 {
 748     if(size() != other.size())
 749         return false;
 750     auto const end_ = other.end();
 751     for(auto e : *this)
 752     {
 753         auto it = other.find(e.key());
 754         if(it == end_)
 755             return false;
 756         if(it->value() != e.value())
 757             return false;
 758     }
 759     return true;
 760 }
 761
 762 std::size_t
 763 object::
 764 growth(
 765     std::size_t new_size) const
 766 {
 767     if(new_size > max_size())
 768         detail::throw_length_error(
 769             "object too large",
 770             BOOST_CURRENT_LOCATION);
 771     std::size_t const old = capacity();
 772     if(old > max_size() - old / 2)
 773         return new_size;
 774     std::size_t const g =
 775         old + old / 2; // 1.5x
 776     if(g < new_size)
 777         return new_size;
 778     return g;
 779 }
 780
 781 void
 782 object::
 783 remove(
 784     index_t& head,
 785     key_value_pair& v) noexcept
 786 {
 787     BOOST_ASSERT(! t_->is_small());
 788     auto const i = static_cast<
 789         index_t>(&v - begin());
 790     if(head == i)
 791     {
 792         head = access::next(v);
 793         return;
 794     }
 795     auto* pn =
 796         &access::next((*t_)[head]);
 797     while(*pn != i)
 798         pn = &access::next((*t_)[*pn]);
 799     *pn = access::next(v);
 800 }
 801
 802 void
 803 object::
 804 destroy() noexcept
 805 {
 806     BOOST_ASSERT(t_->capacity > 0);
 807     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
 808     destroy(begin(), end());
 809     table::deallocate(t_, sp_);
 810 }
 811
 812 void
 813 object::
 814 destroy(
 815     key_value_pair* first,
 816     key_value_pair* last) noexcept
 817 {
 818     BOOST_ASSERT(! sp_.is_not_shared_and_deallocate_is_trivial());
 819     while(last != first)
 820         (--last)->~key_value_pair();
 821 }
 822
 823 BOOST_JSON_NS_END
 824
 825 #endif