diff mbox series

Introduce qsort_range interface for GCC vector

Message ID DB5PR0801MB27427080EF52F920D24BF223E74F0@DB5PR0801MB2742.eurprd08.prod.outlook.com
State New
Headers show
Series Introduce qsort_range interface for GCC vector | expand

Commit Message

Bin Cheng Oct. 16, 2017, 2:53 p.m. UTC 
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.cheng@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.

Comments

Richard Biener Oct. 17, 2017, 1 p.m. UTC | #1 
On Mon, Oct 16, 2017 at 4:53 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> 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?

I think you want

  gcc_checking_assert (e >= s && e < length ());
  if (e - s + 1 > 1)
    ::qsort (...);

so elide qsort for 1 element and do the validity verification with a
checking assert.

Ok with that change.

Richard.

> Thanks,
> bin
> 2017-10-13  Bin Cheng  <bin.cheng@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.
diff mbox series

Patch

From a6aa2866fb067628f63f508e9314c3a092b6055c Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@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