1 /*
2  * Copyright (C) 2014 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 H_ATTRIBUTE_FINDER
18 #define H_ATTRIBUTE_FINDER
19 
20 #include <stdint.h>
21 #include <utils/KeyedVector.h>
22 
23 namespace android {
24 
getPackage(uint32_t attr)25 static inline uint32_t getPackage(uint32_t attr) {
26     return attr >> 24;
27 }
28 
29 /**
30  * A helper class to search linearly for the requested
31  * attribute, maintaining it's position and optimizing for
32  * the case that subsequent searches will involve an attribute with
33  * a higher attribute ID.
34  *
35  * In the case that a subsequent attribute has a different package ID,
36  * its resource ID may not be larger than the preceding search, so
37  * back tracking is supported for this case. This
38  * back tracking requirement is mainly for shared library
39  * resources, whose package IDs get assigned at runtime
40  * and thus attributes from a shared library may
41  * be out of order.
42  *
43  * We make two assumptions about the order of attributes:
44  * 1) The input has the same sorting rules applied to it as
45  *    the attribute data contained by this class.
46  * 2) Attributes are grouped by package ID.
47  * 3) Among attributes with the same package ID, the attributes are
48  *    sorted by increasing resource ID.
49  *
50  * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003
51  *
52  * The total order of attributes (including package ID) can not be linear
53  * as shared libraries get assigned dynamic package IDs at runtime, which
54  * may break the sort order established at build time.
55  */
56 template <typename Derived, typename Iterator>
57 class BackTrackingAttributeFinder {
58 public:
59     BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
60 
61     Iterator find(uint32_t attr);
62 
63 private:
64     void jumpToClosestAttribute(uint32_t packageId);
65     void markCurrentPackageId(uint32_t packageId);
66 
67     bool mFirstTime;
68     Iterator mBegin;
69     Iterator mEnd;
70     Iterator mCurrent;
71     Iterator mLargest;
72     uint32_t mLastPackageId;
73     uint32_t mCurrentAttr;
74 
75     // Package Offsets (best-case, fast look-up).
76     Iterator mFrameworkStart;
77     Iterator mAppStart;
78 
79     // Worst case, we have shared-library resources.
80     KeyedVector<uint32_t, Iterator> mPackageOffsets;
81 };
82 
83 template <typename Derived, typename Iterator> inline
BackTrackingAttributeFinder(const Iterator & begin,const Iterator & end)84 BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end)
85     : mFirstTime(true)
86     , mBegin(begin)
87     , mEnd(end)
88     , mCurrent(begin)
89     , mLargest(begin)
90     , mLastPackageId(0)
91     , mCurrentAttr(0)
92     , mFrameworkStart(end)
93     , mAppStart(end) {
94 }
95 
96 template <typename Derived, typename Iterator>
jumpToClosestAttribute(const uint32_t packageId)97 void BackTrackingAttributeFinder<Derived, Iterator>::jumpToClosestAttribute(const uint32_t packageId) {
98     switch (packageId) {
99         case 0x01:
100             mCurrent = mFrameworkStart;
101             break;
102         case 0x7f:
103             mCurrent = mAppStart;
104             break;
105         default: {
106             ssize_t idx = mPackageOffsets.indexOfKey(packageId);
107             if (idx >= 0) {
108                 // We have seen this package ID before, so jump to the first
109                 // attribute with this package ID.
110                 mCurrent = mPackageOffsets[idx];
111             } else {
112                 mCurrent = mEnd;
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 (mCurrent == mEnd) {
121         mCurrent = mLargest;
122     }
123 
124     if (mCurrent != mEnd) {
125         mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
126     }
127 }
128 
129 template <typename Derived, typename Iterator>
markCurrentPackageId(const uint32_t packageId)130 void BackTrackingAttributeFinder<Derived, Iterator>::markCurrentPackageId(const uint32_t packageId) {
131     switch (packageId) {
132         case 0x01:
133             mFrameworkStart = mCurrent;
134             break;
135         case 0x7f:
136             mAppStart = mCurrent;
137             break;
138         default:
139             mPackageOffsets.add(packageId, mCurrent);
140             break;
141     }
142 }
143 
144 template <typename Derived, typename Iterator>
find(uint32_t attr)145 Iterator BackTrackingAttributeFinder<Derived, Iterator>::find(uint32_t attr) {
146     if (!(mBegin < mEnd)) {
147         return mEnd;
148     }
149 
150     if (mFirstTime) {
151         // One-time initialization. We do this here instead of the constructor
152         // because the derived class we access in getAttribute() may not be
153         // fully constructed.
154         mFirstTime = false;
155         mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mBegin);
156         mLastPackageId = getPackage(mCurrentAttr);
157         markCurrentPackageId(mLastPackageId);
158     }
159 
160     // Looking for the needle (attribute we're looking for)
161     // in the haystack (the attributes we're searching through)
162     const uint32_t needlePackageId = getPackage(attr);
163     if (mLastPackageId != needlePackageId) {
164         jumpToClosestAttribute(needlePackageId);
165         mLastPackageId = needlePackageId;
166     }
167 
168     // Walk through the xml attributes looking for the requested attribute.
169     while (mCurrent != mEnd) {
170         const uint32_t haystackPackageId = getPackage(mCurrentAttr);
171         if (needlePackageId == haystackPackageId && attr < mCurrentAttr) {
172             // The attribute we are looking was not found.
173             break;
174         }
175         const uint32_t prevAttr = mCurrentAttr;
176 
177         // Move to the next attribute in the XML.
178         ++mCurrent;
179         if (mCurrent != mEnd) {
180             mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
181             const uint32_t newHaystackPackageId = getPackage(mCurrentAttr);
182             if (haystackPackageId != newHaystackPackageId) {
183                 // We've moved to the next group of attributes
184                 // with a new package ID, so we should record
185                 // the offset of this new package ID.
186                 markCurrentPackageId(newHaystackPackageId);
187             }
188         }
189 
190         if (mCurrent > mLargest) {
191             // We've moved past the latest attribute we've
192             // seen.
193             mLargest = mCurrent;
194         }
195 
196         if (attr == prevAttr) {
197             // We found the attribute we were looking for.
198             return mCurrent - 1;
199         }
200     }
201     return mEnd;
202 }
203 
204 } // namespace android
205 
206 #endif // H_ATTRIBUTE_FINDER
207