Avoid possible O(n) stack space use by skqsort.
https://codereview.appspot.com/7222043/
git-svn-id: http://skia.googlecode.com/svn/trunk@7470 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 32f531f..88fc079 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -261,8 +261,7 @@
// Evaluate each sort
for (int j = 0; j < 2; ++j) {
-
- SkQSort(sorts[i][j], children, children + fMaxChildren, &RectLessThan);
+ SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
// Evaluate each split index
for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
@@ -299,7 +298,7 @@
// replicate the sort of the winning distribution, (we can skip this if the last
// sort ended up being best)
if (!(axis == 1 && sortSide == 1)) {
- SkQSort(sorts[axis][sortSide], children, children + fMaxChildren, &RectLessThan);
+ SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
}
return fMinChildren - 1 + k;
@@ -325,7 +324,7 @@
return out;
} else {
// First we sort the whole list by y coordinates
- SkQSort<int, Branch>(level, branches->begin(), branches->end() - 1, &RectLessY);
+ SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
int numBranches = branches->count() / fMaxChildren;
int remainder = branches->count() % fMaxChildren;
@@ -357,8 +356,7 @@
}
// Now we sort horizontal strips of rectangles by their x coords
- SkQSort<int, Branch>(level, branches->begin() + begin, branches->begin() + end - 1,
- &RectLessX);
+ SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
int incrementBy = fMaxChildren;
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 139cc61..0a53667 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -119,19 +119,28 @@
typedef int32_t SkIRect::*SortSide;
// Helper for sorting our children arrays by sides of their rects
- static bool RectLessThan(SortSide const& side, const Branch lhs, const Branch rhs) {
- return lhs.fBounds.*side < rhs.fBounds.*side;
- }
+ struct RectLessThan {
+ RectLessThan(SkRTree::SortSide side) : fSide(side) { }
+ bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
+ return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
+ }
+ private:
+ const SkRTree::SortSide fSide;
+ };
- static bool RectLessX(int&, const Branch lhs, const Branch rhs) {
- return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
- ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
- }
+ struct RectLessX {
+ bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
+ return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
+ ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
+ }
+ };
- static bool RectLessY(int&, const Branch lhs, const Branch rhs) {
- return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
- ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
- }
+ struct RectLessY {
+ bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
+ return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
+ ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
+ }
+ };
SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio);
diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
index 820e364..8d4403c 100644
--- a/src/core/SkTSort.h
+++ b/src/core/SkTSort.h
@@ -11,8 +11,22 @@
#define SkTSort_DEFINED
#include "SkTypes.h"
-/**
- * Sifts a broken heap. The input array is a heap from root to bottom
+#include "SkMath.h"
+#include <stddef.h>
+
+/* A comparison functor which performs the comparison 'a < b'. */
+template <typename T> struct SkTCompareLT {
+ bool operator()(const T a, const T b) const { return a < b; }
+};
+
+/* A comparison functor which performs the comparison '*a < *b'. */
+template <typename T> struct SkTPointerCompareLT {
+ bool operator()(const T* a, const T* b) const { return *a < *b; }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+/* Sifts a broken heap. The input array is a heap from root to bottom
* except that the root entry may be out of place.
*
* Sinks a hole from array[root] to leaf and then sifts the original array[root] element
@@ -26,12 +40,13 @@
* @param root the one based index into array of the out-of-place root of the heap.
* @param bottom the one based index in the array of the last entry in the heap.
*/
-template <typename T> void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom) {
+template <typename T, typename C>
+void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) {
T x = array[root-1];
size_t start = root;
size_t j = root << 1;
while (j <= bottom) {
- if (j < bottom && array[j-1] < array[j]) {
+ if (j < bottom && lessThan(array[j-1], array[j])) {
++j;
}
array[root-1] = array[j-1];
@@ -40,7 +55,7 @@
}
j = root >> 1;
while (j >= start) {
- if (array[j-1] < x) {
+ if (lessThan(array[j-1], x)) {
array[root-1] = array[j-1];
root = j;
j = root >> 1;
@@ -51,8 +66,7 @@
array[root-1] = x;
}
-/**
- * Sifts a broken heap. The input array is a heap from root to bottom
+/* Sifts a broken heap. The input array is a heap from root to bottom
* except that the root entry may be out of place.
*
* Sifts the array[root] element from the root down.
@@ -60,14 +74,15 @@
* @param root the one based index into array of the out-of-place root of the heap.
* @param bottom the one based index in the array of the last entry in the heap.
*/
-template <typename T> void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom) {
+template <typename T, typename C>
+void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) {
T x = array[root-1];
size_t child = root << 1;
while (child <= bottom) {
- if (child < bottom && array[child-1] < array[child]) {
+ if (child < bottom && lessThan(array[child-1], array[child])) {
++child;
}
- if (x < array[child-1]) {
+ if (lessThan(x, array[child-1])) {
array[root-1] = array[child-1];
root = child;
child = root << 1;
@@ -78,26 +93,52 @@
array[root-1] = x;
}
-template <typename T> void SkTHeapSort(T array[], size_t count) {
+/** Sorts the array of size count using comparator lessThan using a Heap Sort algorithm
+ *
+ * @param array the array to be sorted.
+ * @param count the number of elements in the array.
+ * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
+ */
+template <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) {
for (size_t i = count >> 1; i > 0; --i) {
- SkTHeapSort_SiftDown<T>(array, i, count);
+ SkTHeapSort_SiftDown(array, i, count, lessThan);
}
for (size_t i = count - 1; i > 0; --i) {
SkTSwap<T>(array[0], array[i]);
- SkTHeapSort_SiftUp(array, 1, i);
+ SkTHeapSort_SiftUp(array, 1, i, lessThan);
+ }
+}
+
+/** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */
+template <typename T> void SkTHeapSort(T array[], size_t count) {
+ SkTHeapSort(array, count, SkTCompareLT<T>());
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+/** Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm. */
+template <typename T, typename C> static void SkTInsertionSort(T* left, T* right, C lessThan) {
+ for (T* next = left + 1; next <= right; ++next) {
+ T insert = *next;
+ T* hole = next;
+ while (left < hole && lessThan(insert, *(hole - 1))) {
+ *hole = *(hole - 1);
+ --hole;
+ }
+ *hole = insert;
}
}
///////////////////////////////////////////////////////////////////////////////
-template <typename T>
-static T** SkTQSort_Partition(T** left, T** right, T** pivot) {
- T* pivotValue = *pivot;
+template <typename T, typename C>
+static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) {
+ T pivotValue = *pivot;
SkTSwap(*pivot, *right);
- T** newPivot = left;
+ T* newPivot = left;
while (left < right) {
- if (**left < *pivotValue) {
+ if (lessThan(*left, pivotValue)) {
SkTSwap(*left, *newPivot);
newPivot += 1;
}
@@ -107,74 +148,62 @@
return newPivot;
}
-template <typename T> void SkTQSort(T** left, T** right) {
+/* Intro Sort is a modified Quick Sort.
+ * It recurses on the smaller region after pivoting and loops on the larger.
+ * When the region to be sorted is a small constant size it uses Insertion Sort.
+ * When depth becomes zero, it switches over to Heap Sort.
+ */
+template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) {
while (left < right) {
- T** pivot = left + ((right - left) >> 1);
- pivot = SkTQSort_Partition(left, right, pivot);
+ if (depth == 0) {
+ SkTHeapSort<T>(left, right - left + 1, lessThan);
+ return;
+ }
+ --depth;
- if (right - pivot > pivot - left) {
- SkTQSort(left, pivot - 1);
+ T* pivot = left + ((right - left) >> 1);
+ pivot = SkTQSort_Partition(left, right, pivot, lessThan);
+
+ ptrdiff_t leftSize = pivot - left;
+ ptrdiff_t rightSize = right - pivot;
+ if (leftSize < rightSize) {
+ if (leftSize < 8) {
+ SkTInsertionSort(left, pivot - 1, lessThan);
+ } else {
+ SkTIntroSort(depth, left, pivot - 1, lessThan);
+ }
left = pivot + 1;
} else {
- SkTQSort(pivot + 1, right);
+ if (rightSize < 8) {
+ SkTInsertionSort(pivot + 1, right, lessThan);
+ } else {
+ SkTIntroSort(depth, pivot + 1, right, lessThan);
+ }
right = pivot - 1;
}
}
}
-template <typename T>
-static T* SkTQSort_Partition(T* left, T* right, T* pivot) {
- T pivotValue = *pivot;
- SkTSwap(*pivot, *right);
- T* newPivot = left;
- while (left < right) {
- if (*left < pivotValue) {
- SkTSwap(*left, *newPivot);
- newPivot += 1;
- }
- left += 1;
- }
- SkTSwap(*newPivot, *right);
- return newPivot;
+/** Sorts the region from left to right using comparator lessThan using a Quick Sort algorithm.
+ *
+ * @param left the beginning of the region to be sorted.
+ * @param right the end of the region to be sorted (inclusive).
+ * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
+ */
+template <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) {
+ ptrdiff_t size = right - left;
+ int depth = SkNextLog2(SkToU32(size));
+ SkTIntroSort(depth * 2, left, right, lessThan);
}
+/** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */
template <typename T> void SkTQSort(T* left, T* right) {
- if (left >= right) {
- return;
- }
- T* pivot = left + ((right - left) >> 1);
- pivot = SkTQSort_Partition(left, right, pivot);
- SkTQSort(left, pivot - 1);
- SkTQSort(pivot + 1, right);
+ SkTQSort(left, right, SkTCompareLT<T>());
}
-template <typename S, typename T>
-static T* SkTQSort_Partition(S& context, T* left, T* right, T* pivot,
- bool (*lessThan)(S&, const T, const T)) {
- T pivotValue = *pivot;
- SkTSwap(*pivot, *right);
- T* newPivot = left;
- while (left < right) {
- if (lessThan(context, *left, pivotValue)) {
- SkTSwap(*left, *newPivot);
- newPivot += 1;
- }
- left += 1;
- }
- SkTSwap(*newPivot, *right);
- return newPivot;
-}
-
-template <typename S, typename T>
-void SkQSort(S& context, T* left, T* right,
- bool (*lessThan)(S& , const T, const T)) {
- if (left >= right) {
- return;
- }
- T* pivot = left + ((right - left) >> 1);
- pivot = SkTQSort_Partition(context, left, right, pivot, lessThan);
- SkQSort(context, left, pivot - 1, lessThan);
- SkQSort(context, pivot + 1, right, lessThan);
+/** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */
+template <typename T> void SkTQSort(T** left, T** right) {
+ SkTQSort(left, right, SkTPointerCompareLT<T>());
}
#endif