[PATCH GCC]Introduce qsort_range interface for GCC vector

[Bin Cheng]

Hi,
I was asked by Richi to replace insertion sort with qsort_range in loop
nest distribution patch.  Although I believe stable sort (thus insertion)
sort is needed in that case, I also added qsort_range interface in vec.h.
The new interface might be useful in other places.
Bootstrap and test on x86_64 and AArch64 with other patches.  Is it OK?

Thanks,
bin
2017-10-13  Bin Cheng  <bin.ch...@arm.com>

        * vec.h (struct GTY((user)) vec<T, A, vl_embed>::qsort_range): New
        member function.
        (struct vec<T, va_heap, vl_ptr>): New member function.
From a6aa2866fb067628f63f508e9314c3a092b6055c Mon Sep 17 00:00:00 2001
From: Bin Cheng <binch...@e108451-lin.cambridge.arm.com>
Date: Fri, 13 Oct 2017 13:55:03 +0100
Subject: [PATCH 7/8] vec-qsort_range-20171013.txt

---
 gcc/vec.h | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/gcc/vec.h b/gcc/vec.h
index cbdd439..f49177d 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -497,6 +497,7 @@ public:
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
+  void qsort_range (unsigned, unsigned, int (*) (const void *, const void *));
   T *bsearch (const void *key, int (*compar)(const void *, const void *));
   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
   bool contains (const T &search) const;
@@ -974,6 +975,20 @@ vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
 }
 
 
+/* Sort the contents within range [S, E] of this vector with qsort.  Both
+   S and E should be within [0, length).  CMP is the comparison function
+   to pass to qsort.  */
+
+template<typename T, typename A>
+inline void
+vec<T, A, vl_embed>::qsort_range (unsigned s, unsigned e,
+				  int (*cmp) (const void *, const void *))
+{
+  if (e > s && length () > e)
+    ::qsort (&(*this)[s], e - s + 1, sizeof (T), cmp);
+}
+
+
 /* Search the contents of the sorted vector with a binary search.
    CMP is the comparison function to pass to bsearch.  */
 
@@ -1260,6 +1275,7 @@ public:
   void unordered_remove (unsigned);
   void block_remove (unsigned, unsigned);
   void qsort (int (*) (const void *, const void *));
+  void qsort_range (unsigned, unsigned, int (*) (const void *, const void *));
   T *bsearch (const void *key, int (*compar)(const void *, const void *));
   unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
   bool contains (const T &search) const;
@@ -1736,6 +1752,20 @@ vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *))
 }
 
 
+/* Sort the contents within range [S, E] of this vector with qsort.  Both
+   S and E should be within [0, length).  CMP is the comparison function
+   to pass to qsort.  */
+
+template<typename T>
+inline void
+vec<T, va_heap, vl_ptr>::qsort_range (unsigned s, unsigned e,
+				      int (*cmp) (const void *, const void *))
+{
+  if (m_vec)
+    m_vec->qsort_range (s, e, cmp);
+}
+
+
 /* Search the contents of the sorted vector with a binary search.
    CMP is the comparison function to pass to bsearch.  */
 
-- 
1.9.1