+ // Sort the array.
+ NOISY(printf("SORTING STRINGS BY CONFIGURATION...\n"));
+ // 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.
+ // For more fun, GLibC took qsort_r from BSD but then decided to swap the
+ // order the last two parameters.
+#ifdef __GLIBC__
+ qsort_r(newPosToOriginalPos.editArray(), N, sizeof(size_t), config_sort, this);
+#else
+ qsort_r(newPosToOriginalPos.editArray(), N, sizeof(size_t), this, config_sort);
+#endif
+ //newPosToOriginalPos.sort(config_sort, this);
+ NOISY(printf("DONE SORTING STRINGS BY CONFIGURATION.\n"));
+
+ // Create the reverse mapping from the original position in the array
+ // to the new position where it appears in the sorted array. This is
+ // so that clients can re-map any positions they had previously stored.
+ mOriginalPosToNewPos = newPosToOriginalPos;
+ for (size_t i=0; i<N; i++) {
+ mOriginalPosToNewPos.editItemAt(newPosToOriginalPos[i]) = i;
+ }
+
+#if 0
+ SortedVector<entry> entries;
+
+ for (size_t i=0; i<N; i++) {
+ printf("#%d was %d: %s\n", i, newPosToOriginalPos[i],
+ mEntries[mEntryArray[newPosToOriginalPos[i]]].makeConfigsString().string());
+ entries.add(mEntries[mEntryArray[i]]);
+ }
+
+ for (size_t i=0; i<entries.size(); i++) {
+ printf("Sorted config #%d: %s\n", i,
+ entries[i].makeConfigsString().string());
+ }
+#endif
+
+ // Now we rebuild the arrays.
+ Vector<entry> newEntries;
+ Vector<size_t> newEntryArray;
+ Vector<entry_style> newEntryStyleArray;
+ DefaultKeyedVector<size_t, size_t> origOffsetToNewOffset;
+
+ for (size_t i=0; i<N; i++) {
+ // We are filling in new offset 'i'; oldI is where we can find it
+ // in the original data structure.
+ size_t oldI = newPosToOriginalPos[i];
+ // This is the actual entry associated with the old offset.
+ const entry& oldEnt = mEntries[mEntryArray[oldI]];
+ // This is the same entry the last time we added it to the
+ // new entry array, if any.
+ ssize_t newIndexOfOffset = origOffsetToNewOffset.indexOfKey(oldI);
+ size_t newOffset;
+ if (newIndexOfOffset < 0) {
+ // This is the first time we have seen the entry, so add
+ // it.
+ newOffset = newEntries.add(oldEnt);
+ newEntries.editItemAt(newOffset).indices.clear();
+ } else {
+ // We have seen this entry before, use the existing one
+ // instead of adding it again.
+ newOffset = origOffsetToNewOffset.valueAt(newIndexOfOffset);
+ }
+ // Update the indices to include this new position.
+ newEntries.editItemAt(newOffset).indices.add(i);
+ // And add the offset of the entry to the new entry array.
+ newEntryArray.add(newOffset);
+ // Add any old style to the new style array.
+ if (mEntryStyleArray.size() > 0) {
+ if (oldI < mEntryStyleArray.size()) {
+ newEntryStyleArray.add(mEntryStyleArray[oldI]);
+ } else {
+ newEntryStyleArray.add(entry_style());
+ }
+ }
+ }
+
+ // Now trim any entries at the end of the new style array that are
+ // not needed.
+ for (ssize_t i=newEntryStyleArray.size()-1; i>=0; i--) {
+ const entry_style& style = newEntryStyleArray[i];
+ if (style.spans.size() > 0) {
+ // That's it.
+ break;
+ }
+ // This one is not needed; remove.
+ newEntryStyleArray.removeAt(i);
+ }
+
+ // All done, install the new data structures and upate mValues with
+ // the new positions.
+ mEntries = newEntries;
+ mEntryArray = newEntryArray;
+ mEntryStyleArray = newEntryStyleArray;
+ mValues.clear();
+ for (size_t i=0; i<mEntries.size(); i++) {
+ const entry& ent = mEntries[i];
+ mValues.add(ent.value, ent.indices[0]);
+ }
+
+#if 0
+ printf("FINAL SORTED STRING CONFIGS:\n");
+ for (size_t i=0; i<mEntries.size(); i++) {
+ const entry& ent = mEntries[i];
+ printf("#" ZD " %s: %s\n", (ZD_TYPE)i, ent.makeConfigsString().string(),
+ String8(ent.value).string());
+ }
+#endif
projects / android / aapt.git / blobdiff