?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'maint'
[isl.git] / isl_map_subtract.c
blob2c958c766f9e801469503df13f95fa4d976a9edb
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
9
10 #include <isl_map_private.h>
11 #include <isl/seq.h>
12 #include <isl/set.h>
13 #include <isl/map.h>
14 #include "isl_tab.h"
15 #include <isl_point_private.h>
16
17 /* Expand the constraint "c" into "v". The initial "dim" dimensions
18 * are the same, but "v" may have more divs than "c" and the divs of "c"
19 * may appear in different positions in "v".
20 * The number of divs in "c" is given by "n_div" and the mapping
21 * of divs in "c" to divs in "v" is given by "div_map".
22 *
23 * Although it shouldn't happen in practice, it is theoretically
24 * possible that two or more divs in "c" are mapped to the same div in "v".
25 * These divs are then necessarily the same, so we simply add their
26 * coefficients.
27 */
28 static void expand_constraint(isl_vec *v, unsigned dim,
29 isl_int *c, int *div_map, unsigned n_div)
30 {
31 int i;
32
33 isl_seq_cpy(v->el, c, 1 + dim);
34 isl_seq_clr(v->el + 1 + dim, v->size - (1 + dim));
35
36 for (i = 0; i < n_div; ++i) {
37 int pos = 1 + dim + div_map[i];
38 isl_int_add(v->el[pos], v->el[pos], c[1 + dim + i]);
39 }
40 }
41
42 /* Add all constraints of bmap to tab. The equalities of bmap
43 * are added as a pair of inequalities.
44 */
45 static int tab_add_constraints(struct isl_tab *tab,
46 __isl_keep isl_basic_map *bmap, int *div_map)
47 {
48 int i;
49 unsigned dim;
50 unsigned tab_total;
51 unsigned bmap_total;
52 isl_vec *v;
53
54 if (!tab || !bmap)
55 return -1;
56
57 tab_total = isl_basic_map_total_dim(tab->bmap);
58 bmap_total = isl_basic_map_total_dim(bmap);
59 dim = isl_space_dim(tab->bmap->dim, isl_dim_all);
60
61 if (isl_tab_extend_cons(tab, 2 * bmap->n_eq + bmap->n_ineq) < 0)
62 return -1;
63
64 v = isl_vec_alloc(bmap->ctx, 1 + tab_total);
65 if (!v)
66 return -1;
67
68 for (i = 0; i < bmap->n_eq; ++i) {
69 expand_constraint(v, dim, bmap->eq[i], div_map, bmap->n_div);
70 if (isl_tab_add_ineq(tab, v->el) < 0)
71 goto error;
72 isl_seq_neg(bmap->eq[i], bmap->eq[i], 1 + bmap_total);
73 expand_constraint(v, dim, bmap->eq[i], div_map, bmap->n_div);
74 if (isl_tab_add_ineq(tab, v->el) < 0)
75 goto error;
76 isl_seq_neg(bmap->eq[i], bmap->eq[i], 1 + bmap_total);
77 if (tab->empty)
78 break;
79 }
80
81 for (i = 0; i < bmap->n_ineq; ++i) {
82 expand_constraint(v, dim, bmap->ineq[i], div_map, bmap->n_div);
83 if (isl_tab_add_ineq(tab, v->el) < 0)
84 goto error;
85 if (tab->empty)
86 break;
87 }
88
89 isl_vec_free(v);
90 return 0;
91 error:
92 isl_vec_free(v);
93 return -1;
94 }
95
96 /* Add a specific constraint of bmap (or its opposite) to tab.
97 * The position of the constraint is specified by "c", where
98 * the equalities of bmap are counted twice, once for the inequality
99 * that is equal to the equality, and once for its negation.
100 */
101 static int tab_add_constraint(struct isl_tab *tab,
102 __isl_keep isl_basic_map *bmap, int *div_map, int c, int oppose)
103 {
104 unsigned dim;
105 unsigned tab_total;
106 unsigned bmap_total;
107 isl_vec *v;
108 int r;
109
110 if (!tab || !bmap)
111 return -1;
112
113 tab_total = isl_basic_map_total_dim(tab->bmap);
114 bmap_total = isl_basic_map_total_dim(bmap);
115 dim = isl_space_dim(tab->bmap->dim, isl_dim_all);
116
117 v = isl_vec_alloc(bmap->ctx, 1 + tab_total);
118 if (!v)
119 return -1;
120
121 if (c < 2 * bmap->n_eq) {
122 if ((c % 2) != oppose)
123 isl_seq_neg(bmap->eq[c/2], bmap->eq[c/2],
124 1 + bmap_total);
125 if (oppose)
126 isl_int_sub_ui(bmap->eq[c/2][0], bmap->eq[c/2][0], 1);
127 expand_constraint(v, dim, bmap->eq[c/2], div_map, bmap->n_div);
128 r = isl_tab_add_ineq(tab, v->el);
129 if (oppose)
130 isl_int_add_ui(bmap->eq[c/2][0], bmap->eq[c/2][0], 1);
131 if ((c % 2) != oppose)
132 isl_seq_neg(bmap->eq[c/2], bmap->eq[c/2],
133 1 + bmap_total);
134 } else {
135 c -= 2 * bmap->n_eq;
136 if (oppose) {
137 isl_seq_neg(bmap->ineq[c], bmap->ineq[c],
138 1 + bmap_total);
139 isl_int_sub_ui(bmap->ineq[c][0], bmap->ineq[c][0], 1);
140 }
141 expand_constraint(v, dim, bmap->ineq[c], div_map, bmap->n_div);
142 r = isl_tab_add_ineq(tab, v->el);
143 if (oppose) {
144 isl_int_add_ui(bmap->ineq[c][0], bmap->ineq[c][0], 1);
145 isl_seq_neg(bmap->ineq[c], bmap->ineq[c],
146 1 + bmap_total);
147 }
148 }
149
150 isl_vec_free(v);
151 return r;
152 }
153
154 static int tab_add_divs(struct isl_tab *tab, __isl_keep isl_basic_map *bmap,
155 int **div_map)
156 {
157 int i, j;
158 struct isl_vec *vec;
159 unsigned total;
160 unsigned dim;
161
162 if (!bmap)
163 return -1;
164 if (!bmap->n_div)
165 return 0;
166
167 if (!*div_map)
168 *div_map = isl_alloc_array(bmap->ctx, int, bmap->n_div);
169 if (!*div_map)
170 return -1;
171
172 total = isl_basic_map_total_dim(tab->bmap);
173 dim = total - tab->bmap->n_div;
174 vec = isl_vec_alloc(bmap->ctx, 2 + total + bmap->n_div);
175 if (!vec)
176 return -1;
177
178 for (i = 0; i < bmap->n_div; ++i) {
179 isl_seq_cpy(vec->el, bmap->div[i], 2 + dim);
180 isl_seq_clr(vec->el + 2 + dim, tab->bmap->n_div);
181 for (j = 0; j < i; ++j)
182 isl_int_set(vec->el[2 + dim + (*div_map)[j]],
183 bmap->div[i][2 + dim + j]);
184 for (j = 0; j < tab->bmap->n_div; ++j)
185 if (isl_seq_eq(tab->bmap->div[j],
186 vec->el, 2 + dim + tab->bmap->n_div))
187 break;
188 (*div_map)[i] = j;
189 if (j == tab->bmap->n_div) {
190 vec->size = 2 + dim + tab->bmap->n_div;
191 if (isl_tab_add_div(tab, vec, NULL, NULL) < 0)
192 goto error;
193 }
194 }
195
196 isl_vec_free(vec);
197
198 return 0;
199 error:
200 isl_vec_free(vec);
201
202 return -1;
203 }
204
205 /* Freeze all constraints of tableau tab.
206 */
207 static int tab_freeze_constraints(struct isl_tab *tab)
208 {
209 int i;
210
211 for (i = 0; i < tab->n_con; ++i)
212 if (isl_tab_freeze_constraint(tab, i) < 0)
213 return -1;
214
215 return 0;
216 }
217
218 /* Check for redundant constraints starting at offset.
219 * Put the indices of the redundant constraints in index
220 * and return the number of redundant constraints.
221 */
222 static int n_non_redundant(isl_ctx *ctx, struct isl_tab *tab,
223 int offset, int **index)
224 {
225 int i, n;
226 int n_test = tab->n_con - offset;
227
228 if (isl_tab_detect_redundant(tab) < 0)
229 return -1;
230
231 if (!*index)
232 *index = isl_alloc_array(ctx, int, n_test);
233 if (!*index)
234 return -1;
235
236 for (n = 0, i = 0; i < n_test; ++i) {
237 int r;
238 r = isl_tab_is_redundant(tab, offset + i);
239 if (r < 0)
240 return -1;
241 if (r)
242 continue;
243 (*index)[n++] = i;
244 }
245
246 return n;
247 }
248
249 /* basic_map_collect_diff calls add on each of the pieces of
250 * the set difference between bmap and map until the add method
251 * return a negative value.
252 */
253 struct isl_diff_collector {
254 int (*add)(struct isl_diff_collector *dc,
255 __isl_take isl_basic_map *bmap);
256 };
257
258 /* Compute the set difference between bmap and map and call
259 * dc->add on each of the piece until this function returns
260 * a negative value.
261 * Return 0 on success and -1 on error. dc->add returning
262 * a negative value is treated as an error, but the calling
263 * function can interpret the results based on the state of dc.
264 *
265 * Assumes that map has known divs.
266 *
267 * The difference is computed by a backtracking algorithm.
268 * Each level corresponds to a basic map in "map".
269 * When a node in entered for the first time, we check
270 * if the corresonding basic map intersects the current piece
271 * of "bmap". If not, we move to the next level.
272 * Otherwise, we split the current piece into as many
273 * pieces as there are non-redundant constraints of the current
274 * basic map in the intersection. Each of these pieces is
275 * handled by a child of the current node.
276 * In particular, if there are n non-redundant constraints,
277 * then for each 0 <= i < n, a piece is cut off by adding
278 * constraints 0 <= j < i and adding the opposite of constraint i.
279 * If there are no non-redundant constraints, meaning that the current
280 * piece is a subset of the current basic map, then we simply backtrack.
281 *
282 * In the leaves, we check if the remaining piece has any integer points
283 * and if so, pass it along to dc->add. As a special case, if nothing
284 * has been removed when we end up in a leaf, we simply pass along
285 * the original basic map.
286 */
287 static int basic_map_collect_diff(__isl_take isl_basic_map *bmap,
288 __isl_take isl_map *map, struct isl_diff_collector *dc)
289 {
290 int i;
291 int modified;
292 int level;
293 int init;
294 int empty;
295 isl_ctx *ctx;
296 struct isl_tab *tab = NULL;
297 struct isl_tab_undo **snap = NULL;
298 int *k = NULL;
299 int *n = NULL;
300 int **index = NULL;
301 int **div_map = NULL;
302
303 empty = isl_basic_map_is_empty(bmap);
304 if (empty) {
305 isl_basic_map_free(bmap);
306 isl_map_free(map);
307 return empty < 0 ? -1 : 0;
308 }
309
310 bmap = isl_basic_map_cow(bmap);
311 map = isl_map_cow(map);
312
313 if (!bmap || !map)
314 goto error;
315
316 ctx = map->ctx;
317 snap = isl_alloc_array(map->ctx, struct isl_tab_undo *, map->n);
318 k = isl_alloc_array(map->ctx, int, map->n);
319 n = isl_alloc_array(map->ctx, int, map->n);
320 index = isl_calloc_array(map->ctx, int *, map->n);
321 div_map = isl_calloc_array(map->ctx, int *, map->n);
322 if (!snap || !k || !n || !index || !div_map)
323 goto error;
324
325 bmap = isl_basic_map_order_divs(bmap);
326 map = isl_map_order_divs(map);
327
328 tab = isl_tab_from_basic_map(bmap, 1);
329 if (!tab)
330 goto error;
331
332 modified = 0;
333 level = 0;
334 init = 1;
335
336 while (level >= 0) {
337 if (level >= map->n) {
338 int empty;
339 struct isl_basic_map *bm;
340 if (!modified) {
341 if (dc->add(dc, isl_basic_map_copy(bmap)) < 0)
342 goto error;
343 break;
344 }
345 bm = isl_basic_map_copy(tab->bmap);
346 bm = isl_basic_map_cow(bm);
347 bm = isl_basic_map_update_from_tab(bm, tab);
348 bm = isl_basic_map_simplify(bm);
349 bm = isl_basic_map_finalize(bm);
350 empty = isl_basic_map_is_empty(bm);
351 if (empty)
352 isl_basic_map_free(bm);
353 else if (dc->add(dc, bm) < 0)
354 goto error;
355 if (empty < 0)
356 goto error;
357 level--;
358 init = 0;
359 continue;
360 }
361 if (init) {
362 int offset;
363 struct isl_tab_undo *snap2;
364 snap2 = isl_tab_snap(tab);
365 if (tab_add_divs(tab, map->p[level],
366 &div_map[level]) < 0)
367 goto error;
368 offset = tab->n_con;
369 snap[level] = isl_tab_snap(tab);
370 if (tab_freeze_constraints(tab) < 0)
371 goto error;
372 if (tab_add_constraints(tab, map->p[level],
373 div_map[level]) < 0)
374 goto error;
375 k[level] = 0;
376 n[level] = 0;
377 if (tab->empty) {
378 if (isl_tab_rollback(tab, snap2) < 0)
379 goto error;
380 level++;
381 continue;
382 }
383 modified = 1;
384 n[level] = n_non_redundant(ctx, tab, offset,
385 &index[level]);
386 if (n[level] < 0)
387 goto error;
388 if (n[level] == 0) {
389 level--;
390 init = 0;
391 continue;
392 }
393 if (isl_tab_rollback(tab, snap[level]) < 0)
394 goto error;
395 if (tab_add_constraint(tab, map->p[level],
396 div_map[level], index[level][0], 1) < 0)
397 goto error;
398 level++;
399 continue;
400 } else {
401 if (k[level] + 1 >= n[level]) {
402 level--;
403 continue;
404 }
405 if (isl_tab_rollback(tab, snap[level]) < 0)
406 goto error;
407 if (tab_add_constraint(tab, map->p[level],
408 div_map[level],
409 index[level][k[level]], 0) < 0)
410 goto error;
411 snap[level] = isl_tab_snap(tab);
412 k[level]++;
413 if (tab_add_constraint(tab, map->p[level],
414 div_map[level],
415 index[level][k[level]], 1) < 0)
416 goto error;
417 level++;
418 init = 1;
419 continue;
420 }
421 }
422
423 isl_tab_free(tab);
424 free(snap);
425 free(n);
426 free(k);
427 for (i = 0; index && i < map->n; ++i)
428 free(index[i]);
429 free(index);
430 for (i = 0; div_map && i < map->n; ++i)
431 free(div_map[i]);
432 free(div_map);
433
434 isl_basic_map_free(bmap);
435 isl_map_free(map);
436
437 return 0;
438 error:
439 isl_tab_free(tab);
440 free(snap);
441 free(n);
442 free(k);
443 for (i = 0; index && i < map->n; ++i)
444 free(index[i]);
445 free(index);
446 for (i = 0; div_map && i < map->n; ++i)
447 free(div_map[i]);
448 free(div_map);
449 isl_basic_map_free(bmap);
450 isl_map_free(map);
451 return -1;
452 }
453
454 /* A diff collector that actually collects all parts of the
455 * set difference in the field diff.
456 */
457 struct isl_subtract_diff_collector {
458 struct isl_diff_collector dc;
459 struct isl_map *diff;
460 };
461
462 /* isl_subtract_diff_collector callback.
463 */
464 static int basic_map_subtract_add(struct isl_diff_collector *dc,
465 __isl_take isl_basic_map *bmap)
466 {
467 struct isl_subtract_diff_collector *sdc;
468 sdc = (struct isl_subtract_diff_collector *)dc;
469
470 sdc->diff = isl_map_union_disjoint(sdc->diff,
471 isl_map_from_basic_map(bmap));
472
473 return sdc->diff ? 0 : -1;
474 }
475
476 /* Return the set difference between bmap and map.
477 */
478 static __isl_give isl_map *basic_map_subtract(__isl_take isl_basic_map *bmap,
479 __isl_take isl_map *map)
480 {
481 struct isl_subtract_diff_collector sdc;
482 sdc.dc.add = &basic_map_subtract_add;
483 sdc.diff = isl_map_empty_like_basic_map(bmap);
484 if (basic_map_collect_diff(bmap, map, &sdc.dc) < 0) {
485 isl_map_free(sdc.diff);
486 sdc.diff = NULL;
487 }
488 return sdc.diff;
489 }
490
491 /* Return the set difference between map1 and map2.
492 * (U_i A_i) \ (U_j B_j) is computed as U_i (A_i \ (U_j B_j))
493 */
494 static __isl_give isl_map *map_subtract( __isl_take isl_map *map1,
495 __isl_take isl_map *map2)
496 {
497 int i;
498 struct isl_map *diff;
499
500 if (!map1 || !map2)
501 goto error;
502
503 isl_assert(map1->ctx, isl_space_is_equal(map1->dim, map2->dim), goto error);
504
505 if (isl_map_is_empty(map2)) {
506 isl_map_free(map2);
507 return map1;
508 }
509
510 map1 = isl_map_compute_divs(map1);
511 map2 = isl_map_compute_divs(map2);
512 if (!map1 || !map2)
513 goto error;
514
515 map1 = isl_map_remove_empty_parts(map1);
516 map2 = isl_map_remove_empty_parts(map2);
517
518 diff = isl_map_empty_like(map1);
519 for (i = 0; i < map1->n; ++i) {
520 struct isl_map *d;
521 d = basic_map_subtract(isl_basic_map_copy(map1->p[i]),
522 isl_map_copy(map2));
523 if (ISL_F_ISSET(map1, ISL_MAP_DISJOINT))
524 diff = isl_map_union_disjoint(diff, d);
525 else
526 diff = isl_map_union(diff, d);
527 }
528
529 isl_map_free(map1);
530 isl_map_free(map2);
531
532 return diff;
533 error:
534 isl_map_free(map1);
535 isl_map_free(map2);
536 return NULL;
537 }
538
539 __isl_give isl_map *isl_map_subtract( __isl_take isl_map *map1,
540 __isl_take isl_map *map2)
541 {
542 return isl_map_align_params_map_map_and(map1, map2, &map_subtract);
543 }
544
545 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
546 {
547 return (struct isl_set *)
548 isl_map_subtract(
549 (struct isl_map *)set1, (struct isl_map *)set2);
550 }
551
552 /* Remove the elements of "dom" from the domain of "map".
553 */
554 static __isl_give isl_map *map_subtract_domain(__isl_take isl_map *map,
555 __isl_take isl_set *dom)
556 {
557 isl_map *ext_dom;
558
559 if (!isl_map_compatible_domain(map, dom))
560 isl_die(isl_set_get_ctx(dom), isl_error_invalid,
561 "incompatible spaces", goto error);
562
563 ext_dom = isl_map_universe(isl_map_get_space(map));
564 ext_dom = isl_map_intersect_domain(ext_dom, dom);
565 return isl_map_subtract(map, ext_dom);
566 error:
567 isl_map_free(map);
568 isl_set_free(dom);
569 return NULL;
570 }
571
572 __isl_give isl_map *isl_map_subtract_domain(__isl_take isl_map *map,
573 __isl_take isl_set *dom)
574 {
575 return isl_map_align_params_map_map_and(map, dom, &map_subtract_domain);
576 }
577
578 /* Remove the elements of "dom" from the range of "map".
579 */
580 static __isl_give isl_map *map_subtract_range(__isl_take isl_map *map,
581 __isl_take isl_set *dom)
582 {
583 isl_map *ext_dom;
584
585 if (!isl_map_compatible_range(map, dom))
586 isl_die(isl_set_get_ctx(dom), isl_error_invalid,
587 "incompatible spaces", goto error);
588
589 ext_dom = isl_map_universe(isl_map_get_space(map));
590 ext_dom = isl_map_intersect_range(ext_dom, dom);
591 return isl_map_subtract(map, ext_dom);
592 error:
593 isl_map_free(map);
594 isl_set_free(dom);
595 return NULL;
596 }
597
598 __isl_give isl_map *isl_map_subtract_range(__isl_take isl_map *map,
599 __isl_take isl_set *dom)
600 {
601 return isl_map_align_params_map_map_and(map, dom, &map_subtract_range);
602 }
603
604 /* A diff collector that aborts as soon as its add function is called,
605 * setting empty to 0.
606 */
607 struct isl_is_empty_diff_collector {
608 struct isl_diff_collector dc;
609 int empty;
610 };
611
612 /* isl_is_empty_diff_collector callback.
613 */
614 static int basic_map_is_empty_add(struct isl_diff_collector *dc,
615 __isl_take isl_basic_map *bmap)
616 {
617 struct isl_is_empty_diff_collector *edc;
618 edc = (struct isl_is_empty_diff_collector *)dc;
619
620 edc->empty = 0;
621
622 isl_basic_map_free(bmap);
623 return -1;
624 }
625
626 /* Check if bmap \ map is empty by computing this set difference
627 * and breaking off as soon as the difference is known to be non-empty.
628 */
629 static int basic_map_diff_is_empty(__isl_keep isl_basic_map *bmap,
630 __isl_keep isl_map *map)
631 {
632 int r;
633 struct isl_is_empty_diff_collector edc;
634
635 r = isl_basic_map_plain_is_empty(bmap);
636 if (r)
637 return r;
638
639 edc.dc.add = &basic_map_is_empty_add;
640 edc.empty = 1;
641 r = basic_map_collect_diff(isl_basic_map_copy(bmap),
642 isl_map_copy(map), &edc.dc);
643 if (!edc.empty)
644 return 0;
645
646 return r < 0 ? -1 : 1;
647 }
648
649 /* Check if map1 \ map2 is empty by checking if the set difference is empty
650 * for each of the basic maps in map1.
651 */
652 static int map_diff_is_empty(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
653 {
654 int i;
655 int is_empty = 1;
656
657 if (!map1 || !map2)
658 return -1;
659
660 for (i = 0; i < map1->n; ++i) {
661 is_empty = basic_map_diff_is_empty(map1->p[i], map2);
662 if (is_empty < 0 || !is_empty)
663 break;
664 }
665
666 return is_empty;
667 }
668
669 /* Return 1 if "bmap" contains a single element.
670 */
671 int isl_basic_map_plain_is_singleton(__isl_keep isl_basic_map *bmap)
672 {
673 if (!bmap)
674 return -1;
675 if (bmap->n_div)
676 return 0;
677 if (bmap->n_ineq)
678 return 0;
679 return bmap->n_eq == isl_basic_map_total_dim(bmap);
680 }
681
682 /* Return 1 if "map" contains a single element.
683 */
684 int isl_map_plain_is_singleton(__isl_keep isl_map *map)
685 {
686 if (!map)
687 return -1;
688 if (map->n != 1)
689 return 0;
690
691 return isl_basic_map_plain_is_singleton(map->p[0]);
692 }
693
694 /* Given a singleton basic map, extract the single element
695 * as an isl_point.
696 */
697 static __isl_give isl_point *singleton_extract_point(
698 __isl_keep isl_basic_map *bmap)
699 {
700 int j;
701 unsigned dim;
702 struct isl_vec *point;
703 isl_int m;
704
705 if (!bmap)
706 return NULL;
707
708 dim = isl_basic_map_total_dim(bmap);
709 isl_assert(bmap->ctx, bmap->n_eq == dim, return NULL);
710 point = isl_vec_alloc(bmap->ctx, 1 + dim);
711 if (!point)
712 return NULL;
713
714 isl_int_init(m);
715
716 isl_int_set_si(point->el[0], 1);
717 for (j = 0; j < bmap->n_eq; ++j) {
718 int i = dim - 1 - j;
719 isl_assert(bmap->ctx,
720 isl_seq_first_non_zero(bmap->eq[j] + 1, i) == -1,
721 goto error);
722 isl_assert(bmap->ctx,
723 isl_int_is_one(bmap->eq[j][1 + i]) ||
724 isl_int_is_negone(bmap->eq[j][1 + i]),
725 goto error);
726 isl_assert(bmap->ctx,
727 isl_seq_first_non_zero(bmap->eq[j]+1+i+1, dim-i-1) == -1,
728 goto error);
729
730 isl_int_gcd(m, point->el[0], bmap->eq[j][1 + i]);
731 isl_int_divexact(m, bmap->eq[j][1 + i], m);
732 isl_int_abs(m, m);
733 isl_seq_scale(point->el, point->el, m, 1 + i);
734 isl_int_divexact(m, point->el[0], bmap->eq[j][1 + i]);
735 isl_int_neg(m, m);
736 isl_int_mul(point->el[1 + i], m, bmap->eq[j][0]);
737 }
738
739 isl_int_clear(m);
740 return isl_point_alloc(isl_basic_map_get_space(bmap), point);
741 error:
742 isl_int_clear(m);
743 isl_vec_free(point);
744 return NULL;
745 }
746
747 /* Return 1 is the singleton map "map1" is a subset of "map2",
748 * i.e., if the single element of "map1" is also an element of "map2".
749 * Assumes "map2" has known divs.
750 */
751 static int map_is_singleton_subset(__isl_keep isl_map *map1,
752 __isl_keep isl_map *map2)
753 {
754 int i;
755 int is_subset = 0;
756 struct isl_point *point;
757
758 if (!map1 || !map2)
759 return -1;
760 if (map1->n != 1)
761 return -1;
762
763 point = singleton_extract_point(map1->p[0]);
764 if (!point)
765 return -1;
766
767 for (i = 0; i < map2->n; ++i) {
768 is_subset = isl_basic_map_contains_point(map2->p[i], point);
769 if (is_subset)
770 break;
771 }
772
773 isl_point_free(point);
774 return is_subset;
775 }
776
777 static int map_is_subset(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
778 {
779 int is_subset = 0;
780 int empty;
781 int rat1, rat2;
782
783 if (!map1 || !map2)
784 return -1;
785
786 if (!isl_map_has_equal_space(map1, map2))
787 return 0;
788
789 empty = isl_map_is_empty(map1);
790 if (empty < 0)
791 return -1;
792 if (empty)
793 return 1;
794
795 empty = isl_map_is_empty(map2);
796 if (empty < 0)
797 return -1;
798 if (empty)
799 return 0;
800
801 rat1 = isl_map_has_rational(map1);
802 rat2 = isl_map_has_rational(map2);
803 if (rat1 < 0 || rat2 < 0)
804 return -1;
805 if (rat1 && !rat2)
806 return 0;
807
808 if (isl_map_plain_is_universe(map2))
809 return 1;
810
811 map2 = isl_map_compute_divs(isl_map_copy(map2));
812 if (isl_map_plain_is_singleton(map1)) {
813 is_subset = map_is_singleton_subset(map1, map2);
814 isl_map_free(map2);
815 return is_subset;
816 }
817 is_subset = map_diff_is_empty(map1, map2);
818 isl_map_free(map2);
819
820 return is_subset;
821 }
822
823 int isl_map_is_subset(__isl_keep isl_map *map1, __isl_keep isl_map *map2)
824 {
825 return isl_map_align_params_map_map_and_test(map1, map2,
826 &map_is_subset);
827 }
828
829 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
830 {
831 return isl_map_is_subset(
832 (struct isl_map *)set1, (struct isl_map *)set2);
833 }
834
835 __isl_give isl_map *isl_map_make_disjoint(__isl_take isl_map *map)
836 {
837 int i;
838 struct isl_subtract_diff_collector sdc;
839 sdc.dc.add = &basic_map_subtract_add;
840
841 if (!map)
842 return NULL;
843 if (ISL_F_ISSET(map, ISL_MAP_DISJOINT))
844 return map;
845 if (map->n <= 1)
846 return map;
847
848 map = isl_map_compute_divs(map);
849 map = isl_map_remove_empty_parts(map);
850
851 if (!map || map->n <= 1)
852 return map;
853
854 sdc.diff = isl_map_from_basic_map(isl_basic_map_copy(map->p[0]));
855
856 for (i = 1; i < map->n; ++i) {
857 struct isl_basic_map *bmap = isl_basic_map_copy(map->p[i]);
858 struct isl_map *copy = isl_map_copy(sdc.diff);
859 if (basic_map_collect_diff(bmap, copy, &sdc.dc) < 0) {
860 isl_map_free(sdc.diff);
861 sdc.diff = NULL;
862 break;
863 }
864 }
865
866 isl_map_free(map);
867
868 return sdc.diff;
869 }
870
871 __isl_give isl_set *isl_set_make_disjoint(__isl_take isl_set *set)
872 {
873 return (struct isl_set *)isl_map_make_disjoint((struct isl_map *)set);
874 }
875
876 __isl_give isl_map *isl_map_complement(__isl_take isl_map *map)
877 {
878 isl_map *universe;
879
880 if (!map)
881 return NULL;
882
883 universe = isl_map_universe(isl_map_get_space(map));
884
885 return isl_map_subtract(universe, map);
886 }
887
888 __isl_give isl_set *isl_set_complement(__isl_take isl_set *set)
889 {
890 return isl_map_complement(set);
891 }
Integer set library