1 /* 2 * Copyright (C) 2016 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ANDROIDFW_ATTRIBUTE_FINDER_H 18 #define ANDROIDFW_ATTRIBUTE_FINDER_H 19 20 #include <utils/KeyedVector.h> 21 22 #include <stdint.h> 23 24 namespace android { 25 26 static inline uint32_t get_package(uint32_t attr) { return attr >> 24; } 27 28 /** 29 * A helper class to search linearly for the requested 30 * attribute, maintaining it's position and optimizing for 31 * the case that subsequent searches will involve an attribute with 32 * a higher attribute ID. 33 * 34 * In the case that a subsequent attribute has a different package ID, 35 * its resource ID may not be larger than the preceding search, so 36 * back tracking is supported for this case. This 37 * back tracking requirement is mainly for shared library 38 * resources, whose package IDs get assigned at runtime 39 * and thus attributes from a shared library may 40 * be out of order. 41 * 42 * We make two assumptions about the order of attributes: 43 * 1) The input has the same sorting rules applied to it as 44 * the attribute data contained by this class. 45 * 2) Attributes are grouped by package ID. 46 * 3) Among attributes with the same package ID, the attributes are 47 * sorted by increasing resource ID. 48 * 49 * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003 50 * 51 * The total order of attributes (including package ID) can not be linear 52 * as shared libraries get assigned dynamic package IDs at runtime, which 53 * may break the sort order established at build time. 54 */ 55 template <typename Derived, typename Iterator> 56 class BackTrackingAttributeFinder { 57 public: 58 BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end); 59 60 Iterator Find(uint32_t attr); 61 62 private: 63 void JumpToClosestAttribute(uint32_t package_id); 64 void MarkCurrentPackageId(uint32_t package_id); 65 66 bool first_time_; 67 Iterator begin_; 68 Iterator end_; 69 Iterator current_; 70 Iterator largest_; 71 uint32_t last_package_id_; 72 uint32_t current_attr_; 73 74 // Package offsets (best-case, fast look-up). 75 Iterator framework_start_; 76 Iterator app_start_; 77 78 // Worst case, we have shared-library resources. 79 KeyedVector<uint32_t, Iterator> package_offsets_; 80 }; 81 82 template <typename Derived, typename Iterator> 83 inline BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder( 84 const Iterator& begin, const Iterator& end) 85 : first_time_(true), 86 begin_(begin), 87 end_(end), 88 current_(begin), 89 largest_(begin), 90 last_package_id_(0), 91 current_attr_(0), 92 framework_start_(end), 93 app_start_(end) {} 94 95 template <typename Derived, typename Iterator> 96 void BackTrackingAttributeFinder<Derived, Iterator>::JumpToClosestAttribute( 97 const uint32_t package_id) { 98 switch (package_id) { 99 case 0x01u: 100 current_ = framework_start_; 101 break; 102 case 0x7fu: 103 current_ = app_start_; 104 break; 105 default: { 106 ssize_t idx = package_offsets_.indexOfKey(package_id); 107 if (idx >= 0) { 108 // We have seen this package ID before, so jump to the first 109 // attribute with this package ID. 110 current_ = package_offsets_[idx]; 111 } else { 112 current_ = end_; 113 } 114 break; 115 } 116 } 117 118 // We have never seen this package ID yet, so jump to the 119 // latest/largest index we have processed so far. 120 if (current_ == end_) { 121 current_ = largest_; 122 } 123 124 if (current_ != end_) { 125 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_); 126 } 127 } 128 129 template <typename Derived, typename Iterator> 130 void BackTrackingAttributeFinder<Derived, Iterator>::MarkCurrentPackageId( 131 const uint32_t package_id) { 132 switch (package_id) { 133 case 0x01u: 134 framework_start_ = current_; 135 break; 136 case 0x7fu: 137 app_start_ = current_; 138 break; 139 default: 140 package_offsets_.add(package_id, current_); 141 break; 142 } 143 } 144 145 template <typename Derived, typename Iterator> 146 Iterator BackTrackingAttributeFinder<Derived, Iterator>::Find(uint32_t attr) { 147 if (!(begin_ < end_)) { 148 return end_; 149 } 150 151 if (first_time_) { 152 // One-time initialization. We do this here instead of the constructor 153 // because the derived class we access in getAttribute() may not be 154 // fully constructed. 155 first_time_ = false; 156 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(begin_); 157 last_package_id_ = get_package(current_attr_); 158 MarkCurrentPackageId(last_package_id_); 159 } 160 161 // Looking for the needle (attribute we're looking for) 162 // in the haystack (the attributes we're searching through) 163 const uint32_t needle_package_id = get_package(attr); 164 if (last_package_id_ != needle_package_id) { 165 JumpToClosestAttribute(needle_package_id); 166 last_package_id_ = needle_package_id; 167 } 168 169 // Walk through the xml attributes looking for the requested attribute. 170 while (current_ != end_) { 171 const uint32_t haystack_package_id = get_package(current_attr_); 172 if (needle_package_id == haystack_package_id && attr < current_attr_) { 173 // The attribute we are looking was not found. 174 break; 175 } 176 const uint32_t prev_attr = current_attr_; 177 178 // Move to the next attribute in the XML. 179 ++current_; 180 if (current_ != end_) { 181 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_); 182 const uint32_t new_haystack_package_id = get_package(current_attr_); 183 if (haystack_package_id != new_haystack_package_id) { 184 // We've moved to the next group of attributes 185 // with a new package ID, so we should record 186 // the offset of this new package ID. 187 MarkCurrentPackageId(new_haystack_package_id); 188 } 189 } 190 191 if (current_ > largest_) { 192 // We've moved past the latest attribute we've seen. 193 largest_ = current_; 194 } 195 196 if (attr == prev_attr) { 197 // We found the attribute we were looking for. 198 return current_ - 1; 199 } 200 } 201 return end_; 202 } 203 204 } // namespace android 205 206 #endif // ANDROIDFW_ATTRIBUTE_FINDER_H 207
