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>
17 #include <isl_space_private.h>
18 #include <isl_union_map_private.h>
19 #include <isl/union_set.h>
21 /* Is this union set a parameter domain?
23 int isl_union_set_is_params(__isl_keep isl_union_set *uset)
30 if (uset->table.n != 1)
33 set = isl_set_from_union_set(isl_union_set_copy(uset));
34 params = isl_set_is_params(set);
39 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
47 umap = isl_calloc_type(dim->ctx, isl_union_map);
53 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
54 return isl_union_map_free(umap);
59 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
61 return isl_union_map_alloc(dim, 16);
64 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
66 return isl_union_map_empty(dim);
69 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
71 return umap ? umap->dim->ctx : NULL;
74 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
76 return uset ? uset->dim->ctx : NULL;
79 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
83 return isl_space_copy(umap->dim);
86 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
88 return isl_union_map_get_space(uset);
91 static int free_umap_entry(void **entry, void *user)
93 isl_map *map = *entry;
98 static int add_map(__isl_take isl_map *map, void *user)
100 isl_union_map **umap = (isl_union_map **)user;
102 *umap = isl_union_map_add_map(*umap, map);
107 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
114 dup = isl_union_map_empty(isl_space_copy(umap->dim));
115 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
119 isl_union_map_free(dup);
123 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
131 return isl_union_map_dup(umap);
134 struct isl_union_align {
139 static int align_entry(void **entry, void *user)
141 isl_map *map = *entry;
143 struct isl_union_align *data = user;
145 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
146 isl_map_get_space(map));
148 data->res = isl_union_map_add_map(data->res,
149 isl_map_realign(isl_map_copy(map), exp));
154 /* Align the parameters of umap along those of model.
155 * The result has the parameters of model first, in the same order
156 * as they appear in model, followed by any remaining parameters of
157 * umap that do not appear in model.
159 __isl_give isl_union_map *isl_union_map_align_params(
160 __isl_take isl_union_map *umap, __isl_take isl_space *model)
162 struct isl_union_align data = { NULL, NULL };
167 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
168 isl_space_free(model);
172 model = isl_space_params(model);
173 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
177 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
179 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
180 &align_entry, &data) < 0)
183 isl_reordering_free(data.exp);
184 isl_union_map_free(umap);
185 isl_space_free(model);
188 isl_reordering_free(data.exp);
189 isl_union_map_free(umap);
190 isl_union_map_free(data.res);
191 isl_space_free(model);
195 __isl_give isl_union_set *isl_union_set_align_params(
196 __isl_take isl_union_set *uset, __isl_take isl_space *model)
198 return isl_union_map_align_params(uset, model);
201 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
202 __isl_take isl_union_map *umap2)
204 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
205 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
207 umap1 = isl_union_map_cow(umap1);
209 if (!umap1 || !umap2)
212 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
215 isl_union_map_free(umap2);
219 isl_union_map_free(umap1);
220 isl_union_map_free(umap2);
224 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
225 __isl_take isl_union_set *uset2)
227 return isl_union_map_union(uset1, uset2);
230 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
239 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
241 return isl_union_map_copy(uset);
244 void *isl_union_map_free(__isl_take isl_union_map *umap)
252 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
253 &free_umap_entry, NULL);
254 isl_hash_table_clear(&umap->table);
255 isl_space_free(umap->dim);
260 void *isl_union_set_free(__isl_take isl_union_set *uset)
262 return isl_union_map_free(uset);
265 static int has_dim(const void *entry, const void *val)
267 isl_map *map = (isl_map *)entry;
268 isl_space *dim = (isl_space *)val;
270 return isl_space_is_equal(map->dim, dim);
273 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
274 __isl_take isl_map *map)
277 struct isl_hash_table_entry *entry;
282 if (isl_map_plain_is_empty(map)) {
287 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
288 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
289 map = isl_map_align_params(map, isl_union_map_get_space(umap));
292 umap = isl_union_map_cow(umap);
297 hash = isl_space_get_hash(map->dim);
298 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
299 &has_dim, map->dim, 1);
306 entry->data = isl_map_union(entry->data, isl_map_copy(map));
315 isl_union_map_free(umap);
319 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
320 __isl_take isl_set *set)
322 return isl_union_map_add_map(uset, (isl_map *)set);
325 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
333 dim = isl_map_get_space(map);
334 dim = isl_space_params(dim);
335 umap = isl_union_map_empty(dim);
336 umap = isl_union_map_add_map(umap, map);
341 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
343 return isl_union_map_from_map((isl_map *)set);
346 __isl_give isl_union_map *isl_union_map_from_basic_map(
347 __isl_take isl_basic_map *bmap)
349 return isl_union_map_from_map(isl_map_from_basic_map(bmap));
352 __isl_give isl_union_set *isl_union_set_from_basic_set(
353 __isl_take isl_basic_set *bset)
355 return isl_union_map_from_basic_map(bset);
358 struct isl_union_map_foreach_data
360 int (*fn)(__isl_take isl_map *map, void *user);
364 static int call_on_copy(void **entry, void *user)
366 isl_map *map = *entry;
367 struct isl_union_map_foreach_data *data;
368 data = (struct isl_union_map_foreach_data *)user;
370 return data->fn(isl_map_copy(map), data->user);
373 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
375 return umap ? umap->table.n : 0;
378 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
380 return uset ? uset->table.n : 0;
383 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
384 int (*fn)(__isl_take isl_map *map, void *user), void *user)
386 struct isl_union_map_foreach_data data = { fn, user };
391 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
392 &call_on_copy, &data);
395 static int copy_map(void **entry, void *user)
397 isl_map *map = *entry;
398 isl_map **map_p = user;
400 *map_p = isl_map_copy(map);
405 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
412 ctx = isl_union_map_get_ctx(umap);
413 if (umap->table.n != 1)
414 isl_die(ctx, isl_error_invalid,
415 "union map needs to contain elements in exactly "
416 "one space", return isl_union_map_free(umap));
418 isl_hash_table_foreach(ctx, &umap->table, ©_map, &map);
420 isl_union_map_free(umap);
425 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
427 return isl_map_from_union_map(uset);
430 /* Extract the map in "umap" that lives in the given space (ignoring
433 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
434 __isl_take isl_space *space)
437 struct isl_hash_table_entry *entry;
439 space = isl_space_drop_dims(space, isl_dim_param,
440 0, isl_space_dim(space, isl_dim_param));
441 space = isl_space_align_params(space, isl_union_map_get_space(umap));
445 hash = isl_space_get_hash(space);
446 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
449 return isl_map_empty(space);
450 isl_space_free(space);
451 return isl_map_copy(entry->data);
453 isl_space_free(space);
457 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
458 __isl_take isl_space *dim)
460 return (isl_set *)isl_union_map_extract_map(uset, dim);
463 /* Check if umap contains a map in the given space.
465 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
466 __isl_keep isl_space *dim)
469 struct isl_hash_table_entry *entry;
474 hash = isl_space_get_hash(dim);
475 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
480 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
481 __isl_keep isl_space *dim)
483 return isl_union_map_contains(uset, dim);
486 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
487 int (*fn)(__isl_take isl_set *set, void *user), void *user)
489 return isl_union_map_foreach_map(uset,
490 (int(*)(__isl_take isl_map *, void*))fn, user);
493 struct isl_union_set_foreach_point_data {
494 int (*fn)(__isl_take isl_point *pnt, void *user);
498 static int foreach_point(__isl_take isl_set *set, void *user)
500 struct isl_union_set_foreach_point_data *data = user;
503 r = isl_set_foreach_point(set, data->fn, data->user);
509 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
510 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
512 struct isl_union_set_foreach_point_data data = { fn, user };
513 return isl_union_set_foreach_set(uset, &foreach_point, &data);
516 struct isl_union_map_gen_bin_data {
517 isl_union_map *umap2;
521 static int subtract_entry(void **entry, void *user)
523 struct isl_union_map_gen_bin_data *data = user;
525 struct isl_hash_table_entry *entry2;
526 isl_map *map = *entry;
528 hash = isl_space_get_hash(map->dim);
529 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
530 hash, &has_dim, map->dim, 0);
531 map = isl_map_copy(map);
534 map = isl_map_subtract(map, isl_map_copy(entry2->data));
536 empty = isl_map_is_empty(map);
546 data->res = isl_union_map_add_map(data->res, map);
551 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
552 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
554 struct isl_union_map_gen_bin_data data = { NULL, NULL };
556 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
557 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
559 if (!umap1 || !umap2)
563 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
565 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
569 isl_union_map_free(umap1);
570 isl_union_map_free(umap2);
573 isl_union_map_free(umap1);
574 isl_union_map_free(umap2);
575 isl_union_map_free(data.res);
579 __isl_give isl_union_map *isl_union_map_subtract(
580 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
582 return gen_bin_op(umap1, umap2, &subtract_entry);
585 __isl_give isl_union_set *isl_union_set_subtract(
586 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
588 return isl_union_map_subtract(uset1, uset2);
591 struct isl_union_map_gen_bin_set_data {
596 static int intersect_params_entry(void **entry, void *user)
598 struct isl_union_map_gen_bin_set_data *data = user;
599 isl_map *map = *entry;
602 map = isl_map_copy(map);
603 map = isl_map_intersect_params(map, isl_set_copy(data->set));
605 empty = isl_map_is_empty(map);
611 data->res = isl_union_map_add_map(data->res, map);
616 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
617 __isl_take isl_set *set, int (*fn)(void **, void *))
619 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
621 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
622 set = isl_set_align_params(set, isl_union_map_get_space(umap));
628 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
630 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
634 isl_union_map_free(umap);
638 isl_union_map_free(umap);
640 isl_union_map_free(data.res);
644 __isl_give isl_union_map *isl_union_map_intersect_params(
645 __isl_take isl_union_map *umap, __isl_take isl_set *set)
647 return gen_bin_set_op(umap, set, &intersect_params_entry);
650 __isl_give isl_union_set *isl_union_set_intersect_params(
651 __isl_take isl_union_set *uset, __isl_take isl_set *set)
653 return isl_union_map_intersect_params(uset, set);
656 static __isl_give isl_union_map *union_map_intersect_params(
657 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
659 return isl_union_map_intersect_params(umap,
660 isl_set_from_union_set(uset));
663 static __isl_give isl_union_map *union_map_gist_params(
664 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
666 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
669 struct isl_union_map_match_bin_data {
670 isl_union_map *umap2;
672 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
675 static int match_bin_entry(void **entry, void *user)
677 struct isl_union_map_match_bin_data *data = user;
679 struct isl_hash_table_entry *entry2;
680 isl_map *map = *entry;
683 hash = isl_space_get_hash(map->dim);
684 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
685 hash, &has_dim, map->dim, 0);
689 map = isl_map_copy(map);
690 map = data->fn(map, isl_map_copy(entry2->data));
692 empty = isl_map_is_empty(map);
702 data->res = isl_union_map_add_map(data->res, map);
707 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
708 __isl_take isl_union_map *umap2,
709 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
711 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
713 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
714 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
716 if (!umap1 || !umap2)
720 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
722 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
723 &match_bin_entry, &data) < 0)
726 isl_union_map_free(umap1);
727 isl_union_map_free(umap2);
730 isl_union_map_free(umap1);
731 isl_union_map_free(umap2);
732 isl_union_map_free(data.res);
736 __isl_give isl_union_map *isl_union_map_intersect(
737 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
739 return match_bin_op(umap1, umap2, &isl_map_intersect);
742 /* Compute the intersection of the two union_sets.
743 * As a special case, if exactly one of the two union_sets
744 * is a parameter domain, then intersect the parameter domain
745 * of the other one with this set.
747 __isl_give isl_union_set *isl_union_set_intersect(
748 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
752 p1 = isl_union_set_is_params(uset1);
753 p2 = isl_union_set_is_params(uset2);
754 if (p1 < 0 || p2 < 0)
757 return union_map_intersect_params(uset1, uset2);
759 return union_map_intersect_params(uset2, uset1);
760 return isl_union_map_intersect(uset1, uset2);
762 isl_union_set_free(uset1);
763 isl_union_set_free(uset2);
767 static int gist_params_entry(void **entry, void *user)
769 struct isl_union_map_gen_bin_set_data *data = user;
770 isl_map *map = *entry;
773 map = isl_map_copy(map);
774 map = isl_map_gist_params(map, isl_set_copy(data->set));
776 empty = isl_map_is_empty(map);
782 data->res = isl_union_map_add_map(data->res, map);
787 __isl_give isl_union_map *isl_union_map_gist_params(
788 __isl_take isl_union_map *umap, __isl_take isl_set *set)
790 return gen_bin_set_op(umap, set, &gist_params_entry);
793 __isl_give isl_union_set *isl_union_set_gist_params(
794 __isl_take isl_union_set *uset, __isl_take isl_set *set)
796 return isl_union_map_gist_params(uset, set);
799 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
800 __isl_take isl_union_map *context)
802 return match_bin_op(umap, context, &isl_map_gist);
805 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
806 __isl_take isl_union_set *context)
808 if (isl_union_set_is_params(context))
809 return union_map_gist_params(uset, context);
810 return isl_union_map_gist(uset, context);
813 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
814 __isl_take isl_map *set2)
816 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
819 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
820 __isl_take isl_map *set2)
822 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
825 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
826 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
828 return match_bin_op(uset1, uset2, &lex_lt_set);
831 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
832 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
834 return match_bin_op(uset1, uset2, &lex_le_set);
837 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
838 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
840 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
843 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
844 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
846 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
849 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
850 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
852 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
855 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
856 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
858 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
861 static int intersect_domain_entry(void **entry, void *user)
863 struct isl_union_map_gen_bin_data *data = user;
865 struct isl_hash_table_entry *entry2;
867 isl_map *map = *entry;
870 dim = isl_map_get_space(map);
871 dim = isl_space_domain(dim);
872 hash = isl_space_get_hash(dim);
873 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
874 hash, &has_dim, dim, 0);
879 map = isl_map_copy(map);
880 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
882 empty = isl_map_is_empty(map);
892 data->res = isl_union_map_add_map(data->res, map);
897 /* Intersect the domain of "umap" with "uset".
898 * If "uset" is a parameters domain, then intersect the parameter
899 * domain of "umap" with this set.
901 __isl_give isl_union_map *isl_union_map_intersect_domain(
902 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
904 if (isl_union_set_is_params(uset))
905 return union_map_intersect_params(umap, uset);
906 return gen_bin_op(umap, uset, &intersect_domain_entry);
909 /* Remove the elements of data->umap2 from the domain of *entry
910 * and add the result to data->res.
912 static int subtract_domain_entry(void **entry, void *user)
914 struct isl_union_map_gen_bin_data *data = user;
916 struct isl_hash_table_entry *entry2;
918 isl_map *map = *entry;
921 dim = isl_map_get_space(map);
922 dim = isl_space_domain(dim);
923 hash = isl_space_get_hash(dim);
924 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
925 hash, &has_dim, dim, 0);
928 map = isl_map_copy(map);
931 data->res = isl_union_map_add_map(data->res, map);
935 map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
937 empty = isl_map_is_empty(map);
947 data->res = isl_union_map_add_map(data->res, map);
952 /* Remove the elements of "uset" from the domain of "umap".
954 __isl_give isl_union_map *isl_union_map_subtract_domain(
955 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
957 return gen_bin_op(umap, dom, &subtract_domain_entry);
960 /* Remove the elements of data->umap2 from the range of *entry
961 * and add the result to data->res.
963 static int subtract_range_entry(void **entry, void *user)
965 struct isl_union_map_gen_bin_data *data = user;
967 struct isl_hash_table_entry *entry2;
969 isl_map *map = *entry;
972 space = isl_map_get_space(map);
973 space = isl_space_range(space);
974 hash = isl_space_get_hash(space);
975 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
976 hash, &has_dim, space, 0);
977 isl_space_free(space);
979 map = isl_map_copy(map);
982 data->res = isl_union_map_add_map(data->res, map);
986 map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
988 empty = isl_map_is_empty(map);
998 data->res = isl_union_map_add_map(data->res, map);
1003 /* Remove the elements of "uset" from the range of "umap".
1005 __isl_give isl_union_map *isl_union_map_subtract_range(
1006 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1008 return gen_bin_op(umap, dom, &subtract_range_entry);
1011 static int gist_domain_entry(void **entry, void *user)
1013 struct isl_union_map_gen_bin_data *data = user;
1015 struct isl_hash_table_entry *entry2;
1017 isl_map *map = *entry;
1020 dim = isl_map_get_space(map);
1021 dim = isl_space_domain(dim);
1022 hash = isl_space_get_hash(dim);
1023 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1024 hash, &has_dim, dim, 0);
1025 isl_space_free(dim);
1029 map = isl_map_copy(map);
1030 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1032 empty = isl_map_is_empty(map);
1038 data->res = isl_union_map_add_map(data->res, map);
1043 /* Compute the gist of "umap" with respect to the domain "uset".
1044 * If "uset" is a parameters domain, then compute the gist
1045 * with respect to this parameter domain.
1047 __isl_give isl_union_map *isl_union_map_gist_domain(
1048 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1050 if (isl_union_set_is_params(uset))
1051 return union_map_gist_params(umap, uset);
1052 return gen_bin_op(umap, uset, &gist_domain_entry);
1055 static int gist_range_entry(void **entry, void *user)
1057 struct isl_union_map_gen_bin_data *data = user;
1059 struct isl_hash_table_entry *entry2;
1061 isl_map *map = *entry;
1064 space = isl_map_get_space(map);
1065 space = isl_space_range(space);
1066 hash = isl_space_get_hash(space);
1067 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1068 hash, &has_dim, space, 0);
1069 isl_space_free(space);
1073 map = isl_map_copy(map);
1074 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1076 empty = isl_map_is_empty(map);
1082 data->res = isl_union_map_add_map(data->res, map);
1087 /* Compute the gist of "umap" with respect to the range "uset".
1089 __isl_give isl_union_map *isl_union_map_gist_range(
1090 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1092 return gen_bin_op(umap, uset, &gist_range_entry);
1095 static int intersect_range_entry(void **entry, void *user)
1097 struct isl_union_map_gen_bin_data *data = user;
1099 struct isl_hash_table_entry *entry2;
1101 isl_map *map = *entry;
1104 dim = isl_map_get_space(map);
1105 dim = isl_space_range(dim);
1106 hash = isl_space_get_hash(dim);
1107 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1108 hash, &has_dim, dim, 0);
1109 isl_space_free(dim);
1113 map = isl_map_copy(map);
1114 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1116 empty = isl_map_is_empty(map);
1126 data->res = isl_union_map_add_map(data->res, map);
1131 __isl_give isl_union_map *isl_union_map_intersect_range(
1132 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1134 return gen_bin_op(umap, uset, &intersect_range_entry);
1137 struct isl_union_map_bin_data {
1138 isl_union_map *umap2;
1141 int (*fn)(void **entry, void *user);
1144 static int apply_range_entry(void **entry, void *user)
1146 struct isl_union_map_bin_data *data = user;
1147 isl_map *map2 = *entry;
1150 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1151 map2->dim, isl_dim_in))
1154 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1156 empty = isl_map_is_empty(map2);
1166 data->res = isl_union_map_add_map(data->res, map2);
1171 static int bin_entry(void **entry, void *user)
1173 struct isl_union_map_bin_data *data = user;
1174 isl_map *map = *entry;
1177 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1178 data->fn, data) < 0)
1184 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1185 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1187 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1189 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1190 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1192 if (!umap1 || !umap2)
1196 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1198 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1199 &bin_entry, &data) < 0)
1202 isl_union_map_free(umap1);
1203 isl_union_map_free(umap2);
1206 isl_union_map_free(umap1);
1207 isl_union_map_free(umap2);
1208 isl_union_map_free(data.res);
1212 __isl_give isl_union_map *isl_union_map_apply_range(
1213 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1215 return bin_op(umap1, umap2, &apply_range_entry);
1218 __isl_give isl_union_map *isl_union_map_apply_domain(
1219 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1221 umap1 = isl_union_map_reverse(umap1);
1222 umap1 = isl_union_map_apply_range(umap1, umap2);
1223 return isl_union_map_reverse(umap1);
1226 __isl_give isl_union_set *isl_union_set_apply(
1227 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1229 return isl_union_map_apply_range(uset, umap);
1232 static int map_lex_lt_entry(void **entry, void *user)
1234 struct isl_union_map_bin_data *data = user;
1235 isl_map *map2 = *entry;
1237 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1238 map2->dim, isl_dim_out))
1241 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1243 data->res = isl_union_map_add_map(data->res, map2);
1248 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1249 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1251 return bin_op(umap1, umap2, &map_lex_lt_entry);
1254 static int map_lex_le_entry(void **entry, void *user)
1256 struct isl_union_map_bin_data *data = user;
1257 isl_map *map2 = *entry;
1259 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1260 map2->dim, isl_dim_out))
1263 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1265 data->res = isl_union_map_add_map(data->res, map2);
1270 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1271 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1273 return bin_op(umap1, umap2, &map_lex_le_entry);
1276 static int product_entry(void **entry, void *user)
1278 struct isl_union_map_bin_data *data = user;
1279 isl_map *map2 = *entry;
1281 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1283 data->res = isl_union_map_add_map(data->res, map2);
1288 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1289 __isl_take isl_union_map *umap2)
1291 return bin_op(umap1, umap2, &product_entry);
1294 static int set_product_entry(void **entry, void *user)
1296 struct isl_union_map_bin_data *data = user;
1297 isl_set *set2 = *entry;
1299 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1301 data->res = isl_union_set_add_set(data->res, set2);
1306 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1307 __isl_take isl_union_set *uset2)
1309 return bin_op(uset1, uset2, &set_product_entry);
1312 static int domain_product_entry(void **entry, void *user)
1314 struct isl_union_map_bin_data *data = user;
1315 isl_map *map2 = *entry;
1317 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1318 map2->dim, isl_dim_out))
1321 map2 = isl_map_domain_product(isl_map_copy(data->map),
1322 isl_map_copy(map2));
1324 data->res = isl_union_map_add_map(data->res, map2);
1329 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1331 __isl_give isl_union_map *isl_union_map_domain_product(
1332 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1334 return bin_op(umap1, umap2, &domain_product_entry);
1337 static int range_product_entry(void **entry, void *user)
1339 struct isl_union_map_bin_data *data = user;
1340 isl_map *map2 = *entry;
1342 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1343 map2->dim, isl_dim_in))
1346 map2 = isl_map_range_product(isl_map_copy(data->map),
1347 isl_map_copy(map2));
1349 data->res = isl_union_map_add_map(data->res, map2);
1354 __isl_give isl_union_map *isl_union_map_range_product(
1355 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1357 return bin_op(umap1, umap2, &range_product_entry);
1360 static int flat_range_product_entry(void **entry, void *user)
1362 struct isl_union_map_bin_data *data = user;
1363 isl_map *map2 = *entry;
1365 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1366 map2->dim, isl_dim_in))
1369 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1370 isl_map_copy(map2));
1372 data->res = isl_union_map_add_map(data->res, map2);
1377 __isl_give isl_union_map *isl_union_map_flat_range_product(
1378 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1380 return bin_op(umap1, umap2, &flat_range_product_entry);
1383 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1384 int (*fn)(void **, void *))
1391 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1392 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1395 isl_union_map_free(umap);
1398 isl_union_map_free(umap);
1399 isl_union_set_free(res);
1403 static int from_range_entry(void **entry, void *user)
1405 isl_map *set = *entry;
1406 isl_union_set **res = user;
1408 *res = isl_union_map_add_map(*res,
1409 isl_map_from_range(isl_set_copy(set)));
1414 __isl_give isl_union_map *isl_union_map_from_range(
1415 __isl_take isl_union_set *uset)
1417 return cond_un_op(uset, &from_range_entry);
1420 __isl_give isl_union_map *isl_union_map_from_domain(
1421 __isl_take isl_union_set *uset)
1423 return isl_union_map_reverse(isl_union_map_from_range(uset));
1426 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1427 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1429 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1430 isl_union_map_from_range(range));
1433 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1434 int (*fn)(void **, void *))
1436 umap = isl_union_map_cow(umap);
1440 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1445 isl_union_map_free(umap);
1449 static int affine_entry(void **entry, void *user)
1451 isl_map **map = (isl_map **)entry;
1453 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1455 return *map ? 0 : -1;
1458 __isl_give isl_union_map *isl_union_map_affine_hull(
1459 __isl_take isl_union_map *umap)
1461 return un_op(umap, &affine_entry);
1464 __isl_give isl_union_set *isl_union_set_affine_hull(
1465 __isl_take isl_union_set *uset)
1467 return isl_union_map_affine_hull(uset);
1470 static int polyhedral_entry(void **entry, void *user)
1472 isl_map **map = (isl_map **)entry;
1474 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1476 return *map ? 0 : -1;
1479 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1480 __isl_take isl_union_map *umap)
1482 return un_op(umap, &polyhedral_entry);
1485 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1486 __isl_take isl_union_set *uset)
1488 return isl_union_map_polyhedral_hull(uset);
1491 static int simple_entry(void **entry, void *user)
1493 isl_map **map = (isl_map **)entry;
1495 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1497 return *map ? 0 : -1;
1500 __isl_give isl_union_map *isl_union_map_simple_hull(
1501 __isl_take isl_union_map *umap)
1503 return un_op(umap, &simple_entry);
1506 __isl_give isl_union_set *isl_union_set_simple_hull(
1507 __isl_take isl_union_set *uset)
1509 return isl_union_map_simple_hull(uset);
1512 static int inplace_entry(void **entry, void *user)
1514 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1515 isl_map **map = (isl_map **)entry;
1518 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1519 copy = fn(isl_map_copy(*map));
1529 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1530 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1535 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1536 &inplace_entry, &fn) < 0)
1541 isl_union_map_free(umap);
1545 __isl_give isl_union_map *isl_union_map_coalesce(
1546 __isl_take isl_union_map *umap)
1548 return inplace(umap, &isl_map_coalesce);
1551 __isl_give isl_union_set *isl_union_set_coalesce(
1552 __isl_take isl_union_set *uset)
1554 return isl_union_map_coalesce(uset);
1557 __isl_give isl_union_map *isl_union_map_detect_equalities(
1558 __isl_take isl_union_map *umap)
1560 return inplace(umap, &isl_map_detect_equalities);
1563 __isl_give isl_union_set *isl_union_set_detect_equalities(
1564 __isl_take isl_union_set *uset)
1566 return isl_union_map_detect_equalities(uset);
1569 __isl_give isl_union_map *isl_union_map_compute_divs(
1570 __isl_take isl_union_map *umap)
1572 return inplace(umap, &isl_map_compute_divs);
1575 __isl_give isl_union_set *isl_union_set_compute_divs(
1576 __isl_take isl_union_set *uset)
1578 return isl_union_map_compute_divs(uset);
1581 static int lexmin_entry(void **entry, void *user)
1583 isl_map **map = (isl_map **)entry;
1585 *map = isl_map_lexmin(*map);
1587 return *map ? 0 : -1;
1590 __isl_give isl_union_map *isl_union_map_lexmin(
1591 __isl_take isl_union_map *umap)
1593 return un_op(umap, &lexmin_entry);
1596 __isl_give isl_union_set *isl_union_set_lexmin(
1597 __isl_take isl_union_set *uset)
1599 return isl_union_map_lexmin(uset);
1602 static int lexmax_entry(void **entry, void *user)
1604 isl_map **map = (isl_map **)entry;
1606 *map = isl_map_lexmax(*map);
1608 return *map ? 0 : -1;
1611 __isl_give isl_union_map *isl_union_map_lexmax(
1612 __isl_take isl_union_map *umap)
1614 return un_op(umap, &lexmax_entry);
1617 __isl_give isl_union_set *isl_union_set_lexmax(
1618 __isl_take isl_union_set *uset)
1620 return isl_union_map_lexmax(uset);
1623 static int universe_entry(void **entry, void *user)
1625 isl_map *map = *entry;
1626 isl_union_map **res = user;
1628 map = isl_map_universe(isl_map_get_space(map));
1629 *res = isl_union_map_add_map(*res, map);
1634 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1636 return cond_un_op(umap, &universe_entry);
1639 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1641 return isl_union_map_universe(uset);
1644 static int reverse_entry(void **entry, void *user)
1646 isl_map *map = *entry;
1647 isl_union_map **res = user;
1649 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1654 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1656 return cond_un_op(umap, &reverse_entry);
1659 static int params_entry(void **entry, void *user)
1661 isl_map *map = *entry;
1662 isl_union_set **res = user;
1664 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1669 /* Compute the parameter domain of the given union map.
1671 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1675 empty = isl_union_map_is_empty(umap);
1677 return isl_union_map_free(umap);
1679 return isl_set_empty(isl_union_map_get_space(umap));
1680 return isl_set_from_union_set(cond_un_op(umap, ¶ms_entry));
1683 /* Compute the parameter domain of the given union set.
1685 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1687 return isl_union_map_params(uset);
1690 static int domain_entry(void **entry, void *user)
1692 isl_map *map = *entry;
1693 isl_union_set **res = user;
1695 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1700 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1702 return cond_un_op(umap, &domain_entry);
1705 static int range_entry(void **entry, void *user)
1707 isl_map *map = *entry;
1708 isl_union_set **res = user;
1710 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1715 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1717 return cond_un_op(umap, &range_entry);
1720 static int domain_map_entry(void **entry, void *user)
1722 isl_map *map = *entry;
1723 isl_union_set **res = user;
1725 *res = isl_union_map_add_map(*res,
1726 isl_map_domain_map(isl_map_copy(map)));
1731 __isl_give isl_union_map *isl_union_map_domain_map(
1732 __isl_take isl_union_map *umap)
1734 return cond_un_op(umap, &domain_map_entry);
1737 static int range_map_entry(void **entry, void *user)
1739 isl_map *map = *entry;
1740 isl_union_set **res = user;
1742 *res = isl_union_map_add_map(*res,
1743 isl_map_range_map(isl_map_copy(map)));
1748 __isl_give isl_union_map *isl_union_map_range_map(
1749 __isl_take isl_union_map *umap)
1751 return cond_un_op(umap, &range_map_entry);
1754 static int deltas_entry(void **entry, void *user)
1756 isl_map *map = *entry;
1757 isl_union_set **res = user;
1759 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1762 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1767 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1769 return cond_un_op(umap, &deltas_entry);
1772 static int deltas_map_entry(void **entry, void *user)
1774 isl_map *map = *entry;
1775 isl_union_map **res = user;
1777 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1780 *res = isl_union_map_add_map(*res,
1781 isl_map_deltas_map(isl_map_copy(map)));
1786 __isl_give isl_union_map *isl_union_map_deltas_map(
1787 __isl_take isl_union_map *umap)
1789 return cond_un_op(umap, &deltas_map_entry);
1792 static int identity_entry(void **entry, void *user)
1794 isl_set *set = *entry;
1795 isl_union_map **res = user;
1797 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1802 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1804 return cond_un_op(uset, &identity_entry);
1807 static int unwrap_entry(void **entry, void *user)
1809 isl_set *set = *entry;
1810 isl_union_set **res = user;
1812 if (!isl_set_is_wrapping(set))
1815 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1820 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1822 return cond_un_op(uset, &unwrap_entry);
1825 static int wrap_entry(void **entry, void *user)
1827 isl_map *map = *entry;
1828 isl_union_set **res = user;
1830 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1835 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1837 return cond_un_op(umap, &wrap_entry);
1840 struct isl_union_map_is_subset_data {
1841 isl_union_map *umap2;
1845 static int is_subset_entry(void **entry, void *user)
1847 struct isl_union_map_is_subset_data *data = user;
1849 struct isl_hash_table_entry *entry2;
1850 isl_map *map = *entry;
1852 hash = isl_space_get_hash(map->dim);
1853 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1854 hash, &has_dim, map->dim, 0);
1856 int empty = isl_map_is_empty(map);
1861 data->is_subset = 0;
1865 data->is_subset = isl_map_is_subset(map, entry2->data);
1866 if (data->is_subset < 0 || !data->is_subset)
1872 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1873 __isl_keep isl_union_map *umap2)
1875 struct isl_union_map_is_subset_data data = { NULL, 1 };
1877 umap1 = isl_union_map_copy(umap1);
1878 umap2 = isl_union_map_copy(umap2);
1879 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1880 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1882 if (!umap1 || !umap2)
1886 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1887 &is_subset_entry, &data) < 0 &&
1891 isl_union_map_free(umap1);
1892 isl_union_map_free(umap2);
1894 return data.is_subset;
1896 isl_union_map_free(umap1);
1897 isl_union_map_free(umap2);
1901 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1902 __isl_keep isl_union_set *uset2)
1904 return isl_union_map_is_subset(uset1, uset2);
1907 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1908 __isl_keep isl_union_map *umap2)
1912 if (!umap1 || !umap2)
1914 is_subset = isl_union_map_is_subset(umap1, umap2);
1917 is_subset = isl_union_map_is_subset(umap2, umap1);
1921 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1922 __isl_keep isl_union_set *uset2)
1924 return isl_union_map_is_equal(uset1, uset2);
1927 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1928 __isl_keep isl_union_map *umap2)
1932 if (!umap1 || !umap2)
1934 is_subset = isl_union_map_is_subset(umap1, umap2);
1937 is_subset = isl_union_map_is_subset(umap2, umap1);
1938 if (is_subset == -1)
1943 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1944 __isl_keep isl_union_set *uset2)
1946 return isl_union_map_is_strict_subset(uset1, uset2);
1949 static int sample_entry(void **entry, void *user)
1951 isl_basic_map **sample = (isl_basic_map **)user;
1952 isl_map *map = *entry;
1954 *sample = isl_map_sample(isl_map_copy(map));
1957 if (!isl_basic_map_plain_is_empty(*sample))
1962 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1964 isl_basic_map *sample = NULL;
1969 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1970 &sample_entry, &sample) < 0 &&
1975 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1977 isl_union_map_free(umap);
1981 isl_union_map_free(umap);
1985 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1987 return (isl_basic_set *)isl_union_map_sample(uset);
1990 struct isl_forall_data {
1992 int (*fn)(__isl_keep isl_map *map);
1995 static int forall_entry(void **entry, void *user)
1997 struct isl_forall_data *data = user;
1998 isl_map *map = *entry;
2000 data->res = data->fn(map);
2010 static int union_map_forall(__isl_keep isl_union_map *umap,
2011 int (*fn)(__isl_keep isl_map *map))
2013 struct isl_forall_data data = { 1, fn };
2018 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2019 &forall_entry, &data) < 0 && data.res)
2025 struct isl_forall_user_data {
2027 int (*fn)(__isl_keep isl_map *map, void *user);
2031 static int forall_user_entry(void **entry, void *user)
2033 struct isl_forall_user_data *data = user;
2034 isl_map *map = *entry;
2036 data->res = data->fn(map, data->user);
2046 /* Check if fn(map, user) returns true for all maps "map" in umap.
2048 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2049 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2051 struct isl_forall_user_data data = { 1, fn, user };
2056 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2057 &forall_user_entry, &data) < 0 && data.res)
2063 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2065 return union_map_forall(umap, &isl_map_is_empty);
2068 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2070 return isl_union_map_is_empty(uset);
2073 static int is_subset_of_identity(__isl_keep isl_map *map)
2082 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2085 dim = isl_map_get_space(map);
2086 id = isl_map_identity(dim);
2088 is_subset = isl_map_is_subset(map, id);
2095 /* Check if the given map is single-valued.
2100 * and check if the result is a subset of the identity mapping.
2102 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2104 isl_union_map *test;
2107 if (isl_union_map_n_map(umap) == 1) {
2109 umap = isl_union_map_copy(umap);
2110 map = isl_map_from_union_map(umap);
2111 sv = isl_map_is_single_valued(map);
2116 test = isl_union_map_reverse(isl_union_map_copy(umap));
2117 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2119 sv = union_map_forall(test, &is_subset_of_identity);
2121 isl_union_map_free(test);
2126 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2130 umap = isl_union_map_copy(umap);
2131 umap = isl_union_map_reverse(umap);
2132 in = isl_union_map_is_single_valued(umap);
2133 isl_union_map_free(umap);
2138 /* Represents a map that has a fixed value (v) for one of its
2140 * The map in this structure is not reference counted, so it
2141 * is only valid while the isl_union_map from which it was
2142 * obtained is still alive.
2144 struct isl_fixed_map {
2149 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2153 struct isl_fixed_map *v;
2155 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2158 for (i = 0; i < n; ++i)
2159 isl_int_init(v[i].v);
2163 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2169 for (i = 0; i < n; ++i)
2170 isl_int_clear(v[i].v);
2174 /* Compare the "v" field of two isl_fixed_map structs.
2176 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2178 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2179 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2181 return isl_int_cmp(e1->v, e2->v);
2184 /* Internal data structure used while checking whether all maps
2185 * in a union_map have a fixed value for a given output dimension.
2186 * v is the list of maps, with the fixed value for the dimension
2187 * n is the number of maps considered so far
2188 * pos is the output dimension under investigation
2190 struct isl_fixed_dim_data {
2191 struct isl_fixed_map *v;
2196 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2198 struct isl_fixed_dim_data *data = user;
2200 data->v[data->n].map = map;
2201 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2202 &data->v[data->n++].v);
2205 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2206 int first, int n_range);
2208 /* Given a list of the maps, with their fixed values at output dimension "pos",
2209 * check whether the ranges of the maps form an obvious partition.
2211 * We first sort the maps according to their fixed values.
2212 * If all maps have a different value, then we know the ranges form
2214 * Otherwise, we collect the maps with the same fixed value and
2215 * check whether each such collection is obviously injective
2216 * based on later dimensions.
2218 static int separates(struct isl_fixed_map *v, int n,
2219 __isl_take isl_space *dim, int pos, int n_range)
2226 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2228 for (i = 0; i + 1 < n; ++i) {
2230 isl_union_map *part;
2233 for (j = i + 1; j < n; ++j)
2234 if (isl_int_ne(v[i].v, v[j].v))
2240 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2241 for (k = i; k < j; ++k)
2242 part = isl_union_map_add_map(part,
2243 isl_map_copy(v[k].map));
2245 injective = plain_injective_on_range(part, pos + 1, n_range);
2254 isl_space_free(dim);
2255 free_isl_fixed_map_array(v, n);
2258 isl_space_free(dim);
2259 free_isl_fixed_map_array(v, n);
2263 /* Check whether the maps in umap have obviously distinct ranges.
2264 * In particular, check for an output dimension in the range
2265 * [first,n_range) for which all maps have a fixed value
2266 * and then check if these values, possibly along with fixed values
2267 * at later dimensions, entail distinct ranges.
2269 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2270 int first, int n_range)
2274 struct isl_fixed_dim_data data = { NULL };
2276 ctx = isl_union_map_get_ctx(umap);
2278 n = isl_union_map_n_map(umap);
2283 isl_union_map_free(umap);
2287 if (first >= n_range) {
2288 isl_union_map_free(umap);
2292 data.v = alloc_isl_fixed_map_array(ctx, n);
2296 for (data.pos = first; data.pos < n_range; ++data.pos) {
2302 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2307 dim = isl_union_map_get_space(umap);
2308 injective = separates(data.v, n, dim, data.pos, n_range);
2309 isl_union_map_free(umap);
2313 free_isl_fixed_map_array(data.v, n);
2314 isl_union_map_free(umap);
2318 free_isl_fixed_map_array(data.v, n);
2319 isl_union_map_free(umap);
2323 /* Check whether the maps in umap that map to subsets of "ran"
2324 * have obviously distinct ranges.
2326 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2328 isl_union_map *umap = user;
2330 umap = isl_union_map_copy(umap);
2331 umap = isl_union_map_intersect_range(umap,
2332 isl_union_set_from_set(isl_set_copy(ran)));
2333 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2336 /* Check if the given union_map is obviously injective.
2338 * In particular, we first check if all individual maps are obviously
2339 * injective and then check if all the ranges of these maps are
2340 * obviously disjoint.
2342 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2345 isl_union_map *univ;
2348 in = union_map_forall(umap, &isl_map_plain_is_injective);
2354 univ = isl_union_map_universe(isl_union_map_copy(umap));
2355 ran = isl_union_map_range(univ);
2357 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2359 isl_union_set_free(ran);
2364 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2368 sv = isl_union_map_is_single_valued(umap);
2372 return isl_union_map_is_injective(umap);
2375 static int zip_entry(void **entry, void *user)
2377 isl_map *map = *entry;
2378 isl_union_map **res = user;
2380 if (!isl_map_can_zip(map))
2383 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2388 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2390 return cond_un_op(umap, &zip_entry);
2393 static int uncurry_entry(void **entry, void *user)
2395 isl_map *map = *entry;
2396 isl_union_map **res = user;
2398 if (!isl_map_can_uncurry(map))
2401 *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2406 /* Given a union map, take the maps of the form A -> (B -> C) and
2407 * return the union of the corresponding maps (A -> B) -> C.
2409 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2411 return cond_un_op(umap, &uncurry_entry);
2414 static int curry_entry(void **entry, void *user)
2416 isl_map *map = *entry;
2417 isl_union_map **res = user;
2419 if (!isl_map_can_curry(map))
2422 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2427 /* Given a union map, take the maps of the form (A -> B) -> C and
2428 * return the union of the corresponding maps A -> (B -> C).
2430 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2432 return cond_un_op(umap, &curry_entry);
2435 static int lift_entry(void **entry, void *user)
2437 isl_set *set = *entry;
2438 isl_union_set **res = user;
2440 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2445 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2447 return cond_un_op(uset, &lift_entry);
2450 static int coefficients_entry(void **entry, void *user)
2452 isl_set *set = *entry;
2453 isl_union_set **res = user;
2455 set = isl_set_copy(set);
2456 set = isl_set_from_basic_set(isl_set_coefficients(set));
2457 *res = isl_union_set_add_set(*res, set);
2462 __isl_give isl_union_set *isl_union_set_coefficients(
2463 __isl_take isl_union_set *uset)
2472 ctx = isl_union_set_get_ctx(uset);
2473 dim = isl_space_set_alloc(ctx, 0, 0);
2474 res = isl_union_map_alloc(dim, uset->table.n);
2475 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2476 &coefficients_entry, &res) < 0)
2479 isl_union_set_free(uset);
2482 isl_union_set_free(uset);
2483 isl_union_set_free(res);
2487 static int solutions_entry(void **entry, void *user)
2489 isl_set *set = *entry;
2490 isl_union_set **res = user;
2492 set = isl_set_copy(set);
2493 set = isl_set_from_basic_set(isl_set_solutions(set));
2495 *res = isl_union_set_from_set(set);
2497 *res = isl_union_set_add_set(*res, set);
2505 __isl_give isl_union_set *isl_union_set_solutions(
2506 __isl_take isl_union_set *uset)
2508 isl_union_set *res = NULL;
2513 if (uset->table.n == 0) {
2514 res = isl_union_set_empty(isl_union_set_get_space(uset));
2515 isl_union_set_free(uset);
2519 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2520 &solutions_entry, &res) < 0)
2523 isl_union_set_free(uset);
2526 isl_union_set_free(uset);
2527 isl_union_set_free(res);