AttributeFinder.h revision 4c67a475a334e4f65238d439a3339195e03c03be 
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
24namespace android {
25
26static 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 */
55template <typename Derived, typename Iterator>
56class 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
82template <typename Derived, typename Iterator>
83inline 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
95template <typename Derived, typename Iterator>
96void 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
129template <typename Derived, typename Iterator>
130void 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
145template <typename Derived, typename Iterator>
146Iterator 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