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
get_package(uint32_t attr)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>
BackTrackingAttributeFinder(const Iterator & begin,const Iterator & end)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>
JumpToClosestAttribute(const uint32_t package_id)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>
MarkCurrentPackageId(const uint32_t package_id)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>
Find(uint32_t attr)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