Merge "Plumbing through GPU context priority from SF to RE"
diff --git a/cmds/servicemanager/ServiceManager.cpp b/cmds/servicemanager/ServiceManager.cpp
index 7aac7da..b21010d 100644
--- a/cmds/servicemanager/ServiceManager.cpp
+++ b/cmds/servicemanager/ServiceManager.cpp
@@ -494,7 +494,7 @@
sp<BpBinder> bpBinder = binder->remoteBinder();
if (bpBinder == nullptr) return -1;
- return ProcessState::self()->getStrongRefCountForNodeByHandle(bpBinder->handle());
+ return ProcessState::self()->getStrongRefCountForNode(bpBinder);
}
void ServiceManager::handleClientCallbacks() {
diff --git a/include/audiomanager/AudioManager.h b/include/audiomanager/AudioManager.h
index 4aa2f60..639df7a 100644
--- a/include/audiomanager/AudioManager.h
+++ b/include/audiomanager/AudioManager.h
@@ -37,7 +37,6 @@
PLAYER_STATE_STARTED = 2,
PLAYER_STATE_PAUSED = 3,
PLAYER_STATE_STOPPED = 4,
- PLAYER_UPDATE_DEVICE_ID = 5,
} player_state_t;
// must be kept in sync with definitions in AudioManager.java
diff --git a/include/audiomanager/IAudioManager.h b/include/audiomanager/IAudioManager.h
index 7d1f38f..2f5ccb8 100644
--- a/include/audiomanager/IAudioManager.h
+++ b/include/audiomanager/IAudioManager.h
@@ -49,8 +49,7 @@
audio_content_type_t content, const sp<IBinder>& player) = 0;
/*oneway*/ virtual status_t playerAttributes(audio_unique_id_t piid, audio_usage_t usage,
audio_content_type_t content)= 0;
- /*oneway*/ virtual status_t playerEvent(audio_unique_id_t piid, player_state_t event,
- audio_port_handle_t deviceId) = 0;
+ /*oneway*/ virtual status_t playerEvent(audio_unique_id_t piid, player_state_t event) = 0;
/*oneway*/ virtual status_t releasePlayer(audio_unique_id_t piid) = 0;
virtual audio_unique_id_t trackRecorder(const sp<IBinder>& recorder) = 0;
/*oneway*/ virtual status_t recorderEvent(audio_unique_id_t riid, recorder_state_t event) = 0;
diff --git a/include/ftl/.clang-format b/include/ftl/.clang-format
new file mode 120000
index 0000000..86b1593
--- /dev/null
+++ b/include/ftl/.clang-format
@@ -0,0 +1 @@
+../../../../build/soong/scripts/system-clang-format-2
\ No newline at end of file
diff --git a/include/ftl/ArrayTraits.h b/include/ftl/ArrayTraits.h
deleted file mode 100644
index ff685c5..0000000
--- a/include/ftl/ArrayTraits.h
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
- * Copyright 2020 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 <algorithm>
-#include <iterator>
-#include <new>
-#include <type_traits>
-
-#define FTL_ARRAY_TRAIT(T, U) using U = typename ArrayTraits<T>::U
-
-namespace android::ftl {
-
-template <typename T>
-struct ArrayTraits {
- using value_type = T;
- using size_type = size_t;
- using difference_type = ptrdiff_t;
-
- using pointer = value_type*;
- using reference = value_type&;
- using iterator = pointer;
- using reverse_iterator = std::reverse_iterator<iterator>;
-
- using const_pointer = const value_type*;
- using const_reference = const value_type&;
- using const_iterator = const_pointer;
- using const_reverse_iterator = std::reverse_iterator<const_iterator>;
-
- template <typename... Args>
- static pointer construct_at(const_iterator it, Args&&... args) {
- void* const ptr = const_cast<void*>(static_cast<const void*>(it));
- if constexpr (std::is_constructible_v<value_type, Args...>) {
- // TODO: Replace with std::construct_at in C++20.
- return new (ptr) value_type(std::forward<Args>(args)...);
- } else {
- // Fall back to list initialization.
- return new (ptr) value_type{std::forward<Args>(args)...};
- }
- }
-};
-
-// CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end.
-template <typename Self, typename T>
-class ArrayIterators {
- FTL_ARRAY_TRAIT(T, size_type);
-
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
-
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
-
- Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); }
-
-public:
- const_iterator begin() const { return cbegin(); }
- const_iterator cbegin() const { return self().begin(); }
-
- const_iterator end() const { return cend(); }
- const_iterator cend() const { return self().end(); }
-
- reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); }
- const_reverse_iterator rbegin() const { return crbegin(); }
- const_reverse_iterator crbegin() const { return self().rbegin(); }
-
- reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); }
- const_reverse_iterator rend() const { return crend(); }
- const_reverse_iterator crend() const { return self().rend(); }
-
- iterator last() { return self().end() - 1; }
- const_iterator last() const { return self().last(); }
-
- reference front() { return *self().begin(); }
- const_reference front() const { return self().front(); }
-
- reference back() { return *last(); }
- const_reference back() const { return self().back(); }
-
- reference operator[](size_type i) { return *(self().begin() + i); }
- const_reference operator[](size_type i) const { return self()[i]; }
-};
-
-// Mixin to define comparison operators for an array-like template.
-// TODO: Replace with operator<=> in C++20.
-template <template <typename, size_t> class Array>
-struct ArrayComparators {
- template <typename T, size_t N, size_t M>
- friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
- }
-
- template <typename T, size_t N, size_t M>
- friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
- }
-
- template <typename T, size_t N, size_t M>
- friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return rhs < lhs;
- }
-
- template <typename T, size_t N, size_t M>
- friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs == rhs);
- }
-
- template <typename T, size_t N, size_t M>
- friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs < rhs);
- }
-
- template <typename T, size_t N, size_t M>
- friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
- return !(lhs > rhs);
- }
-};
-
-} // namespace android::ftl
diff --git a/include/ftl/InitializerList.h b/include/ftl/InitializerList.h
deleted file mode 100644
index bb99280..0000000
--- a/include/ftl/InitializerList.h
+++ /dev/null
@@ -1,110 +0,0 @@
-/*
- * Copyright 2020 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 <tuple>
-#include <utility>
-
-namespace android::ftl {
-
-// Compile-time counterpart of std::initializer_list<T> that stores per-element constructor
-// arguments with heterogeneous types. For a container with elements of type T, given Sizes
-// (S0, S1, ..., SN), N elements are initialized: the first element is initialized with the
-// first S0 arguments, the second element is initialized with the next S1 arguments, and so
-// on. The list of Types (T0, ..., TM) is flattened, so M is equal to the sum of the Sizes.
-//
-// The InitializerList is created using ftl::init::list, and is consumed by constructors of
-// containers. The function call operator is overloaded such that arguments are accumulated
-// in a tuple with each successive call. For instance, the following calls initialize three
-// strings using different constructors, i.e. string literal, default, and count/character:
-//
-// ... = ftl::init::list<std::string>("abc")()(3u, '?');
-//
-// The following syntax is a shorthand for key-value pairs, where the first argument is the
-// key, and the rest construct the value. The types of the key and value are deduced if the
-// first pair contains exactly two arguments:
-//
-// ... = ftl::init::map<int, std::string>(-1, "abc")(-2)(-3, 3u, '?');
-//
-// ... = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
-//
-// WARNING: The InitializerList returned by an ftl::init::list expression must be consumed
-// immediately, since temporary arguments are destroyed after the full expression. Storing
-// an InitializerList results in dangling references.
-//
-template <typename T, typename Sizes = std::index_sequence<>, typename... Types>
-struct InitializerList;
-
-template <typename T, size_t... Sizes, typename... Types>
-struct InitializerList<T, std::index_sequence<Sizes...>, Types...> {
- // Creates a superset InitializerList by appending the number of arguments to Sizes, and
- // expanding Types with forwarding references for each argument.
- template <typename... Args>
- [[nodiscard]] constexpr auto operator()(Args&&... args) && -> InitializerList<
- T, std::index_sequence<Sizes..., sizeof...(Args)>, Types..., Args&&...> {
- return {std::tuple_cat(std::move(tuple),
- std::forward_as_tuple(std::forward<Args>(args)...))};
- }
-
- // The temporary InitializerList returned by operator() is bound to an rvalue reference in
- // container constructors, which extends the lifetime of any temporary arguments that this
- // tuple refers to until the completion of the full expression containing the construction.
- std::tuple<Types...> tuple;
-};
-
-template <typename K, typename V>
-struct KeyValue {};
-
-// Shorthand for key-value pairs that assigns the first argument to the key, and the rest to the
-// value. The specialization is on KeyValue rather than std::pair, so that ftl::init::list works
-// with the latter.
-template <typename K, typename V, size_t... Sizes, typename... Types>
-struct InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...> {
- // Accumulate the three arguments to std::pair's piecewise constructor.
- template <typename... Args>
- [[nodiscard]] constexpr auto operator()(K&& k, Args&&... args) && -> InitializerList<
- KeyValue<K, V>, std::index_sequence<Sizes..., 3>, Types..., std::piecewise_construct_t,
- std::tuple<K&&>, std::tuple<Args&&...>> {
- return {std::tuple_cat(std::move(tuple),
- std::forward_as_tuple(std::piecewise_construct,
- std::forward_as_tuple(std::forward<K>(k)),
- std::forward_as_tuple(
- std::forward<Args>(args)...)))};
- }
-
- std::tuple<Types...> tuple;
-};
-
-namespace init {
-
-template <typename T, typename... Args>
-[[nodiscard]] constexpr auto list(Args&&... args) {
- return InitializerList<T>{}(std::forward<Args>(args)...);
-}
-
-template <typename K, typename V, typename... Args>
-[[nodiscard]] constexpr auto map(Args&&... args) {
- return list<KeyValue<K, V>>(std::forward<Args>(args)...);
-}
-
-template <typename K, typename V>
-[[nodiscard]] constexpr auto map(K&& k, V&& v) {
- return list<KeyValue<K, V>>(std::forward<K>(k), std::forward<V>(v));
-}
-
-} // namespace init
-} // namespace android::ftl
diff --git a/include/ftl/SmallMap.h b/include/ftl/SmallMap.h
deleted file mode 100644
index 87ae99c..0000000
--- a/include/ftl/SmallMap.h
+++ /dev/null
@@ -1,205 +0,0 @@
-/*
- * Copyright 2020 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 <ftl/InitializerList.h>
-#include <ftl/SmallVector.h>
-
-#include <functional>
-#include <optional>
-#include <type_traits>
-#include <utility>
-
-namespace android::ftl {
-
-// Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
-// stored in contiguous storage for cache efficiency. The map is allocated statically until its size
-// exceeds N, at which point mappings are relocated to dynamic memory.
-//
-// SmallMap<K, V, 0> unconditionally allocates on the heap.
-//
-// Example usage:
-//
-// ftl::SmallMap<int, std::string, 3> map;
-// assert(map.empty());
-// assert(!map.dynamic());
-//
-// map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
-// assert(map.size() == 3u);
-// assert(!map.dynamic());
-//
-// assert(map.contains(123));
-// assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u);
-//
-// const auto opt = map.find(-1);
-// assert(opt);
-//
-// std::string& ref = *opt;
-// assert(ref.empty());
-// ref = "xyz";
-//
-// assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
-//
-template <typename K, typename V, size_t N>
-class SmallMap final {
- using Map = SmallVector<std::pair<const K, V>, N>;
-
-public:
- using key_type = K;
- using mapped_type = V;
-
- using value_type = typename Map::value_type;
- using size_type = typename Map::size_type;
- using difference_type = typename Map::difference_type;
-
- using reference = typename Map::reference;
- using iterator = typename Map::iterator;
-
- using const_reference = typename Map::const_reference;
- using const_iterator = typename Map::const_iterator;
-
- // Creates an empty map.
- SmallMap() = default;
-
- // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
- // The template arguments K, V, and N are inferred using the deduction guide defined below.
- // The syntax for listing pairs is as follows:
- //
- // ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
- //
- // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
- // assert(map.size() == 3u);
- // assert(map.contains(-1) && map.find(-1)->get().empty());
- // assert(map.contains(42) && map.find(42)->get() == "???");
- // assert(map.contains(123) && map.find(123)->get() == "abc");
- //
- // The types of the key and value are deduced if the first pair contains exactly two arguments:
- //
- // ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
- // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
- //
- template <typename U, size_t... Sizes, typename... Types>
- SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& init)
- : mMap(std::move(init)) {
- // TODO: Enforce unique keys.
- }
-
- size_type max_size() const { return mMap.max_size(); }
- size_type size() const { return mMap.size(); }
- bool empty() const { return mMap.empty(); }
-
- // Returns whether the map is backed by static or dynamic storage.
- bool dynamic() const { return mMap.dynamic(); }
-
- iterator begin() { return mMap.begin(); }
- const_iterator begin() const { return cbegin(); }
- const_iterator cbegin() const { return mMap.cbegin(); }
-
- iterator end() { return mMap.end(); }
- const_iterator end() const { return cend(); }
- const_iterator cend() const { return mMap.cend(); }
-
- // Returns whether a mapping exists for the given key.
- bool contains(const key_type& key) const {
- return find(key, [](const mapped_type&) {});
- }
-
- // Returns a reference to the value for the given key, or std::nullopt if the key was not found.
- //
- // ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
- //
- // const auto opt = map.find('c');
- // assert(opt == 'C');
- //
- // char d = 'd';
- // const auto ref = map.find('d').value_or(std::ref(d));
- // ref.get() = 'D';
- // assert(d == 'D');
- //
- auto find(const key_type& key) const
- -> std::optional<std::reference_wrapper<const mapped_type>> {
- return find(key, [](const mapped_type& v) { return std::cref(v); });
- }
-
- auto find(const key_type& key) -> std::optional<std::reference_wrapper<mapped_type>> {
- return find(key, [](mapped_type& v) { return std::ref(v); });
- }
-
- // Returns the result R of a unary operation F on (a constant or mutable reference to) the value
- // for the given key, or std::nullopt if the key was not found. If F has a return type of void,
- // then the Boolean result indicates whether the key was found.
- //
- // ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
- //
- // assert(map.find('c', [](char c) { return std::toupper(c); }) == 'Z');
- // assert(map.find('c', [](char& c) { c = std::toupper(c); }));
- //
- template <typename F, typename R = std::invoke_result_t<F, const mapped_type&>>
- auto find(const key_type& key, F f) const
- -> std::conditional_t<std::is_void_v<R>, bool, std::optional<R>> {
- for (auto& [k, v] : *this) {
- if (k == key) {
- if constexpr (std::is_void_v<R>) {
- f(v);
- return true;
- } else {
- return f(v);
- }
- }
- }
-
- return {};
- }
-
- template <typename F>
- auto find(const key_type& key, F f) {
- return std::as_const(*this).find(key, [&f](const mapped_type& v) {
- return f(const_cast<mapped_type&>(v));
- });
- }
-
-private:
- Map mMap;
-};
-
-// Deduction guide for in-place constructor.
-template <typename K, typename V, size_t... Sizes, typename... Types>
-SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&)
- -> SmallMap<K, V, sizeof...(Sizes)>;
-
-// Returns whether the key-value pairs of two maps are equal.
-template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
-bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
- if (lhs.size() != rhs.size()) return false;
-
- for (const auto& [k, v] : lhs) {
- const auto& lv = v;
- if (!rhs.find(k, [&lv](const auto& rv) { return lv == rv; }).value_or(false)) {
- return false;
- }
- }
-
- return true;
-}
-
-// TODO: Remove in C++20.
-template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
-inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
- return !(lhs == rhs);
-}
-
-} // namespace android::ftl
diff --git a/include/ftl/SmallVector.h b/include/ftl/SmallVector.h
deleted file mode 100644
index 2f05a9b..0000000
--- a/include/ftl/SmallVector.h
+++ /dev/null
@@ -1,391 +0,0 @@
-/*
- * Copyright 2020 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 <ftl/ArrayTraits.h>
-#include <ftl/StaticVector.h>
-
-#include <algorithm>
-#include <iterator>
-#include <type_traits>
-#include <utility>
-#include <variant>
-#include <vector>
-
-namespace android::ftl {
-
-template <typename>
-struct IsSmallVector;
-
-// ftl::StaticVector that promotes to std::vector when full. SmallVector is a drop-in replacement
-// for std::vector with statically allocated storage for N elements, whose goal is to improve run
-// time by avoiding heap allocation and increasing probability of cache hits. The standard API is
-// augmented by an unstable_erase operation that does not preserve order, and a replace operation
-// that destructively emplaces.
-//
-// SmallVector<T, 0> is a specialization that thinly wraps std::vector.
-//
-// Example usage:
-//
-// ftl::SmallVector<char, 3> vector;
-// assert(vector.empty());
-// assert(!vector.dynamic());
-//
-// vector = {'a', 'b', 'c'};
-// assert(vector.size() == 3u);
-// assert(!vector.dynamic());
-//
-// vector.push_back('d');
-// assert(vector.dynamic());
-//
-// vector.unstable_erase(vector.begin());
-// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
-//
-// vector.pop_back();
-// assert(vector.back() == 'b');
-// assert(vector.dynamic());
-//
-// const char array[] = "hi";
-// vector = ftl::SmallVector(array);
-// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
-// assert(!vector.dynamic());
-//
-// ftl::SmallVector strings = ftl::init::list<std::string>("abc")
-// ("123456", 3u)
-// (3u, '?');
-// assert(strings.size() == 3u);
-// assert(!strings.dynamic());
-//
-// assert(strings[0] == "abc");
-// assert(strings[1] == "123");
-// assert(strings[2] == "???");
-//
-template <typename T, size_t N>
-class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
- using Static = StaticVector<T, N>;
- using Dynamic = SmallVector<T, 0>;
-
- // TODO: Replace with std::remove_cvref_t in C++20.
- template <typename U>
- using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
-
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
-
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
-
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
-
- // Creates an empty vector.
- SmallVector() = default;
-
- // Constructs at most N elements. See StaticVector for underlying constructors.
- template <typename Arg, typename... Args,
- typename = std::enable_if_t<!IsSmallVector<remove_cvref_t<Arg>>{}>>
- SmallVector(Arg&& arg, Args&&... args)
- : mVector(std::in_place_type<Static>, std::forward<Arg>(arg),
- std::forward<Args>(args)...) {}
-
- // Copies at most N elements from a smaller convertible vector.
- template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
- SmallVector(const SmallVector<U, M>& other)
- : SmallVector(IteratorRange, other.begin(), other.end()) {}
-
- void swap(SmallVector& other) { mVector.swap(other.mVector); }
-
- // Returns whether the vector is backed by static or dynamic storage.
- bool dynamic() const { return std::holds_alternative<Dynamic>(mVector); }
-
- // Avoid std::visit as it generates a dispatch table.
-#define DISPATCH(T, F, ...) \
- T F() __VA_ARGS__ { \
- return dynamic() ? std::get<Dynamic>(mVector).F() : std::get<Static>(mVector).F(); \
- }
-
- DISPATCH(size_type, max_size, const)
- DISPATCH(size_type, size, const)
- DISPATCH(bool, empty, const)
-
- // noexcept to suppress warning about zero variadic macro arguments.
- DISPATCH(iterator, begin, noexcept)
- DISPATCH(const_iterator, begin, const)
- DISPATCH(const_iterator, cbegin, const)
-
- DISPATCH(iterator, end, noexcept)
- DISPATCH(const_iterator, end, const)
- DISPATCH(const_iterator, cend, const)
-
- DISPATCH(reverse_iterator, rbegin, noexcept)
- DISPATCH(const_reverse_iterator, rbegin, const)
- DISPATCH(const_reverse_iterator, crbegin, const)
-
- DISPATCH(reverse_iterator, rend, noexcept)
- DISPATCH(const_reverse_iterator, rend, const)
- DISPATCH(const_reverse_iterator, crend, const)
-
- DISPATCH(iterator, last, noexcept)
- DISPATCH(const_iterator, last, const)
-
- DISPATCH(reference, front, noexcept)
- DISPATCH(const_reference, front, const)
-
- DISPATCH(reference, back, noexcept)
- DISPATCH(const_reference, back, const)
-
-#undef DISPATCH
-
- reference operator[](size_type i) {
- return dynamic() ? std::get<Dynamic>(mVector)[i] : std::get<Static>(mVector)[i];
- }
-
- const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
-
- // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
- // replacing at end() is erroneous.
- //
- // The element is emplaced via move constructor, so type T does not need to define copy/move
- // assignment, e.g. its data members may be const.
- //
- // The arguments may directly or indirectly refer to the element being replaced.
- //
- // Iterators to the replaced element point to its replacement, and others remain valid.
- //
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- if (dynamic()) {
- return std::get<Dynamic>(mVector).replace(it, std::forward<Args>(args)...);
- } else {
- return std::get<Static>(mVector).replace(it, std::forward<Args>(args)...);
- }
- }
-
- // Appends an element, and returns a reference to it.
- //
- // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
- // Otherwise, only the end() iterator is invalidated.
- //
- template <typename... Args>
- reference emplace_back(Args&&... args) {
- constexpr auto insertStatic = &Static::template emplace_back<Args...>;
- constexpr auto insertDynamic = &Dynamic::template emplace_back<Args...>;
- return *insert<insertStatic, insertDynamic>(std::forward<Args>(args)...);
- }
-
- // Appends an element.
- //
- // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
- // Otherwise, only the end() iterator is invalidated.
- //
- void push_back(const value_type& v) {
- constexpr auto insertStatic =
- static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
- constexpr auto insertDynamic =
- static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
- insert<insertStatic, insertDynamic>(v);
- }
-
- void push_back(value_type&& v) {
- constexpr auto insertStatic =
- static_cast<bool (Static::*)(value_type&&)>(&Static::push_back);
- constexpr auto insertDynamic =
- static_cast<bool (Dynamic::*)(value_type&&)>(&Dynamic::push_back);
- insert<insertStatic, insertDynamic>(std::move(v));
- }
-
- // Removes the last element. The vector must not be empty, or the call is erroneous.
- //
- // The last() and end() iterators are invalidated.
- //
- void pop_back() {
- if (dynamic()) {
- std::get<Dynamic>(mVector).pop_back();
- } else {
- std::get<Static>(mVector).pop_back();
- }
- }
-
- // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
- // this moves the last element to the slot of the erased element.
- //
- // The last() and end() iterators, as well as those to the erased element, are invalidated.
- //
- void unstable_erase(iterator it) {
- if (dynamic()) {
- std::get<Dynamic>(mVector).unstable_erase(it);
- } else {
- std::get<Static>(mVector).unstable_erase(it);
- }
- }
-
-private:
- template <auto insertStatic, auto insertDynamic, typename... Args>
- auto insert(Args&&... args) {
- if (Dynamic* const vector = std::get_if<Dynamic>(&mVector)) {
- return (vector->*insertDynamic)(std::forward<Args>(args)...);
- }
-
- auto& vector = std::get<Static>(mVector);
- if (vector.full()) {
- return (promote(vector).*insertDynamic)(std::forward<Args>(args)...);
- } else {
- return (vector.*insertStatic)(std::forward<Args>(args)...);
- }
- }
-
- Dynamic& promote(Static& staticVector) {
- assert(staticVector.full());
-
- // Allocate double capacity to reduce probability of reallocation.
- Dynamic vector;
- vector.reserve(Static::max_size() * 2);
- std::move(staticVector.begin(), staticVector.end(), std::back_inserter(vector));
-
- return mVector.template emplace<Dynamic>(std::move(vector));
- }
-
- std::variant<Static, Dynamic> mVector;
-};
-
-// Partial specialization without static storage.
-template <typename T>
-class SmallVector<T, 0> final : ArrayTraits<T>,
- ArrayIterators<SmallVector<T, 0>, T>,
- std::vector<T> {
- using ArrayTraits<T>::construct_at;
-
- using Iter = ArrayIterators<SmallVector, T>;
- using Impl = std::vector<T>;
-
- friend Iter;
-
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
-
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
-
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
-
- using Impl::Impl;
-
- using Impl::empty;
- using Impl::max_size;
- using Impl::size;
-
- using Impl::reserve;
-
- // std::vector iterators are not necessarily raw pointers.
- iterator begin() { return Impl::data(); }
- iterator end() { return Impl::data() + size(); }
-
- using Iter::begin;
- using Iter::end;
-
- using Iter::cbegin;
- using Iter::cend;
-
- using Iter::rbegin;
- using Iter::rend;
-
- using Iter::crbegin;
- using Iter::crend;
-
- using Iter::last;
-
- using Iter::back;
- using Iter::front;
-
- using Iter::operator[];
-
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
- }
-
- template <typename... Args>
- iterator emplace_back(Args&&... args) {
- return &Impl::emplace_back(std::forward<Args>(args)...);
- }
-
- bool push_back(const value_type& v) {
- Impl::push_back(v);
- return true;
- }
-
- bool push_back(value_type&& v) {
- Impl::push_back(std::move(v));
- return true;
- }
-
- using Impl::pop_back;
-
- void unstable_erase(iterator it) {
- if (it != last()) std::iter_swap(it, last());
- pop_back();
- }
-
- void swap(SmallVector& other) { Impl::swap(other); }
-};
-
-template <typename>
-struct IsSmallVector : std::false_type {};
-
-template <typename T, size_t N>
-struct IsSmallVector<SmallVector<T, N>> : std::true_type {};
-
-// Deduction guide for array constructor.
-template <typename T, size_t N>
-SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>;
-
-// Deduction guide for variadic constructor.
-template <typename T, typename... Us, typename V = std::decay_t<T>,
- typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
-SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
-
-// Deduction guide for in-place constructor.
-template <typename T, size_t... Sizes, typename... Types>
-SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
- -> SmallVector<T, sizeof...(Sizes)>;
-
-// Deduction guide for StaticVector conversion.
-template <typename T, size_t N>
-SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>;
-
-template <typename T, size_t N>
-inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
- lhs.swap(rhs);
-}
-
-} // namespace android::ftl
diff --git a/include/ftl/StaticVector.h b/include/ftl/StaticVector.h
deleted file mode 100644
index c132556..0000000
--- a/include/ftl/StaticVector.h
+++ /dev/null
@@ -1,393 +0,0 @@
-/*
- * Copyright 2020 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 <ftl/ArrayTraits.h>
-#include <ftl/InitializerList.h>
-
-#include <algorithm>
-#include <cassert>
-#include <iterator>
-#include <memory>
-#include <type_traits>
-#include <utility>
-
-namespace android::ftl {
-
-constexpr struct IteratorRangeTag {} IteratorRange;
-
-// Fixed-capacity, statically allocated counterpart of std::vector. Akin to std::array, StaticVector
-// allocates contiguous storage for N elements of type T at compile time, but stores at most (rather
-// than exactly) N elements. Unlike std::array, its default constructor does not require T to have a
-// default constructor, since elements are constructed in place as the vector grows. Operations that
-// insert an element (emplace_back, push_back, etc.) fail when the vector is full. The API otherwise
-// adheres to standard containers, except the unstable_erase operation that does not preserve order,
-// and the replace operation that destructively emplaces.
-//
-// StaticVector<T, 1> is analogous to an iterable std::optional, but StaticVector<T, 0> is an error.
-//
-// Example usage:
-//
-// ftl::StaticVector<char, 3> vector;
-// assert(vector.empty());
-//
-// vector = {'a', 'b'};
-// assert(vector.size() == 2u);
-//
-// vector.push_back('c');
-// assert(vector.full());
-//
-// assert(!vector.push_back('d'));
-// assert(vector.size() == 3u);
-//
-// vector.unstable_erase(vector.begin());
-// assert(vector == (ftl::StaticVector{'c', 'b'}));
-//
-// vector.pop_back();
-// assert(vector.back() == 'c');
-//
-// const char array[] = "hi";
-// vector = ftl::StaticVector(array);
-// assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
-//
-// ftl::StaticVector strings = ftl::init::list<std::string>("abc")
-// ("123456", 3u)
-// (3u, '?');
-// assert(strings.size() == 3u);
-// assert(strings[0] == "abc");
-// assert(strings[1] == "123");
-// assert(strings[2] == "???");
-//
-template <typename T, size_t N>
-class StaticVector final : ArrayTraits<T>,
- ArrayIterators<StaticVector<T, N>, T>,
- ArrayComparators<StaticVector> {
- static_assert(N > 0);
-
- using ArrayTraits<T>::construct_at;
-
- using Iter = ArrayIterators<StaticVector, T>;
- friend Iter;
-
- // There is ambiguity when constructing from two iterator-like elements like pointers:
- // they could be an iterator range, or arguments for in-place construction. Assume the
- // latter unless they are input iterators and cannot be used to construct elements. If
- // the former is intended, the caller can pass an IteratorRangeTag to disambiguate.
- template <typename I, typename Traits = std::iterator_traits<I>>
- using IsInputIterator = std::conjunction<
- std::is_base_of<std::input_iterator_tag, typename Traits::iterator_category>,
- std::negation<std::is_constructible<T, I>>>;
-
-public:
- FTL_ARRAY_TRAIT(T, value_type);
- FTL_ARRAY_TRAIT(T, size_type);
- FTL_ARRAY_TRAIT(T, difference_type);
-
- FTL_ARRAY_TRAIT(T, pointer);
- FTL_ARRAY_TRAIT(T, reference);
- FTL_ARRAY_TRAIT(T, iterator);
- FTL_ARRAY_TRAIT(T, reverse_iterator);
-
- FTL_ARRAY_TRAIT(T, const_pointer);
- FTL_ARRAY_TRAIT(T, const_reference);
- FTL_ARRAY_TRAIT(T, const_iterator);
- FTL_ARRAY_TRAIT(T, const_reverse_iterator);
-
- // Creates an empty vector.
- StaticVector() = default;
-
- // Copies and moves a vector, respectively.
- StaticVector(const StaticVector& other)
- : StaticVector(IteratorRange, other.begin(), other.end()) {}
- StaticVector(StaticVector&& other) { swap<Empty>(other); }
-
- // Copies at most N elements from a smaller convertible vector.
- template <typename U, size_t M, typename = std::enable_if_t<M <= N>>
- StaticVector(const StaticVector<U, M>& other)
- : StaticVector(IteratorRange, other.begin(), other.end()) {}
-
- // Copies at most N elements from an array.
- template <typename U, size_t M>
- explicit StaticVector(U (&array)[M])
- : StaticVector(IteratorRange, std::begin(array), std::end(array)) {}
-
- // Copies at most N elements from the range [first, last).
- //
- // IteratorRangeTag disambiguates with initialization from two iterator-like elements.
- //
- template <typename Iterator, typename = std::enable_if_t<IsInputIterator<Iterator>{}>>
- StaticVector(Iterator first, Iterator last) : StaticVector(IteratorRange, first, last) {
- using V = typename std::iterator_traits<Iterator>::value_type;
- static_assert(std::is_constructible_v<value_type, V>, "Incompatible iterator range");
- }
-
- template <typename Iterator>
- StaticVector(IteratorRangeTag, Iterator first, Iterator last)
- : mSize(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
- std::uninitialized_copy(first, first + mSize, begin());
- }
-
- // Constructs at most N elements. The template arguments T and N are inferred using the
- // deduction guide defined below. Note that T is determined from the first element, and
- // subsequent elements must have convertible types:
- //
- // ftl::StaticVector vector = {1, 2, 3};
- // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<int, 3>>);
- //
- // const auto copy = "quince"s;
- // auto move = "tart"s;
- // ftl::StaticVector vector = {copy, std::move(move)};
- //
- // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 2>>);
- //
- template <typename E, typename... Es,
- typename = std::enable_if_t<std::is_constructible_v<value_type, E>>>
- StaticVector(E&& element, Es&&... elements)
- : StaticVector(std::index_sequence<0>{}, std::forward<E>(element),
- std::forward<Es>(elements)...) {
- static_assert(sizeof...(elements) < N, "Too many elements");
- }
-
- // Constructs at most N elements in place by forwarding per-element constructor arguments. The
- // template arguments T and N are inferred using the deduction guide defined below. The syntax
- // for listing arguments is as follows:
- //
- // ftl::StaticVector vector = ftl::init::list<std::string>("abc")()(3u, '?');
- //
- // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 3>>);
- // assert(vector.full());
- // assert(vector[0] == "abc");
- // assert(vector[1].empty());
- // assert(vector[2] == "???");
- //
- template <typename U, size_t Size, size_t... Sizes, typename... Types>
- StaticVector(InitializerList<U, std::index_sequence<Size, Sizes...>, Types...>&& init)
- : StaticVector(std::index_sequence<0, 0, Size>{}, std::make_index_sequence<Size>{},
- std::index_sequence<Sizes...>{}, init.tuple) {}
-
- ~StaticVector() { std::destroy(begin(), end()); }
-
- StaticVector& operator=(const StaticVector& other) {
- StaticVector copy(other);
- swap(copy);
- return *this;
- }
-
- StaticVector& operator=(StaticVector&& other) {
- std::destroy(begin(), end());
- mSize = 0;
- swap<Empty>(other);
- return *this;
- }
-
- template <typename = void>
- void swap(StaticVector&);
-
- static constexpr size_type max_size() { return N; }
- size_type size() const { return mSize; }
-
- bool empty() const { return size() == 0; }
- bool full() const { return size() == max_size(); }
-
- iterator begin() { return std::launder(reinterpret_cast<pointer>(mData)); }
- iterator end() { return begin() + size(); }
-
- using Iter::begin;
- using Iter::end;
-
- using Iter::cbegin;
- using Iter::cend;
-
- using Iter::rbegin;
- using Iter::rend;
-
- using Iter::crbegin;
- using Iter::crend;
-
- using Iter::last;
-
- using Iter::back;
- using Iter::front;
-
- using Iter::operator[];
-
- // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
- // replacing at end() is erroneous.
- //
- // The element is emplaced via move constructor, so type T does not need to define copy/move
- // assignment, e.g. its data members may be const.
- //
- // The arguments may directly or indirectly refer to the element being replaced.
- //
- // Iterators to the replaced element point to its replacement, and others remain valid.
- //
- template <typename... Args>
- reference replace(const_iterator it, Args&&... args) {
- value_type element{std::forward<Args>(args)...};
- std::destroy_at(it);
- // This is only safe because exceptions are disabled.
- return *construct_at(it, std::move(element));
- }
-
- // Appends an element, and returns an iterator to it. If the vector is full, the element is not
- // inserted, and the end() iterator is returned.
- //
- // On success, the end() iterator is invalidated.
- //
- template <typename... Args>
- iterator emplace_back(Args&&... args) {
- if (full()) return end();
- const iterator it = construct_at(end(), std::forward<Args>(args)...);
- ++mSize;
- return it;
- }
-
- // Appends an element unless the vector is full, and returns whether the element was inserted.
- //
- // On success, the end() iterator is invalidated.
- //
- bool push_back(const value_type& v) {
- // Two statements for sequence point.
- const iterator it = emplace_back(v);
- return it != end();
- }
-
- bool push_back(value_type&& v) {
- // Two statements for sequence point.
- const iterator it = emplace_back(std::move(v));
- return it != end();
- }
-
- // Removes the last element. The vector must not be empty, or the call is erroneous.
- //
- // The last() and end() iterators are invalidated.
- //
- void pop_back() { unstable_erase(last()); }
-
- // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
- // this moves the last element to the slot of the erased element.
- //
- // The last() and end() iterators, as well as those to the erased element, are invalidated.
- //
- void unstable_erase(const_iterator it) {
- std::destroy_at(it);
- if (it != last()) {
- // Move last element and destroy its source for destructor side effects. This is only
- // safe because exceptions are disabled.
- construct_at(it, std::move(back()));
- std::destroy_at(last());
- }
- --mSize;
- }
-
-private:
- struct Empty {};
-
- // Recursion for variadic constructor.
- template <size_t I, typename E, typename... Es>
- StaticVector(std::index_sequence<I>, E&& element, Es&&... elements)
- : StaticVector(std::index_sequence<I + 1>{}, std::forward<Es>(elements)...) {
- construct_at(begin() + I, std::forward<E>(element));
- }
-
- // Base case for variadic constructor.
- template <size_t I>
- explicit StaticVector(std::index_sequence<I>) : mSize(I) {}
-
- // Recursion for in-place constructor.
- //
- // Construct element I by extracting its arguments from the InitializerList tuple. ArgIndex
- // is the position of its first argument in Args, and ArgCount is the number of arguments.
- // The Indices sequence corresponds to [0, ArgCount).
- //
- // The Sizes sequence lists the argument counts for elements after I, so Size is the ArgCount
- // for the next element. The recursion stops when Sizes is empty for the last element.
- //
- template <size_t I, size_t ArgIndex, size_t ArgCount, size_t... Indices, size_t Size,
- size_t... Sizes, typename... Args>
- StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
- std::index_sequence<Size, Sizes...>, std::tuple<Args...>& tuple)
- : StaticVector(std::index_sequence<I + 1, ArgIndex + ArgCount, Size>{},
- std::make_index_sequence<Size>{}, std::index_sequence<Sizes...>{}, tuple) {
- construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
- }
-
- // Base case for in-place constructor.
- template <size_t I, size_t ArgIndex, size_t ArgCount, size_t... Indices, typename... Args>
- StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
- std::index_sequence<>, std::tuple<Args...>& tuple)
- : mSize(I + 1) {
- construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
- }
-
- size_type mSize = 0;
- std::aligned_storage_t<sizeof(value_type), alignof(value_type)> mData[N];
-};
-
-// Deduction guide for array constructor.
-template <typename T, size_t N>
-StaticVector(T (&)[N]) -> StaticVector<std::remove_cv_t<T>, N>;
-
-// Deduction guide for variadic constructor.
-template <typename T, typename... Us, typename V = std::decay_t<T>,
- typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
-StaticVector(T&&, Us&&...) -> StaticVector<V, 1 + sizeof...(Us)>;
-
-// Deduction guide for in-place constructor.
-template <typename T, size_t... Sizes, typename... Types>
-StaticVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
- -> StaticVector<T, sizeof...(Sizes)>;
-
-template <typename T, size_t N>
-template <typename E>
-void StaticVector<T, N>::swap(StaticVector& other) {
- auto [to, from] = std::make_pair(this, &other);
- if (from == this) return;
-
- // Assume this vector has fewer elements, so the excess of the other vector will be moved to it.
- auto [min, max] = std::make_pair(size(), other.size());
-
- // No elements to swap if moving into an empty vector.
- if constexpr (std::is_same_v<E, Empty>) {
- assert(min == 0);
- } else {
- if (min > max) {
- std::swap(from, to);
- std::swap(min, max);
- }
-
- // Swap elements [0, min).
- std::swap_ranges(begin(), begin() + min, other.begin());
-
- // No elements to move if sizes are equal.
- if (min == max) return;
- }
-
- // Move elements [min, max) and destroy their source for destructor side effects.
- const auto [first, last] = std::make_pair(from->begin() + min, from->begin() + max);
- std::uninitialized_move(first, last, to->begin() + min);
- std::destroy(first, last);
-
- std::swap(mSize, other.mSize);
-}
-
-template <typename T, size_t N>
-inline void swap(StaticVector<T, N>& lhs, StaticVector<T, N>& rhs) {
- lhs.swap(rhs);
-}
-
-} // namespace android::ftl
diff --git a/include/ftl/array_traits.h b/include/ftl/array_traits.h
new file mode 100644
index 0000000..1265fa1
--- /dev/null
+++ b/include/ftl/array_traits.h
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2020 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 <algorithm>
+#include <iterator>
+#include <new>
+#include <type_traits>
+
+#define FTL_ARRAY_TRAIT(T, U) using U = typename ArrayTraits<T>::U
+
+namespace android::ftl {
+
+template <typename T>
+struct ArrayTraits {
+ using value_type = T;
+ using size_type = std::size_t;
+ using difference_type = std::ptrdiff_t;
+
+ using pointer = value_type*;
+ using reference = value_type&;
+ using iterator = pointer;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+
+ using const_pointer = const value_type*;
+ using const_reference = const value_type&;
+ using const_iterator = const_pointer;
+ using const_reverse_iterator = std::reverse_iterator<const_iterator>;
+
+ template <typename... Args>
+ static pointer construct_at(const_iterator it, Args&&... args) {
+ void* const ptr = const_cast<void*>(static_cast<const void*>(it));
+ if constexpr (std::is_constructible_v<value_type, Args...>) {
+ // TODO: Replace with std::construct_at in C++20.
+ return new (ptr) value_type(std::forward<Args>(args)...);
+ } else {
+ // Fall back to list initialization.
+ return new (ptr) value_type{std::forward<Args>(args)...};
+ }
+ }
+};
+
+// CRTP mixin to define iterator functions in terms of non-const Self::begin and Self::end.
+template <typename Self, typename T>
+class ArrayIterators {
+ FTL_ARRAY_TRAIT(T, size_type);
+
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
+
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+
+ Self& self() const { return *const_cast<Self*>(static_cast<const Self*>(this)); }
+
+ public:
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return self().begin(); }
+
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return self().end(); }
+
+ reverse_iterator rbegin() { return std::make_reverse_iterator(self().end()); }
+ const_reverse_iterator rbegin() const { return crbegin(); }
+ const_reverse_iterator crbegin() const { return self().rbegin(); }
+
+ reverse_iterator rend() { return std::make_reverse_iterator(self().begin()); }
+ const_reverse_iterator rend() const { return crend(); }
+ const_reverse_iterator crend() const { return self().rend(); }
+
+ iterator last() { return self().end() - 1; }
+ const_iterator last() const { return self().last(); }
+
+ reference front() { return *self().begin(); }
+ const_reference front() const { return self().front(); }
+
+ reference back() { return *last(); }
+ const_reference back() const { return self().back(); }
+
+ reference operator[](size_type i) { return *(self().begin() + i); }
+ const_reference operator[](size_type i) const { return self()[i]; }
+};
+
+// Mixin to define comparison operators for an array-like template.
+// TODO: Replace with operator<=> in C++20.
+template <template <typename, std::size_t> class Array>
+struct ArrayComparators {
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator==(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin());
+ }
+
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator<(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+ }
+
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator>(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return rhs < lhs;
+ }
+
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator!=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs == rhs);
+ }
+
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator>=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs < rhs);
+ }
+
+ template <typename T, std::size_t N, std::size_t M>
+ friend bool operator<=(const Array<T, N>& lhs, const Array<T, M>& rhs) {
+ return !(lhs > rhs);
+ }
+};
+
+} // namespace android::ftl
diff --git a/include/ftl/future.h b/include/ftl/future.h
new file mode 100644
index 0000000..dd6358f
--- /dev/null
+++ b/include/ftl/future.h
@@ -0,0 +1,109 @@
+/*
+ * Copyright 2020 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 <future>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+// Creates a future that defers a function call until its result is queried.
+//
+// auto future = ftl::defer([](int x) { return x + 1; }, 99);
+// assert(future.get() == 100);
+//
+template <typename F, typename... Args>
+inline auto defer(F&& f, Args&&... args) {
+ return std::async(std::launch::deferred, std::forward<F>(f), std::forward<Args>(args)...);
+}
+
+// Creates a future that wraps a value.
+//
+// auto future = ftl::yield(42);
+// assert(future.get() == 42);
+//
+// auto ptr = std::make_unique<char>('!');
+// auto future = ftl::yield(std::move(ptr));
+// assert(*future.get() == '!');
+//
+template <typename T>
+inline std::future<T> yield(T&& v) {
+ return defer([](T&& v) { return std::forward<T>(v); }, std::forward<T>(v));
+}
+
+namespace details {
+
+template <typename T>
+struct future_result {
+ using type = T;
+};
+
+template <typename T>
+struct future_result<std::future<T>> {
+ using type = T;
+};
+
+template <typename T>
+using future_result_t = typename future_result<T>::type;
+
+// Attaches a continuation to a future. The continuation is a function that maps T to either R or
+// std::future<R>. In the former case, the chain wraps the result in a future as if by ftl::yield.
+//
+// auto future = ftl::yield(123);
+// std::future<char> futures[] = {ftl::yield('a'), ftl::yield('b')};
+//
+// std::future<char> chain =
+// ftl::chain(std::move(future))
+// .then([](int x) { return static_cast<std::size_t>(x % 2); })
+// .then([&futures](std::size_t i) { return std::move(futures[i]); });
+//
+// assert(chain.get() == 'b');
+//
+template <typename T>
+struct Chain {
+ // Implicit conversion.
+ Chain(std::future<T>&& f) : future(std::move(f)) {}
+ operator std::future<T>&&() && { return std::move(future); }
+
+ T get() && { return future.get(); }
+
+ template <typename F, typename R = std::invoke_result_t<F, T>>
+ auto then(F&& op) && -> Chain<future_result_t<R>> {
+ return defer(
+ [](auto&& f, F&& op) {
+ R r = op(f.get());
+ if constexpr (std::is_same_v<R, future_result_t<R>>) {
+ return r;
+ } else {
+ return r.get();
+ }
+ },
+ std::move(future), std::forward<F>(op));
+ }
+
+ std::future<T> future;
+};
+
+} // namespace details
+
+template <typename T>
+inline auto chain(std::future<T>&& f) -> details::Chain<T> {
+ return std::move(f);
+}
+
+} // namespace android::ftl
diff --git a/include/ftl/initializer_list.h b/include/ftl/initializer_list.h
new file mode 100644
index 0000000..769c09f
--- /dev/null
+++ b/include/ftl/initializer_list.h
@@ -0,0 +1,108 @@
+/*
+ * Copyright 2020 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 <tuple>
+#include <utility>
+
+namespace android::ftl {
+
+// Compile-time counterpart of std::initializer_list<T> that stores per-element constructor
+// arguments with heterogeneous types. For a container with elements of type T, given Sizes
+// (S0, S1, ..., SN), N elements are initialized: the first element is initialized with the
+// first S0 arguments, the second element is initialized with the next S1 arguments, and so
+// on. The list of Types (T0, ..., TM) is flattened, so M is equal to the sum of the Sizes.
+//
+// An InitializerList is created using ftl::init::list, and is consumed by constructors of
+// containers. The function call operator is overloaded such that arguments are accumulated
+// in a tuple with each successive call. For instance, the following calls initialize three
+// strings using different constructors, i.e. string literal, default, and count/character:
+//
+// ... = ftl::init::list<std::string>("abc")()(3u, '?');
+//
+// The following syntax is a shorthand for key-value pairs, where the first argument is the
+// key, and the rest construct the value. The types of the key and value are deduced if the
+// first pair contains exactly two arguments:
+//
+// ... = ftl::init::map<int, std::string>(-1, "abc")(-2)(-3, 3u, '?');
+//
+// ... = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+//
+// WARNING: The InitializerList returned by an ftl::init::list expression must be consumed
+// immediately, since temporary arguments are destroyed after the full expression. Storing
+// an InitializerList results in dangling references.
+//
+template <typename T, typename Sizes = std::index_sequence<>, typename... Types>
+struct InitializerList;
+
+template <typename T, std::size_t... Sizes, typename... Types>
+struct InitializerList<T, std::index_sequence<Sizes...>, Types...> {
+ // Creates a superset InitializerList by appending the number of arguments to Sizes, and
+ // expanding Types with forwarding references for each argument.
+ template <typename... Args>
+ [[nodiscard]] constexpr auto operator()(Args&&... args) && -> InitializerList<
+ T, std::index_sequence<Sizes..., sizeof...(Args)>, Types..., Args&&...> {
+ return {std::tuple_cat(std::move(tuple), std::forward_as_tuple(std::forward<Args>(args)...))};
+ }
+
+ // The temporary InitializerList returned by operator() is bound to an rvalue reference in
+ // container constructors, which extends the lifetime of any temporary arguments that this
+ // tuple refers to until the completion of the full expression containing the construction.
+ std::tuple<Types...> tuple;
+};
+
+template <typename K, typename V>
+struct KeyValue {};
+
+// Shorthand for key-value pairs that assigns the first argument to the key, and the rest to the
+// value. The specialization is on KeyValue rather than std::pair, so that ftl::init::list works
+// with the latter.
+template <typename K, typename V, std::size_t... Sizes, typename... Types>
+struct InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...> {
+ // Accumulate the three arguments to std::pair's piecewise constructor.
+ template <typename... Args>
+ [[nodiscard]] constexpr auto operator()(K&& k, Args&&... args) && -> InitializerList<
+ KeyValue<K, V>, std::index_sequence<Sizes..., 3>, Types..., std::piecewise_construct_t,
+ std::tuple<K&&>, std::tuple<Args&&...>> {
+ return {std::tuple_cat(
+ std::move(tuple),
+ std::forward_as_tuple(std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)),
+ std::forward_as_tuple(std::forward<Args>(args)...)))};
+ }
+
+ std::tuple<Types...> tuple;
+};
+
+namespace init {
+
+template <typename T, typename... Args>
+[[nodiscard]] constexpr auto list(Args&&... args) {
+ return InitializerList<T>{}(std::forward<Args>(args)...);
+}
+
+template <typename K, typename V, typename... Args>
+[[nodiscard]] constexpr auto map(Args&&... args) {
+ return list<KeyValue<K, V>>(std::forward<Args>(args)...);
+}
+
+template <typename K, typename V>
+[[nodiscard]] constexpr auto map(K&& k, V&& v) {
+ return list<KeyValue<K, V>>(std::forward<K>(k), std::forward<V>(v));
+}
+
+} // namespace init
+} // namespace android::ftl
diff --git a/include/ftl/small_map.h b/include/ftl/small_map.h
new file mode 100644
index 0000000..84c15eb
--- /dev/null
+++ b/include/ftl/small_map.h
@@ -0,0 +1,203 @@
+/*
+ * Copyright 2020 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 <ftl/initializer_list.h>
+#include <ftl/small_vector.h>
+
+#include <functional>
+#include <optional>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+// Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
+// stored in contiguous storage for cache efficiency. The map is allocated statically until its size
+// exceeds N, at which point mappings are relocated to dynamic memory.
+//
+// SmallMap<K, V, 0> unconditionally allocates on the heap.
+//
+// Example usage:
+//
+// ftl::SmallMap<int, std::string, 3> map;
+// assert(map.empty());
+// assert(!map.dynamic());
+//
+// map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+// assert(map.size() == 3u);
+// assert(!map.dynamic());
+//
+// assert(map.contains(123));
+// assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u);
+//
+// const auto opt = map.find(-1);
+// assert(opt);
+//
+// std::string& ref = *opt;
+// assert(ref.empty());
+// ref = "xyz";
+//
+// assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+//
+template <typename K, typename V, std::size_t N>
+class SmallMap final {
+ using Map = SmallVector<std::pair<const K, V>, N>;
+
+ public:
+ using key_type = K;
+ using mapped_type = V;
+
+ using value_type = typename Map::value_type;
+ using size_type = typename Map::size_type;
+ using difference_type = typename Map::difference_type;
+
+ using reference = typename Map::reference;
+ using iterator = typename Map::iterator;
+
+ using const_reference = typename Map::const_reference;
+ using const_iterator = typename Map::const_iterator;
+
+ // Creates an empty map.
+ SmallMap() = default;
+
+ // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
+ // The template arguments K, V, and N are inferred using the deduction guide defined below.
+ // The syntax for listing pairs is as follows:
+ //
+ // ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+ //
+ // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
+ // assert(map.size() == 3u);
+ // assert(map.contains(-1) && map.find(-1)->get().empty());
+ // assert(map.contains(42) && map.find(42)->get() == "???");
+ // assert(map.contains(123) && map.find(123)->get() == "abc");
+ //
+ // The types of the key and value are deduced if the first pair contains exactly two arguments:
+ //
+ // ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+ // static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
+ //
+ template <typename U, std::size_t... Sizes, typename... Types>
+ SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& list)
+ : map_(std::move(list)) {
+ // TODO: Enforce unique keys.
+ }
+
+ size_type max_size() const { return map_.max_size(); }
+ size_type size() const { return map_.size(); }
+ bool empty() const { return map_.empty(); }
+
+ // Returns whether the map is backed by static or dynamic storage.
+ bool dynamic() const { return map_.dynamic(); }
+
+ iterator begin() { return map_.begin(); }
+ const_iterator begin() const { return cbegin(); }
+ const_iterator cbegin() const { return map_.cbegin(); }
+
+ iterator end() { return map_.end(); }
+ const_iterator end() const { return cend(); }
+ const_iterator cend() const { return map_.cend(); }
+
+ // Returns whether a mapping exists for the given key.
+ bool contains(const key_type& key) const {
+ return find(key, [](const mapped_type&) {});
+ }
+
+ // Returns a reference to the value for the given key, or std::nullopt if the key was not found.
+ //
+ // ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+ //
+ // const auto opt = map.find('c');
+ // assert(opt == 'C');
+ //
+ // char d = 'd';
+ // const auto ref = map.find('d').value_or(std::ref(d));
+ // ref.get() = 'D';
+ // assert(d == 'D');
+ //
+ auto find(const key_type& key) const -> std::optional<std::reference_wrapper<const mapped_type>> {
+ return find(key, [](const mapped_type& v) { return std::cref(v); });
+ }
+
+ auto find(const key_type& key) -> std::optional<std::reference_wrapper<mapped_type>> {
+ return find(key, [](mapped_type& v) { return std::ref(v); });
+ }
+
+ // Returns the result R of a unary operation F on (a constant or mutable reference to) the value
+ // for the given key, or std::nullopt if the key was not found. If F has a return type of void,
+ // then the Boolean result indicates whether the key was found.
+ //
+ // ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ //
+ // assert(map.find('c', [](char c) { return std::toupper(c); }) == 'Z');
+ // assert(map.find('c', [](char& c) { c = std::toupper(c); }));
+ //
+ template <typename F, typename R = std::invoke_result_t<F, const mapped_type&>>
+ auto find(const key_type& key, F f) const
+ -> std::conditional_t<std::is_void_v<R>, bool, std::optional<R>> {
+ for (auto& [k, v] : *this) {
+ if (k == key) {
+ if constexpr (std::is_void_v<R>) {
+ f(v);
+ return true;
+ } else {
+ return f(v);
+ }
+ }
+ }
+
+ return {};
+ }
+
+ template <typename F>
+ auto find(const key_type& key, F f) {
+ return std::as_const(*this).find(
+ key, [&f](const mapped_type& v) { return f(const_cast<mapped_type&>(v)); });
+ }
+
+ private:
+ Map map_;
+};
+
+// Deduction guide for in-place constructor.
+template <typename K, typename V, std::size_t... Sizes, typename... Types>
+SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&)
+ -> SmallMap<K, V, sizeof...(Sizes)>;
+
+// Returns whether the key-value pairs of two maps are equal.
+template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M>
+bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+ if (lhs.size() != rhs.size()) return false;
+
+ for (const auto& [k, v] : lhs) {
+ const auto& lv = v;
+ if (!rhs.find(k, [&lv](const auto& rv) { return lv == rv; }).value_or(false)) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
+// TODO: Remove in C++20.
+template <typename K, typename V, std::size_t N, typename Q, typename W, std::size_t M>
+inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+ return !(lhs == rhs);
+}
+
+} // namespace android::ftl
diff --git a/include/ftl/small_vector.h b/include/ftl/small_vector.h
new file mode 100644
index 0000000..cb0ae35
--- /dev/null
+++ b/include/ftl/small_vector.h
@@ -0,0 +1,387 @@
+/*
+ * Copyright 2020 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 <ftl/array_traits.h>
+#include <ftl/static_vector.h>
+
+#include <algorithm>
+#include <iterator>
+#include <type_traits>
+#include <utility>
+#include <variant>
+#include <vector>
+
+namespace android::ftl {
+
+template <typename>
+struct is_small_vector;
+
+// ftl::StaticVector that promotes to std::vector when full. SmallVector is a drop-in replacement
+// for std::vector with statically allocated storage for N elements, whose goal is to improve run
+// time by avoiding heap allocation and increasing probability of cache hits. The standard API is
+// augmented by an unstable_erase operation that does not preserve order, and a replace operation
+// that destructively emplaces.
+//
+// SmallVector<T, 0> is a specialization that thinly wraps std::vector.
+//
+// Example usage:
+//
+// ftl::SmallVector<char, 3> vector;
+// assert(vector.empty());
+// assert(!vector.dynamic());
+//
+// vector = {'a', 'b', 'c'};
+// assert(vector.size() == 3u);
+// assert(!vector.dynamic());
+//
+// vector.push_back('d');
+// assert(vector.dynamic());
+//
+// vector.unstable_erase(vector.begin());
+// assert(vector == (ftl::SmallVector{'d', 'b', 'c'}));
+//
+// vector.pop_back();
+// assert(vector.back() == 'b');
+// assert(vector.dynamic());
+//
+// const char array[] = "hi";
+// vector = ftl::SmallVector(array);
+// assert(vector == (ftl::SmallVector{'h', 'i', '\0'}));
+// assert(!vector.dynamic());
+//
+// ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+// assert(strings.size() == 3u);
+// assert(!strings.dynamic());
+//
+// assert(strings[0] == "abc");
+// assert(strings[1] == "123");
+// assert(strings[2] == "???");
+//
+template <typename T, std::size_t N>
+class SmallVector final : ArrayTraits<T>, ArrayComparators<SmallVector> {
+ using Static = StaticVector<T, N>;
+ using Dynamic = SmallVector<T, 0>;
+
+ // TODO: Replace with std::remove_cvref_t in C++20.
+ template <typename U>
+ using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<U>>;
+
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
+
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
+
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+
+ // Creates an empty vector.
+ SmallVector() = default;
+
+ // Constructs at most N elements. See StaticVector for underlying constructors.
+ template <typename Arg, typename... Args,
+ typename = std::enable_if_t<!is_small_vector<remove_cvref_t<Arg>>{}>>
+ SmallVector(Arg&& arg, Args&&... args)
+ : vector_(std::in_place_type<Static>, std::forward<Arg>(arg), std::forward<Args>(args)...) {}
+
+ // Copies at most N elements from a smaller convertible vector.
+ template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
+ SmallVector(const SmallVector<U, M>& other)
+ : SmallVector(kIteratorRange, other.begin(), other.end()) {}
+
+ void swap(SmallVector& other) { vector_.swap(other.vector_); }
+
+ // Returns whether the vector is backed by static or dynamic storage.
+ bool dynamic() const { return std::holds_alternative<Dynamic>(vector_); }
+
+ // Avoid std::visit as it generates a dispatch table.
+#define DISPATCH(T, F, ...) \
+ T F() __VA_ARGS__ { \
+ return dynamic() ? std::get<Dynamic>(vector_).F() : std::get<Static>(vector_).F(); \
+ }
+
+ DISPATCH(size_type, max_size, const)
+ DISPATCH(size_type, size, const)
+ DISPATCH(bool, empty, const)
+
+ // noexcept to suppress warning about zero variadic macro arguments.
+ DISPATCH(iterator, begin, noexcept)
+ DISPATCH(const_iterator, begin, const)
+ DISPATCH(const_iterator, cbegin, const)
+
+ DISPATCH(iterator, end, noexcept)
+ DISPATCH(const_iterator, end, const)
+ DISPATCH(const_iterator, cend, const)
+
+ DISPATCH(reverse_iterator, rbegin, noexcept)
+ DISPATCH(const_reverse_iterator, rbegin, const)
+ DISPATCH(const_reverse_iterator, crbegin, const)
+
+ DISPATCH(reverse_iterator, rend, noexcept)
+ DISPATCH(const_reverse_iterator, rend, const)
+ DISPATCH(const_reverse_iterator, crend, const)
+
+ DISPATCH(iterator, last, noexcept)
+ DISPATCH(const_iterator, last, const)
+
+ DISPATCH(reference, front, noexcept)
+ DISPATCH(const_reference, front, const)
+
+ DISPATCH(reference, back, noexcept)
+ DISPATCH(const_reference, back, const)
+
+#undef DISPATCH
+
+ reference operator[](size_type i) {
+ return dynamic() ? std::get<Dynamic>(vector_)[i] : std::get<Static>(vector_)[i];
+ }
+
+ const_reference operator[](size_type i) const { return const_cast<SmallVector&>(*this)[i]; }
+
+ // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
+ // replacing at end() is erroneous.
+ //
+ // The element is emplaced via move constructor, so type T does not need to define copy/move
+ // assignment, e.g. its data members may be const.
+ //
+ // The arguments may directly or indirectly refer to the element being replaced.
+ //
+ // Iterators to the replaced element point to its replacement, and others remain valid.
+ //
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ if (dynamic()) {
+ return std::get<Dynamic>(vector_).replace(it, std::forward<Args>(args)...);
+ } else {
+ return std::get<Static>(vector_).replace(it, std::forward<Args>(args)...);
+ }
+ }
+
+ // Appends an element, and returns a reference to it.
+ //
+ // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
+ // Otherwise, only the end() iterator is invalidated.
+ //
+ template <typename... Args>
+ reference emplace_back(Args&&... args) {
+ constexpr auto kInsertStatic = &Static::template emplace_back<Args...>;
+ constexpr auto kInsertDynamic = &Dynamic::template emplace_back<Args...>;
+ return *insert<kInsertStatic, kInsertDynamic>(std::forward<Args>(args)...);
+ }
+
+ // Appends an element.
+ //
+ // If the vector reaches its static or dynamic capacity, then all iterators are invalidated.
+ // Otherwise, only the end() iterator is invalidated.
+ //
+ void push_back(const value_type& v) {
+ constexpr auto kInsertStatic =
+ static_cast<bool (Static::*)(const value_type&)>(&Static::push_back);
+ constexpr auto kInsertDynamic =
+ static_cast<bool (Dynamic::*)(const value_type&)>(&Dynamic::push_back);
+ insert<kInsertStatic, kInsertDynamic>(v);
+ }
+
+ void push_back(value_type&& v) {
+ constexpr auto kInsertStatic = static_cast<bool (Static::*)(value_type &&)>(&Static::push_back);
+ constexpr auto kInsertDynamic =
+ static_cast<bool (Dynamic::*)(value_type &&)>(&Dynamic::push_back);
+ insert<kInsertStatic, kInsertDynamic>(std::move(v));
+ }
+
+ // Removes the last element. The vector must not be empty, or the call is erroneous.
+ //
+ // The last() and end() iterators are invalidated.
+ //
+ void pop_back() {
+ if (dynamic()) {
+ std::get<Dynamic>(vector_).pop_back();
+ } else {
+ std::get<Static>(vector_).pop_back();
+ }
+ }
+
+ // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
+ // this moves the last element to the slot of the erased element.
+ //
+ // The last() and end() iterators, as well as those to the erased element, are invalidated.
+ //
+ void unstable_erase(iterator it) {
+ if (dynamic()) {
+ std::get<Dynamic>(vector_).unstable_erase(it);
+ } else {
+ std::get<Static>(vector_).unstable_erase(it);
+ }
+ }
+
+ private:
+ template <auto InsertStatic, auto InsertDynamic, typename... Args>
+ auto insert(Args&&... args) {
+ if (Dynamic* const vector = std::get_if<Dynamic>(&vector_)) {
+ return (vector->*InsertDynamic)(std::forward<Args>(args)...);
+ }
+
+ auto& vector = std::get<Static>(vector_);
+ if (vector.full()) {
+ return (promote(vector).*InsertDynamic)(std::forward<Args>(args)...);
+ } else {
+ return (vector.*InsertStatic)(std::forward<Args>(args)...);
+ }
+ }
+
+ Dynamic& promote(Static& static_vector) {
+ assert(static_vector.full());
+
+ // Allocate double capacity to reduce probability of reallocation.
+ Dynamic vector;
+ vector.reserve(Static::max_size() * 2);
+ std::move(static_vector.begin(), static_vector.end(), std::back_inserter(vector));
+
+ return vector_.template emplace<Dynamic>(std::move(vector));
+ }
+
+ std::variant<Static, Dynamic> vector_;
+};
+
+// Partial specialization without static storage.
+template <typename T>
+class SmallVector<T, 0> final : ArrayTraits<T>,
+ ArrayIterators<SmallVector<T, 0>, T>,
+ std::vector<T> {
+ using ArrayTraits<T>::construct_at;
+
+ using Iter = ArrayIterators<SmallVector, T>;
+ using Impl = std::vector<T>;
+
+ friend Iter;
+
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
+
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
+
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+
+ using Impl::Impl;
+
+ using Impl::empty;
+ using Impl::max_size;
+ using Impl::size;
+
+ using Impl::reserve;
+
+ // std::vector iterators are not necessarily raw pointers.
+ iterator begin() { return Impl::data(); }
+ iterator end() { return Impl::data() + size(); }
+
+ using Iter::begin;
+ using Iter::end;
+
+ using Iter::cbegin;
+ using Iter::cend;
+
+ using Iter::rbegin;
+ using Iter::rend;
+
+ using Iter::crbegin;
+ using Iter::crend;
+
+ using Iter::last;
+
+ using Iter::back;
+ using Iter::front;
+
+ using Iter::operator[];
+
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ value_type element{std::forward<Args>(args)...};
+ std::destroy_at(it);
+ // This is only safe because exceptions are disabled.
+ return *construct_at(it, std::move(element));
+ }
+
+ template <typename... Args>
+ iterator emplace_back(Args&&... args) {
+ return &Impl::emplace_back(std::forward<Args>(args)...);
+ }
+
+ bool push_back(const value_type& v) {
+ Impl::push_back(v);
+ return true;
+ }
+
+ bool push_back(value_type&& v) {
+ Impl::push_back(std::move(v));
+ return true;
+ }
+
+ using Impl::pop_back;
+
+ void unstable_erase(iterator it) {
+ if (it != last()) std::iter_swap(it, last());
+ pop_back();
+ }
+
+ void swap(SmallVector& other) { Impl::swap(other); }
+};
+
+template <typename>
+struct is_small_vector : std::false_type {};
+
+template <typename T, std::size_t N>
+struct is_small_vector<SmallVector<T, N>> : std::true_type {};
+
+// Deduction guide for array constructor.
+template <typename T, std::size_t N>
+SmallVector(T (&)[N]) -> SmallVector<std::remove_cv_t<T>, N>;
+
+// Deduction guide for variadic constructor.
+template <typename T, typename... Us, typename V = std::decay_t<T>,
+ typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
+SmallVector(T&&, Us&&...) -> SmallVector<V, 1 + sizeof...(Us)>;
+
+// Deduction guide for in-place constructor.
+template <typename T, std::size_t... Sizes, typename... Types>
+SmallVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
+ -> SmallVector<T, sizeof...(Sizes)>;
+
+// Deduction guide for StaticVector conversion.
+template <typename T, std::size_t N>
+SmallVector(StaticVector<T, N>&&) -> SmallVector<T, N>;
+
+template <typename T, std::size_t N>
+inline void swap(SmallVector<T, N>& lhs, SmallVector<T, N>& rhs) {
+ lhs.swap(rhs);
+}
+
+} // namespace android::ftl
diff --git a/include/ftl/static_vector.h b/include/ftl/static_vector.h
new file mode 100644
index 0000000..96a1ae8
--- /dev/null
+++ b/include/ftl/static_vector.h
@@ -0,0 +1,394 @@
+/*
+ * Copyright 2020 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 <ftl/array_traits.h>
+#include <ftl/initializer_list.h>
+
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+constexpr struct IteratorRangeTag {
+} kIteratorRange;
+
+// Fixed-capacity, statically allocated counterpart of std::vector. Like std::array, StaticVector
+// allocates contiguous storage for N elements of type T at compile time, but stores at most (rather
+// than exactly) N elements. Unlike std::array, its default constructor does not require T to have a
+// default constructor, since elements are constructed in place as the vector grows. Operations that
+// insert an element (emplace_back, push_back, etc.) fail when the vector is full. The API otherwise
+// adheres to standard containers, except the unstable_erase operation that does not preserve order,
+// and the replace operation that destructively emplaces.
+//
+// StaticVector<T, 1> is analogous to an iterable std::optional.
+// StaticVector<T, 0> is an error.
+//
+// Example usage:
+//
+// ftl::StaticVector<char, 3> vector;
+// assert(vector.empty());
+//
+// vector = {'a', 'b'};
+// assert(vector.size() == 2u);
+//
+// vector.push_back('c');
+// assert(vector.full());
+//
+// assert(!vector.push_back('d'));
+// assert(vector.size() == 3u);
+//
+// vector.unstable_erase(vector.begin());
+// assert(vector == (ftl::StaticVector{'c', 'b'}));
+//
+// vector.pop_back();
+// assert(vector.back() == 'c');
+//
+// const char array[] = "hi";
+// vector = ftl::StaticVector(array);
+// assert(vector == (ftl::StaticVector{'h', 'i', '\0'}));
+//
+// ftl::StaticVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+// assert(strings.size() == 3u);
+// assert(strings[0] == "abc");
+// assert(strings[1] == "123");
+// assert(strings[2] == "???");
+//
+template <typename T, std::size_t N>
+class StaticVector final : ArrayTraits<T>,
+ ArrayIterators<StaticVector<T, N>, T>,
+ ArrayComparators<StaticVector> {
+ static_assert(N > 0);
+
+ using ArrayTraits<T>::construct_at;
+
+ using Iter = ArrayIterators<StaticVector, T>;
+ friend Iter;
+
+ // There is ambiguity when constructing from two iterator-like elements like pointers:
+ // they could be an iterator range, or arguments for in-place construction. Assume the
+ // latter unless they are input iterators and cannot be used to construct elements. If
+ // the former is intended, the caller can pass an IteratorRangeTag to disambiguate.
+ template <typename I, typename Traits = std::iterator_traits<I>>
+ using is_input_iterator =
+ std::conjunction<std::is_base_of<std::input_iterator_tag, typename Traits::iterator_category>,
+ std::negation<std::is_constructible<T, I>>>;
+
+ public:
+ FTL_ARRAY_TRAIT(T, value_type);
+ FTL_ARRAY_TRAIT(T, size_type);
+ FTL_ARRAY_TRAIT(T, difference_type);
+
+ FTL_ARRAY_TRAIT(T, pointer);
+ FTL_ARRAY_TRAIT(T, reference);
+ FTL_ARRAY_TRAIT(T, iterator);
+ FTL_ARRAY_TRAIT(T, reverse_iterator);
+
+ FTL_ARRAY_TRAIT(T, const_pointer);
+ FTL_ARRAY_TRAIT(T, const_reference);
+ FTL_ARRAY_TRAIT(T, const_iterator);
+ FTL_ARRAY_TRAIT(T, const_reverse_iterator);
+
+ // Creates an empty vector.
+ StaticVector() = default;
+
+ // Copies and moves a vector, respectively.
+ StaticVector(const StaticVector& other)
+ : StaticVector(kIteratorRange, other.begin(), other.end()) {}
+
+ StaticVector(StaticVector&& other) { swap<true>(other); }
+
+ // Copies at most N elements from a smaller convertible vector.
+ template <typename U, std::size_t M, typename = std::enable_if_t<M <= N>>
+ StaticVector(const StaticVector<U, M>& other)
+ : StaticVector(kIteratorRange, other.begin(), other.end()) {}
+
+ // Copies at most N elements from an array.
+ template <typename U, std::size_t M>
+ explicit StaticVector(U (&array)[M])
+ : StaticVector(kIteratorRange, std::begin(array), std::end(array)) {}
+
+ // Copies at most N elements from the range [first, last).
+ //
+ // IteratorRangeTag disambiguates with initialization from two iterator-like elements.
+ //
+ template <typename Iterator, typename = std::enable_if_t<is_input_iterator<Iterator>{}>>
+ StaticVector(Iterator first, Iterator last) : StaticVector(kIteratorRange, first, last) {
+ using V = typename std::iterator_traits<Iterator>::value_type;
+ static_assert(std::is_constructible_v<value_type, V>, "Incompatible iterator range");
+ }
+
+ template <typename Iterator>
+ StaticVector(IteratorRangeTag, Iterator first, Iterator last)
+ : size_(std::min(max_size(), static_cast<size_type>(std::distance(first, last)))) {
+ std::uninitialized_copy(first, first + size_, begin());
+ }
+
+ // Constructs at most N elements. The template arguments T and N are inferred using the
+ // deduction guide defined below. Note that T is determined from the first element, and
+ // subsequent elements must have convertible types:
+ //
+ // ftl::StaticVector vector = {1, 2, 3};
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<int, 3>>);
+ //
+ // const auto copy = "quince"s;
+ // auto move = "tart"s;
+ // ftl::StaticVector vector = {copy, std::move(move)};
+ //
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 2>>);
+ //
+ template <typename E, typename... Es,
+ typename = std::enable_if_t<std::is_constructible_v<value_type, E>>>
+ StaticVector(E&& element, Es&&... elements)
+ : StaticVector(std::index_sequence<0>{}, std::forward<E>(element),
+ std::forward<Es>(elements)...) {
+ static_assert(sizeof...(elements) < N, "Too many elements");
+ }
+
+ // Constructs at most N elements in place by forwarding per-element constructor arguments. The
+ // template arguments T and N are inferred using the deduction guide defined below. The syntax
+ // for listing arguments is as follows:
+ //
+ // ftl::StaticVector vector = ftl::init::list<std::string>("abc")()(3u, '?');
+ //
+ // static_assert(std::is_same_v<decltype(vector), ftl::StaticVector<std::string, 3>>);
+ // assert(vector.full());
+ // assert(vector[0] == "abc");
+ // assert(vector[1].empty());
+ // assert(vector[2] == "???");
+ //
+ template <typename U, std::size_t Size, std::size_t... Sizes, typename... Types>
+ StaticVector(InitializerList<U, std::index_sequence<Size, Sizes...>, Types...>&& list)
+ : StaticVector(std::index_sequence<0, 0, Size>{}, std::make_index_sequence<Size>{},
+ std::index_sequence<Sizes...>{}, list.tuple) {}
+
+ ~StaticVector() { std::destroy(begin(), end()); }
+
+ StaticVector& operator=(const StaticVector& other) {
+ StaticVector copy(other);
+ swap(copy);
+ return *this;
+ }
+
+ StaticVector& operator=(StaticVector&& other) {
+ std::destroy(begin(), end());
+ size_ = 0;
+ swap<true>(other);
+ return *this;
+ }
+
+ // IsEmpty enables a fast path when the vector is known to be empty at compile time.
+ template <bool IsEmpty = false>
+ void swap(StaticVector&);
+
+ static constexpr size_type max_size() { return N; }
+ size_type size() const { return size_; }
+
+ bool empty() const { return size() == 0; }
+ bool full() const { return size() == max_size(); }
+
+ iterator begin() { return std::launder(reinterpret_cast<pointer>(data_)); }
+ iterator end() { return begin() + size(); }
+
+ using Iter::begin;
+ using Iter::end;
+
+ using Iter::cbegin;
+ using Iter::cend;
+
+ using Iter::rbegin;
+ using Iter::rend;
+
+ using Iter::crbegin;
+ using Iter::crend;
+
+ using Iter::last;
+
+ using Iter::back;
+ using Iter::front;
+
+ using Iter::operator[];
+
+ // Replaces an element, and returns a reference to it. The iterator must be dereferenceable, so
+ // replacing at end() is erroneous.
+ //
+ // The element is emplaced via move constructor, so type T does not need to define copy/move
+ // assignment, e.g. its data members may be const.
+ //
+ // The arguments may directly or indirectly refer to the element being replaced.
+ //
+ // Iterators to the replaced element point to its replacement, and others remain valid.
+ //
+ template <typename... Args>
+ reference replace(const_iterator it, Args&&... args) {
+ value_type element{std::forward<Args>(args)...};
+ std::destroy_at(it);
+ // This is only safe because exceptions are disabled.
+ return *construct_at(it, std::move(element));
+ }
+
+ // Appends an element, and returns an iterator to it. If the vector is full, the element is not
+ // inserted, and the end() iterator is returned.
+ //
+ // On success, the end() iterator is invalidated.
+ //
+ template <typename... Args>
+ iterator emplace_back(Args&&... args) {
+ if (full()) return end();
+ const iterator it = construct_at(end(), std::forward<Args>(args)...);
+ ++size_;
+ return it;
+ }
+
+ // Appends an element unless the vector is full, and returns whether the element was inserted.
+ //
+ // On success, the end() iterator is invalidated.
+ //
+ bool push_back(const value_type& v) {
+ // Two statements for sequence point.
+ const iterator it = emplace_back(v);
+ return it != end();
+ }
+
+ bool push_back(value_type&& v) {
+ // Two statements for sequence point.
+ const iterator it = emplace_back(std::move(v));
+ return it != end();
+ }
+
+ // Removes the last element. The vector must not be empty, or the call is erroneous.
+ //
+ // The last() and end() iterators are invalidated.
+ //
+ void pop_back() { unstable_erase(last()); }
+
+ // Erases an element, but does not preserve order. Rather than shifting subsequent elements,
+ // this moves the last element to the slot of the erased element.
+ //
+ // The last() and end() iterators, as well as those to the erased element, are invalidated.
+ //
+ void unstable_erase(const_iterator it) {
+ std::destroy_at(it);
+ if (it != last()) {
+ // Move last element and destroy its source for destructor side effects. This is only
+ // safe because exceptions are disabled.
+ construct_at(it, std::move(back()));
+ std::destroy_at(last());
+ }
+ --size_;
+ }
+
+ private:
+ // Recursion for variadic constructor.
+ template <std::size_t I, typename E, typename... Es>
+ StaticVector(std::index_sequence<I>, E&& element, Es&&... elements)
+ : StaticVector(std::index_sequence<I + 1>{}, std::forward<Es>(elements)...) {
+ construct_at(begin() + I, std::forward<E>(element));
+ }
+
+ // Base case for variadic constructor.
+ template <std::size_t I>
+ explicit StaticVector(std::index_sequence<I>) : size_(I) {}
+
+ // Recursion for in-place constructor.
+ //
+ // Construct element I by extracting its arguments from the InitializerList tuple. ArgIndex
+ // is the position of its first argument in Args, and ArgCount is the number of arguments.
+ // The Indices sequence corresponds to [0, ArgCount).
+ //
+ // The Sizes sequence lists the argument counts for elements after I, so Size is the ArgCount
+ // for the next element. The recursion stops when Sizes is empty for the last element.
+ //
+ template <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
+ std::size_t Size, std::size_t... Sizes, typename... Args>
+ StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
+ std::index_sequence<Size, Sizes...>, std::tuple<Args...>& tuple)
+ : StaticVector(std::index_sequence<I + 1, ArgIndex + ArgCount, Size>{},
+ std::make_index_sequence<Size>{}, std::index_sequence<Sizes...>{}, tuple) {
+ construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
+ }
+
+ // Base case for in-place constructor.
+ template <std::size_t I, std::size_t ArgIndex, std::size_t ArgCount, std::size_t... Indices,
+ typename... Args>
+ StaticVector(std::index_sequence<I, ArgIndex, ArgCount>, std::index_sequence<Indices...>,
+ std::index_sequence<>, std::tuple<Args...>& tuple)
+ : size_(I + 1) {
+ construct_at(begin() + I, std::move(std::get<ArgIndex + Indices>(tuple))...);
+ }
+
+ size_type size_ = 0;
+ std::aligned_storage_t<sizeof(value_type), alignof(value_type)> data_[N];
+};
+
+// Deduction guide for array constructor.
+template <typename T, std::size_t N>
+StaticVector(T (&)[N]) -> StaticVector<std::remove_cv_t<T>, N>;
+
+// Deduction guide for variadic constructor.
+template <typename T, typename... Us, typename V = std::decay_t<T>,
+ typename = std::enable_if_t<(std::is_constructible_v<V, Us> && ...)>>
+StaticVector(T&&, Us&&...) -> StaticVector<V, 1 + sizeof...(Us)>;
+
+// Deduction guide for in-place constructor.
+template <typename T, std::size_t... Sizes, typename... Types>
+StaticVector(InitializerList<T, std::index_sequence<Sizes...>, Types...>&&)
+ -> StaticVector<T, sizeof...(Sizes)>;
+
+template <typename T, std::size_t N>
+template <bool IsEmpty>
+void StaticVector<T, N>::swap(StaticVector& other) {
+ auto [to, from] = std::make_pair(this, &other);
+ if (from == this) return;
+
+ // Assume this vector has fewer elements, so the excess of the other vector will be moved to it.
+ auto [min, max] = std::make_pair(size(), other.size());
+
+ // No elements to swap if moving into an empty vector.
+ if constexpr (IsEmpty) {
+ assert(min == 0);
+ } else {
+ if (min > max) {
+ std::swap(from, to);
+ std::swap(min, max);
+ }
+
+ // Swap elements [0, min).
+ std::swap_ranges(begin(), begin() + min, other.begin());
+
+ // No elements to move if sizes are equal.
+ if (min == max) return;
+ }
+
+ // Move elements [min, max) and destroy their source for destructor side effects.
+ const auto [first, last] = std::make_pair(from->begin() + min, from->begin() + max);
+ std::uninitialized_move(first, last, to->begin() + min);
+ std::destroy(first, last);
+
+ std::swap(size_, other.size_);
+}
+
+template <typename T, std::size_t N>
+inline void swap(StaticVector<T, N>& lhs, StaticVector<T, N>& rhs) {
+ lhs.swap(rhs);
+}
+
+} // namespace android::ftl
diff --git a/libs/binder/Parcel.cpp b/libs/binder/Parcel.cpp
index 91e465f..b90cc27 100644
--- a/libs/binder/Parcel.cpp
+++ b/libs/binder/Parcel.cpp
@@ -206,7 +206,7 @@
if (proxy == nullptr) {
ALOGE("null proxy");
}
- const int32_t handle = proxy ? proxy->handle() : 0;
+ const int32_t handle = proxy ? proxy->getPrivateAccessorForHandle().handle() : 0;
obj.hdr.type = BINDER_TYPE_HANDLE;
obj.binder = 0; /* Don't pass uninitialized stack data to a remote process */
obj.handle = handle;
diff --git a/libs/binder/ProcessState.cpp b/libs/binder/ProcessState.cpp
index 9aedf28..6f26450 100644
--- a/libs/binder/ProcessState.cpp
+++ b/libs/binder/ProcessState.cpp
@@ -204,11 +204,11 @@
// that the handle points to. Can only be used by the servicemanager.
//
// Returns -1 in case of failure, otherwise the strong reference count.
-ssize_t ProcessState::getStrongRefCountForNodeByHandle(int32_t handle) {
+ssize_t ProcessState::getStrongRefCountForNode(const sp<BpBinder>& binder) {
binder_node_info_for_ref info;
memset(&info, 0, sizeof(binder_node_info_for_ref));
- info.handle = handle;
+ info.handle = binder->getPrivateAccessorForHandle().handle();
status_t result = ioctl(mDriverFD, BINDER_GET_NODE_INFO_FOR_REF, &info);
diff --git a/libs/binder/include/binder/BpBinder.h b/libs/binder/include/binder/BpBinder.h
index 2735315..22300ac 100644
--- a/libs/binder/include/binder/BpBinder.h
+++ b/libs/binder/include/binder/BpBinder.h
@@ -29,6 +29,7 @@
namespace internal {
class Stability;
}
+class ProcessState;
using binder_proxy_limit_callback = void(*)(int);
@@ -37,8 +38,6 @@
public:
static BpBinder* create(int32_t handle);
- int32_t handle() const;
-
virtual const String16& getInterfaceDescriptor() const;
virtual bool isBinderAlive() const;
virtual status_t pingBinder();
@@ -109,7 +108,23 @@
KeyedVector<const void*, entry_t> mObjects;
};
+ class PrivateAccessorForHandle {
+ private:
+ friend BpBinder;
+ friend ::android::Parcel;
+ friend ::android::ProcessState;
+ explicit PrivateAccessorForHandle(const BpBinder* binder) : mBinder(binder) {}
+ int32_t handle() const { return mBinder->handle(); }
+ const BpBinder* mBinder;
+ };
+ const PrivateAccessorForHandle getPrivateAccessorForHandle() const {
+ return PrivateAccessorForHandle(this);
+ }
+
private:
+ friend PrivateAccessorForHandle;
+
+ int32_t handle() const;
BpBinder(int32_t handle,int32_t trackedUid);
virtual ~BpBinder();
virtual void onFirstRef();
diff --git a/libs/binder/include/binder/Parcel.h b/libs/binder/include/binder/Parcel.h
index 9f5260a..b49951b 100644
--- a/libs/binder/include/binder/Parcel.h
+++ b/libs/binder/include/binder/Parcel.h
@@ -504,9 +504,6 @@
const binder_size_t* objects, size_t objectsCount,
release_func relFunc);
- Parcel(const Parcel& o);
- Parcel& operator=(const Parcel& o);
-
status_t finishWrite(size_t len);
void releaseObjects();
void acquireObjects();
diff --git a/libs/binder/include/binder/ProcessState.h b/libs/binder/include/binder/ProcessState.h
index 46457cd..bab6469 100644
--- a/libs/binder/include/binder/ProcessState.h
+++ b/libs/binder/include/binder/ProcessState.h
@@ -70,7 +70,7 @@
// 2. Temporary strong references held by the kernel during a
// transaction on the node.
// It does NOT include local strong references to the node
- ssize_t getStrongRefCountForNodeByHandle(int32_t handle);
+ ssize_t getStrongRefCountForNode(const sp<BpBinder>& binder);
enum class CallRestriction {
// all calls okay
diff --git a/libs/binder/rust/src/proxy.rs b/libs/binder/rust/src/proxy.rs
index 9d612a4..17af099 100644
--- a/libs/binder/rust/src/proxy.rs
+++ b/libs/binder/rust/src/proxy.rs
@@ -416,6 +416,16 @@
}
}
+impl Drop for WpIBinder {
+ fn drop(&mut self) {
+ unsafe {
+ // Safety: WpIBinder always holds a valid `AIBinder_Weak` pointer, so we
+ // know this pointer is safe to pass to `AIBinder_Weak_delete` here.
+ sys::AIBinder_Weak_delete(self.0);
+ }
+ }
+}
+
/// Rust wrapper around DeathRecipient objects.
#[repr(C)]
pub struct DeathRecipient {
diff --git a/libs/binder/tests/fuzzers/BpBinderFuzzFunctions.h b/libs/binder/tests/fuzzers/BpBinderFuzzFunctions.h
index c685b41..6ca0e2f 100644
--- a/libs/binder/tests/fuzzers/BpBinderFuzzFunctions.h
+++ b/libs/binder/tests/fuzzers/BpBinderFuzzFunctions.h
@@ -48,9 +48,7 @@
static const std::vector<std::function<void(FuzzedDataProvider*, const sp<BpBinder>&,
const sp<IBinder::DeathRecipient>&)>>
gBPBinderOperations =
- {[](FuzzedDataProvider*, const sp<BpBinder>& bpbinder,
- const sp<IBinder::DeathRecipient>&) -> void { bpbinder->handle(); },
- [](FuzzedDataProvider* fdp, const sp<BpBinder>& bpbinder,
+ {[](FuzzedDataProvider* fdp, const sp<BpBinder>& bpbinder,
const sp<IBinder::DeathRecipient>& s_recipient) -> void {
// Clean up possible leftover memory.
wp<IBinder::DeathRecipient> outRecipient(nullptr);
diff --git a/libs/ftl/.clang-format b/libs/ftl/.clang-format
new file mode 120000
index 0000000..86b1593
--- /dev/null
+++ b/libs/ftl/.clang-format
@@ -0,0 +1 @@
+../../../../build/soong/scripts/system-clang-format-2
\ No newline at end of file
diff --git a/libs/ftl/Android.bp b/libs/ftl/Android.bp
index eb8e57a..5bccaca 100644
--- a/libs/ftl/Android.bp
+++ b/libs/ftl/Android.bp
@@ -5,9 +5,10 @@
address: true,
},
srcs: [
- "SmallMap_test.cpp",
- "SmallVector_test.cpp",
- "StaticVector_test.cpp",
+ "future_test.cpp",
+ "small_map_test.cpp",
+ "small_vector_test.cpp",
+ "static_vector_test.cpp",
],
cflags: [
"-Wall",
diff --git a/libs/ftl/README.md b/libs/ftl/README.md
new file mode 100644
index 0000000..bdd750f
--- /dev/null
+++ b/libs/ftl/README.md
@@ -0,0 +1,41 @@
+# FTL
+
+FTL is a template library shared by SurfaceFlinger and InputFlinger, inspired by
+and supplementing the C++ Standard Library. The intent is to fill gaps for areas
+not (yet) covered—like cache-efficient data structures and lock-free concurrency
+primitives—and implement proposals that are missing or experimental in Android's
+libc++ branch. The design takes some liberties with standard compliance, notably
+assuming that exceptions are disabled.
+
+## Tests
+
+ atest ftl_test
+
+## Style
+
+- Based on [Google C++ Style](https://google.github.io/styleguide/cppguide.html).
+- Informed by [C++ Core Guidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines).
+
+Naming conventions are as follows:
+
+- `PascalCase`
+ - Types and aliases, except standard interfaces.
+ - Template parameters, including non-type ones.
+- `snake_case`
+ - Variables, and data members with trailing underscore.
+ - Functions, free and member alike.
+ - Type traits, with standard `_t` and `_v` suffixes.
+- `kCamelCase`
+ - Enumerators and `constexpr` constants with static storage duration.
+- `MACRO_CASE`
+ - Macros, with `FTL_` prefix unless `#undef`ed.
+
+Template parameter packs are named with the following convention:
+
+ typename T, typename... Ts
+ typename Arg, typename... Args
+
+ std::size_t I, std::size_t... Is
+ std::size_t Size, std::size_t... Sizes
+
+The `details` namespace contains implementation details.
diff --git a/libs/ftl/SmallMap_test.cpp b/libs/ftl/SmallMap_test.cpp
deleted file mode 100644
index fa00c06..0000000
--- a/libs/ftl/SmallMap_test.cpp
+++ /dev/null
@@ -1,131 +0,0 @@
-/*
- * Copyright 2020 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.
- */
-
-#include <ftl/SmallMap.h>
-#include <gtest/gtest.h>
-
-#include <cctype>
-
-namespace android::test {
-
-using ftl::SmallMap;
-
-// Keep in sync with example usage in header file.
-TEST(SmallMap, Example) {
- ftl::SmallMap<int, std::string, 3> map;
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.dynamic());
-
- map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
- EXPECT_EQ(map.size(), 3u);
- EXPECT_FALSE(map.dynamic());
-
- EXPECT_TRUE(map.contains(123));
-
- EXPECT_EQ(map.find(42, [](const std::string& s) { return s.size(); }), 3u);
-
- const auto opt = map.find(-1);
- ASSERT_TRUE(opt);
-
- std::string& ref = *opt;
- EXPECT_TRUE(ref.empty());
- ref = "xyz";
-
- EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
-}
-
-TEST(SmallMap, Construct) {
- {
- // Default constructor.
- SmallMap<int, std::string, 2> map;
-
- EXPECT_TRUE(map.empty());
- EXPECT_FALSE(map.dynamic());
- }
- {
- // In-place constructor with same types.
- SmallMap<int, std::string, 5> map =
- ftl::init::map<int, std::string>(123, "abc")(456, "def")(789, "ghi");
-
- EXPECT_EQ(map.size(), 3u);
- EXPECT_EQ(map.max_size(), 5u);
- EXPECT_FALSE(map.dynamic());
-
- EXPECT_EQ(map, SmallMap(ftl::init::map(123, "abc")(456, "def")(789, "ghi")));
- }
- {
- // In-place constructor with different types.
- SmallMap<int, std::string, 5> map =
- ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
-
- EXPECT_EQ(map.size(), 3u);
- EXPECT_EQ(map.max_size(), 5u);
- EXPECT_FALSE(map.dynamic());
-
- EXPECT_EQ(map, SmallMap(ftl::init::map(42, "???")(123, "abc")(-1, "\0\0\0")));
- }
- {
- // In-place constructor with implicit size.
- SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
-
- static_assert(std::is_same_v<decltype(map), SmallMap<int, std::string, 3>>);
- EXPECT_EQ(map.size(), 3u);
- EXPECT_EQ(map.max_size(), 3u);
- EXPECT_FALSE(map.dynamic());
-
- EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "\0\0\0")(42, "???")(123, "abc")));
- }
-}
-
-TEST(SmallMap, Find) {
- {
- // Constant reference.
- const ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
-
- const auto opt = map.find('b');
- EXPECT_EQ(opt, 'B');
-
- const char d = 'D';
- const auto ref = map.find('d').value_or(std::cref(d));
- EXPECT_EQ(ref.get(), 'D');
- }
- {
- // Mutable reference.
- ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
-
- const auto opt = map.find('c');
- EXPECT_EQ(opt, 'C');
-
- char d = 'd';
- const auto ref = map.find('d').value_or(std::ref(d));
- ref.get() = 'D';
- EXPECT_EQ(d, 'D');
- }
- {
- // Constant unary operation.
- const ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
- EXPECT_EQ(map.find('c', [](char c) { return std::toupper(c); }), 'Z');
- }
- {
- // Mutable unary operation.
- ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
- EXPECT_TRUE(map.find('c', [](char& c) { c = std::toupper(c); }));
-
- EXPECT_EQ(map, SmallMap(ftl::init::map('c', 'Z')('b', 'y')('a', 'x')));
- }
-}
-
-} // namespace android::test
diff --git a/libs/ftl/SmallVector_test.cpp b/libs/ftl/SmallVector_test.cpp
deleted file mode 100644
index d0c2858..0000000
--- a/libs/ftl/SmallVector_test.cpp
+++ /dev/null
@@ -1,465 +0,0 @@
-/*
- * Copyright 2020 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.
- */
-
-#include <ftl/SmallVector.h>
-#include <gtest/gtest.h>
-
-#include <algorithm>
-#include <iterator>
-#include <string>
-#include <utility>
-
-using namespace std::string_literals;
-
-namespace android::test {
-
-using ftl::SmallVector;
-
-// Keep in sync with example usage in header file.
-TEST(SmallVector, Example) {
- ftl::SmallVector<char, 3> vector;
- EXPECT_TRUE(vector.empty());
- EXPECT_FALSE(vector.dynamic());
-
- vector = {'a', 'b', 'c'};
- EXPECT_EQ(vector.size(), 3u);
- EXPECT_FALSE(vector.dynamic());
-
- vector.push_back('d');
- EXPECT_TRUE(vector.dynamic());
-
- vector.unstable_erase(vector.begin());
- EXPECT_EQ(vector, (ftl::SmallVector{'d', 'b', 'c'}));
-
- vector.pop_back();
- EXPECT_EQ(vector.back(), 'b');
- EXPECT_TRUE(vector.dynamic());
-
- const char array[] = "hi";
- vector = ftl::SmallVector(array);
- EXPECT_EQ(vector, (ftl::SmallVector{'h', 'i', '\0'}));
- EXPECT_FALSE(vector.dynamic());
-
- ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
- ASSERT_EQ(strings.size(), 3u);
- EXPECT_FALSE(strings.dynamic());
-
- EXPECT_EQ(strings[0], "abc");
- EXPECT_EQ(strings[1], "123");
- EXPECT_EQ(strings[2], "???");
-}
-
-TEST(SmallVector, Construct) {
- {
- // Default constructor.
- SmallVector<std::string, 2> vector;
-
- EXPECT_TRUE(vector.empty());
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // Array constructor.
- const float kFloats[] = {.1f, .2f, .3f};
- SmallVector vector(kFloats);
-
- EXPECT_EQ(vector, (SmallVector{.1f, .2f, .3f}));
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // Iterator constructor.
- const char chars[] = "abcdef";
- std::string string(chars);
- SmallVector<char, sizeof(chars)> vector(string.begin(), string.end());
-
- EXPECT_STREQ(vector.begin(), chars);
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // Variadic constructor with same types.
- SmallVector vector = {1, 2, 3};
-
- static_assert(std::is_same_v<decltype(vector), SmallVector<int, 3>>);
- EXPECT_EQ(vector, (SmallVector{1, 2, 3}));
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // Variadic constructor with different types.
- const auto copy = "quince"s;
- auto move = "tart"s;
- SmallVector vector = {copy, std::move(move)};
-
- static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 2>>);
- EXPECT_EQ(vector, (SmallVector{"quince"s, "tart"s}));
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // In-place constructor with same types.
- SmallVector vector =
- ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
-
- static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
- EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // In-place constructor with different types.
- const auto copy = "red"s;
- auto move = "velvet"s;
- std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
- SmallVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
-
- static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
- EXPECT_TRUE(move.empty());
- EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
- EXPECT_FALSE(vector.dynamic());
- }
- {
- // Conversion from StaticVector.
- ftl::StaticVector doubles = {.1, .2, .3};
- SmallVector vector = std::move(doubles);
- EXPECT_TRUE(doubles.empty());
-
- static_assert(std::is_same_v<decltype(vector), SmallVector<double, 3>>);
- EXPECT_EQ(vector, (SmallVector{.1, .2, .3}));
- EXPECT_FALSE(vector.dynamic());
- }
-}
-
-TEST(SmallVector, String) {
- SmallVector<char, 10> chars;
- char c = 'a';
- std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
- chars.push_back('\0');
-
- EXPECT_TRUE(chars.dynamic());
- EXPECT_EQ(chars.size(), 11u);
- EXPECT_STREQ(chars.begin(), "abcdefghij");
-
- // Constructor takes iterator range.
- const char kString[] = "123456";
- SmallVector<char, 10> string(std::begin(kString), std::end(kString));
-
- EXPECT_FALSE(string.dynamic());
- EXPECT_STREQ(string.begin(), "123456");
- EXPECT_EQ(string.size(), 7u);
-
- // Similar to emplace, but replaces rather than inserts.
- string.replace(string.begin() + 5, '\0');
- EXPECT_STREQ(string.begin(), "12345");
-
- swap(chars, string);
-
- EXPECT_STREQ(chars.begin(), "12345");
- EXPECT_STREQ(string.begin(), "abcdefghij");
-
- EXPECT_FALSE(chars.dynamic());
- EXPECT_TRUE(string.dynamic());
-}
-
-TEST(SmallVector, CopyableElement) {
- struct Pair {
- // Needed because std::vector emplace does not use uniform initialization.
- Pair(int a, int b) : a(a), b(b) {}
-
- const int a, b;
- bool operator==(Pair p) const { return p.a == a && p.b == b; }
- };
-
- SmallVector<Pair, 5> pairs;
-
- EXPECT_TRUE(pairs.empty());
- EXPECT_EQ(pairs.max_size(), 5u);
-
- for (size_t i = 0; i < pairs.max_size(); ++i) {
- EXPECT_EQ(pairs.size(), i);
-
- const int a = static_cast<int>(i) * 2;
- EXPECT_EQ(pairs.emplace_back(a, a + 1), Pair(a, a + 1));
- }
-
- EXPECT_EQ(pairs.size(), 5u);
- EXPECT_FALSE(pairs.dynamic());
-
- // The vector is promoted when full.
- EXPECT_EQ(pairs.emplace_back(10, 11), Pair(10, 11));
- EXPECT_TRUE(pairs.dynamic());
-
- EXPECT_EQ(pairs,
- (SmallVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9},
- Pair{10, 11}}));
-
- // Constructor takes at most N elements.
- SmallVector<int, 6> sums = {0, 0, 0, 0, 0, 0};
- EXPECT_FALSE(sums.dynamic());
-
- // Random-access iterators comply with standard.
- std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
- EXPECT_EQ(sums, (SmallVector{1, 5, 9, 13, 17, 21}));
-
- sums.pop_back();
- std::reverse(sums.begin(), sums.end());
-
- EXPECT_EQ(sums, (SmallVector{17, 13, 9, 5, 1}));
-}
-
-TEST(SmallVector, MovableElement) {
- // Construct std::string elements in place from per-element arguments.
- SmallVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
- strings.pop_back();
-
- EXPECT_EQ(strings.max_size(), 7u);
- EXPECT_EQ(strings.size(), 6u);
-
- // Erase "cake" and append a substring copy.
- {
- const auto it = std::find_if(strings.begin(), strings.end(),
- [](const auto& s) { return !s.empty(); });
- ASSERT_FALSE(it == strings.end());
- EXPECT_EQ(*it, "cake");
-
- // Construct std::string from first 4 characters of string literal.
- strings.unstable_erase(it);
- EXPECT_EQ(strings.emplace_back("cakewalk", 4u), "cake"s);
- }
-
- strings[1] = "quince"s;
-
- // Replace last empty string with "tart".
- {
- const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
- ASSERT_FALSE(rit == strings.rend());
-
- std::initializer_list<char> list = {'t', 'a', 'r', 't'};
- strings.replace(rit.base() - 1, list);
- }
-
- strings.front().assign("pie");
-
- EXPECT_EQ(strings, (SmallVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
-
- strings.push_back("nougat");
- strings.push_back("oreo");
- EXPECT_TRUE(strings.dynamic());
-
- std::rotate(strings.begin(), strings.end() - 2, strings.end());
-
- EXPECT_EQ(strings,
- (SmallVector{"nougat"s, "oreo"s, "pie"s, "quince"s, "tart"s, "red"s, "velvet"s,
- "cake"s}));
-}
-
-TEST(SmallVector, Replace) {
- // Replacing does not require a copy/move assignment operator.
- struct Word {
- explicit Word(std::string str) : str(std::move(str)) {}
- const std::string str;
-
- bool operator==(const Word& other) const { return other.str == str; }
- };
-
- SmallVector words = ftl::init::list<Word>("colored")("velour");
-
- // The replaced element can be referenced by the replacement.
- {
- const Word& word = words.replace(words.last(), words.back().str.substr(0, 3) + "vet");
- EXPECT_EQ(word, Word("velvet"));
- }
-
- // The vector is not promoted if replacing while full.
- EXPECT_FALSE(words.dynamic());
-
- words.emplace_back("cake");
- EXPECT_TRUE(words.dynamic());
-
- {
- const Word& word = words.replace(words.begin(), words.front().str.substr(4));
- EXPECT_EQ(word, Word("red"));
- }
-
- EXPECT_EQ(words, (SmallVector{Word("red"), Word("velvet"), Word("cake")}));
-}
-
-TEST(SmallVector, ReverseAppend) {
- SmallVector strings = {"red"s, "velvet"s, "cake"s};
- EXPECT_FALSE(strings.dynamic());
-
- auto rit = strings.rbegin();
- while (rit != strings.rend()) {
- // Iterator and reference are invalidated on insertion.
- const auto i = std::distance(strings.begin(), rit.base());
- std::string s = *rit;
-
- strings.push_back(std::move(s));
- rit = std::make_reverse_iterator(strings.begin() + i) + 1;
- }
-
- EXPECT_EQ(strings, (SmallVector{"red"s, "velvet"s, "cake"s, "cake"s, "velvet"s, "red"s}));
- EXPECT_TRUE(strings.dynamic());
-}
-
-TEST(SmallVector, Sort) {
- SmallVector strings = ftl::init::list<std::string>("pie")("quince")("tart")("red")("velvet");
- strings.push_back("cake"s);
-
- auto sorted = std::move(strings);
- EXPECT_TRUE(strings.empty());
-
- EXPECT_TRUE(sorted.dynamic());
- EXPECT_TRUE(strings.dynamic());
-
- std::sort(sorted.begin(), sorted.end());
- EXPECT_EQ(sorted, (SmallVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
-
- // Constructor takes array reference.
- {
- const char* kStrings[] = {"cake", "lie"};
- strings = SmallVector(kStrings);
- EXPECT_FALSE(strings.dynamic());
- }
-
- EXPECT_GT(sorted, strings);
- swap(sorted, strings);
- EXPECT_LT(sorted, strings);
-
- EXPECT_FALSE(sorted.dynamic());
- EXPECT_TRUE(strings.dynamic());
-
- // Append remaining elements, such that "pie" is the only difference.
- for (const char* str : {"quince", "red", "tart", "velvet"}) {
- sorted.emplace_back(str);
- }
- EXPECT_TRUE(sorted.dynamic());
-
- EXPECT_NE(sorted, strings);
-
- // Replace second element with "pie".
- const auto it = sorted.begin() + 1;
- EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie");
-
- EXPECT_EQ(sorted, strings);
-}
-
-namespace {
-
-struct DestroyCounts {
- DestroyCounts(int& live, int& dead) : counts{live, dead} {}
- DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
- DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
- ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
-
- struct {
- int& live;
- int& dead;
- } counts;
-
- bool alive = true;
-};
-
-void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
- std::swap(lhs.alive, rhs.alive);
-}
-
-} // namespace
-
-TEST(SmallVector, Destroy) {
- int live = 0;
- int dead = 0;
-
- { SmallVector<DestroyCounts, 3> counts; }
- EXPECT_EQ(0, live);
- EXPECT_EQ(0, dead);
-
- {
- SmallVector<DestroyCounts, 3> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- EXPECT_FALSE(counts.dynamic());
- }
- EXPECT_EQ(3, live);
- EXPECT_EQ(0, dead);
-
- live = 0;
- {
- SmallVector<DestroyCounts, 3> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- EXPECT_TRUE(counts.dynamic());
- }
- EXPECT_EQ(4, live);
- EXPECT_EQ(3, dead);
-
- live = dead = 0;
- {
- SmallVector<DestroyCounts, 2> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- auto copy = counts;
- EXPECT_TRUE(copy.dynamic());
- }
- EXPECT_EQ(6, live);
- EXPECT_EQ(2, dead);
-
- live = dead = 0;
- {
- SmallVector<DestroyCounts, 2> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- auto move = std::move(counts);
- EXPECT_TRUE(move.dynamic());
- }
- EXPECT_EQ(3, live);
- EXPECT_EQ(2, dead);
-
- live = dead = 0;
- {
- SmallVector<DestroyCounts, 2> counts1;
- counts1.emplace_back(live, dead);
- counts1.emplace_back(live, dead);
- counts1.emplace_back(live, dead);
-
- EXPECT_TRUE(counts1.dynamic());
- EXPECT_EQ(2, dead);
- dead = 0;
-
- SmallVector<DestroyCounts, 2> counts2;
- counts2.emplace_back(live, dead);
-
- EXPECT_FALSE(counts2.dynamic());
-
- swap(counts1, counts2);
-
- EXPECT_FALSE(counts1.dynamic());
- EXPECT_TRUE(counts2.dynamic());
-
- EXPECT_EQ(0, live);
- EXPECT_EQ(1, dead);
-
- dead = 0;
- }
- EXPECT_EQ(4, live);
- EXPECT_EQ(0, dead);
-}
-
-} // namespace android::test
diff --git a/libs/ftl/StaticVector_test.cpp b/libs/ftl/StaticVector_test.cpp
deleted file mode 100644
index db42d23..0000000
--- a/libs/ftl/StaticVector_test.cpp
+++ /dev/null
@@ -1,399 +0,0 @@
-/*
- * Copyright 2020 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.
- */
-
-#include <ftl/StaticVector.h>
-#include <gtest/gtest.h>
-
-#include <algorithm>
-#include <iterator>
-#include <string>
-#include <utility>
-
-using namespace std::string_literals;
-
-namespace android::test {
-
-using ftl::StaticVector;
-
-// Keep in sync with example usage in header file.
-TEST(StaticVector, Example) {
- ftl::StaticVector<char, 3> vector;
- EXPECT_TRUE(vector.empty());
-
- vector = {'a', 'b'};
- EXPECT_EQ(vector.size(), 2u);
-
- vector.push_back('c');
- EXPECT_TRUE(vector.full());
-
- EXPECT_FALSE(vector.push_back('d'));
- EXPECT_EQ(vector.size(), 3u);
-
- vector.unstable_erase(vector.begin());
- EXPECT_EQ(vector, (ftl::StaticVector{'c', 'b'}));
-
- vector.pop_back();
- EXPECT_EQ(vector.back(), 'c');
-
- const char array[] = "hi";
- vector = ftl::StaticVector(array);
- EXPECT_EQ(vector, (ftl::StaticVector{'h', 'i', '\0'}));
-
- ftl::StaticVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
- ASSERT_EQ(strings.size(), 3u);
-
- EXPECT_EQ(strings[0], "abc");
- EXPECT_EQ(strings[1], "123");
- EXPECT_EQ(strings[2], "???");
-}
-
-TEST(StaticVector, Construct) {
- {
- // Default constructor.
- StaticVector<std::string, 2> vector;
- EXPECT_TRUE(vector.empty());
- }
- {
- // Array constructor.
- const float kFloats[] = {.1f, .2f, .3f};
- StaticVector vector(kFloats);
- EXPECT_EQ(vector, (StaticVector{.1f, .2f, .3f}));
- }
- {
- // Iterator constructor.
- const char chars[] = "abcdef";
- std::string string(chars);
- StaticVector<char, sizeof(chars)> vector(string.begin(), string.end());
-
- EXPECT_STREQ(vector.begin(), chars);
- }
- {
- // Variadic constructor with same types.
- StaticVector vector = {1, 2, 3};
-
- static_assert(std::is_same_v<decltype(vector), StaticVector<int, 3>>);
- EXPECT_EQ(vector, (StaticVector{1, 2, 3}));
- }
- {
- // Variadic constructor with different types.
- const auto copy = "quince"s;
- auto move = "tart"s;
- StaticVector vector = {copy, std::move(move)};
-
- static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 2>>);
- EXPECT_EQ(vector, (StaticVector{"quince"s, "tart"s}));
- }
- {
- // In-place constructor with same types.
- StaticVector vector =
- ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
-
- static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
- EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
- }
- {
- // In-place constructor with different types.
- const auto copy = "red"s;
- auto move = "velvet"s;
- std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
- StaticVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
-
- static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
- EXPECT_TRUE(move.empty());
- EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
- }
- {
- struct String {
- explicit String(const char* str) : str(str) {}
- explicit String(const char** ptr) : str(*ptr) {}
- const char* str;
- };
-
- const char* kStrings[] = {"a", "b", "c", "d"};
-
- {
- // Two iterator-like elements.
- StaticVector<String, 3> vector(kStrings, kStrings + 3);
- ASSERT_EQ(vector.size(), 2u);
-
- EXPECT_STREQ(vector[0].str, "a");
- EXPECT_STREQ(vector[1].str, "d");
- }
- {
- // Disambiguating iterator constructor.
- StaticVector<String, 3> vector(ftl::IteratorRange, kStrings, kStrings + 3);
- ASSERT_EQ(vector.size(), 3u);
-
- EXPECT_STREQ(vector[0].str, "a");
- EXPECT_STREQ(vector[1].str, "b");
- EXPECT_STREQ(vector[2].str, "c");
- }
- }
-}
-
-TEST(StaticVector, String) {
- StaticVector<char, 10> chars;
- char c = 'a';
- std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
- chars.back() = '\0';
-
- EXPECT_STREQ(chars.begin(), "abcdefghi");
-
- // Constructor takes iterator range.
- const char kString[] = "123456";
- StaticVector<char, 10> string(std::begin(kString), std::end(kString));
-
- EXPECT_STREQ(string.begin(), "123456");
- EXPECT_EQ(string.size(), 7u);
-
- // Similar to emplace, but replaces rather than inserts.
- string.replace(string.begin() + 5, '\0');
- EXPECT_STREQ(string.begin(), "12345");
-
- swap(chars, string);
-
- EXPECT_STREQ(chars.begin(), "12345");
- EXPECT_STREQ(string.begin(), "abcdefghi");
-}
-
-TEST(StaticVector, CopyableElement) {
- struct Pair {
- const int a, b;
- bool operator==(Pair p) const { return p.a == a && p.b == b; }
- };
-
- StaticVector<Pair, 5> pairs;
-
- EXPECT_TRUE(pairs.empty());
- EXPECT_EQ(pairs.max_size(), 5u);
-
- for (size_t i = 0; i < pairs.max_size(); ++i) {
- EXPECT_EQ(pairs.size(), i);
-
- const int a = static_cast<int>(i) * 2;
- const auto it = pairs.emplace_back(a, a + 1);
- ASSERT_NE(it, pairs.end());
- EXPECT_EQ(*it, (Pair{a, a + 1}));
- }
-
- EXPECT_TRUE(pairs.full());
- EXPECT_EQ(pairs.size(), 5u);
-
- // Insertion fails if the vector is full.
- const auto it = pairs.emplace_back(10, 11);
- EXPECT_EQ(it, pairs.end());
-
- EXPECT_EQ(pairs, (StaticVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9}}));
-
- // Constructor takes at most N elements.
- StaticVector<int, 6> sums = {0, 0, 0, 0, 0, -1};
- EXPECT_TRUE(sums.full());
-
- // Random-access iterators comply with standard.
- std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
- EXPECT_EQ(sums, (StaticVector{1, 5, 9, 13, 17, -1}));
-
- sums.pop_back();
- std::reverse(sums.begin(), sums.end());
-
- EXPECT_EQ(sums, (StaticVector{17, 13, 9, 5, 1}));
-}
-
-TEST(StaticVector, MovableElement) {
- // Construct std::string elements in place from per-element arguments.
- StaticVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
- strings.pop_back();
-
- EXPECT_EQ(strings.max_size(), 7u);
- EXPECT_EQ(strings.size(), 6u);
-
- // Erase "cake" and append a substring copy.
- {
- auto it = std::find_if(strings.begin(), strings.end(),
- [](const auto& s) { return !s.empty(); });
- ASSERT_FALSE(it == strings.end());
- EXPECT_EQ(*it, "cake");
-
- strings.unstable_erase(it);
-
- // Construct std::string from first 4 characters of string literal.
- it = strings.emplace_back("cakewalk", 4u);
- ASSERT_NE(it, strings.end());
- EXPECT_EQ(*it, "cake"s);
- }
-
- strings[1] = "quince"s;
-
- // Replace last empty string with "tart".
- {
- const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
- ASSERT_FALSE(rit == strings.rend());
-
- std::initializer_list<char> list = {'t', 'a', 'r', 't'};
- strings.replace(rit.base() - 1, list);
- }
-
- strings.front().assign("pie");
-
- EXPECT_EQ(strings, (StaticVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
-}
-
-TEST(StaticVector, Replace) {
- // Replacing does not require a copy/move assignment operator.
- struct Word {
- explicit Word(std::string str) : str(std::move(str)) {}
- const std::string str;
- };
-
- StaticVector words = ftl::init::list<Word>("red")("velour")("cake");
-
- // The replaced element can be referenced by the replacement.
- const auto it = words.begin() + 1;
- const Word& word = words.replace(it, it->str.substr(0, 3) + "vet");
- EXPECT_EQ(word.str, "velvet");
-}
-
-TEST(StaticVector, ReverseTruncate) {
- StaticVector<std::string, 10> strings("pie", "quince", "tart", "red", "velvet", "cake");
- EXPECT_FALSE(strings.full());
-
- for (auto it = strings.begin(); it != strings.end(); ++it) {
- strings.replace(it, strings.back());
- strings.pop_back();
- }
-
- EXPECT_EQ(strings, (StaticVector{"cake"s, "velvet"s, "red"s}));
-}
-
-TEST(StaticVector, Sort) {
- StaticVector<std::string, 7> strings("pie", "quince", "tart", "red", "velvet", "cake");
- EXPECT_FALSE(strings.full());
-
- auto sorted = std::move(strings);
- EXPECT_TRUE(strings.empty());
-
- std::sort(sorted.begin(), sorted.end());
- EXPECT_EQ(sorted, (StaticVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
-
- // Constructor takes array reference.
- {
- const char* kStrings[] = {"cake", "lie"};
- strings = StaticVector(kStrings);
- }
-
- EXPECT_GT(sorted, strings);
- swap(sorted, strings);
- EXPECT_LT(sorted, strings);
-
- // Append remaining elements, such that "pie" is the only difference.
- for (const char* str : {"quince", "red", "tart", "velvet"}) {
- sorted.emplace_back(str);
- }
-
- EXPECT_NE(sorted, strings);
-
- // Replace second element with "pie".
- const auto it = sorted.begin() + 1;
- EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie");
-
- EXPECT_EQ(sorted, strings);
-}
-
-namespace {
-
-struct DestroyCounts {
- DestroyCounts(int& live, int& dead) : counts{live, dead} {}
- DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
- DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
- ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
-
- struct {
- int& live;
- int& dead;
- } counts;
-
- bool alive = true;
-};
-
-void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
- std::swap(lhs.alive, rhs.alive);
-}
-
-} // namespace
-
-TEST(StaticVector, Destroy) {
- int live = 0;
- int dead = 0;
-
- { StaticVector<DestroyCounts, 5> counts; }
- EXPECT_EQ(0, live);
- EXPECT_EQ(0, dead);
-
- {
- StaticVector<DestroyCounts, 5> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- }
- EXPECT_EQ(3, live);
- EXPECT_EQ(0, dead);
-
- live = 0;
- {
- StaticVector<DestroyCounts, 5> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- auto copy = counts;
- }
- EXPECT_EQ(6, live);
- EXPECT_EQ(0, dead);
-
- live = 0;
- {
- StaticVector<DestroyCounts, 5> counts;
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
- counts.emplace_back(live, dead);
-
- auto move = std::move(counts);
- }
- EXPECT_EQ(3, live);
- EXPECT_EQ(3, dead);
-
- live = dead = 0;
- {
- StaticVector<DestroyCounts, 5> counts1;
- counts1.emplace_back(live, dead);
- counts1.emplace_back(live, dead);
- counts1.emplace_back(live, dead);
-
- StaticVector<DestroyCounts, 5> counts2;
- counts2.emplace_back(live, dead);
-
- swap(counts1, counts2);
-
- EXPECT_EQ(0, live);
- EXPECT_EQ(2, dead);
-
- dead = 0;
- }
- EXPECT_EQ(4, live);
- EXPECT_EQ(0, dead);
-}
-
-} // namespace android::test
diff --git a/libs/ftl/future_test.cpp b/libs/ftl/future_test.cpp
new file mode 100644
index 0000000..9b3e936
--- /dev/null
+++ b/libs/ftl/future_test.cpp
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#include <ftl/future.h>
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <future>
+#include <string>
+#include <thread>
+#include <vector>
+
+namespace android::test {
+
+// Keep in sync with example usage in header file.
+TEST(Future, Example) {
+ {
+ auto future = ftl::defer([](int x) { return x + 1; }, 99);
+ EXPECT_EQ(future.get(), 100);
+ }
+ {
+ auto future = ftl::yield(42);
+ EXPECT_EQ(future.get(), 42);
+ }
+ {
+ auto ptr = std::make_unique<char>('!');
+ auto future = ftl::yield(std::move(ptr));
+ EXPECT_EQ(*future.get(), '!');
+ }
+ {
+ auto future = ftl::yield(123);
+ std::future<char> futures[] = {ftl::yield('a'), ftl::yield('b')};
+
+ std::future<char> chain = ftl::chain(std::move(future))
+ .then([](int x) { return static_cast<size_t>(x % 2); })
+ .then([&futures](size_t i) { return std::move(futures[i]); });
+
+ EXPECT_EQ(chain.get(), 'b');
+ }
+}
+
+namespace {
+
+using ByteVector = std::vector<uint8_t>;
+
+ByteVector decrement(ByteVector bytes) {
+ std::transform(bytes.begin(), bytes.end(), bytes.begin(), [](auto b) { return b - 1; });
+ return bytes;
+}
+
+} // namespace
+
+TEST(Future, Chain) {
+ std::packaged_task<const char*()> fetch_string([] { return "ifmmp-"; });
+
+ std::packaged_task<ByteVector(std::string)> append_string([](std::string str) {
+ str += "!xpsme";
+ return ByteVector{str.begin(), str.end()};
+ });
+
+ std::packaged_task<std::future<ByteVector>(ByteVector)> decrement_bytes(
+ [](ByteVector bytes) { return ftl::defer(decrement, std::move(bytes)); });
+
+ auto fetch = fetch_string.get_future();
+ std::thread fetch_thread(std::move(fetch_string));
+
+ std::thread append_thread, decrement_thread;
+
+ EXPECT_EQ(
+ "hello, world",
+ ftl::chain(std::move(fetch))
+ .then([](const char* str) { return std::string(str); })
+ .then([&](std::string str) {
+ auto append = append_string.get_future();
+ append_thread = std::thread(std::move(append_string), std::move(str));
+ return append;
+ })
+ .then([&](ByteVector bytes) {
+ auto decrement = decrement_bytes.get_future();
+ decrement_thread = std::thread(std::move(decrement_bytes), std::move(bytes));
+ return decrement;
+ })
+ .then([](std::future<ByteVector> bytes) { return bytes; })
+ .then([](const ByteVector& bytes) { return std::string(bytes.begin(), bytes.end()); })
+ .get());
+
+ fetch_thread.join();
+ append_thread.join();
+ decrement_thread.join();
+}
+
+} // namespace android::test
diff --git a/libs/ftl/small_map_test.cpp b/libs/ftl/small_map_test.cpp
new file mode 100644
index 0000000..323b9f9
--- /dev/null
+++ b/libs/ftl/small_map_test.cpp
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#include <ftl/small_map.h>
+#include <gtest/gtest.h>
+
+#include <cctype>
+
+namespace android::test {
+
+using ftl::SmallMap;
+
+// Keep in sync with example usage in header file.
+TEST(SmallMap, Example) {
+ ftl::SmallMap<int, std::string, 3> map;
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.dynamic());
+
+ map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_TRUE(map.contains(123));
+
+ EXPECT_EQ(map.find(42, [](const std::string& s) { return s.size(); }), 3u);
+
+ const auto opt = map.find(-1);
+ ASSERT_TRUE(opt);
+
+ std::string& ref = *opt;
+ EXPECT_TRUE(ref.empty());
+ ref = "xyz";
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+}
+
+TEST(SmallMap, Construct) {
+ {
+ // Default constructor.
+ SmallMap<int, std::string, 2> map;
+
+ EXPECT_TRUE(map.empty());
+ EXPECT_FALSE(map.dynamic());
+ }
+ {
+ // In-place constructor with same types.
+ SmallMap<int, std::string, 5> map =
+ ftl::init::map<int, std::string>(123, "abc")(456, "def")(789, "ghi");
+
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 5u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(123, "abc")(456, "def")(789, "ghi")));
+ }
+ {
+ // In-place constructor with different types.
+ SmallMap<int, std::string, 5> map =
+ ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 5u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(42, "???")(123, "abc")(-1, "\0\0\0")));
+ }
+ {
+ // In-place constructor with implicit size.
+ SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+
+ static_assert(std::is_same_v<decltype(map), SmallMap<int, std::string, 3>>);
+ EXPECT_EQ(map.size(), 3u);
+ EXPECT_EQ(map.max_size(), 3u);
+ EXPECT_FALSE(map.dynamic());
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map(-1, "\0\0\0")(42, "???")(123, "abc")));
+ }
+}
+
+TEST(SmallMap, Find) {
+ {
+ // Constant reference.
+ const ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+
+ const auto opt = map.find('b');
+ EXPECT_EQ(opt, 'B');
+
+ const char d = 'D';
+ const auto ref = map.find('d').value_or(std::cref(d));
+ EXPECT_EQ(ref.get(), 'D');
+ }
+ {
+ // Mutable reference.
+ ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+
+ const auto opt = map.find('c');
+ EXPECT_EQ(opt, 'C');
+
+ char d = 'd';
+ const auto ref = map.find('d').value_or(std::ref(d));
+ ref.get() = 'D';
+ EXPECT_EQ(d, 'D');
+ }
+ {
+ // Constant unary operation.
+ const ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ EXPECT_EQ(map.find('c', [](char c) { return std::toupper(c); }), 'Z');
+ }
+ {
+ // Mutable unary operation.
+ ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+ EXPECT_TRUE(map.find('c', [](char& c) { c = std::toupper(c); }));
+
+ EXPECT_EQ(map, SmallMap(ftl::init::map('c', 'Z')('b', 'y')('a', 'x')));
+ }
+}
+
+} // namespace android::test
diff --git a/libs/ftl/small_vector_test.cpp b/libs/ftl/small_vector_test.cpp
new file mode 100644
index 0000000..3a03e69
--- /dev/null
+++ b/libs/ftl/small_vector_test.cpp
@@ -0,0 +1,463 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#include <ftl/small_vector.h>
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <iterator>
+#include <string>
+#include <utility>
+
+using namespace std::string_literals;
+
+namespace android::test {
+
+using ftl::SmallVector;
+
+// Keep in sync with example usage in header file.
+TEST(SmallVector, Example) {
+ ftl::SmallVector<char, 3> vector;
+ EXPECT_TRUE(vector.empty());
+ EXPECT_FALSE(vector.dynamic());
+
+ vector = {'a', 'b', 'c'};
+ EXPECT_EQ(vector.size(), 3u);
+ EXPECT_FALSE(vector.dynamic());
+
+ vector.push_back('d');
+ EXPECT_TRUE(vector.dynamic());
+
+ vector.unstable_erase(vector.begin());
+ EXPECT_EQ(vector, (ftl::SmallVector{'d', 'b', 'c'}));
+
+ vector.pop_back();
+ EXPECT_EQ(vector.back(), 'b');
+ EXPECT_TRUE(vector.dynamic());
+
+ const char array[] = "hi";
+ vector = ftl::SmallVector(array);
+ EXPECT_EQ(vector, (ftl::SmallVector{'h', 'i', '\0'}));
+ EXPECT_FALSE(vector.dynamic());
+
+ ftl::SmallVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+ ASSERT_EQ(strings.size(), 3u);
+ EXPECT_FALSE(strings.dynamic());
+
+ EXPECT_EQ(strings[0], "abc");
+ EXPECT_EQ(strings[1], "123");
+ EXPECT_EQ(strings[2], "???");
+}
+
+TEST(SmallVector, Construct) {
+ {
+ // Default constructor.
+ SmallVector<std::string, 2> vector;
+
+ EXPECT_TRUE(vector.empty());
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // Array constructor.
+ const float floats[] = {.1f, .2f, .3f};
+ SmallVector vector(floats);
+
+ EXPECT_EQ(vector, (SmallVector{.1f, .2f, .3f}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // Iterator constructor.
+ const char chars[] = "abcdef";
+ std::string string(chars);
+ SmallVector<char, sizeof(chars)> vector(string.begin(), string.end());
+
+ EXPECT_STREQ(vector.begin(), chars);
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // Variadic constructor with same types.
+ SmallVector vector = {1, 2, 3};
+
+ static_assert(std::is_same_v<decltype(vector), SmallVector<int, 3>>);
+ EXPECT_EQ(vector, (SmallVector{1, 2, 3}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // Variadic constructor with different types.
+ const auto copy = "quince"s;
+ auto move = "tart"s;
+ SmallVector vector = {copy, std::move(move)};
+
+ static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 2>>);
+ EXPECT_EQ(vector, (SmallVector{"quince"s, "tart"s}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // In-place constructor with same types.
+ SmallVector vector =
+ ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
+
+ static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
+ EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // In-place constructor with different types.
+ const auto copy = "red"s;
+ auto move = "velvet"s;
+ std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
+ SmallVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
+
+ static_assert(std::is_same_v<decltype(vector), SmallVector<std::string, 3>>);
+ EXPECT_TRUE(move.empty());
+ EXPECT_EQ(vector, (SmallVector{"red"s, "velvet"s, "cake"s}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+ {
+ // Conversion from StaticVector.
+ ftl::StaticVector doubles = {.1, .2, .3};
+ SmallVector vector = std::move(doubles);
+ EXPECT_TRUE(doubles.empty());
+
+ static_assert(std::is_same_v<decltype(vector), SmallVector<double, 3>>);
+ EXPECT_EQ(vector, (SmallVector{.1, .2, .3}));
+ EXPECT_FALSE(vector.dynamic());
+ }
+}
+
+TEST(SmallVector, String) {
+ SmallVector<char, 10> chars;
+ char c = 'a';
+ std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
+ chars.push_back('\0');
+
+ EXPECT_TRUE(chars.dynamic());
+ EXPECT_EQ(chars.size(), 11u);
+ EXPECT_STREQ(chars.begin(), "abcdefghij");
+
+ // Constructor takes iterator range.
+ const char numbers[] = "123456";
+ SmallVector<char, 10> string(std::begin(numbers), std::end(numbers));
+
+ EXPECT_FALSE(string.dynamic());
+ EXPECT_STREQ(string.begin(), "123456");
+ EXPECT_EQ(string.size(), 7u);
+
+ // Similar to emplace, but replaces rather than inserts.
+ string.replace(string.begin() + 5, '\0');
+ EXPECT_STREQ(string.begin(), "12345");
+
+ swap(chars, string);
+
+ EXPECT_STREQ(chars.begin(), "12345");
+ EXPECT_STREQ(string.begin(), "abcdefghij");
+
+ EXPECT_FALSE(chars.dynamic());
+ EXPECT_TRUE(string.dynamic());
+}
+
+TEST(SmallVector, CopyableElement) {
+ struct Pair {
+ // Needed because std::vector does not use list initialization to emplace.
+ Pair(int a, int b) : a(a), b(b) {}
+
+ const int a, b;
+ bool operator==(Pair p) const { return p.a == a && p.b == b; }
+ };
+
+ SmallVector<Pair, 5> pairs;
+
+ EXPECT_TRUE(pairs.empty());
+ EXPECT_EQ(pairs.max_size(), 5u);
+
+ for (size_t i = 0; i < pairs.max_size(); ++i) {
+ EXPECT_EQ(pairs.size(), i);
+
+ const int a = static_cast<int>(i) * 2;
+ EXPECT_EQ(pairs.emplace_back(a, a + 1), Pair(a, a + 1));
+ }
+
+ EXPECT_EQ(pairs.size(), 5u);
+ EXPECT_FALSE(pairs.dynamic());
+
+ // The vector is promoted when full.
+ EXPECT_EQ(pairs.emplace_back(10, 11), Pair(10, 11));
+ EXPECT_TRUE(pairs.dynamic());
+
+ EXPECT_EQ(pairs, (SmallVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9},
+ Pair{10, 11}}));
+
+ // Constructor takes at most N elements.
+ SmallVector<int, 6> sums = {0, 0, 0, 0, 0, 0};
+ EXPECT_FALSE(sums.dynamic());
+
+ // Random-access iterators comply with standard.
+ std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
+ EXPECT_EQ(sums, (SmallVector{1, 5, 9, 13, 17, 21}));
+
+ sums.pop_back();
+ std::reverse(sums.begin(), sums.end());
+
+ EXPECT_EQ(sums, (SmallVector{17, 13, 9, 5, 1}));
+}
+
+TEST(SmallVector, MovableElement) {
+ // Construct std::string elements in place from per-element arguments.
+ SmallVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
+ strings.pop_back();
+
+ EXPECT_EQ(strings.max_size(), 7u);
+ EXPECT_EQ(strings.size(), 6u);
+
+ // Erase "cake" and append a substring copy.
+ {
+ const auto it =
+ std::find_if(strings.begin(), strings.end(), [](const auto& s) { return !s.empty(); });
+ ASSERT_FALSE(it == strings.end());
+ EXPECT_EQ(*it, "cake");
+
+ // Construct std::string from first 4 characters of string literal.
+ strings.unstable_erase(it);
+ EXPECT_EQ(strings.emplace_back("cakewalk", 4u), "cake"s);
+ }
+
+ strings[1] = "quince"s;
+
+ // Replace last empty string with "tart".
+ {
+ const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
+ ASSERT_FALSE(rit == strings.rend());
+
+ std::initializer_list<char> list = {'t', 'a', 'r', 't'};
+ strings.replace(rit.base() - 1, list);
+ }
+
+ strings.front().assign("pie");
+
+ EXPECT_EQ(strings, (SmallVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
+
+ strings.push_back("nougat");
+ strings.push_back("oreo");
+ EXPECT_TRUE(strings.dynamic());
+
+ std::rotate(strings.begin(), strings.end() - 2, strings.end());
+
+ EXPECT_EQ(strings, (SmallVector{"nougat"s, "oreo"s, "pie"s, "quince"s, "tart"s, "red"s, "velvet"s,
+ "cake"s}));
+}
+
+TEST(SmallVector, Replace) {
+ // Replacing does not require a copy/move assignment operator.
+ struct Word {
+ explicit Word(std::string str) : str(std::move(str)) {}
+ const std::string str;
+
+ bool operator==(const Word& other) const { return other.str == str; }
+ };
+
+ SmallVector words = ftl::init::list<Word>("colored")("velour");
+
+ // The replaced element can be referenced by the replacement.
+ {
+ const Word& word = words.replace(words.last(), words.back().str.substr(0, 3) + "vet");
+ EXPECT_EQ(word, Word("velvet"));
+ }
+
+ // The vector is not promoted if replacing while full.
+ EXPECT_FALSE(words.dynamic());
+
+ words.emplace_back("cake");
+ EXPECT_TRUE(words.dynamic());
+
+ {
+ const Word& word = words.replace(words.begin(), words.front().str.substr(4));
+ EXPECT_EQ(word, Word("red"));
+ }
+
+ EXPECT_EQ(words, (SmallVector{Word("red"), Word("velvet"), Word("cake")}));
+}
+
+TEST(SmallVector, ReverseAppend) {
+ SmallVector strings = {"red"s, "velvet"s, "cake"s};
+ EXPECT_FALSE(strings.dynamic());
+
+ auto rit = strings.rbegin();
+ while (rit != strings.rend()) {
+ // Iterator and reference are invalidated on insertion.
+ const auto i = std::distance(strings.begin(), rit.base());
+ std::string s = *rit;
+
+ strings.push_back(std::move(s));
+ rit = std::make_reverse_iterator(strings.begin() + i) + 1;
+ }
+
+ EXPECT_EQ(strings, (SmallVector{"red"s, "velvet"s, "cake"s, "cake"s, "velvet"s, "red"s}));
+ EXPECT_TRUE(strings.dynamic());
+}
+
+TEST(SmallVector, Sort) {
+ SmallVector strings = ftl::init::list<std::string>("pie")("quince")("tart")("red")("velvet");
+ strings.push_back("cake"s);
+
+ auto sorted = std::move(strings);
+ EXPECT_TRUE(strings.empty());
+
+ EXPECT_TRUE(sorted.dynamic());
+ EXPECT_TRUE(strings.dynamic());
+
+ std::sort(sorted.begin(), sorted.end());
+ EXPECT_EQ(sorted, (SmallVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
+
+ // Constructor takes array reference.
+ {
+ const char* array[] = {"cake", "lie"};
+ strings = SmallVector(array);
+ EXPECT_FALSE(strings.dynamic());
+ }
+
+ EXPECT_GT(sorted, strings);
+ swap(sorted, strings);
+ EXPECT_LT(sorted, strings);
+
+ EXPECT_FALSE(sorted.dynamic());
+ EXPECT_TRUE(strings.dynamic());
+
+ // Append remaining elements, such that "pie" is the only difference.
+ for (const char* str : {"quince", "red", "tart", "velvet"}) {
+ sorted.emplace_back(str);
+ }
+ EXPECT_TRUE(sorted.dynamic());
+
+ EXPECT_NE(sorted, strings);
+
+ // Replace second element with "pie".
+ const auto it = sorted.begin() + 1;
+ EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie");
+
+ EXPECT_EQ(sorted, strings);
+}
+
+namespace {
+
+struct DestroyCounts {
+ DestroyCounts(int& live, int& dead) : counts{live, dead} {}
+ DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
+ DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
+ ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
+
+ struct {
+ int& live;
+ int& dead;
+ } counts;
+
+ bool alive = true;
+};
+
+void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
+ std::swap(lhs.alive, rhs.alive);
+}
+
+} // namespace
+
+TEST(SmallVector, Destroy) {
+ int live = 0;
+ int dead = 0;
+
+ { SmallVector<DestroyCounts, 3> counts; }
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(0, dead);
+
+ {
+ SmallVector<DestroyCounts, 3> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ EXPECT_FALSE(counts.dynamic());
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(0, dead);
+
+ live = 0;
+ {
+ SmallVector<DestroyCounts, 3> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ EXPECT_TRUE(counts.dynamic());
+ }
+ EXPECT_EQ(4, live);
+ EXPECT_EQ(3, dead);
+
+ live = dead = 0;
+ {
+ SmallVector<DestroyCounts, 2> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto copy = counts;
+ EXPECT_TRUE(copy.dynamic());
+ }
+ EXPECT_EQ(6, live);
+ EXPECT_EQ(2, dead);
+
+ live = dead = 0;
+ {
+ SmallVector<DestroyCounts, 2> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto move = std::move(counts);
+ EXPECT_TRUE(move.dynamic());
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(2, dead);
+
+ live = dead = 0;
+ {
+ SmallVector<DestroyCounts, 2> counts1;
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+
+ EXPECT_TRUE(counts1.dynamic());
+ EXPECT_EQ(2, dead);
+ dead = 0;
+
+ SmallVector<DestroyCounts, 2> counts2;
+ counts2.emplace_back(live, dead);
+
+ EXPECT_FALSE(counts2.dynamic());
+
+ swap(counts1, counts2);
+
+ EXPECT_FALSE(counts1.dynamic());
+ EXPECT_TRUE(counts2.dynamic());
+
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(1, dead);
+
+ dead = 0;
+ }
+ EXPECT_EQ(4, live);
+ EXPECT_EQ(0, dead);
+}
+
+} // namespace android::test
diff --git a/libs/ftl/static_vector_test.cpp b/libs/ftl/static_vector_test.cpp
new file mode 100644
index 0000000..cbe8dff
--- /dev/null
+++ b/libs/ftl/static_vector_test.cpp
@@ -0,0 +1,399 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#include <ftl/static_vector.h>
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <iterator>
+#include <string>
+#include <utility>
+
+using namespace std::string_literals;
+
+namespace android::test {
+
+using ftl::StaticVector;
+
+// Keep in sync with example usage in header file.
+TEST(StaticVector, Example) {
+ ftl::StaticVector<char, 3> vector;
+ EXPECT_TRUE(vector.empty());
+
+ vector = {'a', 'b'};
+ EXPECT_EQ(vector.size(), 2u);
+
+ vector.push_back('c');
+ EXPECT_TRUE(vector.full());
+
+ EXPECT_FALSE(vector.push_back('d'));
+ EXPECT_EQ(vector.size(), 3u);
+
+ vector.unstable_erase(vector.begin());
+ EXPECT_EQ(vector, (ftl::StaticVector{'c', 'b'}));
+
+ vector.pop_back();
+ EXPECT_EQ(vector.back(), 'c');
+
+ const char array[] = "hi";
+ vector = ftl::StaticVector(array);
+ EXPECT_EQ(vector, (ftl::StaticVector{'h', 'i', '\0'}));
+
+ ftl::StaticVector strings = ftl::init::list<std::string>("abc")("123456", 3u)(3u, '?');
+ ASSERT_EQ(strings.size(), 3u);
+
+ EXPECT_EQ(strings[0], "abc");
+ EXPECT_EQ(strings[1], "123");
+ EXPECT_EQ(strings[2], "???");
+}
+
+TEST(StaticVector, Construct) {
+ {
+ // Default constructor.
+ StaticVector<std::string, 2> vector;
+ EXPECT_TRUE(vector.empty());
+ }
+ {
+ // Array constructor.
+ const float floats[] = {.1f, .2f, .3f};
+ StaticVector vector(floats);
+ EXPECT_EQ(vector, (StaticVector{.1f, .2f, .3f}));
+ }
+ {
+ // Iterator constructor.
+ const char chars[] = "abcdef";
+ std::string string(chars);
+ StaticVector<char, sizeof(chars)> vector(string.begin(), string.end());
+
+ EXPECT_STREQ(vector.begin(), chars);
+ }
+ {
+ // Variadic constructor with same types.
+ StaticVector vector = {1, 2, 3};
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<int, 3>>);
+ EXPECT_EQ(vector, (StaticVector{1, 2, 3}));
+ }
+ {
+ // Variadic constructor with different types.
+ const auto copy = "quince"s;
+ auto move = "tart"s;
+ StaticVector vector = {copy, std::move(move)};
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 2>>);
+ EXPECT_EQ(vector, (StaticVector{"quince"s, "tart"s}));
+ }
+ {
+ // In-place constructor with same types.
+ StaticVector vector =
+ ftl::init::list<std::string>("redolent", 3u)("velveteen", 6u)("cakewalk", 4u);
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
+ EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
+ }
+ {
+ // In-place constructor with different types.
+ const auto copy = "red"s;
+ auto move = "velvet"s;
+ std::initializer_list<char> list = {'c', 'a', 'k', 'e'};
+ StaticVector vector = ftl::init::list<std::string>(copy.c_str())(std::move(move))(list);
+
+ static_assert(std::is_same_v<decltype(vector), StaticVector<std::string, 3>>);
+ EXPECT_TRUE(move.empty());
+ EXPECT_EQ(vector, (StaticVector{"red"s, "velvet"s, "cake"s}));
+ }
+ {
+ struct String {
+ explicit String(const char* str) : str(str) {}
+ explicit String(const char** ptr) : str(*ptr) {}
+ const char* str;
+ };
+
+ const char* strings[] = {"a", "b", "c", "d"};
+
+ {
+ // Two iterator-like elements.
+ StaticVector<String, 3> vector(strings, strings + 3);
+ ASSERT_EQ(vector.size(), 2u);
+
+ EXPECT_STREQ(vector[0].str, "a");
+ EXPECT_STREQ(vector[1].str, "d");
+ }
+ {
+ // Disambiguating iterator constructor.
+ StaticVector<String, 3> vector(ftl::kIteratorRange, strings, strings + 3);
+ ASSERT_EQ(vector.size(), 3u);
+
+ EXPECT_STREQ(vector[0].str, "a");
+ EXPECT_STREQ(vector[1].str, "b");
+ EXPECT_STREQ(vector[2].str, "c");
+ }
+ }
+}
+
+TEST(StaticVector, String) {
+ StaticVector<char, 10> chars;
+ char c = 'a';
+ std::generate_n(std::back_inserter(chars), chars.max_size(), [&c] { return c++; });
+ chars.back() = '\0';
+
+ EXPECT_STREQ(chars.begin(), "abcdefghi");
+
+ // Constructor takes iterator range.
+ const char numbers[] = "123456";
+ StaticVector<char, 10> string(std::begin(numbers), std::end(numbers));
+
+ EXPECT_STREQ(string.begin(), "123456");
+ EXPECT_EQ(string.size(), 7u);
+
+ // Similar to emplace, but replaces rather than inserts.
+ string.replace(string.begin() + 5, '\0');
+ EXPECT_STREQ(string.begin(), "12345");
+
+ swap(chars, string);
+
+ EXPECT_STREQ(chars.begin(), "12345");
+ EXPECT_STREQ(string.begin(), "abcdefghi");
+}
+
+TEST(StaticVector, CopyableElement) {
+ struct Pair {
+ const int a, b;
+ bool operator==(Pair p) const { return p.a == a && p.b == b; }
+ };
+
+ StaticVector<Pair, 5> pairs;
+
+ EXPECT_TRUE(pairs.empty());
+ EXPECT_EQ(pairs.max_size(), 5u);
+
+ for (size_t i = 0; i < pairs.max_size(); ++i) {
+ EXPECT_EQ(pairs.size(), i);
+
+ const int a = static_cast<int>(i) * 2;
+ const auto it = pairs.emplace_back(a, a + 1);
+ ASSERT_NE(it, pairs.end());
+ EXPECT_EQ(*it, (Pair{a, a + 1}));
+ }
+
+ EXPECT_TRUE(pairs.full());
+ EXPECT_EQ(pairs.size(), 5u);
+
+ // Insertion fails if the vector is full.
+ const auto it = pairs.emplace_back(10, 11);
+ EXPECT_EQ(it, pairs.end());
+
+ EXPECT_EQ(pairs, (StaticVector{Pair{0, 1}, Pair{2, 3}, Pair{4, 5}, Pair{6, 7}, Pair{8, 9}}));
+
+ // Constructor takes at most N elements.
+ StaticVector<int, 6> sums = {0, 0, 0, 0, 0, -1};
+ EXPECT_TRUE(sums.full());
+
+ // Random-access iterators comply with standard.
+ std::transform(pairs.begin(), pairs.end(), sums.begin(), [](Pair p) { return p.a + p.b; });
+ EXPECT_EQ(sums, (StaticVector{1, 5, 9, 13, 17, -1}));
+
+ sums.pop_back();
+ std::reverse(sums.begin(), sums.end());
+
+ EXPECT_EQ(sums, (StaticVector{17, 13, 9, 5, 1}));
+}
+
+TEST(StaticVector, MovableElement) {
+ // Construct std::string elements in place from per-element arguments.
+ StaticVector strings = ftl::init::list<std::string>()()()("cake")("velvet")("red")();
+ strings.pop_back();
+
+ EXPECT_EQ(strings.max_size(), 7u);
+ EXPECT_EQ(strings.size(), 6u);
+
+ // Erase "cake" and append a substring copy.
+ {
+ auto it =
+ std::find_if(strings.begin(), strings.end(), [](const auto& s) { return !s.empty(); });
+ ASSERT_FALSE(it == strings.end());
+ EXPECT_EQ(*it, "cake");
+
+ strings.unstable_erase(it);
+
+ // Construct std::string from first 4 characters of string literal.
+ it = strings.emplace_back("cakewalk", 4u);
+ ASSERT_NE(it, strings.end());
+ EXPECT_EQ(*it, "cake"s);
+ }
+
+ strings[1] = "quince"s;
+
+ // Replace last empty string with "tart".
+ {
+ const auto rit = std::find(strings.rbegin(), strings.rend(), std::string());
+ ASSERT_FALSE(rit == strings.rend());
+
+ std::initializer_list<char> list = {'t', 'a', 'r', 't'};
+ strings.replace(rit.base() - 1, list);
+ }
+
+ strings.front().assign("pie");
+
+ EXPECT_EQ(strings, (StaticVector{"pie"s, "quince"s, "tart"s, "red"s, "velvet"s, "cake"s}));
+}
+
+TEST(StaticVector, Replace) {
+ // Replacing does not require a copy/move assignment operator.
+ struct Word {
+ explicit Word(std::string str) : str(std::move(str)) {}
+ const std::string str;
+ };
+
+ StaticVector words = ftl::init::list<Word>("red")("velour")("cake");
+
+ // The replaced element can be referenced by the replacement.
+ const auto it = words.begin() + 1;
+ const Word& word = words.replace(it, it->str.substr(0, 3) + "vet");
+ EXPECT_EQ(word.str, "velvet");
+}
+
+TEST(StaticVector, ReverseTruncate) {
+ StaticVector<std::string, 10> strings("pie", "quince", "tart", "red", "velvet", "cake");
+ EXPECT_FALSE(strings.full());
+
+ for (auto it = strings.begin(); it != strings.end(); ++it) {
+ strings.replace(it, strings.back());
+ strings.pop_back();
+ }
+
+ EXPECT_EQ(strings, (StaticVector{"cake"s, "velvet"s, "red"s}));
+}
+
+TEST(StaticVector, Sort) {
+ StaticVector<std::string, 7> strings("pie", "quince", "tart", "red", "velvet", "cake");
+ EXPECT_FALSE(strings.full());
+
+ auto sorted = std::move(strings);
+ EXPECT_TRUE(strings.empty());
+
+ std::sort(sorted.begin(), sorted.end());
+ EXPECT_EQ(sorted, (StaticVector{"cake"s, "pie"s, "quince"s, "red"s, "tart"s, "velvet"s}));
+
+ // Constructor takes array reference.
+ {
+ const char* array[] = {"cake", "lie"};
+ strings = StaticVector(array);
+ }
+
+ EXPECT_GT(sorted, strings);
+ swap(sorted, strings);
+ EXPECT_LT(sorted, strings);
+
+ // Append remaining elements, such that "pie" is the only difference.
+ for (const char* str : {"quince", "red", "tart", "velvet"}) {
+ sorted.emplace_back(str);
+ }
+
+ EXPECT_NE(sorted, strings);
+
+ // Replace second element with "pie".
+ const auto it = sorted.begin() + 1;
+ EXPECT_EQ(sorted.replace(it, 'p' + it->substr(1)), "pie");
+
+ EXPECT_EQ(sorted, strings);
+}
+
+namespace {
+
+struct DestroyCounts {
+ DestroyCounts(int& live, int& dead) : counts{live, dead} {}
+ DestroyCounts(const DestroyCounts& other) : counts(other.counts) {}
+ DestroyCounts(DestroyCounts&& other) : counts(other.counts) { other.alive = false; }
+ ~DestroyCounts() { ++(alive ? counts.live : counts.dead); }
+
+ struct {
+ int& live;
+ int& dead;
+ } counts;
+
+ bool alive = true;
+};
+
+void swap(DestroyCounts& lhs, DestroyCounts& rhs) {
+ std::swap(lhs.alive, rhs.alive);
+}
+
+} // namespace
+
+TEST(StaticVector, Destroy) {
+ int live = 0;
+ int dead = 0;
+
+ { StaticVector<DestroyCounts, 5> counts; }
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(0, dead);
+
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(0, dead);
+
+ live = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto copy = counts;
+ }
+ EXPECT_EQ(6, live);
+ EXPECT_EQ(0, dead);
+
+ live = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts;
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+ counts.emplace_back(live, dead);
+
+ auto move = std::move(counts);
+ }
+ EXPECT_EQ(3, live);
+ EXPECT_EQ(3, dead);
+
+ live = dead = 0;
+ {
+ StaticVector<DestroyCounts, 5> counts1;
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+ counts1.emplace_back(live, dead);
+
+ StaticVector<DestroyCounts, 5> counts2;
+ counts2.emplace_back(live, dead);
+
+ swap(counts1, counts2);
+
+ EXPECT_EQ(0, live);
+ EXPECT_EQ(2, dead);
+
+ dead = 0;
+ }
+ EXPECT_EQ(4, live);
+ EXPECT_EQ(0, dead);
+}
+
+} // namespace android::test
diff --git a/libs/input/KeyCharacterMap.cpp b/libs/input/KeyCharacterMap.cpp
index 5666de6..44f3f34 100644
--- a/libs/input/KeyCharacterMap.cpp
+++ b/libs/input/KeyCharacterMap.cpp
@@ -154,7 +154,7 @@
}
std::unique_ptr<Tokenizer> t(tokenizer);
auto ret = load(t.get(), format);
- if (ret) {
+ if (ret.ok()) {
(*ret)->mLoadFileName = filename;
}
return ret;
@@ -170,7 +170,7 @@
}
std::unique_ptr<Tokenizer> t(tokenizer);
auto ret = load(t.get(), format);
- if (ret) {
+ if (ret.ok()) {
(*ret)->mLoadFileName = filename;
}
return ret;
diff --git a/libs/input/KeyLayoutMap.cpp b/libs/input/KeyLayoutMap.cpp
index d36e417..fa5a541 100644
--- a/libs/input/KeyLayoutMap.cpp
+++ b/libs/input/KeyLayoutMap.cpp
@@ -80,7 +80,7 @@
}
std::unique_ptr<Tokenizer> t(tokenizer);
auto ret = load(t.get());
- if (ret) {
+ if (ret.ok()) {
(*ret)->mLoadFileName = filename;
}
return ret;
@@ -95,7 +95,7 @@
}
std::unique_ptr<Tokenizer> t(tokenizer);
auto ret = load(t.get());
- if (ret) {
+ if (ret.ok()) {
(*ret)->mLoadFileName = filename;
}
return ret;
diff --git a/libs/input/Keyboard.cpp b/libs/input/Keyboard.cpp
index 14dc9e5..f0895b3 100644
--- a/libs/input/Keyboard.cpp
+++ b/libs/input/Keyboard.cpp
@@ -111,7 +111,7 @@
}
base::Result<std::shared_ptr<KeyLayoutMap>> ret = KeyLayoutMap::load(path);
- if (!ret) {
+ if (!ret.ok()) {
return ret.error().code();
}
keyLayoutMap = *ret;
@@ -129,7 +129,7 @@
base::Result<std::shared_ptr<KeyCharacterMap>> ret =
KeyCharacterMap::load(path, KeyCharacterMap::Format::BASE);
- if (!ret) {
+ if (!ret.ok()) {
return ret.error().code();
}
keyCharacterMap = *ret;
diff --git a/libs/input/tests/InputDevice_test.cpp b/libs/input/tests/InputDevice_test.cpp
index e2cf245..f8f2f4e 100644
--- a/libs/input/tests/InputDevice_test.cpp
+++ b/libs/input/tests/InputDevice_test.cpp
@@ -43,7 +43,7 @@
KEY_LAYOUT);
ASSERT_FALSE(path.empty());
base::Result<std::shared_ptr<KeyLayoutMap>> ret = KeyLayoutMap::load(path);
- ASSERT_TRUE(ret) << "Cannot load KeyLayout at " << path;
+ ASSERT_TRUE(ret.ok()) << "Cannot load KeyLayout at " << path;
mKeyMap.keyLayoutMap = std::move(*ret);
mKeyMap.keyLayoutFile = path;
}
@@ -58,7 +58,7 @@
ASSERT_FALSE(path.empty()) << "KeyCharacterMap for " << name << " not found";
base::Result<std::shared_ptr<KeyCharacterMap>> ret =
KeyCharacterMap::load(path, KeyCharacterMap::Format::BASE);
- ASSERT_TRUE(ret) << "Cannot load KeyCharacterMap at " << path;
+ ASSERT_TRUE(ret.ok()) << "Cannot load KeyCharacterMap at " << path;
mKeyMap.keyCharacterMap = *ret;
mKeyMap.keyCharacterMapFile = path;
}
@@ -82,4 +82,4 @@
ASSERT_EQ(*map, *mKeyMap.keyCharacterMap);
}
-} // namespace android
\ No newline at end of file
+} // namespace android
diff --git a/opengl/Android.bp b/opengl/Android.bp
index 393ced7..48abdce 100644
--- a/opengl/Android.bp
+++ b/opengl/Android.bp
@@ -52,36 +52,17 @@
license: "include/KHR/NOTICE",
}
-llndk_library {
- name: "libEGL.llndk",
- symbol_file: "libs/libEGL.map.txt",
- export_include_dirs: ["include"],
-}
-
-llndk_library {
- name: "libGLESv1_CM.llndk",
- symbol_file: "libs/libGLESv1_CM.map.txt",
- export_include_dirs: ["include"],
-}
-
-llndk_library {
- name: "libGLESv2.llndk",
- symbol_file: "libs/libGLESv2.map.txt",
- export_include_dirs: ["include"],
-}
-
-llndk_library {
- name: "libGLESv3.llndk",
- symbol_file: "libs/libGLESv3.map.txt",
- export_include_dirs: ["include"],
-}
-
cc_library_headers {
name: "gl_headers",
vendor_available: true,
export_include_dirs: ["include"],
}
+llndk_headers {
+ name: "gl_llndk_headers",
+ export_include_dirs: ["include"],
+}
+
subdirs = [
"*",
]
diff --git a/opengl/libs/Android.bp b/opengl/libs/Android.bp
index 77d887c..5d17561 100644
--- a/opengl/libs/Android.bp
+++ b/opengl/libs/Android.bp
@@ -225,3 +225,27 @@
srcs: ["GLES2/gl2.cpp"],
cflags: ["-DLOG_TAG=\"libGLESv3\""],
}
+
+llndk_library {
+ name: "libEGL.llndk",
+ symbol_file: "libEGL.map.txt",
+ export_llndk_headers: ["gl_llndk_headers"],
+}
+
+llndk_library {
+ name: "libGLESv1_CM.llndk",
+ symbol_file: "libGLESv1_CM.map.txt",
+ export_llndk_headers: ["gl_llndk_headers"],
+}
+
+llndk_library {
+ name: "libGLESv2.llndk",
+ symbol_file: "libGLESv2.map.txt",
+ export_llndk_headers: ["gl_llndk_headers"],
+}
+
+llndk_library {
+ name: "libGLESv3.llndk",
+ symbol_file: "libGLESv3.map.txt",
+ export_llndk_headers: ["gl_llndk_headers"],
+}
diff --git a/services/audiomanager/IAudioManager.cpp b/services/audiomanager/IAudioManager.cpp
index 0d17265..6235f06 100644
--- a/services/audiomanager/IAudioManager.cpp
+++ b/services/audiomanager/IAudioManager.cpp
@@ -84,13 +84,11 @@
return remote()->transact(PLAYER_ATTRIBUTES, data, &reply, IBinder::FLAG_ONEWAY);
}
- virtual status_t playerEvent(audio_unique_id_t piid, player_state_t event,
- audio_port_handle_t deviceId) {
+ virtual status_t playerEvent(audio_unique_id_t piid, player_state_t event) {
Parcel data, reply;
data.writeInterfaceToken(IAudioManager::getInterfaceDescriptor());
data.writeInt32((int32_t) piid);
data.writeInt32((int32_t) event);
- data.writeInt32((int32_t) deviceId);
return remote()->transact(PLAYER_EVENT, data, &reply, IBinder::FLAG_ONEWAY);
}
diff --git a/services/gpuservice/tests/unittests/Android.bp b/services/gpuservice/tests/unittests/Android.bp
index 940a26b..b35a611 100644
--- a/services/gpuservice/tests/unittests/Android.bp
+++ b/services/gpuservice/tests/unittests/Android.bp
@@ -20,6 +20,7 @@
},
srcs: [
"GpuMemTest.cpp",
+ "GpuMemTracerTest.cpp",
"GpuStatsTest.cpp",
],
shared_libs: [
@@ -29,14 +30,18 @@
"libcutils",
"libgfxstats",
"libgpumem",
+ "libgpumemtracer",
"libgraphicsenv",
"liblog",
+ "libprotobuf-cpp-lite",
+ "libprotoutil",
"libstatslog",
"libstatspull",
"libutils",
],
static_libs: [
"libgmock",
+ "perfetto_trace_protos",
],
require_root: true,
}
diff --git a/services/gpuservice/tests/unittests/GpuMemTracerTest.cpp b/services/gpuservice/tests/unittests/GpuMemTracerTest.cpp
new file mode 100644
index 0000000..7fa75e1
--- /dev/null
+++ b/services/gpuservice/tests/unittests/GpuMemTracerTest.cpp
@@ -0,0 +1,182 @@
+/*
+ * Copyright 2020 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.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "gpuservice_unittest"
+
+#include <bpf/BpfMap.h>
+#include <gpumem/GpuMem.h>
+#include <gtest/gtest.h>
+#include <perfetto/trace/trace.pb.h>
+#include <tracing/GpuMemTracer.h>
+
+#include "TestableGpuMem.h"
+
+namespace android {
+
+constexpr uint32_t TEST_MAP_SIZE = 10;
+constexpr uint64_t TEST_GLOBAL_KEY = 0;
+constexpr uint32_t TEST_GLOBAL_PID = 0;
+constexpr uint64_t TEST_GLOBAL_VAL = 123;
+constexpr uint32_t TEST_GLOBAL_GPU_ID = 0;
+constexpr uint64_t TEST_PROC_KEY_1 = 1;
+constexpr uint32_t TEST_PROC_PID_1 = 1;
+constexpr uint64_t TEST_PROC_VAL_1 = 234;
+constexpr uint32_t TEST_PROC_1_GPU_ID = 0;
+constexpr uint64_t TEST_PROC_KEY_2 = 4294967298; // (1 << 32) + 2
+constexpr uint32_t TEST_PROC_PID_2 = 2;
+constexpr uint64_t TEST_PROC_VAL_2 = 345;
+constexpr uint32_t TEST_PROC_2_GPU_ID = 1;
+
+class GpuMemTracerTest : public testing::Test {
+public:
+ GpuMemTracerTest() {
+ const ::testing::TestInfo* const test_info =
+ ::testing::UnitTest::GetInstance()->current_test_info();
+ ALOGD("**** Setting up for %s.%s\n", test_info->test_case_name(), test_info->name());
+ }
+
+ ~GpuMemTracerTest() {
+ const ::testing::TestInfo* const test_info =
+ ::testing::UnitTest::GetInstance()->current_test_info();
+ ALOGD("**** Tearing down after %s.%s\n", test_info->test_case_name(), test_info->name());
+ }
+
+ void SetUp() override {
+ SKIP_IF_BPF_NOT_SUPPORTED;
+ bpf::setrlimitForTest();
+
+ mGpuMem = std::make_shared<GpuMem>();
+ mGpuMemTracer = std::make_unique<GpuMemTracer>();
+ mGpuMemTracer->initializeForTest(mGpuMem);
+ mTestableGpuMem = TestableGpuMem(mGpuMem.get());
+
+ errno = 0;
+ mTestMap = bpf::BpfMap<uint64_t, uint64_t>(BPF_MAP_TYPE_HASH, TEST_MAP_SIZE,
+ BPF_F_NO_PREALLOC);
+
+ EXPECT_EQ(0, errno);
+ EXPECT_LE(0, mTestMap.getMap().get());
+ EXPECT_TRUE(mTestMap.isValid());
+ }
+
+ int getTracerThreadCount() { return mGpuMemTracer->tracerThreadCount; }
+
+ std::shared_ptr<GpuMem> mGpuMem;
+ TestableGpuMem mTestableGpuMem;
+ std::unique_ptr<GpuMemTracer> mGpuMemTracer;
+ bpf::BpfMap<uint64_t, uint64_t> mTestMap;
+};
+
+static constexpr uint64_t getSizeForPid(uint32_t pid) {
+ switch (pid) {
+ case TEST_GLOBAL_PID:
+ return TEST_GLOBAL_VAL;
+ case TEST_PROC_PID_1:
+ return TEST_PROC_VAL_1;
+ case TEST_PROC_PID_2:
+ return TEST_PROC_VAL_2;
+ }
+ return 0;
+}
+
+static constexpr uint32_t getGpuIdForPid(uint32_t pid) {
+ switch (pid) {
+ case TEST_GLOBAL_PID:
+ return TEST_GLOBAL_GPU_ID;
+ case TEST_PROC_PID_1:
+ return TEST_PROC_1_GPU_ID;
+ case TEST_PROC_PID_2:
+ return TEST_PROC_2_GPU_ID;
+ }
+ return 0;
+}
+
+TEST_F(GpuMemTracerTest, traceInitialCountersAfterGpuMemInitialize) {
+ SKIP_IF_BPF_NOT_SUPPORTED;
+ ASSERT_RESULT_OK(mTestMap.writeValue(TEST_GLOBAL_KEY, TEST_GLOBAL_VAL, BPF_ANY));
+ ASSERT_RESULT_OK(mTestMap.writeValue(TEST_PROC_KEY_1, TEST_PROC_VAL_1, BPF_ANY));
+ ASSERT_RESULT_OK(mTestMap.writeValue(TEST_PROC_KEY_2, TEST_PROC_VAL_2, BPF_ANY));
+ mTestableGpuMem.setGpuMemTotalMap(mTestMap);
+ mTestableGpuMem.setInitialized();
+
+ // Only 1 tracer thread should be existing for test.
+ EXPECT_EQ(getTracerThreadCount(), 1);
+ auto tracingSession = mGpuMemTracer->getTracingSessionForTest();
+
+ tracingSession->StartBlocking();
+ // Sleep for a short time to let the tracer thread finish its work
+ sleep(1);
+ tracingSession->StopBlocking();
+
+ // The test tracer thread should have finished its execution by now.
+ EXPECT_EQ(getTracerThreadCount(), 0);
+
+ auto packets = mGpuMemTracer->readGpuMemTotalPacketsForTestBlocking(tracingSession.get());
+ EXPECT_EQ(packets.size(), 3);
+
+ const auto& packet0 = packets[0];
+ ASSERT_TRUE(packet0.has_timestamp());
+ ASSERT_TRUE(packet0.has_gpu_mem_total_event());
+ const auto& gpuMemEvent0 = packet0.gpu_mem_total_event();
+ ASSERT_TRUE(gpuMemEvent0.has_pid());
+ const auto& pid0 = gpuMemEvent0.pid();
+ ASSERT_TRUE(gpuMemEvent0.has_size());
+ EXPECT_EQ(gpuMemEvent0.size(), getSizeForPid(pid0));
+ ASSERT_TRUE(gpuMemEvent0.has_gpu_id());
+ EXPECT_EQ(gpuMemEvent0.gpu_id(), getGpuIdForPid(pid0));
+
+ const auto& packet1 = packets[1];
+ ASSERT_TRUE(packet1.has_timestamp());
+ ASSERT_TRUE(packet1.has_gpu_mem_total_event());
+ const auto& gpuMemEvent1 = packet1.gpu_mem_total_event();
+ ASSERT_TRUE(gpuMemEvent1.has_pid());
+ const auto& pid1 = gpuMemEvent1.pid();
+ ASSERT_TRUE(gpuMemEvent1.has_size());
+ EXPECT_EQ(gpuMemEvent1.size(), getSizeForPid(pid1));
+ ASSERT_TRUE(gpuMemEvent1.has_gpu_id());
+ EXPECT_EQ(gpuMemEvent1.gpu_id(), getGpuIdForPid(pid1));
+
+ const auto& packet2 = packets[2];
+ ASSERT_TRUE(packet2.has_timestamp());
+ ASSERT_TRUE(packet2.has_gpu_mem_total_event());
+ const auto& gpuMemEvent2 = packet2.gpu_mem_total_event();
+ ASSERT_TRUE(gpuMemEvent2.has_pid());
+ const auto& pid2 = gpuMemEvent2.pid();
+ ASSERT_TRUE(gpuMemEvent2.has_size());
+ EXPECT_EQ(gpuMemEvent2.size(), getSizeForPid(pid2));
+ ASSERT_TRUE(gpuMemEvent2.has_gpu_id());
+ EXPECT_EQ(gpuMemEvent2.gpu_id(), getGpuIdForPid(pid2));
+}
+
+TEST_F(GpuMemTracerTest, noTracingWithoutGpuMemInitialize) {
+ // Only 1 tracer thread should be existing for test.
+ EXPECT_EQ(getTracerThreadCount(), 1);
+
+ auto tracingSession = mGpuMemTracer->getTracingSessionForTest();
+
+ tracingSession->StartBlocking();
+ // Sleep for a short time to let the tracer thread finish its work
+ sleep(1);
+ tracingSession->StopBlocking();
+
+ // The test tracer thread should have finished its execution by now.
+ EXPECT_EQ(getTracerThreadCount(), 0);
+
+ auto packets = mGpuMemTracer->readGpuMemTotalPacketsForTestBlocking(tracingSession.get());
+ EXPECT_EQ(packets.size(), 0);
+}
+} // namespace android
diff --git a/services/gpuservice/tracing/Android.bp b/services/gpuservice/tracing/Android.bp
index 919fed3..9f951d3 100644
--- a/services/gpuservice/tracing/Android.bp
+++ b/services/gpuservice/tracing/Android.bp
@@ -21,10 +21,13 @@
"libgpumem",
"libbase",
"liblog",
+ "libprotobuf-cpp-lite",
+ "libprotoutil",
"libutils",
],
static_libs: [
"libperfetto_client_experimental",
+ "perfetto_trace_protos",
],
export_include_dirs: ["include"],
export_static_lib_headers: [
diff --git a/services/gpuservice/tracing/GpuMemTracer.cpp b/services/gpuservice/tracing/GpuMemTracer.cpp
index 000cf27..584498e 100644
--- a/services/gpuservice/tracing/GpuMemTracer.cpp
+++ b/services/gpuservice/tracing/GpuMemTracer.cpp
@@ -22,6 +22,7 @@
#include <gpumem/GpuMem.h>
#include <perfetto/trace/android/gpu_mem_event.pbzero.h>
+#include <perfetto/trace/trace.pb.h>
#include <unistd.h>
#include <thread>
@@ -44,9 +45,51 @@
args.backends = perfetto::kSystemBackend;
perfetto::Tracing::Initialize(args);
registerDataSource();
- std::thread tracerThread(&GpuMemTracer::threadLoop, this);
+ std::thread tracerThread(&GpuMemTracer::threadLoop, this, true);
pthread_setname_np(tracerThread.native_handle(), "GpuMemTracerThread");
tracerThread.detach();
+ tracerThreadCount++;
+}
+
+void GpuMemTracer::initializeForTest(std::shared_ptr<GpuMem> gpuMem) {
+ mGpuMem = gpuMem;
+ perfetto::TracingInitArgs args;
+ args.backends = perfetto::kInProcessBackend;
+ perfetto::Tracing::Initialize(args);
+ registerDataSource();
+ std::thread tracerThread(&GpuMemTracer::threadLoop, this, false);
+ pthread_setname_np(tracerThread.native_handle(), "GpuMemTracerThreadForTest");
+ tracerThread.detach();
+ tracerThreadCount++;
+}
+
+std::vector<perfetto::protos::TracePacket> GpuMemTracer::readGpuMemTotalPacketsForTestBlocking(
+ perfetto::TracingSession* tracingSession) {
+ std::vector<char> raw_trace = tracingSession->ReadTraceBlocking();
+ perfetto::protos::Trace trace;
+ trace.ParseFromArray(raw_trace.data(), int(raw_trace.size()));
+
+ std::vector<perfetto::protos::TracePacket> packets;
+ for (const auto& packet : trace.packet()) {
+ if (!packet.has_gpu_mem_total_event()) {
+ continue;
+ }
+ packets.emplace_back(packet);
+ }
+ return packets;
+}
+
+// Each tracing session can be used for a single block of Start -> Stop.
+std::unique_ptr<perfetto::TracingSession> GpuMemTracer::getTracingSessionForTest() {
+ perfetto::TraceConfig cfg;
+ cfg.set_duration_ms(500);
+ cfg.add_buffers()->set_size_kb(1024);
+ auto* ds_cfg = cfg.add_data_sources()->mutable_config();
+ ds_cfg->set_name(GpuMemTracer::kGpuMemDataSource);
+
+ auto tracingSession = perfetto::Tracing::NewTrace(perfetto::kInProcessBackend);
+ tracingSession->Setup(cfg);
+ return tracingSession;
}
void GpuMemTracer::registerDataSource() {
@@ -55,8 +98,8 @@
GpuMemDataSource::Register(dsd);
}
-void GpuMemTracer::threadLoop() {
- while (true) {
+void GpuMemTracer::threadLoop(bool infiniteLoop) {
+ do {
{
std::unique_lock<std::mutex> lock(GpuMemTracer::sTraceMutex);
while (!sTraceStarted) {
@@ -68,7 +111,11 @@
std::lock_guard<std::mutex> lock(GpuMemTracer::sTraceMutex);
sTraceStarted = false;
}
- }
+ } while (infiniteLoop);
+
+ // Thread loop is exiting. Reduce the tracerThreadCount to reflect the number of active threads
+ // in the wait loop.
+ tracerThreadCount--;
}
void GpuMemTracer::traceInitialCounters() {
diff --git a/services/gpuservice/tracing/include/tracing/GpuMemTracer.h b/services/gpuservice/tracing/include/tracing/GpuMemTracer.h
index 40deb4c..ae871f1 100644
--- a/services/gpuservice/tracing/include/tracing/GpuMemTracer.h
+++ b/services/gpuservice/tracing/include/tracing/GpuMemTracer.h
@@ -20,6 +20,10 @@
#include <mutex>
+namespace perfetto::protos {
+class TracePacket;
+}
+
namespace android {
class GpuMem;
@@ -45,16 +49,37 @@
// perfetto::kInProcessBackend in tests.
void registerDataSource();
+ // TODO(b/175904796): Refactor gpuservice lib to include perfetto lib and move the test
+ // functions into the unittests.
+ // Functions only used for testing with in-process backend. These functions require the static
+ // perfetto lib to be linked. If the tests have a perfetto linked, while libgpumemtracer.so also
+ // has one linked, they will both use different static states maintained in perfetto. Since the
+ // static perfetto states are not shared, tracing sessions created in the unit test are not
+ // recognized by GpuMemTracer. As a result, we cannot use any of the perfetto functions from
+ // this class, which defeats the purpose of the unit test. To solve this, we restrict all
+ // tracing functionality to this class, while the unit test validates the data.
+ // Sets up the perfetto in-process backend and calls into registerDataSource.
+ void initializeForTest(std::shared_ptr<GpuMem>);
+ // Creates a tracing session with in process backend, for testing.
+ std::unique_ptr<perfetto::TracingSession> getTracingSessionForTest();
+ // Read and filter the gpu memory packets from the created trace.
+ std::vector<perfetto::protos::TracePacket> readGpuMemTotalPacketsForTestBlocking(
+ perfetto::TracingSession* tracingSession);
+
static constexpr char kGpuMemDataSource[] = "android.gpu.memory";
static std::condition_variable sCondition;
static std::mutex sTraceMutex;
static bool sTraceStarted;
private:
- void traceInitialCounters();
- void threadLoop();
+ // Friend class for testing
+ friend class GpuMemTracerTest;
+ void threadLoop(bool infiniteLoop);
+ void traceInitialCounters();
std::shared_ptr<GpuMem> mGpuMem;
+ // Count of how many tracer threads are currently active. Useful for testing.
+ std::atomic<int32_t> tracerThreadCount = 0;
};
} // namespace android
diff --git a/services/inputflinger/InputManager.cpp b/services/inputflinger/InputManager.cpp
index 3d99589..a50e5c7 100644
--- a/services/inputflinger/InputManager.cpp
+++ b/services/inputflinger/InputManager.cpp
@@ -148,7 +148,7 @@
}
base::Result<std::unique_ptr<InputChannel>> channel = mDispatcher->createInputChannel(name);
- if (!channel) {
+ if (!channel.ok()) {
return binder::Status::fromExceptionCode(exceptionCodeFromStatusT(channel.error().code()),
channel.error().message().c_str());
}
diff --git a/services/inputflinger/OWNERS b/services/inputflinger/OWNERS
index 0313a40..82c6ee1 100644
--- a/services/inputflinger/OWNERS
+++ b/services/inputflinger/OWNERS
@@ -1,2 +1,3 @@
+lzye@google.com
michaelwr@google.com
svv@google.com
diff --git a/services/inputflinger/dispatcher/InputDispatcher.cpp b/services/inputflinger/dispatcher/InputDispatcher.cpp
index 5ccff18..5832109 100644
--- a/services/inputflinger/dispatcher/InputDispatcher.cpp
+++ b/services/inputflinger/dispatcher/InputDispatcher.cpp
@@ -4932,7 +4932,7 @@
}
base::Result<std::unique_ptr<InputChannel>> InputDispatcher::createInputMonitor(
- int32_t displayId, bool isGestureMonitor, const std::string& name) {
+ int32_t displayId, bool isGestureMonitor, const std::string& name, int32_t pid) {
std::shared_ptr<InputChannel> serverChannel;
std::unique_ptr<InputChannel> clientChannel;
status_t result = openInputChannelPair(name, serverChannel, clientChannel);
@@ -4956,7 +4956,7 @@
auto& monitorsByDisplay =
isGestureMonitor ? mGestureMonitorsByDisplay : mGlobalMonitorsByDisplay;
- monitorsByDisplay[displayId].emplace_back(serverChannel);
+ monitorsByDisplay[displayId].emplace_back(serverChannel, pid);
mLooper->addFd(fd, 0, ALOOPER_EVENT_INPUT, handleReceiveCallback, this);
}
diff --git a/services/inputflinger/dispatcher/InputDispatcher.h b/services/inputflinger/dispatcher/InputDispatcher.h
index 3004701..4806a27 100644
--- a/services/inputflinger/dispatcher/InputDispatcher.h
+++ b/services/inputflinger/dispatcher/InputDispatcher.h
@@ -124,8 +124,10 @@
virtual base::Result<std::unique_ptr<InputChannel>> createInputChannel(
const std::string& name) override;
virtual void setFocusedWindow(const FocusRequest&) override;
- virtual base::Result<std::unique_ptr<InputChannel>> createInputMonitor(
- int32_t displayId, bool isGestureMonitor, const std::string& name) override;
+ virtual base::Result<std::unique_ptr<InputChannel>> createInputMonitor(int32_t displayId,
+ bool isGestureMonitor,
+ const std::string& name,
+ int32_t pid) override;
virtual status_t removeInputChannel(const sp<IBinder>& connectionToken) override;
virtual status_t pilferPointers(const sp<IBinder>& token) override;
virtual void requestPointerCapture(const sp<IBinder>& windowToken, bool enabled) override;
diff --git a/services/inputflinger/dispatcher/Monitor.cpp b/services/inputflinger/dispatcher/Monitor.cpp
index b347674..bbce759 100644
--- a/services/inputflinger/dispatcher/Monitor.cpp
+++ b/services/inputflinger/dispatcher/Monitor.cpp
@@ -19,7 +19,8 @@
namespace android::inputdispatcher {
// --- Monitor ---
-Monitor::Monitor(const std::shared_ptr<InputChannel>& inputChannel) : inputChannel(inputChannel) {}
+Monitor::Monitor(const std::shared_ptr<InputChannel>& inputChannel, int32_t pid)
+ : inputChannel(inputChannel), pid(pid) {}
// --- TouchedMonitor ---
TouchedMonitor::TouchedMonitor(const Monitor& monitor, float xOffset, float yOffset)
diff --git a/services/inputflinger/dispatcher/Monitor.h b/services/inputflinger/dispatcher/Monitor.h
index fc0b020..7be0760 100644
--- a/services/inputflinger/dispatcher/Monitor.h
+++ b/services/inputflinger/dispatcher/Monitor.h
@@ -24,7 +24,9 @@
struct Monitor {
std::shared_ptr<InputChannel> inputChannel; // never null
- explicit Monitor(const std::shared_ptr<InputChannel>& inputChannel);
+ int32_t pid;
+
+ explicit Monitor(const std::shared_ptr<InputChannel>& inputChannel, int32_t pid);
};
// For tracking the offsets we need to apply when adding gesture monitor targets.
diff --git a/services/inputflinger/dispatcher/include/InputDispatcherInterface.h b/services/inputflinger/dispatcher/include/InputDispatcherInterface.h
index 6e76c92..3491893 100644
--- a/services/inputflinger/dispatcher/include/InputDispatcherInterface.h
+++ b/services/inputflinger/dispatcher/include/InputDispatcherInterface.h
@@ -173,8 +173,10 @@
*
* This method may be called on any thread (usually by the input manager).
*/
- virtual base::Result<std::unique_ptr<InputChannel>> createInputMonitor(
- int32_t displayId, bool gestureMonitor, const std::string& name) = 0;
+ virtual base::Result<std::unique_ptr<InputChannel>> createInputMonitor(int32_t displayId,
+ bool gestureMonitor,
+ const std::string& name,
+ int32_t pid) = 0;
/* Removes input channels that will no longer receive input events.
*
diff --git a/services/inputflinger/reader/mapper/SensorInputMapper.cpp b/services/inputflinger/reader/mapper/SensorInputMapper.cpp
index 7d97014..7ac2dec 100644
--- a/services/inputflinger/reader/mapper/SensorInputMapper.cpp
+++ b/services/inputflinger/reader/mapper/SensorInputMapper.cpp
@@ -146,7 +146,7 @@
axisInfo.axis = -1;
// Check key layout map for sensor data mapping to axes
auto ret = getDeviceContext().mapSensor(abs);
- if (ret) {
+ if (ret.ok()) {
InputDeviceSensorType sensorType = (*ret).first;
int32_t sensorDataIndex = (*ret).second;
const Axis& axis = createAxis(axisInfo, rawAxisInfo);
diff --git a/services/inputflinger/reader/mapper/SensorInputMapper.h b/services/inputflinger/reader/mapper/SensorInputMapper.h
index 3371002..1797fe3 100644
--- a/services/inputflinger/reader/mapper/SensorInputMapper.h
+++ b/services/inputflinger/reader/mapper/SensorInputMapper.h
@@ -98,7 +98,6 @@
this->samplingPeriod = std::chrono::nanoseconds(0);
this->maxBatchReportLatency = std::chrono::nanoseconds(0);
this->lastSampleTimeNs = std::nullopt;
- this->dataVec.fill(0);
}
};
diff --git a/services/inputflinger/tests/InputDispatcher_test.cpp b/services/inputflinger/tests/InputDispatcher_test.cpp
index e365529..0b30ff5 100644
--- a/services/inputflinger/tests/InputDispatcher_test.cpp
+++ b/services/inputflinger/tests/InputDispatcher_test.cpp
@@ -48,6 +48,9 @@
static const int32_t INJECTOR_PID = 999;
static const int32_t INJECTOR_UID = 1001;
+// An arbitrary pid of the gesture monitor window
+static constexpr int32_t MONITOR_PID = 2001;
+
struct PointF {
float x;
float y;
@@ -1787,7 +1790,7 @@
FakeMonitorReceiver(const sp<InputDispatcher>& dispatcher, const std::string name,
int32_t displayId, bool isGestureMonitor = false) {
base::Result<std::unique_ptr<InputChannel>> channel =
- dispatcher->createInputMonitor(displayId, isGestureMonitor, name);
+ dispatcher->createInputMonitor(displayId, isGestureMonitor, name, MONITOR_PID);
mInputReceiver = std::make_unique<FakeInputReceiver>(std::move(*channel), name);
}
diff --git a/services/surfaceflinger/BufferStateLayer.cpp b/services/surfaceflinger/BufferStateLayer.cpp
index b6c59cd..0b9caba 100644
--- a/services/surfaceflinger/BufferStateLayer.cpp
+++ b/services/surfaceflinger/BufferStateLayer.cpp
@@ -347,6 +347,12 @@
if (mCurrentState.buffer) {
mReleasePreviousBuffer = true;
+ if (mCurrentState.buffer != mDrawingState.buffer) {
+ // If mCurrentState has a buffer, and we are about to update again
+ // before swapping to drawing state, then the first buffer will be
+ // dropped and we should decrement the pending buffer count.
+ decrementPendingBufferCount();
+ }
}
mCurrentState.frameNumber = frameNumber;
@@ -629,6 +635,7 @@
if (s.buffer == nullptr) {
return BAD_VALUE;
}
+ decrementPendingBufferCount();
mPreviousBufferId = getCurrentBufferId();
mBufferInfo.mBuffer = s.buffer;
@@ -826,6 +833,32 @@
const Rect layerSize{getBounds()};
return layerSize.width() != bufferWidth || layerSize.height() != bufferHeight;
}
+
+void BufferStateLayer::incrementPendingBufferCount() {
+ mPendingBufferTransactions++;
+ tracePendingBufferCount();
+}
+
+void BufferStateLayer::decrementPendingBufferCount() {
+ mPendingBufferTransactions--;
+ tracePendingBufferCount();
+}
+
+void BufferStateLayer::tracePendingBufferCount() {
+ ATRACE_INT(mBlastTransactionName.c_str(), mPendingBufferTransactions);
+}
+
+uint32_t BufferStateLayer::doTransaction(uint32_t flags) {
+ if (mDrawingState.buffer != nullptr && mDrawingState.buffer != mBufferInfo.mBuffer) {
+ // If we are about to update mDrawingState.buffer but it has not yet latched
+ // then we will drop a buffer and should decrement the pending buffer count.
+ // This logic may not work perfectly in the face of a BufferStateLayer being the
+ // deferred side of a deferred transaction, but we don't expect this use case.
+ decrementPendingBufferCount();
+ }
+ return Layer::doTransaction(flags);
+}
+
} // namespace android
// TODO(b/129481165): remove the #pragma below and fix conversion issues
diff --git a/services/surfaceflinger/BufferStateLayer.h b/services/surfaceflinger/BufferStateLayer.h
index 69b27e4..ad00c65 100644
--- a/services/surfaceflinger/BufferStateLayer.h
+++ b/services/surfaceflinger/BufferStateLayer.h
@@ -112,6 +112,11 @@
bool onPreComposition(nsecs_t refreshStartTime) override;
uint32_t getEffectiveScalingMode() const override;
+ // See mPendingBufferTransactions
+ void incrementPendingBufferCount() override;
+ void decrementPendingBufferCount();
+ uint32_t doTransaction(uint32_t flags) override;
+
protected:
void gatherBufferInfo() override;
uint64_t getHeadFrameNumber(nsecs_t expectedPresentTime) const;
@@ -119,6 +124,7 @@
private:
friend class SlotGenerationTest;
+ inline void tracePendingBufferCount();
bool updateFrameEventHistory(const sp<Fence>& acquireFence, nsecs_t postedTime,
nsecs_t requestedPresentTime);
@@ -163,6 +169,18 @@
std::deque<std::shared_ptr<android::frametimeline::SurfaceFrame>> mPendingJankClassifications;
+ const std::string mBlastTransactionName{"BufferTX - " + mName};
+ // This integer is incremented everytime a buffer arrives at the server for this layer,
+ // and decremented when a buffer is dropped or latched. When changed the integer is exported
+ // to systrace with ATRACE_INT and mBlastTransactionName. This way when debugging perf it is
+ // possible to see when a buffer arrived at the server, and in which frame it latched.
+ //
+ // You can understand the trace this way:
+ // - If the integer increases, a buffer arrived at the server.
+ // - If the integer decreases in latchBuffer, that buffer was latched
+ // - If the integer decreases in setBuffer or doTransaction, a buffer was dropped
+ uint64_t mPendingBufferTransactions{0};
+
// TODO(marissaw): support sticky transform for LEGACY camera mode
class HwcSlotGenerator : public ClientCache::ErasedRecipient {
diff --git a/services/surfaceflinger/DisplayHardware/HWC2.cpp b/services/surfaceflinger/DisplayHardware/HWC2.cpp
index e6bff04..426092d 100644
--- a/services/surfaceflinger/DisplayHardware/HWC2.cpp
+++ b/services/surfaceflinger/DisplayHardware/HWC2.cpp
@@ -26,18 +26,17 @@
#include "HWC2.h"
+#include <android/configuration.h>
+#include <ftl/future.h>
#include <ui/Fence.h>
#include <ui/FloatRect.h>
#include <ui/GraphicBuffer.h>
-#include <android/configuration.h>
-
-#include <inttypes.h>
#include <algorithm>
+#include <cinttypes>
#include <iterator>
#include <set>
-#include "../Promise.h"
#include "ComposerHal.h"
namespace android {
@@ -647,7 +646,7 @@
}
std::future<Error> Display::setDisplayBrightness(float brightness) {
- return promise::defer([composer = &mComposer, id = mId, brightness] {
+ return ftl::defer([composer = &mComposer, id = mId, brightness] {
const auto intError = composer->setDisplayBrightness(id, brightness);
return static_cast<Error>(intError);
});
diff --git a/services/surfaceflinger/DisplayHardware/HWComposer.cpp b/services/surfaceflinger/DisplayHardware/HWComposer.cpp
index 1548d18..5fa72b8 100644
--- a/services/surfaceflinger/DisplayHardware/HWComposer.cpp
+++ b/services/surfaceflinger/DisplayHardware/HWComposer.cpp
@@ -30,6 +30,7 @@
#include <compositionengine/Output.h>
#include <compositionengine/OutputLayer.h>
#include <compositionengine/impl/OutputLayerCompositionState.h>
+#include <ftl/future.h>
#include <log/log.h>
#include <ui/DebugUtils.h>
#include <ui/GraphicBuffer.h>
@@ -37,7 +38,6 @@
#include <utils/Trace.h>
#include "../Layer.h" // needed only for debugging
-#include "../Promise.h"
#include "../SurfaceFlinger.h"
#include "../SurfaceFlingerProperties.h"
#include "ComposerHal.h"
@@ -792,10 +792,10 @@
std::future<status_t> HWComposer::setDisplayBrightness(PhysicalDisplayId displayId,
float brightness) {
- RETURN_IF_INVALID_DISPLAY(displayId, promise::yield<status_t>(BAD_INDEX));
+ RETURN_IF_INVALID_DISPLAY(displayId, ftl::yield<status_t>(BAD_INDEX));
auto& display = mDisplayData[displayId].hwcDisplay;
- return promise::chain(display->setDisplayBrightness(brightness))
+ return ftl::chain(display->setDisplayBrightness(brightness))
.then([displayId](hal::Error error) -> status_t {
if (error == hal::Error::UNSUPPORTED) {
RETURN_IF_HWC_ERROR(error, displayId, INVALID_OPERATION);
diff --git a/services/surfaceflinger/Layer.cpp b/services/surfaceflinger/Layer.cpp
index 0e861ab..f53c4cc 100644
--- a/services/surfaceflinger/Layer.cpp
+++ b/services/surfaceflinger/Layer.cpp
@@ -2187,7 +2187,10 @@
}
int32_t Layer::getBackgroundBlurRadius() const {
- return getDrawingState().backgroundBlurRadius;
+ const auto& p = mDrawingParent.promote();
+
+ half parentAlpha = (p != nullptr) ? p->getAlpha() : 1.0_hf;
+ return parentAlpha * getDrawingState().backgroundBlurRadius;
}
const std::vector<BlurRegion>& Layer::getBlurRegions() const {
diff --git a/services/surfaceflinger/Layer.h b/services/surfaceflinger/Layer.h
index 2cfdba3..bb897d5 100644
--- a/services/surfaceflinger/Layer.h
+++ b/services/surfaceflinger/Layer.h
@@ -481,6 +481,8 @@
virtual void useSurfaceDamage() {}
virtual void useEmptyDamage() {}
+ virtual void incrementPendingBufferCount() {}
+
/*
* isOpaque - true if this surface is opaque
*
@@ -745,7 +747,7 @@
* doTransaction - process the transaction. This is a good place to figure
* out which attributes of the surface have changed.
*/
- uint32_t doTransaction(uint32_t transactionFlags);
+ virtual uint32_t doTransaction(uint32_t transactionFlags);
/*
* Remove relative z for the layer if its relative parent is not part of the
diff --git a/services/surfaceflinger/Promise.h b/services/surfaceflinger/Promise.h
deleted file mode 100644
index a80d441..0000000
--- a/services/surfaceflinger/Promise.h
+++ /dev/null
@@ -1,80 +0,0 @@
-/*
- * Copyright 2020 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 <future>
-#include <type_traits>
-#include <utility>
-
-namespace android::promise {
-namespace impl {
-
-template <typename T>
-struct FutureResult {
- using Type = T;
-};
-
-template <typename T>
-struct FutureResult<std::future<T>> {
- using Type = T;
-};
-
-} // namespace impl
-
-template <typename T>
-using FutureResult = typename impl::FutureResult<T>::Type;
-
-template <typename... Args>
-inline auto defer(Args... args) {
- return std::async(std::launch::deferred, std::forward<Args>(args)...);
-}
-
-template <typename T>
-inline std::future<T> yield(T&& v) {
- return defer([](T&& v) { return std::forward<T>(v); }, std::forward<T>(v));
-}
-
-template <typename T>
-struct Chain {
- Chain(std::future<T>&& f) : future(std::move(f)) {}
- operator std::future<T>&&() && { return std::move(future); }
-
- T get() && { return future.get(); }
-
- template <typename F, typename R = std::invoke_result_t<F, T>>
- auto then(F&& op) && -> Chain<FutureResult<R>> {
- return defer(
- [](auto&& f, F&& op) {
- R r = op(f.get());
- if constexpr (std::is_same_v<R, FutureResult<R>>) {
- return r;
- } else {
- return r.get();
- }
- },
- std::move(future), std::forward<F>(op));
- }
-
- std::future<T> future;
-};
-
-template <typename T>
-inline Chain<T> chain(std::future<T>&& f) {
- return std::move(f);
-}
-
-} // namespace android::promise
diff --git a/services/surfaceflinger/RegionSamplingThread.cpp b/services/surfaceflinger/RegionSamplingThread.cpp
index 2511eb3..ad4877b 100644
--- a/services/surfaceflinger/RegionSamplingThread.cpp
+++ b/services/surfaceflinger/RegionSamplingThread.cpp
@@ -28,6 +28,7 @@
#include <compositionengine/Display.h>
#include <compositionengine/impl/OutputCompositionState.h>
#include <cutils/properties.h>
+#include <ftl/future.h>
#include <gui/IRegionSamplingListener.h>
#include <gui/SyncScreenCaptureListener.h>
#include <ui/DisplayStatInfo.h>
@@ -38,7 +39,6 @@
#include "DisplayDevice.h"
#include "DisplayRenderArea.h"
#include "Layer.h"
-#include "Promise.h"
#include "Scheduler/VsyncController.h"
#include "SurfaceFlinger.h"
@@ -389,7 +389,7 @@
const Rect sampledBounds = sampleRegion.bounds();
- SurfaceFlinger::RenderAreaFuture renderAreaFuture = promise::defer([=] {
+ SurfaceFlinger::RenderAreaFuture renderAreaFuture = ftl::defer([=] {
return DisplayRenderArea::create(displayWeak, screencapRegion.bounds(),
sampledBounds.getSize(), ui::Dataspace::V0_SRGB,
orientation);
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index 16996b8..38ee1eb 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -47,8 +47,7 @@
#include <configstore/Utils.h>
#include <cutils/compiler.h>
#include <cutils/properties.h>
-#include <dlfcn.h>
-#include <errno.h>
+#include <ftl/future.h>
#include <gui/BufferQueue.h>
#include <gui/DebugEGLImageTracker.h>
#include <gui/IDisplayEventConnection.h>
@@ -81,6 +80,7 @@
#include <utils/misc.h>
#include <algorithm>
+#include <cerrno>
#include <cinttypes>
#include <cmath>
#include <cstdint>
@@ -112,7 +112,6 @@
#include "LayerVector.h"
#include "MonitoredProducer.h"
#include "NativeWindowSurface.h"
-#include "Promise.h"
#include "RefreshRateOverlay.h"
#include "RegionSamplingThread.h"
#include "Scheduler/DispSyncSource.h"
@@ -1513,12 +1512,12 @@
return BAD_VALUE;
}
- return promise::chain(schedule([=]() MAIN_THREAD {
+ return ftl::chain(schedule([=]() MAIN_THREAD {
if (const auto displayId = getPhysicalDisplayIdLocked(displayToken)) {
return getHwComposer().setDisplayBrightness(*displayId, brightness);
} else {
ALOGE("%s: Invalid display token %p", __FUNCTION__, displayToken.get());
- return promise::yield<status_t>(NAME_NOT_FOUND);
+ return ftl::yield<status_t>(NAME_NOT_FOUND);
}
}))
.then([](std::future<status_t> task) { return task; })
@@ -3274,14 +3273,16 @@
bool SurfaceFlinger::transactionIsReadyToBeApplied(int64_t desiredPresentTime,
- const Vector<ComposerState>& states) {
+ const Vector<ComposerState>& states,
+ bool updateTransactionCounters) {
const nsecs_t expectedPresentTime = mExpectedPresentTime.load();
+ bool ready = true;
// Do not present if the desiredPresentTime has not passed unless it is more than one second
// in the future. We ignore timestamps more than 1 second in the future for stability reasons.
if (desiredPresentTime >= 0 && desiredPresentTime >= expectedPresentTime &&
desiredPresentTime < expectedPresentTime + s2ns(1)) {
- return false;
+ ready = false;
}
for (const ComposerState& state : states) {
@@ -3290,10 +3291,22 @@
continue;
}
if (s.acquireFence && s.acquireFence->getStatus() == Fence::Status::Unsignaled) {
- return false;
+ ready = false;
+ }
+ if (updateTransactionCounters) {
+ sp<Layer> layer = nullptr;
+ if (s.surface) {
+ layer = fromHandleLocked(s.surface).promote();
+ } else {
+ ALOGW("Transaction with buffer, but no Layer?");
+ continue;
+ }
+ // See BufferStateLayer::mPendingBufferTransactions
+ if (layer) layer->incrementPendingBufferCount();
+
}
}
- return true;
+ return ready;
}
status_t SurfaceFlinger::setTransactionState(
@@ -3337,7 +3350,7 @@
const int originPid = ipc->getCallingPid();
const int originUid = ipc->getCallingUid();
- if (pendingTransactions || !transactionIsReadyToBeApplied(desiredPresentTime, states)) {
+ if (pendingTransactions || !transactionIsReadyToBeApplied(desiredPresentTime, states, true)) {
mTransactionQueues[applyToken].emplace(frameTimelineVsyncId, states, displays, flags,
desiredPresentTime, uncacheBuffer, postTime,
privileged, hasListenerCallbacks, listenerCallbacks,
@@ -5526,7 +5539,7 @@
}
}
- RenderAreaFuture renderAreaFuture = promise::defer([=] {
+ RenderAreaFuture renderAreaFuture = ftl::defer([=] {
return DisplayRenderArea::create(displayWeak, args.sourceCrop, reqSize, dataspace,
args.useIdentityTransform, args.captureSecureLayers);
});
@@ -5560,7 +5573,7 @@
pickDataspaceFromColorMode(display->getCompositionDisplay()->getState().colorMode);
}
- RenderAreaFuture renderAreaFuture = promise::defer([=] {
+ RenderAreaFuture renderAreaFuture = ftl::defer([=] {
return DisplayRenderArea::create(displayWeak, Rect(), size, dataspace,
false /* useIdentityTransform */,
false /* captureSecureLayers */);
@@ -5664,7 +5677,7 @@
}
bool childrenOnly = args.childrenOnly;
- RenderAreaFuture renderAreaFuture = promise::defer([=]() -> std::unique_ptr<RenderArea> {
+ RenderAreaFuture renderAreaFuture = ftl::defer([=]() -> std::unique_ptr<RenderArea> {
return std::make_unique<LayerRenderArea>(*this, parent, crop, reqSize, dataspace,
childrenOnly, layerStackSpaceRect,
captureSecureLayers);
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index 2e4d1ce..542ba98 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -745,7 +745,8 @@
void commitTransaction() REQUIRES(mStateLock);
void commitOffscreenLayers();
bool transactionIsReadyToBeApplied(int64_t desiredPresentTime,
- const Vector<ComposerState>& states);
+ const Vector<ComposerState>& states,
+ bool updateTransactionCounters = false) REQUIRES(mStateLock);
uint32_t setDisplayStateLocked(const DisplayState& s) REQUIRES(mStateLock);
uint32_t addInputWindowCommands(const InputWindowCommands& inputWindowCommands)
REQUIRES(mStateLock);
diff --git a/services/surfaceflinger/tests/LayerTypeAndRenderTypeTransaction_test.cpp b/services/surfaceflinger/tests/LayerTypeAndRenderTypeTransaction_test.cpp
index c57ad43..782a364 100644
--- a/services/surfaceflinger/tests/LayerTypeAndRenderTypeTransaction_test.cpp
+++ b/services/surfaceflinger/tests/LayerTypeAndRenderTypeTransaction_test.cpp
@@ -377,6 +377,72 @@
40 /* tolerance */);
}
+TEST_P(LayerTypeAndRenderTypeTransactionTest, SetBackgroundBlurAffectedByParentAlpha) {
+ char value[PROPERTY_VALUE_MAX];
+ property_get("ro.surface_flinger.supports_background_blur", value, "0");
+ if (!atoi(value)) {
+ // This device doesn't support blurs, no-op.
+ return;
+ }
+
+ property_get("debug.renderengine.backend", value, "");
+ if (strcmp(value, "skiagl") != 0) {
+ // This device isn't using Skia render engine, no-op.
+ return;
+ }
+
+ sp<SurfaceControl> left;
+ sp<SurfaceControl> right;
+ sp<SurfaceControl> blur;
+ sp<SurfaceControl> blurParent;
+
+ const auto size = 32;
+ ASSERT_NO_FATAL_FAILURE(left = createLayer("Left", size, size));
+ ASSERT_NO_FATAL_FAILURE(fillLayerColor(left, Color::BLUE, size, size));
+ ASSERT_NO_FATAL_FAILURE(right = createLayer("Right", size, size));
+ ASSERT_NO_FATAL_FAILURE(fillLayerColor(right, Color::RED, size, size));
+
+ Transaction()
+ .setLayer(left, mLayerZBase + 1)
+ .setFrame(left, {0, 0, size, size})
+ .setLayer(right, mLayerZBase + 2)
+ .setPosition(right, size, 0)
+ .setFrame(right, {size, 0, size * 2, size})
+ .apply();
+
+ {
+ auto shot = getScreenCapture();
+ shot->expectColor(Rect(0, 0, size, size), Color::BLUE);
+ shot->expectColor(Rect(size, 0, size * 2, size), Color::RED);
+ }
+
+ ASSERT_NO_FATAL_FAILURE(blur = createLayer("BackgroundBlur", size * 2, size));
+ ASSERT_NO_FATAL_FAILURE(fillLayerColor(blur, Color::TRANSPARENT, size * 2, size));
+ ASSERT_NO_FATAL_FAILURE(blurParent = createLayer("BackgroundBlurParent", size * 2, size));
+ ASSERT_NO_FATAL_FAILURE(fillLayerColor(blurParent, Color::TRANSPARENT, size * 2, size));
+
+ Transaction()
+ .setLayer(blurParent, mLayerZBase + 3)
+ .setAlpha(blurParent, 0.5)
+ .setLayer(blur, mLayerZBase + 4)
+ .setBackgroundBlurRadius(blur, size) // set the blur radius to the size of one rect
+ .setFrame(blur, {0, 0, size * 2, size})
+ .reparent(blur, blurParent)
+ .apply();
+
+ {
+ auto shot = getScreenCapture();
+ // assert that outer sides of the red and blue rects are not blended with the other color;
+ // if the blur didn't take into account parent alpha, the outer sides would have traces of
+ // the other color
+ shot->expectColor(Rect(0, 0, size / 2, size), Color::BLUE);
+ shot->expectColor(Rect(size + size / 2, 0, size * 2, size), Color::RED);
+ // assert that middle line has blended red and blur color; adding a tolerance of 10 to
+ // account for future blur algorithm changes
+ shot->expectColor(Rect(size, 0, size + 1, size), {136, 0, 119, 255}, 10);
+ }
+}
+
TEST_P(LayerTypeAndRenderTypeTransactionTest, SetColorWithBuffer) {
sp<SurfaceControl> bufferLayer;
ASSERT_NO_FATAL_FAILURE(bufferLayer = createLayer("test", 32, 32));
diff --git a/services/surfaceflinger/tests/unittests/Android.bp b/services/surfaceflinger/tests/unittests/Android.bp
index a00e959..13c7c8b 100644
--- a/services/surfaceflinger/tests/unittests/Android.bp
+++ b/services/surfaceflinger/tests/unittests/Android.bp
@@ -51,7 +51,6 @@
"LayerHistoryTest.cpp",
"LayerMetadataTest.cpp",
"MessageQueueTest.cpp",
- "PromiseTest.cpp",
"SurfaceFlinger_CreateDisplayTest.cpp",
"SurfaceFlinger_DestroyDisplayTest.cpp",
"SurfaceFlinger_GetDisplayNativePrimariesTest.cpp",
diff --git a/services/surfaceflinger/tests/unittests/PromiseTest.cpp b/services/surfaceflinger/tests/unittests/PromiseTest.cpp
deleted file mode 100644
index e4dc1fe..0000000
--- a/services/surfaceflinger/tests/unittests/PromiseTest.cpp
+++ /dev/null
@@ -1,88 +0,0 @@
-/*
- * Copyright 2020 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.
- */
-
-#include <algorithm>
-#include <future>
-#include <string>
-#include <thread>
-#include <vector>
-
-#include <gtest/gtest.h>
-
-#include "Promise.h"
-
-namespace android {
-namespace {
-
-using Bytes = std::vector<uint8_t>;
-
-Bytes decrement(Bytes bytes) {
- std::transform(bytes.begin(), bytes.end(), bytes.begin(), [](auto b) { return b - 1; });
- return bytes;
-}
-
-} // namespace
-
-TEST(PromiseTest, yield) {
- EXPECT_EQ(42, promise::yield(42).get());
-
- auto ptr = std::make_unique<char>('!');
- auto future = promise::yield(std::move(ptr));
- EXPECT_EQ('!', *future.get());
-}
-
-TEST(PromiseTest, chain) {
- std::packaged_task<const char*()> fetchString([] { return "ifmmp-"; });
-
- std::packaged_task<Bytes(std::string)> appendString([](std::string str) {
- str += "!xpsme";
- return Bytes{str.begin(), str.end()};
- });
-
- std::packaged_task<std::future<Bytes>(Bytes)> decrementBytes(
- [](Bytes bytes) { return promise::defer(decrement, std::move(bytes)); });
-
- auto fetch = fetchString.get_future();
- std::thread fetchThread(std::move(fetchString));
-
- std::thread appendThread, decrementThread;
-
- EXPECT_EQ("hello, world",
- promise::chain(std::move(fetch))
- .then([](const char* str) { return std::string(str); })
- .then([&](std::string str) {
- auto append = appendString.get_future();
- appendThread = std::thread(std::move(appendString), std::move(str));
- return append;
- })
- .then([&](Bytes bytes) {
- auto decrement = decrementBytes.get_future();
- decrementThread = std::thread(std::move(decrementBytes),
- std::move(bytes));
- return decrement;
- })
- .then([](std::future<Bytes> bytes) { return bytes; })
- .then([](const Bytes& bytes) {
- return std::string(bytes.begin(), bytes.end());
- })
- .get());
-
- fetchThread.join();
- appendThread.join();
- decrementThread.join();
-}
-
-} // namespace android