From 10cb2990800fb4ab281613915395366b1d0960c4 Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Wed, 27 Mar 2013 12:27:40 +0100
Subject: [PATCH] add isl_*_list_sort

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 doc/user.pod       |  5 +++++
 include/isl/list.h |  5 +++++
 isl_list_templ.c   | 51 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 60 insertions(+), 1 deletion(-)

diff --git a/doc/user.pod b/doc/user.pod
index a33887cf..6ab35070 100644
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -3105,6 +3105,11 @@ Lists can be created, copied, modified and freed using the following functions.
 	__isl_give isl_set_list *isl_set_list_concat(
 		__isl_take isl_set_list *list1,
 		__isl_take isl_set_list *list2);
+	__isl_give isl_set_list *isl_set_list_sort(
+		__isl_take isl_set_list *list,
+		int (*cmp)(__isl_keep isl_set *a,
+			__isl_keep isl_set *b, void *user),
+		void *user);
 	void *isl_set_list_free(__isl_take isl_set_list *list);
 
 C<isl_set_list_alloc> creates an empty list with a capacity for
diff --git a/include/isl/list.h b/include/isl/list.h
index 0de7d1ce..d13987ae 100644
--- a/include/isl/list.h
+++ b/include/isl/list.h
@@ -48,6 +48,11 @@ __isl_give struct isl_##EL##_list *isl_##EL##_list_set_##EL(		\
 int isl_##EL##_list_foreach(__isl_keep isl_##EL##_list *list,		\
 	int (*fn)(__isl_take struct isl_##EL *el, void *user),		\
 	void *user);							\
+__isl_give isl_##EL##_list *isl_##EL##_list_sort(			\
+	__isl_take isl_##EL##_list *list,				\
+	int (*cmp)(__isl_keep struct isl_##EL *a,			\
+		__isl_keep struct isl_##EL *b,				\
+		void *user), void *user);				\
 __isl_give isl_printer *isl_printer_print_##EL##_list(			\
 	__isl_take isl_printer *p, __isl_keep isl_##EL##_list *list);	\
 void isl_##EL##_list_dump(__isl_keep isl_##EL##_list *list);
diff --git a/isl_list_templ.c b/isl_list_templ.c
index 0af5b763..5e861b1d 100644
--- a/isl_list_templ.c
+++ b/isl_list_templ.c
@@ -1,7 +1,7 @@
 /*
  * Copyright 2008-2009 Katholieke Universiteit Leuven
  * Copyright 2011      INRIA Saclay
- * Copyright 2012      Ecole Normale Superieure
+ * Copyright 2012-2013 Ecole Normale Superieure
  *
  * Use of this software is governed by the MIT license
  *
@@ -12,6 +12,8 @@
  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  */
 
+#include <isl_sort.h>
+
 #define xCAT(A,B) A ## B
 #define CAT(A,B) xCAT(A,B)
 #undef EL
@@ -20,6 +22,8 @@
 #define FN(TYPE,NAME) xFN(TYPE,NAME)
 #define xLIST(EL) EL ## _list
 #define LIST(EL) xLIST(EL)
+#define xS(TYPE,NAME) struct TYPE ## _ ## NAME
+#define S(TYPE,NAME) xS(TYPE,NAME)
 
 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
 {
@@ -283,6 +287,51 @@ int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
 	return 0;
 }
 
+/* Internal data structure for isl_*_list_sort.
+ *
+ * "cmp" is the original comparison function.
+ * "user" is a user provided pointer that should be passed to "cmp".
+ */
+S(LIST(EL),sort_data) {
+	int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
+	void *user;
+};
+
+/* Compare two entries of an isl_*_list based on the user provided
+ * comparison function on pairs of isl_* objects.
+ */
+static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
+{
+	S(LIST(EL),sort_data) *data = user;
+	EL * const *el1 = a;
+	EL * const *el2 = b;
+
+	return data->cmp(*el1, *el2, data->user);
+}
+
+/* Sort the elements of "list" in ascending order according to
+ * comparison function "cmp".
+ */
+__isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
+	int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
+{
+	S(LIST(EL),sort_data) data = { cmp, user };
+
+	if (!list)
+		return NULL;
+	if (list->n <= 1)
+		return list;
+	list = FN(LIST(EL),cow)(list);
+	if (!list)
+		return NULL;
+
+	if (isl_sort(list->p, list->n, sizeof(list->p[0]),
+			&FN(LIST(EL),cmp), &data) < 0)
+		return FN(LIST(EL),free)(list);
+
+	return list;
+}
+
 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
 {
 	isl_ctx *ctx;
-- 
2.11.4.GIT