17a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski/* 27a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * Copyright (C) 2016 The Android Open Source Project 37a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 47a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 57a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * you may not use this file except in compliance with the License. 67a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * You may obtain a copy of the License at 77a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 87a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 97a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 107a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * Unless required by applicable law or agreed to in writing, software 117a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 127a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * See the License for the specific language governing permissions and 147a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * limitations under the License. 157a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski */ 167a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 177a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski#ifndef ANDROIDFW_ATTRIBUTE_FINDER_H 187a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski#define ANDROIDFW_ATTRIBUTE_FINDER_H 197a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 207a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski#include <utils/KeyedVector.h> 217a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 227a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski#include <stdint.h> 237a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 247a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskinamespace android { 257a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 267a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskistatic inline uint32_t get_package(uint32_t attr) { return attr >> 24; } 277a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 287a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski/** 297a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * A helper class to search linearly for the requested 307a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * attribute, maintaining it's position and optimizing for 317a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * the case that subsequent searches will involve an attribute with 327a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * a higher attribute ID. 337a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 347a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * In the case that a subsequent attribute has a different package ID, 357a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * its resource ID may not be larger than the preceding search, so 367a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * back tracking is supported for this case. This 377a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * back tracking requirement is mainly for shared library 387a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * resources, whose package IDs get assigned at runtime 397a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * and thus attributes from a shared library may 407a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * be out of order. 417a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 427a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * We make two assumptions about the order of attributes: 437a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 1) The input has the same sorting rules applied to it as 447a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * the attribute data contained by this class. 457a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 2) Attributes are grouped by package ID. 467a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 3) Among attributes with the same package ID, the attributes are 477a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * sorted by increasing resource ID. 487a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 497a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003 507a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * 517a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * The total order of attributes (including package ID) can not be linear 527a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * as shared libraries get assigned dynamic package IDs at runtime, which 537a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski * may break the sort order established at build time. 547a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski */ 557a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskitemplate <typename Derived, typename Iterator> 567a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskiclass BackTrackingAttributeFinder { 577a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski public: 587a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end); 597a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 607a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator Find(uint32_t attr); 61bebfcc46a249a70af04bc18490a897888a142fb8Adam Lesinski inline Iterator end(); 627a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 637a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski private: 647a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski void JumpToClosestAttribute(uint32_t package_id); 657a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski void MarkCurrentPackageId(uint32_t package_id); 667a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 677a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski bool first_time_; 687a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator begin_; 697a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator end_; 707a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator current_; 717a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator largest_; 727a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski uint32_t last_package_id_; 737a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski uint32_t current_attr_; 747a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 757a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // Package offsets (best-case, fast look-up). 767a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator framework_start_; 777a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski Iterator app_start_; 787a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 797a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // Worst case, we have shared-library resources. 807a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski KeyedVector<uint32_t, Iterator> package_offsets_; 817a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski}; 827a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 837a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskitemplate <typename Derived, typename Iterator> 847a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskiinline BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder( 857a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const Iterator& begin, const Iterator& end) 867a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski : first_time_(true), 877a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski begin_(begin), 887a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski end_(end), 897a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_(begin), 907a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski largest_(begin), 917a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski last_package_id_(0), 927a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_attr_(0), 937a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski framework_start_(end), 947a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski app_start_(end) {} 957a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 967a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskitemplate <typename Derived, typename Iterator> 977a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskivoid BackTrackingAttributeFinder<Derived, Iterator>::JumpToClosestAttribute( 987a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t package_id) { 997a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski switch (package_id) { 1007a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski case 0x01u: 1017a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_ = framework_start_; 1027a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1037a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski case 0x7fu: 1047a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_ = app_start_; 1057a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1067a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski default: { 1077a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski ssize_t idx = package_offsets_.indexOfKey(package_id); 1087a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (idx >= 0) { 1097a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // We have seen this package ID before, so jump to the first 1107a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // attribute with this package ID. 1117a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_ = package_offsets_[idx]; 1127a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } else { 1137a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_ = end_; 1147a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1157a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1167a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1177a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1187a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1197a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // We have never seen this package ID yet, so jump to the 1207a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // latest/largest index we have processed so far. 1217a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (current_ == end_) { 1227a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_ = largest_; 1237a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1247a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1257a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (current_ != end_) { 1267a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_); 1277a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1287a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski} 1297a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1307a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskitemplate <typename Derived, typename Iterator> 1317a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskivoid BackTrackingAttributeFinder<Derived, Iterator>::MarkCurrentPackageId( 1327a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t package_id) { 1337a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski switch (package_id) { 1347a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski case 0x01u: 1357a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski framework_start_ = current_; 1367a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1377a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski case 0x7fu: 1387a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski app_start_ = current_; 1397a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1407a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski default: 1417a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski package_offsets_.add(package_id, current_); 1427a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1437a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1447a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski} 1457a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1467a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinskitemplate <typename Derived, typename Iterator> 1477a37b74d37ff79e805c9e97d977e07bfec753c5aAdam LesinskiIterator BackTrackingAttributeFinder<Derived, Iterator>::Find(uint32_t attr) { 1487a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (!(begin_ < end_)) { 1497a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski return end_; 1507a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1517a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1527a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (first_time_) { 1537a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // One-time initialization. We do this here instead of the constructor 1547a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // because the derived class we access in getAttribute() may not be 1557a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // fully constructed. 1567a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski first_time_ = false; 1577a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_attr_ = static_cast<const Derived*>(this)->GetAttribute(begin_); 1587a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski last_package_id_ = get_package(current_attr_); 1597a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski MarkCurrentPackageId(last_package_id_); 1607a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1617a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1627a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // Looking for the needle (attribute we're looking for) 1637a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // in the haystack (the attributes we're searching through) 1647a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t needle_package_id = get_package(attr); 1657a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (last_package_id_ != needle_package_id) { 1667a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski JumpToClosestAttribute(needle_package_id); 1677a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski last_package_id_ = needle_package_id; 1687a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1697a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1707a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // Walk through the xml attributes looking for the requested attribute. 1717a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski while (current_ != end_) { 1727a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t haystack_package_id = get_package(current_attr_); 1737a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (needle_package_id == haystack_package_id && attr < current_attr_) { 1747a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // The attribute we are looking was not found. 1757a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski break; 1767a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1777a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t prev_attr = current_attr_; 1787a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1797a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // Move to the next attribute in the XML. 1807a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski ++current_; 1817a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (current_ != end_) { 1827a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_); 1837a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski const uint32_t new_haystack_package_id = get_package(current_attr_); 1847a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (haystack_package_id != new_haystack_package_id) { 1857a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // We've moved to the next group of attributes 1867a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // with a new package ID, so we should record 1877a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // the offset of this new package ID. 1887a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski MarkCurrentPackageId(new_haystack_package_id); 1897a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1907a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1917a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1927a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (current_ > largest_) { 1937a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // We've moved past the latest attribute we've seen. 1947a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski largest_ = current_; 1957a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 1967a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 1977a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski if (attr == prev_attr) { 1987a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski // We found the attribute we were looking for. 1997a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski return current_ - 1; 2007a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 2017a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski } 2027a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski return end_; 2037a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski} 2047a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 205bebfcc46a249a70af04bc18490a897888a142fb8Adam Lesinskitemplate <typename Derived, typename Iterator> 206bebfcc46a249a70af04bc18490a897888a142fb8Adam LesinskiIterator BackTrackingAttributeFinder<Derived, Iterator>::end() { 207bebfcc46a249a70af04bc18490a897888a142fb8Adam Lesinski return end_; 208bebfcc46a249a70af04bc18490a897888a142fb8Adam Lesinski} 209bebfcc46a249a70af04bc18490a897888a142fb8Adam Lesinski 2107a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski} // namespace android 2117a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski 2127a37b74d37ff79e805c9e97d977e07bfec753c5aAdam Lesinski#endif // ANDROIDFW_ATTRIBUTE_FINDER_H 213