am ba1992f8: Merge "Remove doSingleCrunch call DO NOT MERGE" into jb-mr1-aah-dev

[android/aapt.git] / StringPool.cpp

diff --git a/StringPool.cpp b/StringPool.cpp
index 963ae59cdb5c6c1b08eb04fa1c6f8cd310fe6f7d..839eda5151b03bc602e612464842a72a8e0b51cc 100644 (file)
--- a/StringPool.cpp
+++ b/StringPool.cpp
@@ -9,6 +9,7 @@
 
 #include <utils/ByteOrder.h>
 #include <utils/SortedVector.h>
 
 #include <utils/ByteOrder.h>
 #include <utils/SortedVector.h>

+#include <cutils/qsort_r_compat.h>

 
 #if HAVE_PRINTF_ZD
 #  define ZD "%zd"
 
 #if HAVE_PRINTF_ZD
 #  define ZD "%zd"


@@ -213,11 +214,11 @@ status_t StringPool::addStyleSpan(size_t idx, const entry_style_span& span)
     return NO_ERROR;
 }
 
     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;
 {
     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);
 }
 
     return lhe.compare(rhe);
 }
 


@@ -232,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;
     // 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.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
     NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
 
     // Create the reverse mapping from the original position in the array