From 1fd58b69c62d1bb590a4860b0db30212b2fd2af4 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 29 Sep 2020 12:37:57 -0700 Subject: Export of internal Abseil changes -- dad7313f7e8c36c35fc213ce5110100595f90990 by Andy Getzendanner : Fix log_severity.h header guard to match path. PiperOrigin-RevId: 334439123 -- 8a58aa0f4171219d38fb49a2e008e249f86de4cb by Abseil Team : Minor comment cleanup PiperOrigin-RevId: 334409054 -- a1bc324e53c358b874f99b3f5624658fff99453e by Evan Brown : Cleanup in btree.h: - Combine internal_locate_impls and update comments. - Avoid use of auto with SearchResult. - Change one iterator reference to be stored by value (copy is cheap). PiperOrigin-RevId: 334396951 GitOrigin-RevId: dad7313f7e8c36c35fc213ce5110100595f90990 Change-Id: I79862795abd3169587f5bafe0e5369bdde90c1e1 --- absl/container/internal/btree.h | 72 +++++++++++++---------------------------- 1 file changed, 22 insertions(+), 50 deletions(-) (limited to 'absl/container/internal') diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index 002ccc1e..2e291d31 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -391,6 +391,9 @@ struct SearchResult { // useful information. template struct SearchResult { + explicit SearchResult(V value) : value(value) {} + SearchResult(V value, MatchKind /*match*/) : value(value) {} + V value; static constexpr bool HasMatch() { return false; } @@ -672,7 +675,7 @@ class btree_node { } ++s; } - return {s}; + return SearchResult{s}; } // Returns the position of the first value whose key is not less than k using @@ -707,7 +710,7 @@ class btree_node { e = mid; } } - return {s}; + return SearchResult{s}; } // Returns the position of the first value whose key is not less than k using @@ -1453,25 +1456,15 @@ class btree { static IterType internal_last(IterType iter); // Returns an iterator pointing to the leaf position at which key would - // reside in the tree. We provide 2 versions of internal_locate. The first - // version uses a less-than comparator and is incapable of distinguishing when - // there is an exact match. The second version is for the key-compare-to - // specialization and distinguishes exact matches. The key-compare-to - // specialization allows the caller to avoid a subsequent comparison to - // determine if an exact match was made, which is important for keys with - // expensive comparison, such as strings. + // reside in the tree, unless there is an exact match - in which case, the + // result may not be on a leaf. When there's a three-way comparator, we can + // return whether there was an exact match. This allows the caller to avoid a + // subsequent comparison to determine if an exact match was made, which is + // important for keys with expensive comparison, such as strings. template SearchResult internal_locate( const K &key) const; - template - SearchResult internal_locate_impl( - const K &key, std::false_type /* IsCompareTo */) const; - - template - SearchResult internal_locate_impl( - const K &key, std::true_type /* IsCompareTo */) const; - // Internal routine which implements lower_bound(). template iterator internal_lower_bound(const K &key) const; @@ -1934,8 +1927,8 @@ auto btree

::insert_unique(const K &key, Args &&... args) mutable_root() = rightmost_ = new_leaf_root_node(1); } - auto res = internal_locate(key); - iterator &iter = res.value; + SearchResult res = internal_locate(key); + iterator iter = res.value; if (res.HasMatch()) { if (res.IsEq()) { @@ -2501,46 +2494,25 @@ template template inline auto btree

::internal_locate(const K &key) const -> SearchResult { - return internal_locate_impl(key, is_key_compare_to()); -} - -template -template -inline auto btree

::internal_locate_impl( - const K &key, std::false_type /* IsCompareTo */) const - -> SearchResult { - iterator iter(const_cast(root())); - for (;;) { - iter.position = iter.node->lower_bound(key, key_comp()).value; - // NOTE: we don't need to walk all the way down the tree if the keys are - // equal, but determining equality would require doing an extra comparison - // on each node on the way down, and we will need to go all the way to the - // leaf node in the expected case. - if (iter.node->leaf()) { - break; - } - iter.node = iter.node->child(iter.position); - } - return {iter}; -} - -template -template -inline auto btree

::internal_locate_impl( - const K &key, std::true_type /* IsCompareTo */) const - -> SearchResult { iterator iter(const_cast(root())); for (;;) { - SearchResult res = iter.node->lower_bound(key, key_comp()); + SearchResult res = + iter.node->lower_bound(key, key_comp()); iter.position = res.value; - if (res.match == MatchKind::kEq) { + if (res.IsEq()) { return {iter, MatchKind::kEq}; } + // Note: in the non-key-compare-to case, we don't need to walk all the way + // down the tree if the keys are equal, but determining equality would + // require doing an extra comparison on each node on the way down, and we + // will need to go all the way to the leaf node in the expected case. if (iter.node->leaf()) { break; } iter.node = iter.node->child(iter.position); } + // Note: in the non-key-compare-to case, the key may actually be equivalent + // here (and the MatchKind::kNe is ignored). return {iter, MatchKind::kNe}; } @@ -2575,7 +2547,7 @@ auto btree

::internal_upper_bound(const K &key) const -> iterator { template template auto btree

::internal_find(const K &key) const -> iterator { - auto res = internal_locate(key); + SearchResult res = internal_locate(key); if (res.HasMatch()) { if (res.IsEq()) { return res.value; -- cgit v1.2.3