Optimize ResTable::getLocales() to improve bindApplication performance

Change from linear searching for uniqueness to binary search.

Bug:27198799
Change-Id: I1ccb6e93cc213810848f07d631d9d8de7c719803

5 files changed, 104 insertions, 26 deletions

diff --git a/libs/androidfw/tests/ResTable_test.cpp b/libs/androidfw/tests/ResTable_test.cpp
index 7cd7fb5cd711..b8b46259f0d1 100644
--- a/libs/androidfw/tests/ResTable_test.cpp
+++ b/libs/androidfw/tests/ResTable_test.cpp
@@ -39,8 +39,20 @@ namespace {
  */
 #include "data/basic/basic_arsc.h"
 
+/**
+ * Include a binary library resource table.
+ *
+ * Package: com.android.test.basic
+ */
 #include "data/lib/lib_arsc.h"
 
+/**
+ * Include a system resource table.
+ *
+ * Package: android
+ */
+#include "data/system/system_arsc.h"
+
 TEST(ResTableTest, shouldLoadSuccessfully) {
     ResTable table;
     ASSERT_EQ(NO_ERROR, table.add(basic_arsc, basic_arsc_len));
@@ -324,4 +336,25 @@ TEST(ResTableTest, ShareButDontModifyResTable) {
     ASSERT_EQ(uint32_t(600), val.data);
 }
 
+TEST(ResTableTest, GetConfigurationsReturnsUniqueList) {
+    ResTable table;
+    ASSERT_EQ(NO_ERROR, table.add(system_arsc, system_arsc_len));
+    ASSERT_EQ(NO_ERROR, table.add(basic_arsc, basic_arsc_len));
+
+    ResTable_config configSv;
+    memset(&configSv, 0, sizeof(configSv));
+    configSv.language[0] = 's';
+    configSv.language[1] = 'v';
+
+    Vector<ResTable_config> configs;
+    table.getConfigurations(&configs);
+
+    EXPECT_EQ(1, std::count(configs.begin(), configs.end(), configSv));
+
+    Vector<String8> locales;
+    table.getLocales(&locales);
+
+    EXPECT_EQ(1, std::count(locales.begin(), locales.end(), String8("sv")));
+}
+
 } // namespace
diff --git a/libs/androidfw/tests/TestHelpers.h b/libs/androidfw/tests/TestHelpers.h
index ac80d8868090..ff9be164dbb0 100644
--- a/libs/androidfw/tests/TestHelpers.h
+++ b/libs/androidfw/tests/TestHelpers.h
@@ -21,7 +21,7 @@ namespace android {
 enum { MAY_NOT_BE_BAG = false };
 
 static inline bool operator==(const android::ResTable_config& a, const android::ResTable_config& b) {
-    return memcmp(&a, &b, sizeof(a)) == 0;
+    return a.compare(b) == 0;
 }
 
 static inline ::std::ostream& operator<<(::std::ostream& out, const android::ResTable_config& c) {
diff --git a/libs/androidfw/tests/data/system/R.h b/libs/androidfw/tests/data/system/R.h
index 27f25fec0d01..6a31fb8ff088 100644
--- a/libs/androidfw/tests/data/system/R.h
+++ b/libs/androidfw/tests/data/system/R.h
@@ -33,6 +33,12 @@ namespace style {
     };
 }
 
+namespace integer {
+    enum {
+        number = 0x01030000, // sv
+    };
+}
+
 } // namespace R
 } // namespace android
 
diff --git a/libs/androidfw/tests/data/system/res/values-sv/values.xml b/libs/androidfw/tests/data/system/res/values-sv/values.xml
new file mode 100644
index 000000000000..b97bdb68aca7
--- /dev/null
+++ b/libs/androidfw/tests/data/system/res/values-sv/values.xml
@@ -0,0 +1,20 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2016 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.
+-->
+
+<resources>
+    <public type="integer" name="number" id="0x01030000" />
+    <integer name="number">1</integer>
+</resources>
diff --git a/libs/androidfw/tests/data/system/system_arsc.h b/libs/androidfw/tests/data/system/system_arsc.h
index 215ecae552c5..b0dab6b357e9 100644
--- a/libs/androidfw/tests/data/system/system_arsc.h
+++ b/libs/androidfw/tests/data/system/system_arsc.h
@@ -1,8 +1,8 @@
 unsigned char system_arsc[] = {
-  0x02, 0x00, 0x0c, 0x00, 0x18, 0x03, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+  0x02, 0x00, 0x0c, 0x00, 0xf8, 0x03, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
   0x01, 0x00, 0x1c, 0x00, 0x1c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1c, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x20, 0x01, 0xf0, 0x02, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x20, 0x01, 0xd0, 0x03, 0x00, 0x00,
   0x01, 0x00, 0x00, 0x00, 0x61, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x72, 0x00,
   0x6f, 0x00, 0x69, 0x00, 0x64, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
@@ -25,26 +25,33 @@ unsigned char system_arsc[] = {
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x20, 0x01, 0x00, 0x00,
-  0x02, 0x00, 0x00, 0x00, 0x60, 0x01, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x40, 0x00, 0x00, 0x00,
-  0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x24, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x0c, 0x00, 0x00, 0x00, 0x04, 0x00, 0x61, 0x00, 0x74, 0x00, 0x74, 0x00,
-  0x72, 0x00, 0x00, 0x00, 0x05, 0x00, 0x73, 0x00, 0x74, 0x00, 0x79, 0x00,
-  0x6c, 0x00, 0x65, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00,
-  0x70, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x18, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00,
+  0x04, 0x00, 0x00, 0x00, 0x98, 0x01, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x78, 0x00, 0x00, 0x00,
+  0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x2c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x0c, 0x00, 0x00, 0x00, 0x1a, 0x00, 0x00, 0x00, 0x2c, 0x00, 0x00, 0x00,
+  0x04, 0x00, 0x61, 0x00, 0x74, 0x00, 0x74, 0x00, 0x72, 0x00, 0x00, 0x00,
+  0x05, 0x00, 0x73, 0x00, 0x74, 0x00, 0x79, 0x00, 0x6c, 0x00, 0x65, 0x00,
+  0x00, 0x00, 0x07, 0x00, 0x69, 0x00, 0x6e, 0x00, 0x74, 0x00, 0x65, 0x00,
+  0x67, 0x00, 0x65, 0x00, 0x72, 0x00, 0x00, 0x00, 0x0d, 0x00, 0x5e, 0x00,
+  0x61, 0x00, 0x74, 0x00, 0x74, 0x00, 0x72, 0x00, 0x2d, 0x00, 0x70, 0x00,
+  0x72, 0x00, 0x69, 0x00, 0x76, 0x00, 0x61, 0x00, 0x74, 0x00, 0x65, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x84, 0x00, 0x00, 0x00,
+  0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x2c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x18, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00, 0x46, 0x00, 0x00, 0x00,
   0x0a, 0x00, 0x62, 0x00, 0x61, 0x00, 0x63, 0x00, 0x6b, 0x00, 0x67, 0x00,
   0x72, 0x00, 0x6f, 0x00, 0x75, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x00, 0x00,
   0x0a, 0x00, 0x66, 0x00, 0x6f, 0x00, 0x72, 0x00, 0x65, 0x00, 0x67, 0x00,
   0x72, 0x00, 0x6f, 0x00, 0x75, 0x00, 0x6e, 0x00, 0x64, 0x00, 0x00, 0x00,
   0x09, 0x00, 0x54, 0x00, 0x68, 0x00, 0x65, 0x00, 0x6d, 0x00, 0x65, 0x00,
-  0x2e, 0x00, 0x4f, 0x00, 0x6e, 0x00, 0x65, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x02, 0x02, 0x10, 0x00, 0x18, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
-  0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x40,
-  0x01, 0x02, 0x44, 0x00, 0x84, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
-  0x02, 0x00, 0x00, 0x00, 0x4c, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00,
+  0x2e, 0x00, 0x4f, 0x00, 0x6e, 0x00, 0x65, 0x00, 0x00, 0x00, 0x06, 0x00,
+  0x6e, 0x00, 0x75, 0x00, 0x6d, 0x00, 0x62, 0x00, 0x65, 0x00, 0x72, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x10, 0x00, 0x18, 0x00, 0x00, 0x00,
+  0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40,
+  0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00, 0x8c, 0x00, 0x00, 0x00,
+  0x01, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00,
+  0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
@@ -55,15 +62,27 @@ unsigned char system_arsc[] = {
   0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x01, 0x08, 0x00, 0x00, 0x10, 0x11, 0x00, 0x00, 0x00,
   0x02, 0x02, 0x10, 0x00, 0x14, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
-  0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x44, 0x00,
-  0x70, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
-  0x48, 0x00, 0x00, 0x00, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00,
+  0x78, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+  0x50, 0x00, 0x00, 0x00, 0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
   0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x03, 0x00,
-  0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00,
-  0x00, 0x00, 0x01, 0x01, 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0xff, 0xff,
-  0x01, 0x00, 0x01, 0x01, 0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0x00, 0xff
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x10, 0x00, 0x03, 0x00, 0x02, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01,
+  0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0xff, 0xff, 0x01, 0x00, 0x01, 0x01,
+  0x08, 0x00, 0x00, 0x1d, 0x00, 0x00, 0x00, 0xff, 0x02, 0x02, 0x10, 0x00,
+  0x14, 0x00, 0x00, 0x00, 0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x40, 0x01, 0x02, 0x4c, 0x00, 0x60, 0x00, 0x00, 0x00,
+  0x03, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x50, 0x00, 0x00, 0x00,
+  0x38, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x73, 0x76, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+  0x08, 0x00, 0x02, 0x00, 0x03, 0x00, 0x00, 0x00, 0x08, 0x00, 0x00, 0x10,
+  0x01, 0x00, 0x00, 0x00, 0x02, 0x02, 0x10, 0x00, 0x10, 0x00, 0x00, 0x00,
+  0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
 };
-unsigned int system_arsc_len = 792;
+unsigned int system_arsc_len = 1016;