isl_sample.c: sample_bounded: use isl_basic_set_get_ctx
[isl.git] / isl_union_map.c
blob0f19110db085b60ca1c36fc4c8603ed3bb99f8a0
1 /*
2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2013-2014 Ecole Normale Superieure
4 * Copyright 2014 INRIA Rocquencourt
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
12 * B.P. 105 - 78153 Le Chesnay, France
15 #define ISL_DIM_H
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl/ctx.h>
19 #include <isl/hash.h>
20 #include <isl/aff.h>
21 #include <isl/map.h>
22 #include <isl/set.h>
23 #include <isl_space_private.h>
24 #include <isl/union_set.h>
25 #include <isl/deprecated/union_map_int.h>
27 /* Return the number of parameters of "umap", where "type"
28 * is required to be set to isl_dim_param.
30 unsigned isl_union_map_dim(__isl_keep isl_union_map *umap,
31 enum isl_dim_type type)
33 if (!umap)
34 return 0;
36 if (type != isl_dim_param)
37 isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
38 "can only reference parameters", return 0);
40 return isl_space_dim(umap->dim, type);
43 /* Return the number of parameters of "uset", where "type"
44 * is required to be set to isl_dim_param.
46 unsigned isl_union_set_dim(__isl_keep isl_union_set *uset,
47 enum isl_dim_type type)
49 return isl_union_map_dim(uset, type);
52 /* Return the id of the specified dimension.
54 __isl_give isl_id *isl_union_map_get_dim_id(__isl_keep isl_union_map *umap,
55 enum isl_dim_type type, unsigned pos)
57 if (!umap)
58 return NULL;
60 if (type != isl_dim_param)
61 isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
62 "can only reference parameters", return NULL);
64 return isl_space_get_dim_id(umap->dim, type, pos);
67 /* Is this union set a parameter domain?
69 int isl_union_set_is_params(__isl_keep isl_union_set *uset)
71 isl_set *set;
72 int params;
74 if (!uset)
75 return -1;
76 if (uset->table.n != 1)
77 return 0;
79 set = isl_set_from_union_set(isl_union_set_copy(uset));
80 params = isl_set_is_params(set);
81 isl_set_free(set);
82 return params;
85 static __isl_give isl_union_map *isl_union_map_alloc(
86 __isl_take isl_space *space, int size)
88 isl_union_map *umap;
90 space = isl_space_params(space);
91 if (!space)
92 return NULL;
94 umap = isl_calloc_type(space->ctx, isl_union_map);
95 if (!umap) {
96 isl_space_free(space);
97 return NULL;
100 umap->ref = 1;
101 umap->dim = space;
102 if (isl_hash_table_init(space->ctx, &umap->table, size) < 0)
103 return isl_union_map_free(umap);
105 return umap;
108 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
110 return isl_union_map_alloc(dim, 16);
113 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
115 return isl_union_map_empty(dim);
118 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
120 return umap ? umap->dim->ctx : NULL;
123 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
125 return uset ? uset->dim->ctx : NULL;
128 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
130 if (!umap)
131 return NULL;
132 return isl_space_copy(umap->dim);
135 /* Return the position of the parameter with the given name
136 * in "umap".
137 * Return -1 if no such dimension can be found.
139 int isl_union_map_find_dim_by_name(__isl_keep isl_union_map *umap,
140 enum isl_dim_type type, const char *name)
142 if (!umap)
143 return -1;
144 return isl_space_find_dim_by_name(umap->dim, type, name);
147 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
149 return isl_union_map_get_space(uset);
152 static int free_umap_entry(void **entry, void *user)
154 isl_map *map = *entry;
155 isl_map_free(map);
156 return 0;
159 static int add_map(__isl_take isl_map *map, void *user)
161 isl_union_map **umap = (isl_union_map **)user;
163 *umap = isl_union_map_add_map(*umap, map);
165 return 0;
168 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
170 isl_union_map *dup;
172 if (!umap)
173 return NULL;
175 dup = isl_union_map_empty(isl_space_copy(umap->dim));
176 if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
177 goto error;
178 return dup;
179 error:
180 isl_union_map_free(dup);
181 return NULL;
184 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
186 if (!umap)
187 return NULL;
189 if (umap->ref == 1)
190 return umap;
191 umap->ref--;
192 return isl_union_map_dup(umap);
195 struct isl_union_align {
196 isl_reordering *exp;
197 isl_union_map *res;
200 static int align_entry(void **entry, void *user)
202 isl_map *map = *entry;
203 isl_reordering *exp;
204 struct isl_union_align *data = user;
206 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
207 isl_map_get_space(map));
209 data->res = isl_union_map_add_map(data->res,
210 isl_map_realign(isl_map_copy(map), exp));
212 return 0;
215 /* Align the parameters of umap along those of model.
216 * The result has the parameters of model first, in the same order
217 * as they appear in model, followed by any remaining parameters of
218 * umap that do not appear in model.
220 __isl_give isl_union_map *isl_union_map_align_params(
221 __isl_take isl_union_map *umap, __isl_take isl_space *model)
223 struct isl_union_align data = { NULL, NULL };
225 if (!umap || !model)
226 goto error;
228 if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
229 isl_space_free(model);
230 return umap;
233 model = isl_space_params(model);
234 data.exp = isl_parameter_alignment_reordering(umap->dim, model);
235 if (!data.exp)
236 goto error;
238 data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
239 umap->table.n);
240 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
241 &align_entry, &data) < 0)
242 goto error;
244 isl_reordering_free(data.exp);
245 isl_union_map_free(umap);
246 isl_space_free(model);
247 return data.res;
248 error:
249 isl_reordering_free(data.exp);
250 isl_union_map_free(umap);
251 isl_union_map_free(data.res);
252 isl_space_free(model);
253 return NULL;
256 __isl_give isl_union_set *isl_union_set_align_params(
257 __isl_take isl_union_set *uset, __isl_take isl_space *model)
259 return isl_union_map_align_params(uset, model);
262 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
263 __isl_take isl_union_map *umap2)
265 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
266 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
268 umap1 = isl_union_map_cow(umap1);
270 if (!umap1 || !umap2)
271 goto error;
273 if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
274 goto error;
276 isl_union_map_free(umap2);
278 return umap1;
279 error:
280 isl_union_map_free(umap1);
281 isl_union_map_free(umap2);
282 return NULL;
285 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
286 __isl_take isl_union_set *uset2)
288 return isl_union_map_union(uset1, uset2);
291 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
293 if (!umap)
294 return NULL;
296 umap->ref++;
297 return umap;
300 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
302 return isl_union_map_copy(uset);
305 __isl_null isl_union_map *isl_union_map_free(__isl_take isl_union_map *umap)
307 if (!umap)
308 return NULL;
310 if (--umap->ref > 0)
311 return NULL;
313 isl_hash_table_foreach(umap->dim->ctx, &umap->table,
314 &free_umap_entry, NULL);
315 isl_hash_table_clear(&umap->table);
316 isl_space_free(umap->dim);
317 free(umap);
318 return NULL;
321 __isl_null isl_union_set *isl_union_set_free(__isl_take isl_union_set *uset)
323 return isl_union_map_free(uset);
326 static int has_dim(const void *entry, const void *val)
328 isl_map *map = (isl_map *)entry;
329 isl_space *dim = (isl_space *)val;
331 return isl_space_is_equal(map->dim, dim);
334 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
335 __isl_take isl_map *map)
337 uint32_t hash;
338 struct isl_hash_table_entry *entry;
340 if (!map || !umap)
341 goto error;
343 if (isl_map_plain_is_empty(map)) {
344 isl_map_free(map);
345 return umap;
348 if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
349 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
350 map = isl_map_align_params(map, isl_union_map_get_space(umap));
353 umap = isl_union_map_cow(umap);
355 if (!map || !umap)
356 goto error;
358 hash = isl_space_get_hash(map->dim);
359 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
360 &has_dim, map->dim, 1);
361 if (!entry)
362 goto error;
364 if (!entry->data)
365 entry->data = map;
366 else {
367 entry->data = isl_map_union(entry->data, isl_map_copy(map));
368 if (!entry->data)
369 goto error;
370 isl_map_free(map);
373 return umap;
374 error:
375 isl_map_free(map);
376 isl_union_map_free(umap);
377 return NULL;
380 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
381 __isl_take isl_set *set)
383 return isl_union_map_add_map(uset, (isl_map *)set);
386 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
388 isl_space *dim;
389 isl_union_map *umap;
391 if (!map)
392 return NULL;
394 dim = isl_map_get_space(map);
395 dim = isl_space_params(dim);
396 umap = isl_union_map_empty(dim);
397 umap = isl_union_map_add_map(umap, map);
399 return umap;
402 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
404 return isl_union_map_from_map((isl_map *)set);
407 __isl_give isl_union_map *isl_union_map_from_basic_map(
408 __isl_take isl_basic_map *bmap)
410 return isl_union_map_from_map(isl_map_from_basic_map(bmap));
413 __isl_give isl_union_set *isl_union_set_from_basic_set(
414 __isl_take isl_basic_set *bset)
416 return isl_union_map_from_basic_map(bset);
419 struct isl_union_map_foreach_data
421 int (*fn)(__isl_take isl_map *map, void *user);
422 void *user;
425 static int call_on_copy(void **entry, void *user)
427 isl_map *map = *entry;
428 struct isl_union_map_foreach_data *data;
429 data = (struct isl_union_map_foreach_data *)user;
431 return data->fn(isl_map_copy(map), data->user);
434 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
436 return umap ? umap->table.n : 0;
439 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
441 return uset ? uset->table.n : 0;
444 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
445 int (*fn)(__isl_take isl_map *map, void *user), void *user)
447 struct isl_union_map_foreach_data data = { fn, user };
449 if (!umap)
450 return -1;
452 return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
453 &call_on_copy, &data);
456 static int copy_map(void **entry, void *user)
458 isl_map *map = *entry;
459 isl_map **map_p = user;
461 *map_p = isl_map_copy(map);
463 return -1;
466 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
468 isl_ctx *ctx;
469 isl_map *map = NULL;
471 if (!umap)
472 return NULL;
473 ctx = isl_union_map_get_ctx(umap);
474 if (umap->table.n != 1)
475 isl_die(ctx, isl_error_invalid,
476 "union map needs to contain elements in exactly "
477 "one space", goto error);
479 isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
481 isl_union_map_free(umap);
483 return map;
484 error:
485 isl_union_map_free(umap);
486 return NULL;
489 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
491 return isl_map_from_union_map(uset);
494 /* Extract the map in "umap" that lives in the given space (ignoring
495 * parameters).
497 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
498 __isl_take isl_space *space)
500 uint32_t hash;
501 struct isl_hash_table_entry *entry;
503 space = isl_space_drop_dims(space, isl_dim_param,
504 0, isl_space_dim(space, isl_dim_param));
505 space = isl_space_align_params(space, isl_union_map_get_space(umap));
506 if (!umap || !space)
507 goto error;
509 hash = isl_space_get_hash(space);
510 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
511 &has_dim, space, 0);
512 if (!entry)
513 return isl_map_empty(space);
514 isl_space_free(space);
515 return isl_map_copy(entry->data);
516 error:
517 isl_space_free(space);
518 return NULL;
521 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
522 __isl_take isl_space *dim)
524 return (isl_set *)isl_union_map_extract_map(uset, dim);
527 /* Check if umap contains a map in the given space.
529 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
530 __isl_keep isl_space *dim)
532 uint32_t hash;
533 struct isl_hash_table_entry *entry;
535 if (!umap || !dim)
536 return -1;
538 hash = isl_space_get_hash(dim);
539 entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
540 &has_dim, dim, 0);
541 return !!entry;
544 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
545 __isl_keep isl_space *dim)
547 return isl_union_map_contains(uset, dim);
550 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
551 int (*fn)(__isl_take isl_set *set, void *user), void *user)
553 return isl_union_map_foreach_map(uset,
554 (int(*)(__isl_take isl_map *, void*))fn, user);
557 struct isl_union_set_foreach_point_data {
558 int (*fn)(__isl_take isl_point *pnt, void *user);
559 void *user;
562 static int foreach_point(__isl_take isl_set *set, void *user)
564 struct isl_union_set_foreach_point_data *data = user;
565 int r;
567 r = isl_set_foreach_point(set, data->fn, data->user);
568 isl_set_free(set);
570 return r;
573 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
574 int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
576 struct isl_union_set_foreach_point_data data = { fn, user };
577 return isl_union_set_foreach_set(uset, &foreach_point, &data);
580 struct isl_union_map_gen_bin_data {
581 isl_union_map *umap2;
582 isl_union_map *res;
585 static int subtract_entry(void **entry, void *user)
587 struct isl_union_map_gen_bin_data *data = user;
588 uint32_t hash;
589 struct isl_hash_table_entry *entry2;
590 isl_map *map = *entry;
592 hash = isl_space_get_hash(map->dim);
593 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
594 hash, &has_dim, map->dim, 0);
595 map = isl_map_copy(map);
596 if (entry2) {
597 int empty;
598 map = isl_map_subtract(map, isl_map_copy(entry2->data));
600 empty = isl_map_is_empty(map);
601 if (empty < 0) {
602 isl_map_free(map);
603 return -1;
605 if (empty) {
606 isl_map_free(map);
607 return 0;
610 data->res = isl_union_map_add_map(data->res, map);
612 return 0;
615 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
616 __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
618 struct isl_union_map_gen_bin_data data = { NULL, NULL };
620 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
621 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
623 if (!umap1 || !umap2)
624 goto error;
626 data.umap2 = umap2;
627 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
628 umap1->table.n);
629 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
630 fn, &data) < 0)
631 goto error;
633 isl_union_map_free(umap1);
634 isl_union_map_free(umap2);
635 return data.res;
636 error:
637 isl_union_map_free(umap1);
638 isl_union_map_free(umap2);
639 isl_union_map_free(data.res);
640 return NULL;
643 __isl_give isl_union_map *isl_union_map_subtract(
644 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
646 return gen_bin_op(umap1, umap2, &subtract_entry);
649 __isl_give isl_union_set *isl_union_set_subtract(
650 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
652 return isl_union_map_subtract(uset1, uset2);
655 struct isl_union_map_gen_bin_set_data {
656 isl_set *set;
657 isl_union_map *res;
660 static int intersect_params_entry(void **entry, void *user)
662 struct isl_union_map_gen_bin_set_data *data = user;
663 isl_map *map = *entry;
664 int empty;
666 map = isl_map_copy(map);
667 map = isl_map_intersect_params(map, isl_set_copy(data->set));
669 empty = isl_map_is_empty(map);
670 if (empty < 0) {
671 isl_map_free(map);
672 return -1;
675 data->res = isl_union_map_add_map(data->res, map);
677 return 0;
680 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
681 __isl_take isl_set *set, int (*fn)(void **, void *))
683 struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
685 umap = isl_union_map_align_params(umap, isl_set_get_space(set));
686 set = isl_set_align_params(set, isl_union_map_get_space(umap));
688 if (!umap || !set)
689 goto error;
691 data.set = set;
692 data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
693 umap->table.n);
694 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
695 fn, &data) < 0)
696 goto error;
698 isl_union_map_free(umap);
699 isl_set_free(set);
700 return data.res;
701 error:
702 isl_union_map_free(umap);
703 isl_set_free(set);
704 isl_union_map_free(data.res);
705 return NULL;
708 /* Intersect "umap" with the parameter domain "set".
710 * If "set" does not have any constraints, then we can return immediately.
712 __isl_give isl_union_map *isl_union_map_intersect_params(
713 __isl_take isl_union_map *umap, __isl_take isl_set *set)
715 int is_universe;
717 is_universe = isl_set_plain_is_universe(set);
718 if (is_universe < 0)
719 goto error;
720 if (is_universe) {
721 isl_set_free(set);
722 return umap;
725 return gen_bin_set_op(umap, set, &intersect_params_entry);
726 error:
727 isl_union_map_free(umap);
728 isl_set_free(set);
729 return NULL;
732 __isl_give isl_union_set *isl_union_set_intersect_params(
733 __isl_take isl_union_set *uset, __isl_take isl_set *set)
735 return isl_union_map_intersect_params(uset, set);
738 static __isl_give isl_union_map *union_map_intersect_params(
739 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
741 return isl_union_map_intersect_params(umap,
742 isl_set_from_union_set(uset));
745 static __isl_give isl_union_map *union_map_gist_params(
746 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
748 return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
751 struct isl_union_map_match_bin_data {
752 isl_union_map *umap2;
753 isl_union_map *res;
754 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
757 static int match_bin_entry(void **entry, void *user)
759 struct isl_union_map_match_bin_data *data = user;
760 uint32_t hash;
761 struct isl_hash_table_entry *entry2;
762 isl_map *map = *entry;
763 int empty;
765 hash = isl_space_get_hash(map->dim);
766 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
767 hash, &has_dim, map->dim, 0);
768 if (!entry2)
769 return 0;
771 map = isl_map_copy(map);
772 map = data->fn(map, isl_map_copy(entry2->data));
774 empty = isl_map_is_empty(map);
775 if (empty < 0) {
776 isl_map_free(map);
777 return -1;
779 if (empty) {
780 isl_map_free(map);
781 return 0;
784 data->res = isl_union_map_add_map(data->res, map);
786 return 0;
789 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
790 __isl_take isl_union_map *umap2,
791 __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
793 struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
795 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
796 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
798 if (!umap1 || !umap2)
799 goto error;
801 data.umap2 = umap2;
802 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
803 umap1->table.n);
804 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
805 &match_bin_entry, &data) < 0)
806 goto error;
808 isl_union_map_free(umap1);
809 isl_union_map_free(umap2);
810 return data.res;
811 error:
812 isl_union_map_free(umap1);
813 isl_union_map_free(umap2);
814 isl_union_map_free(data.res);
815 return NULL;
818 __isl_give isl_union_map *isl_union_map_intersect(
819 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
821 return match_bin_op(umap1, umap2, &isl_map_intersect);
824 /* Compute the intersection of the two union_sets.
825 * As a special case, if exactly one of the two union_sets
826 * is a parameter domain, then intersect the parameter domain
827 * of the other one with this set.
829 __isl_give isl_union_set *isl_union_set_intersect(
830 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
832 int p1, p2;
834 p1 = isl_union_set_is_params(uset1);
835 p2 = isl_union_set_is_params(uset2);
836 if (p1 < 0 || p2 < 0)
837 goto error;
838 if (!p1 && p2)
839 return union_map_intersect_params(uset1, uset2);
840 if (p1 && !p2)
841 return union_map_intersect_params(uset2, uset1);
842 return isl_union_map_intersect(uset1, uset2);
843 error:
844 isl_union_set_free(uset1);
845 isl_union_set_free(uset2);
846 return NULL;
849 static int gist_params_entry(void **entry, void *user)
851 struct isl_union_map_gen_bin_set_data *data = user;
852 isl_map *map = *entry;
853 int empty;
855 map = isl_map_copy(map);
856 map = isl_map_gist_params(map, isl_set_copy(data->set));
858 empty = isl_map_is_empty(map);
859 if (empty < 0) {
860 isl_map_free(map);
861 return -1;
864 data->res = isl_union_map_add_map(data->res, map);
866 return 0;
869 __isl_give isl_union_map *isl_union_map_gist_params(
870 __isl_take isl_union_map *umap, __isl_take isl_set *set)
872 return gen_bin_set_op(umap, set, &gist_params_entry);
875 __isl_give isl_union_set *isl_union_set_gist_params(
876 __isl_take isl_union_set *uset, __isl_take isl_set *set)
878 return isl_union_map_gist_params(uset, set);
881 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
882 __isl_take isl_union_map *context)
884 return match_bin_op(umap, context, &isl_map_gist);
887 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
888 __isl_take isl_union_set *context)
890 if (isl_union_set_is_params(context))
891 return union_map_gist_params(uset, context);
892 return isl_union_map_gist(uset, context);
895 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
896 __isl_take isl_map *set2)
898 return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
901 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
902 __isl_take isl_map *set2)
904 return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
907 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
908 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
910 return match_bin_op(uset1, uset2, &lex_lt_set);
913 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
914 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
916 return match_bin_op(uset1, uset2, &lex_le_set);
919 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
920 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
922 return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
925 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
926 __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
928 return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
931 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
932 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
934 return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
937 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
938 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
940 return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
943 static int intersect_domain_entry(void **entry, void *user)
945 struct isl_union_map_gen_bin_data *data = user;
946 uint32_t hash;
947 struct isl_hash_table_entry *entry2;
948 isl_space *dim;
949 isl_map *map = *entry;
950 int empty;
952 dim = isl_map_get_space(map);
953 dim = isl_space_domain(dim);
954 hash = isl_space_get_hash(dim);
955 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
956 hash, &has_dim, dim, 0);
957 isl_space_free(dim);
958 if (!entry2)
959 return 0;
961 map = isl_map_copy(map);
962 map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
964 empty = isl_map_is_empty(map);
965 if (empty < 0) {
966 isl_map_free(map);
967 return -1;
969 if (empty) {
970 isl_map_free(map);
971 return 0;
974 data->res = isl_union_map_add_map(data->res, map);
976 return 0;
979 /* Intersect the domain of "umap" with "uset".
980 * If "uset" is a parameters domain, then intersect the parameter
981 * domain of "umap" with this set.
983 __isl_give isl_union_map *isl_union_map_intersect_domain(
984 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
986 if (isl_union_set_is_params(uset))
987 return union_map_intersect_params(umap, uset);
988 return gen_bin_op(umap, uset, &intersect_domain_entry);
991 /* Remove the elements of data->umap2 from the domain of *entry
992 * and add the result to data->res.
994 static int subtract_domain_entry(void **entry, void *user)
996 struct isl_union_map_gen_bin_data *data = user;
997 uint32_t hash;
998 struct isl_hash_table_entry *entry2;
999 isl_space *dim;
1000 isl_map *map = *entry;
1001 int empty;
1003 dim = isl_map_get_space(map);
1004 dim = isl_space_domain(dim);
1005 hash = isl_space_get_hash(dim);
1006 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1007 hash, &has_dim, dim, 0);
1008 isl_space_free(dim);
1010 map = isl_map_copy(map);
1012 if (!entry2) {
1013 data->res = isl_union_map_add_map(data->res, map);
1014 return 0;
1017 map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
1019 empty = isl_map_is_empty(map);
1020 if (empty < 0) {
1021 isl_map_free(map);
1022 return -1;
1024 if (empty) {
1025 isl_map_free(map);
1026 return 0;
1029 data->res = isl_union_map_add_map(data->res, map);
1031 return 0;
1034 /* Remove the elements of "uset" from the domain of "umap".
1036 __isl_give isl_union_map *isl_union_map_subtract_domain(
1037 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1039 return gen_bin_op(umap, dom, &subtract_domain_entry);
1042 /* Remove the elements of data->umap2 from the range of *entry
1043 * and add the result to data->res.
1045 static int subtract_range_entry(void **entry, void *user)
1047 struct isl_union_map_gen_bin_data *data = user;
1048 uint32_t hash;
1049 struct isl_hash_table_entry *entry2;
1050 isl_space *space;
1051 isl_map *map = *entry;
1052 int empty;
1054 space = isl_map_get_space(map);
1055 space = isl_space_range(space);
1056 hash = isl_space_get_hash(space);
1057 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1058 hash, &has_dim, space, 0);
1059 isl_space_free(space);
1061 map = isl_map_copy(map);
1063 if (!entry2) {
1064 data->res = isl_union_map_add_map(data->res, map);
1065 return 0;
1068 map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
1070 empty = isl_map_is_empty(map);
1071 if (empty < 0) {
1072 isl_map_free(map);
1073 return -1;
1075 if (empty) {
1076 isl_map_free(map);
1077 return 0;
1080 data->res = isl_union_map_add_map(data->res, map);
1082 return 0;
1085 /* Remove the elements of "uset" from the range of "umap".
1087 __isl_give isl_union_map *isl_union_map_subtract_range(
1088 __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1090 return gen_bin_op(umap, dom, &subtract_range_entry);
1093 static int gist_domain_entry(void **entry, void *user)
1095 struct isl_union_map_gen_bin_data *data = user;
1096 uint32_t hash;
1097 struct isl_hash_table_entry *entry2;
1098 isl_space *dim;
1099 isl_map *map = *entry;
1100 int empty;
1102 dim = isl_map_get_space(map);
1103 dim = isl_space_domain(dim);
1104 hash = isl_space_get_hash(dim);
1105 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1106 hash, &has_dim, dim, 0);
1107 isl_space_free(dim);
1108 if (!entry2)
1109 return 0;
1111 map = isl_map_copy(map);
1112 map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1114 empty = isl_map_is_empty(map);
1115 if (empty < 0) {
1116 isl_map_free(map);
1117 return -1;
1120 data->res = isl_union_map_add_map(data->res, map);
1122 return 0;
1125 /* Compute the gist of "umap" with respect to the domain "uset".
1126 * If "uset" is a parameters domain, then compute the gist
1127 * with respect to this parameter domain.
1129 __isl_give isl_union_map *isl_union_map_gist_domain(
1130 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1132 if (isl_union_set_is_params(uset))
1133 return union_map_gist_params(umap, uset);
1134 return gen_bin_op(umap, uset, &gist_domain_entry);
1137 static int gist_range_entry(void **entry, void *user)
1139 struct isl_union_map_gen_bin_data *data = user;
1140 uint32_t hash;
1141 struct isl_hash_table_entry *entry2;
1142 isl_space *space;
1143 isl_map *map = *entry;
1144 int empty;
1146 space = isl_map_get_space(map);
1147 space = isl_space_range(space);
1148 hash = isl_space_get_hash(space);
1149 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1150 hash, &has_dim, space, 0);
1151 isl_space_free(space);
1152 if (!entry2)
1153 return 0;
1155 map = isl_map_copy(map);
1156 map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1158 empty = isl_map_is_empty(map);
1159 if (empty < 0) {
1160 isl_map_free(map);
1161 return -1;
1164 data->res = isl_union_map_add_map(data->res, map);
1166 return 0;
1169 /* Compute the gist of "umap" with respect to the range "uset".
1171 __isl_give isl_union_map *isl_union_map_gist_range(
1172 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1174 return gen_bin_op(umap, uset, &gist_range_entry);
1177 static int intersect_range_entry(void **entry, void *user)
1179 struct isl_union_map_gen_bin_data *data = user;
1180 uint32_t hash;
1181 struct isl_hash_table_entry *entry2;
1182 isl_space *dim;
1183 isl_map *map = *entry;
1184 int empty;
1186 dim = isl_map_get_space(map);
1187 dim = isl_space_range(dim);
1188 hash = isl_space_get_hash(dim);
1189 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1190 hash, &has_dim, dim, 0);
1191 isl_space_free(dim);
1192 if (!entry2)
1193 return 0;
1195 map = isl_map_copy(map);
1196 map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1198 empty = isl_map_is_empty(map);
1199 if (empty < 0) {
1200 isl_map_free(map);
1201 return -1;
1203 if (empty) {
1204 isl_map_free(map);
1205 return 0;
1208 data->res = isl_union_map_add_map(data->res, map);
1210 return 0;
1213 __isl_give isl_union_map *isl_union_map_intersect_range(
1214 __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1216 return gen_bin_op(umap, uset, &intersect_range_entry);
1219 struct isl_union_map_bin_data {
1220 isl_union_map *umap2;
1221 isl_union_map *res;
1222 isl_map *map;
1223 int (*fn)(void **entry, void *user);
1226 static int apply_range_entry(void **entry, void *user)
1228 struct isl_union_map_bin_data *data = user;
1229 isl_map *map2 = *entry;
1230 int empty;
1232 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1233 map2->dim, isl_dim_in))
1234 return 0;
1236 map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1238 empty = isl_map_is_empty(map2);
1239 if (empty < 0) {
1240 isl_map_free(map2);
1241 return -1;
1243 if (empty) {
1244 isl_map_free(map2);
1245 return 0;
1248 data->res = isl_union_map_add_map(data->res, map2);
1250 return 0;
1253 static int bin_entry(void **entry, void *user)
1255 struct isl_union_map_bin_data *data = user;
1256 isl_map *map = *entry;
1258 data->map = map;
1259 if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1260 data->fn, data) < 0)
1261 return -1;
1263 return 0;
1266 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1267 __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1269 struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1271 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1272 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1274 if (!umap1 || !umap2)
1275 goto error;
1277 data.umap2 = umap2;
1278 data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1279 umap1->table.n);
1280 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1281 &bin_entry, &data) < 0)
1282 goto error;
1284 isl_union_map_free(umap1);
1285 isl_union_map_free(umap2);
1286 return data.res;
1287 error:
1288 isl_union_map_free(umap1);
1289 isl_union_map_free(umap2);
1290 isl_union_map_free(data.res);
1291 return NULL;
1294 __isl_give isl_union_map *isl_union_map_apply_range(
1295 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1297 return bin_op(umap1, umap2, &apply_range_entry);
1300 __isl_give isl_union_map *isl_union_map_apply_domain(
1301 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1303 umap1 = isl_union_map_reverse(umap1);
1304 umap1 = isl_union_map_apply_range(umap1, umap2);
1305 return isl_union_map_reverse(umap1);
1308 __isl_give isl_union_set *isl_union_set_apply(
1309 __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1311 return isl_union_map_apply_range(uset, umap);
1314 static int map_lex_lt_entry(void **entry, void *user)
1316 struct isl_union_map_bin_data *data = user;
1317 isl_map *map2 = *entry;
1319 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1320 map2->dim, isl_dim_out))
1321 return 0;
1323 map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1325 data->res = isl_union_map_add_map(data->res, map2);
1327 return 0;
1330 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1331 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1333 return bin_op(umap1, umap2, &map_lex_lt_entry);
1336 static int map_lex_le_entry(void **entry, void *user)
1338 struct isl_union_map_bin_data *data = user;
1339 isl_map *map2 = *entry;
1341 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1342 map2->dim, isl_dim_out))
1343 return 0;
1345 map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1347 data->res = isl_union_map_add_map(data->res, map2);
1349 return 0;
1352 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1353 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1355 return bin_op(umap1, umap2, &map_lex_le_entry);
1358 static int product_entry(void **entry, void *user)
1360 struct isl_union_map_bin_data *data = user;
1361 isl_map *map2 = *entry;
1363 map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1365 data->res = isl_union_map_add_map(data->res, map2);
1367 return 0;
1370 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1371 __isl_take isl_union_map *umap2)
1373 return bin_op(umap1, umap2, &product_entry);
1376 static int set_product_entry(void **entry, void *user)
1378 struct isl_union_map_bin_data *data = user;
1379 isl_set *set2 = *entry;
1381 set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1383 data->res = isl_union_set_add_set(data->res, set2);
1385 return 0;
1388 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1389 __isl_take isl_union_set *uset2)
1391 return bin_op(uset1, uset2, &set_product_entry);
1394 static int domain_product_entry(void **entry, void *user)
1396 struct isl_union_map_bin_data *data = user;
1397 isl_map *map2 = *entry;
1399 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1400 map2->dim, isl_dim_out))
1401 return 0;
1403 map2 = isl_map_domain_product(isl_map_copy(data->map),
1404 isl_map_copy(map2));
1406 data->res = isl_union_map_add_map(data->res, map2);
1408 return 0;
1411 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1413 __isl_give isl_union_map *isl_union_map_domain_product(
1414 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1416 return bin_op(umap1, umap2, &domain_product_entry);
1419 static int range_product_entry(void **entry, void *user)
1421 struct isl_union_map_bin_data *data = user;
1422 isl_map *map2 = *entry;
1424 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in,
1425 map2->dim, isl_dim_in))
1426 return 0;
1428 map2 = isl_map_range_product(isl_map_copy(data->map),
1429 isl_map_copy(map2));
1431 data->res = isl_union_map_add_map(data->res, map2);
1433 return 0;
1436 __isl_give isl_union_map *isl_union_map_range_product(
1437 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1439 return bin_op(umap1, umap2, &range_product_entry);
1442 /* If data->map A -> B and "map2" C -> D have the same range space,
1443 * then add (A, C) -> (B * D) to data->res.
1445 static int flat_domain_product_entry(void **entry, void *user)
1447 struct isl_union_map_bin_data *data = user;
1448 isl_map *map2 = *entry;
1450 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out,
1451 map2->dim, isl_dim_out))
1452 return 0;
1454 map2 = isl_map_flat_domain_product(isl_map_copy(data->map),
1455 isl_map_copy(map2));
1457 data->res = isl_union_map_add_map(data->res, map2);
1459 return 0;
1462 /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D).
1464 __isl_give isl_union_map *isl_union_map_flat_domain_product(
1465 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1467 return bin_op(umap1, umap2, &flat_domain_product_entry);
1470 static int flat_range_product_entry(void **entry, void *user)
1472 struct isl_union_map_bin_data *data = user;
1473 isl_map *map2 = *entry;
1475 if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in,
1476 map2->dim, isl_dim_in))
1477 return 0;
1479 map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1480 isl_map_copy(map2));
1482 data->res = isl_union_map_add_map(data->res, map2);
1484 return 0;
1487 __isl_give isl_union_map *isl_union_map_flat_range_product(
1488 __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1490 return bin_op(umap1, umap2, &flat_range_product_entry);
1493 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1494 int (*fn)(void **, void *))
1496 isl_union_set *res;
1498 if (!umap)
1499 return NULL;
1501 res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1502 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1503 goto error;
1505 isl_union_map_free(umap);
1506 return res;
1507 error:
1508 isl_union_map_free(umap);
1509 isl_union_set_free(res);
1510 return NULL;
1513 static int from_range_entry(void **entry, void *user)
1515 isl_map *set = *entry;
1516 isl_union_set **res = user;
1518 *res = isl_union_map_add_map(*res,
1519 isl_map_from_range(isl_set_copy(set)));
1521 return 0;
1524 __isl_give isl_union_map *isl_union_map_from_range(
1525 __isl_take isl_union_set *uset)
1527 return cond_un_op(uset, &from_range_entry);
1530 __isl_give isl_union_map *isl_union_map_from_domain(
1531 __isl_take isl_union_set *uset)
1533 return isl_union_map_reverse(isl_union_map_from_range(uset));
1536 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1537 __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1539 return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1540 isl_union_map_from_range(range));
1543 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1544 int (*fn)(void **, void *))
1546 umap = isl_union_map_cow(umap);
1547 if (!umap)
1548 return NULL;
1550 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1551 goto error;
1553 return umap;
1554 error:
1555 isl_union_map_free(umap);
1556 return NULL;
1559 static int affine_entry(void **entry, void *user)
1561 isl_map **map = (isl_map **)entry;
1563 *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1565 return *map ? 0 : -1;
1568 __isl_give isl_union_map *isl_union_map_affine_hull(
1569 __isl_take isl_union_map *umap)
1571 return un_op(umap, &affine_entry);
1574 __isl_give isl_union_set *isl_union_set_affine_hull(
1575 __isl_take isl_union_set *uset)
1577 return isl_union_map_affine_hull(uset);
1580 static int polyhedral_entry(void **entry, void *user)
1582 isl_map **map = (isl_map **)entry;
1584 *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1586 return *map ? 0 : -1;
1589 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1590 __isl_take isl_union_map *umap)
1592 return un_op(umap, &polyhedral_entry);
1595 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1596 __isl_take isl_union_set *uset)
1598 return isl_union_map_polyhedral_hull(uset);
1601 static int simple_entry(void **entry, void *user)
1603 isl_map **map = (isl_map **)entry;
1605 *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1607 return *map ? 0 : -1;
1610 __isl_give isl_union_map *isl_union_map_simple_hull(
1611 __isl_take isl_union_map *umap)
1613 return un_op(umap, &simple_entry);
1616 __isl_give isl_union_set *isl_union_set_simple_hull(
1617 __isl_take isl_union_set *uset)
1619 return isl_union_map_simple_hull(uset);
1622 static int inplace_entry(void **entry, void *user)
1624 __isl_give isl_map *(*fn)(__isl_take isl_map *);
1625 isl_map **map = (isl_map **)entry;
1626 isl_map *copy;
1628 fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1629 copy = fn(isl_map_copy(*map));
1630 if (!copy)
1631 return -1;
1633 isl_map_free(*map);
1634 *map = copy;
1636 return 0;
1639 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1640 __isl_give isl_map *(*fn)(__isl_take isl_map *))
1642 if (!umap)
1643 return NULL;
1645 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1646 &inplace_entry, &fn) < 0)
1647 goto error;
1649 return umap;
1650 error:
1651 isl_union_map_free(umap);
1652 return NULL;
1655 /* Remove redundant constraints in each of the basic maps of "umap".
1656 * Since removing redundant constraints does not change the meaning
1657 * or the space, the operation can be performed in-place.
1659 __isl_give isl_union_map *isl_union_map_remove_redundancies(
1660 __isl_take isl_union_map *umap)
1662 return inplace(umap, &isl_map_remove_redundancies);
1665 /* Remove redundant constraints in each of the basic sets of "uset".
1667 __isl_give isl_union_set *isl_union_set_remove_redundancies(
1668 __isl_take isl_union_set *uset)
1670 return isl_union_map_remove_redundancies(uset);
1673 __isl_give isl_union_map *isl_union_map_coalesce(
1674 __isl_take isl_union_map *umap)
1676 return inplace(umap, &isl_map_coalesce);
1679 __isl_give isl_union_set *isl_union_set_coalesce(
1680 __isl_take isl_union_set *uset)
1682 return isl_union_map_coalesce(uset);
1685 __isl_give isl_union_map *isl_union_map_detect_equalities(
1686 __isl_take isl_union_map *umap)
1688 return inplace(umap, &isl_map_detect_equalities);
1691 __isl_give isl_union_set *isl_union_set_detect_equalities(
1692 __isl_take isl_union_set *uset)
1694 return isl_union_map_detect_equalities(uset);
1697 __isl_give isl_union_map *isl_union_map_compute_divs(
1698 __isl_take isl_union_map *umap)
1700 return inplace(umap, &isl_map_compute_divs);
1703 __isl_give isl_union_set *isl_union_set_compute_divs(
1704 __isl_take isl_union_set *uset)
1706 return isl_union_map_compute_divs(uset);
1709 static int lexmin_entry(void **entry, void *user)
1711 isl_map **map = (isl_map **)entry;
1713 *map = isl_map_lexmin(*map);
1715 return *map ? 0 : -1;
1718 __isl_give isl_union_map *isl_union_map_lexmin(
1719 __isl_take isl_union_map *umap)
1721 return un_op(umap, &lexmin_entry);
1724 __isl_give isl_union_set *isl_union_set_lexmin(
1725 __isl_take isl_union_set *uset)
1727 return isl_union_map_lexmin(uset);
1730 static int lexmax_entry(void **entry, void *user)
1732 isl_map **map = (isl_map **)entry;
1734 *map = isl_map_lexmax(*map);
1736 return *map ? 0 : -1;
1739 __isl_give isl_union_map *isl_union_map_lexmax(
1740 __isl_take isl_union_map *umap)
1742 return un_op(umap, &lexmax_entry);
1745 __isl_give isl_union_set *isl_union_set_lexmax(
1746 __isl_take isl_union_set *uset)
1748 return isl_union_map_lexmax(uset);
1751 static int universe_entry(void **entry, void *user)
1753 isl_map *map = *entry;
1754 isl_union_map **res = user;
1756 map = isl_map_universe(isl_map_get_space(map));
1757 *res = isl_union_map_add_map(*res, map);
1759 return 0;
1762 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1764 return cond_un_op(umap, &universe_entry);
1767 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1769 return isl_union_map_universe(uset);
1772 static int reverse_entry(void **entry, void *user)
1774 isl_map *map = *entry;
1775 isl_union_map **res = user;
1777 *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1779 return 0;
1782 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1784 return cond_un_op(umap, &reverse_entry);
1787 static int params_entry(void **entry, void *user)
1789 isl_map *map = *entry;
1790 isl_union_set **res = user;
1792 *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1794 return 0;
1797 /* Compute the parameter domain of the given union map.
1799 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1801 int empty;
1803 empty = isl_union_map_is_empty(umap);
1804 if (empty < 0)
1805 goto error;
1806 if (empty) {
1807 isl_space *space;
1808 space = isl_union_map_get_space(umap);
1809 isl_union_map_free(umap);
1810 return isl_set_empty(space);
1812 return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1813 error:
1814 isl_union_map_free(umap);
1815 return NULL;
1818 /* Compute the parameter domain of the given union set.
1820 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1822 return isl_union_map_params(uset);
1825 static int domain_entry(void **entry, void *user)
1827 isl_map *map = *entry;
1828 isl_union_set **res = user;
1830 *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1832 return 0;
1835 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1837 return cond_un_op(umap, &domain_entry);
1840 static int range_entry(void **entry, void *user)
1842 isl_map *map = *entry;
1843 isl_union_set **res = user;
1845 *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1847 return 0;
1850 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1852 return cond_un_op(umap, &range_entry);
1855 static int domain_map_entry(void **entry, void *user)
1857 isl_map *map = *entry;
1858 isl_union_set **res = user;
1860 *res = isl_union_map_add_map(*res,
1861 isl_map_domain_map(isl_map_copy(map)));
1863 return 0;
1866 __isl_give isl_union_map *isl_union_map_domain_map(
1867 __isl_take isl_union_map *umap)
1869 return cond_un_op(umap, &domain_map_entry);
1872 /* Construct an isl_pw_multi_aff that maps "map" to its domain and
1873 * add the result to "res".
1875 static int domain_map_upma(__isl_take isl_map *map, void *user)
1877 isl_union_pw_multi_aff **res = user;
1878 isl_multi_aff *ma;
1879 isl_pw_multi_aff *pma;
1881 ma = isl_multi_aff_domain_map(isl_map_get_space(map));
1882 pma = isl_pw_multi_aff_alloc(isl_map_wrap(map), ma);
1883 *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
1885 return *res ? 0 : -1;
1889 /* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap"
1890 * to its domain.
1892 __isl_give isl_union_pw_multi_aff *isl_union_map_domain_map_union_pw_multi_aff(
1893 __isl_take isl_union_map *umap)
1895 isl_union_pw_multi_aff *res;
1897 res = isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap));
1898 if (isl_union_map_foreach_map(umap, &domain_map_upma, &res) < 0)
1899 res = isl_union_pw_multi_aff_free(res);
1901 isl_union_map_free(umap);
1902 return res;
1905 static int range_map_entry(void **entry, void *user)
1907 isl_map *map = *entry;
1908 isl_union_set **res = user;
1910 *res = isl_union_map_add_map(*res,
1911 isl_map_range_map(isl_map_copy(map)));
1913 return 0;
1916 __isl_give isl_union_map *isl_union_map_range_map(
1917 __isl_take isl_union_map *umap)
1919 return cond_un_op(umap, &range_map_entry);
1922 /* Check if "set" is of the form A[B -> C].
1923 * If so, add A[B -> C] -> B to "res".
1925 static int wrapped_domain_map_entry(void **entry, void *user)
1927 isl_set *set = *entry;
1928 isl_union_set **res = user;
1929 int wrapping;
1931 wrapping = isl_set_is_wrapping(set);
1932 if (wrapping < 0)
1933 return -1;
1934 if (!wrapping)
1935 return 0;
1937 *res = isl_union_map_add_map(*res,
1938 isl_set_wrapped_domain_map(isl_set_copy(set)));
1940 return 0;
1943 /* Given a collection of wrapped maps of the form A[B -> C],
1944 * return the collection of maps A[B -> C] -> B.
1946 __isl_give isl_union_map *isl_union_set_wrapped_domain_map(
1947 __isl_take isl_union_set *uset)
1949 return cond_un_op(uset, &wrapped_domain_map_entry);
1952 static int deltas_entry(void **entry, void *user)
1954 isl_map *map = *entry;
1955 isl_union_set **res = user;
1957 if (!isl_space_tuple_is_equal(map->dim, isl_dim_in,
1958 map->dim, isl_dim_out))
1959 return 0;
1961 *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1963 return 0;
1966 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1968 return cond_un_op(umap, &deltas_entry);
1971 static int deltas_map_entry(void **entry, void *user)
1973 isl_map *map = *entry;
1974 isl_union_map **res = user;
1976 if (!isl_space_tuple_is_equal(map->dim, isl_dim_in,
1977 map->dim, isl_dim_out))
1978 return 0;
1980 *res = isl_union_map_add_map(*res,
1981 isl_map_deltas_map(isl_map_copy(map)));
1983 return 0;
1986 __isl_give isl_union_map *isl_union_map_deltas_map(
1987 __isl_take isl_union_map *umap)
1989 return cond_un_op(umap, &deltas_map_entry);
1992 static int identity_entry(void **entry, void *user)
1994 isl_set *set = *entry;
1995 isl_union_map **res = user;
1997 *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1999 return 0;
2002 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
2004 return cond_un_op(uset, &identity_entry);
2007 /* Construct an identity isl_pw_multi_aff on "set" and add it to *res.
2009 static int identity_upma(__isl_take isl_set *set, void *user)
2011 isl_union_pw_multi_aff **res = user;
2012 isl_space *space;
2013 isl_pw_multi_aff *pma;
2015 space = isl_space_map_from_set(isl_set_get_space(set));
2016 pma = isl_pw_multi_aff_identity(space);
2017 pma = isl_pw_multi_aff_intersect_domain(pma, set);
2018 *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma);
2020 return *res ? 0 : -1;
2023 /* Return an identity function on "uset" in the form
2024 * of an isl_union_pw_multi_aff.
2026 __isl_give isl_union_pw_multi_aff *isl_union_set_identity_union_pw_multi_aff(
2027 __isl_take isl_union_set *uset)
2029 isl_union_pw_multi_aff *res;
2031 res = isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset));
2032 if (isl_union_set_foreach_set(uset, &identity_upma, &res) < 0)
2033 res = isl_union_pw_multi_aff_free(res);
2035 isl_union_set_free(uset);
2036 return res;
2039 /* If "map" is of the form [A -> B] -> C, then add A -> C to "res".
2041 static int domain_factor_domain_entry(void **entry, void *user)
2043 isl_map *map = *entry;
2044 isl_union_map **res = user;
2046 if (!isl_map_domain_is_wrapping(map))
2047 return 0;
2049 *res = isl_union_map_add_map(*res,
2050 isl_map_domain_factor_domain(isl_map_copy(map)));
2052 return *res ? 0 : -1;
2055 /* For each map in "umap" of the form [A -> B] -> C,
2056 * construct the map A -> C and collect the results.
2058 __isl_give isl_union_map *isl_union_map_domain_factor_domain(
2059 __isl_take isl_union_map *umap)
2061 return cond_un_op(umap, &domain_factor_domain_entry);
2064 /* If "map" is of the form [A -> B] -> C, then add B -> C to "res".
2066 static int domain_factor_range_entry(void **entry, void *user)
2068 isl_map *map = *entry;
2069 isl_union_map **res = user;
2071 if (!isl_map_domain_is_wrapping(map))
2072 return 0;
2074 *res = isl_union_map_add_map(*res,
2075 isl_map_domain_factor_range(isl_map_copy(map)));
2077 return *res ? 0 : -1;
2080 /* For each map in "umap" of the form [A -> B] -> C,
2081 * construct the map B -> C and collect the results.
2083 __isl_give isl_union_map *isl_union_map_domain_factor_range(
2084 __isl_take isl_union_map *umap)
2086 return cond_un_op(umap, &domain_factor_range_entry);
2089 /* If "map" is of the form A -> [B -> C], then add A -> C to "res".
2091 static int range_factor_range_entry(void **entry, void *user)
2093 isl_map *map = *entry;
2094 isl_union_map **res = user;
2096 if (!isl_map_range_is_wrapping(map))
2097 return 0;
2099 *res = isl_union_map_add_map(*res,
2100 isl_map_range_factor_range(isl_map_copy(map)));
2102 return *res ? 0 : -1;
2105 /* For each map in "umap" of the form A -> [B -> C],
2106 * construct the map A -> C and collect the results.
2108 __isl_give isl_union_map *isl_union_map_range_factor_range(
2109 __isl_take isl_union_map *umap)
2111 return cond_un_op(umap, &range_factor_range_entry);
2114 /* If "map" is of the form [A -> B] -> [C -> D], then add A -> C to "res".
2116 static int factor_domain_entry(void **entry, void *user)
2118 isl_map *map = *entry;
2119 isl_union_map **res = user;
2121 if (!isl_map_domain_is_wrapping(map) || !isl_map_range_is_wrapping(map))
2122 return 0;
2124 *res = isl_union_map_add_map(*res,
2125 isl_map_factor_domain(isl_map_copy(map)));
2127 return *res ? 0 : -1;
2130 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2131 * construct the map A -> C and collect the results.
2133 __isl_give isl_union_map *isl_union_map_factor_domain(
2134 __isl_take isl_union_map *umap)
2136 return cond_un_op(umap, &factor_domain_entry);
2139 /* If "map" is of the form [A -> B] -> [C -> D], then add B -> D to "res".
2141 static int factor_range_entry(void **entry, void *user)
2143 isl_map *map = *entry;
2144 isl_union_map **res = user;
2146 if (!isl_map_domain_is_wrapping(map) || !isl_map_range_is_wrapping(map))
2147 return 0;
2149 *res = isl_union_map_add_map(*res,
2150 isl_map_factor_range(isl_map_copy(map)));
2152 return *res ? 0 : -1;
2155 /* For each map in "umap" of the form [A -> B] -> [C -> D],
2156 * construct the map B -> D and collect the results.
2158 __isl_give isl_union_map *isl_union_map_factor_range(
2159 __isl_take isl_union_map *umap)
2161 return cond_un_op(umap, &factor_range_entry);
2164 static int unwrap_entry(void **entry, void *user)
2166 isl_set *set = *entry;
2167 isl_union_set **res = user;
2169 if (!isl_set_is_wrapping(set))
2170 return 0;
2172 *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
2174 return 0;
2177 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
2179 return cond_un_op(uset, &unwrap_entry);
2182 static int wrap_entry(void **entry, void *user)
2184 isl_map *map = *entry;
2185 isl_union_set **res = user;
2187 *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
2189 return 0;
2192 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
2194 return cond_un_op(umap, &wrap_entry);
2197 struct isl_union_map_is_subset_data {
2198 isl_union_map *umap2;
2199 int is_subset;
2202 static int is_subset_entry(void **entry, void *user)
2204 struct isl_union_map_is_subset_data *data = user;
2205 uint32_t hash;
2206 struct isl_hash_table_entry *entry2;
2207 isl_map *map = *entry;
2209 hash = isl_space_get_hash(map->dim);
2210 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2211 hash, &has_dim, map->dim, 0);
2212 if (!entry2) {
2213 int empty = isl_map_is_empty(map);
2214 if (empty < 0)
2215 return -1;
2216 if (empty)
2217 return 0;
2218 data->is_subset = 0;
2219 return -1;
2222 data->is_subset = isl_map_is_subset(map, entry2->data);
2223 if (data->is_subset < 0 || !data->is_subset)
2224 return -1;
2226 return 0;
2229 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
2230 __isl_keep isl_union_map *umap2)
2232 struct isl_union_map_is_subset_data data = { NULL, 1 };
2234 umap1 = isl_union_map_copy(umap1);
2235 umap2 = isl_union_map_copy(umap2);
2236 umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
2237 umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
2239 if (!umap1 || !umap2)
2240 goto error;
2242 data.umap2 = umap2;
2243 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2244 &is_subset_entry, &data) < 0 &&
2245 data.is_subset)
2246 goto error;
2248 isl_union_map_free(umap1);
2249 isl_union_map_free(umap2);
2251 return data.is_subset;
2252 error:
2253 isl_union_map_free(umap1);
2254 isl_union_map_free(umap2);
2255 return -1;
2258 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
2259 __isl_keep isl_union_set *uset2)
2261 return isl_union_map_is_subset(uset1, uset2);
2264 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
2265 __isl_keep isl_union_map *umap2)
2267 int is_subset;
2269 if (!umap1 || !umap2)
2270 return -1;
2271 is_subset = isl_union_map_is_subset(umap1, umap2);
2272 if (is_subset != 1)
2273 return is_subset;
2274 is_subset = isl_union_map_is_subset(umap2, umap1);
2275 return is_subset;
2278 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
2279 __isl_keep isl_union_set *uset2)
2281 return isl_union_map_is_equal(uset1, uset2);
2284 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
2285 __isl_keep isl_union_map *umap2)
2287 int is_subset;
2289 if (!umap1 || !umap2)
2290 return -1;
2291 is_subset = isl_union_map_is_subset(umap1, umap2);
2292 if (is_subset != 1)
2293 return is_subset;
2294 is_subset = isl_union_map_is_subset(umap2, umap1);
2295 if (is_subset == -1)
2296 return is_subset;
2297 return !is_subset;
2300 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
2301 __isl_keep isl_union_set *uset2)
2303 return isl_union_map_is_strict_subset(uset1, uset2);
2306 /* Internal data structure for isl_union_map_is_disjoint.
2307 * umap2 is the union map with which we are comparing.
2308 * is_disjoint is initialized to 1 and is set to 0 as soon
2309 * as the union maps turn out not to be disjoint.
2311 struct isl_union_map_is_disjoint_data {
2312 isl_union_map *umap2;
2313 int is_disjoint;
2316 /* Check if "map" is disjoint from data->umap2 and abort
2317 * the search if it is not.
2319 static int is_disjoint_entry(void **entry, void *user)
2321 struct isl_union_map_is_disjoint_data *data = user;
2322 uint32_t hash;
2323 struct isl_hash_table_entry *entry2;
2324 isl_map *map = *entry;
2326 hash = isl_space_get_hash(map->dim);
2327 entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
2328 hash, &has_dim, map->dim, 0);
2329 if (!entry2)
2330 return 0;
2332 data->is_disjoint = isl_map_is_disjoint(map, entry2->data);
2333 if (data->is_disjoint < 0 || !data->is_disjoint)
2334 return -1;
2336 return 0;
2339 /* Are "umap1" and "umap2" disjoint?
2341 int isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1,
2342 __isl_keep isl_union_map *umap2)
2344 struct isl_union_map_is_disjoint_data data = { NULL, 1 };
2346 umap1 = isl_union_map_copy(umap1);
2347 umap2 = isl_union_map_copy(umap2);
2348 umap1 = isl_union_map_align_params(umap1,
2349 isl_union_map_get_space(umap2));
2350 umap2 = isl_union_map_align_params(umap2,
2351 isl_union_map_get_space(umap1));
2353 if (!umap1 || !umap2)
2354 goto error;
2356 data.umap2 = umap2;
2357 if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
2358 &is_disjoint_entry, &data) < 0 &&
2359 data.is_disjoint)
2360 goto error;
2362 isl_union_map_free(umap1);
2363 isl_union_map_free(umap2);
2365 return data.is_disjoint;
2366 error:
2367 isl_union_map_free(umap1);
2368 isl_union_map_free(umap2);
2369 return -1;
2372 /* Are "uset1" and "uset2" disjoint?
2374 int isl_union_set_is_disjoint(__isl_keep isl_union_set *uset1,
2375 __isl_keep isl_union_set *uset2)
2377 return isl_union_map_is_disjoint(uset1, uset2);
2380 static int sample_entry(void **entry, void *user)
2382 isl_basic_map **sample = (isl_basic_map **)user;
2383 isl_map *map = *entry;
2385 *sample = isl_map_sample(isl_map_copy(map));
2386 if (!*sample)
2387 return -1;
2388 if (!isl_basic_map_plain_is_empty(*sample))
2389 return -1;
2390 return 0;
2393 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
2395 isl_basic_map *sample = NULL;
2397 if (!umap)
2398 return NULL;
2400 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2401 &sample_entry, &sample) < 0 &&
2402 !sample)
2403 goto error;
2405 if (!sample)
2406 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
2408 isl_union_map_free(umap);
2410 return sample;
2411 error:
2412 isl_union_map_free(umap);
2413 return NULL;
2416 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
2418 return (isl_basic_set *)isl_union_map_sample(uset);
2421 struct isl_forall_data {
2422 int res;
2423 int (*fn)(__isl_keep isl_map *map);
2426 static int forall_entry(void **entry, void *user)
2428 struct isl_forall_data *data = user;
2429 isl_map *map = *entry;
2431 data->res = data->fn(map);
2432 if (data->res < 0)
2433 return -1;
2435 if (!data->res)
2436 return -1;
2438 return 0;
2441 static int union_map_forall(__isl_keep isl_union_map *umap,
2442 int (*fn)(__isl_keep isl_map *map))
2444 struct isl_forall_data data = { 1, fn };
2446 if (!umap)
2447 return -1;
2449 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2450 &forall_entry, &data) < 0 && data.res)
2451 return -1;
2453 return data.res;
2456 struct isl_forall_user_data {
2457 int res;
2458 int (*fn)(__isl_keep isl_map *map, void *user);
2459 void *user;
2462 static int forall_user_entry(void **entry, void *user)
2464 struct isl_forall_user_data *data = user;
2465 isl_map *map = *entry;
2467 data->res = data->fn(map, data->user);
2468 if (data->res < 0)
2469 return -1;
2471 if (!data->res)
2472 return -1;
2474 return 0;
2477 /* Check if fn(map, user) returns true for all maps "map" in umap.
2479 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2480 int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2482 struct isl_forall_user_data data = { 1, fn, user };
2484 if (!umap)
2485 return -1;
2487 if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2488 &forall_user_entry, &data) < 0 && data.res)
2489 return -1;
2491 return data.res;
2494 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2496 return union_map_forall(umap, &isl_map_is_empty);
2499 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2501 return isl_union_map_is_empty(uset);
2504 static int is_subset_of_identity(__isl_keep isl_map *map)
2506 int is_subset;
2507 isl_space *dim;
2508 isl_map *id;
2510 if (!map)
2511 return -1;
2513 if (!isl_space_tuple_is_equal(map->dim, isl_dim_in,
2514 map->dim, isl_dim_out))
2515 return 0;
2517 dim = isl_map_get_space(map);
2518 id = isl_map_identity(dim);
2520 is_subset = isl_map_is_subset(map, id);
2522 isl_map_free(id);
2524 return is_subset;
2527 /* Given an isl_union_map that consists of a single map, check
2528 * if it is single-valued.
2530 static int single_map_is_single_valued(__isl_keep isl_union_map *umap)
2532 isl_map *map;
2533 int sv;
2535 umap = isl_union_map_copy(umap);
2536 map = isl_map_from_union_map(umap);
2537 sv = isl_map_is_single_valued(map);
2538 isl_map_free(map);
2540 return sv;
2543 /* Internal data structure for single_valued_on_domain.
2545 * "umap" is the union map to be tested.
2546 * "sv" is set to 1 as long as "umap" may still be single-valued.
2548 struct isl_union_map_is_sv_data {
2549 isl_union_map *umap;
2550 int sv;
2553 /* Check if the data->umap is single-valued on "set".
2555 * If data->umap consists of a single map on "set", then test it
2556 * as an isl_map.
2558 * Otherwise, compute
2560 * M \circ M^-1
2562 * check if the result is a subset of the identity mapping and
2563 * store the result in data->sv.
2565 * Terminate as soon as data->umap has been determined not to
2566 * be single-valued.
2568 static int single_valued_on_domain(__isl_take isl_set *set, void *user)
2570 struct isl_union_map_is_sv_data *data = user;
2571 isl_union_map *umap, *test;
2573 umap = isl_union_map_copy(data->umap);
2574 umap = isl_union_map_intersect_domain(umap,
2575 isl_union_set_from_set(set));
2577 if (isl_union_map_n_map(umap) == 1) {
2578 data->sv = single_map_is_single_valued(umap);
2579 isl_union_map_free(umap);
2580 } else {
2581 test = isl_union_map_reverse(isl_union_map_copy(umap));
2582 test = isl_union_map_apply_range(test, umap);
2584 data->sv = union_map_forall(test, &is_subset_of_identity);
2586 isl_union_map_free(test);
2589 if (data->sv < 0 || !data->sv)
2590 return -1;
2591 return 0;
2594 /* Check if the given map is single-valued.
2596 * If the union map consists of a single map, then test it as an isl_map.
2597 * Otherwise, check if the union map is single-valued on each of its
2598 * domain spaces.
2600 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2602 isl_union_map *universe;
2603 isl_union_set *domain;
2604 struct isl_union_map_is_sv_data data;
2606 if (isl_union_map_n_map(umap) == 1)
2607 return single_map_is_single_valued(umap);
2609 universe = isl_union_map_universe(isl_union_map_copy(umap));
2610 domain = isl_union_map_domain(universe);
2612 data.sv = 1;
2613 data.umap = umap;
2614 if (isl_union_set_foreach_set(domain,
2615 &single_valued_on_domain, &data) < 0 && data.sv)
2616 data.sv = -1;
2617 isl_union_set_free(domain);
2619 return data.sv;
2622 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2624 int in;
2626 umap = isl_union_map_copy(umap);
2627 umap = isl_union_map_reverse(umap);
2628 in = isl_union_map_is_single_valued(umap);
2629 isl_union_map_free(umap);
2631 return in;
2634 /* Represents a map that has a fixed value (v) for one of its
2635 * range dimensions.
2636 * The map in this structure is not reference counted, so it
2637 * is only valid while the isl_union_map from which it was
2638 * obtained is still alive.
2640 struct isl_fixed_map {
2641 isl_int v;
2642 isl_map *map;
2645 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2646 int n)
2648 int i;
2649 struct isl_fixed_map *v;
2651 v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2652 if (!v)
2653 return NULL;
2654 for (i = 0; i < n; ++i)
2655 isl_int_init(v[i].v);
2656 return v;
2659 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2661 int i;
2663 if (!v)
2664 return;
2665 for (i = 0; i < n; ++i)
2666 isl_int_clear(v[i].v);
2667 free(v);
2670 /* Compare the "v" field of two isl_fixed_map structs.
2672 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2674 const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2675 const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2677 return isl_int_cmp(e1->v, e2->v);
2680 /* Internal data structure used while checking whether all maps
2681 * in a union_map have a fixed value for a given output dimension.
2682 * v is the list of maps, with the fixed value for the dimension
2683 * n is the number of maps considered so far
2684 * pos is the output dimension under investigation
2686 struct isl_fixed_dim_data {
2687 struct isl_fixed_map *v;
2688 int n;
2689 int pos;
2692 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2694 struct isl_fixed_dim_data *data = user;
2696 data->v[data->n].map = map;
2697 return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2698 &data->v[data->n++].v);
2701 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2702 int first, int n_range);
2704 /* Given a list of the maps, with their fixed values at output dimension "pos",
2705 * check whether the ranges of the maps form an obvious partition.
2707 * We first sort the maps according to their fixed values.
2708 * If all maps have a different value, then we know the ranges form
2709 * a partition.
2710 * Otherwise, we collect the maps with the same fixed value and
2711 * check whether each such collection is obviously injective
2712 * based on later dimensions.
2714 static int separates(struct isl_fixed_map *v, int n,
2715 __isl_take isl_space *dim, int pos, int n_range)
2717 int i;
2719 if (!v)
2720 goto error;
2722 qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2724 for (i = 0; i + 1 < n; ++i) {
2725 int j, k;
2726 isl_union_map *part;
2727 int injective;
2729 for (j = i + 1; j < n; ++j)
2730 if (isl_int_ne(v[i].v, v[j].v))
2731 break;
2733 if (j == i + 1)
2734 continue;
2736 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2737 for (k = i; k < j; ++k)
2738 part = isl_union_map_add_map(part,
2739 isl_map_copy(v[k].map));
2741 injective = plain_injective_on_range(part, pos + 1, n_range);
2742 if (injective < 0)
2743 goto error;
2744 if (!injective)
2745 break;
2747 i = j - 1;
2750 isl_space_free(dim);
2751 free_isl_fixed_map_array(v, n);
2752 return i + 1 >= n;
2753 error:
2754 isl_space_free(dim);
2755 free_isl_fixed_map_array(v, n);
2756 return -1;
2759 /* Check whether the maps in umap have obviously distinct ranges.
2760 * In particular, check for an output dimension in the range
2761 * [first,n_range) for which all maps have a fixed value
2762 * and then check if these values, possibly along with fixed values
2763 * at later dimensions, entail distinct ranges.
2765 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2766 int first, int n_range)
2768 isl_ctx *ctx;
2769 int n;
2770 struct isl_fixed_dim_data data = { NULL };
2772 ctx = isl_union_map_get_ctx(umap);
2774 n = isl_union_map_n_map(umap);
2775 if (!umap)
2776 goto error;
2778 if (n <= 1) {
2779 isl_union_map_free(umap);
2780 return 1;
2783 if (first >= n_range) {
2784 isl_union_map_free(umap);
2785 return 0;
2788 data.v = alloc_isl_fixed_map_array(ctx, n);
2789 if (!data.v)
2790 goto error;
2792 for (data.pos = first; data.pos < n_range; ++data.pos) {
2793 int fixed;
2794 int injective;
2795 isl_space *dim;
2797 data.n = 0;
2798 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2799 if (fixed < 0)
2800 goto error;
2801 if (!fixed)
2802 continue;
2803 dim = isl_union_map_get_space(umap);
2804 injective = separates(data.v, n, dim, data.pos, n_range);
2805 isl_union_map_free(umap);
2806 return injective;
2809 free_isl_fixed_map_array(data.v, n);
2810 isl_union_map_free(umap);
2812 return 0;
2813 error:
2814 free_isl_fixed_map_array(data.v, n);
2815 isl_union_map_free(umap);
2816 return -1;
2819 /* Check whether the maps in umap that map to subsets of "ran"
2820 * have obviously distinct ranges.
2822 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2824 isl_union_map *umap = user;
2826 umap = isl_union_map_copy(umap);
2827 umap = isl_union_map_intersect_range(umap,
2828 isl_union_set_from_set(isl_set_copy(ran)));
2829 return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2832 /* Check if the given union_map is obviously injective.
2834 * In particular, we first check if all individual maps are obviously
2835 * injective and then check if all the ranges of these maps are
2836 * obviously disjoint.
2838 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2840 int in;
2841 isl_union_map *univ;
2842 isl_union_set *ran;
2844 in = union_map_forall(umap, &isl_map_plain_is_injective);
2845 if (in < 0)
2846 return -1;
2847 if (!in)
2848 return 0;
2850 univ = isl_union_map_universe(isl_union_map_copy(umap));
2851 ran = isl_union_map_range(univ);
2853 in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2855 isl_union_set_free(ran);
2857 return in;
2860 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2862 int sv;
2864 sv = isl_union_map_is_single_valued(umap);
2865 if (sv < 0 || !sv)
2866 return sv;
2868 return isl_union_map_is_injective(umap);
2871 static int zip_entry(void **entry, void *user)
2873 isl_map *map = *entry;
2874 isl_union_map **res = user;
2876 if (!isl_map_can_zip(map))
2877 return 0;
2879 *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2881 return 0;
2884 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2886 return cond_un_op(umap, &zip_entry);
2889 static int uncurry_entry(void **entry, void *user)
2891 isl_map *map = *entry;
2892 isl_union_map **res = user;
2894 if (!isl_map_can_uncurry(map))
2895 return 0;
2897 *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2899 return 0;
2902 /* Given a union map, take the maps of the form A -> (B -> C) and
2903 * return the union of the corresponding maps (A -> B) -> C.
2905 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2907 return cond_un_op(umap, &uncurry_entry);
2910 static int curry_entry(void **entry, void *user)
2912 isl_map *map = *entry;
2913 isl_union_map **res = user;
2915 if (!isl_map_can_curry(map))
2916 return 0;
2918 *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2920 return 0;
2923 /* Given a union map, take the maps of the form (A -> B) -> C and
2924 * return the union of the corresponding maps A -> (B -> C).
2926 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2928 return cond_un_op(umap, &curry_entry);
2931 static int lift_entry(void **entry, void *user)
2933 isl_set *set = *entry;
2934 isl_union_set **res = user;
2936 *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2938 return 0;
2941 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2943 return cond_un_op(uset, &lift_entry);
2946 static int coefficients_entry(void **entry, void *user)
2948 isl_set *set = *entry;
2949 isl_union_set **res = user;
2951 set = isl_set_copy(set);
2952 set = isl_set_from_basic_set(isl_set_coefficients(set));
2953 *res = isl_union_set_add_set(*res, set);
2955 return 0;
2958 __isl_give isl_union_set *isl_union_set_coefficients(
2959 __isl_take isl_union_set *uset)
2961 isl_ctx *ctx;
2962 isl_space *dim;
2963 isl_union_set *res;
2965 if (!uset)
2966 return NULL;
2968 ctx = isl_union_set_get_ctx(uset);
2969 dim = isl_space_set_alloc(ctx, 0, 0);
2970 res = isl_union_map_alloc(dim, uset->table.n);
2971 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2972 &coefficients_entry, &res) < 0)
2973 goto error;
2975 isl_union_set_free(uset);
2976 return res;
2977 error:
2978 isl_union_set_free(uset);
2979 isl_union_set_free(res);
2980 return NULL;
2983 static int solutions_entry(void **entry, void *user)
2985 isl_set *set = *entry;
2986 isl_union_set **res = user;
2988 set = isl_set_copy(set);
2989 set = isl_set_from_basic_set(isl_set_solutions(set));
2990 if (!*res)
2991 *res = isl_union_set_from_set(set);
2992 else
2993 *res = isl_union_set_add_set(*res, set);
2995 if (!*res)
2996 return -1;
2998 return 0;
3001 __isl_give isl_union_set *isl_union_set_solutions(
3002 __isl_take isl_union_set *uset)
3004 isl_union_set *res = NULL;
3006 if (!uset)
3007 return NULL;
3009 if (uset->table.n == 0) {
3010 res = isl_union_set_empty(isl_union_set_get_space(uset));
3011 isl_union_set_free(uset);
3012 return res;
3015 if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
3016 &solutions_entry, &res) < 0)
3017 goto error;
3019 isl_union_set_free(uset);
3020 return res;
3021 error:
3022 isl_union_set_free(uset);
3023 isl_union_set_free(res);
3024 return NULL;
3027 /* Is the domain space of "map" equal to "space"?
3029 static int domain_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3031 return isl_space_tuple_is_equal(map->dim, isl_dim_in,
3032 space, isl_dim_out);
3035 /* Is the range space of "map" equal to "space"?
3037 static int range_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3039 return isl_space_tuple_is_equal(map->dim, isl_dim_out,
3040 space, isl_dim_out);
3043 /* Is the set space of "map" equal to "space"?
3045 static int set_match(__isl_keep isl_map *map, __isl_keep isl_space *space)
3047 return isl_space_tuple_is_equal(map->dim, isl_dim_set,
3048 space, isl_dim_out);
3051 /* Internal data structure for preimage_pw_multi_aff.
3053 * "pma" is the function under which the preimage should be taken.
3054 * "space" is the space of "pma".
3055 * "res" collects the results.
3056 * "fn" computes the preimage for a given map.
3057 * "match" returns true if "fn" can be called.
3059 struct isl_union_map_preimage_data {
3060 isl_space *space;
3061 isl_pw_multi_aff *pma;
3062 isl_union_map *res;
3063 int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);
3064 __isl_give isl_map *(*fn)(__isl_take isl_map *map,
3065 __isl_take isl_pw_multi_aff *pma);
3068 /* Call data->fn to compute the preimage of the domain or range of *entry
3069 * under the function represented by data->pma, provided the domain/range
3070 * space of *entry matches the target space of data->pma
3071 * (as given by data->match), and add the result to data->res.
3073 static int preimage_entry(void **entry, void *user)
3075 int m;
3076 isl_map *map = *entry;
3077 struct isl_union_map_preimage_data *data = user;
3078 int empty;
3080 m = data->match(map, data->space);
3081 if (m < 0)
3082 return -1;
3083 if (!m)
3084 return 0;
3086 map = isl_map_copy(map);
3087 map = data->fn(map, isl_pw_multi_aff_copy(data->pma));
3089 empty = isl_map_is_empty(map);
3090 if (empty < 0 || empty) {
3091 isl_map_free(map);
3092 return empty < 0 ? -1 : 0;
3095 data->res = isl_union_map_add_map(data->res, map);
3097 return 0;
3100 /* Compute the preimage of the domain or range of "umap" under the function
3101 * represented by "pma".
3102 * In other words, plug in "pma" in the domain or range of "umap".
3103 * The function "fn" performs the actual preimage computation on a map,
3104 * while "match" determines to which maps the function should be applied.
3106 static __isl_give isl_union_map *preimage_pw_multi_aff(
3107 __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma,
3108 int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),
3109 __isl_give isl_map *(*fn)(__isl_take isl_map *map,
3110 __isl_take isl_pw_multi_aff *pma))
3112 isl_ctx *ctx;
3113 isl_space *space;
3114 struct isl_union_map_preimage_data data;
3116 umap = isl_union_map_align_params(umap,
3117 isl_pw_multi_aff_get_space(pma));
3118 pma = isl_pw_multi_aff_align_params(pma, isl_union_map_get_space(umap));
3120 if (!umap || !pma)
3121 goto error;
3123 ctx = isl_union_map_get_ctx(umap);
3124 space = isl_union_map_get_space(umap);
3125 data.space = isl_pw_multi_aff_get_space(pma);
3126 data.pma = pma;
3127 data.res = isl_union_map_alloc(space, umap->table.n);
3128 data.match = match;
3129 data.fn = fn;
3130 if (isl_hash_table_foreach(ctx, &umap->table, &preimage_entry,
3131 &data) < 0)
3132 data.res = isl_union_map_free(data.res);
3134 isl_space_free(data.space);
3135 isl_union_map_free(umap);
3136 isl_pw_multi_aff_free(pma);
3137 return data.res;
3138 error:
3139 isl_union_map_free(umap);
3140 isl_pw_multi_aff_free(pma);
3141 return NULL;
3144 /* Compute the preimage of the domain of "umap" under the function
3145 * represented by "pma".
3146 * In other words, plug in "pma" in the domain of "umap".
3147 * The result contains maps that live in the same spaces as the maps of "umap"
3148 * with domain space equal to the target space of "pma",
3149 * except that the domain has been replaced by the domain space of "pma".
3151 __isl_give isl_union_map *isl_union_map_preimage_domain_pw_multi_aff(
3152 __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)
3154 return preimage_pw_multi_aff(umap, pma, &domain_match,
3155 &isl_map_preimage_domain_pw_multi_aff);
3158 /* Compute the preimage of the range of "umap" under the function
3159 * represented by "pma".
3160 * In other words, plug in "pma" in the range of "umap".
3161 * The result contains maps that live in the same spaces as the maps of "umap"
3162 * with range space equal to the target space of "pma",
3163 * except that the range has been replaced by the domain space of "pma".
3165 __isl_give isl_union_map *isl_union_map_preimage_range_pw_multi_aff(
3166 __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma)
3168 return preimage_pw_multi_aff(umap, pma, &range_match,
3169 &isl_map_preimage_range_pw_multi_aff);
3172 /* Compute the preimage of "uset" under the function represented by "pma".
3173 * In other words, plug in "pma" in "uset".
3174 * The result contains sets that live in the same spaces as the sets of "uset"
3175 * with space equal to the target space of "pma",
3176 * except that the space has been replaced by the domain space of "pma".
3178 __isl_give isl_union_set *isl_union_set_preimage_pw_multi_aff(
3179 __isl_take isl_union_set *uset, __isl_take isl_pw_multi_aff *pma)
3181 return preimage_pw_multi_aff(uset, pma, &set_match,
3182 &isl_set_preimage_pw_multi_aff);
3185 /* Compute the preimage of the domain of "umap" under the function
3186 * represented by "ma".
3187 * In other words, plug in "ma" in the domain of "umap".
3188 * The result contains maps that live in the same spaces as the maps of "umap"
3189 * with domain space equal to the target space of "ma",
3190 * except that the domain has been replaced by the domain space of "ma".
3192 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(
3193 __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
3195 return isl_union_map_preimage_domain_pw_multi_aff(umap,
3196 isl_pw_multi_aff_from_multi_aff(ma));
3199 /* Compute the preimage of the range of "umap" under the function
3200 * represented by "ma".
3201 * In other words, plug in "ma" in the range of "umap".
3202 * The result contains maps that live in the same spaces as the maps of "umap"
3203 * with range space equal to the target space of "ma",
3204 * except that the range has been replaced by the domain space of "ma".
3206 __isl_give isl_union_map *isl_union_map_preimage_range_multi_aff(
3207 __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
3209 return isl_union_map_preimage_range_pw_multi_aff(umap,
3210 isl_pw_multi_aff_from_multi_aff(ma));
3213 /* Compute the preimage of "uset" under the function represented by "ma".
3214 * In other words, plug in "ma" in "uset".
3215 * The result contains sets that live in the same spaces as the sets of "uset"
3216 * with space equal to the target space of "ma",
3217 * except that the space has been replaced by the domain space of "ma".
3219 __isl_give isl_union_map *isl_union_set_preimage_multi_aff(
3220 __isl_take isl_union_set *uset, __isl_take isl_multi_aff *ma)
3222 return isl_union_set_preimage_pw_multi_aff(uset,
3223 isl_pw_multi_aff_from_multi_aff(ma));
3226 /* Internal data structure for preimage_multi_pw_aff.
3228 * "mpa" is the function under which the preimage should be taken.
3229 * "space" is the space of "mpa".
3230 * "res" collects the results.
3231 * "fn" computes the preimage for a given map.
3232 * "match" returns true if "fn" can be called.
3234 struct isl_union_map_preimage_mpa_data {
3235 isl_space *space;
3236 isl_multi_pw_aff *mpa;
3237 isl_union_map *res;
3238 int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space);
3239 __isl_give isl_map *(*fn)(__isl_take isl_map *map,
3240 __isl_take isl_multi_pw_aff *mpa);
3243 /* Call data->fn to compute the preimage of the domain or range of *entry
3244 * under the function represented by data->mpa, provided the domain/range
3245 * space of *entry matches the target space of data->mpa
3246 * (as given by data->match), and add the result to data->res.
3248 static int preimage_mpa_entry(void **entry, void *user)
3250 int m;
3251 isl_map *map = *entry;
3252 struct isl_union_map_preimage_mpa_data *data = user;
3253 int empty;
3255 m = data->match(map, data->space);
3256 if (m < 0)
3257 return -1;
3258 if (!m)
3259 return 0;
3261 map = isl_map_copy(map);
3262 map = data->fn(map, isl_multi_pw_aff_copy(data->mpa));
3264 empty = isl_map_is_empty(map);
3265 if (empty < 0 || empty) {
3266 isl_map_free(map);
3267 return empty < 0 ? -1 : 0;
3270 data->res = isl_union_map_add_map(data->res, map);
3272 return 0;
3275 /* Compute the preimage of the domain or range of "umap" under the function
3276 * represented by "mpa".
3277 * In other words, plug in "mpa" in the domain or range of "umap".
3278 * The function "fn" performs the actual preimage computation on a map,
3279 * while "match" determines to which maps the function should be applied.
3281 static __isl_give isl_union_map *preimage_multi_pw_aff(
3282 __isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa,
3283 int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space),
3284 __isl_give isl_map *(*fn)(__isl_take isl_map *map,
3285 __isl_take isl_multi_pw_aff *mpa))
3287 isl_ctx *ctx;
3288 isl_space *space;
3289 struct isl_union_map_preimage_mpa_data data;
3291 umap = isl_union_map_align_params(umap,
3292 isl_multi_pw_aff_get_space(mpa));
3293 mpa = isl_multi_pw_aff_align_params(mpa, isl_union_map_get_space(umap));
3295 if (!umap || !mpa)
3296 goto error;
3298 ctx = isl_union_map_get_ctx(umap);
3299 space = isl_union_map_get_space(umap);
3300 data.space = isl_multi_pw_aff_get_space(mpa);
3301 data.mpa = mpa;
3302 data.res = isl_union_map_alloc(space, umap->table.n);
3303 data.match = match;
3304 data.fn = fn;
3305 if (isl_hash_table_foreach(ctx, &umap->table, &preimage_mpa_entry,
3306 &data) < 0)
3307 data.res = isl_union_map_free(data.res);
3309 isl_space_free(data.space);
3310 isl_union_map_free(umap);
3311 isl_multi_pw_aff_free(mpa);
3312 return data.res;
3313 error:
3314 isl_union_map_free(umap);
3315 isl_multi_pw_aff_free(mpa);
3316 return NULL;
3319 /* Compute the preimage of the domain of "umap" under the function
3320 * represented by "mpa".
3321 * In other words, plug in "mpa" in the domain of "umap".
3322 * The result contains maps that live in the same spaces as the maps of "umap"
3323 * with domain space equal to the target space of "mpa",
3324 * except that the domain has been replaced by the domain space of "mpa".
3326 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_pw_aff(
3327 __isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa)
3329 return preimage_multi_pw_aff(umap, mpa, &domain_match,
3330 &isl_map_preimage_domain_multi_pw_aff);
3333 /* Internal data structure for preimage_upma.
3335 * "umap" is the map of which the preimage should be computed.
3336 * "res" collects the results.
3337 * "fn" computes the preimage for a given piecewise multi-affine function.
3339 struct isl_union_map_preimage_upma_data {
3340 isl_union_map *umap;
3341 isl_union_map *res;
3342 __isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,
3343 __isl_take isl_pw_multi_aff *pma);
3346 /* Call data->fn to compute the preimage of the domain or range of data->umap
3347 * under the function represented by pma and add the result to data->res.
3349 static int preimage_upma(__isl_take isl_pw_multi_aff *pma, void *user)
3351 struct isl_union_map_preimage_upma_data *data = user;
3352 isl_union_map *umap;
3354 umap = isl_union_map_copy(data->umap);
3355 umap = data->fn(umap, pma);
3356 data->res = isl_union_map_union(data->res, umap);
3358 return data->res ? 0 : -1;
3361 /* Compute the preimage of the domain or range of "umap" under the function
3362 * represented by "upma".
3363 * In other words, plug in "upma" in the domain or range of "umap".
3364 * The function "fn" performs the actual preimage computation
3365 * on a piecewise multi-affine function.
3367 static __isl_give isl_union_map *preimage_union_pw_multi_aff(
3368 __isl_take isl_union_map *umap,
3369 __isl_take isl_union_pw_multi_aff *upma,
3370 __isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap,
3371 __isl_take isl_pw_multi_aff *pma))
3373 struct isl_union_map_preimage_upma_data data;
3375 data.umap = umap;
3376 data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3377 data.fn = fn;
3378 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3379 &preimage_upma, &data) < 0)
3380 data.res = isl_union_map_free(data.res);
3382 isl_union_map_free(umap);
3383 isl_union_pw_multi_aff_free(upma);
3385 return data.res;
3388 /* Compute the preimage of the domain of "umap" under the function
3389 * represented by "upma".
3390 * In other words, plug in "upma" in the domain of "umap".
3391 * The result contains maps that live in the same spaces as the maps of "umap"
3392 * with domain space equal to one of the target spaces of "upma",
3393 * except that the domain has been replaced by one of the the domain spaces that
3394 * corresponds to that target space of "upma".
3396 __isl_give isl_union_map *isl_union_map_preimage_domain_union_pw_multi_aff(
3397 __isl_take isl_union_map *umap,
3398 __isl_take isl_union_pw_multi_aff *upma)
3400 return preimage_union_pw_multi_aff(umap, upma,
3401 &isl_union_map_preimage_domain_pw_multi_aff);
3404 /* Compute the preimage of the range of "umap" under the function
3405 * represented by "upma".
3406 * In other words, plug in "upma" in the range of "umap".
3407 * The result contains maps that live in the same spaces as the maps of "umap"
3408 * with range space equal to one of the target spaces of "upma",
3409 * except that the range has been replaced by one of the the domain spaces that
3410 * corresponds to that target space of "upma".
3412 __isl_give isl_union_map *isl_union_map_preimage_range_union_pw_multi_aff(
3413 __isl_take isl_union_map *umap,
3414 __isl_take isl_union_pw_multi_aff *upma)
3416 return preimage_union_pw_multi_aff(umap, upma,
3417 &isl_union_map_preimage_range_pw_multi_aff);
3420 /* Compute the preimage of "uset" under the function represented by "upma".
3421 * In other words, plug in "upma" in the range of "uset".
3422 * The result contains sets that live in the same spaces as the sets of "uset"
3423 * with space equal to one of the target spaces of "upma",
3424 * except that the space has been replaced by one of the the domain spaces that
3425 * corresponds to that target space of "upma".
3427 __isl_give isl_union_set *isl_union_set_preimage_union_pw_multi_aff(
3428 __isl_take isl_union_set *uset,
3429 __isl_take isl_union_pw_multi_aff *upma)
3431 return preimage_union_pw_multi_aff(uset, upma,
3432 &isl_union_set_preimage_pw_multi_aff);
3435 /* Reset the user pointer on all identifiers of parameters and tuples
3436 * of the space of *entry.
3438 static int reset_user(void **entry, void *user)
3440 isl_map **map = (isl_map **)entry;
3442 *map = isl_map_reset_user(*map);
3444 return *map ? 0 : -1;
3447 /* Reset the user pointer on all identifiers of parameters and tuples
3448 * of the spaces of "umap".
3450 __isl_give isl_union_map *isl_union_map_reset_user(
3451 __isl_take isl_union_map *umap)
3453 umap = isl_union_map_cow(umap);
3454 if (!umap)
3455 return NULL;
3456 umap->dim = isl_space_reset_user(umap->dim);
3457 if (!umap->dim)
3458 return isl_union_map_free(umap);
3459 umap = un_op(umap, &reset_user);
3461 return umap;
3464 /* Reset the user pointer on all identifiers of parameters and tuples
3465 * of the spaces of "uset".
3467 __isl_give isl_union_set *isl_union_set_reset_user(
3468 __isl_take isl_union_set *uset)
3470 return isl_union_map_reset_user(uset);
3473 /* Internal data structure for isl_union_map_project_out.
3474 * "type", "first" and "n" are the arguments for the isl_map_project_out
3475 * call.
3476 * "res" collects the results.
3478 struct isl_union_map_project_out_data {
3479 enum isl_dim_type type;
3480 unsigned first;
3481 unsigned n;
3483 isl_union_map *res;
3486 /* Turn the data->n dimensions of type data->type, starting at data->first
3487 * into existentially quantified variables and add the result to data->res.
3489 static int project_out(__isl_take isl_map *map, void *user)
3491 struct isl_union_map_project_out_data *data = user;
3493 map = isl_map_project_out(map, data->type, data->first, data->n);
3494 data->res = isl_union_map_add_map(data->res, map);
3496 return 0;
3499 /* Turn the "n" dimensions of type "type", starting at "first"
3500 * into existentially quantified variables.
3501 * Since the space of an isl_union_map only contains parameters,
3502 * type is required to be equal to isl_dim_param.
3504 __isl_give isl_union_map *isl_union_map_project_out(
3505 __isl_take isl_union_map *umap,
3506 enum isl_dim_type type, unsigned first, unsigned n)
3508 isl_space *space;
3509 struct isl_union_map_project_out_data data = { type, first, n };
3511 if (!umap)
3512 return NULL;
3514 if (type != isl_dim_param)
3515 isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
3516 "can only project out parameters",
3517 return isl_union_map_free(umap));
3519 space = isl_union_map_get_space(umap);
3520 space = isl_space_drop_dims(space, type, first, n);
3521 data.res = isl_union_map_empty(space);
3522 if (isl_union_map_foreach_map(umap, &project_out, &data) < 0)
3523 data.res = isl_union_map_free(data.res);
3525 isl_union_map_free(umap);
3527 return data.res;
3530 /* Turn the "n" dimensions of type "type", starting at "first"
3531 * into existentially quantified variables.
3532 * Since the space of an isl_union_set only contains parameters,
3533 * "type" is required to be equal to isl_dim_param.
3535 __isl_give isl_union_set *isl_union_set_project_out(
3536 __isl_take isl_union_set *uset,
3537 enum isl_dim_type type, unsigned first, unsigned n)
3539 return isl_union_map_project_out(uset, type, first, n);
3542 /* Internal data structure for isl_union_map_involves_dims.
3543 * "first" and "n" are the arguments for the isl_map_involves_dims calls.
3545 struct isl_union_map_involves_dims_data {
3546 unsigned first;
3547 unsigned n;
3550 /* Does "map" _not_ involve the data->n parameters starting at data->first?
3552 static int map_excludes(__isl_keep isl_map *map, void *user)
3554 struct isl_union_map_involves_dims_data *data = user;
3555 int involves;
3557 involves = isl_map_involves_dims(map,
3558 isl_dim_param, data->first, data->n);
3559 if (involves < 0)
3560 return -1;
3561 return !involves;
3564 /* Does "umap" involve any of the n parameters starting at first?
3565 * "type" is required to be set to isl_dim_param.
3567 * "umap" involves any of those parameters if any of its maps
3568 * involve the parameters. In other words, "umap" does not
3569 * involve any of the parameters if all its maps to not
3570 * involve the parameters.
3572 int isl_union_map_involves_dims(__isl_keep isl_union_map *umap,
3573 enum isl_dim_type type, unsigned first, unsigned n)
3575 struct isl_union_map_involves_dims_data data = { first, n };
3576 int excludes;
3578 if (type != isl_dim_param)
3579 isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,
3580 "can only reference parameters", return 0);
3582 excludes = union_map_forall_user(umap, &map_excludes, &data);
3584 if (excludes < 0)
3585 return -1;
3587 return !excludes;
3590 /* Internal data structure for isl_union_map_reset_range_space.
3591 * "range" is the space from which to set the range space.
3592 * "res" collects the results.
3594 struct isl_union_map_reset_range_space_data {
3595 isl_space *range;
3596 isl_union_map *res;
3599 /* Replace the range space of "map" by the range space of data->range and
3600 * add the result to data->res.
3602 static int reset_range_space(__isl_take isl_map *map, void *user)
3604 struct isl_union_map_reset_range_space_data *data = user;
3605 isl_space *space;
3607 space = isl_map_get_space(map);
3608 space = isl_space_domain(space);
3609 space = isl_space_extend_domain_with_range(space,
3610 isl_space_copy(data->range));
3611 map = isl_map_reset_space(map, space);
3612 data->res = isl_union_map_add_map(data->res, map);
3614 return data->res ? 0 : -1;
3617 /* Replace the range space of all the maps in "umap" by
3618 * the range space of "space".
3620 * This assumes that all maps have the same output dimension.
3621 * This function should therefore not be made publicly available.
3623 * Since the spaces of the maps change, so do their hash value.
3624 * We therefore need to create a new isl_union_map.
3626 __isl_give isl_union_map *isl_union_map_reset_range_space(
3627 __isl_take isl_union_map *umap, __isl_take isl_space *space)
3629 struct isl_union_map_reset_range_space_data data = { space };
3631 data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3632 if (isl_union_map_foreach_map(umap, &reset_range_space, &data) < 0)
3633 data.res = isl_union_map_free(data.res);
3635 isl_space_free(space);
3636 isl_union_map_free(umap);
3637 return data.res;
3640 /* Internal data structure for isl_union_map_order_at_multi_union_pw_aff.
3641 * "mupa" is the function from which the isl_multi_pw_affs are extracted.
3642 * "order" is applied to the extracted isl_multi_pw_affs that correspond
3643 * to the domain and the range of each map.
3644 * "res" collects the results.
3646 struct isl_union_order_at_data {
3647 isl_multi_union_pw_aff *mupa;
3648 __isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,
3649 __isl_take isl_multi_pw_aff *mpa2);
3650 isl_union_map *res;
3653 /* Intersect "map" with the result of applying data->order to
3654 * the functions in data->mupa that apply to the domain and the range
3655 * of "map" and add the result to data->res.
3657 static int order_at(__isl_take isl_map *map, void *user)
3659 struct isl_union_order_at_data *data = user;
3660 isl_space *space;
3661 isl_multi_pw_aff *mpa1, *mpa2;
3662 isl_map *order;
3664 space = isl_space_domain(isl_map_get_space(map));
3665 mpa1 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);
3666 space = isl_space_range(isl_map_get_space(map));
3667 mpa2 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space);
3668 order = data->order(mpa1, mpa2);
3669 map = isl_map_intersect(map, order);
3670 data->res = isl_union_map_add_map(data->res, map);
3672 return data->res ? 0 : -1;
3675 /* Intersect each map in "umap" with the result of calling "order"
3676 * on the functions is "mupa" that apply to the domain and the range
3677 * of the map.
3679 static __isl_give isl_union_map *isl_union_map_order_at_multi_union_pw_aff(
3680 __isl_take isl_union_map *umap, __isl_take isl_multi_union_pw_aff *mupa,
3681 __isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1,
3682 __isl_take isl_multi_pw_aff *mpa2))
3684 struct isl_union_order_at_data data;
3686 umap = isl_union_map_align_params(umap,
3687 isl_multi_union_pw_aff_get_space(mupa));
3688 mupa = isl_multi_union_pw_aff_align_params(mupa,
3689 isl_union_map_get_space(umap));
3690 data.mupa = mupa;
3691 data.order = order;
3692 data.res = isl_union_map_empty(isl_union_map_get_space(umap));
3693 if (isl_union_map_foreach_map(umap, &order_at, &data) < 0)
3694 data.res = isl_union_map_free(data.res);
3696 isl_multi_union_pw_aff_free(mupa);
3697 isl_union_map_free(umap);
3698 return data.res;
3701 /* Return the subset of "umap" where the domain and the range
3702 * have equal "mupa" values.
3704 __isl_give isl_union_map *isl_union_map_eq_at_multi_union_pw_aff(
3705 __isl_take isl_union_map *umap,
3706 __isl_take isl_multi_union_pw_aff *mupa)
3708 return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
3709 &isl_multi_pw_aff_eq_map);
3712 /* Return the subset of "umap" where the domain has a lexicographically
3713 * smaller "mupa" value than the range.
3715 __isl_give isl_union_map *isl_union_map_lex_lt_at_multi_union_pw_aff(
3716 __isl_take isl_union_map *umap,
3717 __isl_take isl_multi_union_pw_aff *mupa)
3719 return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
3720 &isl_multi_pw_aff_lex_lt_map);
3723 /* Return the subset of "umap" where the domain has a lexicographically
3724 * greater "mupa" value than the range.
3726 __isl_give isl_union_map *isl_union_map_lex_gt_at_multi_union_pw_aff(
3727 __isl_take isl_union_map *umap,
3728 __isl_take isl_multi_union_pw_aff *mupa)
3730 return isl_union_map_order_at_multi_union_pw_aff(umap, mupa,
3731 &isl_multi_pw_aff_lex_gt_map);
3734 /* Return the union of the elements in the list "list".
3736 __isl_give isl_union_set *isl_union_set_list_union(
3737 __isl_take isl_union_set_list *list)
3739 int i, n;
3740 isl_ctx *ctx;
3741 isl_space *space;
3742 isl_union_set *res;
3744 if (!list)
3745 return NULL;
3747 ctx = isl_union_set_list_get_ctx(list);
3748 space = isl_space_params_alloc(ctx, 0);
3749 res = isl_union_set_empty(space);
3751 n = isl_union_set_list_n_union_set(list);
3752 for (i = 0; i < n; ++i) {
3753 isl_union_set *uset_i;
3755 uset_i = isl_union_set_list_get_union_set(list, i);
3756 res = isl_union_set_union(res, uset_i);
3759 isl_union_set_list_free(list);
3760 return res;