Merge commit '06d8b7b8' into manualmerge

Conflicts:
	core/jni/android_util_AssetManager.cpp

Change-Id: I77b72d0d3ec8184ccd97419e4c76b7d55b1a52ca

1 files changed, 201 insertions, 0 deletions

diff --git a/include/androidfw/AttributeFinder.h b/include/androidfw/AttributeFinder.h
new file mode 100644
index 0000000..a0ffeb3
--- /dev/null
+++ b/include/androidfw/AttributeFinder.h
@@ -0,0 +1,201 @@
+/*
+ * 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);
+
+    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)
+    : 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 (mCurrentAttr == 0) {
+        // One-time initialization.
+        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