From 1e4209e3871493ccfb09e43634d4082f49c227be Mon Sep 17 00:00:00 2001
From: John Reck <jreck@google.com>
Date: Wed, 1 Jul 2015 09:54:47 -0700
Subject: Use std::sort instead of quickSortX

Bug: 22208220

Libcxx has a really good sort algorithm, use that
instead. This speeds up shadow tesellation by about 10%.

Also less code

Change-Id: Iaad424187121d7644076f94ba8a3cf4c110da2f2
---
 libs/hwui/SpotShadow.cpp | 35 +++++------------------------------
 1 file changed, 5 insertions(+), 30 deletions(-)

diff --git a/libs/hwui/SpotShadow.cpp b/libs/hwui/SpotShadow.cpp
index db3c2d9..b8c9804 100644
--- a/libs/hwui/SpotShadow.cpp
+++ b/libs/hwui/SpotShadow.cpp
@@ -48,6 +48,7 @@
 #define TRANSFORMED_PENUMBRA_ALPHA 1.0f
 #define TRANSFORMED_UMBRA_ALPHA 0.0f
 
+#include <algorithm>
 #include <math.h>
 #include <stdlib.h>
 #include <utils/Log.h>
@@ -145,7 +146,10 @@ static float rayIntersectPoints(const Vector2& rayOrigin, float dx, float dy,
  * @param pointsLength the number of vertices of the polygon.
  */
 void SpotShadow::xsort(Vector2* points, int pointsLength) {
-    quicksortX(points, 0, pointsLength - 1);
+    auto cmp = [](const Vector2& a, const Vector2& b) -> bool {
+        return a.x < b.x;
+    };
+    std::sort(points, points + pointsLength, cmp);
 }
 
 /**
@@ -273,35 +277,6 @@ void SpotShadow::quicksortCirc(Vector2* points, int low, int high,
 }
 
 /**
- * Sort points by x axis
- *
- * @param points points to sort
- * @param low start index
- * @param high end index
- */
-void SpotShadow::quicksortX(Vector2* points, int low, int high) {
-    int i = low, j = high;
-    int p = low + (high - low) / 2;
-    float pivot = points[p].x;
-    while (i <= j) {
-        while (points[i].x < pivot) {
-            i++;
-        }
-        while (points[j].x > pivot) {
-            j--;
-        }
-
-        if (i <= j) {
-            swap(points, i, j);
-            i++;
-            j--;
-        }
-    }
-    if (low < j) quicksortX(points, low, j);
-    if (i < high) quicksortX(points, i, high);
-}
-
-/**
  * Test whether a point is inside the polygon.
  *
  * @param testPoint the point to test
-- 
cgit v1.1