Support multiple resource tables with same package

In order to support APK split features, the resource
table needs to support loading multiple resource
tables with the same package but potentially new set
of type IDs.

This adds some complexity as the type ID space changes
from dense and ordered to potentially sparse.

A ByteBucketArray is used to store the type IDs in
a memory efficient way that allows for fast retrieval.

In addition, the IDMAP format has changed. We no longer
need random access to the type data, since we store the
types differently. However, random access to entries of
a given type is still required.

Change-Id: If6f5be680b405b368941d9c1f2b5d2ddca964160

3 files changed, 222 insertions, 13 deletions

diff --git a/include/androidfw/ByteBucketArray.h b/include/androidfw/ByteBucketArray.h
new file mode 100644
index 0000000..87c6b12
--- /dev/null
+++ b/include/androidfw/ByteBucketArray.h
@@ -0,0 +1,97 @@
+/*
+ * 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 __BYTE_BUCKET_ARRAY_H
+#define __BYTE_BUCKET_ARRAY_H
+
+#include <utils/Log.h>
+#include <stdint.h>
+#include <string.h>
+
+namespace android {
+
+/**
+ * Stores a sparsely populated array. Has a fixed size of 256
+ * (number of entries that a byte can represent).
+ */
+template<typename T>
+class ByteBucketArray {
+public:
+    ByteBucketArray() : mDefault() {
+        memset(mBuckets, 0, sizeof(mBuckets));
+    }
+
+    ~ByteBucketArray() {
+        for (size_t i = 0; i < NUM_BUCKETS; i++) {
+            if (mBuckets[i] != NULL) {
+                delete [] mBuckets[i];
+            }
+        }
+        memset(mBuckets, 0, sizeof(mBuckets));
+    }
+
+    inline size_t size() const {
+        return NUM_BUCKETS * BUCKET_SIZE;
+    }
+
+    inline const T& get(size_t index) const {
+        return (*this)[index];
+    }
+
+    const T& operator[](size_t index) const {
+        if (index >= size()) {
+            return mDefault;
+        }
+
+        uint8_t bucketIndex = static_cast<uint8_t>(index) >> 4;
+        T* bucket = mBuckets[bucketIndex];
+        if (bucket == NULL) {
+            return mDefault;
+        }
+        return bucket[0x0f & static_cast<uint8_t>(index)];
+    }
+
+    T& editItemAt(size_t index) {
+        ALOG_ASSERT(index < size(), "ByteBucketArray.getOrCreate(index=%u) with size=%u",
+                (uint32_t) index, (uint32_t) size());
+
+        uint8_t bucketIndex = static_cast<uint8_t>(index) >> 4;
+        T* bucket = mBuckets[bucketIndex];
+        if (bucket == NULL) {
+            bucket = mBuckets[bucketIndex] = new T[BUCKET_SIZE]();
+        }
+        return bucket[0x0f & static_cast<uint8_t>(index)];
+    }
+
+    bool set(size_t index, const T& value) {
+        if (index >= size()) {
+            return false;
+        }
+
+        editItemAt(index) = value;
+        return true;
+    }
+
+private:
+    enum { NUM_BUCKETS = 16, BUCKET_SIZE = 16 };
+
+    T*  mBuckets[NUM_BUCKETS];
+    T   mDefault;
+};
+
+} // namespace android
+
+#endif // __BYTE_BUCKET_ARRAY_H
diff --git a/include/androidfw/ResourceTypes.h b/include/androidfw/ResourceTypes.h
index 4d8e512..e612c0a 100644
--- a/include/androidfw/ResourceTypes.h
+++ b/include/androidfw/ResourceTypes.h
@@ -237,6 +237,7 @@ enum {
 #define Res_MAKEARRAY(entry) (0x02000000 | (entry&0xFFFF))
 
 #define Res_MAXPACKAGE 255
+#define Res_MAXTYPE 255
 
 /**
  * Representation of a value in a resource, supplying type
@@ -510,6 +511,23 @@ private:
     uint32_t                    mStylePoolSize;    // number of uint32_t
 };
 
+/**
+ * Wrapper class that allows the caller to retrieve a string from
+ * a string pool without knowing which string pool to look.
+ */
+class StringPoolRef {
+public:
+    StringPoolRef();
+    StringPoolRef(const ResStringPool* pool, uint32_t index);
+
+    const char* string8(size_t* outLen) const;
+    const char16_t* string16(size_t* outLen) const;
+
+private:
+    const ResStringPool*        mPool;
+    uint32_t                    mIndex;
+};
+
 /** ********************************************************************
  *  XML Tree
  *
@@ -835,6 +853,8 @@ struct ResTable_package
 
     // Last index into keyStrings that is for public use by others.
     uint32_t lastPublicKey;
+
+    uint32_t typeIdOffset;
 };
 
 // The most specific locale can consist of:
@@ -1469,9 +1489,13 @@ public:
              bool copyData=false);
     ~ResTable();
 
-    status_t add(Asset* asset, const int32_t cookie, bool copyData,
-                 const void* idmap = NULL);
-    status_t add(const void *data, size_t size);
+    status_t add(const void* data, size_t size, const int32_t cookie=-1, bool copyData=false);
+    status_t add(const void* data, size_t size, const void* idmapData, size_t idmapDataSize,
+            const int32_t cookie=-1, bool copyData=false);
+
+    status_t add(Asset* asset, const int32_t cookie=-1, bool copyData=false);
+    status_t add(Asset* asset, Asset* idmapAsset, const int32_t cookie=-1, bool copyData=false);
+
     status_t add(ResTable* src);
     status_t addEmpty(const int32_t cookie);
 
@@ -1610,13 +1634,14 @@ public:
             uint32_t typeSpecFlags;
             Res_value value;
         };
+
         struct type_info {
             size_t numEntries;
             theme_entry* entries;
         };
+
         struct package_info {
-            size_t numTypes;
-            type_info types[];
+            type_info types[Res_MAXTYPE + 1];
         };
 
         void free_package(package_info* pi);
@@ -1711,6 +1736,7 @@ public:
     size_t getBasePackageCount() const;
     const String16 getBasePackageName(size_t idx) const;
     uint32_t getBasePackageId(size_t idx) const;
+    uint32_t getLastTypeIdForPackage(size_t idx) const;
 
     // Return the number of resource tables that the object contains.
     size_t getTableCount() const;
@@ -1740,13 +1766,15 @@ public:
             void** outData, size_t* outSize) const;
 
     enum {
-        IDMAP_HEADER_SIZE_BYTES = 3 * sizeof(uint32_t) + 2 * 256,
+        IDMAP_HEADER_SIZE_BYTES = 4 * sizeof(uint32_t) + 2 * 256,
     };
+
     // Retrieve idmap meta-data.
     //
     // This function only requires the idmap header (the first
     // IDMAP_HEADER_SIZE_BYTES) bytes of an idmap file.
     static bool getIdmapInfo(const void* idmap, size_t size,
+            uint32_t* pVersion,
             uint32_t* pTargetCrc, uint32_t* pOverlayCrc,
             String8* pTargetPath, String8* pOverlayPath);
 
@@ -1756,21 +1784,24 @@ public:
 private:
     struct Header;
     struct Type;
+    struct Entry;
     struct Package;
     struct PackageGroup;
     struct bag_set;
+    typedef Vector<Type*> TypeList;
 
-    status_t addInternal(const void* data, size_t size, const int32_t cookie,
-                 bool copyData, const Asset* idmap);
+    status_t addInternal(const void* data, size_t size, const void* idmapData, size_t idmapDataSize,
+            const int32_t cookie, bool copyData);
 
     ssize_t getResourcePackageIndex(uint32_t resID) const;
-    ssize_t getEntry(
-        const Package* package, int typeIndex, int entryIndex,
+
+    status_t getEntry(
+        const PackageGroup* packageGroup, int typeIndex, int entryIndex,
         const ResTable_config* config,
-        const ResTable_type** outType, const ResTable_entry** outEntry,
-        const Type** outTypeClass) const;
+        Entry* outEntry) const;
+
     status_t parsePackage(
-        const ResTable_package* const pkg, const Header* const header, uint32_t idmap_id);
+        const ResTable_package* const pkg, const Header* const header);
 
     void print_value(const Package* pkg, const Res_value& value) const;
     
diff --git a/include/androidfw/TypeWrappers.h b/include/androidfw/TypeWrappers.h
new file mode 100644
index 0000000..7bdf8af
--- /dev/null
+++ b/include/androidfw/TypeWrappers.h
@@ -0,0 +1,81 @@
+/*
+ * 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 __TYPE_WRAPPERS_H
+#define __TYPE_WRAPPERS_H
+
+#include <androidfw/ResourceTypes.h>
+
+namespace android {
+
+struct TypeVariant {
+    TypeVariant(const ResTable_type* data)
+        : data(data) {}
+
+    class iterator {
+    public:
+        iterator& operator=(const iterator& rhs) {
+            mTypeVariant = rhs.mTypeVariant;
+            mIndex = rhs.mIndex;
+        }
+
+        bool operator==(const iterator& rhs) const {
+            return mTypeVariant == rhs.mTypeVariant && mIndex == rhs.mIndex;
+        }
+
+        bool operator!=(const iterator& rhs) const {
+            return mTypeVariant != rhs.mTypeVariant || mIndex != rhs.mIndex;
+        }
+
+        iterator operator++(int) {
+            uint32_t prevIndex = mIndex;
+            operator++();
+            return iterator(mTypeVariant, prevIndex);
+        }
+
+        const ResTable_entry* operator->() const {
+            return operator*();
+        }
+
+        uint32_t index() const {
+            return mIndex;
+        }
+
+        iterator& operator++();
+        const ResTable_entry* operator*() const;
+
+    private:
+        friend struct TypeVariant;
+        iterator(const TypeVariant* tv, uint32_t index)
+            : mTypeVariant(tv), mIndex(index) {}
+        const TypeVariant* mTypeVariant;
+        uint32_t mIndex;
+    };
+
+    iterator beginEntries() const {
+        return iterator(this, 0);
+    }
+
+    iterator endEntries() const {
+        return iterator(this, dtohl(data->entryCount));
+    }
+
+    const ResTable_type* data;
+};
+
+} // namespace android
+
+#endif // __TYPE_WRAPPERS_H