diff options
author | Shawn Willden <swillden@google.com> | 2020-12-01 22:53:33 +0000 |
---|---|---|
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | 2020-12-01 22:53:33 +0000 |
commit | 897d2b0bfd2c42d40e84b602ac2dc05b4d8e5d47 (patch) | |
tree | 49b51e493facf5c43a711284e34811dd0f984730 | |
parent | 2a1a25d6aff301b32e7904a0869364a0372c02c5 (diff) | |
parent | afec41111894a5a5b5ed4db40429aa8a47f157d8 (diff) | |
download | libcppbor-897d2b0bfd2c42d40e84b602ac2dc05b4d8e5d47.tar.gz |
Improve Map sorting performance. am: d613c9aa81 am: 4f9010ce6f am: afec411118
Original change: https://android-review.googlesource.com/c/platform/external/libcppbor/+/1515379
Change-Id: I28b1471677e36f36d42aff6f22e4079c02eca0cc
-rw-r--r-- | src/cppbor.cpp | 22 |
1 files changed, 13 insertions, 9 deletions
diff --git a/src/cppbor.cpp b/src/cppbor.cpp index e644840..50e98ca 100644 --- a/src/cppbor.cpp +++ b/src/cppbor.cpp @@ -395,20 +395,24 @@ void Map::assertInvariant() const { CHECK(mEntries.size() % 2 == 0); } -bool mapKeyLess(const std::pair<std::unique_ptr<Item>&, std::unique_ptr<Item>&>& a, - const std::pair<std::unique_ptr<Item>&, std::unique_ptr<Item>&>& b) { - auto keyA = a.first->encode(); - auto keyB = b.first->encode(); +bool mapKeyLess(const std::pair<std::unique_ptr<Item>, std::unique_ptr<Item>>& a, + const std::pair<std::unique_ptr<Item>, std::unique_ptr<Item>>& b) { + auto& keyA = a.first; + auto& keyB = b.first; // CBOR map canonicalization rules are: // 1. If two keys have different lengths, the shorter one sorts earlier. - if (keyA.size() < keyB.size()) return true; - if (keyA.size() > keyB.size()) return false; + if (keyA->encodedSize() < keyB->encodedSize()) return true; + if (keyA->encodedSize() > keyB->encodedSize()) return false; - // 2. If two keys have the same length, the one with the lower value in - // (byte-wise) lexical order sorts earlier. - return std::lexicographical_compare(keyA.begin(), keyA.end(), keyB.begin(), keyB.end()); + // 2. If two keys have the same length, the one with the lower value in (byte-wise) lexical + // order sorts earlier. This requires encoding both items. + auto encodedA = keyA->encode(); + auto encodedB = keyB->encode(); + + return std::lexicographical_compare(encodedA.begin(), encodedA.end(), // + encodedB.begin(), encodedB.end()); } Map& Map::canonicalize() & { |