Optimize sorting performance by 7.64% in DocumentsUI.
This CL prevents allocating new strings just due to the prefix,
which also simplifies the code.
Bug: 27286016
Change-Id: I3d0ea9e4ede68814c78404bd9ac820b8900851f5
diff --git a/packages/DocumentsUI/src/com/android/documentsui/Shared.java b/packages/DocumentsUI/src/com/android/documentsui/Shared.java
index 26900a7..b539421 100644
--- a/packages/DocumentsUI/src/com/android/documentsui/Shared.java
+++ b/packages/DocumentsUI/src/com/android/documentsui/Shared.java
@@ -86,12 +86,6 @@
*/
public static final String EXTRA_IGNORE_STATE = "ignoreState";
-
- /**
- * String prefix used to indicate the document is a directory.
- */
- public static final char DIR_PREFIX = '\001';
-
private static final Collator sCollator;
static {
@@ -150,12 +144,6 @@
if (leftEmpty) return -1;
if (rightEmpty) return 1;
- final boolean leftDir = (lhs.charAt(0) == DIR_PREFIX);
- final boolean rightDir = (rhs.charAt(0) == DIR_PREFIX);
-
- if (leftDir && !rightDir) return -1;
- if (rightDir && !leftDir) return 1;
-
return sCollator.compare(lhs, rhs);
}
diff --git a/packages/DocumentsUI/src/com/android/documentsui/dirlist/Model.java b/packages/DocumentsUI/src/com/android/documentsui/dirlist/Model.java
index ab4f5c4..c5ee592 100644
--- a/packages/DocumentsUI/src/com/android/documentsui/dirlist/Model.java
+++ b/packages/DocumentsUI/src/com/android/documentsui/dirlist/Model.java
@@ -153,48 +153,53 @@
private void updateModelData() {
int[] positions = new int[mCursorCount];
mIds = new String[mCursorCount];
- String[] stringValues = new String[mCursorCount];
+ boolean[] isDirs = new boolean[mCursorCount];
+ String[] displayNames = null;
long[] longValues = null;
- if (mSortOrder == SORT_ORDER_LAST_MODIFIED || mSortOrder == SORT_ORDER_SIZE) {
- longValues = new long[mCursorCount];
+ switch (mSortOrder) {
+ case SORT_ORDER_DISPLAY_NAME:
+ displayNames = new String[mCursorCount];
+ break;
+ case SORT_ORDER_LAST_MODIFIED:
+ case SORT_ORDER_SIZE:
+ longValues = new long[mCursorCount];
+ break;
}
+ String mimeType;
+
mCursor.moveToPosition(-1);
for (int pos = 0; pos < mCursorCount; ++pos) {
mCursor.moveToNext();
positions[pos] = pos;
mIds[pos] = createModelId(mCursor);
+ mimeType = getCursorString(mCursor, Document.COLUMN_MIME_TYPE);
+ isDirs[pos] = Document.MIME_TYPE_DIR.equals(mimeType);
+
switch(mSortOrder) {
case SORT_ORDER_DISPLAY_NAME:
- final String mimeType = getCursorString(mCursor, Document.COLUMN_MIME_TYPE);
final String displayName = getCursorString(
mCursor, Document.COLUMN_DISPLAY_NAME);
- if (Document.MIME_TYPE_DIR.equals(mimeType)) {
- stringValues[pos] = Shared.DIR_PREFIX + displayName;
- } else {
- stringValues[pos] = displayName;
- }
+ displayNames[pos] = displayName;
break;
case SORT_ORDER_LAST_MODIFIED:
longValues[pos] = getLastModified(mCursor);
- stringValues[pos] = getCursorString(mCursor, Document.COLUMN_MIME_TYPE);
break;
case SORT_ORDER_SIZE:
longValues[pos] = getCursorLong(mCursor, Document.COLUMN_SIZE);
- stringValues[pos] = getCursorString(mCursor, Document.COLUMN_MIME_TYPE);
break;
}
}
switch (mSortOrder) {
case SORT_ORDER_DISPLAY_NAME:
- binarySort(stringValues, positions, mIds);
+ binarySort(displayNames, isDirs, positions, mIds);
break;
case SORT_ORDER_LAST_MODIFIED:
case SORT_ORDER_SIZE:
- binarySort(longValues, stringValues, positions, mIds);
+ binarySort(longValues, isDirs, positions, mIds);
break;
}
@@ -207,18 +212,20 @@
/**
* Sorts model data. Takes three columns of index-corresponded data. The first column is the
- * sort key. Rows are sorted in ascending alphabetical order on the sort key. This code is based
- * on TimSort.binarySort().
+ * sort key. Rows are sorted in ascending alphabetical order on the sort key.
+ * Directories are always shown first. This code is based on TimSort.binarySort().
*
* @param sortKey Data is sorted in ascending alphabetical order.
+ * @param isDirs Array saying whether an item is a directory or not.
* @param positions Cursor positions to be sorted.
* @param ids Model IDs to be sorted.
*/
- private static void binarySort(String[] sortKey, int[] positions, String[] ids) {
+ private static void binarySort(String[] sortKey, boolean[] isDirs, int[] positions, String[] ids) {
final int count = positions.length;
for (int start = 1; start < count; start++) {
final int pivotPosition = positions[start];
final String pivotValue = sortKey[start];
+ final boolean pivotIsDir = isDirs[start];
final String pivotId = ids[start];
int left = 0;
@@ -227,9 +234,18 @@
while (left < right) {
int mid = (left + right) >>> 1;
- final String lhs = pivotValue;
- final String rhs = sortKey[mid];
- final int compare = Shared.compareToIgnoreCaseNullable(lhs, rhs);
+ // Directories always go in front.
+ int compare = 0;
+ final boolean rhsIsDir = isDirs[mid];
+ if (pivotIsDir && !rhsIsDir) {
+ compare = -1;
+ } else if (!pivotIsDir && rhsIsDir) {
+ compare = 1;
+ } else {
+ final String lhs = pivotValue;
+ final String rhs = sortKey[mid];
+ compare = Shared.compareToIgnoreCaseNullable(lhs, rhs);
+ }
if (compare < 0) {
right = mid;
@@ -243,20 +259,24 @@
case 2:
positions[left + 2] = positions[left + 1];
sortKey[left + 2] = sortKey[left + 1];
+ isDirs[left + 2] = isDirs[left + 1];
ids[left + 2] = ids[left + 1];
case 1:
positions[left + 1] = positions[left];
sortKey[left + 1] = sortKey[left];
+ isDirs[left + 1] = isDirs[left];
ids[left + 1] = ids[left];
break;
default:
System.arraycopy(positions, left, positions, left + 1, n);
System.arraycopy(sortKey, left, sortKey, left + 1, n);
+ System.arraycopy(isDirs, left, isDirs, left + 1, n);
System.arraycopy(ids, left, ids, left + 1, n);
}
positions[left] = pivotPosition;
sortKey[left] = pivotValue;
+ isDirs[left] = pivotIsDir;
ids[left] = pivotId;
}
}
@@ -268,17 +288,17 @@
* numerical order on the sort key. This code is based on TimSort.binarySort().
*
* @param sortKey Data is sorted in descending numerical order.
- * @param mimeTypes Corresponding mime types. Directories will be sorted ahead of documents.
+ * @param isDirs Array saying whether an item is a directory or not.
* @param positions Cursor positions to be sorted.
* @param ids Model IDs to be sorted.
*/
private static void binarySort(
- long[] sortKey, String[] mimeTypes, int[] positions, String[] ids) {
+ long[] sortKey, boolean[] isDirs, int[] positions, String[] ids) {
final int count = positions.length;
for (int start = 1; start < count; start++) {
final int pivotPosition = positions[start];
final long pivotValue = sortKey[start];
- final String pivotMime = mimeTypes[start];
+ final boolean pivotIsDir = isDirs[start];
final String pivotId = ids[start];
int left = 0;
@@ -287,13 +307,12 @@
while (left < right) {
int mid = ((left + right) >>> 1);
- // First bucket by mime type. Directories always go in front.
+ // Directories always go in front.
int compare = 0;
- final boolean lhsIsDir = Document.MIME_TYPE_DIR.equals(pivotMime);
- final boolean rhsIsDir = Document.MIME_TYPE_DIR.equals(mimeTypes[mid]);
- if (lhsIsDir && !rhsIsDir) {
+ final boolean rhsIsDir = isDirs[mid];
+ if (pivotIsDir && !rhsIsDir) {
compare = -1;
- } else if (!lhsIsDir && rhsIsDir) {
+ } else if (!pivotIsDir && rhsIsDir) {
compare = 1;
} else {
final long lhs = pivotValue;
@@ -323,24 +342,24 @@
case 2:
positions[left + 2] = positions[left + 1];
sortKey[left + 2] = sortKey[left + 1];
- mimeTypes[left + 2] = mimeTypes[left + 1];
+ isDirs[left + 2] = isDirs[left + 1];
ids[left + 2] = ids[left + 1];
case 1:
positions[left + 1] = positions[left];
sortKey[left + 1] = sortKey[left];
- mimeTypes[left + 1] = mimeTypes[left];
+ isDirs[left + 1] = isDirs[left];
ids[left + 1] = ids[left];
break;
default:
System.arraycopy(positions, left, positions, left + 1, n);
System.arraycopy(sortKey, left, sortKey, left + 1, n);
- System.arraycopy(mimeTypes, left, mimeTypes, left + 1, n);
+ System.arraycopy(isDirs, left, isDirs, left + 1, n);
System.arraycopy(ids, left, ids, left + 1, n);
}
positions[left] = pivotPosition;
sortKey[left] = pivotValue;
- mimeTypes[left] = pivotMime;
+ isDirs[left] = pivotIsDir;
ids[left] = pivotId;
}
}