Sourcemeta Core 0.0.0
Loading...
Searching...
No Matches
json_object.h
1#ifndef SOURCEMETA_CORE_JSON_OBJECT_H_
2#define SOURCEMETA_CORE_JSON_OBJECT_H_
3
4#include <algorithm> // std::sort
5#include <cassert> // assert
6#include <concepts> // std::same_as
7#include <cstddef> // std::size_t
8#include <initializer_list> // std::initializer_list
9#include <iterator> // std::advance
10#include <string_view> // std::basic_string_view
11#include <type_traits> // std::remove_cvref_t
12#include <utility> // std::pair, std::move, std::unreachable
13#include <vector> // std::vector
14
15namespace sourcemeta::core {
16
19template <typename Key, typename Value, typename Hash> class JSONObject {
20public:
21 JSONObject() = default;
22
23 using key_type = Key;
24 using mapped_type = Value;
25 using hash_type = Hash::HashType;
26 using pair_value_type = std::pair<key_type, mapped_type>;
28 using KeyView = std::basic_string_view<typename Key::value_type,
29 typename Key::traits_type>;
30
32 JSONObject(std::initializer_list<pair_value_type> entries) : data_{} {
33 this->data_.reserve(entries.size());
34 for (auto &&entry : entries) {
35 this->emplace(std::move(entry.first), std::move(entry.second));
36 }
37 }
38
40 struct Entry {
42 key_type first;
44 mapped_type second;
46 hash_type hash;
47
62 [[nodiscard]] auto key_equals(const KeyView key,
63 const hash_type key_hash) const -> bool {
64 assert(JSONObject::hash(key) == key_hash);
65 // A perfect hash is unique for the key it was computed from, so
66 // matching it settles the comparison on its own
67 return this->hash == key_hash &&
68 (HASHER.is_perfect(key_hash) || this->first == key);
69 }
70 };
71
72 // A key and a value stand between one hash and the next, so a search over
73 // the hashes strides across a cache line per entry. Giving the hashes
74 // storage of their own, and nothing else, reads the same as this layout at
75 // eight and at thirty two entries, because the width of a hash holds the
76 // search back rather than the stride. Ruling out several candidates at once
77 // instead, over a narrow discriminator and without the branch that leaves
78 // on the first match, did read faster, by around a quarter of the search,
79 // but by less than the same timings move between runs on the machine they
80 // were taken on, so that one is open rather than refused
81 using underlying_type = std::vector<Entry>;
82 using value_type = underlying_type::value_type;
83 using size_type = underlying_type::size_type;
84 using difference_type = underlying_type::difference_type;
85 using allocator_type = underlying_type::allocator_type;
86 using reference = underlying_type::reference;
87 using const_reference = underlying_type::const_reference;
88 using pointer = underlying_type::pointer;
89 using const_pointer = underlying_type::const_pointer;
90 using const_iterator = underlying_type::const_iterator;
91
92 // Operators
93 // We cannot default given that this class references
94 // a JSON "value" as an incomplete type
95
96 auto operator<(const JSONObject<Key, Value, Hash> &other) const noexcept
97 -> bool {
98 // Objects have no inherent order, but a deterministic strict weak ordering
99 // independent of insertion order is needed so that collections of objects
100 // can be sorted. Smaller objects come first, and objects of equal size are
101 // ordered as their entries would compare in key order. That outcome is
102 // decided entirely by the smallest key at which the two objects differ,
103 // which is found by scanning the entries in place to avoid allocating
104 if (this->data_.size() != other.data_.size()) {
105 return this->data_.size() < other.data_.size();
106 }
107
108 const Key *decisive_key{nullptr};
109 bool decision{false};
110 for (const auto &entry : this->data_) {
111 const auto match{other.find(entry.first)};
112 const bool differs{match == other.cend() ||
113 !(entry.second == match->second)};
114 if (differs && (decisive_key == nullptr || entry.first < *decisive_key)) {
115 decisive_key = &entry.first;
116 decision = match == other.cend() || entry.second < match->second;
117 }
118 }
119
120 // A key named twice leaves both objects holding the same number of
121 // entries while naming a different number of keys, so the scan above can
122 // find nothing to disagree on and this one still settle the outcome
123 for (const auto &entry : other.data_) {
124 if (this->find(entry.first) == this->cend() &&
125 (decisive_key == nullptr || entry.first < *decisive_key)) {
126 decisive_key = &entry.first;
127 decision = false;
128 }
129 }
130
131 return decision;
132 }
133
134 auto operator<=(const JSONObject<Key, Value, Hash> &other) const noexcept
135 -> bool {
136 return !(other < *this);
137 }
138 auto operator>(const JSONObject<Key, Value, Hash> &other) const noexcept
139 -> bool {
140 return other < *this;
141 }
142 auto operator>=(const JSONObject<Key, Value, Hash> &other) const noexcept
143 -> bool {
144 return !(*this < other);
145 }
146
147 auto operator==(const JSONObject<Key, Value, Hash> &other) const noexcept
148 -> bool {
149 if (this->size() != other.size()) {
150 return false;
151 }
152
153 for (const auto &entry : this->data_) {
154 const auto *result{other.try_at(entry.first, entry.hash)};
155 if ((result == nullptr) || *result != entry.second) {
156 return false;
157 }
158 }
159
160 return true;
161 }
162
163 auto operator!=(const JSONObject<Key, Value, Hash> &other) const noexcept
164 -> bool = default;
165
166 [[nodiscard]] auto begin() const noexcept -> const_iterator {
167 return this->data_.begin();
168 }
170 [[nodiscard]] auto end() const noexcept -> const_iterator {
171 return this->data_.end();
172 }
174 [[nodiscard]] auto cbegin() const noexcept -> const_iterator {
175 return this->data_.cbegin();
176 }
178 [[nodiscard]] auto cend() const noexcept -> const_iterator {
179 return this->data_.cend();
180 }
181
182 // GCC does not optimise well across implicit type conversions such as
183 // std::string to std::string_view, so we provide separate overloads with
184 // duplicated logic instead of unifying on a single parameter type. The
185 // `KeyView`-accepting overloads are constrained to actual `std::string_view`
186 // arguments only, so callers passing a string literal continue to bind to
187 // the `Key`-accepting overload as before.
188
190 [[nodiscard]] static constexpr auto hash(const Key &key) noexcept
191 -> hash_type {
192 return HASHER(key);
193 }
194
196 template <typename T>
197 requires std::same_as<std::remove_cvref_t<T>, KeyView>
198 [[nodiscard]] static constexpr auto hash(T key) noexcept -> hash_type {
199 return HASHER(key.data(), key.size());
200 }
201
203 [[nodiscard]] static constexpr auto hash(const char *raw_data,
204 const std::size_t raw_size) noexcept
205 -> hash_type {
206 return HASHER(raw_data, raw_size);
207 }
208
210 [[nodiscard]] auto find(const Key &key) const -> const_iterator {
211 return this->find(key, this->hash(key));
212 }
213
215 template <typename T>
216 requires std::same_as<std::remove_cvref_t<T>, KeyView>
217 [[nodiscard]] auto find(T key) const -> const_iterator {
218 return this->find(key, this->hash(key));
219 }
220
238 [[nodiscard]] auto find(const Key &key, const hash_type key_hash) const
239 -> const_iterator {
240 assert(this->hash(key) == key_hash);
241
242 // Move the perfect hash condition out of the loop for extra performance
243 if (this->HASHER.is_perfect(key_hash)) {
244 for (size_type index = 0; index < this->size(); index++) {
245 if (this->data_[index].hash == key_hash) {
246 auto iterator{this->cbegin()};
247 std::advance(iterator, index);
248 return iterator;
249 }
250 }
251 } else {
252 for (size_type index = 0; index < this->size(); index++) {
253 if (this->data_[index].hash == key_hash &&
254 this->data_[index].first == key) {
255 auto iterator{this->cbegin()};
256 std::advance(iterator, index);
257 return iterator;
258 }
259 }
260 }
261
262 return this->cend();
263 }
264
268 template <typename T>
269 requires std::same_as<std::remove_cvref_t<T>, KeyView>
270 [[nodiscard]] auto find(T key, const hash_type key_hash) const
271 -> const_iterator {
272 assert(this->hash(key) == key_hash);
273
274 // Move the perfect hash condition out of the loop for extra performance
275 if (this->HASHER.is_perfect(key_hash)) {
276 for (size_type index = 0; index < this->size(); index++) {
277 if (this->data_[index].hash == key_hash) {
278 auto iterator{this->cbegin()};
279 std::advance(iterator, index);
280 return iterator;
281 }
282 }
283 } else {
284 for (size_type index = 0; index < this->size(); index++) {
285 if (this->data_[index].hash == key_hash &&
286 this->data_[index].first == key) {
287 auto iterator{this->cbegin()};
288 std::advance(iterator, index);
289 return iterator;
290 }
291 }
292 }
293
294 return this->cend();
295 }
296
298 [[nodiscard]] auto defines(const Key &key, const hash_type hash) const
299 -> bool {
300 assert(this->hash(key) == hash);
301
302 // Move the perfect hash condition out of the loop for extra performance
303 if (this->HASHER.is_perfect(hash)) {
304 for (const auto &entry : *this) {
305 if (entry.hash == hash) {
306 return true;
307 }
308 }
309 } else {
310 for (const auto &entry : *this) {
311 if (entry.hash == hash && entry.first == key) {
312 return true;
313 }
314 }
315 }
316
317 return false;
318 }
319
321 template <typename T>
322 requires std::same_as<std::remove_cvref_t<T>, KeyView>
323 [[nodiscard]] auto defines(T key, const hash_type hash) const -> bool {
324 assert(this->hash(key) == hash);
325
326 // Move the perfect hash condition out of the loop for extra performance
327 if (this->HASHER.is_perfect(hash)) {
328 for (const auto &entry : *this) {
329 if (entry.hash == hash) {
330 return true;
331 }
332 }
333 } else {
334 for (const auto &entry : *this) {
335 if (entry.hash == hash && entry.first == key) {
336 return true;
337 }
338 }
339 }
340
341 return false;
342 }
343
345 [[nodiscard]] auto size() const -> std::size_t { return this->data_.size(); }
346
348 [[nodiscard]] auto empty() const -> bool { return this->data_.empty(); }
349
351 auto reserve(const size_type capacity) -> void {
352 this->data_.reserve(capacity);
353 }
354
356 [[nodiscard]] auto at(const size_type index) const -> const Entry & {
357 assert(index < this->data_.size());
358 return this->data_[index];
359 }
360
362 [[nodiscard]] auto at(const Key &key, const hash_type key_hash) const
363 -> const mapped_type & {
364 assert(this->hash(key) == key_hash);
365
366 // Move the perfect hash condition out of the loop for extra performance
367 if (this->HASHER.is_perfect(key_hash)) {
368 for (const auto &entry : *this) {
369 if (entry.hash == key_hash) {
370 return entry.second;
371 }
372 }
373 } else {
374 for (const auto &entry : *this) {
375 if (entry.hash == key_hash && entry.first == key) {
376 return entry.second;
377 }
378 }
379 }
380
381 std::unreachable();
382 }
383
385 template <typename T>
386 requires std::same_as<std::remove_cvref_t<T>, KeyView>
387 [[nodiscard]] auto at(T key, const hash_type key_hash) const
388 -> const mapped_type & {
389 assert(this->hash(key) == key_hash);
390
391 // Move the perfect hash condition out of the loop for extra performance
392 if (this->HASHER.is_perfect(key_hash)) {
393 for (const auto &entry : *this) {
394 if (entry.hash == key_hash) {
395 return entry.second;
396 }
397 }
398 } else {
399 for (const auto &entry : *this) {
400 if (entry.hash == key_hash && entry.first == key) {
401 return entry.second;
402 }
403 }
404 }
405
406 std::unreachable();
407 }
408
410 auto at(const Key &key, const hash_type key_hash) -> mapped_type & {
411 assert(this->hash(key) == key_hash);
412
413 // Move the perfect hash condition out of the loop for extra performance
414 if (this->HASHER.is_perfect(key_hash)) {
415 for (auto &entry : this->data_) {
416 if (entry.hash == key_hash) {
417 return entry.second;
418 }
419 }
420 } else {
421 for (auto &entry : this->data_) {
422 if (entry.hash == key_hash && entry.first == key) {
423 return entry.second;
424 }
425 }
426 }
427
428 std::unreachable();
429 }
430
432 template <typename T>
433 requires std::same_as<std::remove_cvref_t<T>, KeyView>
434 auto at(T key, const hash_type key_hash) -> mapped_type & {
435 assert(this->hash(key) == key_hash);
436
437 // Move the perfect hash condition out of the loop for extra performance
438 if (this->HASHER.is_perfect(key_hash)) {
439 for (auto &entry : this->data_) {
440 if (entry.hash == key_hash) {
441 return entry.second;
442 }
443 }
444 } else {
445 for (auto &entry : this->data_) {
446 if (entry.hash == key_hash && entry.first == key) {
447 return entry.second;
448 }
449 }
450 }
451
452 std::unreachable();
453 }
454
456 [[nodiscard]] auto try_at(const Key &key, const hash_type key_hash)
457 -> mapped_type * {
458 assert(this->hash(key) == key_hash);
459
460 // Move the perfect hash condition out of the loop for extra performance
461 if (this->HASHER.is_perfect(key_hash)) {
462 for (auto &entry : this->data_) {
463 if (entry.hash == key_hash) {
464 return &entry.second;
465 }
466 }
467 } else {
468 for (auto &entry : this->data_) {
469 if (entry.hash == key_hash && entry.first == key) {
470 return &entry.second;
471 }
472 }
473 }
474
475 return nullptr;
476 }
477
479 template <typename T>
480 requires std::same_as<std::remove_cvref_t<T>, KeyView>
481 [[nodiscard]] auto try_at(T key, const hash_type key_hash) -> mapped_type * {
482 assert(this->hash(key) == key_hash);
483
484 // Move the perfect hash condition out of the loop for extra performance
485 if (this->HASHER.is_perfect(key_hash)) {
486 for (auto &entry : this->data_) {
487 if (entry.hash == key_hash) {
488 return &entry.second;
489 }
490 }
491 } else {
492 for (auto &entry : this->data_) {
493 if (entry.hash == key_hash && entry.first == key) {
494 return &entry.second;
495 }
496 }
497 }
498
499 return nullptr;
500 }
501
503 [[nodiscard]] auto try_at(const Key &key, const hash_type key_hash) const
504 -> const mapped_type * {
505 assert(this->hash(key) == key_hash);
506
507 // Move the perfect hash condition out of the loop for extra performance
508 if (this->HASHER.is_perfect(key_hash)) {
509 for (size_type index = 0; index < this->size(); index++) {
510 if (this->data_[index].hash == key_hash) {
511 return &this->data_[index].second;
512 }
513 }
514 } else {
515 for (size_type index = 0; index < this->size(); index++) {
516 if (this->data_[index].hash == key_hash &&
517 this->data_[index].first == key) {
518 return &this->data_[index].second;
519 }
520 }
521 }
522
523 return nullptr;
524 }
525
527 template <typename T>
528 requires std::same_as<std::remove_cvref_t<T>, KeyView>
529 [[nodiscard]] auto try_at(T key, const hash_type key_hash) const
530 -> const mapped_type * {
531 assert(this->hash(key) == key_hash);
532
533 // Move the perfect hash condition out of the loop for extra performance
534 if (this->HASHER.is_perfect(key_hash)) {
535 for (size_type index = 0; index < this->size(); index++) {
536 if (this->data_[index].hash == key_hash) {
537 return &this->data_[index].second;
538 }
539 }
540 } else {
541 for (size_type index = 0; index < this->size(); index++) {
542 if (this->data_[index].hash == key_hash &&
543 this->data_[index].first == key) {
544 return &this->data_[index].second;
545 }
546 }
547 }
548
549 return nullptr;
550 }
551
554 [[nodiscard]] auto try_at(const Key &key, const hash_type key_hash,
555 size_type &start) const -> const mapped_type * {
556 assert(this->hash(key) == key_hash);
557 const auto object_size{this->size()};
558 const auto scan_start{start};
559 assert(scan_start <= object_size);
560 // The scan runs from where the caller left off to the end and then wraps
561 // around up to that point, which two straight loops express without the
562 // integer division per probe that indexing through a modulo needs
563 if (this->HASHER.is_perfect(key_hash)) {
564 for (size_type index = scan_start; index < object_size; index++) {
565 if (this->data_[index].hash == key_hash) {
566 start = index + 1;
567 return &this->data_[index].second;
568 }
569 }
570
571 for (size_type index = 0; index < scan_start; index++) {
572 if (this->data_[index].hash == key_hash) {
573 start = index + 1;
574 return &this->data_[index].second;
575 }
576 }
577 } else {
578 for (size_type index = scan_start; index < object_size; index++) {
579 if (this->data_[index].hash == key_hash &&
580 this->data_[index].first == key) {
581 start = index + 1;
582 return &this->data_[index].second;
583 }
584 }
585
586 for (size_type index = 0; index < scan_start; index++) {
587 if (this->data_[index].hash == key_hash &&
588 this->data_[index].first == key) {
589 start = index + 1;
590 return &this->data_[index].second;
591 }
592 }
593 }
594
595 return nullptr;
596 }
597
600 template <typename T>
601 requires std::same_as<std::remove_cvref_t<T>, KeyView>
602 [[nodiscard]] auto try_at(T key, const hash_type key_hash,
603 size_type &start) const -> const mapped_type * {
604 assert(this->hash(key) == key_hash);
605 const auto object_size{this->size()};
606 const auto scan_start{start};
607 assert(scan_start <= object_size);
608 // The scan runs from where the caller left off to the end and then wraps
609 // around up to that point, which two straight loops express without the
610 // integer division per probe that indexing through a modulo needs
611 if (this->HASHER.is_perfect(key_hash)) {
612 for (size_type index = scan_start; index < object_size; index++) {
613 if (this->data_[index].hash == key_hash) {
614 start = index + 1;
615 return &this->data_[index].second;
616 }
617 }
618
619 for (size_type index = 0; index < scan_start; index++) {
620 if (this->data_[index].hash == key_hash) {
621 start = index + 1;
622 return &this->data_[index].second;
623 }
624 }
625 } else {
626 for (size_type index = scan_start; index < object_size; index++) {
627 if (this->data_[index].hash == key_hash &&
628 this->data_[index].first == key) {
629 start = index + 1;
630 return &this->data_[index].second;
631 }
632 }
633
634 for (size_type index = 0; index < scan_start; index++) {
635 if (this->data_[index].hash == key_hash &&
636 this->data_[index].first == key) {
637 start = index + 1;
638 return &this->data_[index].second;
639 }
640 }
641 }
642
643 return nullptr;
644 }
645
647 auto try_emplace_before(const Key &key, const mapped_type &value,
648 const Key &suffix) -> hash_type {
649 const auto key_hash{this->hash(key)};
650 const auto suffix_hash{this->hash(suffix)};
651
652 // The suffix can precede the key, so inserting on the first sight of it
653 // would add a second entry under a key the object already holds. The whole
654 // object is scanned for the key instead, remembering where the suffix sat,
655 // which keeps this to the single pass the caller pays for either way
656 auto insertion_point{this->data_.end()};
657
658 if (this->HASHER.is_perfect(key_hash)) {
659 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
660 ++iterator) {
661 if (iterator->hash == key_hash) {
662 iterator->second = value;
663 return key_hash;
664 }
665 if (insertion_point == this->data_.end() &&
666 iterator->hash == suffix_hash && iterator->first == suffix) {
667 insertion_point = iterator;
668 }
669 }
670 } else {
671 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
672 ++iterator) {
673 if (iterator->hash == key_hash && iterator->first == key) {
674 iterator->second = value;
675 return key_hash;
676 }
677 if (insertion_point == this->data_.end() &&
678 iterator->hash == suffix_hash && iterator->first == suffix) {
679 insertion_point = iterator;
680 }
681 }
682 }
683
684 this->data_.insert(insertion_point, {key, value, key_hash});
685 return key_hash;
686 }
687
689 auto emplace(Key &&key, mapped_type &&value) -> hash_type {
690 const auto key_hash{this->hash(key)};
691
692 if (this->HASHER.is_perfect(key_hash)) {
693 for (auto &entry : this->data_) {
694 if (entry.hash == key_hash) {
695 entry.second = std::move(value);
696 return key_hash;
697 }
698 }
699 } else {
700 for (auto &entry : this->data_) {
701 if (entry.hash == key_hash && entry.first == key) {
702 entry.second = std::move(value);
703 return key_hash;
704 }
705 }
706 }
707
708 this->data_.push_back({std::move(key), std::move(value), key_hash});
709 return key_hash;
710 }
711
713 auto emplace(const Key &key, mapped_type &&value) -> hash_type {
714 const auto key_hash{this->hash(key)};
715
716 if (this->HASHER.is_perfect(key_hash)) {
717 for (auto &entry : this->data_) {
718 if (entry.hash == key_hash) {
719 entry.second = std::move(value);
720 return key_hash;
721 }
722 }
723 } else {
724 for (auto &entry : this->data_) {
725 if (entry.hash == key_hash && entry.first == key) {
726 entry.second = std::move(value);
727 return key_hash;
728 }
729 }
730 }
731
732 this->data_.push_back({key, std::move(value), key_hash});
733 return key_hash;
734 }
735
737 auto emplace(const Key &key, const mapped_type &value) -> hash_type {
738 const auto key_hash{this->hash(key)};
739
740 if (this->HASHER.is_perfect(key_hash)) {
741 for (auto &entry : this->data_) {
742 if (entry.hash == key_hash) {
743 entry.second = value;
744 return key_hash;
745 }
746 }
747 } else {
748 for (auto &entry : this->data_) {
749 if (entry.hash == key_hash && entry.first == key) {
750 entry.second = value;
751 return key_hash;
752 }
753 }
754 }
755
756 this->data_.push_back({key, value, key_hash});
757 return key_hash;
758 }
759
761 auto emplace_assume_new(Key &&key, mapped_type &&value) -> hash_type {
762 const auto key_hash{this->hash(key)};
763 this->data_.push_back({std::move(key), std::move(value), key_hash});
764 return key_hash;
765 }
766
768 auto emplace_assume_new(const Key &key, mapped_type &&value) -> hash_type {
769 const auto key_hash{this->hash(key)};
770 this->data_.push_back({key, std::move(value), key_hash});
771 return key_hash;
772 }
773
776 auto emplace_assume_new(Key &&key, mapped_type &&value,
777 const hash_type key_hash) -> mapped_type & {
778 this->data_.push_back({std::move(key), std::move(value), key_hash});
779 return this->data_.back().second;
780 }
781
783 auto emplace_assume_new(const Key &key, mapped_type &&value,
784 const hash_type key_hash) -> void {
785 this->data_.push_back({key, std::move(value), key_hash});
786 }
787
789 [[nodiscard]] auto back_key() const noexcept -> const Key & {
790 assert(!this->data_.empty());
791 return this->data_.back().first;
792 }
793
795 auto clear() noexcept -> void { this->data_.clear(); }
796
798 // Both hashes come in by value, as dropping the target property first can
799 // shift the storage that a caller's reference points into, and the rename
800 // would then record a hash belonging to another property
801 auto rename(const Key &key, const hash_type key_hash, Key &&target,
802 const hash_type target_hash) -> void {
803 this->erase(target, target_hash);
804
805 if (this->HASHER.is_perfect(key_hash)) {
806 for (auto &entry : this->data_) {
807 if (entry.hash == key_hash) {
808 entry.first = std::move(target);
809 entry.hash = target_hash;
810 break;
811 }
812 }
813 } else {
814 for (auto &entry : this->data_) {
815 if (entry.hash == key_hash && entry.first == key) {
816 entry.first = std::move(target);
817 entry.hash = target_hash;
818 break;
819 }
820 }
821 }
822 }
823
825 auto erase(const Key &key, const hash_type key_hash) -> size_type {
826 assert(this->hash(key) == key_hash);
827 const auto current_size{this->size()};
828
829 if (this->HASHER.is_perfect(key_hash)) {
830 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
831 ++iterator) {
832 if (iterator->hash == key_hash) {
833 this->data_.erase(iterator);
834 return current_size - 1;
835 }
836 }
837 } else {
838 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
839 ++iterator) {
840 if (iterator->hash == key_hash && iterator->first == key) {
841 this->data_.erase(iterator);
842 return current_size - 1;
843 }
844 }
845 }
846
847 return current_size;
848 }
849
851 template <typename T>
852 requires std::same_as<std::remove_cvref_t<T>, KeyView>
853 auto erase(T key, const hash_type key_hash) -> size_type {
854 assert(this->hash(key) == key_hash);
855 const auto current_size{this->size()};
856
857 if (this->HASHER.is_perfect(key_hash)) {
858 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
859 ++iterator) {
860 if (iterator->hash == key_hash) {
861 this->data_.erase(iterator);
862 return current_size - 1;
863 }
864 }
865 } else {
866 for (auto iterator = this->data_.begin(); iterator != this->data_.end();
867 ++iterator) {
868 if (iterator->hash == key_hash && iterator->first == key) {
869 this->data_.erase(iterator);
870 return current_size - 1;
871 }
872 }
873 }
874
875 return current_size;
876 }
877
879 auto erase(const Key &key) -> size_type {
880 return this->erase(key, this->hash(key));
881 }
882
884 template <typename T>
885 requires std::same_as<std::remove_cvref_t<T>, KeyView>
886 auto erase(T key) -> size_type {
887 return this->erase(key, this->hash(key));
888 }
889
891 template <typename Compare> auto reorder(const Compare &compare) -> void {
892 std::sort(this->data_.begin(), this->data_.end(),
893 [&compare](const auto &left, const auto &right) -> auto {
894 return compare(left.first, right.first);
895 });
896 }
897
898private:
899 friend Value;
900// Exporting symbols that depends on the standard C++ library is considered
901// safe.
902// https://learn.microsoft.com/en-us/cpp/error-messages/compiler-warnings/compiler-warning-level-2-c4275?view=msvc-170&redirectedfrom=MSDN
903#if defined(_MSC_VER)
904#pragma warning(push)
905#pragma warning(disable : 4251)
906#endif
907 static constexpr Hash HASHER{};
908 underlying_type data_;
909#if defined(_MSC_VER)
910#pragma warning(pop)
911#endif
912};
913
914} // namespace sourcemeta::core
915
916#endif
static constexpr auto hash(const Key &key) noexcept -> hash_type
Compute a hash for a key.
Definition json_object.h:190
auto emplace_assume_new(Key &&key, mapped_type &&value) -> hash_type
Emplace an object property assuming the key does not already exist.
Definition json_object.h:761
auto try_at(T key, const hash_type key_hash, size_type &start) const -> const mapped_type *
Definition json_object.h:602
auto clear() noexcept -> void
Remove every property in the object.
Definition json_object.h:795
auto try_at(const Key &key, const hash_type key_hash) const -> const mapped_type *
Try to access an object entry by its underlying positional index.
Definition json_object.h:503
auto at(T key, const hash_type key_hash) const -> const mapped_type &
Access an object entry by its key name.
Definition json_object.h:387
auto at(const size_type index) const -> const Entry &
Access an object entry by its underlying positional index.
Definition json_object.h:356
auto reserve(const size_type capacity) -> void
Reserve capacity for a given number of entries.
Definition json_object.h:351
auto try_at(const Key &key, const hash_type key_hash) -> mapped_type *
Try to access an object entry by its key name.
Definition json_object.h:456
auto emplace(String &&key, mapped_type &&value) -> hash_type
Definition json_object.h:689
static constexpr auto hash(const char *raw_data, const std::size_t raw_size) noexcept -> hash_type
Compute a hash from raw data.
Definition json_object.h:203
auto emplace(const Key &key, const mapped_type &value) -> hash_type
Emplace an object property.
Definition json_object.h:737
auto empty() const -> bool
Check if the object is empty.
Definition json_object.h:348
auto try_emplace_before(const Key &key, const mapped_type &value, const Key &suffix) -> hash_type
Try to emplace a property before another property.
Definition json_object.h:647
auto at(T key, const hash_type key_hash) -> mapped_type &
Access an object entry by its key name.
Definition json_object.h:434
auto find(T key) const -> const_iterator
Attempt to find an entry by key.
Definition json_object.h:217
static constexpr auto hash(T key) noexcept -> hash_type
Compute a hash for a key.
Definition json_object.h:198
auto reorder(const Compare &compare) -> void
Reorder object properties by keys according to a comparator function.
Definition json_object.h:891
auto try_at(T key, const hash_type key_hash) -> mapped_type *
Try to access an object entry by its key name.
Definition json_object.h:481
auto defines(const Key &key, const hash_type hash) const -> bool
Check if an entry with the given key exists.
Definition json_object.h:298
auto find(const Key &key, const hash_type key_hash) const -> const_iterator
Definition json_object.h:238
auto erase(const Key &key) -> size_type
Erase an object property.
Definition json_object.h:879
auto find(const Key &key) const -> const_iterator
Attempt to find an entry by key.
Definition json_object.h:210
auto at(const Key &key, const hash_type key_hash) const -> const mapped_type &
Access an object entry by its key name.
Definition json_object.h:362
auto emplace_assume_new(Key &&key, mapped_type &&value, const hash_type key_hash) -> mapped_type &
Definition json_object.h:776
JSONObject(std::initializer_list< pair_value_type > entries)
Construct an object from a list of key and value pairs.
Definition json_object.h:32
auto emplace_assume_new(const Key &key, mapped_type &&value, const hash_type key_hash) -> void
Emplace an object property with a pre-computed hash.
Definition json_object.h:783
auto erase(T key) -> size_type
Erase an object property.
Definition json_object.h:886
auto try_at(T key, const hash_type key_hash) const -> const mapped_type *
Try to access an object entry by its underlying positional index.
Definition json_object.h:529
auto back_key() const noexcept -> const Key &
Get the key of the last-inserted property.
Definition json_object.h:789
auto emplace_assume_new(const Key &key, mapped_type &&value) -> hash_type
Emplace an object property assuming the key does not already exist.
Definition json_object.h:768
auto at(const Key &key, const hash_type key_hash) -> mapped_type &
Access an object entry by its key name.
Definition json_object.h:410
auto defines(T key, const hash_type hash) const -> bool
Check if an entry with the given key exists.
Definition json_object.h:323
auto rename(const Key &key, const hash_type key_hash, Key &&target, const hash_type target_hash) -> void
Rename an object property in place.
Definition json_object.h:801
std::basic_string_view< typename Key::value_type, typename Key::traits_type > KeyView
The string view type used to look up object keys.
Definition json_object.h:28
auto size() const -> std::size_t
Check the size of the object.
Definition json_object.h:345
auto erase(const String &key, const hash_type key_hash) -> size_type
Definition json_object.h:825
auto erase(T key, const hash_type key_hash) -> size_type
Erase an object property.
Definition json_object.h:853
auto try_at(const Key &key, const hash_type key_hash, size_type &start) const -> const mapped_type *
Definition json_object.h:554
auto emplace(const Key &key, mapped_type &&value) -> hash_type
Emplace an object property.
Definition json_object.h:713
auto find(T key, const hash_type key_hash) const -> const_iterator
Definition json_object.h:270
Definition json_object.h:19
A single object property entry.
Definition json_object.h:40
mapped_type second
The property value.
Definition json_object.h:44
auto key_equals(const KeyView key, const hash_type key_hash) const -> bool
Definition json_object.h:62
hash_type hash
The precomputed hash of the property key.
Definition json_object.h:46
key_type first
The property key.
Definition json_object.h:42