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 inline Iterator end();
62
63 private:
64 void JumpToClosestAttribute(uint32_t package_id);
65 void MarkCurrentPackageId(uint32_t package_id);
66
67 bool first_time_;
68 Iterator begin_;
69 Iterator end_;
70 Iterator current_;
71 Iterator largest_;
72 uint32_t last_package_id_;
73 uint32_t current_attr_;
74
75 // Package offsets (best-case, fast look-up).
76 Iterator framework_start_;
77 Iterator app_start_;
78
79 // Worst case, we have shared-library resources.
80 KeyedVector<uint32_t, Iterator> package_offsets_;
81 };
82
83 template <typename Derived, typename Iterator>
BackTrackingAttributeFinder(const Iterator & begin,const Iterator & end)84 inline BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(
85 const Iterator& begin, const Iterator& end)
86 : first_time_(true),
87 begin_(begin),
88 end_(end),
89 current_(begin),
90 largest_(begin),
91 last_package_id_(0),
92 current_attr_(0),
93 framework_start_(end),
94 app_start_(end) {}
95
96 template <typename Derived, typename Iterator>
JumpToClosestAttribute(const uint32_t package_id)97 void BackTrackingAttributeFinder<Derived, Iterator>::JumpToClosestAttribute(
98 const uint32_t package_id) {
99 switch (package_id) {
100 case 0x01u:
101 current_ = framework_start_;
102 break;
103 case 0x7fu:
104 current_ = app_start_;
105 break;
106 default: {
107 ssize_t idx = package_offsets_.indexOfKey(package_id);
108 if (idx >= 0) {
109 // We have seen this package ID before, so jump to the first
110 // attribute with this package ID.
111 current_ = package_offsets_[idx];
112 } else {
113 current_ = end_;
114 }
115 break;
116 }
117 }
118
119 // We have never seen this package ID yet, so jump to the
120 // latest/largest index we have processed so far.
121 if (current_ == end_) {
122 current_ = largest_;
123 }
124
125 if (current_ != end_) {
126 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_);
127 }
128 }
129
130 template <typename Derived, typename Iterator>
MarkCurrentPackageId(const uint32_t package_id)131 void BackTrackingAttributeFinder<Derived, Iterator>::MarkCurrentPackageId(
132 const uint32_t package_id) {
133 switch (package_id) {
134 case 0x01u:
135 framework_start_ = current_;
136 break;
137 case 0x7fu:
138 app_start_ = current_;
139 break;
140 default:
141 package_offsets_.add(package_id, current_);
142 break;
143 }
144 }
145
146 template <typename Derived, typename Iterator>
Find(uint32_t attr)147 Iterator BackTrackingAttributeFinder<Derived, Iterator>::Find(uint32_t attr) {
148 if (!(begin_ < end_)) {
149 return end_;
150 }
151
152 if (first_time_) {
153 // One-time initialization. We do this here instead of the constructor
154 // because the derived class we access in getAttribute() may not be
155 // fully constructed.
156 first_time_ = false;
157 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(begin_);
158 last_package_id_ = get_package(current_attr_);
159 MarkCurrentPackageId(last_package_id_);
160 }
161
162 // Looking for the needle (attribute we're looking for)
163 // in the haystack (the attributes we're searching through)
164 const uint32_t needle_package_id = get_package(attr);
165 if (last_package_id_ != needle_package_id) {
166 JumpToClosestAttribute(needle_package_id);
167 last_package_id_ = needle_package_id;
168 }
169
170 // Walk through the xml attributes looking for the requested attribute.
171 while (current_ != end_) {
172 const uint32_t haystack_package_id = get_package(current_attr_);
173 if (needle_package_id == haystack_package_id && attr < current_attr_) {
174 // The attribute we are looking was not found.
175 break;
176 }
177 const uint32_t prev_attr = current_attr_;
178
179 // Move to the next attribute in the XML.
180 ++current_;
181 if (current_ != end_) {
182 current_attr_ = static_cast<const Derived*>(this)->GetAttribute(current_);
183 const uint32_t new_haystack_package_id = get_package(current_attr_);
184 if (haystack_package_id != new_haystack_package_id) {
185 // We've moved to the next group of attributes
186 // with a new package ID, so we should record
187 // the offset of this new package ID.
188 MarkCurrentPackageId(new_haystack_package_id);
189 }
190 }
191
192 if (current_ > largest_) {
193 // We've moved past the latest attribute we've seen.
194 largest_ = current_;
195 }
196
197 if (attr == prev_attr) {
198 // We found the attribute we were looking for.
199 return current_ - 1;
200 }
201 }
202 return end_;
203 }
204
205 template <typename Derived, typename Iterator>
end()206 Iterator BackTrackingAttributeFinder<Derived, Iterator>::end() {
207 return end_;
208 }
209
210 } // namespace android
211
212 #endif // ANDROIDFW_ATTRIBUTE_FINDER_H
213