summaryrefslogtreecommitdiff
path: root/include/ftl
diff options
context:
space:
mode:
Diffstat (limited to 'include/ftl')
-rw-r--r--include/ftl/algorithm.h12
-rw-r--r--include/ftl/concat.h4
-rw-r--r--include/ftl/details/hash.h123
-rw-r--r--include/ftl/expected.h78
-rw-r--r--include/ftl/function.h2
-rw-r--r--include/ftl/hash.h44
-rw-r--r--include/ftl/non_null.h112
-rw-r--r--include/ftl/optional.h10
-rw-r--r--include/ftl/unit.h18
9 files changed, 392 insertions, 11 deletions
diff --git a/include/ftl/algorithm.h b/include/ftl/algorithm.h
index c0f67683ab..68826bb068 100644
--- a/include/ftl/algorithm.h
+++ b/include/ftl/algorithm.h
@@ -24,6 +24,18 @@
namespace android::ftl {
+// Determines if a container contains a value. This is a simplified version of the C++23
+// std::ranges::contains function.
+//
+// const ftl::StaticVector vector = {1, 2, 3};
+// assert(ftl::contains(vector, 1));
+//
+// TODO: Remove in C++23.
+template <typename Container, typename Value>
+auto contains(const Container& container, const Value& value) -> bool {
+ return std::find(container.begin(), container.end(), value) != container.end();
+}
+
// Adapter for std::find_if that converts the return value from iterator to optional.
//
// const ftl::StaticVector vector = {"upside"sv, "down"sv, "cake"sv};
diff --git a/include/ftl/concat.h b/include/ftl/concat.h
index e0774d39f3..7680bed5e8 100644
--- a/include/ftl/concat.h
+++ b/include/ftl/concat.h
@@ -57,7 +57,7 @@ struct Concat<N, T, Ts...> : Concat<N + details::StaticString<T>::N, Ts...> {
template <std::size_t N>
struct Concat<N> {
static constexpr std::size_t max_size() { return N; }
- constexpr std::size_t size() const { return end_ - buffer_; }
+ constexpr std::size_t size() const { return static_cast<std::size_t>(end_ - buffer_); }
constexpr const char* c_str() const { return buffer_; }
@@ -68,6 +68,8 @@ struct Concat<N> {
protected:
constexpr Concat() : end_(buffer_) {}
+ constexpr Concat(const Concat&) = delete;
+
constexpr void append() { *end_ = '\0'; }
char buffer_[N + 1];
diff --git a/include/ftl/details/hash.h b/include/ftl/details/hash.h
new file mode 100644
index 0000000000..230ae51257
--- /dev/null
+++ b/include/ftl/details/hash.h
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <cinttypes>
+#include <cstring>
+
+namespace android::ftl::details {
+
+// Based on CityHash64 v1.0.1 (http://code.google.com/p/cityhash/), but slightly
+// modernized and trimmed for cases with bounded lengths.
+
+template <typename T = std::uint64_t>
+inline T read_unaligned(const void* ptr) {
+ T v;
+ std::memcpy(&v, ptr, sizeof(T));
+ return v;
+}
+
+template <bool NonZeroShift = false>
+constexpr std::uint64_t rotate(std::uint64_t v, std::uint8_t shift) {
+ if constexpr (!NonZeroShift) {
+ if (shift == 0) return v;
+ }
+ return (v >> shift) | (v << (64 - shift));
+}
+
+constexpr std::uint64_t shift_mix(std::uint64_t v) {
+ return v ^ (v >> 47);
+}
+
+__attribute__((no_sanitize("unsigned-integer-overflow")))
+constexpr std::uint64_t hash_length_16(std::uint64_t u, std::uint64_t v) {
+ constexpr std::uint64_t kPrime = 0x9ddfea08eb382d69ull;
+ auto a = (u ^ v) * kPrime;
+ a ^= (a >> 47);
+ auto b = (v ^ a) * kPrime;
+ b ^= (b >> 47);
+ b *= kPrime;
+ return b;
+}
+
+constexpr std::uint64_t kPrime0 = 0xc3a5c85c97cb3127ull;
+constexpr std::uint64_t kPrime1 = 0xb492b66fbe98f273ull;
+constexpr std::uint64_t kPrime2 = 0x9ae16a3b2f90404full;
+constexpr std::uint64_t kPrime3 = 0xc949d7c7509e6557ull;
+
+__attribute__((no_sanitize("unsigned-integer-overflow")))
+inline std::uint64_t hash_length_0_to_16(const char* str, std::uint64_t length) {
+ if (length > 8) {
+ const auto a = read_unaligned(str);
+ const auto b = read_unaligned(str + length - 8);
+ return hash_length_16(a, rotate<true>(b + length, static_cast<std::uint8_t>(length))) ^ b;
+ }
+ if (length >= 4) {
+ const auto a = read_unaligned<std::uint32_t>(str);
+ const auto b = read_unaligned<std::uint32_t>(str + length - 4);
+ return hash_length_16(length + (a << 3), b);
+ }
+ if (length > 0) {
+ const auto a = static_cast<unsigned char>(str[0]);
+ const auto b = static_cast<unsigned char>(str[length >> 1]);
+ const auto c = static_cast<unsigned char>(str[length - 1]);
+ const auto y = static_cast<std::uint32_t>(a) + (static_cast<std::uint32_t>(b) << 8);
+ const auto z = static_cast<std::uint32_t>(length) + (static_cast<std::uint32_t>(c) << 2);
+ return shift_mix(y * kPrime2 ^ z * kPrime3) * kPrime2;
+ }
+ return kPrime2;
+}
+
+__attribute__((no_sanitize("unsigned-integer-overflow")))
+inline std::uint64_t hash_length_17_to_32(const char* str, std::uint64_t length) {
+ const auto a = read_unaligned(str) * kPrime1;
+ const auto b = read_unaligned(str + 8);
+ const auto c = read_unaligned(str + length - 8) * kPrime2;
+ const auto d = read_unaligned(str + length - 16) * kPrime0;
+ return hash_length_16(rotate(a - b, 43) + rotate(c, 30) + d,
+ a + rotate(b ^ kPrime3, 20) - c + length);
+}
+
+__attribute__((no_sanitize("unsigned-integer-overflow")))
+inline std::uint64_t hash_length_33_to_64(const char* str, std::uint64_t length) {
+ auto z = read_unaligned(str + 24);
+ auto a = read_unaligned(str) + (length + read_unaligned(str + length - 16)) * kPrime0;
+ auto b = rotate(a + z, 52);
+ auto c = rotate(a, 37);
+
+ a += read_unaligned(str + 8);
+ c += rotate(a, 7);
+ a += read_unaligned(str + 16);
+
+ const auto vf = a + z;
+ const auto vs = b + rotate(a, 31) + c;
+
+ a = read_unaligned(str + 16) + read_unaligned(str + length - 32);
+ z += read_unaligned(str + length - 8);
+ b = rotate(a + z, 52);
+ c = rotate(a, 37);
+ a += read_unaligned(str + length - 24);
+ c += rotate(a, 7);
+ a += read_unaligned(str + length - 16);
+
+ const auto wf = a + z;
+ const auto ws = b + rotate(a, 31) + c;
+ const auto r = shift_mix((vf + ws) * kPrime2 + (wf + vs) * kPrime0);
+ return shift_mix(r * kPrime0 + vs) * kPrime2;
+}
+
+} // namespace android::ftl::details
diff --git a/include/ftl/expected.h b/include/ftl/expected.h
index 12b6102b6f..7e765c5681 100644
--- a/include/ftl/expected.h
+++ b/include/ftl/expected.h
@@ -18,9 +18,87 @@
#include <android-base/expected.h>
#include <ftl/optional.h>
+#include <ftl/unit.h>
#include <utility>
+// Given an expression `expr` that evaluates to an ftl::Expected<T, E> result (R for short), FTL_TRY
+// unwraps T out of R, or bails out of the enclosing function F if R has an error E. The return type
+// of F must be R, since FTL_TRY propagates R in the error case. As a special case, ftl::Unit may be
+// used as the error E to allow FTL_TRY expressions when F returns `void`.
+//
+// The non-standard syntax requires `-Wno-gnu-statement-expression-from-macro-expansion` to compile.
+// The UnitToVoid conversion allows the macro to be used for early exit from a function that returns
+// `void`.
+//
+// Example usage:
+//
+// using StringExp = ftl::Expected<std::string, std::errc>;
+//
+// StringExp repeat(StringExp exp) {
+// const std::string str = FTL_TRY(exp);
+// return StringExp(str + str);
+// }
+//
+// assert(StringExp("haha"s) == repeat(StringExp("ha"s)));
+// assert(repeat(ftl::Unexpected(std::errc::bad_message)).has_error([](std::errc e) {
+// return e == std::errc::bad_message;
+// }));
+//
+//
+// FTL_TRY may be used in void-returning functions by using ftl::Unit as the error type:
+//
+// void uppercase(char& c, ftl::Optional<char> opt) {
+// c = std::toupper(FTL_TRY(std::move(opt).ok_or(ftl::Unit())));
+// }
+//
+// char c = '?';
+// uppercase(c, std::nullopt);
+// assert(c == '?');
+//
+// uppercase(c, 'a');
+// assert(c == 'A');
+//
+#define FTL_TRY(expr) \
+ ({ \
+ auto exp_ = (expr); \
+ if (!exp_.has_value()) { \
+ using E = decltype(exp_)::error_type; \
+ return android::ftl::details::UnitToVoid<E>::from(std::move(exp_)); \
+ } \
+ exp_.value(); \
+ })
+
+// Given an expression `expr` that evaluates to an ftl::Expected<T, E> result (R for short),
+// FTL_EXPECT unwraps T out of R, or bails out of the enclosing function F if R has an error E.
+// While FTL_TRY bails out with R, FTL_EXPECT bails out with E, which is useful when F does not
+// need to propagate R because T is not relevant to the caller.
+//
+// Example usage:
+//
+// using StringExp = ftl::Expected<std::string, std::errc>;
+//
+// std::errc repeat(StringExp exp, std::string& out) {
+// const std::string str = FTL_EXPECT(exp);
+// out = str + str;
+// return std::errc::operation_in_progress;
+// }
+//
+// std::string str;
+// assert(std::errc::operation_in_progress == repeat(StringExp("ha"s), str));
+// assert("haha"s == str);
+// assert(std::errc::bad_message == repeat(ftl::Unexpected(std::errc::bad_message), str));
+// assert("haha"s == str);
+//
+#define FTL_EXPECT(expr) \
+ ({ \
+ auto exp_ = (expr); \
+ if (!exp_.has_value()) { \
+ return std::move(exp_.error()); \
+ } \
+ exp_.value(); \
+ })
+
namespace android::ftl {
// Superset of base::expected<T, E> with monadic operations.
diff --git a/include/ftl/function.h b/include/ftl/function.h
index 3538ca4eae..bda5b759bb 100644
--- a/include/ftl/function.h
+++ b/include/ftl/function.h
@@ -123,7 +123,7 @@ namespace android::ftl {
// // Create a typedef to give a more meaningful name and bound the size.
// using MyFunction = ftl::Function<int(std::string_view), 2>;
// int* ptr = nullptr;
-// auto f1 = MyFunction::make_function(
+// auto f1 = MyFunction::make(
// [cls = &cls, ptr](std::string_view sv) {
// return cls->on_string(ptr, sv);
// });
diff --git a/include/ftl/hash.h b/include/ftl/hash.h
new file mode 100644
index 0000000000..29a6f719ef
--- /dev/null
+++ b/include/ftl/hash.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2024 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#pragma once
+
+#include <cinttypes>
+#include <optional>
+#include <string_view>
+
+#include <ftl/details/hash.h>
+
+namespace android::ftl {
+
+// Non-cryptographic hash function (namely CityHash64) for strings with at most 64 characters.
+// Unlike std::hash, which returns std::size_t and is only required to produce the same result
+// for the same input within a single execution of a program, this hash is stable.
+inline std::optional<std::uint64_t> stable_hash(std::string_view view) {
+ const auto length = view.length();
+ if (length <= 16) {
+ return details::hash_length_0_to_16(view.data(), length);
+ }
+ if (length <= 32) {
+ return details::hash_length_17_to_32(view.data(), length);
+ }
+ if (length <= 64) {
+ return details::hash_length_33_to_64(view.data(), length);
+ }
+ return {};
+}
+
+} // namespace android::ftl
diff --git a/include/ftl/non_null.h b/include/ftl/non_null.h
index 35d09d71de..4a5d8bffd0 100644
--- a/include/ftl/non_null.h
+++ b/include/ftl/non_null.h
@@ -68,26 +68,28 @@ class NonNull final {
constexpr NonNull(const NonNull&) = default;
constexpr NonNull& operator=(const NonNull&) = default;
- constexpr const Pointer& get() const { return pointer_; }
- constexpr explicit operator const Pointer&() const { return get(); }
+ [[nodiscard]] constexpr const Pointer& get() const { return pointer_; }
+ [[nodiscard]] constexpr explicit operator const Pointer&() const { return get(); }
// Move operations. These break the invariant, so care must be taken to avoid subsequent access.
constexpr NonNull(NonNull&&) = default;
constexpr NonNull& operator=(NonNull&&) = default;
- constexpr Pointer take() && { return std::move(pointer_); }
- constexpr explicit operator Pointer() && { return take(); }
+ [[nodiscard]] constexpr Pointer take() && { return std::move(pointer_); }
+ [[nodiscard]] constexpr explicit operator Pointer() && { return take(); }
// Dereferencing.
- constexpr decltype(auto) operator*() const { return *get(); }
- constexpr decltype(auto) operator->() const { return get(); }
+ [[nodiscard]] constexpr decltype(auto) operator*() const { return *get(); }
+ [[nodiscard]] constexpr decltype(auto) operator->() const { return get(); }
+
+ [[nodiscard]] constexpr explicit operator bool() const { return !(pointer_ == nullptr); }
// Private constructor for ftl::as_non_null. Excluded from candidate constructors for conversions
// through the passkey idiom, for clear compilation errors.
template <typename P>
constexpr NonNull(Passkey, P&& pointer) : pointer_(std::forward<P>(pointer)) {
- if (!pointer_) std::abort();
+ if (pointer_ == nullptr) std::abort();
}
private:
@@ -98,11 +100,13 @@ class NonNull final {
};
template <typename P>
-constexpr auto as_non_null(P&& pointer) -> NonNull<std::decay_t<P>> {
+[[nodiscard]] constexpr auto as_non_null(P&& pointer) -> NonNull<std::decay_t<P>> {
using Passkey = typename NonNull<std::decay_t<P>>::Passkey;
return {Passkey{}, std::forward<P>(pointer)};
}
+// NonNull<P> <=> NonNull<Q>
+
template <typename P, typename Q>
constexpr bool operator==(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
return lhs.get() == rhs.get();
@@ -113,4 +117,96 @@ constexpr bool operator!=(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
return !operator==(lhs, rhs);
}
+template <typename P, typename Q>
+constexpr bool operator<(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
+ return lhs.get() < rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator<=(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
+ return lhs.get() <= rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator>=(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
+ return lhs.get() >= rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator>(const NonNull<P>& lhs, const NonNull<Q>& rhs) {
+ return lhs.get() > rhs.get();
+}
+
+// NonNull<P> <=> Q
+
+template <typename P, typename Q>
+constexpr bool operator==(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() == rhs;
+}
+
+template <typename P, typename Q>
+constexpr bool operator!=(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() != rhs;
+}
+
+template <typename P, typename Q>
+constexpr bool operator<(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() < rhs;
+}
+
+template <typename P, typename Q>
+constexpr bool operator<=(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() <= rhs;
+}
+
+template <typename P, typename Q>
+constexpr bool operator>=(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() >= rhs;
+}
+
+template <typename P, typename Q>
+constexpr bool operator>(const NonNull<P>& lhs, const Q& rhs) {
+ return lhs.get() > rhs;
+}
+
+// P <=> NonNull<Q>
+
+template <typename P, typename Q>
+constexpr bool operator==(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs == rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator!=(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs != rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator<(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs < rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator<=(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs <= rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator>=(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs >= rhs.get();
+}
+
+template <typename P, typename Q>
+constexpr bool operator>(const P& lhs, const NonNull<Q>& rhs) {
+ return lhs > rhs.get();
+}
+
} // namespace android::ftl
+
+// Specialize std::hash for ftl::NonNull<T>
+template <typename P>
+struct std::hash<android::ftl::NonNull<P>> {
+ std::size_t operator()(const android::ftl::NonNull<P>& ptr) const {
+ return std::hash<P>()(ptr.get());
+ }
+};
diff --git a/include/ftl/optional.h b/include/ftl/optional.h
index 94d8e3d7cb..e245d88c1c 100644
--- a/include/ftl/optional.h
+++ b/include/ftl/optional.h
@@ -20,13 +20,14 @@
#include <optional>
#include <utility>
+#include <android-base/expected.h>
#include <ftl/details/optional.h>
namespace android::ftl {
// Superset of std::optional<T> with monadic operations, as proposed in https://wg21.link/P0798R8.
//
-// TODO: Remove in C++23.
+// TODO: Remove standard APIs in C++23.
//
template <typename T>
struct Optional final : std::optional<T> {
@@ -109,6 +110,13 @@ struct Optional final : std::optional<T> {
return std::forward<F>(f)();
}
+ // Maps this Optional<T> to expected<T, E> where nullopt becomes E.
+ template <typename E>
+ constexpr auto ok_or(E&& e) && -> base::expected<T, E> {
+ if (has_value()) return std::move(value());
+ return base::unexpected(std::forward<E>(e));
+ }
+
// Delete new for this class. Its base doesn't have a virtual destructor, and
// if it got deleted via base class pointer, it would cause undefined
// behavior. There's not a good reason to allocate this object on the heap
diff --git a/include/ftl/unit.h b/include/ftl/unit.h
index e38230b976..62549a3f9d 100644
--- a/include/ftl/unit.h
+++ b/include/ftl/unit.h
@@ -58,4 +58,22 @@ constexpr auto unit_fn(F&& f) -> UnitFn<std::decay_t<F>> {
return {std::forward<F>(f)};
}
+namespace details {
+
+// Identity function for all T except Unit, which maps to void.
+template <typename T>
+struct UnitToVoid {
+ template <typename U>
+ static auto from(U&& value) {
+ return value;
+ }
+};
+
+template <>
+struct UnitToVoid<Unit> {
+ template <typename U>
+ static void from(U&&) {}
+};
+
+} // namespace details
} // namespace android::ftl
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-04 04:45:51 +0000