/*
* 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>
return vertices;
error:
- free(vertices);
+ isl_vertices_free(vertices);
free_vertex_list(list);
return NULL;
}
goto error;
isl_assert(bset->ctx, v->v.vertex->n_eq >= nvar, goto error);
v->v.dom = isl_basic_set_copy(v->v.vertex);
- v->v.dom = isl_basic_set_project_out(v->v.dom, isl_dim_set, 0, nvar);
+ v->v.dom = isl_basic_set_params(v->v.dom);
if (!v->v.dom)
goto error;
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);
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;
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)
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;
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)
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;
return vertices;
error:
+ free_vertex_list(list);
isl_mat_free(facets);
free(selection);
free(snap);
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;
{
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)
__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;
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);
v = &vertex->vertices->v[vertex->id];
if (!v->dom) {
- unsigned nvar;
- nvar = isl_basic_set_dim(v->vertex, isl_dim_set);
v->dom = isl_basic_set_copy(v->vertex);
- v->dom = isl_basic_set_project_out(v->dom, isl_dim_set, 0, nvar);
+ v->dom = isl_basic_set_params(v->dom);
}
return isl_basic_set_copy(v->dom);
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;
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(
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;
+}
projects / platform / upstream / isl.git / blobdiff