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>
22 /* Is this union set a parameter domain?
24 int isl_union_set_is_params(__isl_keep isl_union_set
*uset
)
31 if (uset
->table
.n
!= 1)
34 set
= isl_set_from_union_set(isl_union_set_copy(uset
));
35 params
= isl_set_is_params(set
);
40 static __isl_give isl_union_map
*isl_union_map_alloc(__isl_take isl_space
*dim
,
45 dim
= isl_space_params(dim
);
49 umap
= isl_calloc_type(dim
->ctx
, isl_union_map
);
55 if (isl_hash_table_init(dim
->ctx
, &umap
->table
, size
) < 0)
56 return isl_union_map_free(umap
);
61 __isl_give isl_union_map
*isl_union_map_empty(__isl_take isl_space
*dim
)
63 return isl_union_map_alloc(dim
, 16);
66 __isl_give isl_union_set
*isl_union_set_empty(__isl_take isl_space
*dim
)
68 return isl_union_map_empty(dim
);
71 isl_ctx
*isl_union_map_get_ctx(__isl_keep isl_union_map
*umap
)
73 return umap
? umap
->dim
->ctx
: NULL
;
76 isl_ctx
*isl_union_set_get_ctx(__isl_keep isl_union_set
*uset
)
78 return uset
? uset
->dim
->ctx
: NULL
;
81 __isl_give isl_space
*isl_union_map_get_space(__isl_keep isl_union_map
*umap
)
85 return isl_space_copy(umap
->dim
);
88 __isl_give isl_space
*isl_union_set_get_space(__isl_keep isl_union_set
*uset
)
90 return isl_union_map_get_space(uset
);
93 static int free_umap_entry(void **entry
, void *user
)
95 isl_map
*map
= *entry
;
100 static int add_map(__isl_take isl_map
*map
, void *user
)
102 isl_union_map
**umap
= (isl_union_map
**)user
;
104 *umap
= isl_union_map_add_map(*umap
, map
);
109 __isl_give isl_union_map
*isl_union_map_dup(__isl_keep isl_union_map
*umap
)
116 dup
= isl_union_map_empty(isl_space_copy(umap
->dim
));
117 if (isl_union_map_foreach_map(umap
, &add_map
, &dup
) < 0)
121 isl_union_map_free(dup
);
125 __isl_give isl_union_map
*isl_union_map_cow(__isl_take isl_union_map
*umap
)
133 return isl_union_map_dup(umap
);
136 struct isl_union_align
{
141 static int align_entry(void **entry
, void *user
)
143 isl_map
*map
= *entry
;
145 struct isl_union_align
*data
= user
;
147 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
148 isl_map_get_space(map
));
150 data
->res
= isl_union_map_add_map(data
->res
,
151 isl_map_realign(isl_map_copy(map
), exp
));
156 /* Align the parameters of umap along those of model.
157 * The result has the parameters of model first, in the same order
158 * as they appear in model, followed by any remaining parameters of
159 * umap that do not appear in model.
161 __isl_give isl_union_map
*isl_union_map_align_params(
162 __isl_take isl_union_map
*umap
, __isl_take isl_space
*model
)
164 struct isl_union_align data
= { NULL
, NULL
};
169 if (isl_space_match(umap
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
170 isl_space_free(model
);
174 model
= isl_space_params(model
);
175 data
.exp
= isl_parameter_alignment_reordering(umap
->dim
, model
);
179 data
.res
= isl_union_map_alloc(isl_space_copy(data
.exp
->dim
),
181 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
182 &align_entry
, &data
) < 0)
185 isl_reordering_free(data
.exp
);
186 isl_union_map_free(umap
);
187 isl_space_free(model
);
190 isl_reordering_free(data
.exp
);
191 isl_union_map_free(umap
);
192 isl_union_map_free(data
.res
);
193 isl_space_free(model
);
197 __isl_give isl_union_set
*isl_union_set_align_params(
198 __isl_take isl_union_set
*uset
, __isl_take isl_space
*model
)
200 return isl_union_map_align_params(uset
, model
);
203 __isl_give isl_union_map
*isl_union_map_union(__isl_take isl_union_map
*umap1
,
204 __isl_take isl_union_map
*umap2
)
206 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
207 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
209 umap1
= isl_union_map_cow(umap1
);
211 if (!umap1
|| !umap2
)
214 if (isl_union_map_foreach_map(umap2
, &add_map
, &umap1
) < 0)
217 isl_union_map_free(umap2
);
221 isl_union_map_free(umap1
);
222 isl_union_map_free(umap2
);
226 __isl_give isl_union_set
*isl_union_set_union(__isl_take isl_union_set
*uset1
,
227 __isl_take isl_union_set
*uset2
)
229 return isl_union_map_union(uset1
, uset2
);
232 __isl_give isl_union_map
*isl_union_map_copy(__isl_keep isl_union_map
*umap
)
241 __isl_give isl_union_set
*isl_union_set_copy(__isl_keep isl_union_set
*uset
)
243 return isl_union_map_copy(uset
);
246 void *isl_union_map_free(__isl_take isl_union_map
*umap
)
254 isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
255 &free_umap_entry
, NULL
);
256 isl_hash_table_clear(&umap
->table
);
257 isl_space_free(umap
->dim
);
262 void *isl_union_set_free(__isl_take isl_union_set
*uset
)
264 return isl_union_map_free(uset
);
267 static int has_dim(const void *entry
, const void *val
)
269 isl_map
*map
= (isl_map
*)entry
;
270 isl_space
*dim
= (isl_space
*)val
;
272 return isl_space_is_equal(map
->dim
, dim
);
275 __isl_give isl_union_map
*isl_union_map_add_map(__isl_take isl_union_map
*umap
,
276 __isl_take isl_map
*map
)
279 struct isl_hash_table_entry
*entry
;
284 if (isl_map_plain_is_empty(map
)) {
289 if (!isl_space_match(map
->dim
, isl_dim_param
, umap
->dim
, isl_dim_param
)) {
290 umap
= isl_union_map_align_params(umap
, isl_map_get_space(map
));
291 map
= isl_map_align_params(map
, isl_union_map_get_space(umap
));
294 umap
= isl_union_map_cow(umap
);
299 hash
= isl_space_get_hash(map
->dim
);
300 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
301 &has_dim
, map
->dim
, 1);
308 entry
->data
= isl_map_union(entry
->data
, isl_map_copy(map
));
317 isl_union_map_free(umap
);
321 __isl_give isl_union_set
*isl_union_set_add_set(__isl_take isl_union_set
*uset
,
322 __isl_take isl_set
*set
)
324 return isl_union_map_add_map(uset
, (isl_map
*)set
);
327 __isl_give isl_union_map
*isl_union_map_from_map(__isl_take isl_map
*map
)
335 dim
= isl_map_get_space(map
);
336 dim
= isl_space_params(dim
);
337 umap
= isl_union_map_empty(dim
);
338 umap
= isl_union_map_add_map(umap
, map
);
343 __isl_give isl_union_set
*isl_union_set_from_set(__isl_take isl_set
*set
)
345 return isl_union_map_from_map((isl_map
*)set
);
348 __isl_give isl_union_map
*isl_union_map_from_basic_map(
349 __isl_take isl_basic_map
*bmap
)
351 return isl_union_map_from_map(isl_map_from_basic_map(bmap
));
354 __isl_give isl_union_set
*isl_union_set_from_basic_set(
355 __isl_take isl_basic_set
*bset
)
357 return isl_union_map_from_basic_map(bset
);
360 struct isl_union_map_foreach_data
362 int (*fn
)(__isl_take isl_map
*map
, void *user
);
366 static int call_on_copy(void **entry
, void *user
)
368 isl_map
*map
= *entry
;
369 struct isl_union_map_foreach_data
*data
;
370 data
= (struct isl_union_map_foreach_data
*)user
;
372 return data
->fn(isl_map_copy(map
), data
->user
);
375 int isl_union_map_n_map(__isl_keep isl_union_map
*umap
)
377 return umap
? umap
->table
.n
: 0;
380 int isl_union_set_n_set(__isl_keep isl_union_set
*uset
)
382 return uset
? uset
->table
.n
: 0;
385 int isl_union_map_foreach_map(__isl_keep isl_union_map
*umap
,
386 int (*fn
)(__isl_take isl_map
*map
, void *user
), void *user
)
388 struct isl_union_map_foreach_data data
= { fn
, user
};
393 return isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
394 &call_on_copy
, &data
);
397 static int copy_map(void **entry
, void *user
)
399 isl_map
*map
= *entry
;
400 isl_map
**map_p
= user
;
402 *map_p
= isl_map_copy(map
);
407 __isl_give isl_map
*isl_map_from_union_map(__isl_take isl_union_map
*umap
)
414 ctx
= isl_union_map_get_ctx(umap
);
415 if (umap
->table
.n
!= 1)
416 isl_die(ctx
, isl_error_invalid
,
417 "union map needs to contain elements in exactly "
418 "one space", return isl_union_map_free(umap
));
420 isl_hash_table_foreach(ctx
, &umap
->table
, ©_map
, &map
);
422 isl_union_map_free(umap
);
427 __isl_give isl_set
*isl_set_from_union_set(__isl_take isl_union_set
*uset
)
429 return isl_map_from_union_map(uset
);
432 /* Extract the map in "umap" that lives in the given space (ignoring
435 __isl_give isl_map
*isl_union_map_extract_map(__isl_keep isl_union_map
*umap
,
436 __isl_take isl_space
*space
)
439 struct isl_hash_table_entry
*entry
;
441 space
= isl_space_drop_dims(space
, isl_dim_param
,
442 0, isl_space_dim(space
, isl_dim_param
));
443 space
= isl_space_align_params(space
, isl_union_map_get_space(umap
));
447 hash
= isl_space_get_hash(space
);
448 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
451 return isl_map_empty(space
);
452 isl_space_free(space
);
453 return isl_map_copy(entry
->data
);
455 isl_space_free(space
);
459 __isl_give isl_set
*isl_union_set_extract_set(__isl_keep isl_union_set
*uset
,
460 __isl_take isl_space
*dim
)
462 return (isl_set
*)isl_union_map_extract_map(uset
, dim
);
465 /* Check if umap contains a map in the given space.
467 __isl_give
int isl_union_map_contains(__isl_keep isl_union_map
*umap
,
468 __isl_keep isl_space
*dim
)
471 struct isl_hash_table_entry
*entry
;
476 hash
= isl_space_get_hash(dim
);
477 entry
= isl_hash_table_find(umap
->dim
->ctx
, &umap
->table
, hash
,
482 __isl_give
int isl_union_set_contains(__isl_keep isl_union_set
*uset
,
483 __isl_keep isl_space
*dim
)
485 return isl_union_map_contains(uset
, dim
);
488 int isl_union_set_foreach_set(__isl_keep isl_union_set
*uset
,
489 int (*fn
)(__isl_take isl_set
*set
, void *user
), void *user
)
491 return isl_union_map_foreach_map(uset
,
492 (int(*)(__isl_take isl_map
*, void*))fn
, user
);
495 struct isl_union_set_foreach_point_data
{
496 int (*fn
)(__isl_take isl_point
*pnt
, void *user
);
500 static int foreach_point(__isl_take isl_set
*set
, void *user
)
502 struct isl_union_set_foreach_point_data
*data
= user
;
505 r
= isl_set_foreach_point(set
, data
->fn
, data
->user
);
511 int isl_union_set_foreach_point(__isl_keep isl_union_set
*uset
,
512 int (*fn
)(__isl_take isl_point
*pnt
, void *user
), void *user
)
514 struct isl_union_set_foreach_point_data data
= { fn
, user
};
515 return isl_union_set_foreach_set(uset
, &foreach_point
, &data
);
518 struct isl_union_map_gen_bin_data
{
519 isl_union_map
*umap2
;
523 static int subtract_entry(void **entry
, void *user
)
525 struct isl_union_map_gen_bin_data
*data
= user
;
527 struct isl_hash_table_entry
*entry2
;
528 isl_map
*map
= *entry
;
530 hash
= isl_space_get_hash(map
->dim
);
531 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
532 hash
, &has_dim
, map
->dim
, 0);
533 map
= isl_map_copy(map
);
536 map
= isl_map_subtract(map
, isl_map_copy(entry2
->data
));
538 empty
= isl_map_is_empty(map
);
548 data
->res
= isl_union_map_add_map(data
->res
, map
);
553 static __isl_give isl_union_map
*gen_bin_op(__isl_take isl_union_map
*umap1
,
554 __isl_take isl_union_map
*umap2
, int (*fn
)(void **, void *))
556 struct isl_union_map_gen_bin_data data
= { NULL
, NULL
};
558 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
559 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
561 if (!umap1
|| !umap2
)
565 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
567 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
571 isl_union_map_free(umap1
);
572 isl_union_map_free(umap2
);
575 isl_union_map_free(umap1
);
576 isl_union_map_free(umap2
);
577 isl_union_map_free(data
.res
);
581 __isl_give isl_union_map
*isl_union_map_subtract(
582 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
584 return gen_bin_op(umap1
, umap2
, &subtract_entry
);
587 __isl_give isl_union_set
*isl_union_set_subtract(
588 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
590 return isl_union_map_subtract(uset1
, uset2
);
593 struct isl_union_map_gen_bin_set_data
{
598 static int intersect_params_entry(void **entry
, void *user
)
600 struct isl_union_map_gen_bin_set_data
*data
= user
;
601 isl_map
*map
= *entry
;
604 map
= isl_map_copy(map
);
605 map
= isl_map_intersect_params(map
, isl_set_copy(data
->set
));
607 empty
= isl_map_is_empty(map
);
613 data
->res
= isl_union_map_add_map(data
->res
, map
);
618 static __isl_give isl_union_map
*gen_bin_set_op(__isl_take isl_union_map
*umap
,
619 __isl_take isl_set
*set
, int (*fn
)(void **, void *))
621 struct isl_union_map_gen_bin_set_data data
= { NULL
, NULL
};
623 umap
= isl_union_map_align_params(umap
, isl_set_get_space(set
));
624 set
= isl_set_align_params(set
, isl_union_map_get_space(umap
));
630 data
.res
= isl_union_map_alloc(isl_space_copy(umap
->dim
),
632 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
636 isl_union_map_free(umap
);
640 isl_union_map_free(umap
);
642 isl_union_map_free(data
.res
);
646 __isl_give isl_union_map
*isl_union_map_intersect_params(
647 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
649 return gen_bin_set_op(umap
, set
, &intersect_params_entry
);
652 __isl_give isl_union_set
*isl_union_set_intersect_params(
653 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
655 return isl_union_map_intersect_params(uset
, set
);
658 static __isl_give isl_union_map
*union_map_intersect_params(
659 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
661 return isl_union_map_intersect_params(umap
,
662 isl_set_from_union_set(uset
));
665 static __isl_give isl_union_map
*union_map_gist_params(
666 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
668 return isl_union_map_gist_params(umap
, isl_set_from_union_set(uset
));
671 struct isl_union_map_match_bin_data
{
672 isl_union_map
*umap2
;
674 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*);
677 static int match_bin_entry(void **entry
, void *user
)
679 struct isl_union_map_match_bin_data
*data
= user
;
681 struct isl_hash_table_entry
*entry2
;
682 isl_map
*map
= *entry
;
685 hash
= isl_space_get_hash(map
->dim
);
686 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
687 hash
, &has_dim
, map
->dim
, 0);
691 map
= isl_map_copy(map
);
692 map
= data
->fn(map
, isl_map_copy(entry2
->data
));
694 empty
= isl_map_is_empty(map
);
704 data
->res
= isl_union_map_add_map(data
->res
, map
);
709 static __isl_give isl_union_map
*match_bin_op(__isl_take isl_union_map
*umap1
,
710 __isl_take isl_union_map
*umap2
,
711 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*, __isl_take isl_map
*))
713 struct isl_union_map_match_bin_data data
= { NULL
, NULL
, fn
};
715 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
716 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
718 if (!umap1
|| !umap2
)
722 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
724 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
725 &match_bin_entry
, &data
) < 0)
728 isl_union_map_free(umap1
);
729 isl_union_map_free(umap2
);
732 isl_union_map_free(umap1
);
733 isl_union_map_free(umap2
);
734 isl_union_map_free(data
.res
);
738 __isl_give isl_union_map
*isl_union_map_intersect(
739 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
741 return match_bin_op(umap1
, umap2
, &isl_map_intersect
);
744 /* Compute the intersection of the two union_sets.
745 * As a special case, if exactly one of the two union_sets
746 * is a parameter domain, then intersect the parameter domain
747 * of the other one with this set.
749 __isl_give isl_union_set
*isl_union_set_intersect(
750 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
754 p1
= isl_union_set_is_params(uset1
);
755 p2
= isl_union_set_is_params(uset2
);
756 if (p1
< 0 || p2
< 0)
759 return union_map_intersect_params(uset1
, uset2
);
761 return union_map_intersect_params(uset2
, uset1
);
762 return isl_union_map_intersect(uset1
, uset2
);
764 isl_union_set_free(uset1
);
765 isl_union_set_free(uset2
);
769 static int gist_params_entry(void **entry
, void *user
)
771 struct isl_union_map_gen_bin_set_data
*data
= user
;
772 isl_map
*map
= *entry
;
775 map
= isl_map_copy(map
);
776 map
= isl_map_gist_params(map
, isl_set_copy(data
->set
));
778 empty
= isl_map_is_empty(map
);
784 data
->res
= isl_union_map_add_map(data
->res
, map
);
789 __isl_give isl_union_map
*isl_union_map_gist_params(
790 __isl_take isl_union_map
*umap
, __isl_take isl_set
*set
)
792 return gen_bin_set_op(umap
, set
, &gist_params_entry
);
795 __isl_give isl_union_set
*isl_union_set_gist_params(
796 __isl_take isl_union_set
*uset
, __isl_take isl_set
*set
)
798 return isl_union_map_gist_params(uset
, set
);
801 __isl_give isl_union_map
*isl_union_map_gist(__isl_take isl_union_map
*umap
,
802 __isl_take isl_union_map
*context
)
804 return match_bin_op(umap
, context
, &isl_map_gist
);
807 __isl_give isl_union_set
*isl_union_set_gist(__isl_take isl_union_set
*uset
,
808 __isl_take isl_union_set
*context
)
810 if (isl_union_set_is_params(context
))
811 return union_map_gist_params(uset
, context
);
812 return isl_union_map_gist(uset
, context
);
815 static __isl_give isl_map
*lex_le_set(__isl_take isl_map
*set1
,
816 __isl_take isl_map
*set2
)
818 return isl_set_lex_le_set((isl_set
*)set1
, (isl_set
*)set2
);
821 static __isl_give isl_map
*lex_lt_set(__isl_take isl_map
*set1
,
822 __isl_take isl_map
*set2
)
824 return isl_set_lex_lt_set((isl_set
*)set1
, (isl_set
*)set2
);
827 __isl_give isl_union_map
*isl_union_set_lex_lt_union_set(
828 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
830 return match_bin_op(uset1
, uset2
, &lex_lt_set
);
833 __isl_give isl_union_map
*isl_union_set_lex_le_union_set(
834 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
836 return match_bin_op(uset1
, uset2
, &lex_le_set
);
839 __isl_give isl_union_map
*isl_union_set_lex_gt_union_set(
840 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
842 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2
, uset1
));
845 __isl_give isl_union_map
*isl_union_set_lex_ge_union_set(
846 __isl_take isl_union_set
*uset1
, __isl_take isl_union_set
*uset2
)
848 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2
, uset1
));
851 __isl_give isl_union_map
*isl_union_map_lex_gt_union_map(
852 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
854 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2
, umap1
));
857 __isl_give isl_union_map
*isl_union_map_lex_ge_union_map(
858 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
860 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2
, umap1
));
863 static int intersect_domain_entry(void **entry
, void *user
)
865 struct isl_union_map_gen_bin_data
*data
= user
;
867 struct isl_hash_table_entry
*entry2
;
869 isl_map
*map
= *entry
;
872 dim
= isl_map_get_space(map
);
873 dim
= isl_space_domain(dim
);
874 hash
= isl_space_get_hash(dim
);
875 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
876 hash
, &has_dim
, dim
, 0);
881 map
= isl_map_copy(map
);
882 map
= isl_map_intersect_domain(map
, isl_set_copy(entry2
->data
));
884 empty
= isl_map_is_empty(map
);
894 data
->res
= isl_union_map_add_map(data
->res
, map
);
899 /* Intersect the domain of "umap" with "uset".
900 * If "uset" is a parameters domain, then intersect the parameter
901 * domain of "umap" with this set.
903 __isl_give isl_union_map
*isl_union_map_intersect_domain(
904 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
906 if (isl_union_set_is_params(uset
))
907 return union_map_intersect_params(umap
, uset
);
908 return gen_bin_op(umap
, uset
, &intersect_domain_entry
);
911 /* Remove the elements of data->umap2 from the domain of *entry
912 * and add the result to data->res.
914 static int subtract_domain_entry(void **entry
, void *user
)
916 struct isl_union_map_gen_bin_data
*data
= user
;
918 struct isl_hash_table_entry
*entry2
;
920 isl_map
*map
= *entry
;
923 dim
= isl_map_get_space(map
);
924 dim
= isl_space_domain(dim
);
925 hash
= isl_space_get_hash(dim
);
926 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
927 hash
, &has_dim
, dim
, 0);
930 map
= isl_map_copy(map
);
933 data
->res
= isl_union_map_add_map(data
->res
, map
);
937 map
= isl_map_subtract_domain(map
, isl_set_copy(entry2
->data
));
939 empty
= isl_map_is_empty(map
);
949 data
->res
= isl_union_map_add_map(data
->res
, map
);
954 /* Remove the elements of "uset" from the domain of "umap".
956 __isl_give isl_union_map
*isl_union_map_subtract_domain(
957 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
959 return gen_bin_op(umap
, dom
, &subtract_domain_entry
);
962 /* Remove the elements of data->umap2 from the range of *entry
963 * and add the result to data->res.
965 static int subtract_range_entry(void **entry
, void *user
)
967 struct isl_union_map_gen_bin_data
*data
= user
;
969 struct isl_hash_table_entry
*entry2
;
971 isl_map
*map
= *entry
;
974 space
= isl_map_get_space(map
);
975 space
= isl_space_range(space
);
976 hash
= isl_space_get_hash(space
);
977 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
978 hash
, &has_dim
, space
, 0);
979 isl_space_free(space
);
981 map
= isl_map_copy(map
);
984 data
->res
= isl_union_map_add_map(data
->res
, map
);
988 map
= isl_map_subtract_range(map
, isl_set_copy(entry2
->data
));
990 empty
= isl_map_is_empty(map
);
1000 data
->res
= isl_union_map_add_map(data
->res
, map
);
1005 /* Remove the elements of "uset" from the range of "umap".
1007 __isl_give isl_union_map
*isl_union_map_subtract_range(
1008 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*dom
)
1010 return gen_bin_op(umap
, dom
, &subtract_range_entry
);
1013 static int gist_domain_entry(void **entry
, void *user
)
1015 struct isl_union_map_gen_bin_data
*data
= user
;
1017 struct isl_hash_table_entry
*entry2
;
1019 isl_map
*map
= *entry
;
1022 dim
= isl_map_get_space(map
);
1023 dim
= isl_space_domain(dim
);
1024 hash
= isl_space_get_hash(dim
);
1025 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1026 hash
, &has_dim
, dim
, 0);
1027 isl_space_free(dim
);
1031 map
= isl_map_copy(map
);
1032 map
= isl_map_gist_domain(map
, isl_set_copy(entry2
->data
));
1034 empty
= isl_map_is_empty(map
);
1040 data
->res
= isl_union_map_add_map(data
->res
, map
);
1045 /* Compute the gist of "umap" with respect to the domain "uset".
1046 * If "uset" is a parameters domain, then compute the gist
1047 * with respect to this parameter domain.
1049 __isl_give isl_union_map
*isl_union_map_gist_domain(
1050 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1052 if (isl_union_set_is_params(uset
))
1053 return union_map_gist_params(umap
, uset
);
1054 return gen_bin_op(umap
, uset
, &gist_domain_entry
);
1057 static int gist_range_entry(void **entry
, void *user
)
1059 struct isl_union_map_gen_bin_data
*data
= user
;
1061 struct isl_hash_table_entry
*entry2
;
1063 isl_map
*map
= *entry
;
1066 space
= isl_map_get_space(map
);
1067 space
= isl_space_range(space
);
1068 hash
= isl_space_get_hash(space
);
1069 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1070 hash
, &has_dim
, space
, 0);
1071 isl_space_free(space
);
1075 map
= isl_map_copy(map
);
1076 map
= isl_map_gist_range(map
, isl_set_copy(entry2
->data
));
1078 empty
= isl_map_is_empty(map
);
1084 data
->res
= isl_union_map_add_map(data
->res
, map
);
1089 /* Compute the gist of "umap" with respect to the range "uset".
1091 __isl_give isl_union_map
*isl_union_map_gist_range(
1092 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1094 return gen_bin_op(umap
, uset
, &gist_range_entry
);
1097 static int intersect_range_entry(void **entry
, void *user
)
1099 struct isl_union_map_gen_bin_data
*data
= user
;
1101 struct isl_hash_table_entry
*entry2
;
1103 isl_map
*map
= *entry
;
1106 dim
= isl_map_get_space(map
);
1107 dim
= isl_space_range(dim
);
1108 hash
= isl_space_get_hash(dim
);
1109 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1110 hash
, &has_dim
, dim
, 0);
1111 isl_space_free(dim
);
1115 map
= isl_map_copy(map
);
1116 map
= isl_map_intersect_range(map
, isl_set_copy(entry2
->data
));
1118 empty
= isl_map_is_empty(map
);
1128 data
->res
= isl_union_map_add_map(data
->res
, map
);
1133 __isl_give isl_union_map
*isl_union_map_intersect_range(
1134 __isl_take isl_union_map
*umap
, __isl_take isl_union_set
*uset
)
1136 return gen_bin_op(umap
, uset
, &intersect_range_entry
);
1139 struct isl_union_map_bin_data
{
1140 isl_union_map
*umap2
;
1143 int (*fn
)(void **entry
, void *user
);
1146 static int apply_range_entry(void **entry
, void *user
)
1148 struct isl_union_map_bin_data
*data
= user
;
1149 isl_map
*map2
= *entry
;
1152 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1153 map2
->dim
, isl_dim_in
))
1156 map2
= isl_map_apply_range(isl_map_copy(data
->map
), isl_map_copy(map2
));
1158 empty
= isl_map_is_empty(map2
);
1168 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1173 static int bin_entry(void **entry
, void *user
)
1175 struct isl_union_map_bin_data
*data
= user
;
1176 isl_map
*map
= *entry
;
1179 if (isl_hash_table_foreach(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1180 data
->fn
, data
) < 0)
1186 static __isl_give isl_union_map
*bin_op(__isl_take isl_union_map
*umap1
,
1187 __isl_take isl_union_map
*umap2
, int (*fn
)(void **entry
, void *user
))
1189 struct isl_union_map_bin_data data
= { NULL
, NULL
, NULL
, fn
};
1191 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1192 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1194 if (!umap1
|| !umap2
)
1198 data
.res
= isl_union_map_alloc(isl_space_copy(umap1
->dim
),
1200 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1201 &bin_entry
, &data
) < 0)
1204 isl_union_map_free(umap1
);
1205 isl_union_map_free(umap2
);
1208 isl_union_map_free(umap1
);
1209 isl_union_map_free(umap2
);
1210 isl_union_map_free(data
.res
);
1214 __isl_give isl_union_map
*isl_union_map_apply_range(
1215 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1217 return bin_op(umap1
, umap2
, &apply_range_entry
);
1220 __isl_give isl_union_map
*isl_union_map_apply_domain(
1221 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1223 umap1
= isl_union_map_reverse(umap1
);
1224 umap1
= isl_union_map_apply_range(umap1
, umap2
);
1225 return isl_union_map_reverse(umap1
);
1228 __isl_give isl_union_set
*isl_union_set_apply(
1229 __isl_take isl_union_set
*uset
, __isl_take isl_union_map
*umap
)
1231 return isl_union_map_apply_range(uset
, umap
);
1234 static int map_lex_lt_entry(void **entry
, void *user
)
1236 struct isl_union_map_bin_data
*data
= user
;
1237 isl_map
*map2
= *entry
;
1239 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1240 map2
->dim
, isl_dim_out
))
1243 map2
= isl_map_lex_lt_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1245 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1250 __isl_give isl_union_map
*isl_union_map_lex_lt_union_map(
1251 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1253 return bin_op(umap1
, umap2
, &map_lex_lt_entry
);
1256 static int map_lex_le_entry(void **entry
, void *user
)
1258 struct isl_union_map_bin_data
*data
= user
;
1259 isl_map
*map2
= *entry
;
1261 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1262 map2
->dim
, isl_dim_out
))
1265 map2
= isl_map_lex_le_map(isl_map_copy(data
->map
), isl_map_copy(map2
));
1267 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1272 __isl_give isl_union_map
*isl_union_map_lex_le_union_map(
1273 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1275 return bin_op(umap1
, umap2
, &map_lex_le_entry
);
1278 static int product_entry(void **entry
, void *user
)
1280 struct isl_union_map_bin_data
*data
= user
;
1281 isl_map
*map2
= *entry
;
1283 map2
= isl_map_product(isl_map_copy(data
->map
), isl_map_copy(map2
));
1285 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1290 __isl_give isl_union_map
*isl_union_map_product(__isl_take isl_union_map
*umap1
,
1291 __isl_take isl_union_map
*umap2
)
1293 return bin_op(umap1
, umap2
, &product_entry
);
1296 static int set_product_entry(void **entry
, void *user
)
1298 struct isl_union_map_bin_data
*data
= user
;
1299 isl_set
*set2
= *entry
;
1301 set2
= isl_set_product(isl_set_copy(data
->map
), isl_set_copy(set2
));
1303 data
->res
= isl_union_set_add_set(data
->res
, set2
);
1308 __isl_give isl_union_set
*isl_union_set_product(__isl_take isl_union_set
*uset1
,
1309 __isl_take isl_union_set
*uset2
)
1311 return bin_op(uset1
, uset2
, &set_product_entry
);
1314 static int domain_product_entry(void **entry
, void *user
)
1316 struct isl_union_map_bin_data
*data
= user
;
1317 isl_map
*map2
= *entry
;
1319 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_out
,
1320 map2
->dim
, isl_dim_out
))
1323 map2
= isl_map_domain_product(isl_map_copy(data
->map
),
1324 isl_map_copy(map2
));
1326 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1331 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1333 __isl_give isl_union_map
*isl_union_map_domain_product(
1334 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1336 return bin_op(umap1
, umap2
, &domain_product_entry
);
1339 static int range_product_entry(void **entry
, void *user
)
1341 struct isl_union_map_bin_data
*data
= user
;
1342 isl_map
*map2
= *entry
;
1344 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1345 map2
->dim
, isl_dim_in
))
1348 map2
= isl_map_range_product(isl_map_copy(data
->map
),
1349 isl_map_copy(map2
));
1351 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1356 __isl_give isl_union_map
*isl_union_map_range_product(
1357 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1359 return bin_op(umap1
, umap2
, &range_product_entry
);
1362 static int flat_range_product_entry(void **entry
, void *user
)
1364 struct isl_union_map_bin_data
*data
= user
;
1365 isl_map
*map2
= *entry
;
1367 if (!isl_space_tuple_match(data
->map
->dim
, isl_dim_in
,
1368 map2
->dim
, isl_dim_in
))
1371 map2
= isl_map_flat_range_product(isl_map_copy(data
->map
),
1372 isl_map_copy(map2
));
1374 data
->res
= isl_union_map_add_map(data
->res
, map2
);
1379 __isl_give isl_union_map
*isl_union_map_flat_range_product(
1380 __isl_take isl_union_map
*umap1
, __isl_take isl_union_map
*umap2
)
1382 return bin_op(umap1
, umap2
, &flat_range_product_entry
);
1385 static __isl_give isl_union_set
*cond_un_op(__isl_take isl_union_map
*umap
,
1386 int (*fn
)(void **, void *))
1393 res
= isl_union_map_alloc(isl_space_copy(umap
->dim
), umap
->table
.n
);
1394 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, &res
) < 0)
1397 isl_union_map_free(umap
);
1400 isl_union_map_free(umap
);
1401 isl_union_set_free(res
);
1405 static int from_range_entry(void **entry
, void *user
)
1407 isl_map
*set
= *entry
;
1408 isl_union_set
**res
= user
;
1410 *res
= isl_union_map_add_map(*res
,
1411 isl_map_from_range(isl_set_copy(set
)));
1416 __isl_give isl_union_map
*isl_union_map_from_range(
1417 __isl_take isl_union_set
*uset
)
1419 return cond_un_op(uset
, &from_range_entry
);
1422 __isl_give isl_union_map
*isl_union_map_from_domain(
1423 __isl_take isl_union_set
*uset
)
1425 return isl_union_map_reverse(isl_union_map_from_range(uset
));
1428 __isl_give isl_union_map
*isl_union_map_from_domain_and_range(
1429 __isl_take isl_union_set
*domain
, __isl_take isl_union_set
*range
)
1431 return isl_union_map_apply_range(isl_union_map_from_domain(domain
),
1432 isl_union_map_from_range(range
));
1435 static __isl_give isl_union_map
*un_op(__isl_take isl_union_map
*umap
,
1436 int (*fn
)(void **, void *))
1438 umap
= isl_union_map_cow(umap
);
1442 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
, fn
, NULL
) < 0)
1447 isl_union_map_free(umap
);
1451 static int affine_entry(void **entry
, void *user
)
1453 isl_map
**map
= (isl_map
**)entry
;
1455 *map
= isl_map_from_basic_map(isl_map_affine_hull(*map
));
1457 return *map
? 0 : -1;
1460 __isl_give isl_union_map
*isl_union_map_affine_hull(
1461 __isl_take isl_union_map
*umap
)
1463 return un_op(umap
, &affine_entry
);
1466 __isl_give isl_union_set
*isl_union_set_affine_hull(
1467 __isl_take isl_union_set
*uset
)
1469 return isl_union_map_affine_hull(uset
);
1472 static int polyhedral_entry(void **entry
, void *user
)
1474 isl_map
**map
= (isl_map
**)entry
;
1476 *map
= isl_map_from_basic_map(isl_map_polyhedral_hull(*map
));
1478 return *map
? 0 : -1;
1481 __isl_give isl_union_map
*isl_union_map_polyhedral_hull(
1482 __isl_take isl_union_map
*umap
)
1484 return un_op(umap
, &polyhedral_entry
);
1487 __isl_give isl_union_set
*isl_union_set_polyhedral_hull(
1488 __isl_take isl_union_set
*uset
)
1490 return isl_union_map_polyhedral_hull(uset
);
1493 static int simple_entry(void **entry
, void *user
)
1495 isl_map
**map
= (isl_map
**)entry
;
1497 *map
= isl_map_from_basic_map(isl_map_simple_hull(*map
));
1499 return *map
? 0 : -1;
1502 __isl_give isl_union_map
*isl_union_map_simple_hull(
1503 __isl_take isl_union_map
*umap
)
1505 return un_op(umap
, &simple_entry
);
1508 __isl_give isl_union_set
*isl_union_set_simple_hull(
1509 __isl_take isl_union_set
*uset
)
1511 return isl_union_map_simple_hull(uset
);
1514 static int inplace_entry(void **entry
, void *user
)
1516 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*);
1517 isl_map
**map
= (isl_map
**)entry
;
1520 fn
= *(__isl_give isl_map
*(**)(__isl_take isl_map
*)) user
;
1521 copy
= fn(isl_map_copy(*map
));
1531 static __isl_give isl_union_map
*inplace(__isl_take isl_union_map
*umap
,
1532 __isl_give isl_map
*(*fn
)(__isl_take isl_map
*))
1537 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1538 &inplace_entry
, &fn
) < 0)
1543 isl_union_map_free(umap
);
1547 __isl_give isl_union_map
*isl_union_map_coalesce(
1548 __isl_take isl_union_map
*umap
)
1550 return inplace(umap
, &isl_map_coalesce
);
1553 __isl_give isl_union_set
*isl_union_set_coalesce(
1554 __isl_take isl_union_set
*uset
)
1556 return isl_union_map_coalesce(uset
);
1559 __isl_give isl_union_map
*isl_union_map_detect_equalities(
1560 __isl_take isl_union_map
*umap
)
1562 return inplace(umap
, &isl_map_detect_equalities
);
1565 __isl_give isl_union_set
*isl_union_set_detect_equalities(
1566 __isl_take isl_union_set
*uset
)
1568 return isl_union_map_detect_equalities(uset
);
1571 __isl_give isl_union_map
*isl_union_map_compute_divs(
1572 __isl_take isl_union_map
*umap
)
1574 return inplace(umap
, &isl_map_compute_divs
);
1577 __isl_give isl_union_set
*isl_union_set_compute_divs(
1578 __isl_take isl_union_set
*uset
)
1580 return isl_union_map_compute_divs(uset
);
1583 static int lexmin_entry(void **entry
, void *user
)
1585 isl_map
**map
= (isl_map
**)entry
;
1587 *map
= isl_map_lexmin(*map
);
1589 return *map
? 0 : -1;
1592 __isl_give isl_union_map
*isl_union_map_lexmin(
1593 __isl_take isl_union_map
*umap
)
1595 return un_op(umap
, &lexmin_entry
);
1598 __isl_give isl_union_set
*isl_union_set_lexmin(
1599 __isl_take isl_union_set
*uset
)
1601 return isl_union_map_lexmin(uset
);
1604 static int lexmax_entry(void **entry
, void *user
)
1606 isl_map
**map
= (isl_map
**)entry
;
1608 *map
= isl_map_lexmax(*map
);
1610 return *map
? 0 : -1;
1613 __isl_give isl_union_map
*isl_union_map_lexmax(
1614 __isl_take isl_union_map
*umap
)
1616 return un_op(umap
, &lexmax_entry
);
1619 __isl_give isl_union_set
*isl_union_set_lexmax(
1620 __isl_take isl_union_set
*uset
)
1622 return isl_union_map_lexmax(uset
);
1625 static int universe_entry(void **entry
, void *user
)
1627 isl_map
*map
= *entry
;
1628 isl_union_map
**res
= user
;
1630 map
= isl_map_universe(isl_map_get_space(map
));
1631 *res
= isl_union_map_add_map(*res
, map
);
1636 __isl_give isl_union_map
*isl_union_map_universe(__isl_take isl_union_map
*umap
)
1638 return cond_un_op(umap
, &universe_entry
);
1641 __isl_give isl_union_set
*isl_union_set_universe(__isl_take isl_union_set
*uset
)
1643 return isl_union_map_universe(uset
);
1646 static int reverse_entry(void **entry
, void *user
)
1648 isl_map
*map
= *entry
;
1649 isl_union_map
**res
= user
;
1651 *res
= isl_union_map_add_map(*res
, isl_map_reverse(isl_map_copy(map
)));
1656 __isl_give isl_union_map
*isl_union_map_reverse(__isl_take isl_union_map
*umap
)
1658 return cond_un_op(umap
, &reverse_entry
);
1661 static int params_entry(void **entry
, void *user
)
1663 isl_map
*map
= *entry
;
1664 isl_union_set
**res
= user
;
1666 *res
= isl_union_set_add_set(*res
, isl_map_params(isl_map_copy(map
)));
1671 /* Compute the parameter domain of the given union map.
1673 __isl_give isl_set
*isl_union_map_params(__isl_take isl_union_map
*umap
)
1677 empty
= isl_union_map_is_empty(umap
);
1679 return isl_union_map_free(umap
);
1682 space
= isl_union_map_get_space(umap
);
1683 isl_union_map_free(umap
);
1684 return isl_set_empty(space
);
1686 return isl_set_from_union_set(cond_un_op(umap
, ¶ms_entry
));
1689 /* Compute the parameter domain of the given union set.
1691 __isl_give isl_set
*isl_union_set_params(__isl_take isl_union_set
*uset
)
1693 return isl_union_map_params(uset
);
1696 static int domain_entry(void **entry
, void *user
)
1698 isl_map
*map
= *entry
;
1699 isl_union_set
**res
= user
;
1701 *res
= isl_union_set_add_set(*res
, isl_map_domain(isl_map_copy(map
)));
1706 __isl_give isl_union_set
*isl_union_map_domain(__isl_take isl_union_map
*umap
)
1708 return cond_un_op(umap
, &domain_entry
);
1711 static int range_entry(void **entry
, void *user
)
1713 isl_map
*map
= *entry
;
1714 isl_union_set
**res
= user
;
1716 *res
= isl_union_set_add_set(*res
, isl_map_range(isl_map_copy(map
)));
1721 __isl_give isl_union_set
*isl_union_map_range(__isl_take isl_union_map
*umap
)
1723 return cond_un_op(umap
, &range_entry
);
1726 static int domain_map_entry(void **entry
, void *user
)
1728 isl_map
*map
= *entry
;
1729 isl_union_set
**res
= user
;
1731 *res
= isl_union_map_add_map(*res
,
1732 isl_map_domain_map(isl_map_copy(map
)));
1737 __isl_give isl_union_map
*isl_union_map_domain_map(
1738 __isl_take isl_union_map
*umap
)
1740 return cond_un_op(umap
, &domain_map_entry
);
1743 static int range_map_entry(void **entry
, void *user
)
1745 isl_map
*map
= *entry
;
1746 isl_union_set
**res
= user
;
1748 *res
= isl_union_map_add_map(*res
,
1749 isl_map_range_map(isl_map_copy(map
)));
1754 __isl_give isl_union_map
*isl_union_map_range_map(
1755 __isl_take isl_union_map
*umap
)
1757 return cond_un_op(umap
, &range_map_entry
);
1760 static int deltas_entry(void **entry
, void *user
)
1762 isl_map
*map
= *entry
;
1763 isl_union_set
**res
= user
;
1765 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1768 *res
= isl_union_set_add_set(*res
, isl_map_deltas(isl_map_copy(map
)));
1773 __isl_give isl_union_set
*isl_union_map_deltas(__isl_take isl_union_map
*umap
)
1775 return cond_un_op(umap
, &deltas_entry
);
1778 static int deltas_map_entry(void **entry
, void *user
)
1780 isl_map
*map
= *entry
;
1781 isl_union_map
**res
= user
;
1783 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
1786 *res
= isl_union_map_add_map(*res
,
1787 isl_map_deltas_map(isl_map_copy(map
)));
1792 __isl_give isl_union_map
*isl_union_map_deltas_map(
1793 __isl_take isl_union_map
*umap
)
1795 return cond_un_op(umap
, &deltas_map_entry
);
1798 static int identity_entry(void **entry
, void *user
)
1800 isl_set
*set
= *entry
;
1801 isl_union_map
**res
= user
;
1803 *res
= isl_union_map_add_map(*res
, isl_set_identity(isl_set_copy(set
)));
1808 __isl_give isl_union_map
*isl_union_set_identity(__isl_take isl_union_set
*uset
)
1810 return cond_un_op(uset
, &identity_entry
);
1813 static int unwrap_entry(void **entry
, void *user
)
1815 isl_set
*set
= *entry
;
1816 isl_union_set
**res
= user
;
1818 if (!isl_set_is_wrapping(set
))
1821 *res
= isl_union_map_add_map(*res
, isl_set_unwrap(isl_set_copy(set
)));
1826 __isl_give isl_union_map
*isl_union_set_unwrap(__isl_take isl_union_set
*uset
)
1828 return cond_un_op(uset
, &unwrap_entry
);
1831 static int wrap_entry(void **entry
, void *user
)
1833 isl_map
*map
= *entry
;
1834 isl_union_set
**res
= user
;
1836 *res
= isl_union_set_add_set(*res
, isl_map_wrap(isl_map_copy(map
)));
1841 __isl_give isl_union_set
*isl_union_map_wrap(__isl_take isl_union_map
*umap
)
1843 return cond_un_op(umap
, &wrap_entry
);
1846 struct isl_union_map_is_subset_data
{
1847 isl_union_map
*umap2
;
1851 static int is_subset_entry(void **entry
, void *user
)
1853 struct isl_union_map_is_subset_data
*data
= user
;
1855 struct isl_hash_table_entry
*entry2
;
1856 isl_map
*map
= *entry
;
1858 hash
= isl_space_get_hash(map
->dim
);
1859 entry2
= isl_hash_table_find(data
->umap2
->dim
->ctx
, &data
->umap2
->table
,
1860 hash
, &has_dim
, map
->dim
, 0);
1862 int empty
= isl_map_is_empty(map
);
1867 data
->is_subset
= 0;
1871 data
->is_subset
= isl_map_is_subset(map
, entry2
->data
);
1872 if (data
->is_subset
< 0 || !data
->is_subset
)
1878 int isl_union_map_is_subset(__isl_keep isl_union_map
*umap1
,
1879 __isl_keep isl_union_map
*umap2
)
1881 struct isl_union_map_is_subset_data data
= { NULL
, 1 };
1883 umap1
= isl_union_map_copy(umap1
);
1884 umap2
= isl_union_map_copy(umap2
);
1885 umap1
= isl_union_map_align_params(umap1
, isl_union_map_get_space(umap2
));
1886 umap2
= isl_union_map_align_params(umap2
, isl_union_map_get_space(umap1
));
1888 if (!umap1
|| !umap2
)
1892 if (isl_hash_table_foreach(umap1
->dim
->ctx
, &umap1
->table
,
1893 &is_subset_entry
, &data
) < 0 &&
1897 isl_union_map_free(umap1
);
1898 isl_union_map_free(umap2
);
1900 return data
.is_subset
;
1902 isl_union_map_free(umap1
);
1903 isl_union_map_free(umap2
);
1907 int isl_union_set_is_subset(__isl_keep isl_union_set
*uset1
,
1908 __isl_keep isl_union_set
*uset2
)
1910 return isl_union_map_is_subset(uset1
, uset2
);
1913 int isl_union_map_is_equal(__isl_keep isl_union_map
*umap1
,
1914 __isl_keep isl_union_map
*umap2
)
1918 if (!umap1
|| !umap2
)
1920 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1923 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1927 int isl_union_set_is_equal(__isl_keep isl_union_set
*uset1
,
1928 __isl_keep isl_union_set
*uset2
)
1930 return isl_union_map_is_equal(uset1
, uset2
);
1933 int isl_union_map_is_strict_subset(__isl_keep isl_union_map
*umap1
,
1934 __isl_keep isl_union_map
*umap2
)
1938 if (!umap1
|| !umap2
)
1940 is_subset
= isl_union_map_is_subset(umap1
, umap2
);
1943 is_subset
= isl_union_map_is_subset(umap2
, umap1
);
1944 if (is_subset
== -1)
1949 int isl_union_set_is_strict_subset(__isl_keep isl_union_set
*uset1
,
1950 __isl_keep isl_union_set
*uset2
)
1952 return isl_union_map_is_strict_subset(uset1
, uset2
);
1955 static int sample_entry(void **entry
, void *user
)
1957 isl_basic_map
**sample
= (isl_basic_map
**)user
;
1958 isl_map
*map
= *entry
;
1960 *sample
= isl_map_sample(isl_map_copy(map
));
1963 if (!isl_basic_map_plain_is_empty(*sample
))
1968 __isl_give isl_basic_map
*isl_union_map_sample(__isl_take isl_union_map
*umap
)
1970 isl_basic_map
*sample
= NULL
;
1975 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
1976 &sample_entry
, &sample
) < 0 &&
1981 sample
= isl_basic_map_empty(isl_union_map_get_space(umap
));
1983 isl_union_map_free(umap
);
1987 isl_union_map_free(umap
);
1991 __isl_give isl_basic_set
*isl_union_set_sample(__isl_take isl_union_set
*uset
)
1993 return (isl_basic_set
*)isl_union_map_sample(uset
);
1996 struct isl_forall_data
{
1998 int (*fn
)(__isl_keep isl_map
*map
);
2001 static int forall_entry(void **entry
, void *user
)
2003 struct isl_forall_data
*data
= user
;
2004 isl_map
*map
= *entry
;
2006 data
->res
= data
->fn(map
);
2016 static int union_map_forall(__isl_keep isl_union_map
*umap
,
2017 int (*fn
)(__isl_keep isl_map
*map
))
2019 struct isl_forall_data data
= { 1, fn
};
2024 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2025 &forall_entry
, &data
) < 0 && data
.res
)
2031 struct isl_forall_user_data
{
2033 int (*fn
)(__isl_keep isl_map
*map
, void *user
);
2037 static int forall_user_entry(void **entry
, void *user
)
2039 struct isl_forall_user_data
*data
= user
;
2040 isl_map
*map
= *entry
;
2042 data
->res
= data
->fn(map
, data
->user
);
2052 /* Check if fn(map, user) returns true for all maps "map" in umap.
2054 static int union_map_forall_user(__isl_keep isl_union_map
*umap
,
2055 int (*fn
)(__isl_keep isl_map
*map
, void *user
), void *user
)
2057 struct isl_forall_user_data data
= { 1, fn
, user
};
2062 if (isl_hash_table_foreach(umap
->dim
->ctx
, &umap
->table
,
2063 &forall_user_entry
, &data
) < 0 && data
.res
)
2069 int isl_union_map_is_empty(__isl_keep isl_union_map
*umap
)
2071 return union_map_forall(umap
, &isl_map_is_empty
);
2074 int isl_union_set_is_empty(__isl_keep isl_union_set
*uset
)
2076 return isl_union_map_is_empty(uset
);
2079 static int is_subset_of_identity(__isl_keep isl_map
*map
)
2088 if (!isl_space_tuple_match(map
->dim
, isl_dim_in
, map
->dim
, isl_dim_out
))
2091 dim
= isl_map_get_space(map
);
2092 id
= isl_map_identity(dim
);
2094 is_subset
= isl_map_is_subset(map
, id
);
2101 /* Check if the given map is single-valued.
2106 * and check if the result is a subset of the identity mapping.
2108 int isl_union_map_is_single_valued(__isl_keep isl_union_map
*umap
)
2110 isl_union_map
*test
;
2113 if (isl_union_map_n_map(umap
) == 1) {
2115 umap
= isl_union_map_copy(umap
);
2116 map
= isl_map_from_union_map(umap
);
2117 sv
= isl_map_is_single_valued(map
);
2122 test
= isl_union_map_reverse(isl_union_map_copy(umap
));
2123 test
= isl_union_map_apply_range(test
, isl_union_map_copy(umap
));
2125 sv
= union_map_forall(test
, &is_subset_of_identity
);
2127 isl_union_map_free(test
);
2132 int isl_union_map_is_injective(__isl_keep isl_union_map
*umap
)
2136 umap
= isl_union_map_copy(umap
);
2137 umap
= isl_union_map_reverse(umap
);
2138 in
= isl_union_map_is_single_valued(umap
);
2139 isl_union_map_free(umap
);
2144 /* Represents a map that has a fixed value (v) for one of its
2146 * The map in this structure is not reference counted, so it
2147 * is only valid while the isl_union_map from which it was
2148 * obtained is still alive.
2150 struct isl_fixed_map
{
2155 static struct isl_fixed_map
*alloc_isl_fixed_map_array(isl_ctx
*ctx
,
2159 struct isl_fixed_map
*v
;
2161 v
= isl_calloc_array(ctx
, struct isl_fixed_map
, n
);
2164 for (i
= 0; i
< n
; ++i
)
2165 isl_int_init(v
[i
].v
);
2169 static void free_isl_fixed_map_array(struct isl_fixed_map
*v
, int n
)
2175 for (i
= 0; i
< n
; ++i
)
2176 isl_int_clear(v
[i
].v
);
2180 /* Compare the "v" field of two isl_fixed_map structs.
2182 static int qsort_fixed_map_cmp(const void *p1
, const void *p2
)
2184 const struct isl_fixed_map
*e1
= (const struct isl_fixed_map
*) p1
;
2185 const struct isl_fixed_map
*e2
= (const struct isl_fixed_map
*) p2
;
2187 return isl_int_cmp(e1
->v
, e2
->v
);
2190 /* Internal data structure used while checking whether all maps
2191 * in a union_map have a fixed value for a given output dimension.
2192 * v is the list of maps, with the fixed value for the dimension
2193 * n is the number of maps considered so far
2194 * pos is the output dimension under investigation
2196 struct isl_fixed_dim_data
{
2197 struct isl_fixed_map
*v
;
2202 static int fixed_at_pos(__isl_keep isl_map
*map
, void *user
)
2204 struct isl_fixed_dim_data
*data
= user
;
2206 data
->v
[data
->n
].map
= map
;
2207 return isl_map_plain_is_fixed(map
, isl_dim_out
, data
->pos
,
2208 &data
->v
[data
->n
++].v
);
2211 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2212 int first
, int n_range
);
2214 /* Given a list of the maps, with their fixed values at output dimension "pos",
2215 * check whether the ranges of the maps form an obvious partition.
2217 * We first sort the maps according to their fixed values.
2218 * If all maps have a different value, then we know the ranges form
2220 * Otherwise, we collect the maps with the same fixed value and
2221 * check whether each such collection is obviously injective
2222 * based on later dimensions.
2224 static int separates(struct isl_fixed_map
*v
, int n
,
2225 __isl_take isl_space
*dim
, int pos
, int n_range
)
2232 qsort(v
, n
, sizeof(*v
), &qsort_fixed_map_cmp
);
2234 for (i
= 0; i
+ 1 < n
; ++i
) {
2236 isl_union_map
*part
;
2239 for (j
= i
+ 1; j
< n
; ++j
)
2240 if (isl_int_ne(v
[i
].v
, v
[j
].v
))
2246 part
= isl_union_map_alloc(isl_space_copy(dim
), j
- i
);
2247 for (k
= i
; k
< j
; ++k
)
2248 part
= isl_union_map_add_map(part
,
2249 isl_map_copy(v
[k
].map
));
2251 injective
= plain_injective_on_range(part
, pos
+ 1, n_range
);
2260 isl_space_free(dim
);
2261 free_isl_fixed_map_array(v
, n
);
2264 isl_space_free(dim
);
2265 free_isl_fixed_map_array(v
, n
);
2269 /* Check whether the maps in umap have obviously distinct ranges.
2270 * In particular, check for an output dimension in the range
2271 * [first,n_range) for which all maps have a fixed value
2272 * and then check if these values, possibly along with fixed values
2273 * at later dimensions, entail distinct ranges.
2275 static int plain_injective_on_range(__isl_take isl_union_map
*umap
,
2276 int first
, int n_range
)
2280 struct isl_fixed_dim_data data
= { NULL
};
2282 ctx
= isl_union_map_get_ctx(umap
);
2284 n
= isl_union_map_n_map(umap
);
2289 isl_union_map_free(umap
);
2293 if (first
>= n_range
) {
2294 isl_union_map_free(umap
);
2298 data
.v
= alloc_isl_fixed_map_array(ctx
, n
);
2302 for (data
.pos
= first
; data
.pos
< n_range
; ++data
.pos
) {
2308 fixed
= union_map_forall_user(umap
, &fixed_at_pos
, &data
);
2313 dim
= isl_union_map_get_space(umap
);
2314 injective
= separates(data
.v
, n
, dim
, data
.pos
, n_range
);
2315 isl_union_map_free(umap
);
2319 free_isl_fixed_map_array(data
.v
, n
);
2320 isl_union_map_free(umap
);
2324 free_isl_fixed_map_array(data
.v
, n
);
2325 isl_union_map_free(umap
);
2329 /* Check whether the maps in umap that map to subsets of "ran"
2330 * have obviously distinct ranges.
2332 static int plain_injective_on_range_wrap(__isl_keep isl_set
*ran
, void *user
)
2334 isl_union_map
*umap
= user
;
2336 umap
= isl_union_map_copy(umap
);
2337 umap
= isl_union_map_intersect_range(umap
,
2338 isl_union_set_from_set(isl_set_copy(ran
)));
2339 return plain_injective_on_range(umap
, 0, isl_set_dim(ran
, isl_dim_set
));
2342 /* Check if the given union_map is obviously injective.
2344 * In particular, we first check if all individual maps are obviously
2345 * injective and then check if all the ranges of these maps are
2346 * obviously disjoint.
2348 int isl_union_map_plain_is_injective(__isl_keep isl_union_map
*umap
)
2351 isl_union_map
*univ
;
2354 in
= union_map_forall(umap
, &isl_map_plain_is_injective
);
2360 univ
= isl_union_map_universe(isl_union_map_copy(umap
));
2361 ran
= isl_union_map_range(univ
);
2363 in
= union_map_forall_user(ran
, &plain_injective_on_range_wrap
, umap
);
2365 isl_union_set_free(ran
);
2370 int isl_union_map_is_bijective(__isl_keep isl_union_map
*umap
)
2374 sv
= isl_union_map_is_single_valued(umap
);
2378 return isl_union_map_is_injective(umap
);
2381 static int zip_entry(void **entry
, void *user
)
2383 isl_map
*map
= *entry
;
2384 isl_union_map
**res
= user
;
2386 if (!isl_map_can_zip(map
))
2389 *res
= isl_union_map_add_map(*res
, isl_map_zip(isl_map_copy(map
)));
2394 __isl_give isl_union_map
*isl_union_map_zip(__isl_take isl_union_map
*umap
)
2396 return cond_un_op(umap
, &zip_entry
);
2399 static int uncurry_entry(void **entry
, void *user
)
2401 isl_map
*map
= *entry
;
2402 isl_union_map
**res
= user
;
2404 if (!isl_map_can_uncurry(map
))
2407 *res
= isl_union_map_add_map(*res
, isl_map_uncurry(isl_map_copy(map
)));
2412 /* Given a union map, take the maps of the form A -> (B -> C) and
2413 * return the union of the corresponding maps (A -> B) -> C.
2415 __isl_give isl_union_map
*isl_union_map_uncurry(__isl_take isl_union_map
*umap
)
2417 return cond_un_op(umap
, &uncurry_entry
);
2420 static int curry_entry(void **entry
, void *user
)
2422 isl_map
*map
= *entry
;
2423 isl_union_map
**res
= user
;
2425 if (!isl_map_can_curry(map
))
2428 *res
= isl_union_map_add_map(*res
, isl_map_curry(isl_map_copy(map
)));
2433 /* Given a union map, take the maps of the form (A -> B) -> C and
2434 * return the union of the corresponding maps A -> (B -> C).
2436 __isl_give isl_union_map
*isl_union_map_curry(__isl_take isl_union_map
*umap
)
2438 return cond_un_op(umap
, &curry_entry
);
2441 static int lift_entry(void **entry
, void *user
)
2443 isl_set
*set
= *entry
;
2444 isl_union_set
**res
= user
;
2446 *res
= isl_union_set_add_set(*res
, isl_set_lift(isl_set_copy(set
)));
2451 __isl_give isl_union_set
*isl_union_set_lift(__isl_take isl_union_set
*uset
)
2453 return cond_un_op(uset
, &lift_entry
);
2456 static int coefficients_entry(void **entry
, void *user
)
2458 isl_set
*set
= *entry
;
2459 isl_union_set
**res
= user
;
2461 set
= isl_set_copy(set
);
2462 set
= isl_set_from_basic_set(isl_set_coefficients(set
));
2463 *res
= isl_union_set_add_set(*res
, set
);
2468 __isl_give isl_union_set
*isl_union_set_coefficients(
2469 __isl_take isl_union_set
*uset
)
2478 ctx
= isl_union_set_get_ctx(uset
);
2479 dim
= isl_space_set_alloc(ctx
, 0, 0);
2480 res
= isl_union_map_alloc(dim
, uset
->table
.n
);
2481 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2482 &coefficients_entry
, &res
) < 0)
2485 isl_union_set_free(uset
);
2488 isl_union_set_free(uset
);
2489 isl_union_set_free(res
);
2493 static int solutions_entry(void **entry
, void *user
)
2495 isl_set
*set
= *entry
;
2496 isl_union_set
**res
= user
;
2498 set
= isl_set_copy(set
);
2499 set
= isl_set_from_basic_set(isl_set_solutions(set
));
2501 *res
= isl_union_set_from_set(set
);
2503 *res
= isl_union_set_add_set(*res
, set
);
2511 __isl_give isl_union_set
*isl_union_set_solutions(
2512 __isl_take isl_union_set
*uset
)
2514 isl_union_set
*res
= NULL
;
2519 if (uset
->table
.n
== 0) {
2520 res
= isl_union_set_empty(isl_union_set_get_space(uset
));
2521 isl_union_set_free(uset
);
2525 if (isl_hash_table_foreach(uset
->dim
->ctx
, &uset
->table
,
2526 &solutions_entry
, &res
) < 0)
2529 isl_union_set_free(uset
);
2532 isl_union_set_free(uset
);
2533 isl_union_set_free(res
);
2537 /* Internal data structure for isl_union_map_preimage_domain_multi_aff.
2539 * "ma" is the function under which the preimage should be taken.
2540 * "space" is the space of "ma".
2541 * "res" collects the results.
2543 struct isl_union_map_preimage_domain_data
{
2549 /* Compute the preimage of the domain of *entry under the function
2550 * represented by data->ma, provided the domain space of *entry
2551 * match the target space of data->ma, and add the result to data->res.
2553 static int preimage_domain_entry(void **entry
, void *user
)
2556 isl_map
*map
= *entry
;
2557 struct isl_union_map_preimage_domain_data
*data
= user
;
2560 m
= isl_space_tuple_match(map
->dim
, isl_dim_in
,
2561 data
->space
, isl_dim_out
);
2567 map
= isl_map_copy(map
);
2568 map
= isl_map_preimage_domain_multi_aff(map
,
2569 isl_multi_aff_copy(data
->ma
));
2571 empty
= isl_map_is_empty(map
);
2572 if (empty
< 0 || empty
) {
2574 return empty
< 0 ? -1 : 0;
2577 data
->res
= isl_union_map_add_map(data
->res
, map
);
2582 /* Compute the preimage of the domain of "umap" under the function
2583 * represented by "ma".
2584 * In other words, plug in "ma" in the domain of "umap".
2585 * The result contains maps that live in the same spaces as the maps of "umap"
2586 * with domain space equal to the target space of "ma",
2587 * except that the domain has been replaced by the domain space of "ma".
2589 __isl_give isl_union_map
*isl_union_map_preimage_domain_multi_aff(
2590 __isl_take isl_union_map
*umap
, __isl_take isl_multi_aff
*ma
)
2594 struct isl_union_map_preimage_domain_data data
;
2599 ctx
= isl_union_map_get_ctx(umap
);
2600 space
= isl_union_map_get_space(umap
);
2601 data
.space
= isl_multi_aff_get_space(ma
);
2603 data
.res
= isl_union_map_alloc(space
, umap
->table
.n
);
2604 if (isl_hash_table_foreach(ctx
, &umap
->table
, &preimage_domain_entry
,
2606 data
.res
= isl_union_map_free(data
.res
);
2608 isl_space_free(data
.space
);
2609 isl_union_map_free(umap
);
2610 isl_multi_aff_free(ma
);
2613 isl_union_map_free(umap
);
2614 isl_multi_aff_free(ma
);