From bc6ebff07e303e6739130a540f44704f0c1acffb Mon Sep 17 00:00:00 2001 From: Gil Date: Tue, 24 Apr 2018 10:24:32 -0700 Subject: Add key-only projections to immutable C++ maps (#1166) * Add a simple range adapter. * Add SortedMap::keys * Add SortedMap::keys_from * Add SortedMap::keys_in --- .../firebase/firestore/immutable/CMakeLists.txt | 1 + .../firestore/immutable/array_sorted_map.h | 62 +++++++++++++--- .../src/firebase/firestore/immutable/keys_view.h | 86 ++++++++++++++++++++++ .../src/firebase/firestore/immutable/sorted_map.h | 61 ++++++++++++++- .../firebase/firestore/immutable/tree_sorted_map.h | 50 +++++++++++-- .../src/firebase/firestore/util/CMakeLists.txt | 1 + .../firebase/firestore/util/comparator_holder.h | 2 + Firestore/core/src/firebase/firestore/util/range.h | 78 ++++++++++++++++++++ .../firestore/immutable/sorted_map_test.cc | 60 +++++++++++++++ 9 files changed, 380 insertions(+), 21 deletions(-) create mode 100644 Firestore/core/src/firebase/firestore/immutable/keys_view.h create mode 100644 Firestore/core/src/firebase/firestore/util/range.h (limited to 'Firestore/core') diff --git a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt index accf5c5..90ce204 100644 --- a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt @@ -16,6 +16,7 @@ cc_library( firebase_firestore_immutable SOURCES array_sorted_map.h + keys_view.h llrb_node.h llrb_node_iterator.h map_entry.h diff --git a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h index 487a25a..db53969 100644 --- a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h @@ -24,10 +24,12 @@ #include #include +#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h" #include "Firestore/core/src/firebase/firestore/immutable/map_entry.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h" #include "Firestore/core/src/firebase/firestore/util/comparison.h" #include "Firestore/core/src/firebase/firestore/util/firebase_assert.h" +#include "Firestore/core/src/firebase/firestore/util/range.h" namespace firebase { namespace firestore { @@ -133,6 +135,7 @@ class ArraySortedMap : public SortedMapBase { */ using array_type = FixedArray; using const_iterator = typename array_type::const_iterator; + using const_key_iterator = util::iterator_first; using array_pointer = std::shared_ptr; @@ -162,8 +165,8 @@ class ArraySortedMap : public SortedMapBase { return array_->size(); } - const key_comparator_type& comparator() const { - return key_comparator_; + const C& comparator() const { + return key_comparator_.comparator(); } /** @@ -176,12 +179,12 @@ class ArraySortedMap : public SortedMapBase { */ ArraySortedMap insert(const K& key, const V& value) const { const_iterator current_end = end(); - const_iterator pos = LowerBound(key); + const_iterator pos = lower_bound(key); bool replacing_entry = false; if (pos != current_end) { - // LowerBound found an entry where pos->first >= pair.first. Reversing the - // argument order here tests pair.first < pos->first. + // lower_bound found an entry where pos->first >= pair.first. Reversing + // the argument order here tests pair.first < pos->first. replacing_entry = !key_comparator_(key, *pos); if (replacing_entry && value == pos->second) { return *this; @@ -239,9 +242,9 @@ class ArraySortedMap : public SortedMapBase { */ const_iterator find(const K& key) const { const_iterator not_found = end(); - const_iterator lower_bound = LowerBound(key); - if (lower_bound != not_found && !key_comparator_(key, *lower_bound)) { - return lower_bound; + const_iterator bound = lower_bound(key); + if (bound != not_found && !key_comparator_(key, *bound)) { + return bound; } else { return not_found; } @@ -258,6 +261,19 @@ class ArraySortedMap : public SortedMapBase { return found == end() ? npos : static_cast(found - begin()); } + /** + * Finds the first entry in the map containing a key greater than or equal + * to the given key. + * + * @param key The key to look up. + * @return An iterator pointing to the entry containing the key or the next + * largest key. Can return end() if all keys in the map are less than the + * requested key. + */ + const_iterator lower_bound(const K& key) const { + return std::lower_bound(begin(), end(), key, key_comparator_); + } + const_iterator min() const { return begin(); } @@ -285,6 +301,32 @@ class ArraySortedMap : public SortedMapBase { return array_->end(); } + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted. + */ + const util::range keys() const { + return KeysView(*this); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given key. + */ + const util::range keys_from(const K& key) const { + return KeysViewFrom(*this, key); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given start_key and less + * than the given end_key. + */ + const util::range keys_in(const K& start_key, + const K& end_key) const { + return impl::KeysViewIn(*this, start_key, end_key, comparator()); + } + private: static array_pointer EmptyArray() { static const array_pointer kEmptyArray = @@ -301,10 +343,6 @@ class ArraySortedMap : public SortedMapBase { return ArraySortedMap{array, key_comparator_}; } - const_iterator LowerBound(const K& key) const { - return std::lower_bound(begin(), end(), key, key_comparator_); - } - array_pointer array_; key_comparator_type key_comparator_; }; diff --git a/Firestore/core/src/firebase/firestore/immutable/keys_view.h b/Firestore/core/src/firebase/firestore/immutable/keys_view.h new file mode 100644 index 0000000..6cf04b6 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/immutable/keys_view.h @@ -0,0 +1,86 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_ + +#include + +#include "Firestore/core/src/firebase/firestore/util/iterator_adaptors.h" +#include "Firestore/core/src/firebase/firestore/util/range.h" + +namespace firebase { +namespace firestore { +namespace immutable { +namespace impl { + +template +using KeysRange = util::range>; + +template +KeysRange MakeKeysRange(Iterator begin, Iterator end) { + auto keys_begin = util::make_iterator_first(begin); + auto keys_end = util::make_iterator_first(end); + return util::make_range(keys_begin, keys_end); +} + +/** + * Returns a view of the keys of the given key-value range. + */ +template +auto KeysView(const Range& range) -> KeysRange { + return MakeKeysRange(std::begin(range), std::end(range)); +} + +template +auto KeysViewFrom(const Range& range, const K& key) + -> KeysRange { + auto keys_begin = util::make_iterator_first(range.lower_bound(key)); + auto keys_end = util::make_iterator_first(std::end(range)); + return util::make_range(keys_begin, keys_end); +} + +/** + * Returns a view of keys of the given key-value range that are greater than or + * equal to the given start_key and less than the given end_key. + * + * If `end_key` is less than or equal to `start_key`, creates empty range. + */ +template +auto KeysViewIn(const Range& range, + const K& start_key, + const K& end_key, + const C& comparator) + -> KeysRange { + // Forward iterators can't ever reach the end if the end is behind the start: + // they just keep incrementing until address space runs out. Adjust the range + // accordingly. + bool empty_range = !comparator(start_key, end_key); + if (empty_range) { + return MakeKeysRange(std::end(range), std::end(range)); + } + + auto range_begin = range.lower_bound(start_key); + auto range_end = range.lower_bound(end_key); + return MakeKeysRange(std::move(range_begin), std::move(range_end)); +} + +} // namespace impl +} // namespace immutable +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_ diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h index 6f4d91b..647bab0 100644 --- a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h @@ -20,6 +20,7 @@ #include #include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h" +#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h" #include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h" @@ -46,6 +47,8 @@ class SortedMap : public impl::SortedMapBase { typename impl::FixedArray::const_iterator, typename impl::LlrbNode::const_iterator>; + using const_key_iterator = util::iterator_first; + /** * Creates an empty SortedMap. */ @@ -173,8 +176,7 @@ class SortedMap : public impl::SortedMapBase { // exactly where this cut-off happens and just unconditionally // converting if the next insertion could overflow keeps things // simpler. - const C& comparator = array_.comparator().comparator(); - tree_type tree = tree_type::Create(array_, comparator); + tree_type tree = tree_type::Create(array_, comparator()); return SortedMap{tree.insert(key, value)}; } else { return SortedMap{array_.insert(key, value)}; @@ -249,6 +251,25 @@ class SortedMap : public impl::SortedMapBase { FIREBASE_UNREACHABLE(); } + /** + * Finds the first entry in the map containing a key greater than or equal + * to the given key. + * + * @param key The key to look up. + * @return An iterator pointing to the entry containing the key or the next + * largest key. Can return end() if all keys in the map are less than the + * requested key. + */ + const_iterator lower_bound(const K& key) const { + switch (tag_) { + case Tag::Array: + return const_iterator(array_.lower_bound(key)); + case Tag::Tree: + return const_iterator{tree_.lower_bound(key)}; + } + FIREBASE_UNREACHABLE(); + } + const_iterator min() const { switch (tag_) { case Tag::Array: @@ -296,6 +317,32 @@ class SortedMap : public impl::SortedMapBase { FIREBASE_UNREACHABLE(); } + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted. + */ + const util::range keys() const { + return impl::KeysView(*this); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given key. + */ + const util::range keys_from(const K& key) const { + return impl::KeysViewFrom(*this, key); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given start_key and less + * than the given end_key. + */ + const util::range keys_in(const K& start_key, + const K& end_key) const { + return impl::KeysViewIn(*this, start_key, end_key, comparator()); + } + private: explicit SortedMap(array_type&& array) : tag_{Tag::Array}, array_{std::move(array)} { @@ -305,6 +352,16 @@ class SortedMap : public impl::SortedMapBase { : tag_{Tag::Tree}, tree_{std::move(tree)} { } + const C& comparator() const { + switch (tag_) { + case Tag::Array: + return array_.comparator(); + case Tag::Tree: + return tree_.comparator(); + } + FIREBASE_UNREACHABLE(); + } + enum class Tag { Array, Tree, diff --git a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h index 609b9da..9fd51c3 100644 --- a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h +++ b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h @@ -23,12 +23,12 @@ #include #include +#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h" #include "Firestore/core/src/firebase/firestore/immutable/llrb_node.h" #include "Firestore/core/src/firebase/firestore/immutable/map_entry.h" #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h" #include "Firestore/core/src/firebase/firestore/util/comparator_holder.h" #include "Firestore/core/src/firebase/firestore/util/comparison.h" -#include "Firestore/core/src/firebase/firestore/util/iterator_adaptors.h" namespace firebase { namespace firestore { @@ -40,7 +40,7 @@ namespace impl { * methods to efficiently create new maps that are mutations of it. */ template > -class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { +class TreeSortedMap : public SortedMapBase, public util::ComparatorHolder { public: /** * The type of the entries stored in the map. @@ -52,6 +52,7 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { */ using node_type = LlrbNode; using const_iterator = typename node_type::const_iterator; + using const_key_iterator = util::iterator_first; /** * Creates an empty TreeSortedMap. @@ -136,7 +137,7 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { * not found. */ const_iterator find(const K& key) const { - const_iterator found = LowerBound(key); + const_iterator found = lower_bound(key); if (!found.is_end() && !this->comparator()(key, found->first)) { return found; } else { @@ -171,6 +172,19 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { return npos; } + /** + * Finds the first entry in the map containing a key greater than or equal + * to the given key. + * + * @param key The key to look up. + * @return An iterator pointing to the entry containing the key or the next + * largest key. Can return end() if all keys in the map are less than the + * requested key. + */ + const_iterator lower_bound(const K& key) const { + return const_iterator::LowerBound(&root_, key, this->comparator()); + } + const_iterator min() const { return begin(); } @@ -203,15 +217,37 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder { return const_iterator::End(); } + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted. + */ + const util::range keys() const { + return KeysView(*this); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given key. + */ + const util::range keys_from(const K& key) const { + return KeysViewFrom(*this, key); + } + + /** + * Returns a view of this SortedMap containing just the keys that have been + * inserted that are greater than or equal to the given start_key and less + * than the given end_key. + */ + const util::range keys_in(const K& start_key, + const K& end_key) const { + return impl::KeysViewIn(*this, start_key, end_key, this->comparator()); + } + private: TreeSortedMap(node_type&& root, const C& comparator) noexcept : util::ComparatorHolder{comparator}, root_{std::move(root)} { } - const_iterator LowerBound(const K& key) const noexcept { - return const_iterator::LowerBound(&root_, key, this->comparator()); - } - TreeSortedMap Wrap(node_type&& root) noexcept { return TreeSortedMap{std::move(root), this->comparator()}; } diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt index 701d288..3afead1 100644 --- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt +++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt @@ -131,6 +131,7 @@ cc_library( iterator_adaptors.h ordered_code.cc ordered_code.h + range.h secure_random.h status.cc status.h diff --git a/Firestore/core/src/firebase/firestore/util/comparator_holder.h b/Firestore/core/src/firebase/firestore/util/comparator_holder.h index c7f6144..3147117 100644 --- a/Firestore/core/src/firebase/firestore/util/comparator_holder.h +++ b/Firestore/core/src/firebase/firestore/util/comparator_holder.h @@ -35,6 +35,7 @@ class ComparatorHolder { : comparator_(comparator) { } + public: const C& comparator() const noexcept { return comparator_; } @@ -50,6 +51,7 @@ class ComparatorHolder : private C { explicit ComparatorHolder(const C& /* comparator */) noexcept { } + public: const C& comparator() const noexcept { return *this; } diff --git a/Firestore/core/src/firebase/firestore/util/range.h b/Firestore/core/src/firebase/firestore/util/range.h new file mode 100644 index 0000000..9e96c67 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/util/range.h @@ -0,0 +1,78 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_ + +#include +#include + +namespace firebase { +namespace firestore { +namespace util { + +/** + * Adapts a pair of iterators into a range suitable for use with range-based + * for loops. + */ +template +class range { + public: + using value_type = typename std::iterator_traits::value_type; + using iterator = Iterator; + using const_iterator = Iterator; + + /** + * Default range which constructs default begin and end pointers. For most + * implementations where the end pointer is a null pointer or some other + * default value, this ends up constructing the empty range. + */ + range() : begin_{}, end_{} { + } + + /** + * Creates a half-open range starting from begin up to, but not including end. + */ + range(iterator&& begin, iterator&& end) + : begin_{std::move(begin)}, end_{std::move(end)} { + } + + iterator begin() const { + return begin_; + } + + iterator end() const { + return end_; + } + + private: + Iterator begin_; + Iterator end_; +}; + +/** + * Creates ranges with type deduction. + */ +template +range make_range(Iterator begin, Iterator end) { + return range{std::move(begin), std::move(end)}; +} + +} // namespace util +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_ diff --git a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc index 25332c2..bcacb50 100644 --- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -403,6 +403,66 @@ TYPED_TEST(SortedMapTest, IteratorInvalidation) { ASSERT_EQ(size, result.size()); } +TYPED_TEST(SortedMapTest, KeyIterator) { + std::vector all = Sequence(this->large_number()); + TypeParam map = ToMap(Shuffled(all)); + + auto begin = map.keys().begin(); + ASSERT_EQ(0, *begin); + + auto end = map.keys().end(); + ASSERT_EQ(all.size(), static_cast(std::distance(begin, end))); + + ASSERT_SEQ_EQ(all, map.keys()); +} + +TYPED_TEST(SortedMapTest, KeysFrom) { + std::vector all = Sequence(2, 42, 2); + TypeParam map = ToMap(Shuffled(all)); + ASSERT_EQ(20u, map.size()); + + // Test from before keys. + ASSERT_SEQ_EQ(all, map.keys_from(0)); + + // Test from after keys. + ASSERT_SEQ_EQ(Empty(), map.keys_from(100)); + + // Test from a key in the map: should start at that key. + ASSERT_SEQ_EQ(Sequence(10, 42, 2), map.keys_from(10)); + + // Test from in between keys: should start just after that key. + ASSERT_SEQ_EQ(Sequence(12, 42, 2), map.keys_from(11)); +} + +TYPED_TEST(SortedMapTest, KeysIn) { + std::vector all = Sequence(2, 42, 2); + TypeParam map = ToMap(Shuffled(all)); + ASSERT_EQ(20u, map.size()); + + // Constructs a sequence from `start` up to but not including `end` by 2. + auto Seq = [](int start, int end) { return Sequence(start, end, 2); }; + + ASSERT_SEQ_EQ(Empty(), map.keys_in(0, 1)); // before to before + ASSERT_SEQ_EQ(all, map.keys_in(0, 100)) // before to after + ASSERT_SEQ_EQ(Seq(2, 6), map.keys_in(0, 6)) // before to in map + ASSERT_SEQ_EQ(Seq(2, 8), map.keys_in(0, 7)) // before to in between + + ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 0)); // after to before + ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 110)); // after to after + ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 6)); // after to in map + ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 7)); // after to in between + + ASSERT_SEQ_EQ(Empty(), map.keys_in(6, 0)); // in map to before + ASSERT_SEQ_EQ(Seq(6, 42), map.keys_in(6, 100)); // in map to after + ASSERT_SEQ_EQ(Seq(6, 10), map.keys_in(6, 10)); // in map to in map + ASSERT_SEQ_EQ(Seq(6, 12), map.keys_in(6, 11)); // in map to in between + + ASSERT_SEQ_EQ(Empty(), map.keys_in(7, 0)); // in between to before + ASSERT_SEQ_EQ(Seq(8, 42), map.keys_in(7, 100)); // in between to after + ASSERT_SEQ_EQ(Seq(8, 10), map.keys_in(7, 10)); // in between to key in map + ASSERT_SEQ_EQ(Seq(8, 14), map.keys_in(7, 13)); // in between to in between +} + } // namespace immutable } // namespace firestore } // namespace firebase -- cgit v1.2.3