diff options
| -rw-r--r-- | libs/androidfw/Android.bp | 1 | ||||
| -rw-r--r-- | libs/androidfw/AssetManager2.cpp | 86 | ||||
| -rw-r--r-- | libs/androidfw/include/androidfw/CombinedIterator.h | 176 | ||||
| -rw-r--r-- | libs/androidfw/tests/CombinedIterator_test.cpp | 98 |
4 files changed, 342 insertions, 19 deletions
diff --git a/libs/androidfw/Android.bp b/libs/androidfw/Android.bp index 260f3c148841..2fff4f5e9f7c 100644 --- a/libs/androidfw/Android.bp +++ b/libs/androidfw/Android.bp @@ -212,6 +212,7 @@ cc_test { "tests/AttributeResolution_test.cpp", "tests/BigBuffer_test.cpp", "tests/ByteBucketArray_test.cpp", + "tests/CombinedIterator_test.cpp", "tests/Config_test.cpp", "tests/ConfigDescription_test.cpp", "tests/ConfigLocale_test.cpp", diff --git a/libs/androidfw/AssetManager2.cpp b/libs/androidfw/AssetManager2.cpp index 46f636e2ae7f..822a387351e3 100644 --- a/libs/androidfw/AssetManager2.cpp +++ b/libs/androidfw/AssetManager2.cpp @@ -23,9 +23,11 @@ #include <map> #include <set> #include <span> +#include <utility> #include "android-base/logging.h" #include "android-base/stringprintf.h" +#include "androidfw/CombinedIterator.h" #include "androidfw/ResourceTypes.h" #include "androidfw/ResourceUtils.h" #include "androidfw/Util.h" @@ -1622,6 +1624,12 @@ Theme::Theme(AssetManager2* asset_manager) : asset_manager_(asset_manager) { Theme::~Theme() = default; +static bool IsUndefined(const Res_value& value) { + // DATA_NULL_EMPTY (@empty) is a valid resource value and DATA_NULL_UNDEFINED represents + // an absence of a valid value. + return value.dataType == Res_value::TYPE_NULL && value.data != Res_value::DATA_NULL_EMPTY; +} + base::expected<std::monostate, NullOrIOError> Theme::ApplyStyle(uint32_t resid, bool force) { ATRACE_NAME("Theme::ApplyStyle"); @@ -1633,39 +1641,76 @@ base::expected<std::monostate, NullOrIOError> Theme::ApplyStyle(uint32_t resid, // Merge the flags from this style. type_spec_flags_ |= (*bag)->type_spec_flags; + // + // This function is the most expensive part of applying an frro to the existing app resources, + // and needs to be as efficient as possible. + // The data structure we're working with is two parallel sorted arrays of keys (resource IDs) + // and entries (resource value + some attributes). + // The styles get applied in sequence, starting with an empty set of attributes. Each style + // contains its values for the theme attributes, and gets applied in either normal or forced way: + // - normal way never overrides the existing attribute, so only unique style attributes are added + // - forced way overrides anything for that attribute, and if it's undefined it removes the + // previous value completely + // + // Style attributes come in a Bag data type - a sorted array of attributes with their values. This + // means we don't need to re-sort the attributes ever, and instead: + // - for an already existing attribute just skip it or apply the forced value + // - if the forced value is undefined, mark it undefined as well to get rid of it later + // - for a new attribute append it to the array, forming a new sorted section of new attributes + // past the end of the original ones (ignore undefined ones here) + // - inplace merge two sorted sections to form a single sorted array again. + // - run the last pass to remove all undefined elements + // + // Using this algorithm performs better than a repeated binary search + insert in the middle, + // as that keeps shifting the tail end of the arrays and wasting CPU cycles in memcpy(). + // + const auto starting_size = keys_.size(); + if (starting_size == 0) { + keys_.reserve((*bag)->entry_count); + entries_.reserve((*bag)->entry_count); + } + bool wrote_undefined = false; for (auto it = begin(*bag); it != end(*bag); ++it) { const uint32_t attr_res_id = it->key; - // If the resource ID passed in is not a style, the key can be some other identifier that is not // a resource ID. We should fail fast instead of operating with strange resource IDs. if (!is_valid_resid(attr_res_id)) { return base::unexpected(std::nullopt); } - - // DATA_NULL_EMPTY (@empty) is a valid resource value and DATA_NULL_UNDEFINED represents - // an absence of a valid value. - bool is_undefined = it->value.dataType == Res_value::TYPE_NULL && - it->value.data != Res_value::DATA_NULL_EMPTY; + const bool is_undefined = IsUndefined(it->value); if (!force && is_undefined) { continue; } - - const auto key_it = std::lower_bound(keys_.begin(), keys_.end(), attr_res_id); - const auto entry_it = entries_.begin() + (key_it - keys_.begin()); - if (key_it != keys_.end() && *key_it == attr_res_id) { - if (is_undefined) { - // DATA_NULL_UNDEFINED clears the value of the attribute in the theme only when `force` is - // true. - keys_.erase(key_it); - entries_.erase(entry_it); - } else if (force) { + const auto key_it = std::lower_bound(keys_.begin(), keys_.begin() + starting_size, attr_res_id); + if (key_it != keys_.begin() + starting_size && *key_it == attr_res_id) { + const auto entry_it = entries_.begin() + (key_it - keys_.begin()); + if (force || IsUndefined(entry_it->value)) { *entry_it = Entry{it->cookie, (*bag)->type_spec_flags, it->value}; + wrote_undefined |= is_undefined; } - } else { - keys_.insert(key_it, attr_res_id); - entries_.insert(entry_it, Entry{it->cookie, (*bag)->type_spec_flags, it->value}); + } else if (!is_undefined) { + keys_.emplace_back(attr_res_id); + entries_.emplace_back(it->cookie, (*bag)->type_spec_flags, it->value); } } + + if (starting_size && keys_.size() != starting_size) { + std::inplace_merge( + CombinedIterator(keys_.begin(), entries_.begin()), + CombinedIterator(keys_.begin() + starting_size, entries_.begin() + starting_size), + CombinedIterator(keys_.end(), entries_.end())); + } + if (wrote_undefined) { + auto new_end = std::remove_if(CombinedIterator(keys_.begin(), entries_.begin()), + CombinedIterator(keys_.end(), entries_.end()), + [](const auto& pair) { return IsUndefined(pair.second.value); }); + keys_.erase(new_end.it1, keys_.end()); + entries_.erase(new_end.it2, entries_.end()); + } + if (android::base::kEnableDChecks && !std::is_sorted(keys_.begin(), keys_.end())) { + ALOGW("Bag %u was unsorted in the apk?", unsigned(resid)); + return base::unexpected(std::nullopt); + } return {}; } @@ -1691,6 +1736,9 @@ std::optional<AssetManager2::SelectedValue> Theme::GetAttribute(uint32_t resid) return std::nullopt; } const auto entry_it = entries_.begin() + (key_it - keys_.begin()); + if (IsUndefined(entry_it->value)) { + return std::nullopt; + } type_spec_flags |= entry_it->type_spec_flags; if (entry_it->value.dataType == Res_value::TYPE_ATTRIBUTE) { resid = entry_it->value.data; diff --git a/libs/androidfw/include/androidfw/CombinedIterator.h b/libs/androidfw/include/androidfw/CombinedIterator.h new file mode 100644 index 000000000000..4ff6a7d7e6c9 --- /dev/null +++ b/libs/androidfw/include/androidfw/CombinedIterator.h @@ -0,0 +1,176 @@ +/* + * Copyright (C) 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#pragma once + +#include <compare> +#include <iterator> +#include <utility> + +namespace android { + +namespace detail { +// A few useful aliases to not repeat them everywhere +template <class It1, class It2> +using Value = std::pair<typename std::iterator_traits<It1>::value_type, + typename std::iterator_traits<It2>::value_type>; + +template <class It1, class It2> +using BaseRefPair = std::pair<typename std::iterator_traits<It1>::reference, + typename std::iterator_traits<It2>::reference>; + +template <class It1, class It2> +struct RefPair : BaseRefPair<It1, It2> { + using Base = BaseRefPair<It1, It2>; + using Value = detail::Value<It1, It2>; + + RefPair(It1 it1, It2 it2) : Base(*it1, *it2) { + } + + RefPair& operator=(const Value& v) { + this->first = v.first; + this->second = v.second; + return *this; + } + operator Value() const { + return Value(this->first, this->second); + } + bool operator==(const RefPair& other) { + return this->first == other.first; + } + bool operator==(const Value& other) { + return this->first == other.first; + } + std::strong_ordering operator<=>(const RefPair& other) const { + return this->first <=> other.first; + } + std::strong_ordering operator<=>(const Value& other) const { + return this->first <=> other.first; + } + friend void swap(RefPair& l, RefPair& r) { + using std::swap; + swap(l.first, r.first); + swap(l.second, r.second); + } +}; + +template <class It1, class It2> +struct RefPairPtr { + RefPair<It1, It2> value; + + RefPair<It1, It2>* operator->() const { + return &value; + } +}; +} // namespace detail + +// +// CombinedIterator - a class to combine two iterators to process them as a single iterator to a +// pair of values. Useful for processing a data structure of "struct of arrays", replacing +// array of structs for cache locality. +// +// The value type is a pair of copies of the values of each iterator, and the reference is a +// pair of references to the corresponding values. Comparison only compares the first element, +// making it most useful for using on data like (vector<Key>, vector<Value>) for binary searching, +// sorting both together and so on. +// +// The class is designed for handling arrays, so it requires random access iterators as an input. +// + +template <class It1, class It2> +requires std::random_access_iterator<It1> && std::random_access_iterator<It2> +struct CombinedIterator { + typedef detail::Value<It1, It2> value_type; + typedef detail::RefPair<It1, It2> reference; + typedef std::ptrdiff_t difference_type; + typedef detail::RefPairPtr<It1, It2> pointer; + typedef std::random_access_iterator_tag iterator_category; + + CombinedIterator(It1 it1 = {}, It2 it2 = {}) : it1(it1), it2(it2) { + } + + bool operator<(const CombinedIterator& other) const { + return it1 < other.it1; + } + bool operator<=(const CombinedIterator& other) const { + return it1 <= other.it1; + } + bool operator>(const CombinedIterator& other) const { + return it1 > other.it1; + } + bool operator>=(const CombinedIterator& other) const { + return it1 >= other.it1; + } + bool operator==(const CombinedIterator& other) const { + return it1 == other.it1; + } + pointer operator->() const { + return pointer{{it1, it2}}; + } + reference operator*() const { + return {it1, it2}; + } + reference operator[](difference_type n) const { + return {it1 + n, it2 + n}; + } + + CombinedIterator& operator++() { + ++it1; + ++it2; + return *this; + } + CombinedIterator operator++(int) { + const auto res = *this; + ++*this; + return res; + } + CombinedIterator& operator--() { + --it1; + --it2; + return *this; + } + CombinedIterator operator--(int) { + const auto res = *this; + --*this; + return res; + } + CombinedIterator& operator+=(difference_type n) { + it1 += n; + it2 += n; + return *this; + } + CombinedIterator operator+(difference_type n) const { + CombinedIterator res = *this; + return res += n; + } + + CombinedIterator& operator-=(difference_type n) { + it1 -= n; + it2 -= n; + return *this; + } + CombinedIterator operator-(difference_type n) const { + CombinedIterator res = *this; + return res -= n; + } + difference_type operator-(const CombinedIterator& other) { + return it1 - other.it1; + } + + It1 it1; + It2 it2; +}; + +} // namespace android diff --git a/libs/androidfw/tests/CombinedIterator_test.cpp b/libs/androidfw/tests/CombinedIterator_test.cpp new file mode 100644 index 000000000000..c1228f34625f --- /dev/null +++ b/libs/androidfw/tests/CombinedIterator_test.cpp @@ -0,0 +1,98 @@ +/* + * Copyright (C) 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "androidfw/CombinedIterator.h" + +#include <algorithm> +#include <string> +#include <strstream> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" + +namespace android { + +template <class Coll> +std::string toString(const Coll& coll) { + std::stringstream res; + res << "(" << std::size(coll) << ")"; + if (std::size(coll)) { + res << "{" << coll[0]; + for (int i = 1; i != std::size(coll); ++i) { + res << "," << coll[i]; + } + res << "}"; + } + return res.str(); +} + +template <class Coll> +void AssertCollectionEq(const Coll& first, const Coll& second) { + ASSERT_EQ(std::size(first), std::size(second)) + << "first: " << toString(first) << ", second: " << toString(second); + for (int i = 0; i != std::size(first); ++i) { + ASSERT_EQ(first[i], second[i]) + << "index: " << i << " first: " << toString(first) << ", second: " << toString(second); + } +} + +TEST(CombinedIteratorTest, Sorting) { + std::vector<int> v1 = {2, 1, 3, 4, 0}; + std::vector<int> v2 = {20, 10, 30, 40, 0}; + + std::sort(CombinedIterator(v1.begin(), v2.begin()), CombinedIterator(v1.end(), v2.end())); + + ASSERT_EQ(v1.size(), v2.size()); + ASSERT_TRUE(std::is_sorted(v1.begin(), v1.end())); + ASSERT_TRUE(std::is_sorted(v2.begin(), v2.end())); + AssertCollectionEq(v1, {0, 1, 2, 3, 4}); + AssertCollectionEq(v2, {0, 10, 20, 30, 40}); +} + +TEST(CombinedIteratorTest, Removing) { + std::vector<int> v1 = {1, 2, 3, 4, 5, 5, 5, 6}; + std::vector<int> v2 = {10, 20, 30, 40, 50, 50, 50, 60}; + + auto newEnd = + std::remove_if(CombinedIterator(v1.begin(), v2.begin()), CombinedIterator(v1.end(), v2.end()), + [](auto&& pair) { return pair.first >= 3 && pair.first <= 5; }); + + ASSERT_EQ(newEnd.it1, v1.begin() + 3); + ASSERT_EQ(newEnd.it2, v2.begin() + 3); + + v1.erase(newEnd.it1, v1.end()); + AssertCollectionEq(v1, {1, 2, 6}); + v2.erase(newEnd.it2, v2.end()); + AssertCollectionEq(v2, {10, 20, 60}); +} + +TEST(CombinedIteratorTest, InplaceMerge) { + std::vector<int> v1 = {1, 3, 4, 7, 2, 5, 6}; + std::vector<int> v2 = {10, 30, 40, 70, 20, 50, 60}; + + std::inplace_merge(CombinedIterator(v1.begin(), v2.begin()), + CombinedIterator(v1.begin() + 4, v2.begin() + 4), + CombinedIterator(v1.end(), v2.end())); + ASSERT_TRUE(std::is_sorted(v1.begin(), v1.end())); + ASSERT_TRUE(std::is_sorted(v2.begin(), v2.end())); + + AssertCollectionEq(v1, {1, 2, 3, 4, 5, 6, 7}); + AssertCollectionEq(v2, {10, 20, 30, 40, 50, 60, 70}); +} + +} // namespace android |