isl_test: generalize coalesce tests
[isl.git] / isl_union_map.c
blobed6639f63ca0f7a095fdd7a0116daeb87b7ac098
1 /*
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,
8 * 91893 Orsay, France
9 */
11 #define ISL_DIM_H
12 #include <isl_map_private.h>
13 #include <isl/ctx.h>
14 #include <isl/hash.h>
15 #include <isl/map.h>
16 #include <isl/set.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)
25 isl_set *set;
26 int params;
28 if (!uset)
29 return -1;
30 if (uset->table.n != 1)
31 return 0;
33 set = isl_set_from_union_set(isl_union_set_copy(uset));
34 params = isl_set_is_params(set);
35 isl_set_free(set);
36 return params;
39 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
40 int size)
42 isl_union_map *umap;
44 dim = isl_space_params(dim);
45 if (!dim)
46 return NULL;
48 umap = isl_calloc_type(dim->ctx, isl_union_map);
49 if (!umap)
50 return NULL;
52 umap->ref = 1;
53 umap->dim = dim;
54 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
55 goto error;
57 return umap;
58 error:
59 isl_space_free(dim);
60 isl_union_map_free(umap);
61 return NULL;
64 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
66 return isl_union_map_alloc(dim, 16);
69 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
71 return isl_union_map_empty(dim);
74 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
76 return umap ? umap->dim->ctx : NULL;
79 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
81 return uset ? uset->dim->ctx : NULL;
84 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
86 if (!umap)
87 return NULL;
88 return isl_space_copy(umap->dim);
91 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
93 return isl_union_map_get_space(uset);
96 static int free_umap_entry(void **entry, void *user)
98 isl_map *map = *entry;
99 isl_map_free(map);
100 return 0;
103 static int add_map(__isl_take isl_map *map, void *user)
105 isl_union_map **umap = (isl_union_map **)user;
107 *umap = isl_union_map_add_map(*umap, map);
109 return 0;
112 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
114 isl_union_map *dup;
116 if (!umap)
117 return NULL;
119 dup = isl_union_map_empty(isl_space_copy(umap->dim));
120 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
121 goto error;
122 return dup;
123 error:
124 isl_union_map_free(dup);
125 return NULL;
128 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
130 if (!umap)
131 return NULL;
133 if (umap->ref == 1)
134 return umap;
135 umap->ref--;
136 return isl_union_map_dup(umap);
139 struct isl_union_align {
140 isl_reordering *exp;
141 isl_union_map *res;
144 static int align_entry(void **entry, void *user)
146 isl_map *map = *entry;
147 isl_reordering *exp;
148 struct isl_union_align *data = user;
150 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
151 isl_map_get_space(map));
153 data->res = isl_union_map_add_map(data->res,
154 isl_map_realign(isl_map_copy(map), exp));
156 return 0;
159 /* Align the parameters of umap along those of model.
160 * The result has the parameters of model first, in the same order
161 * as they appear in model, followed by any remaining parameters of
162 * umap that do not appear in model.
164 __isl_give isl_union_map *isl_union_map_align_params(
165 __isl_take isl_union_map *umap, __isl_take isl_space *model)
167 struct isl_union_align data = { NULL, NULL };
169 if (!umap || !model)
170 goto error;
172 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
173 isl_space_free(model);
174 return umap;
177 model = isl_space_params(model);
178 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
179 if (!data.exp)
180 goto error;
182 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
183 umap->table.n);
184 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
185 &align_entry, &data) < 0)
186 goto error;
188 isl_reordering_free(data.exp);
189 isl_union_map_free(umap);
190 isl_space_free(model);
191 return data.res;
192 error:
193 isl_reordering_free(data.exp);
194 isl_union_map_free(umap);
195 isl_union_map_free(data.res);
196 isl_space_free(model);
197 return NULL;
200 __isl_give isl_union_set *isl_union_set_align_params(
201 __isl_take isl_union_set *uset, __isl_take isl_space *model)
203 return isl_union_map_align_params(uset, model);
206 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
207 __isl_take isl_union_map *umap2)
209 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
210 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
212 umap1 = isl_union_map_cow(umap1);
214 if (!umap1 || !umap2)
215 goto error;
217 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
218 goto error;
220 isl_union_map_free(umap2);
222 return umap1;
223 error:
224 isl_union_map_free(umap1);
225 isl_union_map_free(umap2);
226 return NULL;
229 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
230 __isl_take isl_union_set *uset2)
232 return isl_union_map_union(uset1, uset2);
235 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
237 if (!umap)
238 return NULL;
240 umap->ref++;
241 return umap;
244 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
246 return isl_union_map_copy(uset);
249 void *isl_union_map_free(__isl_take isl_union_map *umap)
251 if (!umap)
252 return NULL;
254 if (--umap->ref > 0)
255 return NULL;
257 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
258 &free_umap_entry, NULL);
259 isl_hash_table_clear(&umap->table);
260 isl_space_free(umap->dim);
261 free(umap);
262 return NULL;
265 void *isl_union_set_free(__isl_take isl_union_set *uset)
267 return isl_union_map_free(uset);
270 static int has_dim(const void *entry, const void *val)
272 isl_map *map = (isl_map *)entry;
273 isl_space *dim = (isl_space *)val;
275 return isl_space_is_equal(map->dim, dim);
278 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
279 __isl_take isl_map *map)
281 uint32_t hash;
282 struct isl_hash_table_entry *entry;
284 if (!map || !umap)
285 goto error;
287 if (isl_map_plain_is_empty(map)) {
288 isl_map_free(map);
289 return umap;
292 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
293 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
294 map = isl_map_align_params(map, isl_union_map_get_space(umap));
297 umap = isl_union_map_cow(umap);
299 if (!map || !umap)
300 goto error;
302 hash = isl_space_get_hash(map->dim);
303 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
304 &has_dim, map->dim, 1);
305 if (!entry)
306 goto error;
308 if (!entry->data)
309 entry->data = map;
310 else {
311 entry->data = isl_map_union(entry->data, isl_map_copy(map));
312 if (!entry->data)
313 goto error;
314 isl_map_free(map);
317 return umap;
318 error:
319 isl_map_free(map);
320 isl_union_map_free(umap);
321 return NULL;
324 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
325 __isl_take isl_set *set)
327 return isl_union_map_add_map(uset, (isl_map *)set);
330 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
332 isl_space *dim;
333 isl_union_map *umap;
335 if (!map)
336 return NULL;
338 dim = isl_map_get_space(map);
339 dim = isl_space_params(dim);
340 umap = isl_union_map_empty(dim);
341 umap = isl_union_map_add_map(umap, map);
343 return umap;
346 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
348 return isl_union_map_from_map((isl_map *)set);
351 __isl_give isl_union_map *isl_union_map_from_basic_map(
352 __isl_take isl_basic_map *bmap)
354 return isl_union_map_from_map(isl_map_from_basic_map(bmap));
357 __isl_give isl_union_set *isl_union_set_from_basic_set(
358 __isl_take isl_basic_set *bset)
360 return isl_union_map_from_basic_map(bset);
363 struct isl_union_map_foreach_data
365 int (*fn)(__isl_take isl_map *map, void *user);
366 void *user;
369 static int call_on_copy(void **entry, void *user)
371 isl_map *map = *entry;
372 struct isl_union_map_foreach_data *data;
373 data = (struct isl_union_map_foreach_data *)user;
375 return data->fn(isl_map_copy(map), data->user);
378 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
380 return umap ? umap->table.n : 0;
383 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
385 return uset ? uset->table.n : 0;
388 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
389 int (*fn)(__isl_take isl_map *map, void *user), void *user)
391 struct isl_union_map_foreach_data data = { fn, user };
393 if (!umap)
394 return -1;
396 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
397 &call_on_copy, &data);
400 static int copy_map(void **entry, void *user)
402 isl_map *map = *entry;
403 isl_map **map_p = user;
405 *map_p = isl_map_copy(map);
407 return -1;
410 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
412 isl_ctx *ctx;
413 isl_map *map = NULL;
415 if (!umap)
416 return NULL;
417 ctx = isl_union_map_get_ctx(umap);
418 if (umap->table.n != 1)
419 isl_die(ctx, isl_error_invalid,
420 "union map needs to contain elements in exactly "
421 "one space", return isl_union_map_free(umap));
423 isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
425 isl_union_map_free(umap);
427 return map;
430 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
432 return isl_map_from_union_map(uset);
435 /* Extract the map in "umap" that lives in the given space (ignoring
436 * parameters).
438 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
439 __isl_take isl_space *space)
441 uint32_t hash;
442 struct isl_hash_table_entry *entry;
444 space = isl_space_drop_dims(space, isl_dim_param,
445 0, isl_space_dim(space, isl_dim_param));
446 space = isl_space_align_params(space, isl_union_map_get_space(umap));
447 if (!umap || !space)
448 goto error;
450 hash = isl_space_get_hash(space);
451 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
452 &has_dim, space, 0);
453 if (!entry)
454 return isl_map_empty(space);
455 isl_space_free(space);
456 return isl_map_copy(entry->data);
457 error:
458 isl_space_free(space);
459 return NULL;
462 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
463 __isl_take isl_space *dim)
465 return (isl_set *)isl_union_map_extract_map(uset, dim);
468 /* Check if umap contains a map in the given space.
470 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
471 __isl_keep isl_space *dim)
473 uint32_t hash;
474 struct isl_hash_table_entry *entry;
476 if (!umap || !dim)
477 return -1;
479 hash = isl_space_get_hash(dim);
480 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
481 &has_dim, dim, 0);
482 return !!entry;
485 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
486 __isl_keep isl_space *dim)
488 return isl_union_map_contains(uset, dim);
491 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
492 int (*fn)(__isl_take isl_set *set, void *user), void *user)
494 return isl_union_map_foreach_map(uset,
495 (int(*)(__isl_take isl_map *, void*))fn, user);
498 struct isl_union_set_foreach_point_data {
499 int (*fn)(__isl_take isl_point *pnt, void *user);
500 void *user;
503 static int foreach_point(__isl_take isl_set *set, void *user)
505 struct isl_union_set_foreach_point_data *data = user;
506 int r;
508 r = isl_set_foreach_point(set, data->fn, data->user);
509 isl_set_free(set);
511 return r;
514 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
515 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
517 struct isl_union_set_foreach_point_data data = { fn, user };
518 return isl_union_set_foreach_set(uset, &foreach_point, &data);
521 struct isl_union_map_gen_bin_data {
522 isl_union_map *umap2;
523 isl_union_map *res;
526 static int subtract_entry(void **entry, void *user)
528 struct isl_union_map_gen_bin_data *data = user;
529 uint32_t hash;
530 struct isl_hash_table_entry *entry2;
531 isl_map *map = *entry;
533 hash = isl_space_get_hash(map->dim);
534 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
535 hash, &has_dim, map->dim, 0);
536 map = isl_map_copy(map);
537 if (entry2) {
538 int empty;
539 map = isl_map_subtract(map, isl_map_copy(entry2->data));
541 empty = isl_map_is_empty(map);
542 if (empty < 0) {
543 isl_map_free(map);
544 return -1;
546 if (empty) {
547 isl_map_free(map);
548 return 0;
551 data->res = isl_union_map_add_map(data->res, map);
553 return 0;
556 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
557 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
559 struct isl_union_map_gen_bin_data data = { NULL, NULL };
561 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
562 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
564 if (!umap1 || !umap2)
565 goto error;
567 data.umap2 = umap2;
568 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
569 umap1->table.n);
570 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
571 fn, &data) < 0)
572 goto error;
574 isl_union_map_free(umap1);
575 isl_union_map_free(umap2);
576 return data.res;
577 error:
578 isl_union_map_free(umap1);
579 isl_union_map_free(umap2);
580 isl_union_map_free(data.res);
581 return NULL;
584 __isl_give isl_union_map *isl_union_map_subtract(
585 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
587 return gen_bin_op(umap1, umap2, &subtract_entry);
590 __isl_give isl_union_set *isl_union_set_subtract(
591 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
593 return isl_union_map_subtract(uset1, uset2);
596 struct isl_union_map_gen_bin_set_data {
597 isl_set *set;
598 isl_union_map *res;
601 static int intersect_params_entry(void **entry, void *user)
603 struct isl_union_map_gen_bin_set_data *data = user;
604 isl_map *map = *entry;
605 int empty;
607 map = isl_map_copy(map);
608 map = isl_map_intersect_params(map, isl_set_copy(data->set));
610 empty = isl_map_is_empty(map);
611 if (empty < 0) {
612 isl_map_free(map);
613 return -1;
616 data->res = isl_union_map_add_map(data->res, map);
618 return 0;
621 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
622 __isl_take isl_set *set, int (*fn)(void **, void *))
624 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
626 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
627 set = isl_set_align_params(set, isl_union_map_get_space(umap));
629 if (!umap || !set)
630 goto error;
632 data.set = set;
633 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
634 umap->table.n);
635 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
636 fn, &data) < 0)
637 goto error;
639 isl_union_map_free(umap);
640 isl_set_free(set);
641 return data.res;
642 error:
643 isl_union_map_free(umap);
644 isl_set_free(set);
645 isl_union_map_free(data.res);
646 return NULL;
649 __isl_give isl_union_map *isl_union_map_intersect_params(
650 __isl_take isl_union_map *umap, __isl_take isl_set *set)
652 return gen_bin_set_op(umap, set, &intersect_params_entry);
655 __isl_give isl_union_set *isl_union_set_intersect_params(
656 __isl_take isl_union_set *uset, __isl_take isl_set *set)
658 return isl_union_map_intersect_params(uset, set);
661 static __isl_give isl_union_map *union_map_intersect_params(
662 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
664 return isl_union_map_intersect_params(umap,
665 isl_set_from_union_set(uset));
668 static __isl_give isl_union_map *union_map_gist_params(
669 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
671 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
674 struct isl_union_map_match_bin_data {
675 isl_union_map *umap2;
676 isl_union_map *res;
677 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
680 static int match_bin_entry(void **entry, void *user)
682 struct isl_union_map_match_bin_data *data = user;
683 uint32_t hash;
684 struct isl_hash_table_entry *entry2;
685 isl_map *map = *entry;
686 int empty;
688 hash = isl_space_get_hash(map->dim);
689 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
690 hash, &has_dim, map->dim, 0);
691 if (!entry2)
692 return 0;
694 map = isl_map_copy(map);
695 map = data->fn(map, isl_map_copy(entry2->data));
697 empty = isl_map_is_empty(map);
698 if (empty < 0) {
699 isl_map_free(map);
700 return -1;
702 if (empty) {
703 isl_map_free(map);
704 return 0;
707 data->res = isl_union_map_add_map(data->res, map);
709 return 0;
712 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
713 __isl_take isl_union_map *umap2,
714 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
716 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
718 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
719 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
721 if (!umap1 || !umap2)
722 goto error;
724 data.umap2 = umap2;
725 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
726 umap1->table.n);
727 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
728 &match_bin_entry, &data) < 0)
729 goto error;
731 isl_union_map_free(umap1);
732 isl_union_map_free(umap2);
733 return data.res;
734 error:
735 isl_union_map_free(umap1);
736 isl_union_map_free(umap2);
737 isl_union_map_free(data.res);
738 return NULL;
741 __isl_give isl_union_map *isl_union_map_intersect(
742 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
744 return match_bin_op(umap1, umap2, &isl_map_intersect);
747 /* Compute the intersection of the two union_sets.
748 * As a special case, if exactly one of the two union_sets
749 * is a parameter domain, then intersect the parameter domain
750 * of the other one with this set.
752 __isl_give isl_union_set *isl_union_set_intersect(
753 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
755 int p1, p2;
757 p1 = isl_union_set_is_params(uset1);
758 p2 = isl_union_set_is_params(uset2);
759 if (p1 < 0 || p2 < 0)
760 goto error;
761 if (!p1 && p2)
762 return union_map_intersect_params(uset1, uset2);
763 if (p1 && !p2)
764 return union_map_intersect_params(uset2, uset1);
765 return isl_union_map_intersect(uset1, uset2);
766 error:
767 isl_union_set_free(uset1);
768 isl_union_set_free(uset2);
769 return NULL;
772 static int gist_params_entry(void **entry, void *user)
774 struct isl_union_map_gen_bin_set_data *data = user;
775 isl_map *map = *entry;
776 int empty;
778 map = isl_map_copy(map);
779 map = isl_map_gist_params(map, isl_set_copy(data->set));
781 empty = isl_map_is_empty(map);
782 if (empty < 0) {
783 isl_map_free(map);
784 return -1;
787 data->res = isl_union_map_add_map(data->res, map);
789 return 0;
792 __isl_give isl_union_map *isl_union_map_gist_params(
793 __isl_take isl_union_map *umap, __isl_take isl_set *set)
795 return gen_bin_set_op(umap, set, &gist_params_entry);
798 __isl_give isl_union_set *isl_union_set_gist_params(
799 __isl_take isl_union_set *uset, __isl_take isl_set *set)
801 return isl_union_map_gist_params(uset, set);
804 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
805 __isl_take isl_union_map *context)
807 return match_bin_op(umap, context, &isl_map_gist);
810 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
811 __isl_take isl_union_set *context)
813 if (isl_union_set_is_params(context))
814 return union_map_gist_params(uset, context);
815 return isl_union_map_gist(uset, context);
818 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
819 __isl_take isl_map *set2)
821 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
824 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
825 __isl_take isl_map *set2)
827 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
830 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
831 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
833 return match_bin_op(uset1, uset2, &lex_lt_set);
836 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
837 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
839 return match_bin_op(uset1, uset2, &lex_le_set);
842 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
843 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
845 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
848 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
849 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
851 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
854 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
855 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
857 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
860 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
861 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
863 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
866 static int intersect_domain_entry(void **entry, void *user)
868 struct isl_union_map_gen_bin_data *data = user;
869 uint32_t hash;
870 struct isl_hash_table_entry *entry2;
871 isl_space *dim;
872 isl_map *map = *entry;
873 int empty;
875 dim = isl_map_get_space(map);
876 dim = isl_space_domain(dim);
877 hash = isl_space_get_hash(dim);
878 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
879 hash, &has_dim, dim, 0);
880 isl_space_free(dim);
881 if (!entry2)
882 return 0;
884 map = isl_map_copy(map);
885 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
887 empty = isl_map_is_empty(map);
888 if (empty < 0) {
889 isl_map_free(map);
890 return -1;
892 if (empty) {
893 isl_map_free(map);
894 return 0;
897 data->res = isl_union_map_add_map(data->res, map);
899 return 0;
902 /* Intersect the domain of "umap" with "uset".
903 * If "uset" is a parameters domain, then intersect the parameter
904 * domain of "umap" with this set.
906 __isl_give isl_union_map *isl_union_map_intersect_domain(
907 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
909 if (isl_union_set_is_params(uset))
910 return union_map_intersect_params(umap, uset);
911 return gen_bin_op(umap, uset, &intersect_domain_entry);
914 /* Remove the elements of data->umap2 from the domain of *entry
915 * and add the result to data->res.
917 static int subtract_domain_entry(void **entry, void *user)
919 struct isl_union_map_gen_bin_data *data = user;
920 uint32_t hash;
921 struct isl_hash_table_entry *entry2;
922 isl_space *dim;
923 isl_map *map = *entry;
924 int empty;
926 dim = isl_map_get_space(map);
927 dim = isl_space_domain(dim);
928 hash = isl_space_get_hash(dim);
929 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
930 hash, &has_dim, dim, 0);
931 isl_space_free(dim);
933 map = isl_map_copy(map);
935 if (!entry2) {
936 data->res = isl_union_map_add_map(data->res, map);
937 return 0;
940 map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
942 empty = isl_map_is_empty(map);
943 if (empty < 0) {
944 isl_map_free(map);
945 return -1;
947 if (empty) {
948 isl_map_free(map);
949 return 0;
952 data->res = isl_union_map_add_map(data->res, map);
954 return 0;
957 /* Remove the elements of "uset" from the domain of "umap".
959 __isl_give isl_union_map *isl_union_map_subtract_domain(
960 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
962 return gen_bin_op(umap, dom, &subtract_domain_entry);
965 /* Remove the elements of data->umap2 from the range of *entry
966 * and add the result to data->res.
968 static int subtract_range_entry(void **entry, void *user)
970 struct isl_union_map_gen_bin_data *data = user;
971 uint32_t hash;
972 struct isl_hash_table_entry *entry2;
973 isl_space *space;
974 isl_map *map = *entry;
975 int empty;
977 space = isl_map_get_space(map);
978 space = isl_space_range(space);
979 hash = isl_space_get_hash(space);
980 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
981 hash, &has_dim, space, 0);
982 isl_space_free(space);
984 map = isl_map_copy(map);
986 if (!entry2) {
987 data->res = isl_union_map_add_map(data->res, map);
988 return 0;
991 map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
993 empty = isl_map_is_empty(map);
994 if (empty < 0) {
995 isl_map_free(map);
996 return -1;
998 if (empty) {
999 isl_map_free(map);
1000 return 0;
1003 data->res = isl_union_map_add_map(data->res, map);
1005 return 0;
1008 /* Remove the elements of "uset" from the range of "umap".
1010 __isl_give isl_union_map *isl_union_map_subtract_range(
1011 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1013 return gen_bin_op(umap, dom, &subtract_range_entry);
1016 static int gist_domain_entry(void **entry, void *user)
1018 struct isl_union_map_gen_bin_data *data = user;
1019 uint32_t hash;
1020 struct isl_hash_table_entry *entry2;
1021 isl_space *dim;
1022 isl_map *map = *entry;
1023 int empty;
1025 dim = isl_map_get_space(map);
1026 dim = isl_space_domain(dim);
1027 hash = isl_space_get_hash(dim);
1028 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1029 hash, &has_dim, dim, 0);
1030 isl_space_free(dim);
1031 if (!entry2)
1032 return 0;
1034 map = isl_map_copy(map);
1035 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1037 empty = isl_map_is_empty(map);
1038 if (empty < 0) {
1039 isl_map_free(map);
1040 return -1;
1043 data->res = isl_union_map_add_map(data->res, map);
1045 return 0;
1048 /* Compute the gist of "umap" with respect to the domain "uset".
1049 * If "uset" is a parameters domain, then compute the gist
1050 * with respect to this parameter domain.
1052 __isl_give isl_union_map *isl_union_map_gist_domain(
1053 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1055 if (isl_union_set_is_params(uset))
1056 return union_map_gist_params(umap, uset);
1057 return gen_bin_op(umap, uset, &gist_domain_entry);
1060 static int gist_range_entry(void **entry, void *user)
1062 struct isl_union_map_gen_bin_data *data = user;
1063 uint32_t hash;
1064 struct isl_hash_table_entry *entry2;
1065 isl_space *space;
1066 isl_map *map = *entry;
1067 int empty;
1069 space = isl_map_get_space(map);
1070 space = isl_space_range(space);
1071 hash = isl_space_get_hash(space);
1072 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1073 hash, &has_dim, space, 0);
1074 isl_space_free(space);
1075 if (!entry2)
1076 return 0;
1078 map = isl_map_copy(map);
1079 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1081 empty = isl_map_is_empty(map);
1082 if (empty < 0) {
1083 isl_map_free(map);
1084 return -1;
1087 data->res = isl_union_map_add_map(data->res, map);
1089 return 0;
1092 /* Compute the gist of "umap" with respect to the range "uset".
1094 __isl_give isl_union_map *isl_union_map_gist_range(
1095 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1097 return gen_bin_op(umap, uset, &gist_range_entry);
1100 static int intersect_range_entry(void **entry, void *user)
1102 struct isl_union_map_gen_bin_data *data = user;
1103 uint32_t hash;
1104 struct isl_hash_table_entry *entry2;
1105 isl_space *dim;
1106 isl_map *map = *entry;
1107 int empty;
1109 dim = isl_map_get_space(map);
1110 dim = isl_space_range(dim);
1111 hash = isl_space_get_hash(dim);
1112 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1113 hash, &has_dim, dim, 0);
1114 isl_space_free(dim);
1115 if (!entry2)
1116 return 0;
1118 map = isl_map_copy(map);
1119 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1121 empty = isl_map_is_empty(map);
1122 if (empty < 0) {
1123 isl_map_free(map);
1124 return -1;
1126 if (empty) {
1127 isl_map_free(map);
1128 return 0;
1131 data->res = isl_union_map_add_map(data->res, map);
1133 return 0;
1136 __isl_give isl_union_map *isl_union_map_intersect_range(
1137 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1139 return gen_bin_op(umap, uset, &intersect_range_entry);
1142 struct isl_union_map_bin_data {
1143 isl_union_map *umap2;
1144 isl_union_map *res;
1145 isl_map *map;
1146 int (*fn)(void **entry, void *user);
1149 static int apply_range_entry(void **entry, void *user)
1151 struct isl_union_map_bin_data *data = user;
1152 isl_map *map2 = *entry;
1153 int empty;
1155 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1156 map2->dim, isl_dim_in))
1157 return 0;
1159 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1161 empty = isl_map_is_empty(map2);
1162 if (empty < 0) {
1163 isl_map_free(map2);
1164 return -1;
1166 if (empty) {
1167 isl_map_free(map2);
1168 return 0;
1171 data->res = isl_union_map_add_map(data->res, map2);
1173 return 0;
1176 static int bin_entry(void **entry, void *user)
1178 struct isl_union_map_bin_data *data = user;
1179 isl_map *map = *entry;
1181 data->map = map;
1182 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1183 data->fn, data) < 0)
1184 return -1;
1186 return 0;
1189 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1190 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1192 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1194 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1195 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1197 if (!umap1 || !umap2)
1198 goto error;
1200 data.umap2 = umap2;
1201 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1202 umap1->table.n);
1203 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1204 &bin_entry, &data) < 0)
1205 goto error;
1207 isl_union_map_free(umap1);
1208 isl_union_map_free(umap2);
1209 return data.res;
1210 error:
1211 isl_union_map_free(umap1);
1212 isl_union_map_free(umap2);
1213 isl_union_map_free(data.res);
1214 return NULL;
1217 __isl_give isl_union_map *isl_union_map_apply_range(
1218 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1220 return bin_op(umap1, umap2, &apply_range_entry);
1223 __isl_give isl_union_map *isl_union_map_apply_domain(
1224 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1226 umap1 = isl_union_map_reverse(umap1);
1227 umap1 = isl_union_map_apply_range(umap1, umap2);
1228 return isl_union_map_reverse(umap1);
1231 __isl_give isl_union_set *isl_union_set_apply(
1232 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1234 return isl_union_map_apply_range(uset, umap);
1237 static int map_lex_lt_entry(void **entry, void *user)
1239 struct isl_union_map_bin_data *data = user;
1240 isl_map *map2 = *entry;
1242 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1243 map2->dim, isl_dim_out))
1244 return 0;
1246 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1248 data->res = isl_union_map_add_map(data->res, map2);
1250 return 0;
1253 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1254 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1256 return bin_op(umap1, umap2, &map_lex_lt_entry);
1259 static int map_lex_le_entry(void **entry, void *user)
1261 struct isl_union_map_bin_data *data = user;
1262 isl_map *map2 = *entry;
1264 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1265 map2->dim, isl_dim_out))
1266 return 0;
1268 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1270 data->res = isl_union_map_add_map(data->res, map2);
1272 return 0;
1275 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1276 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1278 return bin_op(umap1, umap2, &map_lex_le_entry);
1281 static int product_entry(void **entry, void *user)
1283 struct isl_union_map_bin_data *data = user;
1284 isl_map *map2 = *entry;
1286 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1288 data->res = isl_union_map_add_map(data->res, map2);
1290 return 0;
1293 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1294 __isl_take isl_union_map *umap2)
1296 return bin_op(umap1, umap2, &product_entry);
1299 static int set_product_entry(void **entry, void *user)
1301 struct isl_union_map_bin_data *data = user;
1302 isl_set *set2 = *entry;
1304 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1306 data->res = isl_union_set_add_set(data->res, set2);
1308 return 0;
1311 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1312 __isl_take isl_union_set *uset2)
1314 return bin_op(uset1, uset2, &set_product_entry);
1317 static int domain_product_entry(void **entry, void *user)
1319 struct isl_union_map_bin_data *data = user;
1320 isl_map *map2 = *entry;
1322 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1323 map2->dim, isl_dim_out))
1324 return 0;
1326 map2 = isl_map_domain_product(isl_map_copy(data->map),
1327 isl_map_copy(map2));
1329 data->res = isl_union_map_add_map(data->res, map2);
1331 return 0;
1334 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1336 __isl_give isl_union_map *isl_union_map_domain_product(
1337 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1339 return bin_op(umap1, umap2, &domain_product_entry);
1342 static int range_product_entry(void **entry, void *user)
1344 struct isl_union_map_bin_data *data = user;
1345 isl_map *map2 = *entry;
1347 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1348 map2->dim, isl_dim_in))
1349 return 0;
1351 map2 = isl_map_range_product(isl_map_copy(data->map),
1352 isl_map_copy(map2));
1354 data->res = isl_union_map_add_map(data->res, map2);
1356 return 0;
1359 __isl_give isl_union_map *isl_union_map_range_product(
1360 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1362 return bin_op(umap1, umap2, &range_product_entry);
1365 static int flat_range_product_entry(void **entry, void *user)
1367 struct isl_union_map_bin_data *data = user;
1368 isl_map *map2 = *entry;
1370 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1371 map2->dim, isl_dim_in))
1372 return 0;
1374 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1375 isl_map_copy(map2));
1377 data->res = isl_union_map_add_map(data->res, map2);
1379 return 0;
1382 __isl_give isl_union_map *isl_union_map_flat_range_product(
1383 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1385 return bin_op(umap1, umap2, &flat_range_product_entry);
1388 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1389 int (*fn)(void **, void *))
1391 isl_union_set *res;
1393 if (!umap)
1394 return NULL;
1396 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1397 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1398 goto error;
1400 isl_union_map_free(umap);
1401 return res;
1402 error:
1403 isl_union_map_free(umap);
1404 isl_union_set_free(res);
1405 return NULL;
1408 static int from_range_entry(void **entry, void *user)
1410 isl_map *set = *entry;
1411 isl_union_set **res = user;
1413 *res = isl_union_map_add_map(*res,
1414 isl_map_from_range(isl_set_copy(set)));
1416 return 0;
1419 __isl_give isl_union_map *isl_union_map_from_range(
1420 __isl_take isl_union_set *uset)
1422 return cond_un_op(uset, &from_range_entry);
1425 __isl_give isl_union_map *isl_union_map_from_domain(
1426 __isl_take isl_union_set *uset)
1428 return isl_union_map_reverse(isl_union_map_from_range(uset));
1431 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1432 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1434 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1435 isl_union_map_from_range(range));
1438 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1439 int (*fn)(void **, void *))
1441 umap = isl_union_map_cow(umap);
1442 if (!umap)
1443 return NULL;
1445 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1446 goto error;
1448 return umap;
1449 error:
1450 isl_union_map_free(umap);
1451 return NULL;
1454 static int affine_entry(void **entry, void *user)
1456 isl_map **map = (isl_map **)entry;
1458 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1460 return *map ? 0 : -1;
1463 __isl_give isl_union_map *isl_union_map_affine_hull(
1464 __isl_take isl_union_map *umap)
1466 return un_op(umap, &affine_entry);
1469 __isl_give isl_union_set *isl_union_set_affine_hull(
1470 __isl_take isl_union_set *uset)
1472 return isl_union_map_affine_hull(uset);
1475 static int polyhedral_entry(void **entry, void *user)
1477 isl_map **map = (isl_map **)entry;
1479 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1481 return *map ? 0 : -1;
1484 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1485 __isl_take isl_union_map *umap)
1487 return un_op(umap, &polyhedral_entry);
1490 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1491 __isl_take isl_union_set *uset)
1493 return isl_union_map_polyhedral_hull(uset);
1496 static int simple_entry(void **entry, void *user)
1498 isl_map **map = (isl_map **)entry;
1500 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1502 return *map ? 0 : -1;
1505 __isl_give isl_union_map *isl_union_map_simple_hull(
1506 __isl_take isl_union_map *umap)
1508 return un_op(umap, &simple_entry);
1511 __isl_give isl_union_set *isl_union_set_simple_hull(
1512 __isl_take isl_union_set *uset)
1514 return isl_union_map_simple_hull(uset);
1517 static int inplace_entry(void **entry, void *user)
1519 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1520 isl_map **map = (isl_map **)entry;
1521 isl_map *copy;
1523 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1524 copy = fn(isl_map_copy(*map));
1525 if (!copy)
1526 return -1;
1528 isl_map_free(*map);
1529 *map = copy;
1531 return 0;
1534 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1535 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1537 if (!umap)
1538 return NULL;
1540 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1541 &inplace_entry, &fn) < 0)
1542 goto error;
1544 return umap;
1545 error:
1546 isl_union_map_free(umap);
1547 return NULL;
1550 __isl_give isl_union_map *isl_union_map_coalesce(
1551 __isl_take isl_union_map *umap)
1553 return inplace(umap, &isl_map_coalesce);
1556 __isl_give isl_union_set *isl_union_set_coalesce(
1557 __isl_take isl_union_set *uset)
1559 return isl_union_map_coalesce(uset);
1562 __isl_give isl_union_map *isl_union_map_detect_equalities(
1563 __isl_take isl_union_map *umap)
1565 return inplace(umap, &isl_map_detect_equalities);
1568 __isl_give isl_union_set *isl_union_set_detect_equalities(
1569 __isl_take isl_union_set *uset)
1571 return isl_union_map_detect_equalities(uset);
1574 __isl_give isl_union_map *isl_union_map_compute_divs(
1575 __isl_take isl_union_map *umap)
1577 return inplace(umap, &isl_map_compute_divs);
1580 __isl_give isl_union_set *isl_union_set_compute_divs(
1581 __isl_take isl_union_set *uset)
1583 return isl_union_map_compute_divs(uset);
1586 static int lexmin_entry(void **entry, void *user)
1588 isl_map **map = (isl_map **)entry;
1590 *map = isl_map_lexmin(*map);
1592 return *map ? 0 : -1;
1595 __isl_give isl_union_map *isl_union_map_lexmin(
1596 __isl_take isl_union_map *umap)
1598 return un_op(umap, &lexmin_entry);
1601 __isl_give isl_union_set *isl_union_set_lexmin(
1602 __isl_take isl_union_set *uset)
1604 return isl_union_map_lexmin(uset);
1607 static int lexmax_entry(void **entry, void *user)
1609 isl_map **map = (isl_map **)entry;
1611 *map = isl_map_lexmax(*map);
1613 return *map ? 0 : -1;
1616 __isl_give isl_union_map *isl_union_map_lexmax(
1617 __isl_take isl_union_map *umap)
1619 return un_op(umap, &lexmax_entry);
1622 __isl_give isl_union_set *isl_union_set_lexmax(
1623 __isl_take isl_union_set *uset)
1625 return isl_union_map_lexmax(uset);
1628 static int universe_entry(void **entry, void *user)
1630 isl_map *map = *entry;
1631 isl_union_map **res = user;
1633 map = isl_map_universe(isl_map_get_space(map));
1634 *res = isl_union_map_add_map(*res, map);
1636 return 0;
1639 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1641 return cond_un_op(umap, &universe_entry);
1644 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1646 return isl_union_map_universe(uset);
1649 static int reverse_entry(void **entry, void *user)
1651 isl_map *map = *entry;
1652 isl_union_map **res = user;
1654 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1656 return 0;
1659 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1661 return cond_un_op(umap, &reverse_entry);
1664 static int params_entry(void **entry, void *user)
1666 isl_map *map = *entry;
1667 isl_union_set **res = user;
1669 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1671 return 0;
1674 /* Compute the parameter domain of the given union map.
1676 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1678 int empty;
1680 empty = isl_union_map_is_empty(umap);
1681 if (empty < 0)
1682 return isl_union_map_free(umap);
1683 if (empty)
1684 return isl_set_empty(isl_union_map_get_space(umap));
1685 return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1688 /* Compute the parameter domain of the given union set.
1690 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1692 return isl_union_map_params(uset);
1695 static int domain_entry(void **entry, void *user)
1697 isl_map *map = *entry;
1698 isl_union_set **res = user;
1700 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1702 return 0;
1705 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1707 return cond_un_op(umap, &domain_entry);
1710 static int range_entry(void **entry, void *user)
1712 isl_map *map = *entry;
1713 isl_union_set **res = user;
1715 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1717 return 0;
1720 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1722 return cond_un_op(umap, &range_entry);
1725 static int domain_map_entry(void **entry, void *user)
1727 isl_map *map = *entry;
1728 isl_union_set **res = user;
1730 *res = isl_union_map_add_map(*res,
1731 isl_map_domain_map(isl_map_copy(map)));
1733 return 0;
1736 __isl_give isl_union_map *isl_union_map_domain_map(
1737 __isl_take isl_union_map *umap)
1739 return cond_un_op(umap, &domain_map_entry);
1742 static int range_map_entry(void **entry, void *user)
1744 isl_map *map = *entry;
1745 isl_union_set **res = user;
1747 *res = isl_union_map_add_map(*res,
1748 isl_map_range_map(isl_map_copy(map)));
1750 return 0;
1753 __isl_give isl_union_map *isl_union_map_range_map(
1754 __isl_take isl_union_map *umap)
1756 return cond_un_op(umap, &range_map_entry);
1759 static int deltas_entry(void **entry, void *user)
1761 isl_map *map = *entry;
1762 isl_union_set **res = user;
1764 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1765 return 0;
1767 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1769 return 0;
1772 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1774 return cond_un_op(umap, &deltas_entry);
1777 static int deltas_map_entry(void **entry, void *user)
1779 isl_map *map = *entry;
1780 isl_union_map **res = user;
1782 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1783 return 0;
1785 *res = isl_union_map_add_map(*res,
1786 isl_map_deltas_map(isl_map_copy(map)));
1788 return 0;
1791 __isl_give isl_union_map *isl_union_map_deltas_map(
1792 __isl_take isl_union_map *umap)
1794 return cond_un_op(umap, &deltas_map_entry);
1797 static int identity_entry(void **entry, void *user)
1799 isl_set *set = *entry;
1800 isl_union_map **res = user;
1802 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1804 return 0;
1807 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1809 return cond_un_op(uset, &identity_entry);
1812 static int unwrap_entry(void **entry, void *user)
1814 isl_set *set = *entry;
1815 isl_union_set **res = user;
1817 if (!isl_set_is_wrapping(set))
1818 return 0;
1820 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1822 return 0;
1825 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1827 return cond_un_op(uset, &unwrap_entry);
1830 static int wrap_entry(void **entry, void *user)
1832 isl_map *map = *entry;
1833 isl_union_set **res = user;
1835 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1837 return 0;
1840 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1842 return cond_un_op(umap, &wrap_entry);
1845 struct isl_union_map_is_subset_data {
1846 isl_union_map *umap2;
1847 int is_subset;
1850 static int is_subset_entry(void **entry, void *user)
1852 struct isl_union_map_is_subset_data *data = user;
1853 uint32_t hash;
1854 struct isl_hash_table_entry *entry2;
1855 isl_map *map = *entry;
1857 hash = isl_space_get_hash(map->dim);
1858 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1859 hash, &has_dim, map->dim, 0);
1860 if (!entry2) {
1861 int empty = isl_map_is_empty(map);
1862 if (empty < 0)
1863 return -1;
1864 if (empty)
1865 return 0;
1866 data->is_subset = 0;
1867 return -1;
1870 data->is_subset = isl_map_is_subset(map, entry2->data);
1871 if (data->is_subset < 0 || !data->is_subset)
1872 return -1;
1874 return 0;
1877 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1878 __isl_keep isl_union_map *umap2)
1880 struct isl_union_map_is_subset_data data = { NULL, 1 };
1882 umap1 = isl_union_map_copy(umap1);
1883 umap2 = isl_union_map_copy(umap2);
1884 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1885 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1887 if (!umap1 || !umap2)
1888 goto error;
1890 data.umap2 = umap2;
1891 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1892 &is_subset_entry, &data) < 0 &&
1893 data.is_subset)
1894 goto error;
1896 isl_union_map_free(umap1);
1897 isl_union_map_free(umap2);
1899 return data.is_subset;
1900 error:
1901 isl_union_map_free(umap1);
1902 isl_union_map_free(umap2);
1903 return -1;
1906 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1907 __isl_keep isl_union_set *uset2)
1909 return isl_union_map_is_subset(uset1, uset2);
1912 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1913 __isl_keep isl_union_map *umap2)
1915 int is_subset;
1917 if (!umap1 || !umap2)
1918 return -1;
1919 is_subset = isl_union_map_is_subset(umap1, umap2);
1920 if (is_subset != 1)
1921 return is_subset;
1922 is_subset = isl_union_map_is_subset(umap2, umap1);
1923 return is_subset;
1926 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1927 __isl_keep isl_union_set *uset2)
1929 return isl_union_map_is_equal(uset1, uset2);
1932 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1933 __isl_keep isl_union_map *umap2)
1935 int is_subset;
1937 if (!umap1 || !umap2)
1938 return -1;
1939 is_subset = isl_union_map_is_subset(umap1, umap2);
1940 if (is_subset != 1)
1941 return is_subset;
1942 is_subset = isl_union_map_is_subset(umap2, umap1);
1943 if (is_subset == -1)
1944 return is_subset;
1945 return !is_subset;
1948 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1949 __isl_keep isl_union_set *uset2)
1951 return isl_union_map_is_strict_subset(uset1, uset2);
1954 static int sample_entry(void **entry, void *user)
1956 isl_basic_map **sample = (isl_basic_map **)user;
1957 isl_map *map = *entry;
1959 *sample = isl_map_sample(isl_map_copy(map));
1960 if (!*sample)
1961 return -1;
1962 if (!isl_basic_map_plain_is_empty(*sample))
1963 return -1;
1964 return 0;
1967 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1969 isl_basic_map *sample = NULL;
1971 if (!umap)
1972 return NULL;
1974 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1975 &sample_entry, &sample) < 0 &&
1976 !sample)
1977 goto error;
1979 if (!sample)
1980 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1982 isl_union_map_free(umap);
1984 return sample;
1985 error:
1986 isl_union_map_free(umap);
1987 return NULL;
1990 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1992 return (isl_basic_set *)isl_union_map_sample(uset);
1995 struct isl_forall_data {
1996 int res;
1997 int (*fn)(__isl_keep isl_map *map);
2000 static int forall_entry(void **entry, void *user)
2002 struct isl_forall_data *data = user;
2003 isl_map *map = *entry;
2005 data->res = data->fn(map);
2006 if (data->res < 0)
2007 return -1;
2009 if (!data->res)
2010 return -1;
2012 return 0;
2015 static int union_map_forall(__isl_keep isl_union_map *umap,
2016 int (*fn)(__isl_keep isl_map *map))
2018 struct isl_forall_data data = { 1, fn };
2020 if (!umap)
2021 return -1;
2023 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2024 &forall_entry, &data) < 0 && data.res)
2025 return -1;
2027 return data.res;
2030 struct isl_forall_user_data {
2031 int res;
2032 int (*fn)(__isl_keep isl_map *map, void *user);
2033 void *user;
2036 static int forall_user_entry(void **entry, void *user)
2038 struct isl_forall_user_data *data = user;
2039 isl_map *map = *entry;
2041 data->res = data->fn(map, data->user);
2042 if (data->res < 0)
2043 return -1;
2045 if (!data->res)
2046 return -1;
2048 return 0;
2051 /* Check if fn(map, user) returns true for all maps "map" in umap.
2053 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2054 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2056 struct isl_forall_user_data data = { 1, fn, user };
2058 if (!umap)
2059 return -1;
2061 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2062 &forall_user_entry, &data) < 0 && data.res)
2063 return -1;
2065 return data.res;
2068 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2070 return union_map_forall(umap, &isl_map_is_empty);
2073 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2075 return isl_union_map_is_empty(uset);
2078 static int is_subset_of_identity(__isl_keep isl_map *map)
2080 int is_subset;
2081 isl_space *dim;
2082 isl_map *id;
2084 if (!map)
2085 return -1;
2087 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2088 return 0;
2090 dim = isl_map_get_space(map);
2091 id = isl_map_identity(dim);
2093 is_subset = isl_map_is_subset(map, id);
2095 isl_map_free(id);
2097 return is_subset;
2100 /* Check if the given map is single-valued.
2101 * We simply compute
2103 * M \circ M^-1
2105 * and check if the result is a subset of the identity mapping.
2107 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2109 isl_union_map *test;
2110 int sv;
2112 if (isl_union_map_n_map(umap) == 1) {
2113 isl_map *map;
2114 umap = isl_union_map_copy(umap);
2115 map = isl_map_from_union_map(umap);
2116 sv = isl_map_is_single_valued(map);
2117 isl_map_free(map);
2118 return sv;
2121 test = isl_union_map_reverse(isl_union_map_copy(umap));
2122 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2124 sv = union_map_forall(test, &is_subset_of_identity);
2126 isl_union_map_free(test);
2128 return sv;
2131 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2133 int in;
2135 umap = isl_union_map_copy(umap);
2136 umap = isl_union_map_reverse(umap);
2137 in = isl_union_map_is_single_valued(umap);
2138 isl_union_map_free(umap);
2140 return in;
2143 /* Represents a map that has a fixed value (v) for one of its
2144 * range dimensions.
2145 * The map in this structure is not reference counted, so it
2146 * is only valid while the isl_union_map from which it was
2147 * obtained is still alive.
2149 struct isl_fixed_map {
2150 isl_int v;
2151 isl_map *map;
2154 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2155 int n)
2157 int i;
2158 struct isl_fixed_map *v;
2160 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2161 if (!v)
2162 return NULL;
2163 for (i = 0; i < n; ++i)
2164 isl_int_init(v[i].v);
2165 return v;
2168 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2170 int i;
2172 if (!v)
2173 return;
2174 for (i = 0; i < n; ++i)
2175 isl_int_clear(v[i].v);
2176 free(v);
2179 /* Compare the "v" field of two isl_fixed_map structs.
2181 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2183 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2184 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2186 return isl_int_cmp(e1->v, e2->v);
2189 /* Internal data structure used while checking whether all maps
2190 * in a union_map have a fixed value for a given output dimension.
2191 * v is the list of maps, with the fixed value for the dimension
2192 * n is the number of maps considered so far
2193 * pos is the output dimension under investigation
2195 struct isl_fixed_dim_data {
2196 struct isl_fixed_map *v;
2197 int n;
2198 int pos;
2201 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2203 struct isl_fixed_dim_data *data = user;
2205 data->v[data->n].map = map;
2206 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2207 &data->v[data->n++].v);
2210 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2211 int first, int n_range);
2213 /* Given a list of the maps, with their fixed values at output dimension "pos",
2214 * check whether the ranges of the maps form an obvious partition.
2216 * We first sort the maps according to their fixed values.
2217 * If all maps have a different value, then we know the ranges form
2218 * a partition.
2219 * Otherwise, we collect the maps with the same fixed value and
2220 * check whether each such collection is obviously injective
2221 * based on later dimensions.
2223 static int separates(struct isl_fixed_map *v, int n,
2224 __isl_take isl_space *dim, int pos, int n_range)
2226 int i;
2228 if (!v)
2229 goto error;
2231 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2233 for (i = 0; i + 1 < n; ++i) {
2234 int j, k;
2235 isl_union_map *part;
2236 int injective;
2238 for (j = i + 1; j < n; ++j)
2239 if (isl_int_ne(v[i].v, v[j].v))
2240 break;
2242 if (j == i + 1)
2243 continue;
2245 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2246 for (k = i; k < j; ++k)
2247 part = isl_union_map_add_map(part,
2248 isl_map_copy(v[k].map));
2250 injective = plain_injective_on_range(part, pos + 1, n_range);
2251 if (injective < 0)
2252 goto error;
2253 if (!injective)
2254 break;
2256 i = j - 1;
2259 isl_space_free(dim);
2260 free_isl_fixed_map_array(v, n);
2261 return i + 1 >= n;
2262 error:
2263 isl_space_free(dim);
2264 free_isl_fixed_map_array(v, n);
2265 return -1;
2268 /* Check whether the maps in umap have obviously distinct ranges.
2269 * In particular, check for an output dimension in the range
2270 * [first,n_range) for which all maps have a fixed value
2271 * and then check if these values, possibly along with fixed values
2272 * at later dimensions, entail distinct ranges.
2274 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2275 int first, int n_range)
2277 isl_ctx *ctx;
2278 int n;
2279 struct isl_fixed_dim_data data = { NULL };
2281 ctx = isl_union_map_get_ctx(umap);
2283 n = isl_union_map_n_map(umap);
2284 if (!umap)
2285 goto error;
2287 if (n <= 1) {
2288 isl_union_map_free(umap);
2289 return 1;
2292 if (first >= n_range) {
2293 isl_union_map_free(umap);
2294 return 0;
2297 data.v = alloc_isl_fixed_map_array(ctx, n);
2298 if (!data.v)
2299 goto error;
2301 for (data.pos = first; data.pos < n_range; ++data.pos) {
2302 int fixed;
2303 int injective;
2304 isl_space *dim;
2306 data.n = 0;
2307 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2308 if (fixed < 0)
2309 goto error;
2310 if (!fixed)
2311 continue;
2312 dim = isl_union_map_get_space(umap);
2313 injective = separates(data.v, n, dim, data.pos, n_range);
2314 isl_union_map_free(umap);
2315 return injective;
2318 free_isl_fixed_map_array(data.v, n);
2319 isl_union_map_free(umap);
2321 return 0;
2322 error:
2323 free_isl_fixed_map_array(data.v, n);
2324 isl_union_map_free(umap);
2325 return -1;
2328 /* Check whether the maps in umap that map to subsets of "ran"
2329 * have obviously distinct ranges.
2331 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2333 isl_union_map *umap = user;
2335 umap = isl_union_map_copy(umap);
2336 umap = isl_union_map_intersect_range(umap,
2337 isl_union_set_from_set(isl_set_copy(ran)));
2338 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2341 /* Check if the given union_map is obviously injective.
2343 * In particular, we first check if all individual maps are obviously
2344 * injective and then check if all the ranges of these maps are
2345 * obviously disjoint.
2347 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2349 int in;
2350 isl_union_map *univ;
2351 isl_union_set *ran;
2353 in = union_map_forall(umap, &isl_map_plain_is_injective);
2354 if (in < 0)
2355 return -1;
2356 if (!in)
2357 return 0;
2359 univ = isl_union_map_universe(isl_union_map_copy(umap));
2360 ran = isl_union_map_range(univ);
2362 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2364 isl_union_set_free(ran);
2366 return in;
2369 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2371 int sv;
2373 sv = isl_union_map_is_single_valued(umap);
2374 if (sv < 0 || !sv)
2375 return sv;
2377 return isl_union_map_is_injective(umap);
2380 static int zip_entry(void **entry, void *user)
2382 isl_map *map = *entry;
2383 isl_union_map **res = user;
2385 if (!isl_map_can_zip(map))
2386 return 0;
2388 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2390 return 0;
2393 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2395 return cond_un_op(umap, &zip_entry);
2398 static int uncurry_entry(void **entry, void *user)
2400 isl_map *map = *entry;
2401 isl_union_map **res = user;
2403 if (!isl_map_can_uncurry(map))
2404 return 0;
2406 *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2408 return 0;
2411 /* Given a union map, take the maps of the form A -> (B -> C) and
2412 * return the union of the corresponding maps (A -> B) -> C.
2414 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2416 return cond_un_op(umap, &uncurry_entry);
2419 static int curry_entry(void **entry, void *user)
2421 isl_map *map = *entry;
2422 isl_union_map **res = user;
2424 if (!isl_map_can_curry(map))
2425 return 0;
2427 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2429 return 0;
2432 /* Given a union map, take the maps of the form (A -> B) -> C and
2433 * return the union of the corresponding maps A -> (B -> C).
2435 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2437 return cond_un_op(umap, &curry_entry);
2440 static int lift_entry(void **entry, void *user)
2442 isl_set *set = *entry;
2443 isl_union_set **res = user;
2445 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2447 return 0;
2450 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2452 return cond_un_op(uset, &lift_entry);
2455 static int coefficients_entry(void **entry, void *user)
2457 isl_set *set = *entry;
2458 isl_union_set **res = user;
2460 set = isl_set_copy(set);
2461 set = isl_set_from_basic_set(isl_set_coefficients(set));
2462 *res = isl_union_set_add_set(*res, set);
2464 return 0;
2467 __isl_give isl_union_set *isl_union_set_coefficients(
2468 __isl_take isl_union_set *uset)
2470 isl_ctx *ctx;
2471 isl_space *dim;
2472 isl_union_set *res;
2474 if (!uset)
2475 return NULL;
2477 ctx = isl_union_set_get_ctx(uset);
2478 dim = isl_space_set_alloc(ctx, 0, 0);
2479 res = isl_union_map_alloc(dim, uset->table.n);
2480 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2481 &coefficients_entry, &res) < 0)
2482 goto error;
2484 isl_union_set_free(uset);
2485 return res;
2486 error:
2487 isl_union_set_free(uset);
2488 isl_union_set_free(res);
2489 return NULL;
2492 static int solutions_entry(void **entry, void *user)
2494 isl_set *set = *entry;
2495 isl_union_set **res = user;
2497 set = isl_set_copy(set);
2498 set = isl_set_from_basic_set(isl_set_solutions(set));
2499 if (!*res)
2500 *res = isl_union_set_from_set(set);
2501 else
2502 *res = isl_union_set_add_set(*res, set);
2504 if (!*res)
2505 return -1;
2507 return 0;
2510 __isl_give isl_union_set *isl_union_set_solutions(
2511 __isl_take isl_union_set *uset)
2513 isl_union_set *res = NULL;
2515 if (!uset)
2516 return NULL;
2518 if (uset->table.n == 0) {
2519 res = isl_union_set_empty(isl_union_set_get_space(uset));
2520 isl_union_set_free(uset);
2521 return res;
2524 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2525 &solutions_entry, &res) < 0)
2526 goto error;
2528 isl_union_set_free(uset);
2529 return res;
2530 error:
2531 isl_union_set_free(uset);
2532 isl_union_set_free(res);
2533 return NULL;