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
23namespace android {
24
25static 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 */
56template <typename Derived, typename Iterator>
57class BackTrackingAttributeFinder {
58public:
59    BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
60
61    Iterator find(uint32_t attr);
62
63private:
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
83template <typename Derived, typename Iterator> inline
84BackTrackingAttributeFinder<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
96template <typename Derived, typename Iterator>
97void 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
129template <typename Derived, typename Iterator>
130void 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
144template <typename Derived, typename Iterator>
145Iterator 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