Remove custom SkSort algorithms.
SortBench shows that SkTQSort and SkTHeapSort are inferior to std::sort.
The difference is small on randomized inputs, but quite significant for
semi-ordered inputs (forward/backward/repeated). There doesn't seem to
to be any compelling advantage to SkTQSort.
Nanobench results: https://screenshot.googleplex.com/9JOLV1d6Z0u
(These performance numbers are from an optimized build my local machine;
it's possible that we might see different results on the test bots.)
Change-Id: Iaf19563041547eae7de2953be249129108f093b1
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/302295
Commit-Queue: John Stiles <johnstiles@google.com>
Reviewed-by: Mike Klein <mtklein@google.com>
diff --git a/src/codec/SkIcoCodec.cpp b/src/codec/SkIcoCodec.cpp
index 0aaf5e0..fd6b5a9 100644
--- a/src/codec/SkIcoCodec.cpp
+++ b/src/codec/SkIcoCodec.cpp
@@ -14,7 +14,6 @@
#include "src/codec/SkIcoCodec.h"
#include "src/codec/SkPngCodec.h"
#include "src/core/SkStreamPriv.h"
-#include "src/core/SkTSort.h"
/*
* Checks the start of the stream to see if the image is an Ico or Cur
@@ -115,13 +114,8 @@
// increasing offset. However, the specification does not indicate that
// they must be stored in this order, so we will not trust that this is the
// case. Here we sort the embedded images by increasing offset.
- struct EntryLessThan {
- bool operator() (Entry a, Entry b) const {
- return a.offset < b.offset;
- }
- };
- EntryLessThan lessThan;
- SkTQSort(directoryEntries, &directoryEntries[numImages - 1], lessThan);
+ std::sort(directoryEntries, directoryEntries + numImages,
+ [](const Entry& a, const Entry& b) { return a.offset < b.offset; });
// Now will construct a candidate codec for each of the embedded images
uint32_t bytesRead = kIcoDirectoryBytes + numImages * kIcoDirEntryBytes;
diff --git a/src/core/SkRegion_path.cpp b/src/core/SkRegion_path.cpp
index af5d2cd..d622eec 100644
--- a/src/core/SkRegion_path.cpp
+++ b/src/core/SkRegion_path.cpp
@@ -12,7 +12,6 @@
#include "src/core/SkRegionPriv.h"
#include "src/core/SkSafeMath.h"
#include "src/core/SkScan.h"
-#include "src/core/SkTSort.h"
// The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
// we may not want to promote this to a "std" routine just yet.
@@ -489,12 +488,6 @@
return count;
}
-struct EdgeLT {
- bool operator()(const Edge& a, const Edge& b) const {
- return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
- }
-};
-
bool SkRegion::getBoundaryPath(SkPath* path) const {
// path could safely be nullptr if we're empty, but the caller shouldn't
// *know* that
@@ -525,7 +518,9 @@
int count = edges.count();
Edge* start = edges.begin();
Edge* stop = start + count;
- SkTQSort<Edge>(start, stop - 1, EdgeLT());
+ std::sort(start, stop, [](const Edge& a, const Edge& b) {
+ return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX;
+ });
Edge* e;
for (e = start; e != stop; e++) {
diff --git a/src/core/SkScan_AAAPath.cpp b/src/core/SkScan_AAAPath.cpp
index 2df03b9..2f4325e 100644
--- a/src/core/SkScan_AAAPath.cpp
+++ b/src/core/SkScan_AAAPath.cpp
@@ -20,7 +20,6 @@
#include "src/core/SkRasterClip.h"
#include "src/core/SkScan.h"
#include "src/core/SkScanPriv.h"
-#include "src/core/SkTSort.h"
#include <utility>
@@ -1019,7 +1018,8 @@
}
static SkAnalyticEdge* sort_edges(SkAnalyticEdge* list[], int count, SkAnalyticEdge** last) {
- SkTQSort(list, list + count - 1);
+ std::sort(list, list + count,
+ [](const SkAnalyticEdge* a, const SkAnalyticEdge* b) { return *a < *b; });
// now make the edges linked in sorted order
for (int i = 1; i < count; ++i) {
diff --git a/src/core/SkScan_Path.cpp b/src/core/SkScan_Path.cpp
index 7668b51..b0eb8ce 100644
--- a/src/core/SkScan_Path.cpp
+++ b/src/core/SkScan_Path.cpp
@@ -18,7 +18,6 @@
#include "src/core/SkRasterClip.h"
#include "src/core/SkRectPriv.h"
#include "src/core/SkScanPriv.h"
-#include "src/core/SkTSort.h"
#include <utility>
@@ -366,20 +365,10 @@
#pragma warning ( pop )
#endif
-static bool operator<(const SkEdge& a, const SkEdge& b) {
- int valuea = a.fFirstY;
- int valueb = b.fFirstY;
-
- if (valuea == valueb) {
- valuea = a.fX;
- valueb = b.fX;
- }
-
- return valuea < valueb;
-}
-
static SkEdge* sort_edges(SkEdge* list[], int count, SkEdge** last) {
- SkTQSort(list, list + count - 1);
+ std::sort(list, list + count, [](const SkEdge* a, const SkEdge* b) {
+ return std::tie(a->fFirstY, a->fX) < std::tie(b->fFirstY, b->fX);
+ });
// now make the edges linked in sorted order
for (int i = 1; i < count; i++) {
diff --git a/src/core/SkTDPQueue.h b/src/core/SkTDPQueue.h
index 569bbcb..d81322d 100644
--- a/src/core/SkTDPQueue.h
+++ b/src/core/SkTDPQueue.h
@@ -9,7 +9,6 @@
#define SkTDPQueue_DEFINED
#include "include/private/SkTDArray.h"
-#include "src/core/SkTSort.h"
#include <utility>
@@ -111,7 +110,7 @@
*/
void sort() {
if (fArray.count() > 1) {
- SkTQSort<T>(fArray.begin(), fArray.end() - 1, LESS);
+ std::sort(fArray.begin(), fArray.end(), LESS);
for (int i = 0; i < fArray.count(); i++) {
this->setIndex(i);
}
diff --git a/src/core/SkTSearch.h b/src/core/SkTSearch.h
index 0466917..098597b 100644
--- a/src/core/SkTSearch.h
+++ b/src/core/SkTSearch.h
@@ -140,7 +140,4 @@
char fStorage[STORAGE+1];
};
-// Helper when calling qsort with a compare proc that has typed its arguments
-#define SkCastForQSort(compare) reinterpret_cast<int (*)(const void*, const void*)>(compare)
-
#endif
diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
deleted file mode 100644
index 1e853b0..0000000
--- a/src/core/SkTSort.h
+++ /dev/null
@@ -1,216 +0,0 @@
-/*
- * Copyright 2006 The Android Open Source Project
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-#ifndef SkTSort_DEFINED
-#define SkTSort_DEFINED
-
-#include "include/core/SkTypes.h"
-#include "include/private/SkTo.h"
-#include "src/core/SkMathPriv.h"
-
-#include <utility>
-
-/* 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
- * from the leaf level up.
- *
- * This version does extra work, in that it copies child to parent on the way down,
- * then copies parent to child on the way back up. When copies are inexpensive,
- * this is an optimization as this sift variant should only be used when
- * the potentially out of place root entry value is expected to be small.
- *
- * @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, 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 && lessThan(array[j-1], array[j])) {
- ++j;
- }
- array[root-1] = array[j-1];
- root = j;
- j = root << 1;
- }
- j = root >> 1;
- while (j >= start) {
- if (lessThan(array[j-1], x)) {
- array[root-1] = array[j-1];
- root = j;
- j = root >> 1;
- } else {
- break;
- }
- }
- array[root-1] = x;
-}
-
-/* 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.
- *
- * @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, 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 && lessThan(array[child-1], array[child])) {
- ++child;
- }
- if (lessThan(x, array[child-1])) {
- array[root-1] = array[child-1];
- root = child;
- child = root << 1;
- } else {
- break;
- }
- }
- array[root-1] = x;
-}
-
-/** Sorts the array of size count using comparator lessThan using a Heap Sort algorithm. Be sure to
- * specialize swap if T has an efficient swap operation.
- *
- * @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(array, i, count, lessThan);
- }
-
- for (size_t i = count - 1; i > 0; --i) {
- using std::swap;
- swap(array[0], array[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) {
- if (!lessThan(*next, *(next - 1))) {
- continue;
- }
- T insert = std::move(*next);
- T* hole = next;
- do {
- *hole = std::move(*(hole - 1));
- --hole;
- } while (left < hole && lessThan(insert, *(hole - 1)));
- *hole = std::move(insert);
- }
-}
-
-///////////////////////////////////////////////////////////////////////////////
-
-template <typename T, typename C>
-static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) {
- using std::swap;
- T pivotValue = *pivot;
- swap(*pivot, *right);
- T* newPivot = left;
- while (left < right) {
- if (lessThan(*left, pivotValue)) {
- swap(*left, *newPivot);
- newPivot += 1;
- }
- left += 1;
- }
- swap(*newPivot, *right);
- return newPivot;
-}
-
-/* Intro Sort is a modified Quick Sort.
- * 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.
- * This implementation recurses on the left region after pivoting and loops on the right,
- * we already limit the stack depth by switching to heap sort,
- * and cache locality on the data appears more important than saving a few stack frames.
- *
- * @param depth at this recursion depth, switch to Heap Sort.
- * @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 SkTIntroSort(int depth, T* left, T* right, C lessThan) {
- while (true) {
- if (right - left < 32) {
- SkTInsertionSort(left, right, lessThan);
- return;
- }
-
- if (depth == 0) {
- SkTHeapSort<T>(left, right - left + 1, lessThan);
- return;
- }
- --depth;
-
- T* pivot = left + ((right - left) >> 1);
- pivot = SkTQSort_Partition(left, right, pivot, lessThan);
-
- SkTIntroSort(depth, left, pivot - 1, lessThan);
- left = pivot + 1;
- }
-}
-
-/** Sorts the region from left to right using comparator lessThan using a Quick Sort algorithm. Be
- * sure to specialize swap if T has an efficient swap operation.
- *
- * @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) {
- if (left >= right) {
- return;
- }
- // Limit Intro Sort recursion depth to no more than 2 * ceil(log2(n)).
- int depth = 2 * SkNextLog2(SkToU32(right - left));
- SkTIntroSort(depth, 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) {
- SkTQSort(left, right, SkTCompareLT<T>());
-}
-
-/** 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
diff --git a/src/gpu/GrDataUtils.cpp b/src/gpu/GrDataUtils.cpp
index 19ab50d..7bdc3b5 100644
--- a/src/gpu/GrDataUtils.cpp
+++ b/src/gpu/GrDataUtils.cpp
@@ -11,6 +11,7 @@
#include "src/core/SkColorSpaceXformSteps.h"
#include "src/core/SkCompressedDataUtils.h"
#include "src/core/SkConvertPixels.h"
+#include "src/core/SkMathPriv.h"
#include "src/core/SkMipMap.h"
#include "src/core/SkTLazy.h"
#include "src/core/SkTraceEvent.h"
diff --git a/src/gpu/GrDrawOpAtlas.cpp b/src/gpu/GrDrawOpAtlas.cpp
index 5c532dd..cb53d0e 100644
--- a/src/gpu/GrDrawOpAtlas.cpp
+++ b/src/gpu/GrDrawOpAtlas.cpp
@@ -8,6 +8,7 @@
#include "src/gpu/GrDrawOpAtlas.h"
#include "include/gpu/GrContext.h"
+#include "src/core/SkMathPriv.h"
#include "src/core/SkOpts.h"
#include "src/gpu/GrContextPriv.h"
#include "src/gpu/GrGpu.h"
diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp
index b3166ac..58fc7be 100644
--- a/src/gpu/GrResourceCache.cpp
+++ b/src/gpu/GrResourceCache.cpp
@@ -11,10 +11,10 @@
#include "include/private/GrSingleOwner.h"
#include "include/private/SkTo.h"
#include "include/utils/SkRandom.h"
+#include "src/core/SkMathPriv.h"
#include "src/core/SkMessageBus.h"
#include "src/core/SkOpts.h"
#include "src/core/SkScopeExit.h"
-#include "src/core/SkTSort.h"
#include "src/gpu/GrCaps.h"
#include "src/gpu/GrContextPriv.h"
#include "src/gpu/GrGpuResourceCacheAccess.h"
@@ -689,8 +689,8 @@
fPurgeableQueue.pop();
}
- SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1,
- CompareTimestamp);
+ std::sort(fNonpurgeableResources.begin(), fNonpurgeableResources.end(),
+ CompareTimestamp);
// Pick resources out of the purgeable and non-purgeable arrays based on lowest
// timestamp and assign new timestamps.
diff --git a/src/gpu/ccpr/GrCCAtlas.cpp b/src/gpu/ccpr/GrCCAtlas.cpp
index 8cf105e..f6f8bbd 100644
--- a/src/gpu/ccpr/GrCCAtlas.cpp
+++ b/src/gpu/ccpr/GrCCAtlas.cpp
@@ -8,6 +8,7 @@
#include "src/gpu/ccpr/GrCCAtlas.h"
#include "src/core/SkIPoint16.h"
+#include "src/core/SkMathPriv.h"
#include "src/gpu/GrOnFlushResourceProvider.h"
#include "src/gpu/ccpr/GrCCPathCache.h"
diff --git a/src/gpu/gl/GrGLCaps.cpp b/src/gpu/gl/GrGLCaps.cpp
index ee04a7e..6197f15 100644
--- a/src/gpu/gl/GrGLCaps.cpp
+++ b/src/gpu/gl/GrGLCaps.cpp
@@ -10,7 +10,6 @@
#include "include/gpu/GrContextOptions.h"
#include "src/core/SkCompressedDataUtils.h"
#include "src/core/SkTSearch.h"
-#include "src/core/SkTSort.h"
#include "src/gpu/GrBackendUtils.h"
#include "src/gpu/GrProgramDesc.h"
#include "src/gpu/GrRenderTargetProxyPriv.h"
diff --git a/src/gpu/gl/GrGLExtensions.cpp b/src/gpu/gl/GrGLExtensions.cpp
index 3f9dbfc..d03bc55 100644
--- a/src/gpu/gl/GrGLExtensions.cpp
+++ b/src/gpu/gl/GrGLExtensions.cpp
@@ -10,7 +10,6 @@
#include "src/gpu/gl/GrGLUtil.h"
#include "src/core/SkTSearch.h"
-#include "src/core/SkTSort.h"
#include "src/utils/SkJSONWriter.h"
namespace { // This cannot be static because it is used as a template parameter.
@@ -117,8 +116,7 @@
eat_space_sep_strings(&fStrings, extensions);
}
if (!fStrings.empty()) {
- SkTLessFunctionToFunctorAdaptor<SkString, extension_compare> cmp;
- SkTQSort(&fStrings.front(), &fStrings.back(), cmp);
+ std::sort(fStrings.begin(), fStrings.end(), extension_compare);
}
fInitialized = true;
return true;
@@ -140,8 +138,7 @@
// most a handful of times when our test programs start.
fStrings.removeShuffle(idx);
if (idx != fStrings.count()) {
- SkTLessFunctionToFunctorAdaptor<SkString, extension_compare> cmp;
- SkTInsertionSort(&(fStrings.operator[](idx)), &fStrings.back(), cmp);
+ std::sort(fStrings.begin() + idx, fStrings.end(), extension_compare);
}
return true;
}
@@ -151,9 +148,8 @@
if (idx < 0) {
// This is not the most effecient approach since we end up looking at all of the
// extensions after the add
- fStrings.emplace_back(ext);
- SkTLessFunctionToFunctorAdaptor<SkString, extension_compare> cmp;
- SkTInsertionSort(&fStrings.front(), &fStrings.back(), cmp);
+ fStrings.push_back(SkString(ext));
+ std::sort(fStrings.begin(), fStrings.end(), extension_compare);
}
}
diff --git a/src/gpu/mock/GrMockCaps.h b/src/gpu/mock/GrMockCaps.h
index 6548aa6..adb7372 100644
--- a/src/gpu/mock/GrMockCaps.h
+++ b/src/gpu/mock/GrMockCaps.h
@@ -9,6 +9,7 @@
#define GrMockCaps_DEFINED
#include "include/gpu/mock/GrMockTypes.h"
+#include "src/core/SkMathPriv.h"
#include "src/gpu/GrCaps.h"
#include "src/gpu/SkGr.h"
diff --git a/src/gpu/vk/GrVkExtensions.cpp b/src/gpu/vk/GrVkExtensions.cpp
index b9990e6..62f9d06 100644
--- a/src/gpu/vk/GrVkExtensions.cpp
+++ b/src/gpu/vk/GrVkExtensions.cpp
@@ -11,7 +11,6 @@
#include "include/gpu/vk/GrVkBackendContext.h"
#include "src/core/SkTSearch.h"
-#include "src/core/SkTSort.h"
// finds the index of ext in infos or a negative result if ext is not found.
static int find_info(const SkTArray<GrVkExtensions::Info>& infos, const char ext[]) {
@@ -39,22 +38,20 @@
const char* const* instanceExtensions,
uint32_t deviceExtensionCount,
const char* const* deviceExtensions) {
- SkTLessFunctionToFunctorAdaptor<GrVkExtensions::Info, extension_compare> cmp;
-
for (uint32_t i = 0; i < instanceExtensionCount; ++i) {
const char* extension = instanceExtensions[i];
// if not already in the list, add it
if (find_info(fExtensions, extension) < 0) {
- fExtensions.push_back() = Info(extension);
- SkTQSort(&fExtensions.front(), &fExtensions.back(), cmp);
+ fExtensions.push_back(Info(extension));
+ std::stable_sort(fExtensions.begin(), fExtensions.end(), extension_compare);
}
}
for (uint32_t i = 0; i < deviceExtensionCount; ++i) {
const char* extension = deviceExtensions[i];
// if not already in the list, add it
if (find_info(fExtensions, extension) < 0) {
- fExtensions.push_back() = Info(extension);
- SkTQSort(&fExtensions.front(), &fExtensions.back(), cmp);
+ fExtensions.push_back(Info(extension));
+ std::stable_sort(fExtensions.begin(), fExtensions.end(), extension_compare);
}
}
this->getSpecVersions(getProc, instance, physDev);
diff --git a/src/pathops/SkOpAngle.cpp b/src/pathops/SkOpAngle.cpp
index 8efdc5d..b2cbc43 100644
--- a/src/pathops/SkOpAngle.cpp
+++ b/src/pathops/SkOpAngle.cpp
@@ -4,7 +4,6 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-#include "src/core/SkTSort.h"
#include "src/pathops/SkOpAngle.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkPathOpsCurve.h"
@@ -1026,7 +1025,7 @@
}
testTs[testCount++] = startT;
testTs[testCount++] = endT;
- SkTQSort<double>(testTs, &testTs[testCount - 1]);
+ std::sort(testTs, testTs + testCount);
double bestSide = 0;
int testCases = (testCount << 1) - 1;
index = 0;
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 508c324..14e4ccd 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -4,7 +4,6 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-#include "src/core/SkTSort.h"
#include "src/pathops/SkOpContour.h"
#include "src/pathops/SkPathWriter.h"
#include "src/pathops/SkReduceOrder.h"
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index e5a55fe..fff2293 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -8,7 +8,6 @@
#define SkOpContour_DEFINED
#include "include/private/SkTDArray.h"
-#include "src/core/SkTSort.h"
#include "src/pathops/SkOpSegment.h"
enum class SkOpRayDir;
diff --git a/src/pathops/SkOpEdgeBuilder.cpp b/src/pathops/SkOpEdgeBuilder.cpp
index 757fa31..fa2a336 100644
--- a/src/pathops/SkOpEdgeBuilder.cpp
+++ b/src/pathops/SkOpEdgeBuilder.cpp
@@ -277,7 +277,7 @@
bool fCanAdd;
} splits[4];
SkASSERT(SK_ARRAY_COUNT(splits) == SK_ARRAY_COUNT(splitT) + 1);
- SkTQSort(splitT, &splitT[breaks - 1]);
+ std::sort(splitT, splitT + breaks);
for (int index = 0; index <= breaks; ++index) {
Splitsville* split = &splits[index];
split->fT[0] = index ? splitT[index - 1] : 0;
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index a4d0fcd..e51a53b 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -6,7 +6,6 @@
*/
#include "include/private/SkMacros.h"
-#include "src/core/SkTSort.h"
#include "src/pathops/SkAddIntersections.h"
#include "src/pathops/SkOpCoincidence.h"
#include "src/pathops/SkOpEdgeBuilder.h"
@@ -165,7 +164,8 @@
return false;
}
if (count > 1) {
- SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
+ std::sort(list.begin(), list.end(),
+ [](const SkOpContour* a, const SkOpContour* b) { return *a < *b; });
}
contour = list[0];
SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
diff --git a/src/pathops/SkPathOpsCubic.cpp b/src/pathops/SkPathOpsCubic.cpp
index 1275fab..3470681 100644
--- a/src/pathops/SkPathOpsCubic.cpp
+++ b/src/pathops/SkPathOpsCubic.cpp
@@ -5,7 +5,6 @@
* found in the LICENSE file.
*/
#include "src/core/SkGeometry.h"
-#include "src/core/SkTSort.h"
#include "src/pathops/SkLineParameters.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
@@ -344,7 +343,7 @@
extremeTs[extrema++] = 0;
extremeTs[extrema] = 1;
SkASSERT(extrema < 6);
- SkTQSort(extremeTs, extremeTs + extrema);
+ std::sort(extremeTs, extremeTs + extrema + 1);
int validCount = 0;
for (int index = 0; index < extrema; ) {
double min = extremeTs[index];
diff --git a/src/pathops/SkPathOpsTSect.cpp b/src/pathops/SkPathOpsTSect.cpp
index 674c635..59b5059 100644
--- a/src/pathops/SkPathOpsTSect.cpp
+++ b/src/pathops/SkPathOpsTSect.cpp
@@ -1754,13 +1754,12 @@
}
void finish(SkIntersections* intersections) const {
- SkSTArray<SkDCubic::kMaxIntersections * 3,
- const SkClosestRecord*, true> closestPtrs;
+ SkSTArray<SkDCubic::kMaxIntersections * 3, const SkClosestRecord*, true> closestPtrs;
for (int index = 0; index < fUsed; ++index) {
closestPtrs.push_back(&fClosest[index]);
}
- SkTQSort<const SkClosestRecord >(closestPtrs.begin(), closestPtrs.end()
- - 1);
+ std::sort(closestPtrs.begin(), closestPtrs.end(),
+ [](const SkClosestRecord* a, const SkClosestRecord* b) { return *a < *b; });
for (int index = 0; index < fUsed; ++index) {
const SkClosestRecord* test = closestPtrs[index];
test->addIntersection(intersections);
diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h
index 587209d..25f1ef2 100644
--- a/src/pathops/SkPathOpsTSect.h
+++ b/src/pathops/SkPathOpsTSect.h
@@ -9,7 +9,6 @@
#include "include/private/SkMacros.h"
#include "src/core/SkArenaAlloc.h"
-#include "src/core/SkTSort.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkPathOpsBounds.h"
#include "src/pathops/SkPathOpsRect.h"
diff --git a/src/pathops/SkPathOpsWinding.cpp b/src/pathops/SkPathOpsWinding.cpp
index 4eb7298..658bf43 100644
--- a/src/pathops/SkPathOpsWinding.cpp
+++ b/src/pathops/SkPathOpsWinding.cpp
@@ -264,9 +264,9 @@
hit = hit->fNext;
}
int count = sorted.count();
- SkTQSort(sorted.begin(), sorted.end() - 1, xy_index(dir)
- ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
- : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
+ std::sort(sorted.begin(), sorted.end(),
+ xy_index(dir) ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y
+ : less_than(dir) ? hit_compare_x : reverse_hit_compare_x);
// verify windings
#if DEBUG_WINDING
SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__,
diff --git a/src/pathops/SkPathWriter.cpp b/src/pathops/SkPathWriter.cpp
index 37264e4..1d7acd4 100644
--- a/src/pathops/SkPathWriter.cpp
+++ b/src/pathops/SkPathWriter.cpp
@@ -4,7 +4,6 @@
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
-#include "src/core/SkTSort.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsPoint.h"
@@ -290,7 +289,7 @@
rRow += endCount;
}
SkASSERT(dIndex == entries);
- SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
+ std::sort(sortedDist.begin(), sortedDist.end(), DistanceLessThan(distances.begin()));
int remaining = linkCount; // number of start/end pairs
for (rIndex = 0; rIndex < entries; ++rIndex) {
int pair = sortedDist[rIndex];
diff --git a/src/utils/win/SkWGL_win.cpp b/src/utils/win/SkWGL_win.cpp
index 7461f66..8cc8892 100644
--- a/src/utils/win/SkWGL_win.cpp
+++ b/src/utils/win/SkWGL_win.cpp
@@ -13,7 +13,6 @@
#include "include/private/SkOnce.h"
#include "include/private/SkTDArray.h"
#include "src/core/SkTSearch.h"
-#include "src/core/SkTSort.h"
bool SkWGLExtensions::hasExtension(HDC dc, const char* ext) const {
if (nullptr == this->fGetExtensionsString) {
@@ -150,9 +149,7 @@
rankedFormats[i].fSampleCnt = std::max(1, numSamples);
rankedFormats[i].fChoosePixelFormatRank = i;
}
- SkTQSort(rankedFormats.begin(),
- rankedFormats.begin() + rankedFormats.count() - 1,
- SkTLessFunctionToFunctorAdaptor<PixelFormat, pf_less>());
+ std::sort(rankedFormats.begin(), rankedFormats.end(), pf_less);
int idx = SkTSearch<PixelFormat, pf_less>(rankedFormats.begin(),
rankedFormats.count(),
desiredFormat,