blob: acf70565c4f92bb9b5703b77c76ad4359bd1d361 [file] [log] [blame]
/*
* Copyright (C) 2014 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef H_ATTRIBUTE_FINDER
#define H_ATTRIBUTE_FINDER
#include <stdint.h>
#include <utils/KeyedVector.h>
namespace android {
static inline uint32_t getPackage(uint32_t attr) {
return attr >> 24;
}
/**
* A helper class to search linearly for the requested
* attribute, maintaining it's position and optimizing for
* the case that subsequent searches will involve an attribute with
* a higher attribute ID.
*
* In the case that a subsequent attribute has a different package ID,
* its resource ID may not be larger than the preceding search, so
* back tracking is supported for this case. This
* back tracking requirement is mainly for shared library
* resources, whose package IDs get assigned at runtime
* and thus attributes from a shared library may
* be out of order.
*
* We make two assumptions about the order of attributes:
* 1) The input has the same sorting rules applied to it as
* the attribute data contained by this class.
* 2) Attributes are grouped by package ID.
* 3) Among attributes with the same package ID, the attributes are
* sorted by increasing resource ID.
*
* Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003
*
* The total order of attributes (including package ID) can not be linear
* as shared libraries get assigned dynamic package IDs at runtime, which
* may break the sort order established at build time.
*/
template <typename Derived, typename Iterator>
class BackTrackingAttributeFinder {
public:
BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end);
Iterator find(uint32_t attr);
private:
void jumpToClosestAttribute(uint32_t packageId);
void markCurrentPackageId(uint32_t packageId);
bool mFirstTime;
Iterator mBegin;
Iterator mEnd;
Iterator mCurrent;
Iterator mLargest;
uint32_t mLastPackageId;
uint32_t mCurrentAttr;
// Package Offsets (best-case, fast look-up).
Iterator mFrameworkStart;
Iterator mAppStart;
// Worst case, we have shared-library resources.
KeyedVector<uint32_t, Iterator> mPackageOffsets;
};
template <typename Derived, typename Iterator> inline
BackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end)
: mFirstTime(true)
, mBegin(begin)
, mEnd(end)
, mCurrent(begin)
, mLargest(begin)
, mLastPackageId(0)
, mCurrentAttr(0)
, mFrameworkStart(end)
, mAppStart(end) {
}
template <typename Derived, typename Iterator>
void BackTrackingAttributeFinder<Derived, Iterator>::jumpToClosestAttribute(const uint32_t packageId) {
switch (packageId) {
case 0x01:
mCurrent = mFrameworkStart;
break;
case 0x7f:
mCurrent = mAppStart;
break;
default: {
ssize_t idx = mPackageOffsets.indexOfKey(packageId);
if (idx >= 0) {
// We have seen this package ID before, so jump to the first
// attribute with this package ID.
mCurrent = mPackageOffsets[idx];
} else {
mCurrent = mEnd;
}
break;
}
}
// We have never seen this package ID yet, so jump to the
// latest/largest index we have processed so far.
if (mCurrent == mEnd) {
mCurrent = mLargest;
}
if (mCurrent != mEnd) {
mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
}
}
template <typename Derived, typename Iterator>
void BackTrackingAttributeFinder<Derived, Iterator>::markCurrentPackageId(const uint32_t packageId) {
switch (packageId) {
case 0x01:
mFrameworkStart = mCurrent;
break;
case 0x7f:
mAppStart = mCurrent;
break;
default:
mPackageOffsets.add(packageId, mCurrent);
break;
}
}
template <typename Derived, typename Iterator>
Iterator BackTrackingAttributeFinder<Derived, Iterator>::find(uint32_t attr) {
if (!(mBegin < mEnd)) {
return mEnd;
}
if (mFirstTime) {
// One-time initialization. We do this here instead of the constructor
// because the derived class we access in getAttribute() may not be
// fully constructed.
mFirstTime = false;
mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mBegin);
mLastPackageId = getPackage(mCurrentAttr);
markCurrentPackageId(mLastPackageId);
}
// Looking for the needle (attribute we're looking for)
// in the haystack (the attributes we're searching through)
const uint32_t needlePackageId = getPackage(attr);
if (mLastPackageId != needlePackageId) {
jumpToClosestAttribute(needlePackageId);
mLastPackageId = needlePackageId;
}
// Walk through the xml attributes looking for the requested attribute.
while (mCurrent != mEnd) {
const uint32_t haystackPackageId = getPackage(mCurrentAttr);
if (needlePackageId == haystackPackageId && attr < mCurrentAttr) {
// The attribute we are looking was not found.
break;
}
const uint32_t prevAttr = mCurrentAttr;
// Move to the next attribute in the XML.
++mCurrent;
if (mCurrent != mEnd) {
mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent);
const uint32_t newHaystackPackageId = getPackage(mCurrentAttr);
if (haystackPackageId != newHaystackPackageId) {
// We've moved to the next group of attributes
// with a new package ID, so we should record
// the offset of this new package ID.
markCurrentPackageId(newHaystackPackageId);
}
}
if (mCurrent > mLargest) {
// We've moved past the latest attribute we've
// seen.
mLargest = mCurrent;
}
if (attr == prevAttr) {
// We found the attribute we were looking for.
return mCurrent - 1;
}
}
return mEnd;
}
} // namespace android
#endif // H_ATTRIBUTE_FINDER