regalloc: hand-roll qsort (bikeshedding...)

1 files changed, 31 insertions, 9 deletions

diff --git a/regalloc.c b/regalloc.c
index 1935e61..2a878d0 100644
--- a/regalloc.c
+++ b/regalloc.c
@@ -730,13 +730,6 @@ buildintervals(struct rega *ra)
    }
 }
 
-static int
-cmppinterval(void *a, void *b)
-{
-   struct interval **la = a, **lb = b;
-   return (int)itrange(*la, 0).from - (int)itrange(*lb, 0).from;
-}
-
 static bool
 itcontainspos(const struct interval *it, int pos)
 {
@@ -748,6 +741,36 @@ itcontainspos(const struct interval *it, int pos)
    return 0;
 }
 
+/* quicksort */
+static void
+sortintervals(struct interval **xs, int lo, int hi)
+{
+   assert(lo >= 0 && hi >= 0);
+   while (lo < hi) {
+      /* partition */
+      int i = lo - 1, p = hi + 1,
+          pivot = itrange(xs[lo], 0).from;
+      for (;;) {
+         struct interval *tmp;
+         do ++i; while (itrange(xs[i], 0).from < pivot);
+         do --p; while (itrange(xs[p], 0).from > pivot);
+         if (i >= p) break;
+         /* swap */
+         tmp = xs[i];
+         xs[i] = xs[p];
+         xs[p] = tmp;
+      }
+      /* recur */
+      if (p + 1 >= hi) {
+         hi = p;
+      } else {
+         if (lo < p)
+            sortintervals(xs, lo, p);
+         lo = p + 1;
+      }
+   }
+}
+
 static void
 linearscan(struct rega *ra)
 {
@@ -758,7 +781,6 @@ linearscan(struct rega *ra)
 
    /* sort intervals */
    {
-      extern void qsort(void *p, size_t n, size_t size, int (*)(void *, void *));
       extern int ninstr;
       unhandled = xcalloc(sizeof *unhandled * intervals->count);
 
@@ -771,7 +793,7 @@ linearscan(struct rega *ra)
          free(unhandled);
          return;
       }
-      qsort(unhandled, nunhandled, sizeof *unhandled, cmppinterval);
+      sortintervals(unhandled, 0, nunhandled-1);
    }
 
    /* LINEAR SCAN */