add isl_term_get_coefficient_val
[platform/upstream/isl.git] / isl_union_map.c
1 /*
2  * Copyright 2010-2011 INRIA Saclay
3  *
4  * Use of this software is governed by the MIT license
5  *
6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8  * 91893 Orsay, France 
9  */
10
11 #define ISL_DIM_H
12 #include <isl_map_private.h>
13 #include <isl/ctx.h>
14 #include <isl/hash.h>
15 #include <isl/aff.h>
16 #include <isl/map.h>
17 #include <isl/set.h>
18 #include <isl_space_private.h>
19 #include <isl_union_map_private.h>
20 #include <isl/union_set.h>
21
22 /* Is this union set a parameter domain?
23  */
24 int isl_union_set_is_params(__isl_keep isl_union_set *uset)
25 {
26         isl_set *set;
27         int params;
28
29         if (!uset)
30                 return -1;
31         if (uset->table.n != 1)
32                 return 0;
33
34         set = isl_set_from_union_set(isl_union_set_copy(uset));
35         params = isl_set_is_params(set);
36         isl_set_free(set);
37         return params;
38 }
39
40 static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
41         int size)
42 {
43         isl_union_map *umap;
44
45         dim = isl_space_params(dim);
46         if (!dim)
47                 return NULL;
48
49         umap = isl_calloc_type(dim->ctx, isl_union_map);
50         if (!umap)
51                 return NULL;
52
53         umap->ref = 1;
54         umap->dim = dim;
55         if (isl_hash_table_init(dim->ctx, &umap->table, size) < 0)
56                 goto error;
57
58         return umap;
59 error:
60         isl_space_free(dim);
61         isl_union_map_free(umap);
62         return NULL;
63 }
64
65 __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
66 {
67         return isl_union_map_alloc(dim, 16);
68 }
69
70 __isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
71 {
72         return isl_union_map_empty(dim);
73 }
74
75 isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
76 {
77         return umap ? umap->dim->ctx : NULL;
78 }
79
80 isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
81 {
82         return uset ? uset->dim->ctx : NULL;
83 }
84
85 __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
86 {
87         if (!umap)
88                 return NULL;
89         return isl_space_copy(umap->dim);
90 }
91
92 __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
93 {
94         return isl_union_map_get_space(uset);
95 }
96
97 static int free_umap_entry(void **entry, void *user)
98 {
99         isl_map *map = *entry;
100         isl_map_free(map);
101         return 0;
102 }
103
104 static int add_map(__isl_take isl_map *map, void *user)
105 {
106         isl_union_map **umap = (isl_union_map **)user;
107
108         *umap = isl_union_map_add_map(*umap, map);
109
110         return 0;
111 }
112
113 __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
114 {
115         isl_union_map *dup;
116
117         if (!umap)
118                 return NULL;
119
120         dup = isl_union_map_empty(isl_space_copy(umap->dim));
121         if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
122                 goto error;
123         return dup;
124 error:
125         isl_union_map_free(dup);
126         return NULL;
127 }
128
129 __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
130 {
131         if (!umap)
132                 return NULL;
133
134         if (umap->ref == 1)
135                 return umap;
136         umap->ref--;
137         return isl_union_map_dup(umap);
138 }
139
140 struct isl_union_align {
141         isl_reordering *exp;
142         isl_union_map *res;
143 };
144
145 static int align_entry(void **entry, void *user)
146 {
147         isl_map *map = *entry;
148         isl_reordering *exp;
149         struct isl_union_align *data = user;
150
151         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
152                                     isl_map_get_space(map));
153
154         data->res = isl_union_map_add_map(data->res,
155                                         isl_map_realign(isl_map_copy(map), exp));
156
157         return 0;
158 }
159
160 /* Align the parameters of umap along those of model.
161  * The result has the parameters of model first, in the same order
162  * as they appear in model, followed by any remaining parameters of
163  * umap that do not appear in model.
164  */
165 __isl_give isl_union_map *isl_union_map_align_params(
166         __isl_take isl_union_map *umap, __isl_take isl_space *model)
167 {
168         struct isl_union_align data = { NULL, NULL };
169
170         if (!umap || !model)
171                 goto error;
172
173         if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
174                 isl_space_free(model);
175                 return umap;
176         }
177
178         model = isl_space_params(model);
179         data.exp = isl_parameter_alignment_reordering(umap->dim, model);
180         if (!data.exp)
181                 goto error;
182
183         data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
184                                         umap->table.n);
185         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
186                                         &align_entry, &data) < 0)
187                 goto error;
188
189         isl_reordering_free(data.exp);
190         isl_union_map_free(umap);
191         isl_space_free(model);
192         return data.res;
193 error:
194         isl_reordering_free(data.exp);
195         isl_union_map_free(umap);
196         isl_union_map_free(data.res);
197         isl_space_free(model);
198         return NULL;
199 }
200
201 __isl_give isl_union_set *isl_union_set_align_params(
202         __isl_take isl_union_set *uset, __isl_take isl_space *model)
203 {
204         return isl_union_map_align_params(uset, model);
205 }
206
207 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
208         __isl_take isl_union_map *umap2)
209 {
210         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
211         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
212
213         umap1 = isl_union_map_cow(umap1);
214
215         if (!umap1 || !umap2)
216                 goto error;
217
218         if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
219                 goto error;
220
221         isl_union_map_free(umap2);
222
223         return umap1;
224 error:
225         isl_union_map_free(umap1);
226         isl_union_map_free(umap2);
227         return NULL;
228 }
229
230 __isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
231         __isl_take isl_union_set *uset2)
232 {
233         return isl_union_map_union(uset1, uset2);
234 }
235
236 __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
237 {
238         if (!umap)
239                 return NULL;
240
241         umap->ref++;
242         return umap;
243 }
244
245 __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
246 {
247         return isl_union_map_copy(uset);
248 }
249
250 void *isl_union_map_free(__isl_take isl_union_map *umap)
251 {
252         if (!umap)
253                 return NULL;
254
255         if (--umap->ref > 0)
256                 return NULL;
257
258         isl_hash_table_foreach(umap->dim->ctx, &umap->table,
259                                &free_umap_entry, NULL);
260         isl_hash_table_clear(&umap->table);
261         isl_space_free(umap->dim);
262         free(umap);
263         return NULL;
264 }
265
266 void *isl_union_set_free(__isl_take isl_union_set *uset)
267 {
268         return isl_union_map_free(uset);
269 }
270
271 static int has_dim(const void *entry, const void *val)
272 {
273         isl_map *map = (isl_map *)entry;
274         isl_space *dim = (isl_space *)val;
275
276         return isl_space_is_equal(map->dim, dim);
277 }
278
279 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
280         __isl_take isl_map *map)
281 {
282         uint32_t hash;
283         struct isl_hash_table_entry *entry;
284
285         if (!map || !umap)
286                 goto error;
287
288         if (isl_map_plain_is_empty(map)) {
289                 isl_map_free(map);
290                 return umap;
291         }
292
293         if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
294                 umap = isl_union_map_align_params(umap, isl_map_get_space(map));
295                 map = isl_map_align_params(map, isl_union_map_get_space(umap));
296         }
297
298         umap = isl_union_map_cow(umap);
299
300         if (!map || !umap)
301                 goto error;
302
303         hash = isl_space_get_hash(map->dim);
304         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
305                                     &has_dim, map->dim, 1);
306         if (!entry)
307                 goto error;
308
309         if (!entry->data)
310                 entry->data = map;
311         else {
312                 entry->data = isl_map_union(entry->data, isl_map_copy(map));
313                 if (!entry->data)
314                         goto error;
315                 isl_map_free(map);
316         }
317
318         return umap;
319 error:
320         isl_map_free(map);
321         isl_union_map_free(umap);
322         return NULL;
323 }
324
325 __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
326         __isl_take isl_set *set)
327 {
328         return isl_union_map_add_map(uset, (isl_map *)set);
329 }
330
331 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
332 {
333         isl_space *dim;
334         isl_union_map *umap;
335
336         if (!map)
337                 return NULL;
338
339         dim = isl_map_get_space(map);
340         dim = isl_space_params(dim);
341         umap = isl_union_map_empty(dim);
342         umap = isl_union_map_add_map(umap, map);
343
344         return umap;
345 }
346
347 __isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
348 {
349         return isl_union_map_from_map((isl_map *)set);
350 }
351
352 __isl_give isl_union_map *isl_union_map_from_basic_map(
353         __isl_take isl_basic_map *bmap)
354 {
355         return isl_union_map_from_map(isl_map_from_basic_map(bmap));
356 }
357
358 __isl_give isl_union_set *isl_union_set_from_basic_set(
359         __isl_take isl_basic_set *bset)
360 {
361         return isl_union_map_from_basic_map(bset);
362 }
363
364 struct isl_union_map_foreach_data
365 {
366         int (*fn)(__isl_take isl_map *map, void *user);
367         void *user;
368 };
369
370 static int call_on_copy(void **entry, void *user)
371 {
372         isl_map *map = *entry;
373         struct isl_union_map_foreach_data *data;
374         data = (struct isl_union_map_foreach_data *)user;
375
376         return data->fn(isl_map_copy(map), data->user);
377 }
378
379 int isl_union_map_n_map(__isl_keep isl_union_map *umap)
380 {
381         return umap ? umap->table.n : 0;
382 }
383
384 int isl_union_set_n_set(__isl_keep isl_union_set *uset)
385 {
386         return uset ? uset->table.n : 0;
387 }
388
389 int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
390         int (*fn)(__isl_take isl_map *map, void *user), void *user)
391 {
392         struct isl_union_map_foreach_data data = { fn, user };
393
394         if (!umap)
395                 return -1;
396
397         return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
398                                       &call_on_copy, &data);
399 }
400
401 static int copy_map(void **entry, void *user)
402 {
403         isl_map *map = *entry;
404         isl_map **map_p = user;
405
406         *map_p = isl_map_copy(map);
407
408         return -1;
409 }
410
411 __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
412 {
413         isl_ctx *ctx;
414         isl_map *map = NULL;
415
416         if (!umap)
417                 return NULL;
418         ctx = isl_union_map_get_ctx(umap);
419         if (umap->table.n != 1)
420                 isl_die(ctx, isl_error_invalid,
421                         "union map needs to contain elements in exactly "
422                         "one space", return isl_union_map_free(umap));
423
424         isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
425
426         isl_union_map_free(umap);
427
428         return map;
429 }
430
431 __isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
432 {
433         return isl_map_from_union_map(uset);
434 }
435
436 /* Extract the map in "umap" that lives in the given space (ignoring
437  * parameters).
438  */
439 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
440         __isl_take isl_space *space)
441 {
442         uint32_t hash;
443         struct isl_hash_table_entry *entry;
444
445         space = isl_space_drop_dims(space, isl_dim_param,
446                                         0, isl_space_dim(space, isl_dim_param));
447         space = isl_space_align_params(space, isl_union_map_get_space(umap));
448         if (!umap || !space)
449                 goto error;
450
451         hash = isl_space_get_hash(space);
452         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
453                                     &has_dim, space, 0);
454         if (!entry)
455                 return isl_map_empty(space);
456         isl_space_free(space);
457         return isl_map_copy(entry->data);
458 error:
459         isl_space_free(space);
460         return NULL;
461 }
462
463 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
464         __isl_take isl_space *dim)
465 {
466         return (isl_set *)isl_union_map_extract_map(uset, dim);
467 }
468
469 /* Check if umap contains a map in the given space.
470  */
471 __isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
472         __isl_keep isl_space *dim)
473 {
474         uint32_t hash;
475         struct isl_hash_table_entry *entry;
476
477         if (!umap || !dim)
478                 return -1;
479
480         hash = isl_space_get_hash(dim);
481         entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
482                                     &has_dim, dim, 0);
483         return !!entry;
484 }
485
486 __isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
487         __isl_keep isl_space *dim)
488 {
489         return isl_union_map_contains(uset, dim);
490 }
491
492 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
493         int (*fn)(__isl_take isl_set *set, void *user), void *user)
494 {
495         return isl_union_map_foreach_map(uset,
496                 (int(*)(__isl_take isl_map *, void*))fn, user);
497 }
498
499 struct isl_union_set_foreach_point_data {
500         int (*fn)(__isl_take isl_point *pnt, void *user);
501         void *user;
502 };
503
504 static int foreach_point(__isl_take isl_set *set, void *user)
505 {
506         struct isl_union_set_foreach_point_data *data = user;
507         int r;
508
509         r = isl_set_foreach_point(set, data->fn, data->user);
510         isl_set_free(set);
511
512         return r;
513 }
514
515 int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
516         int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
517 {
518         struct isl_union_set_foreach_point_data data = { fn, user };
519         return isl_union_set_foreach_set(uset, &foreach_point, &data);
520 }
521
522 struct isl_union_map_gen_bin_data {
523         isl_union_map *umap2;
524         isl_union_map *res;
525 };
526
527 static int subtract_entry(void **entry, void *user)
528 {
529         struct isl_union_map_gen_bin_data *data = user;
530         uint32_t hash;
531         struct isl_hash_table_entry *entry2;
532         isl_map *map = *entry;
533
534         hash = isl_space_get_hash(map->dim);
535         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
536                                      hash, &has_dim, map->dim, 0);
537         map = isl_map_copy(map);
538         if (entry2) {
539                 int empty;
540                 map = isl_map_subtract(map, isl_map_copy(entry2->data));
541
542                 empty = isl_map_is_empty(map);
543                 if (empty < 0) {
544                         isl_map_free(map);
545                         return -1;
546                 }
547                 if (empty) {
548                         isl_map_free(map);
549                         return 0;
550                 }
551         }
552         data->res = isl_union_map_add_map(data->res, map);
553
554         return 0;
555 }
556
557 static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
558         __isl_take isl_union_map *umap2, int (*fn)(void **, void *))
559 {
560         struct isl_union_map_gen_bin_data data = { NULL, NULL };
561
562         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
563         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
564
565         if (!umap1 || !umap2)
566                 goto error;
567
568         data.umap2 = umap2;
569         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
570                                        umap1->table.n);
571         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
572                                    fn, &data) < 0)
573                 goto error;
574
575         isl_union_map_free(umap1);
576         isl_union_map_free(umap2);
577         return data.res;
578 error:
579         isl_union_map_free(umap1);
580         isl_union_map_free(umap2);
581         isl_union_map_free(data.res);
582         return NULL;
583 }
584
585 __isl_give isl_union_map *isl_union_map_subtract(
586         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
587 {
588         return gen_bin_op(umap1, umap2, &subtract_entry);
589 }
590
591 __isl_give isl_union_set *isl_union_set_subtract(
592         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
593 {
594         return isl_union_map_subtract(uset1, uset2);
595 }
596
597 struct isl_union_map_gen_bin_set_data {
598         isl_set *set;
599         isl_union_map *res;
600 };
601
602 static int intersect_params_entry(void **entry, void *user)
603 {
604         struct isl_union_map_gen_bin_set_data *data = user;
605         isl_map *map = *entry;
606         int empty;
607
608         map = isl_map_copy(map);
609         map = isl_map_intersect_params(map, isl_set_copy(data->set));
610
611         empty = isl_map_is_empty(map);
612         if (empty < 0) {
613                 isl_map_free(map);
614                 return -1;
615         }
616
617         data->res = isl_union_map_add_map(data->res, map);
618
619         return 0;
620 }
621
622 static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
623         __isl_take isl_set *set, int (*fn)(void **, void *))
624 {
625         struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
626
627         umap = isl_union_map_align_params(umap, isl_set_get_space(set));
628         set = isl_set_align_params(set, isl_union_map_get_space(umap));
629
630         if (!umap || !set)
631                 goto error;
632
633         data.set = set;
634         data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
635                                        umap->table.n);
636         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
637                                    fn, &data) < 0)
638                 goto error;
639
640         isl_union_map_free(umap);
641         isl_set_free(set);
642         return data.res;
643 error:
644         isl_union_map_free(umap);
645         isl_set_free(set);
646         isl_union_map_free(data.res);
647         return NULL;
648 }
649
650 __isl_give isl_union_map *isl_union_map_intersect_params(
651         __isl_take isl_union_map *umap, __isl_take isl_set *set)
652 {
653         return gen_bin_set_op(umap, set, &intersect_params_entry);
654 }
655
656 __isl_give isl_union_set *isl_union_set_intersect_params(
657         __isl_take isl_union_set *uset, __isl_take isl_set *set)
658 {
659         return isl_union_map_intersect_params(uset, set);
660 }
661
662 static __isl_give isl_union_map *union_map_intersect_params(
663         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
664 {
665         return isl_union_map_intersect_params(umap,
666                                                 isl_set_from_union_set(uset));
667 }
668
669 static __isl_give isl_union_map *union_map_gist_params(
670         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
671 {
672         return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
673 }
674
675 struct isl_union_map_match_bin_data {
676         isl_union_map *umap2;
677         isl_union_map *res;
678         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
679 };
680
681 static int match_bin_entry(void **entry, void *user)
682 {
683         struct isl_union_map_match_bin_data *data = user;
684         uint32_t hash;
685         struct isl_hash_table_entry *entry2;
686         isl_map *map = *entry;
687         int empty;
688
689         hash = isl_space_get_hash(map->dim);
690         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
691                                      hash, &has_dim, map->dim, 0);
692         if (!entry2)
693                 return 0;
694
695         map = isl_map_copy(map);
696         map = data->fn(map, isl_map_copy(entry2->data));
697
698         empty = isl_map_is_empty(map);
699         if (empty < 0) {
700                 isl_map_free(map);
701                 return -1;
702         }
703         if (empty) {
704                 isl_map_free(map);
705                 return 0;
706         }
707
708         data->res = isl_union_map_add_map(data->res, map);
709
710         return 0;
711 }
712
713 static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
714         __isl_take isl_union_map *umap2,
715         __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
716 {
717         struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
718
719         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
720         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
721
722         if (!umap1 || !umap2)
723                 goto error;
724
725         data.umap2 = umap2;
726         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
727                                        umap1->table.n);
728         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
729                                    &match_bin_entry, &data) < 0)
730                 goto error;
731
732         isl_union_map_free(umap1);
733         isl_union_map_free(umap2);
734         return data.res;
735 error:
736         isl_union_map_free(umap1);
737         isl_union_map_free(umap2);
738         isl_union_map_free(data.res);
739         return NULL;
740 }
741
742 __isl_give isl_union_map *isl_union_map_intersect(
743         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
744 {
745         return match_bin_op(umap1, umap2, &isl_map_intersect);
746 }
747
748 /* Compute the intersection of the two union_sets.
749  * As a special case, if exactly one of the two union_sets
750  * is a parameter domain, then intersect the parameter domain
751  * of the other one with this set.
752  */
753 __isl_give isl_union_set *isl_union_set_intersect(
754         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
755 {
756         int p1, p2;
757
758         p1 = isl_union_set_is_params(uset1);
759         p2 = isl_union_set_is_params(uset2);
760         if (p1 < 0 || p2 < 0)
761                 goto error;
762         if (!p1 && p2)
763                 return union_map_intersect_params(uset1, uset2);
764         if (p1 && !p2)
765                 return union_map_intersect_params(uset2, uset1);
766         return isl_union_map_intersect(uset1, uset2);
767 error:
768         isl_union_set_free(uset1);
769         isl_union_set_free(uset2);
770         return NULL;
771 }
772
773 static int gist_params_entry(void **entry, void *user)
774 {
775         struct isl_union_map_gen_bin_set_data *data = user;
776         isl_map *map = *entry;
777         int empty;
778
779         map = isl_map_copy(map);
780         map = isl_map_gist_params(map, isl_set_copy(data->set));
781
782         empty = isl_map_is_empty(map);
783         if (empty < 0) {
784                 isl_map_free(map);
785                 return -1;
786         }
787
788         data->res = isl_union_map_add_map(data->res, map);
789
790         return 0;
791 }
792
793 __isl_give isl_union_map *isl_union_map_gist_params(
794         __isl_take isl_union_map *umap, __isl_take isl_set *set)
795 {
796         return gen_bin_set_op(umap, set, &gist_params_entry);
797 }
798
799 __isl_give isl_union_set *isl_union_set_gist_params(
800         __isl_take isl_union_set *uset, __isl_take isl_set *set)
801 {
802         return isl_union_map_gist_params(uset, set);
803 }
804
805 __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
806         __isl_take isl_union_map *context)
807 {
808         return match_bin_op(umap, context, &isl_map_gist);
809 }
810
811 __isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
812         __isl_take isl_union_set *context)
813 {
814         if (isl_union_set_is_params(context))
815                 return union_map_gist_params(uset, context);
816         return isl_union_map_gist(uset, context);
817 }
818
819 static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
820         __isl_take isl_map *set2)
821 {
822         return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
823 }
824
825 static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
826         __isl_take isl_map *set2)
827 {
828         return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
829 }
830
831 __isl_give isl_union_map *isl_union_set_lex_lt_union_set(
832         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
833 {
834         return match_bin_op(uset1, uset2, &lex_lt_set);
835 }
836
837 __isl_give isl_union_map *isl_union_set_lex_le_union_set(
838         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
839 {
840         return match_bin_op(uset1, uset2, &lex_le_set);
841 }
842
843 __isl_give isl_union_map *isl_union_set_lex_gt_union_set(
844         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
845 {
846         return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
847 }
848
849 __isl_give isl_union_map *isl_union_set_lex_ge_union_set(
850         __isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
851 {
852         return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
853 }
854
855 __isl_give isl_union_map *isl_union_map_lex_gt_union_map(
856         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
857 {
858         return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
859 }
860
861 __isl_give isl_union_map *isl_union_map_lex_ge_union_map(
862         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
863 {
864         return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
865 }
866
867 static int intersect_domain_entry(void **entry, void *user)
868 {
869         struct isl_union_map_gen_bin_data *data = user;
870         uint32_t hash;
871         struct isl_hash_table_entry *entry2;
872         isl_space *dim;
873         isl_map *map = *entry;
874         int empty;
875
876         dim = isl_map_get_space(map);
877         dim = isl_space_domain(dim);
878         hash = isl_space_get_hash(dim);
879         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
880                                      hash, &has_dim, dim, 0);
881         isl_space_free(dim);
882         if (!entry2)
883                 return 0;
884
885         map = isl_map_copy(map);
886         map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
887
888         empty = isl_map_is_empty(map);
889         if (empty < 0) {
890                 isl_map_free(map);
891                 return -1;
892         }
893         if (empty) {
894                 isl_map_free(map);
895                 return 0;
896         }
897
898         data->res = isl_union_map_add_map(data->res, map);
899
900         return 0;
901 }
902
903 /* Intersect the domain of "umap" with "uset".
904  * If "uset" is a parameters domain, then intersect the parameter
905  * domain of "umap" with this set.
906  */
907 __isl_give isl_union_map *isl_union_map_intersect_domain(
908         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
909 {
910         if (isl_union_set_is_params(uset))
911                 return union_map_intersect_params(umap, uset);
912         return gen_bin_op(umap, uset, &intersect_domain_entry);
913 }
914
915 /* Remove the elements of data->umap2 from the domain of *entry
916  * and add the result to data->res.
917  */
918 static int subtract_domain_entry(void **entry, void *user)
919 {
920         struct isl_union_map_gen_bin_data *data = user;
921         uint32_t hash;
922         struct isl_hash_table_entry *entry2;
923         isl_space *dim;
924         isl_map *map = *entry;
925         int empty;
926
927         dim = isl_map_get_space(map);
928         dim = isl_space_domain(dim);
929         hash = isl_space_get_hash(dim);
930         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
931                                      hash, &has_dim, dim, 0);
932         isl_space_free(dim);
933
934         map = isl_map_copy(map);
935
936         if (!entry2) {
937                 data->res = isl_union_map_add_map(data->res, map);
938                 return 0;
939         }
940
941         map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
942
943         empty = isl_map_is_empty(map);
944         if (empty < 0) {
945                 isl_map_free(map);
946                 return -1;
947         }
948         if (empty) {
949                 isl_map_free(map);
950                 return 0;
951         }
952
953         data->res = isl_union_map_add_map(data->res, map);
954
955         return 0;
956 }
957
958 /* Remove the elements of "uset" from the domain of "umap".
959  */
960 __isl_give isl_union_map *isl_union_map_subtract_domain(
961         __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
962 {
963         return gen_bin_op(umap, dom, &subtract_domain_entry);
964 }
965
966 /* Remove the elements of data->umap2 from the range of *entry
967  * and add the result to data->res.
968  */
969 static int subtract_range_entry(void **entry, void *user)
970 {
971         struct isl_union_map_gen_bin_data *data = user;
972         uint32_t hash;
973         struct isl_hash_table_entry *entry2;
974         isl_space *space;
975         isl_map *map = *entry;
976         int empty;
977
978         space = isl_map_get_space(map);
979         space = isl_space_range(space);
980         hash = isl_space_get_hash(space);
981         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
982                                      hash, &has_dim, space, 0);
983         isl_space_free(space);
984
985         map = isl_map_copy(map);
986
987         if (!entry2) {
988                 data->res = isl_union_map_add_map(data->res, map);
989                 return 0;
990         }
991
992         map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
993
994         empty = isl_map_is_empty(map);
995         if (empty < 0) {
996                 isl_map_free(map);
997                 return -1;
998         }
999         if (empty) {
1000                 isl_map_free(map);
1001                 return 0;
1002         }
1003
1004         data->res = isl_union_map_add_map(data->res, map);
1005
1006         return 0;
1007 }
1008
1009 /* Remove the elements of "uset" from the range of "umap".
1010  */
1011 __isl_give isl_union_map *isl_union_map_subtract_range(
1012         __isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1013 {
1014         return gen_bin_op(umap, dom, &subtract_range_entry);
1015 }
1016
1017 static int gist_domain_entry(void **entry, void *user)
1018 {
1019         struct isl_union_map_gen_bin_data *data = user;
1020         uint32_t hash;
1021         struct isl_hash_table_entry *entry2;
1022         isl_space *dim;
1023         isl_map *map = *entry;
1024         int empty;
1025
1026         dim = isl_map_get_space(map);
1027         dim = isl_space_domain(dim);
1028         hash = isl_space_get_hash(dim);
1029         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1030                                      hash, &has_dim, dim, 0);
1031         isl_space_free(dim);
1032         if (!entry2)
1033                 return 0;
1034
1035         map = isl_map_copy(map);
1036         map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1037
1038         empty = isl_map_is_empty(map);
1039         if (empty < 0) {
1040                 isl_map_free(map);
1041                 return -1;
1042         }
1043
1044         data->res = isl_union_map_add_map(data->res, map);
1045
1046         return 0;
1047 }
1048
1049 /* Compute the gist of "umap" with respect to the domain "uset".
1050  * If "uset" is a parameters domain, then compute the gist
1051  * with respect to this parameter domain.
1052  */
1053 __isl_give isl_union_map *isl_union_map_gist_domain(
1054         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1055 {
1056         if (isl_union_set_is_params(uset))
1057                 return union_map_gist_params(umap, uset);
1058         return gen_bin_op(umap, uset, &gist_domain_entry);
1059 }
1060
1061 static int gist_range_entry(void **entry, void *user)
1062 {
1063         struct isl_union_map_gen_bin_data *data = user;
1064         uint32_t hash;
1065         struct isl_hash_table_entry *entry2;
1066         isl_space *space;
1067         isl_map *map = *entry;
1068         int empty;
1069
1070         space = isl_map_get_space(map);
1071         space = isl_space_range(space);
1072         hash = isl_space_get_hash(space);
1073         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1074                                      hash, &has_dim, space, 0);
1075         isl_space_free(space);
1076         if (!entry2)
1077                 return 0;
1078
1079         map = isl_map_copy(map);
1080         map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1081
1082         empty = isl_map_is_empty(map);
1083         if (empty < 0) {
1084                 isl_map_free(map);
1085                 return -1;
1086         }
1087
1088         data->res = isl_union_map_add_map(data->res, map);
1089
1090         return 0;
1091 }
1092
1093 /* Compute the gist of "umap" with respect to the range "uset".
1094  */
1095 __isl_give isl_union_map *isl_union_map_gist_range(
1096         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1097 {
1098         return gen_bin_op(umap, uset, &gist_range_entry);
1099 }
1100
1101 static int intersect_range_entry(void **entry, void *user)
1102 {
1103         struct isl_union_map_gen_bin_data *data = user;
1104         uint32_t hash;
1105         struct isl_hash_table_entry *entry2;
1106         isl_space *dim;
1107         isl_map *map = *entry;
1108         int empty;
1109
1110         dim = isl_map_get_space(map);
1111         dim = isl_space_range(dim);
1112         hash = isl_space_get_hash(dim);
1113         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1114                                      hash, &has_dim, dim, 0);
1115         isl_space_free(dim);
1116         if (!entry2)
1117                 return 0;
1118
1119         map = isl_map_copy(map);
1120         map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1121
1122         empty = isl_map_is_empty(map);
1123         if (empty < 0) {
1124                 isl_map_free(map);
1125                 return -1;
1126         }
1127         if (empty) {
1128                 isl_map_free(map);
1129                 return 0;
1130         }
1131
1132         data->res = isl_union_map_add_map(data->res, map);
1133
1134         return 0;
1135 }
1136
1137 __isl_give isl_union_map *isl_union_map_intersect_range(
1138         __isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1139 {
1140         return gen_bin_op(umap, uset, &intersect_range_entry);
1141 }
1142
1143 struct isl_union_map_bin_data {
1144         isl_union_map *umap2;
1145         isl_union_map *res;
1146         isl_map *map;
1147         int (*fn)(void **entry, void *user);
1148 };
1149
1150 static int apply_range_entry(void **entry, void *user)
1151 {
1152         struct isl_union_map_bin_data *data = user;
1153         isl_map *map2 = *entry;
1154         int empty;
1155
1156         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1157                                  map2->dim, isl_dim_in))
1158                 return 0;
1159
1160         map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1161
1162         empty = isl_map_is_empty(map2);
1163         if (empty < 0) {
1164                 isl_map_free(map2);
1165                 return -1;
1166         }
1167         if (empty) {
1168                 isl_map_free(map2);
1169                 return 0;
1170         }
1171
1172         data->res = isl_union_map_add_map(data->res, map2);
1173
1174         return 0;
1175 }
1176
1177 static int bin_entry(void **entry, void *user)
1178 {
1179         struct isl_union_map_bin_data *data = user;
1180         isl_map *map = *entry;
1181
1182         data->map = map;
1183         if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1184                                    data->fn, data) < 0)
1185                 return -1;
1186
1187         return 0;
1188 }
1189
1190 static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1191         __isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1192 {
1193         struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1194
1195         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1196         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1197
1198         if (!umap1 || !umap2)
1199                 goto error;
1200
1201         data.umap2 = umap2;
1202         data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1203                                        umap1->table.n);
1204         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1205                                    &bin_entry, &data) < 0)
1206                 goto error;
1207
1208         isl_union_map_free(umap1);
1209         isl_union_map_free(umap2);
1210         return data.res;
1211 error:
1212         isl_union_map_free(umap1);
1213         isl_union_map_free(umap2);
1214         isl_union_map_free(data.res);
1215         return NULL;
1216 }
1217
1218 __isl_give isl_union_map *isl_union_map_apply_range(
1219         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1220 {
1221         return bin_op(umap1, umap2, &apply_range_entry);
1222 }
1223
1224 __isl_give isl_union_map *isl_union_map_apply_domain(
1225         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1226 {
1227         umap1 = isl_union_map_reverse(umap1);
1228         umap1 = isl_union_map_apply_range(umap1, umap2);
1229         return isl_union_map_reverse(umap1);
1230 }
1231
1232 __isl_give isl_union_set *isl_union_set_apply(
1233         __isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1234 {
1235         return isl_union_map_apply_range(uset, umap);
1236 }
1237
1238 static int map_lex_lt_entry(void **entry, void *user)
1239 {
1240         struct isl_union_map_bin_data *data = user;
1241         isl_map *map2 = *entry;
1242
1243         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1244                                  map2->dim, isl_dim_out))
1245                 return 0;
1246
1247         map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1248
1249         data->res = isl_union_map_add_map(data->res, map2);
1250
1251         return 0;
1252 }
1253
1254 __isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1255         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1256 {
1257         return bin_op(umap1, umap2, &map_lex_lt_entry);
1258 }
1259
1260 static int map_lex_le_entry(void **entry, void *user)
1261 {
1262         struct isl_union_map_bin_data *data = user;
1263         isl_map *map2 = *entry;
1264
1265         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1266                                  map2->dim, isl_dim_out))
1267                 return 0;
1268
1269         map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1270
1271         data->res = isl_union_map_add_map(data->res, map2);
1272
1273         return 0;
1274 }
1275
1276 __isl_give isl_union_map *isl_union_map_lex_le_union_map(
1277         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1278 {
1279         return bin_op(umap1, umap2, &map_lex_le_entry);
1280 }
1281
1282 static int product_entry(void **entry, void *user)
1283 {
1284         struct isl_union_map_bin_data *data = user;
1285         isl_map *map2 = *entry;
1286
1287         map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1288
1289         data->res = isl_union_map_add_map(data->res, map2);
1290
1291         return 0;
1292 }
1293
1294 __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1295         __isl_take isl_union_map *umap2)
1296 {
1297         return bin_op(umap1, umap2, &product_entry);
1298 }
1299
1300 static int set_product_entry(void **entry, void *user)
1301 {
1302         struct isl_union_map_bin_data *data = user;
1303         isl_set *set2 = *entry;
1304
1305         set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1306
1307         data->res = isl_union_set_add_set(data->res, set2);
1308
1309         return 0;
1310 }
1311
1312 __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1313         __isl_take isl_union_set *uset2)
1314 {
1315         return bin_op(uset1, uset2, &set_product_entry);
1316 }
1317
1318 static int domain_product_entry(void **entry, void *user)
1319 {
1320         struct isl_union_map_bin_data *data = user;
1321         isl_map *map2 = *entry;
1322
1323         if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1324                                  map2->dim, isl_dim_out))
1325                 return 0;
1326
1327         map2 = isl_map_domain_product(isl_map_copy(data->map),
1328                                      isl_map_copy(map2));
1329
1330         data->res = isl_union_map_add_map(data->res, map2);
1331
1332         return 0;
1333 }
1334
1335 /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1336  */
1337 __isl_give isl_union_map *isl_union_map_domain_product(
1338         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1339 {
1340         return bin_op(umap1, umap2, &domain_product_entry);
1341 }
1342
1343 static int range_product_entry(void **entry, void *user)
1344 {
1345         struct isl_union_map_bin_data *data = user;
1346         isl_map *map2 = *entry;
1347
1348         if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1349                                  map2->dim, isl_dim_in))
1350                 return 0;
1351
1352         map2 = isl_map_range_product(isl_map_copy(data->map),
1353                                      isl_map_copy(map2));
1354
1355         data->res = isl_union_map_add_map(data->res, map2);
1356
1357         return 0;
1358 }
1359
1360 __isl_give isl_union_map *isl_union_map_range_product(
1361         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1362 {
1363         return bin_op(umap1, umap2, &range_product_entry);
1364 }
1365
1366 static int flat_range_product_entry(void **entry, void *user)
1367 {
1368         struct isl_union_map_bin_data *data = user;
1369         isl_map *map2 = *entry;
1370
1371         if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1372                                  map2->dim, isl_dim_in))
1373                 return 0;
1374
1375         map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1376                                           isl_map_copy(map2));
1377
1378         data->res = isl_union_map_add_map(data->res, map2);
1379
1380         return 0;
1381 }
1382
1383 __isl_give isl_union_map *isl_union_map_flat_range_product(
1384         __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1385 {
1386         return bin_op(umap1, umap2, &flat_range_product_entry);
1387 }
1388
1389 static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1390         int (*fn)(void **, void *))
1391 {
1392         isl_union_set *res;
1393
1394         if (!umap)
1395                 return NULL;
1396
1397         res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1398         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1399                 goto error;
1400
1401         isl_union_map_free(umap);
1402         return res;
1403 error:
1404         isl_union_map_free(umap);
1405         isl_union_set_free(res);
1406         return NULL;
1407 }
1408
1409 static int from_range_entry(void **entry, void *user)
1410 {
1411         isl_map *set = *entry;
1412         isl_union_set **res = user;
1413
1414         *res = isl_union_map_add_map(*res,
1415                                         isl_map_from_range(isl_set_copy(set)));
1416
1417         return 0;
1418 }
1419
1420 __isl_give isl_union_map *isl_union_map_from_range(
1421         __isl_take isl_union_set *uset)
1422 {
1423         return cond_un_op(uset, &from_range_entry);
1424 }
1425
1426 __isl_give isl_union_map *isl_union_map_from_domain(
1427         __isl_take isl_union_set *uset)
1428 {
1429         return isl_union_map_reverse(isl_union_map_from_range(uset));
1430 }
1431
1432 __isl_give isl_union_map *isl_union_map_from_domain_and_range(
1433         __isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1434 {
1435         return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1436                                          isl_union_map_from_range(range));
1437 }
1438
1439 static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1440         int (*fn)(void **, void *))
1441 {
1442         umap = isl_union_map_cow(umap);
1443         if (!umap)
1444                 return NULL;
1445
1446         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1447                 goto error;
1448
1449         return umap;
1450 error:
1451         isl_union_map_free(umap);
1452         return NULL;
1453 }
1454
1455 static int affine_entry(void **entry, void *user)
1456 {
1457         isl_map **map = (isl_map **)entry;
1458
1459         *map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1460
1461         return *map ? 0 : -1;
1462 }
1463
1464 __isl_give isl_union_map *isl_union_map_affine_hull(
1465         __isl_take isl_union_map *umap)
1466 {
1467         return un_op(umap, &affine_entry);
1468 }
1469
1470 __isl_give isl_union_set *isl_union_set_affine_hull(
1471         __isl_take isl_union_set *uset)
1472 {
1473         return isl_union_map_affine_hull(uset);
1474 }
1475
1476 static int polyhedral_entry(void **entry, void *user)
1477 {
1478         isl_map **map = (isl_map **)entry;
1479
1480         *map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1481
1482         return *map ? 0 : -1;
1483 }
1484
1485 __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1486         __isl_take isl_union_map *umap)
1487 {
1488         return un_op(umap, &polyhedral_entry);
1489 }
1490
1491 __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1492         __isl_take isl_union_set *uset)
1493 {
1494         return isl_union_map_polyhedral_hull(uset);
1495 }
1496
1497 static int simple_entry(void **entry, void *user)
1498 {
1499         isl_map **map = (isl_map **)entry;
1500
1501         *map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1502
1503         return *map ? 0 : -1;
1504 }
1505
1506 __isl_give isl_union_map *isl_union_map_simple_hull(
1507         __isl_take isl_union_map *umap)
1508 {
1509         return un_op(umap, &simple_entry);
1510 }
1511
1512 __isl_give isl_union_set *isl_union_set_simple_hull(
1513         __isl_take isl_union_set *uset)
1514 {
1515         return isl_union_map_simple_hull(uset);
1516 }
1517
1518 static int inplace_entry(void **entry, void *user)
1519 {
1520         __isl_give isl_map *(*fn)(__isl_take isl_map *);
1521         isl_map **map = (isl_map **)entry;
1522         isl_map *copy;
1523
1524         fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1525         copy = fn(isl_map_copy(*map));
1526         if (!copy)
1527                 return -1;
1528
1529         isl_map_free(*map);
1530         *map = copy;
1531
1532         return 0;
1533 }
1534
1535 static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1536         __isl_give isl_map *(*fn)(__isl_take isl_map *))
1537 {
1538         if (!umap)
1539                 return NULL;
1540
1541         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1542                                     &inplace_entry, &fn) < 0)
1543                 goto error;
1544
1545         return umap;
1546 error:
1547         isl_union_map_free(umap);
1548         return NULL;
1549 }
1550
1551 __isl_give isl_union_map *isl_union_map_coalesce(
1552         __isl_take isl_union_map *umap)
1553 {
1554         return inplace(umap, &isl_map_coalesce);
1555 }
1556
1557 __isl_give isl_union_set *isl_union_set_coalesce(
1558         __isl_take isl_union_set *uset)
1559 {
1560         return isl_union_map_coalesce(uset);
1561 }
1562
1563 __isl_give isl_union_map *isl_union_map_detect_equalities(
1564         __isl_take isl_union_map *umap)
1565 {
1566         return inplace(umap, &isl_map_detect_equalities);
1567 }
1568
1569 __isl_give isl_union_set *isl_union_set_detect_equalities(
1570         __isl_take isl_union_set *uset)
1571 {
1572         return isl_union_map_detect_equalities(uset);
1573 }
1574
1575 __isl_give isl_union_map *isl_union_map_compute_divs(
1576         __isl_take isl_union_map *umap)
1577 {
1578         return inplace(umap, &isl_map_compute_divs);
1579 }
1580
1581 __isl_give isl_union_set *isl_union_set_compute_divs(
1582         __isl_take isl_union_set *uset)
1583 {
1584         return isl_union_map_compute_divs(uset);
1585 }
1586
1587 static int lexmin_entry(void **entry, void *user)
1588 {
1589         isl_map **map = (isl_map **)entry;
1590
1591         *map = isl_map_lexmin(*map);
1592
1593         return *map ? 0 : -1;
1594 }
1595
1596 __isl_give isl_union_map *isl_union_map_lexmin(
1597         __isl_take isl_union_map *umap)
1598 {
1599         return un_op(umap, &lexmin_entry);
1600 }
1601
1602 __isl_give isl_union_set *isl_union_set_lexmin(
1603         __isl_take isl_union_set *uset)
1604 {
1605         return isl_union_map_lexmin(uset);
1606 }
1607
1608 static int lexmax_entry(void **entry, void *user)
1609 {
1610         isl_map **map = (isl_map **)entry;
1611
1612         *map = isl_map_lexmax(*map);
1613
1614         return *map ? 0 : -1;
1615 }
1616
1617 __isl_give isl_union_map *isl_union_map_lexmax(
1618         __isl_take isl_union_map *umap)
1619 {
1620         return un_op(umap, &lexmax_entry);
1621 }
1622
1623 __isl_give isl_union_set *isl_union_set_lexmax(
1624         __isl_take isl_union_set *uset)
1625 {
1626         return isl_union_map_lexmax(uset);
1627 }
1628
1629 static int universe_entry(void **entry, void *user)
1630 {
1631         isl_map *map = *entry;
1632         isl_union_map **res = user;
1633
1634         map = isl_map_universe(isl_map_get_space(map));
1635         *res = isl_union_map_add_map(*res, map);
1636
1637         return 0;
1638 }
1639
1640 __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1641 {
1642         return cond_un_op(umap, &universe_entry);
1643 }
1644
1645 __isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1646 {
1647         return isl_union_map_universe(uset);
1648 }
1649
1650 static int reverse_entry(void **entry, void *user)
1651 {
1652         isl_map *map = *entry;
1653         isl_union_map **res = user;
1654
1655         *res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1656
1657         return 0;
1658 }
1659
1660 __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1661 {
1662         return cond_un_op(umap, &reverse_entry);
1663 }
1664
1665 static int params_entry(void **entry, void *user)
1666 {
1667         isl_map *map = *entry;
1668         isl_union_set **res = user;
1669
1670         *res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1671
1672         return 0;
1673 }
1674
1675 /* Compute the parameter domain of the given union map.
1676  */
1677 __isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1678 {
1679         int empty;
1680
1681         empty = isl_union_map_is_empty(umap);
1682         if (empty < 0)
1683                 return isl_union_map_free(umap);
1684         if (empty)
1685                 return isl_set_empty(isl_union_map_get_space(umap));
1686         return isl_set_from_union_set(cond_un_op(umap, &params_entry));
1687 }
1688
1689 /* Compute the parameter domain of the given union set.
1690  */
1691 __isl_give isl_set *isl_union_set_params(__isl_take isl_union_set *uset)
1692 {
1693         return isl_union_map_params(uset);
1694 }
1695
1696 static int domain_entry(void **entry, void *user)
1697 {
1698         isl_map *map = *entry;
1699         isl_union_set **res = user;
1700
1701         *res = isl_union_set_add_set(*res, isl_map_domain(isl_map_copy(map)));
1702
1703         return 0;
1704 }
1705
1706 __isl_give isl_union_set *isl_union_map_domain(__isl_take isl_union_map *umap)
1707 {
1708         return cond_un_op(umap, &domain_entry);
1709 }
1710
1711 static int range_entry(void **entry, void *user)
1712 {
1713         isl_map *map = *entry;
1714         isl_union_set **res = user;
1715
1716         *res = isl_union_set_add_set(*res, isl_map_range(isl_map_copy(map)));
1717
1718         return 0;
1719 }
1720
1721 __isl_give isl_union_set *isl_union_map_range(__isl_take isl_union_map *umap)
1722 {
1723         return cond_un_op(umap, &range_entry);
1724 }
1725
1726 static int domain_map_entry(void **entry, void *user)
1727 {
1728         isl_map *map = *entry;
1729         isl_union_set **res = user;
1730
1731         *res = isl_union_map_add_map(*res,
1732                                         isl_map_domain_map(isl_map_copy(map)));
1733
1734         return 0;
1735 }
1736
1737 __isl_give isl_union_map *isl_union_map_domain_map(
1738         __isl_take isl_union_map *umap)
1739 {
1740         return cond_un_op(umap, &domain_map_entry);
1741 }
1742
1743 static int range_map_entry(void **entry, void *user)
1744 {
1745         isl_map *map = *entry;
1746         isl_union_set **res = user;
1747
1748         *res = isl_union_map_add_map(*res,
1749                                         isl_map_range_map(isl_map_copy(map)));
1750
1751         return 0;
1752 }
1753
1754 __isl_give isl_union_map *isl_union_map_range_map(
1755         __isl_take isl_union_map *umap)
1756 {
1757         return cond_un_op(umap, &range_map_entry);
1758 }
1759
1760 static int deltas_entry(void **entry, void *user)
1761 {
1762         isl_map *map = *entry;
1763         isl_union_set **res = user;
1764
1765         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1766                 return 0;
1767
1768         *res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
1769
1770         return 0;
1771 }
1772
1773 __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
1774 {
1775         return cond_un_op(umap, &deltas_entry);
1776 }
1777
1778 static int deltas_map_entry(void **entry, void *user)
1779 {
1780         isl_map *map = *entry;
1781         isl_union_map **res = user;
1782
1783         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
1784                 return 0;
1785
1786         *res = isl_union_map_add_map(*res,
1787                                      isl_map_deltas_map(isl_map_copy(map)));
1788
1789         return 0;
1790 }
1791
1792 __isl_give isl_union_map *isl_union_map_deltas_map(
1793         __isl_take isl_union_map *umap)
1794 {
1795         return cond_un_op(umap, &deltas_map_entry);
1796 }
1797
1798 static int identity_entry(void **entry, void *user)
1799 {
1800         isl_set *set = *entry;
1801         isl_union_map **res = user;
1802
1803         *res = isl_union_map_add_map(*res, isl_set_identity(isl_set_copy(set)));
1804
1805         return 0;
1806 }
1807
1808 __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_set *uset)
1809 {
1810         return cond_un_op(uset, &identity_entry);
1811 }
1812
1813 static int unwrap_entry(void **entry, void *user)
1814 {
1815         isl_set *set = *entry;
1816         isl_union_set **res = user;
1817
1818         if (!isl_set_is_wrapping(set))
1819                 return 0;
1820
1821         *res = isl_union_map_add_map(*res, isl_set_unwrap(isl_set_copy(set)));
1822
1823         return 0;
1824 }
1825
1826 __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_set *uset)
1827 {
1828         return cond_un_op(uset, &unwrap_entry);
1829 }
1830
1831 static int wrap_entry(void **entry, void *user)
1832 {
1833         isl_map *map = *entry;
1834         isl_union_set **res = user;
1835
1836         *res = isl_union_set_add_set(*res, isl_map_wrap(isl_map_copy(map)));
1837
1838         return 0;
1839 }
1840
1841 __isl_give isl_union_set *isl_union_map_wrap(__isl_take isl_union_map *umap)
1842 {
1843         return cond_un_op(umap, &wrap_entry);
1844 }
1845
1846 struct isl_union_map_is_subset_data {
1847         isl_union_map *umap2;
1848         int is_subset;
1849 };
1850
1851 static int is_subset_entry(void **entry, void *user)
1852 {
1853         struct isl_union_map_is_subset_data *data = user;
1854         uint32_t hash;
1855         struct isl_hash_table_entry *entry2;
1856         isl_map *map = *entry;
1857
1858         hash = isl_space_get_hash(map->dim);
1859         entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1860                                      hash, &has_dim, map->dim, 0);
1861         if (!entry2) {
1862                 int empty = isl_map_is_empty(map);
1863                 if (empty < 0)
1864                         return -1;
1865                 if (empty)
1866                         return 0;
1867                 data->is_subset = 0;
1868                 return -1;
1869         }
1870
1871         data->is_subset = isl_map_is_subset(map, entry2->data);
1872         if (data->is_subset < 0 || !data->is_subset)
1873                 return -1;
1874
1875         return 0;
1876 }
1877
1878 int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
1879         __isl_keep isl_union_map *umap2)
1880 {
1881         struct isl_union_map_is_subset_data data = { NULL, 1 };
1882
1883         umap1 = isl_union_map_copy(umap1);
1884         umap2 = isl_union_map_copy(umap2);
1885         umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1886         umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1887
1888         if (!umap1 || !umap2)
1889                 goto error;
1890
1891         data.umap2 = umap2;
1892         if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1893                                    &is_subset_entry, &data) < 0 &&
1894             data.is_subset)
1895                 goto error;
1896
1897         isl_union_map_free(umap1);
1898         isl_union_map_free(umap2);
1899
1900         return data.is_subset;
1901 error:
1902         isl_union_map_free(umap1);
1903         isl_union_map_free(umap2);
1904         return -1;
1905 }
1906
1907 int isl_union_set_is_subset(__isl_keep isl_union_set *uset1,
1908         __isl_keep isl_union_set *uset2)
1909 {
1910         return isl_union_map_is_subset(uset1, uset2);
1911 }
1912
1913 int isl_union_map_is_equal(__isl_keep isl_union_map *umap1,
1914         __isl_keep isl_union_map *umap2)
1915 {
1916         int is_subset;
1917
1918         if (!umap1 || !umap2)
1919                 return -1;
1920         is_subset = isl_union_map_is_subset(umap1, umap2);
1921         if (is_subset != 1)
1922                 return is_subset;
1923         is_subset = isl_union_map_is_subset(umap2, umap1);
1924         return is_subset;
1925 }
1926
1927 int isl_union_set_is_equal(__isl_keep isl_union_set *uset1,
1928         __isl_keep isl_union_set *uset2)
1929 {
1930         return isl_union_map_is_equal(uset1, uset2);
1931 }
1932
1933 int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1,
1934         __isl_keep isl_union_map *umap2)
1935 {
1936         int is_subset;
1937
1938         if (!umap1 || !umap2)
1939                 return -1;
1940         is_subset = isl_union_map_is_subset(umap1, umap2);
1941         if (is_subset != 1)
1942                 return is_subset;
1943         is_subset = isl_union_map_is_subset(umap2, umap1);
1944         if (is_subset == -1)
1945                 return is_subset;
1946         return !is_subset;
1947 }
1948
1949 int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1,
1950         __isl_keep isl_union_set *uset2)
1951 {
1952         return isl_union_map_is_strict_subset(uset1, uset2);
1953 }
1954
1955 static int sample_entry(void **entry, void *user)
1956 {
1957         isl_basic_map **sample = (isl_basic_map **)user;
1958         isl_map *map = *entry;
1959
1960         *sample = isl_map_sample(isl_map_copy(map));
1961         if (!*sample)
1962                 return -1;
1963         if (!isl_basic_map_plain_is_empty(*sample))
1964                 return -1;
1965         return 0;
1966 }
1967
1968 __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
1969 {
1970         isl_basic_map *sample = NULL;
1971
1972         if (!umap)
1973                 return NULL;
1974
1975         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1976                                    &sample_entry, &sample) < 0 &&
1977             !sample)
1978                 goto error;
1979
1980         if (!sample)
1981                 sample = isl_basic_map_empty(isl_union_map_get_space(umap));
1982
1983         isl_union_map_free(umap);
1984
1985         return sample;
1986 error:
1987         isl_union_map_free(umap);
1988         return NULL;
1989 }
1990
1991 __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
1992 {
1993         return (isl_basic_set *)isl_union_map_sample(uset);
1994 }
1995
1996 struct isl_forall_data {
1997         int res;
1998         int (*fn)(__isl_keep isl_map *map);
1999 };
2000
2001 static int forall_entry(void **entry, void *user)
2002 {
2003         struct isl_forall_data *data = user;
2004         isl_map *map = *entry;
2005
2006         data->res = data->fn(map);
2007         if (data->res < 0)
2008                 return -1;
2009
2010         if (!data->res)
2011                 return -1;
2012
2013         return 0;
2014 }
2015
2016 static int union_map_forall(__isl_keep isl_union_map *umap,
2017         int (*fn)(__isl_keep isl_map *map))
2018 {
2019         struct isl_forall_data data = { 1, fn };
2020
2021         if (!umap)
2022                 return -1;
2023
2024         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2025                                    &forall_entry, &data) < 0 && data.res)
2026                 return -1;
2027
2028         return data.res;
2029 }
2030
2031 struct isl_forall_user_data {
2032         int res;
2033         int (*fn)(__isl_keep isl_map *map, void *user);
2034         void *user;
2035 };
2036
2037 static int forall_user_entry(void **entry, void *user)
2038 {
2039         struct isl_forall_user_data *data = user;
2040         isl_map *map = *entry;
2041
2042         data->res = data->fn(map, data->user);
2043         if (data->res < 0)
2044                 return -1;
2045
2046         if (!data->res)
2047                 return -1;
2048
2049         return 0;
2050 }
2051
2052 /* Check if fn(map, user) returns true for all maps "map" in umap.
2053  */
2054 static int union_map_forall_user(__isl_keep isl_union_map *umap,
2055         int (*fn)(__isl_keep isl_map *map, void *user), void *user)
2056 {
2057         struct isl_forall_user_data data = { 1, fn, user };
2058
2059         if (!umap)
2060                 return -1;
2061
2062         if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
2063                                    &forall_user_entry, &data) < 0 && data.res)
2064                 return -1;
2065
2066         return data.res;
2067 }
2068
2069 int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2070 {
2071         return union_map_forall(umap, &isl_map_is_empty);
2072 }
2073
2074 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2075 {
2076         return isl_union_map_is_empty(uset);
2077 }
2078
2079 static int is_subset_of_identity(__isl_keep isl_map *map)
2080 {
2081         int is_subset;
2082         isl_space *dim;
2083         isl_map *id;
2084
2085         if (!map)
2086                 return -1;
2087
2088         if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
2089                 return 0;
2090
2091         dim = isl_map_get_space(map);
2092         id = isl_map_identity(dim);
2093
2094         is_subset = isl_map_is_subset(map, id);
2095
2096         isl_map_free(id);
2097
2098         return is_subset;
2099 }
2100
2101 /* Check if the given map is single-valued.
2102  * We simply compute
2103  *
2104  *      M \circ M^-1
2105  *
2106  * and check if the result is a subset of the identity mapping.
2107  */
2108 int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
2109 {
2110         isl_union_map *test;
2111         int sv;
2112
2113         if (isl_union_map_n_map(umap) == 1) {
2114                 isl_map *map;
2115                 umap = isl_union_map_copy(umap);
2116                 map = isl_map_from_union_map(umap);
2117                 sv = isl_map_is_single_valued(map);
2118                 isl_map_free(map);
2119                 return sv;
2120         }
2121
2122         test = isl_union_map_reverse(isl_union_map_copy(umap));
2123         test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
2124
2125         sv = union_map_forall(test, &is_subset_of_identity);
2126
2127         isl_union_map_free(test);
2128
2129         return sv;
2130 }
2131
2132 int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
2133 {
2134         int in;
2135
2136         umap = isl_union_map_copy(umap);
2137         umap = isl_union_map_reverse(umap);
2138         in = isl_union_map_is_single_valued(umap);
2139         isl_union_map_free(umap);
2140
2141         return in;
2142 }
2143
2144 /* Represents a map that has a fixed value (v) for one of its
2145  * range dimensions.
2146  * The map in this structure is not reference counted, so it
2147  * is only valid while the isl_union_map from which it was
2148  * obtained is still alive.
2149  */
2150 struct isl_fixed_map {
2151         isl_int v;
2152         isl_map *map;
2153 };
2154
2155 static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
2156         int n)
2157 {
2158         int i;
2159         struct isl_fixed_map *v;
2160
2161         v = isl_calloc_array(ctx, struct isl_fixed_map, n);
2162         if (!v)
2163                 return NULL;
2164         for (i = 0; i < n; ++i)
2165                 isl_int_init(v[i].v);
2166         return v;
2167 }
2168
2169 static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
2170 {
2171         int i;
2172
2173         if (!v)
2174                 return;
2175         for (i = 0; i < n; ++i)
2176                 isl_int_clear(v[i].v);
2177         free(v);
2178 }
2179
2180 /* Compare the "v" field of two isl_fixed_map structs.
2181  */
2182 static int qsort_fixed_map_cmp(const void *p1, const void *p2)
2183 {
2184         const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
2185         const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
2186
2187         return isl_int_cmp(e1->v, e2->v);
2188 }
2189
2190 /* Internal data structure used while checking whether all maps
2191  * in a union_map have a fixed value for a given output dimension.
2192  * v is the list of maps, with the fixed value for the dimension
2193  * n is the number of maps considered so far
2194  * pos is the output dimension under investigation
2195  */
2196 struct isl_fixed_dim_data {
2197         struct isl_fixed_map *v;
2198         int n;
2199         int pos;
2200 };
2201
2202 static int fixed_at_pos(__isl_keep isl_map *map, void *user)
2203 {
2204         struct isl_fixed_dim_data *data = user;
2205
2206         data->v[data->n].map = map;
2207         return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
2208                                       &data->v[data->n++].v);
2209 }
2210
2211 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2212         int first, int n_range);
2213
2214 /* Given a list of the maps, with their fixed values at output dimension "pos",
2215  * check whether the ranges of the maps form an obvious partition.
2216  *
2217  * We first sort the maps according to their fixed values.
2218  * If all maps have a different value, then we know the ranges form
2219  * a partition.
2220  * Otherwise, we collect the maps with the same fixed value and
2221  * check whether each such collection is obviously injective
2222  * based on later dimensions.
2223  */
2224 static int separates(struct isl_fixed_map *v, int n,
2225         __isl_take isl_space *dim, int pos, int n_range)
2226 {
2227         int i;
2228
2229         if (!v)
2230                 goto error;
2231
2232         qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
2233
2234         for (i = 0; i + 1 < n; ++i) {
2235                 int j, k;
2236                 isl_union_map *part;
2237                 int injective;
2238
2239                 for (j = i + 1; j < n; ++j)
2240                         if (isl_int_ne(v[i].v, v[j].v))
2241                                 break;
2242
2243                 if (j == i + 1)
2244                         continue;
2245
2246                 part = isl_union_map_alloc(isl_space_copy(dim), j - i);
2247                 for (k = i; k < j; ++k)
2248                         part = isl_union_map_add_map(part,
2249                                                      isl_map_copy(v[k].map));
2250
2251                 injective = plain_injective_on_range(part, pos + 1, n_range);
2252                 if (injective < 0)
2253                         goto error;
2254                 if (!injective)
2255                         break;
2256
2257                 i = j - 1;
2258         }
2259
2260         isl_space_free(dim);
2261         free_isl_fixed_map_array(v, n);
2262         return i + 1 >= n;
2263 error:
2264         isl_space_free(dim);
2265         free_isl_fixed_map_array(v, n);
2266         return -1;
2267 }
2268
2269 /* Check whether the maps in umap have obviously distinct ranges.
2270  * In particular, check for an output dimension in the range
2271  * [first,n_range) for which all maps have a fixed value
2272  * and then check if these values, possibly along with fixed values
2273  * at later dimensions, entail distinct ranges.
2274  */
2275 static int plain_injective_on_range(__isl_take isl_union_map *umap,
2276         int first, int n_range)
2277 {
2278         isl_ctx *ctx;
2279         int n;
2280         struct isl_fixed_dim_data data = { NULL };
2281
2282         ctx = isl_union_map_get_ctx(umap);
2283
2284         n = isl_union_map_n_map(umap);
2285         if (!umap)
2286                 goto error;
2287
2288         if (n <= 1) {
2289                 isl_union_map_free(umap);
2290                 return 1;
2291         }
2292
2293         if (first >= n_range) {
2294                 isl_union_map_free(umap);
2295                 return 0;
2296         }
2297
2298         data.v = alloc_isl_fixed_map_array(ctx, n);
2299         if (!data.v)
2300                 goto error;
2301
2302         for (data.pos = first; data.pos < n_range; ++data.pos) {
2303                 int fixed;
2304                 int injective;
2305                 isl_space *dim;
2306
2307                 data.n = 0;
2308                 fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
2309                 if (fixed < 0)
2310                         goto error;
2311                 if (!fixed)
2312                         continue;
2313                 dim = isl_union_map_get_space(umap);
2314                 injective = separates(data.v, n, dim, data.pos, n_range);
2315                 isl_union_map_free(umap);
2316                 return injective;
2317         }
2318
2319         free_isl_fixed_map_array(data.v, n);
2320         isl_union_map_free(umap);
2321
2322         return 0;
2323 error:
2324         free_isl_fixed_map_array(data.v, n);
2325         isl_union_map_free(umap);
2326         return -1;
2327 }
2328
2329 /* Check whether the maps in umap that map to subsets of "ran"
2330  * have obviously distinct ranges.
2331  */
2332 static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
2333 {
2334         isl_union_map *umap = user;
2335
2336         umap = isl_union_map_copy(umap);
2337         umap = isl_union_map_intersect_range(umap,
2338                         isl_union_set_from_set(isl_set_copy(ran)));
2339         return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
2340 }
2341
2342 /* Check if the given union_map is obviously injective.
2343  *
2344  * In particular, we first check if all individual maps are obviously
2345  * injective and then check if all the ranges of these maps are
2346  * obviously disjoint.
2347  */
2348 int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
2349 {
2350         int in;
2351         isl_union_map *univ;
2352         isl_union_set *ran;
2353
2354         in = union_map_forall(umap, &isl_map_plain_is_injective);
2355         if (in < 0)
2356                 return -1;
2357         if (!in)
2358                 return 0;
2359
2360         univ = isl_union_map_universe(isl_union_map_copy(umap));
2361         ran = isl_union_map_range(univ);
2362
2363         in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
2364
2365         isl_union_set_free(ran);
2366
2367         return in;
2368 }
2369
2370 int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
2371 {
2372         int sv;
2373
2374         sv = isl_union_map_is_single_valued(umap);
2375         if (sv < 0 || !sv)
2376                 return sv;
2377
2378         return isl_union_map_is_injective(umap);
2379 }
2380
2381 static int zip_entry(void **entry, void *user)
2382 {
2383         isl_map *map = *entry;
2384         isl_union_map **res = user;
2385
2386         if (!isl_map_can_zip(map))
2387                 return 0;
2388
2389         *res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
2390
2391         return 0;
2392 }
2393
2394 __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
2395 {
2396         return cond_un_op(umap, &zip_entry);
2397 }
2398
2399 static int uncurry_entry(void **entry, void *user)
2400 {
2401         isl_map *map = *entry;
2402         isl_union_map **res = user;
2403
2404         if (!isl_map_can_uncurry(map))
2405                 return 0;
2406
2407         *res = isl_union_map_add_map(*res, isl_map_uncurry(isl_map_copy(map)));
2408
2409         return 0;
2410 }
2411
2412 /* Given a union map, take the maps of the form A -> (B -> C) and
2413  * return the union of the corresponding maps (A -> B) -> C.
2414  */
2415 __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap)
2416 {
2417         return cond_un_op(umap, &uncurry_entry);
2418 }
2419
2420 static int curry_entry(void **entry, void *user)
2421 {
2422         isl_map *map = *entry;
2423         isl_union_map **res = user;
2424
2425         if (!isl_map_can_curry(map))
2426                 return 0;
2427
2428         *res = isl_union_map_add_map(*res, isl_map_curry(isl_map_copy(map)));
2429
2430         return 0;
2431 }
2432
2433 /* Given a union map, take the maps of the form (A -> B) -> C and
2434  * return the union of the corresponding maps A -> (B -> C).
2435  */
2436 __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap)
2437 {
2438         return cond_un_op(umap, &curry_entry);
2439 }
2440
2441 static int lift_entry(void **entry, void *user)
2442 {
2443         isl_set *set = *entry;
2444         isl_union_set **res = user;
2445
2446         *res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
2447
2448         return 0;
2449 }
2450
2451 __isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
2452 {
2453         return cond_un_op(uset, &lift_entry);
2454 }
2455
2456 static int coefficients_entry(void **entry, void *user)
2457 {
2458         isl_set *set = *entry;
2459         isl_union_set **res = user;
2460
2461         set = isl_set_copy(set);
2462         set = isl_set_from_basic_set(isl_set_coefficients(set));
2463         *res = isl_union_set_add_set(*res, set);
2464
2465         return 0;
2466 }
2467
2468 __isl_give isl_union_set *isl_union_set_coefficients(
2469         __isl_take isl_union_set *uset)
2470 {
2471         isl_ctx *ctx;
2472         isl_space *dim;
2473         isl_union_set *res;
2474
2475         if (!uset)
2476                 return NULL;
2477
2478         ctx = isl_union_set_get_ctx(uset);
2479         dim = isl_space_set_alloc(ctx, 0, 0);
2480         res = isl_union_map_alloc(dim, uset->table.n);
2481         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2482                                    &coefficients_entry, &res) < 0)
2483                 goto error;
2484
2485         isl_union_set_free(uset);
2486         return res;
2487 error:
2488         isl_union_set_free(uset);
2489         isl_union_set_free(res);
2490         return NULL;
2491 }
2492
2493 static int solutions_entry(void **entry, void *user)
2494 {
2495         isl_set *set = *entry;
2496         isl_union_set **res = user;
2497
2498         set = isl_set_copy(set);
2499         set = isl_set_from_basic_set(isl_set_solutions(set));
2500         if (!*res)
2501                 *res = isl_union_set_from_set(set);
2502         else
2503                 *res = isl_union_set_add_set(*res, set);
2504
2505         if (!*res)
2506                 return -1;
2507
2508         return 0;
2509 }
2510
2511 __isl_give isl_union_set *isl_union_set_solutions(
2512         __isl_take isl_union_set *uset)
2513 {
2514         isl_union_set *res = NULL;
2515
2516         if (!uset)
2517                 return NULL;
2518
2519         if (uset->table.n == 0) {
2520                 res = isl_union_set_empty(isl_union_set_get_space(uset));
2521                 isl_union_set_free(uset);
2522                 return res;
2523         }
2524
2525         if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
2526                                    &solutions_entry, &res) < 0)
2527                 goto error;
2528
2529         isl_union_set_free(uset);
2530         return res;
2531 error:
2532         isl_union_set_free(uset);
2533         isl_union_set_free(res);
2534         return NULL;
2535 }
2536
2537 /* Internal data structure for isl_union_map_preimage_domain_multi_aff.
2538  *
2539  * "ma" is the function under which the preimage should be taken.
2540  * "space" is the space of "ma".
2541  * "res" collects the results.
2542  */
2543 struct isl_union_map_preimage_domain_data {
2544         isl_space *space;
2545         isl_multi_aff *ma;
2546         isl_union_map *res;
2547 };
2548
2549 /* Compute the preimage of the domain of *entry under the function
2550  * represented by data->ma, provided the domain space of *entry
2551  * match the target space of data->ma, and add the result to data->res.
2552  */
2553 static int preimage_domain_entry(void **entry, void *user)
2554 {
2555         int m;
2556         isl_map *map = *entry;
2557         struct isl_union_map_preimage_domain_data *data = user;
2558         int empty;
2559
2560         m = isl_space_tuple_match(map->dim, isl_dim_in,
2561                                         data->space, isl_dim_out);
2562         if (m < 0)
2563                 return -1;
2564         if (!m)
2565                 return 0;
2566
2567         map = isl_map_copy(map);
2568         map = isl_map_preimage_domain_multi_aff(map,
2569                                                 isl_multi_aff_copy(data->ma));
2570
2571         empty = isl_map_is_empty(map);
2572         if (empty < 0 || empty) {
2573                 isl_map_free(map);
2574                 return empty < 0 ? -1 : 0;
2575         }
2576
2577         data->res = isl_union_map_add_map(data->res, map);
2578
2579         return 0;
2580 }
2581
2582 /* Compute the preimage of the domain of "umap" under the function
2583  * represented by "ma".
2584  * In other words, plug in "ma" in the domain of "umap".
2585  * The result contains maps that live in the same spaces as the maps of "umap"
2586  * with domain space equal to the target space of "ma",
2587  * except that the domain has been replaced by the domain space of "ma".
2588  */
2589 __isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff(
2590         __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma)
2591 {
2592         isl_ctx *ctx;
2593         isl_space *space;
2594         struct isl_union_map_preimage_domain_data data;
2595
2596         if (!umap || !ma)
2597                 goto error;
2598
2599         ctx = isl_union_map_get_ctx(umap);
2600         space = isl_union_map_get_space(umap);
2601         data.space = isl_multi_aff_get_space(ma);
2602         data.ma = ma;
2603         data.res = isl_union_map_alloc(space, umap->table.n);
2604         if (isl_hash_table_foreach(ctx, &umap->table, &preimage_domain_entry,
2605                                         &data) < 0)
2606                 data.res = isl_union_map_free(data.res);
2607
2608         isl_space_free(data.space);
2609         isl_union_map_free(umap);
2610         isl_multi_aff_free(ma);
2611         return data.res;
2612 error:
2613         isl_union_map_free(umap);
2614         isl_multi_aff_free(ma);
2615         return NULL;
2616 }