summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Abseil Team <absl-team@google.com>2020-09-29 12:37:57 -0700
committerGravatar Andy Getz <durandal@google.com>2020-09-29 18:20:00 -0400
commit1fd58b69c62d1bb590a4860b0db30212b2fd2af4 (patch)
treefadc28643212042054cacd58f0b1ec2d184378e4
parentd1de75bf540f091b4dfc860713d556e578c0f158 (diff)
Export of internal Abseil changes
-- dad7313f7e8c36c35fc213ce5110100595f90990 by Andy Getzendanner <durandal@google.com>: Fix log_severity.h header guard to match path. PiperOrigin-RevId: 334439123 -- 8a58aa0f4171219d38fb49a2e008e249f86de4cb by Abseil Team <absl-team@google.com>: Minor comment cleanup PiperOrigin-RevId: 334409054 -- a1bc324e53c358b874f99b3f5624658fff99453e by Evan Brown <ezb@google.com>: 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
-rw-r--r--absl/base/log_severity.h6
-rw-r--r--absl/container/internal/btree.h72
-rw-r--r--absl/status/status.h6
3 files changed, 28 insertions, 56 deletions
diff --git a/absl/base/log_severity.h b/absl/base/log_severity.h
index 65a3b166..045f17f8 100644
--- a/absl/base/log_severity.h
+++ b/absl/base/log_severity.h
@@ -12,8 +12,8 @@
// See the License for the specific language governing permissions and
// limitations under the License.
-#ifndef ABSL_BASE_INTERNAL_LOG_SEVERITY_H_
-#define ABSL_BASE_INTERNAL_LOG_SEVERITY_H_
+#ifndef ABSL_BASE_LOG_SEVERITY_H_
+#define ABSL_BASE_LOG_SEVERITY_H_
#include <array>
#include <ostream>
@@ -118,4 +118,4 @@ std::ostream& operator<<(std::ostream& os, absl::LogSeverity s);
ABSL_NAMESPACE_END
} // namespace absl
-#endif // ABSL_BASE_INTERNAL_LOG_SEVERITY_H_
+#endif // ABSL_BASE_LOG_SEVERITY_H_
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 <typename V>
struct SearchResult<V, false> {
+ 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<int, false>{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<int, false>{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 <typename K>
SearchResult<iterator, is_key_compare_to::value> internal_locate(
const K &key) const;
- template <typename K>
- SearchResult<iterator, false> internal_locate_impl(
- const K &key, std::false_type /* IsCompareTo */) const;
-
- template <typename K>
- SearchResult<iterator, true> internal_locate_impl(
- const K &key, std::true_type /* IsCompareTo */) const;
-
// Internal routine which implements lower_bound().
template <typename K>
iterator internal_lower_bound(const K &key) const;
@@ -1934,8 +1927,8 @@ auto btree<P>::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<iterator, is_key_compare_to::value> res = internal_locate(key);
+ iterator iter = res.value;
if (res.HasMatch()) {
if (res.IsEq()) {
@@ -2501,46 +2494,25 @@ template <typename P>
template <typename K>
inline auto btree<P>::internal_locate(const K &key) const
-> SearchResult<iterator, is_key_compare_to::value> {
- return internal_locate_impl(key, is_key_compare_to());
-}
-
-template <typename P>
-template <typename K>
-inline auto btree<P>::internal_locate_impl(
- const K &key, std::false_type /* IsCompareTo */) const
- -> SearchResult<iterator, false> {
- iterator iter(const_cast<node_type *>(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 <typename P>
-template <typename K>
-inline auto btree<P>::internal_locate_impl(
- const K &key, std::true_type /* IsCompareTo */) const
- -> SearchResult<iterator, true> {
iterator iter(const_cast<node_type *>(root()));
for (;;) {
- SearchResult<int, true> res = iter.node->lower_bound(key, key_comp());
+ SearchResult<int, is_key_compare_to::value> 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<P>::internal_upper_bound(const K &key) const -> iterator {
template <typename P>
template <typename K>
auto btree<P>::internal_find(const K &key) const -> iterator {
- auto res = internal_locate(key);
+ SearchResult<iterator, is_key_compare_to::value> res = internal_locate(key);
if (res.HasMatch()) {
if (res.IsEq()) {
return res.value;
diff --git a/absl/status/status.h b/absl/status/status.h
index 42f634e0..c4d6fce0 100644
--- a/absl/status/status.h
+++ b/absl/status/status.h
@@ -98,7 +98,7 @@ enum class StatusCode : int {
// StatusCode::kCancelled
//
- // kCanelled (gRPC code "CANCELLED") indicates the operation was cancelled,
+ // kCancelled (gRPC code "CANCELLED") indicates the operation was cancelled,
// typically by the caller.
kCancelled = 1,
@@ -198,9 +198,9 @@ enum class StatusCode : int {
// `kAborted`, and `kUnavailable`.
kAborted = 10,
- // StatusCode::kOutofRange
+ // StatusCode::kOutOfRange
//
- // kOutofRange (gRPC code "OUT_OF_RANGE") indicates the operation was
+ // kOutOfRange (gRPC code "OUT_OF_RANGE") indicates the operation was
// attempted past the valid range, such as seeking or reading past an
// end-of-file.
//