nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 license
5 *
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
10  
11 #include <isl_map_private.h>
12 #include <isl/set.h>
13 #include <isl/seq.h>
14 #include <isl_tab.h>
15 #include <isl_space_private.h>
16 #include <isl_morph.h>
17 #include <isl_vertices_private.h>
18 #include <isl_mat_private.h>
19  
20 #define SELECTED 1
21 #define DESELECTED -1
22 #define UNSELECTED 0
23  
24 static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
25 __isl_take isl_vertices *vertices);
26  
27 __isl_give isl_vertices *isl_vertices_copy(__isl_keep isl_vertices *vertices)
28 {
29 if (!vertices)
30 return NULL;
31  
32 vertices->ref++;
33 return vertices;
34 }
35  
36 void isl_vertices_free(__isl_take isl_vertices *vertices)
37 {
38 int i;
39  
40 if (!vertices)
41 return;
42  
43 if (--vertices->ref > 0)
44 return;
45  
46 for (i = 0; i < vertices->n_vertices; ++i) {
47 isl_basic_set_free(vertices->v[i].vertex);
48 isl_basic_set_free(vertices->v[i].dom);
49 }
50 free(vertices->v);
51  
52 for (i = 0; i < vertices->n_chambers; ++i) {
53 free(vertices->c[i].vertices);
54 isl_basic_set_free(vertices->c[i].dom);
55 }
56 free(vertices->c);
57  
58 isl_basic_set_free(vertices->bset);
59 free(vertices);
60 }
61  
62 struct isl_vertex_list {
63 struct isl_vertex v;
64 struct isl_vertex_list *next;
65 };
66  
67 static void free_vertex_list(struct isl_vertex_list *list)
68 {
69 struct isl_vertex_list *next;
70  
71 for (; list; list = next) {
72 next = list->next;
73 isl_basic_set_free(list->v.vertex);
74 isl_basic_set_free(list->v.dom);
75 free(list);
76 }
77 }
78  
79 static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_set *bset,
80 int n_vertices, struct isl_vertex_list *list)
81 {
82 int i;
83 struct isl_vertex_list *next;
84 isl_vertices *vertices;
85  
86 vertices = isl_calloc_type(bset->ctx, isl_vertices);
87 if (!vertices)
88 goto error;
89 vertices->ref = 1;
90 vertices->bset = isl_basic_set_copy(bset);
91 vertices->v = isl_alloc_array(bset->ctx, struct isl_vertex, n_vertices);
92 if (!vertices->v)
93 goto error;
94 vertices->n_vertices = n_vertices;
95  
96 for (i = 0; list; list = next, i++) {
97 next = list->next;
98 vertices->v[i] = list->v;
99 free(list);
100 }
101  
102 return vertices;
103 error:
104 free(vertices);
105 free_vertex_list(list);
106 return NULL;
107 }
108  
109 /* Prepend a vertex to the linked list "list" based on the equalities in "tab".
110 */
111 static int add_vertex(struct isl_vertex_list **list,
112 __isl_keep isl_basic_set *bset, struct isl_tab *tab)
113 {
114 unsigned nvar;
115 unsigned nparam;
116 struct isl_vertex_list *v = NULL;
117  
118 if (isl_tab_detect_implicit_equalities(tab) < 0)
119 return -1;
120  
121 nvar = isl_basic_set_dim(bset, isl_dim_set);
122 nparam = isl_basic_set_dim(bset, isl_dim_param);
123  
124 v = isl_calloc_type(tab->mat->ctx, struct isl_vertex_list);
125 if (!v)
126 goto error;
127  
128 v->v.vertex = isl_basic_set_copy(bset);
129 v->v.vertex = isl_basic_set_cow(v->v.vertex);
130 v->v.vertex = isl_basic_set_update_from_tab(v->v.vertex, tab);
131 v->v.vertex = isl_basic_set_simplify(v->v.vertex);
132 v->v.vertex = isl_basic_set_finalize(v->v.vertex);
133 if (!v->v.vertex)
134 goto error;
135 isl_assert(bset->ctx, v->v.vertex->n_eq >= nvar, goto error);
136 v->v.dom = isl_basic_set_copy(v->v.vertex);
137 v->v.dom = isl_basic_set_project_out(v->v.dom, isl_dim_set, 0, nvar);
138 if (!v->v.dom)
139 goto error;
140  
141 v->next = *list;
142 *list = v;
143  
144 return 0;
145 error:
146 free_vertex_list(v);
147 return -1;
148 }
149  
150 /* Compute the parametric vertices and the chamber decomposition
151 * of an empty parametric polytope.
152 */
153 static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_set *bset)
154 {
155 isl_vertices *vertices;
156 unsigned nparam;
157  
158 if (!bset)
159 return NULL;
160  
161 nparam = isl_basic_set_dim(bset, isl_dim_param);
162  
163 vertices = isl_calloc_type(bset->ctx, isl_vertices);
164 if (!vertices)
165 return NULL;
166 vertices->bset = isl_basic_set_copy(bset);
167 vertices->ref = 1;
168  
169 vertices->n_vertices = 0;
170 vertices->n_chambers = 0;
171  
172 return vertices;
173 }
174  
175 /* Compute the parametric vertices and the chamber decomposition
176 * of the parametric polytope defined using the same constraints
177 * as "bset" in the 0D case.
178 * There is exactly one 0D vertex and a single chamber containing
179 * the vertex.
180 */
181 static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_set *bset)
182 {
183 isl_vertices *vertices;
184 unsigned nparam;
185  
186 if (!bset)
187 return NULL;
188  
189 nparam = isl_basic_set_dim(bset, isl_dim_param);
190  
191 vertices = isl_calloc_type(bset->ctx, isl_vertices);
192 if (!vertices)
193 return NULL;
194 vertices->ref = 1;
195 vertices->bset = isl_basic_set_copy(bset);
196  
197 vertices->v = isl_calloc_array(bset->ctx, struct isl_vertex, 1);
198 if (!vertices->v)
199 goto error;
200 vertices->n_vertices = 1;
201 vertices->v[0].vertex = isl_basic_set_copy(bset);
202 vertices->v[0].dom = isl_basic_set_params(isl_basic_set_copy(bset));
203 if (!vertices->v[0].vertex || !vertices->v[0].dom)
204 goto error;
205  
206 vertices->c = isl_calloc_array(bset->ctx, struct isl_chamber, 1);
207 if (!vertices->c)
208 goto error;
209 vertices->n_chambers = 1;
210 vertices->c[0].n_vertices = 1;
211 vertices->c[0].vertices = isl_calloc_array(bset->ctx, int, 1);
212 if (!vertices->c[0].vertices)
213 goto error;
214 vertices->c[0].dom = isl_basic_set_copy(vertices->v[0].dom);
215 if (!vertices->c[0].dom)
216 goto error;
217  
218 return vertices;
219 error:
220 isl_vertices_free(vertices);
221 return NULL;
222 }
223  
224 static int isl_mat_rank(__isl_keep isl_mat *mat)
225 {
226 int row, col;
227 isl_mat *H;
228  
229 H = isl_mat_left_hermite(isl_mat_copy(mat), 0, NULL, NULL);
230 if (!H)
231 return -1;
232  
233 for (col = 0; col < H->n_col; ++col) {
234 for (row = 0; row < H->n_row; ++row)
235 if (!isl_int_is_zero(H->row[row][col]))
236 break;
237 if (row == H->n_row)
238 break;
239 }
240  
241 isl_mat_free(H);
242  
243 return col;
244 }
245  
246 /* Is the row pointed to by "f" linearly independent of the "n" first
247 * rows in "facets"?
248 */
249 static int is_independent(__isl_keep isl_mat *facets, int n, isl_int *f)
250 {
251 int rank;
252  
253 if (isl_seq_first_non_zero(f, facets->n_col) < 0)
254 return 0;
255  
256 isl_seq_cpy(facets->row[n], f, facets->n_col);
257 facets->n_row = n + 1;
258 rank = isl_mat_rank(facets);
259 if (rank < 0)
260 return -1;
261  
262 return rank == n + 1;
263 }
264  
265 /* Check whether we can select constraint "level", given the current selection
266 * reflected by facets in "tab", the rows of "facets" and the earlier
267 * "selected" elements of "selection".
268 *
269 * If the constraint is (strictly) redundant in the tableau, selecting it would
270 * result in an empty tableau, so it can't be selected.
271 * If the set variable part of the constraint is not linearly indepedent
272 * of the set variable parts of the already selected constraints,
273 * the constraint cannot be selected.
274 * If selecting the constraint results in an empty tableau, the constraint
275 * cannot be selected.
276 * Finally, if selecting the constraint results in some explicitly
277 * deselected constraints turning into equalities, then the corresponding
278 * vertices have already been generated, so the constraint cannot be selected.
279 */
280 static int can_select(__isl_keep isl_basic_set *bset, int level,
281 struct isl_tab *tab, __isl_keep isl_mat *facets, int selected,
282 int *selection)
283 {
284 int i;
285 int indep;
286 unsigned ovar;
287 struct isl_tab_undo *snap;
288  
289 if (isl_tab_is_redundant(tab, level))
290 return 0;
291  
292 ovar = isl_space_offset(bset->dim, isl_dim_set);
293  
294 indep = is_independent(facets, selected, bset->ineq[level] + 1 + ovar);
295 if (indep < 0)
296 return -1;
297 if (!indep)
298 return 0;
299  
300 snap = isl_tab_snap(tab);
301 if (isl_tab_select_facet(tab, level) < 0)
302 return -1;
303  
304 if (tab->empty) {
305 if (isl_tab_rollback(tab, snap) < 0)
306 return -1;
307 return 0;
308 }
309  
310 for (i = 0; i < level; ++i) {
311 int sgn;
312  
313 if (selection[i] != DESELECTED)
314 continue;
315  
316 if (isl_tab_is_equality(tab, i))
317 sgn = 0;
318 else if (isl_tab_is_redundant(tab, i))
319 sgn = 1;
320 else
321 sgn = isl_tab_sign_of_max(tab, i);
322 if (sgn < -1)
323 return -1;
324 if (sgn <= 0) {
325 if (isl_tab_rollback(tab, snap) < 0)
326 return -1;
327 return 0;
328 }
329 }
330  
331 return 1;
332 }
333  
334 /* Compute the parametric vertices and the chamber decomposition
335 * of a parametric polytope that is not full-dimensional.
336 *
337 * Simply map the parametric polytope to a lower dimensional space
338 * and map the resulting vertices back.
339 */
340 static __isl_give isl_vertices *lower_dim_vertices(
341 __isl_keep isl_basic_set *bset)
342 {
343 isl_morph *morph;
344 isl_vertices *vertices;
345  
346 bset = isl_basic_set_copy(bset);
347 morph = isl_basic_set_full_compression(bset);
348 bset = isl_morph_basic_set(isl_morph_copy(morph), bset);
349  
350 vertices = isl_basic_set_compute_vertices(bset);
351 isl_basic_set_free(bset);
352  
353 morph = isl_morph_inverse(morph);
354  
355 vertices = isl_morph_vertices(morph, vertices);
356  
357 return vertices;
358 }
359  
360 /* Compute the parametric vertices and the chamber decomposition
361 * of the parametric polytope defined using the same constraints
362 * as "bset". "bset" is assumed to have no existentially quantified
363 * variables.
364 *
365 * The vertices themselves are computed in a fairly simplistic way.
366 * We simply run through all combinations of d constraints,
367 * with d the number of set variables, and check if those d constraints
368 * define a vertex. To avoid the generation of duplicate vertices,
369 * which we may happen if a vertex is defined by more that d constraints,
370 * we make sure we only generate the vertex for the d constraints with
371 * smallest index.
372 *
373 * We set up a tableau and keep track of which facets have been
374 * selected. The tableau is marked strict_redundant so that we can be
375 * sure that any constraint that is marked redundant (and that is not
376 * also marked zero) is not an equality.
377 * If a constraint is marked DESELECTED, it means the constraint was
378 * SELECTED before (in combination with the same selection of earlier
379 * constraints). If such a deselected constraint turns out to be an
380 * equality, then any vertex that may still be found with the current
381 * selection has already been generated when the constraint was selected.
382 * A constraint is marked UNSELECTED when there is no way selecting
383 * the constraint could lead to a vertex (in combination with the current
384 * selection of earlier constraints).
385 *
386 * The set variable coefficients of the selected constraints are stored
387 * in the facets matrix.
388 */
389 __isl_give isl_vertices *isl_basic_set_compute_vertices(
390 __isl_keep isl_basic_set *bset)
391 {
392 struct isl_tab *tab;
393 int level;
394 int init;
395 unsigned nvar;
396 int *selection = NULL;
397 int selected;
398 struct isl_tab_undo **snap = NULL;
399 isl_mat *facets = NULL;
400 struct isl_vertex_list *list = NULL;
401 int n_vertices = 0;
402 isl_vertices *vertices;
403  
404 if (!bset)
405 return NULL;
406  
407 if (isl_basic_set_plain_is_empty(bset))
408 return vertices_empty(bset);
409  
410 if (bset->n_eq != 0)
411 return lower_dim_vertices(bset);
412  
413 isl_assert(bset->ctx, isl_basic_set_dim(bset, isl_dim_div) == 0,
414 return NULL);
415  
416 if (isl_basic_set_dim(bset, isl_dim_set) == 0)
417 return vertices_0D(bset);
418  
419 nvar = isl_basic_set_dim(bset, isl_dim_set);
420  
421 bset = isl_basic_set_copy(bset);
422 bset = isl_basic_set_set_rational(bset);
423 if (!bset)
424 return NULL;
425  
426 tab = isl_tab_from_basic_set(bset, 0);
427 if (!tab)
428 goto error;
429 tab->strict_redundant = 1;
430  
431 if (tab->empty) {
432 vertices = vertices_empty(bset);
433 isl_basic_set_free(bset);
434 isl_tab_free(tab);
435 return vertices;
436 }
437  
438 selection = isl_alloc_array(bset->ctx, int, bset->n_ineq);
439 snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, bset->n_ineq);
440 facets = isl_mat_alloc(bset->ctx, nvar, nvar);
441 if (!selection || !snap || !facets)
442 goto error;
443  
444 level = 0;
445 init = 1;
446 selected = 0;
447  
448 while (level >= 0) {
449 if (level >= bset->n_ineq ||
450 (!init && selection[level] != SELECTED)) {
451 --level;
452 init = 0;
453 continue;
454 }
455 if (init) {
456 int ok;
457 snap[level] = isl_tab_snap(tab);
458 ok = can_select(bset, level, tab, facets, selected,
459 selection);
460 if (ok < 0)
461 goto error;
462 if (ok) {
463 selection[level] = SELECTED;
464 selected++;
465 } else
466 selection[level] = UNSELECTED;
467 } else {
468 selection[level] = DESELECTED;
469 selected--;
470 if (isl_tab_rollback(tab, snap[level]) < 0)
471 goto error;
472 }
473 if (selected == nvar) {
474 if (tab->n_dead == nvar) {
475 if (add_vertex(&list, bset, tab) < 0)
476 goto error;
477 n_vertices++;
478 }
479 init = 0;
480 continue;
481 }
482 ++level;
483 init = 1;
484 }
485  
486 isl_mat_free(facets);
487 free(selection);
488 free(snap);
489  
490 isl_tab_free(tab);
491  
492 vertices = vertices_from_list(bset, n_vertices, list);
493  
494 vertices = compute_chambers(bset, vertices);
495  
496 return vertices;
497 error:
498 isl_mat_free(facets);
499 free(selection);
500 free(snap);
501 isl_tab_free(tab);
502 isl_basic_set_free(bset);
503 return NULL;
504 }
505  
506 struct isl_chamber_list {
507 struct isl_chamber c;
508 struct isl_chamber_list *next;
509 };
510  
511 static void free_chamber_list(struct isl_chamber_list *list)
512 {
513 struct isl_chamber_list *next;
514  
515 for (; list; list = next) {
516 next = list->next;
517 isl_basic_set_free(list->c.dom);
518 free(list->c.vertices);
519 free(list);
520 }
521 }
522  
523 /* Check whether the basic set "bset" is a superset of the basic set described
524 * by "tab", i.e., check whether all constraints of "bset" are redundant.
525 */
526 static int bset_covers_tab(__isl_keep isl_basic_set *bset, struct isl_tab *tab)
527 {
528 int i;
529  
530 if (!bset || !tab)
531 return -1;
532  
533 for (i = 0; i < bset->n_ineq; ++i) {
534 enum isl_ineq_type type = isl_tab_ineq_type(tab, bset->ineq[i]);
535 switch (type) {
536 case isl_ineq_error: return -1;
537 case isl_ineq_redundant: continue;
538 default: return 0;
539 }
540 }
541  
542 return 1;
543 }
544  
545 static __isl_give isl_vertices *vertices_add_chambers(
546 __isl_take isl_vertices *vertices, int n_chambers,
547 struct isl_chamber_list *list)
548 {
549 int i;
550 isl_ctx *ctx;
551 struct isl_chamber_list *next;
552  
553 ctx = isl_vertices_get_ctx(vertices);
554 vertices->c = isl_alloc_array(ctx, struct isl_chamber, n_chambers);
555 if (!vertices->c)
556 goto error;
557 vertices->n_chambers = n_chambers;
558  
559 for (i = 0; list; list = next, i++) {
560 next = list->next;
561 vertices->c[i] = list->c;
562 free(list);
563 }
564  
565 return vertices;
566 error:
567 isl_vertices_free(vertices);
568 free_chamber_list(list);
569 return NULL;
570 }
571  
572 /* Can "tab" be intersected with "bset" without resulting in
573 * a lower-dimensional set.
574 */
575 static int can_intersect(struct isl_tab *tab, __isl_keep isl_basic_set *bset)
576 {
577 int i;
578 struct isl_tab_undo *snap;
579  
580 if (isl_tab_extend_cons(tab, bset->n_ineq) < 0)
581 return -1;
582  
583 snap = isl_tab_snap(tab);
584  
585 for (i = 0; i < bset->n_ineq; ++i) {
586 if (isl_tab_ineq_type(tab, bset->ineq[i]) == isl_ineq_redundant)
587 continue;
588 if (isl_tab_add_ineq(tab, bset->ineq[i]) < 0)
589 return -1;
590 }
591  
592 if (isl_tab_detect_implicit_equalities(tab) < 0)
593 return -1;
594 if (tab->n_dead) {
595 if (isl_tab_rollback(tab, snap) < 0)
596 return -1;
597 return 0;
598 }
599  
600 return 1;
601 }
602  
603 static int add_chamber(struct isl_chamber_list **list,
604 __isl_keep isl_vertices *vertices, struct isl_tab *tab, int *selection)
605 {
606 int n_frozen;
607 int i, j;
608 int n_vertices = 0;
609 struct isl_tab_undo *snap;
610 struct isl_chamber_list *c = NULL;
611  
612 for (i = 0; i < vertices->n_vertices; ++i)
613 if (selection[i])
614 n_vertices++;
615  
616 snap = isl_tab_snap(tab);
617  
618 for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i)
619 tab->con[i].frozen = 0;
620 n_frozen = i;
621  
622 if (isl_tab_detect_redundant(tab) < 0)
623 return -1;
624  
625 c = isl_calloc_type(tab->mat->ctx, struct isl_chamber_list);
626 if (!c)
627 goto error;
628 c->c.vertices = isl_alloc_array(tab->mat->ctx, int, n_vertices);
629 if (!c->c.vertices)
630 goto error;
631 c->c.dom = isl_basic_set_from_basic_map(isl_basic_map_copy(tab->bmap));
632 c->c.dom = isl_basic_set_set_rational(c->c.dom);
633 c->c.dom = isl_basic_set_cow(c->c.dom);
634 c->c.dom = isl_basic_set_update_from_tab(c->c.dom, tab);
635 c->c.dom = isl_basic_set_simplify(c->c.dom);
636 c->c.dom = isl_basic_set_finalize(c->c.dom);
637 if (!c->c.dom)
638 goto error;
639  
640 c->c.n_vertices = n_vertices;
641  
642 for (i = 0, j = 0; i < vertices->n_vertices; ++i)
643 if (selection[i]) {
644 c->c.vertices[j] = i;
645 j++;
646 }
647  
648 c->next = *list;
649 *list = c;
650  
651 for (i = 0; i < n_frozen; ++i)
652 tab->con[i].frozen = 1;
653  
654 if (isl_tab_rollback(tab, snap) < 0)
655 return -1;
656  
657 return 0;
658 error:
659 free_chamber_list(c);
660 return -1;
661 }
662  
663 struct isl_facet_todo {
664 struct isl_tab *tab; /* A tableau representation of the facet */
665 isl_basic_set *bset; /* A normalized basic set representation */
666 isl_vec *constraint; /* Constraint pointing to the other side */
667 struct isl_facet_todo *next;
668 };
669  
670 static void free_todo(struct isl_facet_todo *todo)
671 {
672 while (todo) {
673 struct isl_facet_todo *next = todo->next;
674  
675 isl_tab_free(todo->tab);
676 isl_basic_set_free(todo->bset);
677 isl_vec_free(todo->constraint);
678 free(todo);
679  
680 todo = next;
681 }
682 }
683  
684 static struct isl_facet_todo *create_todo(struct isl_tab *tab, int con)
685 {
686 int i;
687 int n_frozen;
688 struct isl_tab_undo *snap;
689 struct isl_facet_todo *todo;
690  
691 snap = isl_tab_snap(tab);
692  
693 for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i)
694 tab->con[i].frozen = 0;
695 n_frozen = i;
696  
697 if (isl_tab_detect_redundant(tab) < 0)
698 return NULL;
699  
700 todo = isl_calloc_type(tab->mat->ctx, struct isl_facet_todo);
701 if (!todo)
702 return NULL;
703  
704 todo->constraint = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var);
705 if (!todo->constraint)
706 goto error;
707 isl_seq_neg(todo->constraint->el, tab->bmap->ineq[con], 1 + tab->n_var);
708 todo->bset = isl_basic_set_from_basic_map(isl_basic_map_copy(tab->bmap));
709 todo->bset = isl_basic_set_set_rational(todo->bset);
710 todo->bset = isl_basic_set_cow(todo->bset);
711 todo->bset = isl_basic_set_update_from_tab(todo->bset, tab);
712 todo->bset = isl_basic_set_simplify(todo->bset);
713 todo->bset = isl_basic_set_sort_constraints(todo->bset);
714 if (!todo->bset)
715 goto error;
716 ISL_F_SET(todo->bset, ISL_BASIC_SET_NORMALIZED);
717 todo->tab = isl_tab_dup(tab);
718 if (!todo->tab)
719 goto error;
720  
721 for (i = 0; i < n_frozen; ++i)
722 tab->con[i].frozen = 1;
723  
724 if (isl_tab_rollback(tab, snap) < 0)
725 goto error;
726  
727 return todo;
728 error:
729 free_todo(todo);
730 return NULL;
731 }
732  
733 /* Create todo items for all interior facets of the chamber represented
734 * by "tab" and collect them in "next".
735 */
736 static int init_todo(struct isl_facet_todo **next, struct isl_tab *tab)
737 {
738 int i;
739 struct isl_tab_undo *snap;
740 struct isl_facet_todo *todo;
741  
742 snap = isl_tab_snap(tab);
743  
744 for (i = 0; i < tab->n_con; ++i) {
745 if (tab->con[i].frozen)
746 continue;
747 if (tab->con[i].is_redundant)
748 continue;
749  
750 if (isl_tab_select_facet(tab, i) < 0)
751 return -1;
752  
753 todo = create_todo(tab, i);
754 if (!todo)
755 return -1;
756  
757 todo->next = *next;
758 *next = todo;
759  
760 if (isl_tab_rollback(tab, snap) < 0)
761 return -1;
762 }
763  
764 return 0;
765 }
766  
767 /* Does the linked list contain a todo item that is the opposite of "todo".
768 * If so, return 1 and remove the opposite todo item.
769 */
770 static int has_opposite(struct isl_facet_todo *todo,
771 struct isl_facet_todo **list)
772 {
773 for (; *list; list = &(*list)->next) {
774 int eq;
775 eq = isl_basic_set_plain_is_equal(todo->bset, (*list)->bset);
776 if (eq < 0)
777 return -1;
778 if (!eq)
779 continue;
780 todo = *list;
781 *list = todo->next;
782 todo->next = NULL;
783 free_todo(todo);
784 return 1;
785 }
786  
787 return 0;
788 }
789  
790 /* Create todo items for all interior facets of the chamber represented
791 * by "tab" and collect them in first->next, taking care to cancel
792 * opposite todo items.
793 */
794 static int update_todo(struct isl_facet_todo *first, struct isl_tab *tab)
795 {
796 int i;
797 struct isl_tab_undo *snap;
798 struct isl_facet_todo *todo;
799  
800 snap = isl_tab_snap(tab);
801  
802 for (i = 0; i < tab->n_con; ++i) {
803 int drop;
804  
805 if (tab->con[i].frozen)
806 continue;
807 if (tab->con[i].is_redundant)
808 continue;
809  
810 if (isl_tab_select_facet(tab, i) < 0)
811 return -1;
812  
813 todo = create_todo(tab, i);
814 if (!todo)
815 return -1;
816  
817 drop = has_opposite(todo, &first->next);
818 if (drop < 0)
819 return -1;
820  
821 if (drop)
822 free_todo(todo);
823 else {
824 todo->next = first->next;
825 first->next = todo;
826 }
827  
828 if (isl_tab_rollback(tab, snap) < 0)
829 return -1;
830 }
831  
832 return 0;
833 }
834  
835 /* Compute the chamber decomposition of the parametric polytope respresented
836 * by "bset" given the parametric vertices and their activity domains.
837 *
838 * We are only interested in full-dimensional chambers.
839 * Each of these chambers is the intersection of the activity domains of
840 * one or more vertices and the union of all chambers is equal to the
841 * projection of the entire parametric polytope onto the parameter space.
842 *
843 * We first create an initial chamber by intersecting as many activity
844 * domains as possible without ending up with an empty or lower-dimensional
845 * set. As a minor optimization, we only consider those activity domains
846 * that contain some arbitrary point.
847 *
848 * For each of interior facets of the chamber, we construct a todo item,
849 * containing the facet and a constraint containing the other side of the facet,
850 * for constructing the chamber on the other side.
851 * While their are any todo items left, we pick a todo item and
852 * create the required chamber by intersecting all activity domains
853 * that contain the facet and have a full-dimensional intersection with
854 * the other side of the facet. For each of the interior facets, we
855 * again create todo items, taking care to cancel opposite todo items.
856 */
857 static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_set *bset,
858 __isl_take isl_vertices *vertices)
859 {
860 int i;
861 isl_ctx *ctx;
862 isl_vec *sample = NULL;
863 struct isl_tab *tab = NULL;
864 struct isl_tab_undo *snap;
865 int *selection = NULL;
866 int n_chambers = 0;
867 struct isl_chamber_list *list = NULL;
868 struct isl_facet_todo *todo = NULL;
869  
870 if (!bset || !vertices)
871 goto error;
872  
873 ctx = isl_vertices_get_ctx(vertices);
874 selection = isl_alloc_array(ctx, int, vertices->n_vertices);
875 if (!selection)
876 goto error;
877  
878 bset = isl_basic_set_params(bset);
879  
880 tab = isl_tab_from_basic_set(bset, 1);
881 for (i = 0; i < bset->n_ineq; ++i)
882 if (isl_tab_freeze_constraint(tab, i) < 0)
883 goto error;
884 isl_basic_set_free(bset);
885  
886 snap = isl_tab_snap(tab);
887  
888 sample = isl_tab_get_sample_value(tab);
889  
890 for (i = 0; i < vertices->n_vertices; ++i) {
891 selection[i] = isl_basic_set_contains(vertices->v[i].dom, sample);
892 if (selection[i] < 0)
893 goto error;
894 if (!selection[i])
895 continue;
896 selection[i] = can_intersect(tab, vertices->v[i].dom);
897 if (selection[i] < 0)
898 goto error;
899 }
900  
901 if (isl_tab_detect_redundant(tab) < 0)
902 goto error;
903  
904 if (add_chamber(&list, vertices, tab, selection) < 0)
905 goto error;
906 n_chambers++;
907  
908 if (init_todo(&todo, tab) < 0)
909 goto error;
910  
911 while (todo) {
912 struct isl_facet_todo *next;
913  
914 if (isl_tab_rollback(tab, snap) < 0)
915 goto error;
916  
917 if (isl_tab_add_ineq(tab, todo->constraint->el) < 0)
918 goto error;
919 if (isl_tab_freeze_constraint(tab, tab->n_con - 1) < 0)
920 goto error;
921  
922 for (i = 0; i < vertices->n_vertices; ++i) {
923 selection[i] = bset_covers_tab(vertices->v[i].dom,
924 todo->tab);
925 if (selection[i] < 0)
926 goto error;
927 if (!selection[i])
928 continue;
929 selection[i] = can_intersect(tab, vertices->v[i].dom);
930 if (selection[i] < 0)
931 goto error;
932 }
933  
934 if (isl_tab_detect_redundant(tab) < 0)
935 goto error;
936  
937 if (add_chamber(&list, vertices, tab, selection) < 0)
938 goto error;
939 n_chambers++;
940  
941 if (update_todo(todo, tab) < 0)
942 goto error;
943  
944 next = todo->next;
945 todo->next = NULL;
946 free_todo(todo);
947 todo = next;
948 }
949  
950 isl_vec_free(sample);
951  
952 isl_tab_free(tab);
953 free(selection);
954  
955 vertices = vertices_add_chambers(vertices, n_chambers, list);
956  
957 for (i = 0; vertices && i < vertices->n_vertices; ++i) {
958 isl_basic_set_free(vertices->v[i].dom);
959 vertices->v[i].dom = NULL;
960 }
961  
962 return vertices;
963 error:
964 free_chamber_list(list);
965 free_todo(todo);
966 isl_vec_free(sample);
967 isl_tab_free(tab);
968 free(selection);
969 if (!tab)
970 isl_basic_set_free(bset);
971 isl_vertices_free(vertices);
972 return NULL;
973 }
974  
975 isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex)
976 {
977 return vertex ? isl_vertices_get_ctx(vertex->vertices) : NULL;
978 }
979  
980 int isl_vertex_get_id(__isl_keep isl_vertex *vertex)
981 {
982 return vertex ? vertex->id : -1;
983 }
984  
985 __isl_give isl_basic_set *isl_vertex_get_domain(__isl_keep isl_vertex *vertex)
986 {
987 struct isl_vertex *v;
988  
989 if (!vertex)
990 return NULL;
991  
992 v = &vertex->vertices->v[vertex->id];
993 if (!v->dom) {
994 unsigned nvar;
995 nvar = isl_basic_set_dim(v->vertex, isl_dim_set);
996 v->dom = isl_basic_set_copy(v->vertex);
997 v->dom = isl_basic_set_project_out(v->dom, isl_dim_set, 0, nvar);
998 }
999  
1000 return isl_basic_set_copy(v->dom);
1001 }
1002  
1003 __isl_give isl_basic_set *isl_vertex_get_expr(__isl_keep isl_vertex *vertex)
1004 {
1005 struct isl_vertex *v;
1006  
1007 if (!vertex)
1008 return NULL;
1009  
1010 v = &vertex->vertices->v[vertex->id];
1011  
1012 return isl_basic_set_copy(v->vertex);
1013 }
1014  
1015 static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices,
1016 int id)
1017 {
1018 isl_ctx *ctx;
1019 isl_vertex *vertex;
1020  
1021 if (!vertices)
1022 return NULL;
1023  
1024 ctx = isl_vertices_get_ctx(vertices);
1025 vertex = isl_alloc_type(ctx, isl_vertex);
1026 if (!vertex)
1027 goto error;
1028  
1029 vertex->vertices = vertices;
1030 vertex->id = id;
1031  
1032 return vertex;
1033 error:
1034 isl_vertices_free(vertices);
1035 return NULL;
1036 }
1037  
1038 void isl_vertex_free(__isl_take isl_vertex *vertex)
1039 {
1040 if (!vertex)
1041 return;
1042 isl_vertices_free(vertex->vertices);
1043 free(vertex);
1044 }
1045  
1046 __isl_give isl_basic_set *isl_basic_set_set_integral(__isl_take isl_basic_set *bset)
1047 {
1048 if (!bset)
1049 return NULL;
1050  
1051 if (!ISL_F_ISSET(bset, ISL_BASIC_MAP_RATIONAL))
1052 return bset;
1053  
1054 bset = isl_basic_set_cow(bset);
1055 if (!bset)
1056 return NULL;
1057  
1058 ISL_F_CLR(bset, ISL_BASIC_MAP_RATIONAL);
1059  
1060 return isl_basic_set_finalize(bset);
1061 }
1062  
1063 isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell)
1064 {
1065 return cell ? cell->dom->ctx : NULL;
1066 }
1067  
1068 __isl_give isl_basic_set *isl_cell_get_domain(__isl_keep isl_cell *cell)
1069 {
1070 return cell ? isl_basic_set_copy(cell->dom) : NULL;
1071 }
1072  
1073 static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices,
1074 __isl_take isl_basic_set *dom, int id)
1075 {
1076 int i;
1077 isl_cell *cell = NULL;
1078  
1079 if (!vertices || !dom)
1080 goto error;
1081  
1082 cell = isl_calloc_type(dom->ctx, isl_cell);
1083 if (!cell)
1084 goto error;
1085  
1086 cell->n_vertices = vertices->c[id].n_vertices;
1087 cell->ids = isl_alloc_array(dom->ctx, int, cell->n_vertices);
1088 if (!cell->ids)
1089 goto error;
1090 for (i = 0; i < cell->n_vertices; ++i)
1091 cell->ids[i] = vertices->c[id].vertices[i];
1092 cell->vertices = vertices;
1093 cell->dom = dom;
1094  
1095 return cell;
1096 error:
1097 isl_cell_free(cell);
1098 isl_vertices_free(vertices);
1099 isl_basic_set_free(dom);
1100 return NULL;
1101 }
1102  
1103 void isl_cell_free(__isl_take isl_cell *cell)
1104 {
1105 if (!cell)
1106 return;
1107  
1108 isl_vertices_free(cell->vertices);
1109 free(cell->ids);
1110 isl_basic_set_free(cell->dom);
1111 free(cell);
1112 }
1113  
1114 /* Create a tableau of the cone obtained by first homogenizing the given
1115 * polytope and then making all inequalities strict by setting the
1116 * constant term to -1.
1117 */
1118 static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_set *bset)
1119 {
1120 int i;
1121 isl_vec *c = NULL;
1122 struct isl_tab *tab;
1123  
1124 if (!bset)
1125 return NULL;
1126 tab = isl_tab_alloc(bset->ctx, bset->n_ineq + 1,
1127 1 + isl_basic_set_total_dim(bset), 0);
1128 if (!tab)
1129 return NULL;
1130 tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL);
1131 if (ISL_F_ISSET(bset, ISL_BASIC_MAP_EMPTY)) {
1132 if (isl_tab_mark_empty(tab) < 0)
1133 goto error;
1134 return tab;
1135 }
1136  
1137 c = isl_vec_alloc(bset->ctx, 1 + 1 + isl_basic_set_total_dim(bset));
1138 if (!c)
1139 goto error;
1140  
1141 isl_int_set_si(c->el[0], 0);
1142 for (i = 0; i < bset->n_eq; ++i) {
1143 isl_seq_cpy(c->el + 1, bset->eq[i], c->size - 1);
1144 if (isl_tab_add_eq(tab, c->el) < 0)
1145 goto error;
1146 }
1147  
1148 isl_int_set_si(c->el[0], -1);
1149 for (i = 0; i < bset->n_ineq; ++i) {
1150 isl_seq_cpy(c->el + 1, bset->ineq[i], c->size - 1);
1151 if (isl_tab_add_ineq(tab, c->el) < 0)
1152 goto error;
1153 if (tab->empty) {
1154 isl_vec_free(c);
1155 return tab;
1156 }
1157 }
1158  
1159 isl_seq_clr(c->el + 1, c->size - 1);
1160 isl_int_set_si(c->el[1], 1);
1161 if (isl_tab_add_ineq(tab, c->el) < 0)
1162 goto error;
1163  
1164 isl_vec_free(c);
1165 return tab;
1166 error:
1167 isl_vec_free(c);
1168 isl_tab_free(tab);
1169 return NULL;
1170 }
1171  
1172 /* Compute an interior point of "bset" by selecting an interior
1173 * point in homogeneous space and projecting the point back down.
1174 */
1175 static __isl_give isl_vec *isl_basic_set_interior_point(
1176 __isl_keep isl_basic_set *bset)
1177 {
1178 isl_vec *vec;
1179 struct isl_tab *tab;
1180  
1181 tab = tab_for_shifted_cone(bset);
1182 vec = isl_tab_get_sample_value(tab);
1183 isl_tab_free(tab);
1184 if (!vec)
1185 return NULL;
1186  
1187 isl_seq_cpy(vec->el, vec->el + 1, vec->size - 1);
1188 vec->size--;
1189  
1190 return vec;
1191 }
1192  
1193 /* Call "fn" on all chambers of the parametric polytope with the shared
1194 * facets of neighboring chambers only appearing in one of the chambers.
1195 *
1196 * We pick an interior point from one of the chambers and then make
1197 * all constraints that do not satisfy this point strict.
1198 */
1199 int isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices *vertices,
1200 int (*fn)(__isl_take isl_cell *cell, void *user), void *user)
1201 {
1202 int i, j;
1203 isl_vec *vec;
1204 isl_int v;
1205 isl_cell *cell;
1206  
1207 if (!vertices)
1208 return -1;
1209  
1210 if (vertices->n_chambers == 0)
1211 return 0;
1212  
1213 if (vertices->n_chambers == 1) {
1214 isl_basic_set *dom = isl_basic_set_copy(vertices->c[0].dom);
1215 dom = isl_basic_set_set_integral(dom);
1216 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, 0);
1217 if (!cell)
1218 return -1;
1219 return fn(cell, user);
1220 }
1221  
1222 vec = isl_basic_set_interior_point(vertices->c[0].dom);
1223 if (!vec)
1224 return -1;
1225  
1226 isl_int_init(v);
1227  
1228 for (i = 0; i < vertices->n_chambers; ++i) {
1229 int r;
1230 isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);
1231 dom = isl_basic_set_cow(dom);
1232 if (!dom)
1233 goto error;
1234 for (j = 0; i && j < dom->n_ineq; ++j) {
1235 isl_seq_inner_product(vec->el, dom->ineq[j], vec->size,
1236 &v);
1237 if (!isl_int_is_neg(v))
1238 continue;
1239 isl_int_sub_ui(dom->ineq[j][0], dom->ineq[j][0], 1);
1240 }
1241 dom = isl_basic_set_set_integral(dom);
1242 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);
1243 if (!cell)
1244 goto error;
1245 r = fn(cell, user);
1246 if (r < 0)
1247 goto error;
1248 }
1249  
1250 isl_int_clear(v);
1251 isl_vec_free(vec);
1252  
1253 return 0;
1254 error:
1255 isl_int_clear(v);
1256 isl_vec_free(vec);
1257 return -1;
1258 }
1259  
1260 int isl_vertices_foreach_cell(__isl_keep isl_vertices *vertices,
1261 int (*fn)(__isl_take isl_cell *cell, void *user), void *user)
1262 {
1263 int i;
1264 isl_cell *cell;
1265  
1266 if (!vertices)
1267 return -1;
1268  
1269 if (vertices->n_chambers == 0)
1270 return 0;
1271  
1272 for (i = 0; i < vertices->n_chambers; ++i) {
1273 int r;
1274 isl_basic_set *dom = isl_basic_set_copy(vertices->c[i].dom);
1275  
1276 cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i);
1277 if (!cell)
1278 return -1;
1279  
1280 r = fn(cell, user);
1281 if (r < 0)
1282 return -1;
1283 }
1284  
1285 return 0;
1286 }
1287  
1288 int isl_vertices_foreach_vertex(__isl_keep isl_vertices *vertices,
1289 int (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)
1290 {
1291 int i;
1292 isl_vertex *vertex;
1293  
1294 if (!vertices)
1295 return -1;
1296  
1297 if (vertices->n_vertices == 0)
1298 return 0;
1299  
1300 for (i = 0; i < vertices->n_vertices; ++i) {
1301 int r;
1302  
1303 vertex = isl_vertex_alloc(isl_vertices_copy(vertices), i);
1304 if (!vertex)
1305 return -1;
1306  
1307 r = fn(vertex, user);
1308 if (r < 0)
1309 return -1;
1310 }
1311  
1312 return 0;
1313 }
1314  
1315 int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
1316 int (*fn)(__isl_take isl_vertex *vertex, void *user), void *user)
1317 {
1318 int i;
1319 isl_vertex *vertex;
1320  
1321 if (!cell)
1322 return -1;
1323  
1324 if (cell->n_vertices == 0)
1325 return 0;
1326  
1327 for (i = 0; i < cell->n_vertices; ++i) {
1328 int r;
1329  
1330 vertex = isl_vertex_alloc(isl_vertices_copy(cell->vertices),
1331 cell->ids[i]);
1332 if (!vertex)
1333 return -1;
1334  
1335 r = fn(vertex, user);
1336 if (r < 0)
1337 return -1;
1338 }
1339  
1340 return 0;
1341 }
1342  
1343 isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices)
1344 {
1345 return vertices ? vertices->bset->ctx : NULL;
1346 }
1347  
1348 int isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices)
1349 {
1350 return vertices ? vertices->n_vertices : -1;
1351 }
1352  
1353 __isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph,
1354 __isl_take isl_vertices *vertices)
1355 {
1356 int i;
1357 isl_morph *param_morph = NULL;
1358  
1359 if (!morph || !vertices)
1360 goto error;
1361  
1362 isl_assert(vertices->bset->ctx, vertices->ref == 1, goto error);
1363  
1364 param_morph = isl_morph_copy(morph);
1365 param_morph = isl_morph_dom_params(param_morph);
1366 param_morph = isl_morph_ran_params(param_morph);
1367  
1368 for (i = 0; i < vertices->n_vertices; ++i) {
1369 vertices->v[i].dom = isl_morph_basic_set(
1370 isl_morph_copy(param_morph), vertices->v[i].dom);
1371 vertices->v[i].vertex = isl_morph_basic_set(
1372 isl_morph_copy(morph), vertices->v[i].vertex);
1373 if (!vertices->v[i].vertex)
1374 goto error;
1375 }
1376  
1377 for (i = 0; i < vertices->n_chambers; ++i) {
1378 vertices->c[i].dom = isl_morph_basic_set(
1379 isl_morph_copy(param_morph), vertices->c[i].dom);
1380 if (!vertices->c[i].dom)
1381 goto error;
1382 }
1383  
1384 isl_morph_free(param_morph);
1385 isl_morph_free(morph);
1386 return vertices;
1387 error:
1388 isl_morph_free(param_morph);
1389 isl_morph_free(morph);
1390 isl_vertices_free(vertices);
1391 return NULL;
1392 }
1393  
1394 /* Construct a simplex isl_cell spanned by the vertices with indices in
1395 * "simplex_ids" and "other_ids" and call "fn" on this isl_cell.
1396 */
1397 static int call_on_simplex(__isl_keep isl_cell *cell,
1398 int *simplex_ids, int n_simplex, int *other_ids, int n_other,
1399 int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1400 {
1401 int i;
1402 isl_ctx *ctx;
1403 struct isl_cell *simplex;
1404  
1405 ctx = isl_cell_get_ctx(cell);
1406  
1407 simplex = isl_calloc_type(ctx, struct isl_cell);
1408 if (!simplex)
1409 return -1;
1410 simplex->vertices = isl_vertices_copy(cell->vertices);
1411 if (!simplex->vertices)
1412 goto error;
1413 simplex->dom = isl_basic_set_copy(cell->dom);
1414 if (!simplex->dom)
1415 goto error;
1416 simplex->n_vertices = n_simplex + n_other;
1417 simplex->ids = isl_alloc_array(ctx, int, simplex->n_vertices);
1418 if (!simplex->ids)
1419 goto error;
1420  
1421 for (i = 0; i < n_simplex; ++i)
1422 simplex->ids[i] = simplex_ids[i];
1423 for (i = 0; i < n_other; ++i)
1424 simplex->ids[n_simplex + i] = other_ids[i];
1425  
1426 return fn(simplex, user);
1427 error:
1428 isl_cell_free(simplex);
1429 return -1;
1430 }
1431  
1432 /* Check whether the parametric vertex described by "vertex"
1433 * lies on the facet corresponding to constraint "facet" of "bset".
1434 * The isl_vec "v" is a temporary vector than can be used by this function.
1435 *
1436 * We eliminate the variables from the facet constraint using the
1437 * equalities defining the vertex and check if the result is identical
1438 * to zero.
1439 *
1440 * It would probably be better to keep track of the constraints defining
1441 * a vertex during the vertex construction so that we could simply look
1442 * it up here.
1443 */
1444 static int vertex_on_facet(__isl_keep isl_basic_set *vertex,
1445 __isl_keep isl_basic_set *bset, int facet, __isl_keep isl_vec *v)
1446 {
1447 int i;
1448 isl_int m;
1449  
1450 isl_seq_cpy(v->el, bset->ineq[facet], v->size);
1451  
1452 isl_int_init(m);
1453 for (i = 0; i < vertex->n_eq; ++i) {
1454 int k = isl_seq_last_non_zero(vertex->eq[i], v->size);
1455 isl_seq_elim(v->el, vertex->eq[i], k, v->size, &m);
1456 }
1457 isl_int_clear(m);
1458  
1459 return isl_seq_first_non_zero(v->el, v->size) == -1;
1460 }
1461  
1462 /* Triangulate the polytope spanned by the vertices with ids
1463 * in "simplex_ids" and "other_ids" and call "fn" on each of
1464 * the resulting simplices.
1465 * If the input polytope is already a simplex, we simply call "fn".
1466 * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids".
1467 * Then we consider each facet of "bset" that does not contain the point
1468 * we just picked, but does contain some of the other points in "other_ids"
1469 * and call ourselves recursively on the polytope spanned by the new
1470 * "simplex_ids" and those points in "other_ids" that lie on the facet.
1471 */
1472 static int triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v,
1473 int *simplex_ids, int n_simplex, int *other_ids, int n_other,
1474 int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1475 {
1476 int i, j, k;
1477 int d, nparam;
1478 int *ids;
1479 isl_ctx *ctx;
1480 isl_basic_set *vertex;
1481 isl_basic_set *bset;
1482  
1483 ctx = isl_cell_get_ctx(cell);
1484 d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
1485 nparam = isl_basic_set_dim(cell->vertices->bset, isl_dim_param);
1486  
1487 if (n_simplex + n_other == d + 1)
1488 return call_on_simplex(cell, simplex_ids, n_simplex,
1489 other_ids, n_other, fn, user);
1490  
1491 simplex_ids[n_simplex] = other_ids[0];
1492 vertex = cell->vertices->v[other_ids[0]].vertex;
1493 bset = cell->vertices->bset;
1494  
1495 ids = isl_alloc_array(ctx, int, n_other - 1);
1496 for (i = 0; i < bset->n_ineq; ++i) {
1497 if (isl_seq_first_non_zero(bset->ineq[i] + 1 + nparam, d) == -1)
1498 continue;
1499 if (vertex_on_facet(vertex, bset, i, v))
1500 continue;
1501  
1502 for (j = 1, k = 0; j < n_other; ++j) {
1503 isl_basic_set *ov;
1504 ov = cell->vertices->v[other_ids[j]].vertex;
1505 if (vertex_on_facet(ov, bset, i, v))
1506 ids[k++] = other_ids[j];
1507 }
1508 if (k == 0)
1509 continue;
1510  
1511 if (triangulate(cell, v, simplex_ids, n_simplex + 1,
1512 ids, k, fn, user) < 0)
1513 goto error;
1514 }
1515 free(ids);
1516  
1517 return 0;
1518 error:
1519 free(ids);
1520 return -1;
1521 }
1522  
1523 /* Triangulate the given cell and call "fn" on each of the resulting
1524 * simplices.
1525 */
1526 int isl_cell_foreach_simplex(__isl_take isl_cell *cell,
1527 int (*fn)(__isl_take isl_cell *simplex, void *user), void *user)
1528 {
1529 int d, total;
1530 int r;
1531 isl_ctx *ctx;
1532 isl_vec *v = NULL;
1533 int *simplex_ids = NULL;
1534  
1535 if (!cell)
1536 return -1;
1537  
1538 d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set);
1539 total = isl_basic_set_total_dim(cell->vertices->bset);
1540  
1541 if (cell->n_vertices == d + 1)
1542 return fn(cell, user);
1543  
1544 ctx = isl_cell_get_ctx(cell);
1545 simplex_ids = isl_alloc_array(ctx, int, d + 1);
1546 if (!simplex_ids)
1547 goto error;
1548  
1549 v = isl_vec_alloc(ctx, 1 + total);
1550 if (!v)
1551 goto error;
1552  
1553 r = triangulate(cell, v, simplex_ids, 0,
1554 cell->ids, cell->n_vertices, fn, user);
1555  
1556 isl_vec_free(v);
1557 free(simplex_ids);
1558  
1559 isl_cell_free(cell);
1560  
1561 return r;
1562 error:
1563 free(simplex_ids);
1564 isl_vec_free(v);
1565 isl_cell_free(cell);
1566 return -1;
1567 }