isl_union_set_compute_schedule: components may also involve proximity edges
[isl.git] / isl_union_map.c
blobb1d0096f87b198091c7a0b279ec3630bc0128b7c
1 /*
2 * Copyright 2010-2011 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 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 if (!dim)
45 return NULL;
47 umap = isl_calloc_type(dim->ctx, isl_union_map);
48 if (!umap)
49 return NULL;
51 umap->ref = 1;
52 umap->dim = dim;
53 if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
54 goto error;
56 return umap;
57 error:
58 isl_space_free(dim);
59 isl_union_map_free(umap);
60 return NULL;
63 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
65 return isl_union_map_alloc(dim, 16);
68 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
70 return isl_union_map_empty(dim);
73 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
75 return umap ? umap->dim->ctx : NULL;
78 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
80 return uset ? uset->dim->ctx : NULL;
83 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
85 if (!umap)
86 return NULL;
87 return isl_space_copy(umap->dim);
90 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
92 return isl_union_map_get_space(uset);
95 static int free_umap_entry(void **entry, void *user)
97 isl_map *map = *entry;
98 isl_map_free(map);
99 return 0;
102 static int add_map(__isl_take isl_map *map, void *user)
104 isl_union_map **umap = (isl_union_map **)user;
106 *umap = isl_union_map_add_map(*umap, map);
108 return 0;
111 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
113 isl_union_map *dup;
115 if (!umap)
116 return NULL;
118 dup = isl_union_map_empty(isl_space_copy(umap->dim));
119 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
120 goto error;
121 return dup;
122 error:
123 isl_union_map_free(dup);
124 return NULL;
127 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
129 if (!umap)
130 return NULL;
132 if (umap->ref == 1)
133 return umap;
134 umap->ref--;
135 return isl_union_map_dup(umap);
138 struct isl_union_align {
139 isl_reordering *exp;
140 isl_union_map *res;
143 static int align_entry(void **entry, void *user)
145 isl_map *map = *entry;
146 isl_reordering *exp;
147 struct isl_union_align *data = user;
149 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
150 isl_map_get_space(map));
152 data->res = isl_union_map_add_map(data->res,
153 isl_map_realign(isl_map_copy(map), exp));
155 return 0;
158 /* Align the parameters of umap along those of model.
159 * The result has the parameters of model first, in the same order
160 * as they appear in model, followed by any remaining parameters of
161 * umap that do not appear in model.
163 __isl_give isl_union_map *isl_union_map_align_params(
164 __isl_take isl_union_map *umap, __isl_take isl_space *model)
166 struct isl_union_align data = { NULL, NULL };
168 if (!umap || !model)
169 goto error;
171 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
172 isl_space_free(model);
173 return umap;
176 model = isl_space_params(model);
177 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
178 if (!data.exp)
179 goto error;
181 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
182 umap->table.n);
183 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
184 &align_entry, &data) < 0)
185 goto error;
187 isl_reordering_free(data.exp);
188 isl_union_map_free(umap);
189 isl_space_free(model);
190 return data.res;
191 error:
192 isl_reordering_free(data.exp);
193 isl_union_map_free(umap);
194 isl_union_map_free(data.res);
195 isl_space_free(model);
196 return NULL;
199 __isl_give isl_union_set *isl_union_set_align_params(
200 __isl_take isl_union_set *uset, __isl_take isl_space *model)
202 return isl_union_map_align_params(uset, model);
205 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
206 __isl_take isl_union_map *umap2)
208 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
209 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
211 umap1 = isl_union_map_cow(umap1);
213 if (!umap1 || !umap2)
214 goto error;
216 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
217 goto error;
219 isl_union_map_free(umap2);
221 return umap1;
222 error:
223 isl_union_map_free(umap1);
224 isl_union_map_free(umap2);
225 return NULL;
228 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
229 __isl_take isl_union_set *uset2)
231 return isl_union_map_union(uset1, uset2);
234 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
236 if (!umap)
237 return NULL;
239 umap->ref++;
240 return umap;
243 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
245 return isl_union_map_copy(uset);
248 void *isl_union_map_free(__isl_take isl_union_map *umap)
250 if (!umap)
251 return NULL;
253 if (--umap->ref > 0)
254 return NULL;
256 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
257 &free_umap_entry, NULL);
258 isl_hash_table_clear(&umap->table);
259 isl_space_free(umap->dim);
260 free(umap);
261 return NULL;
264 void *isl_union_set_free(__isl_take isl_union_set *uset)
266 return isl_union_map_free(uset);
269 static int has_dim(const void *entry, const void *val)
271 isl_map *map = (isl_map *)entry;
272 isl_space *dim = (isl_space *)val;
274 return isl_space_is_equal(map->dim, dim);
277 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
278 __isl_take isl_map *map)
280 uint32_t hash;
281 struct isl_hash_table_entry *entry;
283 if (!map || !umap)
284 goto error;
286 if (isl_map_plain_is_empty(map)) {
287 isl_map_free(map);
288 return umap;
291 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
292 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
293 map = isl_map_align_params(map, isl_union_map_get_space(umap));
296 umap = isl_union_map_cow(umap);
298 if (!map || !umap)
299 goto error;
301 hash = isl_space_get_hash(map->dim);
302 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
303 &has_dim, map->dim, 1);
304 if (!entry)
305 goto error;
307 if (!entry->data)
308 entry->data = map;
309 else {
310 entry->data = isl_map_union(entry->data, isl_map_copy(map));
311 if (!entry->data)
312 goto error;
313 isl_map_free(map);
316 return umap;
317 error:
318 isl_map_free(map);
319 isl_union_map_free(umap);
320 return NULL;
323 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
324 __isl_take isl_set *set)
326 return isl_union_map_add_map(uset, (isl_map *)set);
329 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
331 isl_space *dim;
332 isl_union_map *umap;
334 if (!map)
335 return NULL;
337 dim = isl_map_get_space(map);
338 dim = isl_space_params(dim);
339 umap = isl_union_map_empty(dim);
340 umap = isl_union_map_add_map(umap, map);
342 return umap;
345 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
347 return isl_union_map_from_map((isl_map *)set);
350 struct isl_union_map_foreach_data
352 int (*fn)(__isl_take isl_map *map, void *user);
353 void *user;
356 static int call_on_copy(void **entry, void *user)
358 isl_map *map = *entry;
359 struct isl_union_map_foreach_data *data;
360 data = (struct isl_union_map_foreach_data *)user;
362 return data->fn(isl_map_copy(map), data->user);
365 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
367 return umap ? umap->table.n : 0;
370 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
372 return uset ? uset->table.n : 0;
375 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
376 int (*fn)(__isl_take isl_map *map, void *user), void *user)
378 struct isl_union_map_foreach_data data = { fn, user };
380 if (!umap)
381 return -1;
383 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
384 &call_on_copy, &data);
387 static int copy_map(void **entry, void *user)
389 isl_map *map = *entry;
390 isl_map **map_p = user;
392 *map_p = isl_map_copy(map);
394 return -1;
397 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
399 isl_ctx *ctx;
400 isl_map *map = NULL;
402 if (!umap)
403 return NULL;
404 ctx = isl_union_map_get_ctx(umap);
405 if (umap->table.n != 1)
406 isl_die(ctx, isl_error_invalid,
407 "union map needs to contain elements in exactly "
408 "one space", return isl_union_map_free(umap));
410 isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
412 isl_union_map_free(umap);
414 return map;
417 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
419 return isl_map_from_union_map(uset);
422 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
423 __isl_take isl_space *dim)
425 uint32_t hash;
426 struct isl_hash_table_entry *entry;
428 if (!umap || !dim)
429 goto error;
431 hash = isl_space_get_hash(dim);
432 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
433 &has_dim, dim, 0);
434 if (!entry)
435 return isl_map_empty(dim);
436 isl_space_free(dim);
437 return isl_map_copy(entry->data);
438 error:
439 isl_space_free(dim);
440 return NULL;
443 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
444 __isl_take isl_space *dim)
446 return (isl_set *)isl_union_map_extract_map(uset, dim);
449 /* Check if umap contains a map in the given space.
451 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
452 __isl_keep isl_space *dim)
454 uint32_t hash;
455 struct isl_hash_table_entry *entry;
457 if (!umap || !dim)
458 return -1;
460 hash = isl_space_get_hash(dim);
461 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
462 &has_dim, dim, 0);
463 return !!entry;
466 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
467 __isl_keep isl_space *dim)
469 return isl_union_map_contains(uset, dim);
472 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
473 int (*fn)(__isl_take isl_set *set, void *user), void *user)
475 return isl_union_map_foreach_map(uset,
476 (int(*)(__isl_take isl_map *, void*))fn, user);
479 struct isl_union_set_foreach_point_data {
480 int (*fn)(__isl_take isl_point *pnt, void *user);
481 void *user;
484 static int foreach_point(__isl_take isl_set *set, void *user)
486 struct isl_union_set_foreach_point_data *data = user;
487 int r;
489 r = isl_set_foreach_point(set, data->fn, data->user);
490 isl_set_free(set);
492 return r;
495 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
496 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
498 struct isl_union_set_foreach_point_data data = { fn, user };
499 return isl_union_set_foreach_set(uset, &foreach_point, &data);
502 struct isl_union_map_gen_bin_data {
503 isl_union_map *umap2;
504 isl_union_map *res;
507 static int subtract_entry(void **entry, void *user)
509 struct isl_union_map_gen_bin_data *data = user;
510 uint32_t hash;
511 struct isl_hash_table_entry *entry2;
512 isl_map *map = *entry;
514 hash = isl_space_get_hash(map->dim);
515 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
516 hash, &has_dim, map->dim, 0);
517 map = isl_map_copy(map);
518 if (entry2) {
519 int empty;
520 map = isl_map_subtract(map, isl_map_copy(entry2->data));
522 empty = isl_map_is_empty(map);
523 if (empty < 0) {
524 isl_map_free(map);
525 return -1;
527 if (empty) {
528 isl_map_free(map);
529 return 0;
532 data->res = isl_union_map_add_map(data->res, map);
534 return 0;
537 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
538 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
540 struct isl_union_map_gen_bin_data data = { NULL, NULL };
542 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
543 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
545 if (!umap1 || !umap2)
546 goto error;
548 data.umap2 = umap2;
549 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
550 umap1->table.n);
551 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
552 fn, &data) < 0)
553 goto error;
555 isl_union_map_free(umap1);
556 isl_union_map_free(umap2);
557 return data.res;
558 error:
559 isl_union_map_free(umap1);
560 isl_union_map_free(umap2);
561 isl_union_map_free(data.res);
562 return NULL;
565 __isl_give isl_union_map *isl_union_map_subtract(
566 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
568 return gen_bin_op(umap1, umap2, &subtract_entry);
571 __isl_give isl_union_set *isl_union_set_subtract(
572 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
574 return isl_union_map_subtract(uset1, uset2);
577 struct isl_union_map_gen_bin_set_data {
578 isl_set *set;
579 isl_union_map *res;
582 static int intersect_params_entry(void **entry, void *user)
584 struct isl_union_map_gen_bin_set_data *data = user;
585 isl_map *map = *entry;
586 int empty;
588 map = isl_map_copy(map);
589 map = isl_map_intersect_params(map, isl_set_copy(data->set));
591 empty = isl_map_is_empty(map);
592 if (empty < 0) {
593 isl_map_free(map);
594 return -1;
597 data->res = isl_union_map_add_map(data->res, map);
599 return 0;
602 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
603 __isl_take isl_set *set, int (*fn)(void **, void *))
605 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
607 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
608 set = isl_set_align_params(set, isl_union_map_get_space(umap));
610 if (!umap || !set)
611 goto error;
613 data.set = set;
614 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
615 umap->table.n);
616 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
617 fn, &data) < 0)
618 goto error;
620 isl_union_map_free(umap);
621 isl_set_free(set);
622 return data.res;
623 error:
624 isl_union_map_free(umap);
625 isl_set_free(set);
626 isl_union_map_free(data.res);
627 return NULL;
630 __isl_give isl_union_map *isl_union_map_intersect_params(
631 __isl_take isl_union_map *umap, __isl_take isl_set *set)
633 return gen_bin_set_op(umap, set, &intersect_params_entry);
636 __isl_give isl_union_set *isl_union_set_intersect_params(
637 __isl_take isl_union_set *uset, __isl_take isl_set *set)
639 return isl_union_map_intersect_params(uset, set);
642 static __isl_give isl_union_map *union_map_intersect_params(
643 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
645 return isl_union_map_intersect_params(umap,
646 isl_set_from_union_set(uset));
649 static __isl_give isl_union_map *union_map_gist_params(
650 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
652 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
655 struct isl_union_map_match_bin_data {
656 isl_union_map *umap2;
657 isl_union_map *res;
658 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
661 static int match_bin_entry(void **entry, void *user)
663 struct isl_union_map_match_bin_data *data = user;
664 uint32_t hash;
665 struct isl_hash_table_entry *entry2;
666 isl_map *map = *entry;
667 int empty;
669 hash = isl_space_get_hash(map->dim);
670 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
671 hash, &has_dim, map->dim, 0);
672 if (!entry2)
673 return 0;
675 map = isl_map_copy(map);
676 map = data->fn(map, isl_map_copy(entry2->data));
678 empty = isl_map_is_empty(map);
679 if (empty < 0) {
680 isl_map_free(map);
681 return -1;
683 if (empty) {
684 isl_map_free(map);
685 return 0;
688 data->res = isl_union_map_add_map(data->res, map);
690 return 0;
693 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
694 __isl_take isl_union_map *umap2,
695 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
697 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
699 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
700 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
702 if (!umap1 || !umap2)
703 goto error;
705 data.umap2 = umap2;
706 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
707 umap1->table.n);
708 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
709 &match_bin_entry, &data) < 0)
710 goto error;
712 isl_union_map_free(umap1);
713 isl_union_map_free(umap2);
714 return data.res;
715 error:
716 isl_union_map_free(umap1);
717 isl_union_map_free(umap2);
718 isl_union_map_free(data.res);
719 return NULL;
722 __isl_give isl_union_map *isl_union_map_intersect(
723 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
725 return match_bin_op(umap1, umap2, &isl_map_intersect);
728 /* Compute the intersection of the two union_sets.
729 * As a special case, if exactly one of the two union_sets
730 * is a parameter domain, then intersect the parameter domain
731 * of the other one with this set.
733 __isl_give isl_union_set *isl_union_set_intersect(
734 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
736 int p1, p2;
738 p1 = isl_union_set_is_params(uset1);
739 p2 = isl_union_set_is_params(uset2);
740 if (p1 < 0 || p2 < 0)
741 goto error;
742 if (!p1 && p2)
743 return union_map_intersect_params(uset1, uset2);
744 if (p1 && !p2)
745 return union_map_intersect_params(uset2, uset1);
746 return isl_union_map_intersect(uset1, uset2);
747 error:
748 isl_union_set_free(uset1);
749 isl_union_set_free(uset2);
750 return NULL;
753 static int gist_params_entry(void **entry, void *user)
755 struct isl_union_map_gen_bin_set_data *data = user;
756 isl_map *map = *entry;
757 int empty;
759 map = isl_map_copy(map);
760 map = isl_map_gist_params(map, isl_set_copy(data->set));
762 empty = isl_map_is_empty(map);
763 if (empty < 0) {
764 isl_map_free(map);
765 return -1;
768 data->res = isl_union_map_add_map(data->res, map);
770 return 0;
773 __isl_give isl_union_map *isl_union_map_gist_params(
774 __isl_take isl_union_map *umap, __isl_take isl_set *set)
776 return gen_bin_set_op(umap, set, &gist_params_entry);
779 __isl_give isl_union_set *isl_union_set_gist_params(
780 __isl_take isl_union_set *uset, __isl_take isl_set *set)
782 return isl_union_map_gist_params(uset, set);
785 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
786 __isl_take isl_union_map *context)
788 return match_bin_op(umap, context, &isl_map_gist);
791 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
792 __isl_take isl_union_set *context)
794 if (isl_union_set_is_params(context))
795 return union_map_gist_params(uset, context);
796 return isl_union_map_gist(uset, context);
799 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
800 __isl_take isl_map *set2)
802 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
805 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
806 __isl_take isl_map *set2)
808 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
811 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
812 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
814 return match_bin_op(uset1, uset2, &lex_lt_set);
817 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
818 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
820 return match_bin_op(uset1, uset2, &lex_le_set);
823 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
824 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
826 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
829 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
830 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
832 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
835 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
836 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
838 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
841 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
842 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
844 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
847 static int intersect_domain_entry(void **entry, void *user)
849 struct isl_union_map_gen_bin_data *data = user;
850 uint32_t hash;
851 struct isl_hash_table_entry *entry2;
852 isl_space *dim;
853 isl_map *map = *entry;
854 int empty;
856 dim = isl_map_get_space(map);
857 dim = isl_space_domain(dim);
858 hash = isl_space_get_hash(dim);
859 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
860 hash, &has_dim, dim, 0);
861 isl_space_free(dim);
862 if (!entry2)
863 return 0;
865 map = isl_map_copy(map);
866 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
868 empty = isl_map_is_empty(map);
869 if (empty < 0) {
870 isl_map_free(map);
871 return -1;
873 if (empty) {
874 isl_map_free(map);
875 return 0;
878 data->res = isl_union_map_add_map(data->res, map);
880 return 0;
883 /* Intersect the domain of "umap" with "uset".
884 * If "uset" is a parameters domain, then intersect the parameter
885 * domain of "umap" with this set.
887 __isl_give isl_union_map *isl_union_map_intersect_domain(
888 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
890 if (isl_union_set_is_params(uset))
891 return union_map_intersect_params(umap, uset);
892 return gen_bin_op(umap, uset, &intersect_domain_entry);
895 static int gist_domain_entry(void **entry, void *user)
897 struct isl_union_map_gen_bin_data *data = user;
898 uint32_t hash;
899 struct isl_hash_table_entry *entry2;
900 isl_space *dim;
901 isl_map *map = *entry;
902 int empty;
904 dim = isl_map_get_space(map);
905 dim = isl_space_domain(dim);
906 hash = isl_space_get_hash(dim);
907 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
908 hash, &has_dim, dim, 0);
909 isl_space_free(dim);
910 if (!entry2)
911 return 0;
913 map = isl_map_copy(map);
914 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
916 empty = isl_map_is_empty(map);
917 if (empty < 0) {
918 isl_map_free(map);
919 return -1;
922 data->res = isl_union_map_add_map(data->res, map);
924 return 0;
927 /* Compute the gist of "umap" with respect to the domain "uset".
928 * If "uset" is a parameters domain, then compute the gist
929 * with respect to this parameter domain.
931 __isl_give isl_union_map *isl_union_map_gist_domain(
932 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
934 if (isl_union_set_is_params(uset))
935 return union_map_gist_params(umap, uset);
936 return gen_bin_op(umap, uset, &gist_domain_entry);
939 static int gist_range_entry(void **entry, void *user)
941 struct isl_union_map_gen_bin_data *data = user;
942 uint32_t hash;
943 struct isl_hash_table_entry *entry2;
944 isl_space *space;
945 isl_map *map = *entry;
946 int empty;
948 space = isl_map_get_space(map);
949 space = isl_space_range(space);
950 hash = isl_space_get_hash(space);
951 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
952 hash, &has_dim, space, 0);
953 isl_space_free(space);
954 if (!entry2)
955 return 0;
957 map = isl_map_copy(map);
958 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
960 empty = isl_map_is_empty(map);
961 if (empty < 0) {
962 isl_map_free(map);
963 return -1;
966 data->res = isl_union_map_add_map(data->res, map);
968 return 0;
971 /* Compute the gist of "umap" with respect to the range "uset".
973 __isl_give isl_union_map *isl_union_map_gist_range(
974 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
976 return gen_bin_op(umap, uset, &gist_range_entry);
979 static int intersect_range_entry(void **entry, void *user)
981 struct isl_union_map_gen_bin_data *data = user;
982 uint32_t hash;
983 struct isl_hash_table_entry *entry2;
984 isl_space *dim;
985 isl_map *map = *entry;
986 int empty;
988 dim = isl_map_get_space(map);
989 dim = isl_space_range(dim);
990 hash = isl_space_get_hash(dim);
991 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
992 hash, &has_dim, dim, 0);
993 isl_space_free(dim);
994 if (!entry2)
995 return 0;
997 map = isl_map_copy(map);
998 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1000 empty = isl_map_is_empty(map);
1001 if (empty < 0) {
1002 isl_map_free(map);
1003 return -1;
1005 if (empty) {
1006 isl_map_free(map);
1007 return 0;
1010 data->res = isl_union_map_add_map(data->res, map);
1012 return 0;
1015 __isl_give isl_union_map *isl_union_map_intersect_range(
1016 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1018 return gen_bin_op(umap, uset, &intersect_range_entry);
1021 struct isl_union_map_bin_data {
1022 isl_union_map *umap2;
1023 isl_union_map *res;
1024 isl_map *map;
1025 int (*fn)(void **entry, void *user);
1028 static int apply_range_entry(void **entry, void *user)
1030 struct isl_union_map_bin_data *data = user;
1031 isl_map *map2 = *entry;
1032 int empty;
1034 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1035 map2->dim, isl_dim_in))
1036 return 0;
1038 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1040 empty = isl_map_is_empty(map2);
1041 if (empty < 0) {
1042 isl_map_free(map2);
1043 return -1;
1045 if (empty) {
1046 isl_map_free(map2);
1047 return 0;
1050 data->res = isl_union_map_add_map(data->res, map2);
1052 return 0;
1055 static int bin_entry(void **entry, void *user)
1057 struct isl_union_map_bin_data *data = user;
1058 isl_map *map = *entry;
1060 data->map = map;
1061 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1062 data->fn, data) < 0)
1063 return -1;
1065 return 0;
1068 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1069 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1071 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1073 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1074 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1076 if (!umap1 || !umap2)
1077 goto error;
1079 data.umap2 = umap2;
1080 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1081 umap1->table.n);
1082 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1083 &bin_entry, &data) < 0)
1084 goto error;
1086 isl_union_map_free(umap1);
1087 isl_union_map_free(umap2);
1088 return data.res;
1089 error:
1090 isl_union_map_free(umap1);
1091 isl_union_map_free(umap2);
1092 isl_union_map_free(data.res);
1093 return NULL;
1096 __isl_give isl_union_map *isl_union_map_apply_range(
1097 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1099 return bin_op(umap1, umap2, &apply_range_entry);
1102 __isl_give isl_union_map *isl_union_map_apply_domain(
1103 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1105 umap1 = isl_union_map_reverse(umap1);
1106 umap1 = isl_union_map_apply_range(umap1, umap2);
1107 return isl_union_map_reverse(umap1);
1110 __isl_give isl_union_set *isl_union_set_apply(
1111 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1113 return isl_union_map_apply_range(uset, umap);
1116 static int map_lex_lt_entry(void **entry, void *user)
1118 struct isl_union_map_bin_data *data = user;
1119 isl_map *map2 = *entry;
1121 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1122 map2->dim, isl_dim_out))
1123 return 0;
1125 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1127 data->res = isl_union_map_add_map(data->res, map2);
1129 return 0;
1132 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1133 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1135 return bin_op(umap1, umap2, &map_lex_lt_entry);
1138 static int map_lex_le_entry(void **entry, void *user)
1140 struct isl_union_map_bin_data *data = user;
1141 isl_map *map2 = *entry;
1143 if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1144 map2->dim, isl_dim_out))
1145 return 0;
1147 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1149 data->res = isl_union_map_add_map(data->res, map2);
1151 return 0;
1154 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1155 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1157 return bin_op(umap1, umap2, &map_lex_le_entry);
1160 static int product_entry(void **entry, void *user)
1162 struct isl_union_map_bin_data *data = user;
1163 isl_map *map2 = *entry;
1165 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1167 data->res = isl_union_map_add_map(data->res, map2);
1169 return 0;
1172 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1173 __isl_take isl_union_map *umap2)
1175 return bin_op(umap1, umap2, &product_entry);
1178 static int set_product_entry(void **entry, void *user)
1180 struct isl_union_map_bin_data *data = user;
1181 isl_set *set2 = *entry;
1183 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1185 data->res = isl_union_set_add_set(data->res, set2);
1187 return 0;
1190 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1191 __isl_take isl_union_set *uset2)
1193 return bin_op(uset1, uset2, &set_product_entry);
1196 static int range_product_entry(void **entry, void *user)
1198 struct isl_union_map_bin_data *data = user;
1199 isl_map *map2 = *entry;
1201 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1202 map2->dim, isl_dim_in))
1203 return 0;
1205 map2 = isl_map_range_product(isl_map_copy(data->map),
1206 isl_map_copy(map2));
1208 data->res = isl_union_map_add_map(data->res, map2);
1210 return 0;
1213 __isl_give isl_union_map *isl_union_map_range_product(
1214 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1216 return bin_op(umap1, umap2, &range_product_entry);
1219 static int flat_range_product_entry(void **entry, void *user)
1221 struct isl_union_map_bin_data *data = user;
1222 isl_map *map2 = *entry;
1224 if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1225 map2->dim, isl_dim_in))
1226 return 0;
1228 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1229 isl_map_copy(map2));
1231 data->res = isl_union_map_add_map(data->res, map2);
1233 return 0;
1236 __isl_give isl_union_map *isl_union_map_flat_range_product(
1237 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1239 return bin_op(umap1, umap2, &flat_range_product_entry);
1242 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1243 int (*fn)(void **, void *))
1245 isl_union_set *res;
1247 if (!umap)
1248 return NULL;
1250 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1251 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1252 goto error;
1254 isl_union_map_free(umap);
1255 return res;
1256 error:
1257 isl_union_map_free(umap);
1258 isl_union_set_free(res);
1259 return NULL;
1262 static int from_range_entry(void **entry, void *user)
1264 isl_map *set = *entry;
1265 isl_union_set **res = user;
1267 *res = isl_union_map_add_map(*res,
1268 isl_map_from_range(isl_set_copy(set)));
1270 return 0;
1273 __isl_give isl_union_map *isl_union_map_from_range(
1274 __isl_take isl_union_set *uset)
1276 return cond_un_op(uset, &from_range_entry);
1279 __isl_give isl_union_map *isl_union_map_from_domain(
1280 __isl_take isl_union_set *uset)
1282 return isl_union_map_reverse(isl_union_map_from_range(uset));
1285 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1286 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1288 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1289 isl_union_map_from_range(range));
1292 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1293 int (*fn)(void **, void *))
1295 umap = isl_union_map_cow(umap);
1296 if (!umap)
1297 return NULL;
1299 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1300 goto error;
1302 return umap;
1303 error:
1304 isl_union_map_free(umap);
1305 return NULL;
1308 static int affine_entry(void **entry, void *user)
1310 isl_map **map = (isl_map **)entry;
1312 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1314 return *map ? 0 : -1;
1317 __isl_give isl_union_map *isl_union_map_affine_hull(
1318 __isl_take isl_union_map *umap)
1320 return un_op(umap, &affine_entry);
1323 __isl_give isl_union_set *isl_union_set_affine_hull(
1324 __isl_take isl_union_set *uset)
1326 return isl_union_map_affine_hull(uset);
1329 static int polyhedral_entry(void **entry, void *user)
1331 isl_map **map = (isl_map **)entry;
1333 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1335 return *map ? 0 : -1;
1338 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1339 __isl_take isl_union_map *umap)
1341 return un_op(umap, &polyhedral_entry);
1344 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1345 __isl_take isl_union_set *uset)
1347 return isl_union_map_polyhedral_hull(uset);
1350 static int simple_entry(void **entry, void *user)
1352 isl_map **map = (isl_map **)entry;
1354 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1356 return *map ? 0 : -1;
1359 __isl_give isl_union_map *isl_union_map_simple_hull(
1360 __isl_take isl_union_map *umap)
1362 return un_op(umap, &simple_entry);
1365 __isl_give isl_union_set *isl_union_set_simple_hull(
1366 __isl_take isl_union_set *uset)
1368 return isl_union_map_simple_hull(uset);
1371 static int inplace_entry(void **entry, void *user)
1373 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1374 isl_map **map = (isl_map **)entry;
1375 isl_map *copy;
1377 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1378 copy = fn(isl_map_copy(*map));
1379 if (!copy)
1380 return -1;
1382 isl_map_free(*map);
1383 *map = copy;
1385 return 0;
1388 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1389 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1391 if (!umap)
1392 return NULL;
1394 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1395 &inplace_entry, &fn) < 0)
1396 goto error;
1398 return umap;
1399 error:
1400 isl_union_map_free(umap);
1401 return NULL;
1404 __isl_give isl_union_map *isl_union_map_coalesce(
1405 __isl_take isl_union_map *umap)
1407 return inplace(umap, &isl_map_coalesce);
1410 __isl_give isl_union_set *isl_union_set_coalesce(
1411 __isl_take isl_union_set *uset)
1413 return isl_union_map_coalesce(uset);
1416 __isl_give isl_union_map *isl_union_map_detect_equalities(
1417 __isl_take isl_union_map *umap)
1419 return inplace(umap, &isl_map_detect_equalities);
1422 __isl_give isl_union_set *isl_union_set_detect_equalities(
1423 __isl_take isl_union_set *uset)
1425 return isl_union_map_detect_equalities(uset);
1428 __isl_give isl_union_map *isl_union_map_compute_divs(
1429 __isl_take isl_union_map *umap)
1431 return inplace(umap, &isl_map_compute_divs);
1434 __isl_give isl_union_set *isl_union_set_compute_divs(
1435 __isl_take isl_union_set *uset)
1437 return isl_union_map_compute_divs(uset);
1440 static int lexmin_entry(void **entry, void *user)
1442 isl_map **map = (isl_map **)entry;
1444 *map = isl_map_lexmin(*map);
1446 return *map ? 0 : -1;
1449 __isl_give isl_union_map *isl_union_map_lexmin(
1450 __isl_take isl_union_map *umap)
1452 return un_op(umap, &lexmin_entry);
1455 __isl_give isl_union_set *isl_union_set_lexmin(
1456 __isl_take isl_union_set *uset)
1458 return isl_union_map_lexmin(uset);
1461 static int lexmax_entry(void **entry, void *user)
1463 isl_map **map = (isl_map **)entry;
1465 *map = isl_map_lexmax(*map);
1467 return *map ? 0 : -1;
1470 __isl_give isl_union_map *isl_union_map_lexmax(
1471 __isl_take isl_union_map *umap)
1473 return un_op(umap, &lexmax_entry);
1476 __isl_give isl_union_set *isl_union_set_lexmax(
1477 __isl_take isl_union_set *uset)
1479 return isl_union_map_lexmax(uset);
1482 static int universe_entry(void **entry, void *user)
1484 isl_map *map = *entry;
1485 isl_union_map **res = user;
1487 map = isl_map_universe(isl_map_get_space(map));
1488 *res = isl_union_map_add_map(*res, map);
1490 return 0;
1493 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1495 return cond_un_op(umap, &universe_entry);
1498 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1500 return isl_union_map_universe(uset);
1503 static int reverse_entry(void **entry, void *user)
1505 isl_map *map = *entry;
1506 isl_union_map **res = user;
1508 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1510 return 0;
1513 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1515 return cond_un_op(umap, &reverse_entry);
1518 static int params_entry(void **entry, void *user)
1520 isl_map *map = *entry;
1521 isl_union_set **res = user;
1523 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1525 return 0;
1528 /* Compute the parameter domain of the given union map.
1530 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1532 int empty;
1534 empty = isl_union_map_is_empty(umap);
1535 if (empty < 0)
1536 return isl_union_map_free(umap);
1537 if (empty)
1538 return isl_set_empty(isl_union_map_get_space(umap));
1539 return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1542 /* Compute the parameter domain of the given union set.
1544 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1546 return isl_union_map_params(uset);
1549 static int domain_entry(void **entry, void *user)
1551 isl_map *map = *entry;
1552 isl_union_set **res = user;
1554 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1556 return 0;
1559 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1561 return cond_un_op(umap, &domain_entry);
1564 static int range_entry(void **entry, void *user)
1566 isl_map *map = *entry;
1567 isl_union_set **res = user;
1569 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1571 return 0;
1574 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1576 return cond_un_op(umap, &range_entry);
1579 static int domain_map_entry(void **entry, void *user)
1581 isl_map *map = *entry;
1582 isl_union_set **res = user;
1584 *res = isl_union_map_add_map(*res,
1585 isl_map_domain_map(isl_map_copy(map)));
1587 return 0;
1590 __isl_give isl_union_map *isl_union_map_domain_map(
1591 __isl_take isl_union_map *umap)
1593 return cond_un_op(umap, &domain_map_entry);
1596 static int range_map_entry(void **entry, void *user)
1598 isl_map *map = *entry;
1599 isl_union_set **res = user;
1601 *res = isl_union_map_add_map(*res,
1602 isl_map_range_map(isl_map_copy(map)));
1604 return 0;
1607 __isl_give isl_union_map *isl_union_map_range_map(
1608 __isl_take isl_union_map *umap)
1610 return cond_un_op(umap, &range_map_entry);
1613 static int deltas_entry(void **entry, void *user)
1615 isl_map *map = *entry;
1616 isl_union_set **res = user;
1618 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1619 return 0;
1621 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1623 return 0;
1626 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1628 return cond_un_op(umap, &deltas_entry);
1631 static int deltas_map_entry(void **entry, void *user)
1633 isl_map *map = *entry;
1634 isl_union_map **res = user;
1636 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1637 return 0;
1639 *res = isl_union_map_add_map(*res,
1640 isl_map_deltas_map(isl_map_copy(map)));
1642 return 0;
1645 __isl_give isl_union_map *isl_union_map_deltas_map(
1646 __isl_take isl_union_map *umap)
1648 return cond_un_op(umap, &deltas_map_entry);
1651 static int identity_entry(void **entry, void *user)
1653 isl_set *set = *entry;
1654 isl_union_map **res = user;
1656 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1658 return 0;
1661 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1663 return cond_un_op(uset, &identity_entry);
1666 static int unwrap_entry(void **entry, void *user)
1668 isl_set *set = *entry;
1669 isl_union_set **res = user;
1671 if (!isl_set_is_wrapping(set))
1672 return 0;
1674 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1676 return 0;
1679 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1681 return cond_un_op(uset, &unwrap_entry);
1684 static int wrap_entry(void **entry, void *user)
1686 isl_map *map = *entry;
1687 isl_union_set **res = user;
1689 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1691 return 0;
1694 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1696 return cond_un_op(umap, &wrap_entry);
1699 struct isl_union_map_is_subset_data {
1700 isl_union_map *umap2;
1701 int is_subset;
1704 static int is_subset_entry(void **entry, void *user)
1706 struct isl_union_map_is_subset_data *data = user;
1707 uint32_t hash;
1708 struct isl_hash_table_entry *entry2;
1709 isl_map *map = *entry;
1711 hash = isl_space_get_hash(map->dim);
1712 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1713 hash, &has_dim, map->dim, 0);
1714 if (!entry2) {
1715 int empty = isl_map_is_empty(map);
1716 if (empty < 0)
1717 return -1;
1718 if (empty)
1719 return 0;
1720 data->is_subset = 0;
1721 return -1;
1724 data->is_subset = isl_map_is_subset(map, entry2->data);
1725 if (data->is_subset < 0 || !data->is_subset)
1726 return -1;
1728 return 0;
1731 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1732 __isl_keep isl_union_map *umap2)
1734 struct isl_union_map_is_subset_data data = { NULL, 1 };
1736 umap1 = isl_union_map_copy(umap1);
1737 umap2 = isl_union_map_copy(umap2);
1738 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1739 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1741 if (!umap1 || !umap2)
1742 goto error;
1744 data.umap2 = umap2;
1745 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1746 &is_subset_entry, &data) < 0 &&
1747 data.is_subset)
1748 goto error;
1750 isl_union_map_free(umap1);
1751 isl_union_map_free(umap2);
1753 return data.is_subset;
1754 error:
1755 isl_union_map_free(umap1);
1756 isl_union_map_free(umap2);
1757 return -1;
1760 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1761 __isl_keep isl_union_set *uset2)
1763 return isl_union_map_is_subset(uset1, uset2);
1766 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1767 __isl_keep isl_union_map *umap2)
1769 int is_subset;
1771 if (!umap1 || !umap2)
1772 return -1;
1773 is_subset = isl_union_map_is_subset(umap1, umap2);
1774 if (is_subset != 1)
1775 return is_subset;
1776 is_subset = isl_union_map_is_subset(umap2, umap1);
1777 return is_subset;
1780 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1781 __isl_keep isl_union_set *uset2)
1783 return isl_union_map_is_equal(uset1, uset2);
1786 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1787 __isl_keep isl_union_map *umap2)
1789 int is_subset;
1791 if (!umap1 || !umap2)
1792 return -1;
1793 is_subset = isl_union_map_is_subset(umap1, umap2);
1794 if (is_subset != 1)
1795 return is_subset;
1796 is_subset = isl_union_map_is_subset(umap2, umap1);
1797 if (is_subset == -1)
1798 return is_subset;
1799 return !is_subset;
1802 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1803 __isl_keep isl_union_set *uset2)
1805 return isl_union_map_is_strict_subset(uset1, uset2);
1808 static int sample_entry(void **entry, void *user)
1810 isl_basic_map **sample = (isl_basic_map **)user;
1811 isl_map *map = *entry;
1813 *sample = isl_map_sample(isl_map_copy(map));
1814 if (!*sample)
1815 return -1;
1816 if (!isl_basic_map_plain_is_empty(*sample))
1817 return -1;
1818 return 0;
1821 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1823 isl_basic_map *sample = NULL;
1825 if (!umap)
1826 return NULL;
1828 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1829 &sample_entry, &sample) < 0 &&
1830 !sample)
1831 goto error;
1833 if (!sample)
1834 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1836 isl_union_map_free(umap);
1838 return sample;
1839 error:
1840 isl_union_map_free(umap);
1841 return NULL;
1844 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1846 return (isl_basic_set *)isl_union_map_sample(uset);
1849 struct isl_forall_data {
1850 int res;
1851 int (*fn)(__isl_keep isl_map *map);
1854 static int forall_entry(void **entry, void *user)
1856 struct isl_forall_data *data = user;
1857 isl_map *map = *entry;
1859 data->res = data->fn(map);
1860 if (data->res < 0)
1861 return -1;
1863 if (!data->res)
1864 return -1;
1866 return 0;
1869 static int union_map_forall(__isl_keep isl_union_map *umap,
1870 int (*fn)(__isl_keep isl_map *map))
1872 struct isl_forall_data data = { 1, fn };
1874 if (!umap)
1875 return -1;
1877 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1878 &forall_entry, &data) < 0 && data.res)
1879 return -1;
1881 return data.res;
1884 struct isl_forall_user_data {
1885 int res;
1886 int (*fn)(__isl_keep isl_map *map, void *user);
1887 void *user;
1890 static int forall_user_entry(void **entry, void *user)
1892 struct isl_forall_user_data *data = user;
1893 isl_map *map = *entry;
1895 data->res = data->fn(map, data->user);
1896 if (data->res < 0)
1897 return -1;
1899 if (!data->res)
1900 return -1;
1902 return 0;
1905 /* Check if fn(map, user) returns true for all maps "map" in umap.
1907 static int union_map_forall_user(__isl_keep isl_union_map *umap,
1908 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
1910 struct isl_forall_user_data data = { 1, fn, user };
1912 if (!umap)
1913 return -1;
1915 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1916 &forall_user_entry, &data) < 0 && data.res)
1917 return -1;
1919 return data.res;
1922 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
1924 return union_map_forall(umap, &isl_map_is_empty);
1927 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
1929 return isl_union_map_is_empty(uset);
1932 static int is_subset_of_identity(__isl_keep isl_map *map)
1934 int is_subset;
1935 isl_space *dim;
1936 isl_map *id;
1938 if (!map)
1939 return -1;
1941 if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1942 return 0;
1944 dim = isl_map_get_space(map);
1945 id = isl_map_identity(dim);
1947 is_subset = isl_map_is_subset(map, id);
1949 isl_map_free(id);
1951 return is_subset;
1954 /* Check if the given map is single-valued.
1955 * We simply compute
1957 * M \circ M^-1
1959 * and check if the result is a subset of the identity mapping.
1961 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
1963 isl_union_map *test;
1964 int sv;
1966 if (isl_union_map_n_map(umap) == 1) {
1967 isl_map *map;
1968 umap = isl_union_map_copy(umap);
1969 map = isl_map_from_union_map(umap);
1970 sv = isl_map_is_single_valued(map);
1971 isl_map_free(map);
1972 return sv;
1975 test = isl_union_map_reverse(isl_union_map_copy(umap));
1976 test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
1978 sv = union_map_forall(test, &is_subset_of_identity);
1980 isl_union_map_free(test);
1982 return sv;
1985 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
1987 int in;
1989 umap = isl_union_map_copy(umap);
1990 umap = isl_union_map_reverse(umap);
1991 in = isl_union_map_is_single_valued(umap);
1992 isl_union_map_free(umap);
1994 return in;
1997 /* Represents a map that has a fixed value (v) for one of its
1998 * range dimensions.
1999 * The map in this structure is not reference counted, so it
2000 * is only valid while the isl_union_map from which it was
2001 * obtained is still alive.
2003 struct isl_fixed_map {
2004 isl_int v;
2005 isl_map *map;
2008 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2009 int n)
2011 int i;
2012 struct isl_fixed_map *v;
2014 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2015 if (!v)
2016 return NULL;
2017 for (i = 0; i < n; ++i)
2018 isl_int_init(v[i].v);
2019 return v;
2022 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2024 int i;
2026 if (!v)
2027 return;
2028 for (i = 0; i < n; ++i)
2029 isl_int_clear(v[i].v);
2030 free(v);
2033 /* Compare the "v" field of two isl_fixed_map structs.
2035 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2037 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2038 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2040 return isl_int_cmp(e1->v, e2->v);
2043 /* Internal data structure used while checking whether all maps
2044 * in a union_map have a fixed value for a given output dimension.
2045 * v is the list of maps, with the fixed value for the dimension
2046 * n is the number of maps considered so far
2047 * pos is the output dimension under investigation
2049 struct isl_fixed_dim_data {
2050 struct isl_fixed_map *v;
2051 int n;
2052 int pos;
2055 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2057 struct isl_fixed_dim_data *data = user;
2059 data->v[data->n].map = map;
2060 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2061 &data->v[data->n++].v);
2064 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2065 int first, int n_range);
2067 /* Given a list of the maps, with their fixed values at output dimension "pos",
2068 * check whether the ranges of the maps form an obvious partition.
2070 * We first sort the maps according to their fixed values.
2071 * If all maps have a different value, then we know the ranges form
2072 * a partition.
2073 * Otherwise, we collect the maps with the same fixed value and
2074 * check whether each such collection is obviously injective
2075 * based on later dimensions.
2077 static int separates(struct isl_fixed_map *v, int n,
2078 __isl_take isl_space *dim, int pos, int n_range)
2080 int i;
2082 if (!v)
2083 goto error;
2085 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2087 for (i = 0; i + 1 < n; ++i) {
2088 int j, k;
2089 isl_union_map *part;
2090 int injective;
2092 for (j = i + 1; j < n; ++j)
2093 if (isl_int_ne(v[i].v, v[j].v))
2094 break;
2096 if (j == i + 1)
2097 continue;
2099 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2100 for (k = i; k < j; ++k)
2101 part = isl_union_map_add_map(part,
2102 isl_map_copy(v[k].map));
2104 injective = plain_injective_on_range(part, pos + 1, n_range);
2105 if (injective < 0)
2106 goto error;
2107 if (!injective)
2108 break;
2110 i = j - 1;
2113 isl_space_free(dim);
2114 free_isl_fixed_map_array(v, n);
2115 return i + 1 >= n;
2116 error:
2117 isl_space_free(dim);
2118 free_isl_fixed_map_array(v, n);
2119 return -1;
2122 /* Check whether the maps in umap have obviously distinct ranges.
2123 * In particular, check for an output dimension in the range
2124 * [first,n_range) for which all maps have a fixed value
2125 * and then check if these values, possibly along with fixed values
2126 * at later dimensions, entail distinct ranges.
2128 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2129 int first, int n_range)
2131 isl_ctx *ctx;
2132 int n;
2133 struct isl_fixed_dim_data data = { NULL };
2135 ctx = isl_union_map_get_ctx(umap);
2137 if (!umap)
2138 goto error;
2140 n = isl_union_map_n_map(umap);
2141 if (n <= 1) {
2142 isl_union_map_free(umap);
2143 return 1;
2146 if (first >= n_range) {
2147 isl_union_map_free(umap);
2148 return 0;
2151 data.v = alloc_isl_fixed_map_array(ctx, n);
2152 if (!data.v)
2153 goto error;
2155 for (data.pos = first; data.pos < n_range; ++data.pos) {
2156 int fixed;
2157 int injective;
2158 isl_space *dim;
2160 data.n = 0;
2161 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2162 if (fixed < 0)
2163 goto error;
2164 if (!fixed)
2165 continue;
2166 dim = isl_union_map_get_space(umap);
2167 injective = separates(data.v, n, dim, data.pos, n_range);
2168 isl_union_map_free(umap);
2169 return injective;
2172 free_isl_fixed_map_array(data.v, n);
2173 isl_union_map_free(umap);
2175 return 0;
2176 error:
2177 free_isl_fixed_map_array(data.v, n);
2178 isl_union_map_free(umap);
2179 return -1;
2182 /* Check whether the maps in umap that map to subsets of "ran"
2183 * have obviously distinct ranges.
2185 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2187 isl_union_map *umap = user;
2189 umap = isl_union_map_copy(umap);
2190 umap = isl_union_map_intersect_range(umap,
2191 isl_union_set_from_set(isl_set_copy(ran)));
2192 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2195 /* Check if the given union_map is obviously injective.
2197 * In particular, we first check if all individual maps are obviously
2198 * injective and then check if all the ranges of these maps are
2199 * obviously disjoint.
2201 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2203 int in;
2204 isl_union_map *univ;
2205 isl_union_set *ran;
2207 in = union_map_forall(umap, &isl_map_plain_is_injective);
2208 if (in < 0)
2209 return -1;
2210 if (!in)
2211 return 0;
2213 univ = isl_union_map_universe(isl_union_map_copy(umap));
2214 ran = isl_union_map_range(univ);
2216 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2218 isl_union_set_free(ran);
2220 return in;
2223 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2225 int sv;
2227 sv = isl_union_map_is_single_valued(umap);
2228 if (sv < 0 || !sv)
2229 return sv;
2231 return isl_union_map_is_injective(umap);
2234 static int zip_entry(void **entry, void *user)
2236 isl_map *map = *entry;
2237 isl_union_map **res = user;
2239 if (!isl_map_can_zip(map))
2240 return 0;
2242 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2244 return 0;
2247 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2249 return cond_un_op(umap, &zip_entry);
2252 static int curry_entry(void **entry, void *user)
2254 isl_map *map = *entry;
2255 isl_union_map **res = user;
2257 if (!isl_map_can_curry(map))
2258 return 0;
2260 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2262 return 0;
2265 /* Given a union map, take the maps of the form (A -> B) -> C and
2266 * return the union of the corresponding maps A -> (B -> C).
2268 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2270 return cond_un_op(umap, &curry_entry);
2273 static int lift_entry(void **entry, void *user)
2275 isl_set *set = *entry;
2276 isl_union_set **res = user;
2278 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2280 return 0;
2283 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2285 return cond_un_op(uset, &lift_entry);
2288 static int coefficients_entry(void **entry, void *user)
2290 isl_set *set = *entry;
2291 isl_union_set **res = user;
2293 set = isl_set_copy(set);
2294 set = isl_set_from_basic_set(isl_set_coefficients(set));
2295 *res = isl_union_set_add_set(*res, set);
2297 return 0;
2300 __isl_give isl_union_set *isl_union_set_coefficients(
2301 __isl_take isl_union_set *uset)
2303 isl_ctx *ctx;
2304 isl_space *dim;
2305 isl_union_set *res;
2307 if (!uset)
2308 return NULL;
2310 ctx = isl_union_set_get_ctx(uset);
2311 dim = isl_space_set_alloc(ctx, 0, 0);
2312 res = isl_union_map_alloc(dim, uset->table.n);
2313 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2314 &coefficients_entry, &res) < 0)
2315 goto error;
2317 isl_union_set_free(uset);
2318 return res;
2319 error:
2320 isl_union_set_free(uset);
2321 isl_union_set_free(res);
2322 return NULL;
2325 static int solutions_entry(void **entry, void *user)
2327 isl_set *set = *entry;
2328 isl_union_set **res = user;
2330 set = isl_set_copy(set);
2331 set = isl_set_from_basic_set(isl_set_solutions(set));
2332 if (!*res)
2333 *res = isl_union_set_from_set(set);
2334 else
2335 *res = isl_union_set_add_set(*res, set);
2337 if (!*res)
2338 return -1;
2340 return 0;
2343 __isl_give isl_union_set *isl_union_set_solutions(
2344 __isl_take isl_union_set *uset)
2346 isl_union_set *res = NULL;
2348 if (!uset)
2349 return NULL;
2351 if (uset->table.n == 0) {
2352 res = isl_union_set_empty(isl_union_set_get_space(uset));
2353 isl_union_set_free(uset);
2354 return res;
2357 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2358 &solutions_entry, &res) < 0)
2359 goto error;
2361 isl_union_set_free(uset);
2362 return res;
2363 error:
2364 isl_union_set_free(uset);
2365 isl_union_set_free(res);
2366 return NULL;