From f3d73d9079d730d7c3afc90885ff39c3a78e2e48 Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Sun, 19 Aug 2012 12:06:15 +0200
Subject: [PATCH] add isl_*_list_insert

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

diff --git a/doc/user.pod b/doc/user.pod
index a222afb..95a809f 100644
--- a/doc/user.pod
+++ b/doc/user.pod
@@ -2947,6 +2947,9 @@ Lists can be created, copied, modified and freed using the following functions.
 		isl_ctx *ctx, int n);
 	__isl_give isl_set_list *isl_set_list_copy(
 		__isl_keep isl_set_list *list);
+	__isl_give isl_set_list *isl_set_list_insert(
+		__isl_take isl_set_list *list, unsigned pos,
+		__isl_take isl_set *el);
 	__isl_give isl_set_list *isl_set_list_add(
 		__isl_take isl_set_list *list,
 		__isl_take isl_set *el);
diff --git a/include/isl/list.h b/include/isl/list.h
index 87596e0..5cc7da3 100644
--- a/include/isl/list.h
+++ b/include/isl/list.h
@@ -31,6 +31,9 @@ void *isl_##EL##_list_free(__isl_take isl_##EL##_list *list);		\
 __isl_give isl_##EL##_list *isl_##EL##_list_add(			\
 	__isl_take isl_##EL##_list *list,				\
 	__isl_take struct isl_##EL *el);				\
+__isl_give isl_##EL##_list *isl_##EL##_list_insert(			\
+	__isl_take isl_##EL##_list *list, unsigned pos,			\
+	__isl_take struct isl_##EL *el);				\
 __isl_give isl_##EL##_list *isl_##EL##_list_drop(			\
 	__isl_take isl_##EL##_list *list, unsigned first, unsigned n);	\
 __isl_give isl_##EL##_list *isl_##EL##_list_concat(			\
diff --git a/isl_list_templ.c b/isl_list_templ.c
index cd6cd9e..0af5b76 100644
--- a/isl_list_templ.c
+++ b/isl_list_templ.c
@@ -1,6 +1,7 @@
 /*
  * Copyright 2008-2009 Katholieke Universiteit Leuven
  * Copyright 2011      INRIA Saclay
+ * Copyright 2012      Ecole Normale Superieure
  *
  * Use of this software is governed by the MIT license
  *
@@ -8,6 +9,7 @@
  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
+ * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  */
 
 #define xCAT(A,B) A ## B
@@ -159,6 +161,50 @@ __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
 	return list;
 }
 
+/* Insert "el" at position "pos" in "list".
+ *
+ * If there is only one reference to "list" and if it already has space
+ * for one extra element, we insert it directly into "list".
+ * Otherwise, we create a new list consisting of "el" and copied
+ * elements from "list".
+ */
+__isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
+	unsigned pos, __isl_take struct EL *el)
+{
+	int i;
+	isl_ctx *ctx;
+	LIST(EL) *res;
+
+	if (!list || !el)
+		goto error;
+	ctx = FN(LIST(EL),get_ctx)(list);
+	if (pos > list->n)
+		isl_die(ctx, isl_error_invalid,
+			"index out of bounds", goto error);
+
+	if (list->ref == 1 && list->size > list->n) {
+		for (i = list->n - 1; i >= pos; --i)
+			list->p[i + 1] = list->p[i];
+		list->n++;
+		list->p[pos] = el;
+		return list;
+	}
+
+	res = FN(LIST(EL),alloc)(ctx, list->n + 1);
+	for (i = 0; i < pos; ++i)
+		res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
+	res = FN(LIST(EL),add)(res, el);
+	for (i = pos; i < list->n; ++i)
+		res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
+	FN(LIST(EL),free)(list);
+
+	return res;
+error:
+	FN(EL,free)(el);
+	FN(LIST(EL),free)(list);
+	return NULL;
+}
+
 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
 {
 	int i;
-- 
2.7.4