2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
12 #include <isl_map_private.h>
18 #include <isl_space_private.h>
19 #include <isl_union_map_private.h>
20 #include <isl/union_set.h>
21 #include <isl/deprecated/union_map_int.h>
23 /* Is this union set a parameter domain?
25 int isl_union_set_is_params(__isl_keep isl_union_set
*uset
)
32 if (uset
->table
.n
!= 1)
35 set
= isl_set_from_union_set(isl_union_set_copy(uset
));
36 params
= isl_set_is_params(set
);
41 static __isl_give isl_union_map
*isl_union_map_alloc(__isl_take isl_space
*dim
,
46 dim
= isl_space_params(dim
);
50 umap
= isl_calloc_type(dim
->ctx
, isl_union_map
);
56 if (isl_hash_table_init(dim
->ctx
, &umap
->table
, size
) < 0)
57 return isl_union_map_free(umap
);
62 __isl_give isl_union_map
*isl_union_map_empty(__isl_take isl_space
*dim
)
64 return isl_union_map_alloc(dim
, 16);
67 __isl_give isl_union_set
*isl_union_set_empty(__isl_take isl_space
*dim
)
69 return isl_union_map_empty(dim
);
72 isl_ctx
*isl_union_map_get_ctx(__isl_keep isl_union_map
*umap
)
74 return umap
? umap
->dim
->ctx
: NULL
;
77 isl_ctx
*isl_union_set_get_ctx(__isl_keep isl_union_set
*uset
)
79 return uset
? uset
->dim
->ctx
: NULL
;
82 __isl_give isl_space
*isl_union_map_get_space(__isl_keep isl_union_map
*umap
)
86 return isl_space_copy(umap
->dim
);
89 __isl_give isl_space
*isl_union_set_get_space(__isl_keep isl_union_set
*uset
)
91 return isl_union_map_get_space(uset
);
94 static int free_umap_entry(void **entry
, void *user
)
96 isl_map
*map
= *entry
;
101 static int add_map(__isl_take isl_map
*map
, void *user
)
103 isl_union_map
**umap
= (isl_union_map
**)user
;
105 *umap
= isl_union_map_add_map(*umap
, map
);
110 __isl_give isl_union_map
*isl_union_map_dup(__isl_keep isl_union_map
*umap
)
117 dup
= isl_union_map_empty(isl_space_copy(umap
->dim
));
118 if (isl_union_map_foreach_map(umap
, &add_map
, &dup
) < 0)
122 isl_union_map_free(dup
);
126 __isl_give isl_union_map
*isl_union_map_cow(__isl_take isl_union_map
*umap
)
134 return isl_union_map_dup(umap
);
137 struct isl_union_align
{
142 static int align_entry(void **entry
, void *user
)
144 isl_map
*map
= *entry
;
146 struct isl_union_align
*data
= user
;
148 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
149 isl_map_get_space(map
));
151 data
->res
= isl_union_map_add_map(data
->res
,
152 isl_map_realign(isl_map_copy(map
), exp
));
157 /* Align the parameters of umap along those of model.
158 * The result has the parameters of model first, in the same order
159 * as they appear in model, followed by any remaining parameters of
160 * umap that do not appear in model.
162 __isl_give isl_union_map
*isl_union_map_align_params(
163 __isl_take isl_union_map
*umap
, __isl_take isl_space
*model
)
165 struct isl_union_align data
= { NULL
, NULL
};
170 if (isl_space_match(umap
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
171 isl_space_free(model
);
175 model
= isl_space_params(model
);
176 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
180 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
182 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
183 &align_entry
, &data
) < 0)
186 isl_reordering_free(data
.exp
);
187 isl_union_map_free(umap
);
188 isl_space_free(model
);
191 isl_reordering_free(data
.exp
);
192 isl_union_map_free(umap
);
193 isl_union_map_free(data
.res
);
194 isl_space_free(model
);
198 __isl_give isl_union_set
*isl_union_set_align_params(
199 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
201 return isl_union_map_align_params(uset
, model
);
204 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
205 __isl_take isl_union_map
*umap2
)
207 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
208 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
210 umap1
= isl_union_map_cow(umap1
);
212 if (!umap1
|| !umap2
)
215 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
218 isl_union_map_free(umap2
);
222 isl_union_map_free(umap1
);
223 isl_union_map_free(umap2
);
227 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
228 __isl_take isl_union_set
*uset2
)
230 return isl_union_map_union(uset1
, uset2
);
233 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
242 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
244 return isl_union_map_copy(uset
);
247 void *isl_union_map_free(__isl_take isl_union_map
*umap
)
255 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
256 &free_umap_entry
, NULL
);
257 isl_hash_table_clear(&umap
->table
);
258 isl_space_free(umap
->dim
);
263 void *isl_union_set_free(__isl_take isl_union_set
*uset
)
265 return isl_union_map_free(uset
);
268 static int has_dim(const void *entry
, const void *val
)
270 isl_map
*map
= (isl_map
*)entry
;
271 isl_space
*dim
= (isl_space
*)val
;
273 return isl_space_is_equal(map
->dim
, dim
);
276 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
277 __isl_take isl_map
*map
)
280 struct isl_hash_table_entry
*entry
;
285 if (isl_map_plain_is_empty(map
)) {
290 if (!isl_space_match(map
->dim
, isl_dim_param
, umap
->dim
, isl_dim_param
)) {
291 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
292 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
295 umap
= isl_union_map_cow(umap
);
300 hash
= isl_space_get_hash(map
->dim
);
301 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
302 &has_dim
, map
->dim
, 1);
309 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
318 isl_union_map_free(umap
);
322 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
323 __isl_take isl_set
*set
)
325 return isl_union_map_add_map(uset
, (isl_map
*)set
);
328 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
336 dim
= isl_map_get_space(map
);
337 dim
= isl_space_params(dim
);
338 umap
= isl_union_map_empty(dim
);
339 umap
= isl_union_map_add_map(umap
, map
);
344 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
346 return isl_union_map_from_map((isl_map
*)set
);
349 __isl_give isl_union_map
*isl_union_map_from_basic_map(
350 __isl_take isl_basic_map
*bmap
)
352 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
355 __isl_give isl_union_set
*isl_union_set_from_basic_set(
356 __isl_take isl_basic_set
*bset
)
358 return isl_union_map_from_basic_map(bset
);
361 struct isl_union_map_foreach_data
363 int (*fn
)(__isl_take isl_map
*map
, void *user
);
367 static int call_on_copy(void **entry
, void *user
)
369 isl_map
*map
= *entry
;
370 struct isl_union_map_foreach_data
*data
;
371 data
= (struct isl_union_map_foreach_data
*)user
;
373 return data
->fn(isl_map_copy(map
), data
->user
);
376 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
378 return umap
? umap
->table
.n
: 0;
381 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
383 return uset
? uset
->table
.n
: 0;
386 int isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
387 int (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
389 struct isl_union_map_foreach_data data
= { fn
, user
};
394 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
395 &call_on_copy
, &data
);
398 static int copy_map(void **entry
, void *user
)
400 isl_map
*map
= *entry
;
401 isl_map
**map_p
= user
;
403 *map_p
= isl_map_copy(map
);
408 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
415 ctx
= isl_union_map_get_ctx(umap
);
416 if (umap
->table
.n
!= 1)
417 isl_die(ctx
, isl_error_invalid
,
418 "union map needs to contain elements in exactly "
419 "one space", return isl_union_map_free(umap
));
421 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
423 isl_union_map_free(umap
);
428 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
430 return isl_map_from_union_map(uset
);
433 /* Extract the map in "umap" that lives in the given space (ignoring
436 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
437 __isl_take isl_space
*space
)
440 struct isl_hash_table_entry
*entry
;
442 space
= isl_space_drop_dims(space
, isl_dim_param
,
443 0, isl_space_dim(space
, isl_dim_param
));
444 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
448 hash
= isl_space_get_hash(space
);
449 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
452 return isl_map_empty(space
);
453 isl_space_free(space
);
454 return isl_map_copy(entry
->data
);
456 isl_space_free(space
);
460 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
461 __isl_take isl_space
*dim
)
463 return (isl_set
*)isl_union_map_extract_map(uset
, dim
);
466 /* Check if umap contains a map in the given space.
468 __isl_give
int isl_union_map_contains(__isl_keep isl_union_map
*umap
,
469 __isl_keep isl_space
*dim
)
472 struct isl_hash_table_entry
*entry
;
477 hash
= isl_space_get_hash(dim
);
478 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
483 __isl_give
int isl_union_set_contains(__isl_keep isl_union_set
*uset
,
484 __isl_keep isl_space
*dim
)
486 return isl_union_map_contains(uset
, dim
);
489 int isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
490 int (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
492 return isl_union_map_foreach_map(uset
,
493 (int(*)(__isl_take isl_map
*, void*))fn
, user
);
496 struct isl_union_set_foreach_point_data
{
497 int (*fn
)(__isl_take isl_point
*pnt
, void *user
);
501 static int foreach_point(__isl_take isl_set
*set
, void *user
)
503 struct isl_union_set_foreach_point_data
*data
= user
;
506 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
512 int isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
513 int (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
515 struct isl_union_set_foreach_point_data data
= { fn
, user
};
516 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
519 struct isl_union_map_gen_bin_data
{
520 isl_union_map
*umap2
;
524 static int subtract_entry(void **entry
, void *user
)
526 struct isl_union_map_gen_bin_data
*data
= user
;
528 struct isl_hash_table_entry
*entry2
;
529 isl_map
*map
= *entry
;
531 hash
= isl_space_get_hash(map
->dim
);
532 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
533 hash
, &has_dim
, map
->dim
, 0);
534 map
= isl_map_copy(map
);
537 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
539 empty
= isl_map_is_empty(map
);
549 data
->res
= isl_union_map_add_map(data
->res
, map
);
554 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
555 __isl_take isl_union_map
*umap2
, int (*fn
)(void **, void *))
557 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
559 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
560 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
562 if (!umap1
|| !umap2
)
566 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
568 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
572 isl_union_map_free(umap1
);
573 isl_union_map_free(umap2
);
576 isl_union_map_free(umap1
);
577 isl_union_map_free(umap2
);
578 isl_union_map_free(data
.res
);
582 __isl_give isl_union_map
*isl_union_map_subtract(
583 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
585 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
588 __isl_give isl_union_set
*isl_union_set_subtract(
589 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
591 return isl_union_map_subtract(uset1
, uset2
);
594 struct isl_union_map_gen_bin_set_data
{
599 static int intersect_params_entry(void **entry
, void *user
)
601 struct isl_union_map_gen_bin_set_data
*data
= user
;
602 isl_map
*map
= *entry
;
605 map
= isl_map_copy(map
);
606 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
608 empty
= isl_map_is_empty(map
);
614 data
->res
= isl_union_map_add_map(data
->res
, map
);
619 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
620 __isl_take isl_set
*set
, int (*fn
)(void **, void *))
622 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
624 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
625 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
631 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
633 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
637 isl_union_map_free(umap
);
641 isl_union_map_free(umap
);
643 isl_union_map_free(data
.res
);
647 __isl_give isl_union_map
*isl_union_map_intersect_params(
648 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
650 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
653 __isl_give isl_union_set
*isl_union_set_intersect_params(
654 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
656 return isl_union_map_intersect_params(uset
, set
);
659 static __isl_give isl_union_map
*union_map_intersect_params(
660 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
662 return isl_union_map_intersect_params(umap
,
663 isl_set_from_union_set(uset
));
666 static __isl_give isl_union_map
*union_map_gist_params(
667 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
669 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
672 struct isl_union_map_match_bin_data
{
673 isl_union_map
*umap2
;
675 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
678 static int match_bin_entry(void **entry
, void *user
)
680 struct isl_union_map_match_bin_data
*data
= user
;
682 struct isl_hash_table_entry
*entry2
;
683 isl_map
*map
= *entry
;
686 hash
= isl_space_get_hash(map
->dim
);
687 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
688 hash
, &has_dim
, map
->dim
, 0);
692 map
= isl_map_copy(map
);
693 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
695 empty
= isl_map_is_empty(map
);
705 data
->res
= isl_union_map_add_map(data
->res
, map
);
710 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
711 __isl_take isl_union_map
*umap2
,
712 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
714 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
716 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
717 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
719 if (!umap1
|| !umap2
)
723 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
725 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
726 &match_bin_entry
, &data
) < 0)
729 isl_union_map_free(umap1
);
730 isl_union_map_free(umap2
);
733 isl_union_map_free(umap1
);
734 isl_union_map_free(umap2
);
735 isl_union_map_free(data
.res
);
739 __isl_give isl_union_map
*isl_union_map_intersect(
740 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
742 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
745 /* Compute the intersection of the two union_sets.
746 * As a special case, if exactly one of the two union_sets
747 * is a parameter domain, then intersect the parameter domain
748 * of the other one with this set.
750 __isl_give isl_union_set
*isl_union_set_intersect(
751 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
755 p1
= isl_union_set_is_params(uset1
);
756 p2
= isl_union_set_is_params(uset2
);
757 if (p1
< 0 || p2
< 0)
760 return union_map_intersect_params(uset1
, uset2
);
762 return union_map_intersect_params(uset2
, uset1
);
763 return isl_union_map_intersect(uset1
, uset2
);
765 isl_union_set_free(uset1
);
766 isl_union_set_free(uset2
);
770 static int gist_params_entry(void **entry
, void *user
)
772 struct isl_union_map_gen_bin_set_data
*data
= user
;
773 isl_map
*map
= *entry
;
776 map
= isl_map_copy(map
);
777 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
779 empty
= isl_map_is_empty(map
);
785 data
->res
= isl_union_map_add_map(data
->res
, map
);
790 __isl_give isl_union_map
*isl_union_map_gist_params(
791 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
793 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
796 __isl_give isl_union_set
*isl_union_set_gist_params(
797 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
799 return isl_union_map_gist_params(uset
, set
);
802 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
803 __isl_take isl_union_map
*context
)
805 return match_bin_op(umap
, context
, &isl_map_gist
);
808 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
809 __isl_take isl_union_set
*context
)
811 if (isl_union_set_is_params(context
))
812 return union_map_gist_params(uset
, context
);
813 return isl_union_map_gist(uset
, context
);
816 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
817 __isl_take isl_map
*set2
)
819 return isl_set_lex_le_set((isl_set
*)set1
, (isl_set
*)set2
);
822 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
823 __isl_take isl_map
*set2
)
825 return isl_set_lex_lt_set((isl_set
*)set1
, (isl_set
*)set2
);
828 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
829 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
831 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
834 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
835 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
837 return match_bin_op(uset1
, uset2
, &lex_le_set
);
840 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
841 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
843 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
846 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
847 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
849 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
852 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
853 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
855 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
858 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
859 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
861 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
864 static int intersect_domain_entry(void **entry
, void *user
)
866 struct isl_union_map_gen_bin_data
*data
= user
;
868 struct isl_hash_table_entry
*entry2
;
870 isl_map
*map
= *entry
;
873 dim
= isl_map_get_space(map
);
874 dim
= isl_space_domain(dim
);
875 hash
= isl_space_get_hash(dim
);
876 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
877 hash
, &has_dim
, dim
, 0);
882 map
= isl_map_copy(map
);
883 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
885 empty
= isl_map_is_empty(map
);
895 data
->res
= isl_union_map_add_map(data
->res
, map
);
900 /* Intersect the domain of "umap" with "uset".
901 * If "uset" is a parameters domain, then intersect the parameter
902 * domain of "umap" with this set.
904 __isl_give isl_union_map
*isl_union_map_intersect_domain(
905 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
907 if (isl_union_set_is_params(uset
))
908 return union_map_intersect_params(umap
, uset
);
909 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
912 /* Remove the elements of data->umap2 from the domain of *entry
913 * and add the result to data->res.
915 static int subtract_domain_entry(void **entry
, void *user
)
917 struct isl_union_map_gen_bin_data
*data
= user
;
919 struct isl_hash_table_entry
*entry2
;
921 isl_map
*map
= *entry
;
924 dim
= isl_map_get_space(map
);
925 dim
= isl_space_domain(dim
);
926 hash
= isl_space_get_hash(dim
);
927 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
928 hash
, &has_dim
, dim
, 0);
931 map
= isl_map_copy(map
);
934 data
->res
= isl_union_map_add_map(data
->res
, map
);
938 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
940 empty
= isl_map_is_empty(map
);
950 data
->res
= isl_union_map_add_map(data
->res
, map
);
955 /* Remove the elements of "uset" from the domain of "umap".
957 __isl_give isl_union_map
*isl_union_map_subtract_domain(
958 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
960 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
963 /* Remove the elements of data->umap2 from the range of *entry
964 * and add the result to data->res.
966 static int subtract_range_entry(void **entry
, void *user
)
968 struct isl_union_map_gen_bin_data
*data
= user
;
970 struct isl_hash_table_entry
*entry2
;
972 isl_map
*map
= *entry
;
975 space
= isl_map_get_space(map
);
976 space
= isl_space_range(space
);
977 hash
= isl_space_get_hash(space
);
978 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
979 hash
, &has_dim
, space
, 0);
980 isl_space_free(space
);
982 map
= isl_map_copy(map
);
985 data
->res
= isl_union_map_add_map(data
->res
, map
);
989 map
= isl_map_subtract_range(map
, isl_set_copy(entry2
->data
));
991 empty
= isl_map_is_empty(map
);
1001 data
->res
= isl_union_map_add_map(data
->res
, map
);
1006 /* Remove the elements of "uset" from the range of "umap".
1008 __isl_give isl_union_map
*isl_union_map_subtract_range(
1009 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1011 return gen_bin_op(umap
, dom
, &subtract_range_entry
);
1014 static int gist_domain_entry(void **entry
, void *user
)
1016 struct isl_union_map_gen_bin_data
*data
= user
;
1018 struct isl_hash_table_entry
*entry2
;
1020 isl_map
*map
= *entry
;
1023 dim
= isl_map_get_space(map
);
1024 dim
= isl_space_domain(dim
);
1025 hash
= isl_space_get_hash(dim
);
1026 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1027 hash
, &has_dim
, dim
, 0);
1028 isl_space_free(dim
);
1032 map
= isl_map_copy(map
);
1033 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
1035 empty
= isl_map_is_empty(map
);
1041 data
->res
= isl_union_map_add_map(data
->res
, map
);
1046 /* Compute the gist of "umap" with respect to the domain "uset".
1047 * If "uset" is a parameters domain, then compute the gist
1048 * with respect to this parameter domain.
1050 __isl_give isl_union_map
*isl_union_map_gist_domain(
1051 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1053 if (isl_union_set_is_params(uset
))
1054 return union_map_gist_params(umap
, uset
);
1055 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1058 static int gist_range_entry(void **entry
, void *user
)
1060 struct isl_union_map_gen_bin_data
*data
= user
;
1062 struct isl_hash_table_entry
*entry2
;
1064 isl_map
*map
= *entry
;
1067 space
= isl_map_get_space(map
);
1068 space
= isl_space_range(space
);
1069 hash
= isl_space_get_hash(space
);
1070 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1071 hash
, &has_dim
, space
, 0);
1072 isl_space_free(space
);
1076 map
= isl_map_copy(map
);
1077 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1079 empty
= isl_map_is_empty(map
);
1085 data
->res
= isl_union_map_add_map(data
->res
, map
);
1090 /* Compute the gist of "umap" with respect to the range "uset".
1092 __isl_give isl_union_map
*isl_union_map_gist_range(
1093 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1095 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1098 static int intersect_range_entry(void **entry
, void *user
)
1100 struct isl_union_map_gen_bin_data
*data
= user
;
1102 struct isl_hash_table_entry
*entry2
;
1104 isl_map
*map
= *entry
;
1107 dim
= isl_map_get_space(map
);
1108 dim
= isl_space_range(dim
);
1109 hash
= isl_space_get_hash(dim
);
1110 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1111 hash
, &has_dim
, dim
, 0);
1112 isl_space_free(dim
);
1116 map
= isl_map_copy(map
);
1117 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1119 empty
= isl_map_is_empty(map
);
1129 data
->res
= isl_union_map_add_map(data
->res
, map
);
1134 __isl_give isl_union_map
*isl_union_map_intersect_range(
1135 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1137 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1140 struct isl_union_map_bin_data
{
1141 isl_union_map
*umap2
;
1144 int (*fn
)(void **entry
, void *user
);
1147 static int apply_range_entry(void **entry
, void *user
)
1149 struct isl_union_map_bin_data
*data
= user
;
1150 isl_map
*map2
= *entry
;
1153 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1154 map2
->dim
, isl_dim_in
))
1157 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1159 empty
= isl_map_is_empty(map2
);
1169 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1174 static int bin_entry(void **entry
, void *user
)
1176 struct isl_union_map_bin_data
*data
= user
;
1177 isl_map
*map
= *entry
;
1180 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1181 data
->fn
, data
) < 0)
1187 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1188 __isl_take isl_union_map
*umap2
, int (*fn
)(void **entry
, void *user
))
1190 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1192 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1193 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1195 if (!umap1
|| !umap2
)
1199 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1201 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1202 &bin_entry
, &data
) < 0)
1205 isl_union_map_free(umap1
);
1206 isl_union_map_free(umap2
);
1209 isl_union_map_free(umap1
);
1210 isl_union_map_free(umap2
);
1211 isl_union_map_free(data
.res
);
1215 __isl_give isl_union_map
*isl_union_map_apply_range(
1216 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1218 return bin_op(umap1
, umap2
, &apply_range_entry
);
1221 __isl_give isl_union_map
*isl_union_map_apply_domain(
1222 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1224 umap1
= isl_union_map_reverse(umap1
);
1225 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1226 return isl_union_map_reverse(umap1
);
1229 __isl_give isl_union_set
*isl_union_set_apply(
1230 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1232 return isl_union_map_apply_range(uset
, umap
);
1235 static int map_lex_lt_entry(void **entry
, void *user
)
1237 struct isl_union_map_bin_data
*data
= user
;
1238 isl_map
*map2
= *entry
;
1240 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1241 map2
->dim
, isl_dim_out
))
1244 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1246 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1251 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1252 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1254 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1257 static int map_lex_le_entry(void **entry
, void *user
)
1259 struct isl_union_map_bin_data
*data
= user
;
1260 isl_map
*map2
= *entry
;
1262 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1263 map2
->dim
, isl_dim_out
))
1266 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1268 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1273 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1274 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1276 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1279 static int product_entry(void **entry
, void *user
)
1281 struct isl_union_map_bin_data
*data
= user
;
1282 isl_map
*map2
= *entry
;
1284 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1286 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1291 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1292 __isl_take isl_union_map
*umap2
)
1294 return bin_op(umap1
, umap2
, &product_entry
);
1297 static int set_product_entry(void **entry
, void *user
)
1299 struct isl_union_map_bin_data
*data
= user
;
1300 isl_set
*set2
= *entry
;
1302 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1304 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1309 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1310 __isl_take isl_union_set
*uset2
)
1312 return bin_op(uset1
, uset2
, &set_product_entry
);
1315 static int domain_product_entry(void **entry
, void *user
)
1317 struct isl_union_map_bin_data
*data
= user
;
1318 isl_map
*map2
= *entry
;
1320 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1321 map2
->dim
, isl_dim_out
))
1324 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1325 isl_map_copy(map2
));
1327 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1332 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1334 __isl_give isl_union_map
*isl_union_map_domain_product(
1335 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1337 return bin_op(umap1
, umap2
, &domain_product_entry
);
1340 static int range_product_entry(void **entry
, void *user
)
1342 struct isl_union_map_bin_data
*data
= user
;
1343 isl_map
*map2
= *entry
;
1345 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1346 map2
->dim
, isl_dim_in
))
1349 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1350 isl_map_copy(map2
));
1352 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1357 __isl_give isl_union_map
*isl_union_map_range_product(
1358 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1360 return bin_op(umap1
, umap2
, &range_product_entry
);
1363 static int flat_range_product_entry(void **entry
, void *user
)
1365 struct isl_union_map_bin_data
*data
= user
;
1366 isl_map
*map2
= *entry
;
1368 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1369 map2
->dim
, isl_dim_in
))
1372 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1373 isl_map_copy(map2
));
1375 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1380 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1381 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1383 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1386 static __isl_give isl_union_set
*cond_un_op(__isl_take isl_union_map
*umap
,
1387 int (*fn
)(void **, void *))
1394 res
= isl_union_map_alloc(isl_space_copy(umap
->dim
), umap
->table
.n
);
1395 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, &res
) < 0)
1398 isl_union_map_free(umap
);
1401 isl_union_map_free(umap
);
1402 isl_union_set_free(res
);
1406 static int from_range_entry(void **entry
, void *user
)
1408 isl_map
*set
= *entry
;
1409 isl_union_set
**res
= user
;
1411 *res
= isl_union_map_add_map(*res
,
1412 isl_map_from_range(isl_set_copy(set
)));
1417 __isl_give isl_union_map
*isl_union_map_from_range(
1418 __isl_take isl_union_set
*uset
)
1420 return cond_un_op(uset
, &from_range_entry
);
1423 __isl_give isl_union_map
*isl_union_map_from_domain(
1424 __isl_take isl_union_set
*uset
)
1426 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1429 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1430 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1432 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1433 isl_union_map_from_range(range
));
1436 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1437 int (*fn
)(void **, void *))
1439 umap
= isl_union_map_cow(umap
);
1443 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, NULL
) < 0)
1448 isl_union_map_free(umap
);
1452 static int affine_entry(void **entry
, void *user
)
1454 isl_map
**map
= (isl_map
**)entry
;
1456 *map
= isl_map_from_basic_map(isl_map_affine_hull(*map
));
1458 return *map
? 0 : -1;
1461 __isl_give isl_union_map
*isl_union_map_affine_hull(
1462 __isl_take isl_union_map
*umap
)
1464 return un_op(umap
, &affine_entry
);
1467 __isl_give isl_union_set
*isl_union_set_affine_hull(
1468 __isl_take isl_union_set
*uset
)
1470 return isl_union_map_affine_hull(uset
);
1473 static int polyhedral_entry(void **entry
, void *user
)
1475 isl_map
**map
= (isl_map
**)entry
;
1477 *map
= isl_map_from_basic_map(isl_map_polyhedral_hull(*map
));
1479 return *map
? 0 : -1;
1482 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1483 __isl_take isl_union_map
*umap
)
1485 return un_op(umap
, &polyhedral_entry
);
1488 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1489 __isl_take isl_union_set
*uset
)
1491 return isl_union_map_polyhedral_hull(uset
);
1494 static int simple_entry(void **entry
, void *user
)
1496 isl_map
**map
= (isl_map
**)entry
;
1498 *map
= isl_map_from_basic_map(isl_map_simple_hull(*map
));
1500 return *map
? 0 : -1;
1503 __isl_give isl_union_map
*isl_union_map_simple_hull(
1504 __isl_take isl_union_map
*umap
)
1506 return un_op(umap
, &simple_entry
);
1509 __isl_give isl_union_set
*isl_union_set_simple_hull(
1510 __isl_take isl_union_set
*uset
)
1512 return isl_union_map_simple_hull(uset
);
1515 static int inplace_entry(void **entry
, void *user
)
1517 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*);
1518 isl_map
**map
= (isl_map
**)entry
;
1521 fn
= *(__isl_give isl_map
*(**)(__isl_take isl_map
*)) user
;
1522 copy
= fn(isl_map_copy(*map
));
1532 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1533 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1538 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1539 &inplace_entry
, &fn
) < 0)
1544 isl_union_map_free(umap
);
1548 __isl_give isl_union_map
*isl_union_map_coalesce(
1549 __isl_take isl_union_map
*umap
)
1551 return inplace(umap
, &isl_map_coalesce
);
1554 __isl_give isl_union_set
*isl_union_set_coalesce(
1555 __isl_take isl_union_set
*uset
)
1557 return isl_union_map_coalesce(uset
);
1560 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1561 __isl_take isl_union_map
*umap
)
1563 return inplace(umap
, &isl_map_detect_equalities
);
1566 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1567 __isl_take isl_union_set
*uset
)
1569 return isl_union_map_detect_equalities(uset
);
1572 __isl_give isl_union_map
*isl_union_map_compute_divs(
1573 __isl_take isl_union_map
*umap
)
1575 return inplace(umap
, &isl_map_compute_divs
);
1578 __isl_give isl_union_set
*isl_union_set_compute_divs(
1579 __isl_take isl_union_set
*uset
)
1581 return isl_union_map_compute_divs(uset
);
1584 static int lexmin_entry(void **entry
, void *user
)
1586 isl_map
**map
= (isl_map
**)entry
;
1588 *map
= isl_map_lexmin(*map
);
1590 return *map
? 0 : -1;
1593 __isl_give isl_union_map
*isl_union_map_lexmin(
1594 __isl_take isl_union_map
*umap
)
1596 return un_op(umap
, &lexmin_entry
);
1599 __isl_give isl_union_set
*isl_union_set_lexmin(
1600 __isl_take isl_union_set
*uset
)
1602 return isl_union_map_lexmin(uset
);
1605 static int lexmax_entry(void **entry
, void *user
)
1607 isl_map
**map
= (isl_map
**)entry
;
1609 *map
= isl_map_lexmax(*map
);
1611 return *map
? 0 : -1;
1614 __isl_give isl_union_map
*isl_union_map_lexmax(
1615 __isl_take isl_union_map
*umap
)
1617 return un_op(umap
, &lexmax_entry
);
1620 __isl_give isl_union_set
*isl_union_set_lexmax(
1621 __isl_take isl_union_set
*uset
)
1623 return isl_union_map_lexmax(uset
);
1626 static int universe_entry(void **entry
, void *user
)
1628 isl_map
*map
= *entry
;
1629 isl_union_map
**res
= user
;
1631 map
= isl_map_universe(isl_map_get_space(map
));
1632 *res
= isl_union_map_add_map(*res
, map
);
1637 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1639 return cond_un_op(umap
, &universe_entry
);
1642 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1644 return isl_union_map_universe(uset
);
1647 static int reverse_entry(void **entry
, void *user
)
1649 isl_map
*map
= *entry
;
1650 isl_union_map
**res
= user
;
1652 *res
= isl_union_map_add_map(*res
, isl_map_reverse(isl_map_copy(map
)));
1657 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1659 return cond_un_op(umap
, &reverse_entry
);
1662 static int params_entry(void **entry
, void *user
)
1664 isl_map
*map
= *entry
;
1665 isl_union_set
**res
= user
;
1667 *res
= isl_union_set_add_set(*res
, isl_map_params(isl_map_copy(map
)));
1672 /* Compute the parameter domain of the given union map.
1674 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1678 empty
= isl_union_map_is_empty(umap
);
1680 return isl_union_map_free(umap
);
1682 return isl_set_empty(isl_union_map_get_space(umap
));
1683 return isl_set_from_union_set(cond_un_op(umap
, ¶ms_entry
));
1686 /* Compute the parameter domain of the given union set.
1688 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1690 return isl_union_map_params(uset
);
1693 static int domain_entry(void **entry
, void *user
)
1695 isl_map
*map
= *entry
;
1696 isl_union_set
**res
= user
;
1698 *res
= isl_union_set_add_set(*res
, isl_map_domain(isl_map_copy(map
)));
1703 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1705 return cond_un_op(umap
, &domain_entry
);
1708 static int range_entry(void **entry
, void *user
)
1710 isl_map
*map
= *entry
;
1711 isl_union_set
**res
= user
;
1713 *res
= isl_union_set_add_set(*res
, isl_map_range(isl_map_copy(map
)));
1718 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1720 return cond_un_op(umap
, &range_entry
);
1723 static int domain_map_entry(void **entry
, void *user
)
1725 isl_map
*map
= *entry
;
1726 isl_union_set
**res
= user
;
1728 *res
= isl_union_map_add_map(*res
,
1729 isl_map_domain_map(isl_map_copy(map
)));
1734 __isl_give isl_union_map
*isl_union_map_domain_map(
1735 __isl_take isl_union_map
*umap
)
1737 return cond_un_op(umap
, &domain_map_entry
);
1740 static int range_map_entry(void **entry
, void *user
)
1742 isl_map
*map
= *entry
;
1743 isl_union_set
**res
= user
;
1745 *res
= isl_union_map_add_map(*res
,
1746 isl_map_range_map(isl_map_copy(map
)));
1751 __isl_give isl_union_map
*isl_union_map_range_map(
1752 __isl_take isl_union_map
*umap
)
1754 return cond_un_op(umap
, &range_map_entry
);
1757 static int deltas_entry(void **entry
, void *user
)
1759 isl_map
*map
= *entry
;
1760 isl_union_set
**res
= user
;
1762 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1765 *res
= isl_union_set_add_set(*res
, isl_map_deltas(isl_map_copy(map
)));
1770 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
1772 return cond_un_op(umap
, &deltas_entry
);
1775 static int deltas_map_entry(void **entry
, void *user
)
1777 isl_map
*map
= *entry
;
1778 isl_union_map
**res
= user
;
1780 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1783 *res
= isl_union_map_add_map(*res
,
1784 isl_map_deltas_map(isl_map_copy(map
)));
1789 __isl_give isl_union_map
*isl_union_map_deltas_map(
1790 __isl_take isl_union_map
*umap
)
1792 return cond_un_op(umap
, &deltas_map_entry
);
1795 static int identity_entry(void **entry
, void *user
)
1797 isl_set
*set
= *entry
;
1798 isl_union_map
**res
= user
;
1800 *res
= isl_union_map_add_map(*res
, isl_set_identity(isl_set_copy(set
)));
1805 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
1807 return cond_un_op(uset
, &identity_entry
);
1810 static int unwrap_entry(void **entry
, void *user
)
1812 isl_set
*set
= *entry
;
1813 isl_union_set
**res
= user
;
1815 if (!isl_set_is_wrapping(set
))
1818 *res
= isl_union_map_add_map(*res
, isl_set_unwrap(isl_set_copy(set
)));
1823 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
1825 return cond_un_op(uset
, &unwrap_entry
);
1828 static int wrap_entry(void **entry
, void *user
)
1830 isl_map
*map
= *entry
;
1831 isl_union_set
**res
= user
;
1833 *res
= isl_union_set_add_set(*res
, isl_map_wrap(isl_map_copy(map
)));
1838 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
1840 return cond_un_op(umap
, &wrap_entry
);
1843 struct isl_union_map_is_subset_data
{
1844 isl_union_map
*umap2
;
1848 static int is_subset_entry(void **entry
, void *user
)
1850 struct isl_union_map_is_subset_data
*data
= user
;
1852 struct isl_hash_table_entry
*entry2
;
1853 isl_map
*map
= *entry
;
1855 hash
= isl_space_get_hash(map
->dim
);
1856 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1857 hash
, &has_dim
, map
->dim
, 0);
1859 int empty
= isl_map_is_empty(map
);
1864 data
->is_subset
= 0;
1868 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
1869 if (data
->is_subset
< 0 || !data
->is_subset
)
1875 int isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
1876 __isl_keep isl_union_map
*umap2
)
1878 struct isl_union_map_is_subset_data data
= { NULL
, 1 };
1880 umap1
= isl_union_map_copy(umap1
);
1881 umap2
= isl_union_map_copy(umap2
);
1882 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1883 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1885 if (!umap1
|| !umap2
)
1889 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1890 &is_subset_entry
, &data
) < 0 &&
1894 isl_union_map_free(umap1
);
1895 isl_union_map_free(umap2
);
1897 return data
.is_subset
;
1899 isl_union_map_free(umap1
);
1900 isl_union_map_free(umap2
);
1904 int isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
1905 __isl_keep isl_union_set
*uset2
)
1907 return isl_union_map_is_subset(uset1
, uset2
);
1910 int isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
1911 __isl_keep isl_union_map
*umap2
)
1915 if (!umap1
|| !umap2
)
1917 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1920 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1924 int isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
1925 __isl_keep isl_union_set
*uset2
)
1927 return isl_union_map_is_equal(uset1
, uset2
);
1930 int isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
1931 __isl_keep isl_union_map
*umap2
)
1935 if (!umap1
|| !umap2
)
1937 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1940 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1941 if (is_subset
== -1)
1946 int isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
1947 __isl_keep isl_union_set
*uset2
)
1949 return isl_union_map_is_strict_subset(uset1
, uset2
);
1952 static int sample_entry(void **entry
, void *user
)
1954 isl_basic_map
**sample
= (isl_basic_map
**)user
;
1955 isl_map
*map
= *entry
;
1957 *sample
= isl_map_sample(isl_map_copy(map
));
1960 if (!isl_basic_map_plain_is_empty(*sample
))
1965 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
1967 isl_basic_map
*sample
= NULL
;
1972 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1973 &sample_entry
, &sample
) < 0 &&
1978 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
1980 isl_union_map_free(umap
);
1984 isl_union_map_free(umap
);
1988 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
1990 return (isl_basic_set
*)isl_union_map_sample(uset
);
1993 struct isl_forall_data
{
1995 int (*fn
)(__isl_keep isl_map
*map
);
1998 static int forall_entry(void **entry
, void *user
)
2000 struct isl_forall_data
*data
= user
;
2001 isl_map
*map
= *entry
;
2003 data
->res
= data
->fn(map
);
2013 static int union_map_forall(__isl_keep isl_union_map
*umap
,
2014 int (*fn
)(__isl_keep isl_map
*map
))
2016 struct isl_forall_data data
= { 1, fn
};
2021 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2022 &forall_entry
, &data
) < 0 && data
.res
)
2028 struct isl_forall_user_data
{
2030 int (*fn
)(__isl_keep isl_map
*map
, void *user
);
2034 static int forall_user_entry(void **entry
, void *user
)
2036 struct isl_forall_user_data
*data
= user
;
2037 isl_map
*map
= *entry
;
2039 data
->res
= data
->fn(map
, data
->user
);
2049 /* Check if fn(map, user) returns true for all maps "map" in umap.
2051 static int union_map_forall_user(__isl_keep isl_union_map
*umap
,
2052 int (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2054 struct isl_forall_user_data data
= { 1, fn
, user
};
2059 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2060 &forall_user_entry
, &data
) < 0 && data
.res
)
2066 int isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2068 return union_map_forall(umap
, &isl_map_is_empty
);
2071 int isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2073 return isl_union_map_is_empty(uset
);
2076 static int is_subset_of_identity(__isl_keep isl_map
*map
)
2085 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
2088 dim
= isl_map_get_space(map
);
2089 id
= isl_map_identity(dim
);
2091 is_subset
= isl_map_is_subset(map
, id
);
2098 /* Check if the given map is single-valued.
2103 * and check if the result is a subset of the identity mapping.
2105 int isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2107 isl_union_map
*test
;
2110 if (isl_union_map_n_map(umap
) == 1) {
2112 umap
= isl_union_map_copy(umap
);
2113 map
= isl_map_from_union_map(umap
);
2114 sv
= isl_map_is_single_valued(map
);
2119 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2120 test
= isl_union_map_apply_range(test
, isl_union_map_copy(umap
));
2122 sv
= union_map_forall(test
, &is_subset_of_identity
);
2124 isl_union_map_free(test
);
2129 int isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2133 umap
= isl_union_map_copy(umap
);
2134 umap
= isl_union_map_reverse(umap
);
2135 in
= isl_union_map_is_single_valued(umap
);
2136 isl_union_map_free(umap
);
2141 /* Represents a map that has a fixed value (v) for one of its
2143 * The map in this structure is not reference counted, so it
2144 * is only valid while the isl_union_map from which it was
2145 * obtained is still alive.
2147 struct isl_fixed_map
{
2152 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2156 struct isl_fixed_map
*v
;
2158 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2161 for (i
= 0; i
< n
; ++i
)
2162 isl_int_init(v
[i
].v
);
2166 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2172 for (i
= 0; i
< n
; ++i
)
2173 isl_int_clear(v
[i
].v
);
2177 /* Compare the "v" field of two isl_fixed_map structs.
2179 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2181 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2182 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2184 return isl_int_cmp(e1
->v
, e2
->v
);
2187 /* Internal data structure used while checking whether all maps
2188 * in a union_map have a fixed value for a given output dimension.
2189 * v is the list of maps, with the fixed value for the dimension
2190 * n is the number of maps considered so far
2191 * pos is the output dimension under investigation
2193 struct isl_fixed_dim_data
{
2194 struct isl_fixed_map
*v
;
2199 static int fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2201 struct isl_fixed_dim_data
*data
= user
;
2203 data
->v
[data
->n
].map
= map
;
2204 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2205 &data
->v
[data
->n
++].v
);
2208 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2209 int first
, int n_range
);
2211 /* Given a list of the maps, with their fixed values at output dimension "pos",
2212 * check whether the ranges of the maps form an obvious partition.
2214 * We first sort the maps according to their fixed values.
2215 * If all maps have a different value, then we know the ranges form
2217 * Otherwise, we collect the maps with the same fixed value and
2218 * check whether each such collection is obviously injective
2219 * based on later dimensions.
2221 static int separates(struct isl_fixed_map
*v
, int n
,
2222 __isl_take isl_space
*dim
, int pos
, int n_range
)
2229 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2231 for (i
= 0; i
+ 1 < n
; ++i
) {
2233 isl_union_map
*part
;
2236 for (j
= i
+ 1; j
< n
; ++j
)
2237 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2243 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2244 for (k
= i
; k
< j
; ++k
)
2245 part
= isl_union_map_add_map(part
,
2246 isl_map_copy(v
[k
].map
));
2248 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2257 isl_space_free(dim
);
2258 free_isl_fixed_map_array(v
, n
);
2261 isl_space_free(dim
);
2262 free_isl_fixed_map_array(v
, n
);
2266 /* Check whether the maps in umap have obviously distinct ranges.
2267 * In particular, check for an output dimension in the range
2268 * [first,n_range) for which all maps have a fixed value
2269 * and then check if these values, possibly along with fixed values
2270 * at later dimensions, entail distinct ranges.
2272 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2273 int first
, int n_range
)
2277 struct isl_fixed_dim_data data
= { NULL
};
2279 ctx
= isl_union_map_get_ctx(umap
);
2281 n
= isl_union_map_n_map(umap
);
2286 isl_union_map_free(umap
);
2290 if (first
>= n_range
) {
2291 isl_union_map_free(umap
);
2295 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2299 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2305 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2310 dim
= isl_union_map_get_space(umap
);
2311 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2312 isl_union_map_free(umap
);
2316 free_isl_fixed_map_array(data
.v
, n
);
2317 isl_union_map_free(umap
);
2321 free_isl_fixed_map_array(data
.v
, n
);
2322 isl_union_map_free(umap
);
2326 /* Check whether the maps in umap that map to subsets of "ran"
2327 * have obviously distinct ranges.
2329 static int plain_injective_on_range_wrap(__isl_keep isl_set
*ran
, void *user
)
2331 isl_union_map
*umap
= user
;
2333 umap
= isl_union_map_copy(umap
);
2334 umap
= isl_union_map_intersect_range(umap
,
2335 isl_union_set_from_set(isl_set_copy(ran
)));
2336 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2339 /* Check if the given union_map is obviously injective.
2341 * In particular, we first check if all individual maps are obviously
2342 * injective and then check if all the ranges of these maps are
2343 * obviously disjoint.
2345 int isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2348 isl_union_map
*univ
;
2351 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
2357 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
2358 ran
= isl_union_map_range(univ
);
2360 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
2362 isl_union_set_free(ran
);
2367 int isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
2371 sv
= isl_union_map_is_single_valued(umap
);
2375 return isl_union_map_is_injective(umap
);
2378 static int zip_entry(void **entry
, void *user
)
2380 isl_map
*map
= *entry
;
2381 isl_union_map
**res
= user
;
2383 if (!isl_map_can_zip(map
))
2386 *res
= isl_union_map_add_map(*res
, isl_map_zip(isl_map_copy(map
)));
2391 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
2393 return cond_un_op(umap
, &zip_entry
);
2396 static int uncurry_entry(void **entry
, void *user
)
2398 isl_map
*map
= *entry
;
2399 isl_union_map
**res
= user
;
2401 if (!isl_map_can_uncurry(map
))
2404 *res
= isl_union_map_add_map(*res
, isl_map_uncurry(isl_map_copy(map
)));
2409 /* Given a union map, take the maps of the form A -> (B -> C) and
2410 * return the union of the corresponding maps (A -> B) -> C.
2412 __isl_give isl_union_map
*isl_union_map_uncurry(__isl_take isl_union_map
*umap
)
2414 return cond_un_op(umap
, &uncurry_entry
);
2417 static int curry_entry(void **entry
, void *user
)
2419 isl_map
*map
= *entry
;
2420 isl_union_map
**res
= user
;
2422 if (!isl_map_can_curry(map
))
2425 *res
= isl_union_map_add_map(*res
, isl_map_curry(isl_map_copy(map
)));
2430 /* Given a union map, take the maps of the form (A -> B) -> C and
2431 * return the union of the corresponding maps A -> (B -> C).
2433 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
2435 return cond_un_op(umap
, &curry_entry
);
2438 static int lift_entry(void **entry
, void *user
)
2440 isl_set
*set
= *entry
;
2441 isl_union_set
**res
= user
;
2443 *res
= isl_union_set_add_set(*res
, isl_set_lift(isl_set_copy(set
)));
2448 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
2450 return cond_un_op(uset
, &lift_entry
);
2453 static int coefficients_entry(void **entry
, void *user
)
2455 isl_set
*set
= *entry
;
2456 isl_union_set
**res
= user
;
2458 set
= isl_set_copy(set
);
2459 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
2460 *res
= isl_union_set_add_set(*res
, set
);
2465 __isl_give isl_union_set
*isl_union_set_coefficients(
2466 __isl_take isl_union_set
*uset
)
2475 ctx
= isl_union_set_get_ctx(uset
);
2476 dim
= isl_space_set_alloc(ctx
, 0, 0);
2477 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
2478 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2479 &coefficients_entry
, &res
) < 0)
2482 isl_union_set_free(uset
);
2485 isl_union_set_free(uset
);
2486 isl_union_set_free(res
);
2490 static int solutions_entry(void **entry
, void *user
)
2492 isl_set
*set
= *entry
;
2493 isl_union_set
**res
= user
;
2495 set
= isl_set_copy(set
);
2496 set
= isl_set_from_basic_set(isl_set_solutions(set
));
2498 *res
= isl_union_set_from_set(set
);
2500 *res
= isl_union_set_add_set(*res
, set
);
2508 __isl_give isl_union_set
*isl_union_set_solutions(
2509 __isl_take isl_union_set
*uset
)
2511 isl_union_set
*res
= NULL
;
2516 if (uset
->table
.n
== 0) {
2517 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
2518 isl_union_set_free(uset
);
2522 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2523 &solutions_entry
, &res
) < 0)
2526 isl_union_set_free(uset
);
2529 isl_union_set_free(uset
);
2530 isl_union_set_free(res
);
2534 /* Internal data structure for isl_union_map_preimage_domain_multi_aff.
2536 * "ma" is the function under which the preimage should be taken.
2537 * "space" is the space of "ma".
2538 * "res" collects the results.
2540 struct isl_union_map_preimage_domain_data
{
2546 /* Compute the preimage of the domain of *entry under the function
2547 * represented by data->ma, provided the domain space of *entry
2548 * match the target space of data->ma, and add the result to data->res.
2550 static int preimage_domain_entry(void **entry
, void *user
)
2553 isl_map
*map
= *entry
;
2554 struct isl_union_map_preimage_domain_data
*data
= user
;
2557 m
= isl_space_tuple_match(map
->dim
, isl_dim_in
,
2558 data
->space
, isl_dim_out
);
2564 map
= isl_map_copy(map
);
2565 map
= isl_map_preimage_domain_multi_aff(map
,
2566 isl_multi_aff_copy(data
->ma
));
2568 empty
= isl_map_is_empty(map
);
2569 if (empty
< 0 || empty
) {
2571 return empty
< 0 ? -1 : 0;
2574 data
->res
= isl_union_map_add_map(data
->res
, map
);
2579 /* Compute the preimage of the domain of "umap" under the function
2580 * represented by "ma".
2581 * In other words, plug in "ma" in the domain of "umap".
2582 * The result contains maps that live in the same spaces as the maps of "umap"
2583 * with domain space equal to the target space of "ma",
2584 * except that the domain has been replaced by the domain space of "ma".
2586 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_aff(
2587 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
2591 struct isl_union_map_preimage_domain_data data
;
2596 ctx
= isl_union_map_get_ctx(umap
);
2597 space
= isl_union_map_get_space(umap
);
2598 data
.space
= isl_multi_aff_get_space(ma
);
2600 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
2601 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_domain_entry
,
2603 data
.res
= isl_union_map_free(data
.res
);
2605 isl_space_free(data
.space
);
2606 isl_union_map_free(umap
);
2607 isl_multi_aff_free(ma
);
2610 isl_union_map_free(umap
);
2611 isl_multi_aff_free(ma
);