1a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski/* 2a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * Copyright (C) 2014 The Android Open Source Project 3a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 4a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * Licensed under the Apache License, Version 2.0 (the "License"); 5a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * you may not use this file except in compliance with the License. 6a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * You may obtain a copy of the License at 7a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 8a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * http://www.apache.org/licenses/LICENSE-2.0 9a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 10a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * Unless required by applicable law or agreed to in writing, software 11a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * distributed under the License is distributed on an "AS IS" BASIS, 12a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * See the License for the specific language governing permissions and 14a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * limitations under the License. 15a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski */ 16a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 17a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski#ifndef H_ATTRIBUTE_FINDER 18a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski#define H_ATTRIBUTE_FINDER 19a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 20a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski#include <stdint.h> 21a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski#include <utils/KeyedVector.h> 22a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 23a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskinamespace android { 24a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 25a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskistatic inline uint32_t getPackage(uint32_t attr) { 26a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski return attr >> 24; 27a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} 28a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 29a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski/** 30a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * A helper class to search linearly for the requested 31a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * attribute, maintaining it's position and optimizing for 32a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * the case that subsequent searches will involve an attribute with 33a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * a higher attribute ID. 34a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 35a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * In the case that a subsequent attribute has a different package ID, 36a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * its resource ID may not be larger than the preceding search, so 37a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * back tracking is supported for this case. This 38a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * back tracking requirement is mainly for shared library 39a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * resources, whose package IDs get assigned at runtime 40a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * and thus attributes from a shared library may 41a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * be out of order. 42a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 43a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * We make two assumptions about the order of attributes: 44a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 1) The input has the same sorting rules applied to it as 45a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * the attribute data contained by this class. 46a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 2) Attributes are grouped by package ID. 47a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 3) Among attributes with the same package ID, the attributes are 48a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * sorted by increasing resource ID. 49a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 50a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * Ex: 02010000, 02010001, 010100f4, 010100f5, 0x7f010001, 07f010003 51a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * 52a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * The total order of attributes (including package ID) can not be linear 53a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * as shared libraries get assigned dynamic package IDs at runtime, which 54a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski * may break the sort order established at build time. 55a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski */ 56a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskitemplate <typename Derived, typename Iterator> 57a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskiclass BackTrackingAttributeFinder { 58a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskipublic: 59a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end); 60a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 61a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator find(uint32_t attr); 62a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 63a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskiprivate: 64a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski void jumpToClosestAttribute(uint32_t packageId); 65a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski void markCurrentPackageId(uint32_t packageId); 66a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 675dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski bool mFirstTime; 68a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mBegin; 69a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mEnd; 70a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mCurrent; 71a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mLargest; 72a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski uint32_t mLastPackageId; 73a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski uint32_t mCurrentAttr; 74a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 75a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // Package Offsets (best-case, fast look-up). 76a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mFrameworkStart; 77a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski Iterator mAppStart; 78a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 79a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // Worst case, we have shared-library resources. 80a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski KeyedVector<uint32_t, Iterator> mPackageOffsets; 81a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski}; 82a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 83a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskitemplate <typename Derived, typename Iterator> inline 84a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam LesinskiBackTrackingAttributeFinder<Derived, Iterator>::BackTrackingAttributeFinder(const Iterator& begin, const Iterator& end) 855dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski : mFirstTime(true) 865dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski , mBegin(begin) 87a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mEnd(end) 88a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mCurrent(begin) 89a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mLargest(begin) 90a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mLastPackageId(0) 91a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mCurrentAttr(0) 92a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mFrameworkStart(end) 93a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski , mAppStart(end) { 94a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} 95a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 96a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskitemplate <typename Derived, typename Iterator> 97a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskivoid BackTrackingAttributeFinder<Derived, Iterator>::jumpToClosestAttribute(const uint32_t packageId) { 98a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski switch (packageId) { 99a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski case 0x01: 100a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrent = mFrameworkStart; 101a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 102a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski case 0x7f: 103a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrent = mAppStart; 104a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 105a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski default: { 106a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski ssize_t idx = mPackageOffsets.indexOfKey(packageId); 107a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (idx >= 0) { 108a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // We have seen this package ID before, so jump to the first 109a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // attribute with this package ID. 110a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrent = mPackageOffsets[idx]; 111a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } else { 112a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrent = mEnd; 113a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 114a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 115a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 116a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 117a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 118a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // We have never seen this package ID yet, so jump to the 119a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // latest/largest index we have processed so far. 120a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (mCurrent == mEnd) { 121a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrent = mLargest; 122a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 123a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 124a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (mCurrent != mEnd) { 125a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent); 126a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 127a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} 128a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 129a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskitemplate <typename Derived, typename Iterator> 130a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskivoid BackTrackingAttributeFinder<Derived, Iterator>::markCurrentPackageId(const uint32_t packageId) { 131a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski switch (packageId) { 132a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski case 0x01: 133a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mFrameworkStart = mCurrent; 134a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 135a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski case 0x7f: 136a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mAppStart = mCurrent; 137a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 138a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski default: 139a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mPackageOffsets.add(packageId, mCurrent); 140a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 141a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 142a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} 143a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 144a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinskitemplate <typename Derived, typename Iterator> 145a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam LesinskiIterator BackTrackingAttributeFinder<Derived, Iterator>::find(uint32_t attr) { 146a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (!(mBegin < mEnd)) { 147a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski return mEnd; 148a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 149a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 1505dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski if (mFirstTime) { 1515dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski // One-time initialization. We do this here instead of the constructor 1525dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski // because the derived class we access in getAttribute() may not be 1535dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski // fully constructed. 1545dce5e67dbdcd14882edf3f64fba671c77577ee4Adam Lesinski mFirstTime = false; 155a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mBegin); 156a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mLastPackageId = getPackage(mCurrentAttr); 157a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski markCurrentPackageId(mLastPackageId); 158a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 159a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 160a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // Looking for the needle (attribute we're looking for) 161a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // in the haystack (the attributes we're searching through) 162a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski const uint32_t needlePackageId = getPackage(attr); 163a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (mLastPackageId != needlePackageId) { 164a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski jumpToClosestAttribute(needlePackageId); 165a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mLastPackageId = needlePackageId; 166a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 167a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 168a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // Walk through the xml attributes looking for the requested attribute. 169a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski while (mCurrent != mEnd) { 170a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski const uint32_t haystackPackageId = getPackage(mCurrentAttr); 171a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (needlePackageId == haystackPackageId && attr < mCurrentAttr) { 172a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // The attribute we are looking was not found. 173a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski break; 174a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 175a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski const uint32_t prevAttr = mCurrentAttr; 176a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 177a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // Move to the next attribute in the XML. 178a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski ++mCurrent; 179a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (mCurrent != mEnd) { 180a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mCurrentAttr = static_cast<const Derived*>(this)->getAttribute(mCurrent); 181a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski const uint32_t newHaystackPackageId = getPackage(mCurrentAttr); 182a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (haystackPackageId != newHaystackPackageId) { 183a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // We've moved to the next group of attributes 184a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // with a new package ID, so we should record 185a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // the offset of this new package ID. 186a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski markCurrentPackageId(newHaystackPackageId); 187a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 188a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 189a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 190a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (mCurrent > mLargest) { 191a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // We've moved past the latest attribute we've 192a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // seen. 193a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski mLargest = mCurrent; 194a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 195a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 196a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski if (attr == prevAttr) { 197a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski // We found the attribute we were looking for. 198a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski return mCurrent - 1; 199a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 200a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski } 201a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski return mEnd; 202a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} 203a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 204a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski} // namespace android 205a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski 206a7d1d73a477fe512d9ea69ee2883084630ec24c4Adam Lesinski#endif // H_ATTRIBUTE_FINDER 207