am 8c71784e: Merge "Initialize mJunkPath to false"

[android/aapt.git] / StringPool.cpp

diff --git a/StringPool.cpp b/StringPool.cpp
index 46a4c3262b66471d359560a22223a4bf871e2b93..839eda5151b03bc602e612464842a72a8e0b51cc 100644 (file)
--- a/StringPool.cpp
+++ b/StringPool.cpp
@@ -9,6 +9,7 @@
 
 #include <utils/ByteOrder.h>
 #include <utils/SortedVector.h>
+#include <cutils/qsort_r_compat.h>
 
 #if HAVE_PRINTF_ZD
 #  define ZD "%zd"
@@ -71,14 +72,16 @@ String8 StringPool::entry::makeConfigsString() const {
 }
 
 int StringPool::entry::compare(const entry& o) const {
-    // Strings with styles go first, to reduce the size of the
-    // styles array.
+    // Strings with styles go first, to reduce the size of the styles array.
+    // We don't care about the relative order of these strings.
     if (hasStyles) {
         return o.hasStyles ? 0 : -1;
     }
     if (o.hasStyles) {
         return 1;
     }
+
+    // Sort unstyled strings by type, then by logical configuration.
     int comp = configTypeName.compare(o.configTypeName);
     if (comp != 0) {
         return comp;
@@ -211,11 +214,11 @@ status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
     return NO_ERROR;
 }
 
-int StringPool::config_sort(const size_t* lhs, const size_t* rhs, void* state)
+int StringPool::config_sort(void* state, const void* lhs, const void* rhs)
 {
     StringPool* pool = (StringPool*)state;
-    const entry& lhe = pool->mEntries[pool->mEntryArray[*lhs]];
-    const entry& rhe = pool->mEntries[pool->mEntryArray[*rhs]];
+    const entry& lhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(lhs)]];
+    const entry& rhe = pool->mEntries[pool->mEntryArray[*static_cast<const size_t*>(rhs)]];
     return lhe.compare(rhe);
 }
 
@@ -230,13 +233,17 @@ void StringPool::sortByConfig()
     // At that point it maps from the new position in the array to the
     // original position the entry appeared.
     Vector<size_t> newPosToOriginalPos;
-    for (size_t i=0; i<mEntryArray.size(); i++) {
+    newPosToOriginalPos.setCapacity(N);
+    for (size_t i=0; i < N; i++) {
         newPosToOriginalPos.add(i);
     }
 
     // Sort the array.
     NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
-    newPosToOriginalPos.sort(config_sort, this);
+    // Vector::sort uses insertion sort, which is very slow for this data set.
+    // Use quicksort instead because we don't need a stable sort here.
+    qsort_r_compat(newPosToOriginalPos.editArray(), N, sizeof(size_t), this, config_sort);
+    //newPosToOriginalPos.sort(config_sort, this);
     NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
 
     // Create the reverse mapping from the original position in the array