X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_vertices.c;h=efd534b442e021b17df7683556a7ab08ca7ad574;hb=de51a9bc4da5dd3f1f9f57c2362da6f9752c44e0;hp=722fea592b5f6c40e3342d0c0f8bf2552e9916ae;hpb=cbb254f3accfec79b5b707251ae234869bb32561;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_vertices.c b/isl_vertices.c
index 722fea5..efd534b 100644
--- a/isl_vertices.c
+++ b/isl_vertices.c
@@ -1,20 +1,21 @@
 /*
  * Copyright 2010      INRIA Saclay
  *
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * Use of this software is governed by the MIT license
  *
  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
  * 91893 Orsay, France 
  */
 
-#include <isl_set.h>
-#include <isl_seq.h>
-#include <isl_tab.h>
 #include <isl_map_private.h>
-#include <isl_dim_private.h>
+#include <isl/set.h>
+#include <isl/seq.h>
+#include <isl_tab.h>
+#include <isl_space_private.h>
 #include <isl_morph.h>
 #include <isl_vertices_private.h>
+#include <isl_mat_private.h>
 
 #define SELECTED	1
 #define DESELECTED	-1
@@ -54,7 +55,7 @@ void isl_vertices_free(__isl_take isl_vertices *vertices)
 	}
 	free(vertices->c);
 
-	isl_ctx_deref(vertices->ctx);
+	isl_basic_set_free(vertices->bset);
 	free(vertices);
 }
 
@@ -85,9 +86,8 @@ static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bse
 	vertices = isl_calloc_type(bset->ctx, isl_vertices);
 	if (!vertices)
 		goto error;
-	vertices->ctx = bset->ctx;
-	isl_ctx_ref(bset->ctx);
 	vertices->ref = 1;
+	vertices->bset = isl_basic_set_copy(bset);
 	vertices->v = isl_alloc_array(bset->ctx, struct isl_vertex, n_vertices);
 	if (!vertices->v)
 		goto error;
@@ -101,7 +101,7 @@ static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bse
 
 	return vertices;
 error:
-	free(vertices);
+	isl_vertices_free(vertices);
 	free_vertex_list(list);
 	return NULL;
 }
@@ -163,8 +163,7 @@ static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset)
 	vertices = isl_calloc_type(bset->ctx, isl_vertices);
 	if (!vertices)
 		return NULL;
-	vertices->ctx = bset->ctx;
-	isl_ctx_ref(bset->ctx);
+	vertices->bset = isl_basic_set_copy(bset);
 	vertices->ref = 1;
 
 	vertices->n_vertices = 0;
@@ -192,16 +191,16 @@ static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset)
 	vertices = isl_calloc_type(bset->ctx, isl_vertices);
 	if (!vertices)
 		return NULL;
-	vertices->ctx = bset->ctx;
-	isl_ctx_ref(bset->ctx);
 	vertices->ref = 1;
+	vertices->bset = isl_basic_set_copy(bset);
 
 	vertices->v = isl_calloc_array(bset->ctx, struct isl_vertex, 1);
 	if (!vertices->v)
 		goto error;
 	vertices->n_vertices = 1;
 	vertices->v[0].vertex = isl_basic_set_copy(bset);
-	if (!vertices->v[0].vertex)
+	vertices->v[0].dom = isl_basic_set_params(isl_basic_set_copy(bset));
+	if (!vertices->v[0].vertex || !vertices->v[0].dom)
 		goto error;
 
 	vertices->c = isl_calloc_array(bset->ctx, struct isl_chamber, 1);
@@ -212,7 +211,7 @@ static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset)
 	vertices->c[0].vertices = isl_calloc_array(bset->ctx, int, 1);
 	if (!vertices->c[0].vertices)
 		goto error;
-	vertices->c[0].dom = isl_basic_set_copy(bset);
+	vertices->c[0].dom = isl_basic_set_copy(vertices->v[0].dom);
 	if (!vertices->c[0].dom)
 		goto error;
 
@@ -290,7 +289,7 @@ static int can_select(__isl_keep isl_basic_set *bset, int level,
 	if (isl_tab_is_redundant(tab, level))
 		return 0;
 
-	ovar = isl_dim_offset(bset->dim, isl_dim_set);
+	ovar = isl_space_offset(bset->dim, isl_dim_set);
 
 	indep = is_independent(facets, selected, bset->ineq[level] + 1 + ovar);
 	if (indep < 0)
@@ -394,10 +393,10 @@ __isl_give isl_vertices *isl_basic_set_compute_vertices(
 	int level;
 	int init;
 	unsigned nvar;
-	int *selection;
+	int *selection = NULL;
 	int selected;
-	struct isl_tab_undo **snap;
-	isl_mat *facets;
+	struct isl_tab_undo **snap = NULL;
+	isl_mat *facets = NULL;
 	struct isl_vertex_list *list = NULL;
 	int n_vertices = 0;
 	isl_vertices *vertices;
@@ -405,7 +404,7 @@ __isl_give isl_vertices *isl_basic_set_compute_vertices(
 	if (!bset)
 		return NULL;
 
-	if (isl_basic_set_fast_is_empty(bset))
+	if (isl_basic_set_plain_is_empty(bset))
 		return vertices_empty(bset);
 
 	if (bset->n_eq != 0)
@@ -424,7 +423,7 @@ __isl_give isl_vertices *isl_basic_set_compute_vertices(
 	if (!bset)
 		return NULL;
 
-	tab = isl_tab_from_basic_set(bset);
+	tab = isl_tab_from_basic_set(bset, 0);
 	if (!tab)
 		goto error;
 	tab->strict_redundant = 1;
@@ -496,6 +495,7 @@ __isl_give isl_vertices *isl_basic_set_compute_vertices(
 
 	return vertices;
 error:
+	free_vertex_list(list);
 	isl_mat_free(facets);
 	free(selection);
 	free(snap);
@@ -548,9 +548,11 @@ static __isl_give isl_vertices *vertices_add_chambers(
 	struct isl_chamber_list *list)
 {
 	int i;
+	isl_ctx *ctx;
 	struct isl_chamber_list *next;
 
-	vertices->c = isl_alloc_array(vertices->ctx, struct isl_chamber, n_chambers);
+	ctx = isl_vertices_get_ctx(vertices);
+	vertices->c = isl_alloc_array(ctx, struct isl_chamber, n_chambers);
 	if (!vertices->c)
 		goto error;
 	vertices->n_chambers = n_chambers;
@@ -771,7 +773,7 @@ static int has_opposite(struct isl_facet_todo *todo,
 {
 	for (; *list; list = &(*list)->next) {
 		int eq;
-		eq = isl_basic_set_fast_is_equal(todo->bset, (*list)->bset);
+		eq = isl_basic_set_plain_is_equal(todo->bset, (*list)->bset);
 		if (eq < 0)
 			return -1;
 		if (!eq)
@@ -857,10 +859,10 @@ static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
 	__isl_take isl_vertices *vertices)
 {
 	int i;
+	isl_ctx *ctx;
 	isl_vec *sample = NULL;
 	struct isl_tab *tab = NULL;
 	struct isl_tab_undo *snap;
-	unsigned nvar;
 	int *selection = NULL;
 	int n_chambers = 0;
 	struct isl_chamber_list *list = NULL;
@@ -869,19 +871,18 @@ static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
 	if (!bset || !vertices)
 		goto error;
 
-	selection = isl_alloc_array(vertices->ctx, int, vertices->n_vertices);
+	ctx = isl_vertices_get_ctx(vertices);
+	selection = isl_alloc_array(ctx, int, vertices->n_vertices);
 	if (!selection)
 		goto error;
 
-	nvar = isl_basic_set_dim(bset, isl_dim_set);
-	bset = isl_basic_set_project_out(bset, isl_dim_set, 0, nvar);
+	bset = isl_basic_set_params(bset);
 
-	tab = isl_tab_from_basic_set(bset);
+	tab = isl_tab_from_basic_set(bset, 1);
 	for (i = 0; i < bset->n_ineq; ++i)
 		if (isl_tab_freeze_constraint(tab, i) < 0)
 			goto error;
-	if (isl_tab_track_bset(tab, bset) < 0)
-		goto error;
+	isl_basic_set_free(bset);
 
 	snap = isl_tab_snap(tab);
 
@@ -974,7 +975,7 @@ error:
 
 isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex)
 {
-	return vertex ? vertex->vertices->ctx : NULL;
+	return vertex ? isl_vertices_get_ctx(vertex->vertices) : NULL;
 }
 
 int isl_vertex_get_id(__isl_keep isl_vertex *vertex)
@@ -1015,12 +1016,14 @@ __isl_give isl_basic_set *isl_vertex_get_expr(__isl_keep isl_vertex *vertex)
 static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices,
 	int id)
 {
+	isl_ctx *ctx;
 	isl_vertex *vertex;
 
 	if (!vertices)
 		return NULL;
 
-	vertex = isl_alloc_type(vertices->ctx, isl_vertex);
+	ctx = isl_vertices_get_ctx(vertices);
+	vertex = isl_alloc_type(ctx, isl_vertex);
 	if (!vertex)
 		goto error;
 
@@ -1060,39 +1063,39 @@ __isl_give isl_basic_set *isl_basic_set_set_integral(__isl_take isl_basic_set *b
 
 isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell)
 {
-	return cell ? cell->vertices->ctx : NULL;
+	return cell ? cell->dom->ctx : NULL;
 }
 
 __isl_give isl_basic_set *isl_cell_get_domain(__isl_keep isl_cell *cell)
 {
-	struct isl_chamber *c;
-
-	if (!cell)
-		return NULL;
-
-	c = &cell->vertices->c[cell->id];
-
-	return isl_basic_set_copy(c->dom);
+	return cell ? isl_basic_set_copy(cell->dom) : NULL;
 }
 
 static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices,
 	__isl_take isl_basic_set *dom, int id)
 {
-	isl_cell *cell;
+	int i;
+	isl_cell *cell = NULL;
 
 	if (!vertices || !dom)
 		goto error;
 
-	cell = isl_alloc_type(dom->ctx, isl_cell);
+	cell = isl_calloc_type(dom->ctx, isl_cell);
 	if (!cell)
 		goto error;
 
+	cell->n_vertices = vertices->c[id].n_vertices;
+	cell->ids = isl_alloc_array(dom->ctx, int, cell->n_vertices);
+	if (!cell->ids)
+		goto error;
+	for (i = 0; i < cell->n_vertices; ++i)
+		cell->ids[i] = vertices->c[id].vertices[i];
 	cell->vertices = vertices;
 	cell->dom = dom;
-	cell->id = id;
 
 	return cell;
 error:
+	isl_cell_free(cell);
 	isl_vertices_free(vertices);
 	isl_basic_set_free(dom);
 	return NULL;
@@ -1104,6 +1107,7 @@ void isl_cell_free(__isl_take isl_cell *cell)
 		return;
 
 	isl_vertices_free(cell->vertices);
+	free(cell->ids);
 	isl_basic_set_free(cell->dom);
 	free(cell);
 }
@@ -1138,11 +1142,8 @@ static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_set *bset)
 	isl_int_set_si(c->el[0], 0);
 	for (i = 0; i < bset->n_eq; ++i) {
 		isl_seq_cpy(c->el + 1, bset->eq[i], c->size - 1);
-		tab = isl_tab_add_eq(tab, c->el);
-		if (!tab) {
-			isl_vec_free(c);
-			return tab;
-		}
+		if (isl_tab_add_eq(tab, c->el) < 0)
+			goto error;
 	}
 
 	isl_int_set_si(c->el[0], -1);
@@ -1317,21 +1318,18 @@ int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
 {
 	int i;
 	isl_vertex *vertex;
-	struct isl_chamber *c;
 
 	if (!cell)
 		return -1;
 
-	c = &cell->vertices->c[cell->id];
-
-	if (c->n_vertices == 0)
+	if (cell->n_vertices == 0)
 		return 0;
 
-	for (i = 0; i < c->n_vertices; ++i) {
+	for (i = 0; i < cell->n_vertices; ++i) {
 		int r;
 
 		vertex = isl_vertex_alloc(isl_vertices_copy(cell->vertices),
-						c->vertices[i]);
+					  cell->ids[i]);
 		if (!vertex)
 			return -1;
 
@@ -1345,7 +1343,7 @@ int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
 
 isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices)
 {
-	return vertices ? vertices->ctx : NULL;
+	return vertices ? vertices->bset->ctx : NULL;
 }
 
 int isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices)
@@ -1362,13 +1360,11 @@ __isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph,
 	if (!morph || !vertices)
 		goto error;
 
-	isl_assert(vertices->ctx, vertices->ref == 1, goto error);
+	isl_assert(vertices->bset->ctx, vertices->ref == 1, goto error);
 
 	param_morph = isl_morph_copy(morph);
-	param_morph = isl_morph_remove_dom_dims(param_morph, isl_dim_set,
-				    0, isl_morph_dom_dim(morph, isl_dim_set));
-	param_morph = isl_morph_remove_ran_dims(param_morph, isl_dim_set,
-				    0, isl_morph_ran_dim(morph, isl_dim_set));
+	param_morph = isl_morph_dom_params(param_morph);
+	param_morph = isl_morph_ran_params(param_morph);
 
 	for (i = 0; i < vertices->n_vertices; ++i) {
 		vertices->v[i].dom = isl_morph_basic_set(
@@ -1395,3 +1391,178 @@ error:
 	isl_vertices_free(vertices);
 	return NULL;
 }
+
+/* Construct a simplex isl_cell spanned by the vertices with indices in
+ * "simplex_ids" and "other_ids" and call "fn" on this isl_cell.
+ */
+static int call_on_simplex(__isl_keep isl_cell *cell,
+	int *simplex_ids, int n_simplex, int *other_ids, int n_other,
+	int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
+{
+	int i;
+	isl_ctx *ctx;
+	struct isl_cell *simplex;
+
+	ctx = isl_cell_get_ctx(cell);
+
+	simplex = isl_calloc_type(ctx, struct isl_cell);
+	if (!simplex)
+		return -1;
+	simplex->vertices = isl_vertices_copy(cell->vertices);
+	if (!simplex->vertices)
+		goto error;
+	simplex->dom = isl_basic_set_copy(cell->dom);
+	if (!simplex->dom)
+		goto error;
+	simplex->n_vertices = n_simplex + n_other;
+	simplex->ids = isl_alloc_array(ctx, int, simplex->n_vertices);
+	if (!simplex->ids)
+		goto error;
+
+	for (i = 0; i < n_simplex; ++i)
+		simplex->ids[i] = simplex_ids[i];
+	for (i = 0; i < n_other; ++i)
+		simplex->ids[n_simplex + i] = other_ids[i];
+
+	return fn(simplex, user);
+error:
+	isl_cell_free(simplex);
+	return -1;
+}
+
+/* Check whether the parametric vertex described by "vertex"
+ * lies on the facet corresponding to constraint "facet" of "bset".
+ * The isl_vec "v" is a temporary vector than can be used by this function.
+ *
+ * We eliminate the variables from the facet constraint using the
+ * equalities defining the vertex and check if the result is identical
+ * to zero.
+ *
+ * It would probably be better to keep track of the constraints defining
+ * a vertex during the vertex construction so that we could simply look
+ * it up here.
+ */
+static int vertex_on_facet(__isl_keep isl_basic_set *vertex,
+	__isl_keep isl_basic_set *bset, int facet, __isl_keep isl_vec *v)
+{
+	int i;
+	isl_int m;
+
+	isl_seq_cpy(v->el, bset->ineq[facet], v->size);
+
+	isl_int_init(m);
+	for (i = 0; i < vertex->n_eq; ++i) {
+		int k = isl_seq_last_non_zero(vertex->eq[i], v->size);
+		isl_seq_elim(v->el, vertex->eq[i], k, v->size, &m);
+	}
+	isl_int_clear(m);
+
+	return isl_seq_first_non_zero(v->el, v->size) == -1;
+}
+
+/* Triangulate the polytope spanned by the vertices with ids
+ * in "simplex_ids" and "other_ids" and call "fn" on each of
+ * the resulting simplices.
+ * If the input polytope is already a simplex, we simply call "fn".
+ * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids".
+ * Then we consider each facet of "bset" that does not contain the point
+ * we just picked, but does contain some of the other points in "other_ids"
+ * and call ourselves recursively on the polytope spanned by the new
+ * "simplex_ids" and those points in "other_ids" that lie on the facet.
+ */
+static int triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v,
+	int *simplex_ids, int n_simplex, int *other_ids, int n_other,
+	int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
+{
+	int i, j, k;
+	int d, nparam;
+	int *ids;
+	isl_ctx *ctx;
+	isl_basic_set *vertex;
+	isl_basic_set *bset;
+
+	ctx = isl_cell_get_ctx(cell);
+	d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
+	nparam = isl_basic_set_dim(cell->vertices->bset, isl_dim_param);
+
+	if (n_simplex + n_other == d + 1)
+		return call_on_simplex(cell, simplex_ids, n_simplex,
+				       other_ids, n_other, fn, user);
+
+	simplex_ids[n_simplex] = other_ids[0];
+	vertex = cell->vertices->v[other_ids[0]].vertex;
+	bset = cell->vertices->bset;
+
+	ids = isl_alloc_array(ctx, int, n_other - 1);
+	for (i = 0; i < bset->n_ineq; ++i) {
+		if (isl_seq_first_non_zero(bset->ineq[i] + 1 + nparam, d) == -1)
+			continue;
+		if (vertex_on_facet(vertex, bset, i, v))
+			continue;
+
+		for (j = 1, k = 0; j < n_other; ++j) {
+			isl_basic_set *ov;
+			ov = cell->vertices->v[other_ids[j]].vertex;
+			if (vertex_on_facet(ov, bset, i, v))
+				ids[k++] = other_ids[j];
+		}
+		if (k == 0)
+			continue;
+
+		if (triangulate(cell, v, simplex_ids, n_simplex + 1,
+				ids, k, fn, user) < 0)
+			goto error;
+	}
+	free(ids);
+
+	return 0;
+error:
+	free(ids);
+	return -1;
+}
+
+/* Triangulate the given cell and call "fn" on each of the resulting
+ * simplices.
+ */
+int isl_cell_foreach_simplex(__isl_take isl_cell *cell,
+	int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
+{
+	int d, total;
+	int r;
+	isl_ctx *ctx;
+	isl_vec *v = NULL;
+	int *simplex_ids = NULL;
+
+	if (!cell)
+		return -1;
+
+	d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
+	total = isl_basic_set_total_dim(cell->vertices->bset);
+
+	if (cell->n_vertices == d + 1)
+		return fn(cell, user);
+
+	ctx = isl_cell_get_ctx(cell);
+	simplex_ids = isl_alloc_array(ctx, int, d + 1);
+	if (!simplex_ids)
+		goto error;
+
+	v = isl_vec_alloc(ctx, 1 + total);
+	if (!v)
+		goto error;
+
+	r = triangulate(cell, v, simplex_ids, 0,
+			cell->ids, cell->n_vertices, fn, user);
+
+	isl_vec_free(v);
+	free(simplex_ids);
+
+	isl_cell_free(cell);
+
+	return r;
+error:
+	free(simplex_ids);
+	isl_vec_free(v);
+	isl_cell_free(cell);
+	return -1;
+}