Home | History | Annotate | Download | only in androidfw 
      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 
     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
     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>
     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>
    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>
    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