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 */
24int 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
40static __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		return isl_union_map_free(umap);
57
58	return umap;
59}
60
61__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
62{
63	return isl_union_map_alloc(dim, 16);
64}
65
66__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
67{
68	return isl_union_map_empty(dim);
69}
70
71isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap)
72{
73	return umap ? umap->dim->ctx : NULL;
74}
75
76isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
77{
78	return uset ? uset->dim->ctx : NULL;
79}
80
81__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
82{
83	if (!umap)
84		return NULL;
85	return isl_space_copy(umap->dim);
86}
87
88__isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
89{
90	return isl_union_map_get_space(uset);
91}
92
93static int free_umap_entry(void **entry, void *user)
94{
95	isl_map *map = *entry;
96	isl_map_free(map);
97	return 0;
98}
99
100static int add_map(__isl_take isl_map *map, void *user)
101{
102	isl_union_map **umap = (isl_union_map **)user;
103
104	*umap = isl_union_map_add_map(*umap, map);
105
106	return 0;
107}
108
109__isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
110{
111	isl_union_map *dup;
112
113	if (!umap)
114		return NULL;
115
116	dup = isl_union_map_empty(isl_space_copy(umap->dim));
117	if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
118		goto error;
119	return dup;
120error:
121	isl_union_map_free(dup);
122	return NULL;
123}
124
125__isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap)
126{
127	if (!umap)
128		return NULL;
129
130	if (umap->ref == 1)
131		return umap;
132	umap->ref--;
133	return isl_union_map_dup(umap);
134}
135
136struct isl_union_align {
137	isl_reordering *exp;
138	isl_union_map *res;
139};
140
141static int align_entry(void **entry, void *user)
142{
143	isl_map *map = *entry;
144	isl_reordering *exp;
145	struct isl_union_align *data = user;
146
147	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
148				    isl_map_get_space(map));
149
150	data->res = isl_union_map_add_map(data->res,
151					isl_map_realign(isl_map_copy(map), exp));
152
153	return 0;
154}
155
156/* Align the parameters of umap along those of model.
157 * The result has the parameters of model first, in the same order
158 * as they appear in model, followed by any remaining parameters of
159 * umap that do not appear in model.
160 */
161__isl_give isl_union_map *isl_union_map_align_params(
162	__isl_take isl_union_map *umap, __isl_take isl_space *model)
163{
164	struct isl_union_align data = { NULL, NULL };
165
166	if (!umap || !model)
167		goto error;
168
169	if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
170		isl_space_free(model);
171		return umap;
172	}
173
174	model = isl_space_params(model);
175	data.exp = isl_parameter_alignment_reordering(umap->dim, model);
176	if (!data.exp)
177		goto error;
178
179	data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
180					umap->table.n);
181	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
182					&align_entry, &data) < 0)
183		goto error;
184
185	isl_reordering_free(data.exp);
186	isl_union_map_free(umap);
187	isl_space_free(model);
188	return data.res;
189error:
190	isl_reordering_free(data.exp);
191	isl_union_map_free(umap);
192	isl_union_map_free(data.res);
193	isl_space_free(model);
194	return NULL;
195}
196
197__isl_give isl_union_set *isl_union_set_align_params(
198	__isl_take isl_union_set *uset, __isl_take isl_space *model)
199{
200	return isl_union_map_align_params(uset, model);
201}
202
203__isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
204	__isl_take isl_union_map *umap2)
205{
206	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
207	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
208
209	umap1 = isl_union_map_cow(umap1);
210
211	if (!umap1 || !umap2)
212		goto error;
213
214	if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0)
215		goto error;
216
217	isl_union_map_free(umap2);
218
219	return umap1;
220error:
221	isl_union_map_free(umap1);
222	isl_union_map_free(umap2);
223	return NULL;
224}
225
226__isl_give isl_union_set *isl_union_set_union(__isl_take isl_union_set *uset1,
227	__isl_take isl_union_set *uset2)
228{
229	return isl_union_map_union(uset1, uset2);
230}
231
232__isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap)
233{
234	if (!umap)
235		return NULL;
236
237	umap->ref++;
238	return umap;
239}
240
241__isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
242{
243	return isl_union_map_copy(uset);
244}
245
246void *isl_union_map_free(__isl_take isl_union_map *umap)
247{
248	if (!umap)
249		return NULL;
250
251	if (--umap->ref > 0)
252		return NULL;
253
254	isl_hash_table_foreach(umap->dim->ctx, &umap->table,
255			       &free_umap_entry, NULL);
256	isl_hash_table_clear(&umap->table);
257	isl_space_free(umap->dim);
258	free(umap);
259	return NULL;
260}
261
262void *isl_union_set_free(__isl_take isl_union_set *uset)
263{
264	return isl_union_map_free(uset);
265}
266
267static int has_dim(const void *entry, const void *val)
268{
269	isl_map *map = (isl_map *)entry;
270	isl_space *dim = (isl_space *)val;
271
272	return isl_space_is_equal(map->dim, dim);
273}
274
275__isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
276	__isl_take isl_map *map)
277{
278	uint32_t hash;
279	struct isl_hash_table_entry *entry;
280
281	if (!map || !umap)
282		goto error;
283
284	if (isl_map_plain_is_empty(map)) {
285		isl_map_free(map);
286		return umap;
287	}
288
289	if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
290		umap = isl_union_map_align_params(umap, isl_map_get_space(map));
291		map = isl_map_align_params(map, isl_union_map_get_space(umap));
292	}
293
294	umap = isl_union_map_cow(umap);
295
296	if (!map || !umap)
297		goto error;
298
299	hash = isl_space_get_hash(map->dim);
300	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
301				    &has_dim, map->dim, 1);
302	if (!entry)
303		goto error;
304
305	if (!entry->data)
306		entry->data = map;
307	else {
308		entry->data = isl_map_union(entry->data, isl_map_copy(map));
309		if (!entry->data)
310			goto error;
311		isl_map_free(map);
312	}
313
314	return umap;
315error:
316	isl_map_free(map);
317	isl_union_map_free(umap);
318	return NULL;
319}
320
321__isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
322	__isl_take isl_set *set)
323{
324	return isl_union_map_add_map(uset, (isl_map *)set);
325}
326
327__isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
328{
329	isl_space *dim;
330	isl_union_map *umap;
331
332	if (!map)
333		return NULL;
334
335	dim = isl_map_get_space(map);
336	dim = isl_space_params(dim);
337	umap = isl_union_map_empty(dim);
338	umap = isl_union_map_add_map(umap, map);
339
340	return umap;
341}
342
343__isl_give isl_union_set *isl_union_set_from_set(__isl_take isl_set *set)
344{
345	return isl_union_map_from_map((isl_map *)set);
346}
347
348__isl_give isl_union_map *isl_union_map_from_basic_map(
349	__isl_take isl_basic_map *bmap)
350{
351	return isl_union_map_from_map(isl_map_from_basic_map(bmap));
352}
353
354__isl_give isl_union_set *isl_union_set_from_basic_set(
355	__isl_take isl_basic_set *bset)
356{
357	return isl_union_map_from_basic_map(bset);
358}
359
360struct isl_union_map_foreach_data
361{
362	int (*fn)(__isl_take isl_map *map, void *user);
363	void *user;
364};
365
366static int call_on_copy(void **entry, void *user)
367{
368	isl_map *map = *entry;
369	struct isl_union_map_foreach_data *data;
370	data = (struct isl_union_map_foreach_data *)user;
371
372	return data->fn(isl_map_copy(map), data->user);
373}
374
375int isl_union_map_n_map(__isl_keep isl_union_map *umap)
376{
377	return umap ? umap->table.n : 0;
378}
379
380int isl_union_set_n_set(__isl_keep isl_union_set *uset)
381{
382	return uset ? uset->table.n : 0;
383}
384
385int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
386	int (*fn)(__isl_take isl_map *map, void *user), void *user)
387{
388	struct isl_union_map_foreach_data data = { fn, user };
389
390	if (!umap)
391		return -1;
392
393	return isl_hash_table_foreach(umap->dim->ctx, &umap->table,
394				      &call_on_copy, &data);
395}
396
397static int copy_map(void **entry, void *user)
398{
399	isl_map *map = *entry;
400	isl_map **map_p = user;
401
402	*map_p = isl_map_copy(map);
403
404	return -1;
405}
406
407__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
408{
409	isl_ctx *ctx;
410	isl_map *map = NULL;
411
412	if (!umap)
413		return NULL;
414	ctx = isl_union_map_get_ctx(umap);
415	if (umap->table.n != 1)
416		isl_die(ctx, isl_error_invalid,
417			"union map needs to contain elements in exactly "
418			"one space", return isl_union_map_free(umap));
419
420	isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
421
422	isl_union_map_free(umap);
423
424	return map;
425}
426
427__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
428{
429	return isl_map_from_union_map(uset);
430}
431
432/* Extract the map in "umap" that lives in the given space (ignoring
433 * parameters).
434 */
435__isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
436	__isl_take isl_space *space)
437{
438	uint32_t hash;
439	struct isl_hash_table_entry *entry;
440
441	space = isl_space_drop_dims(space, isl_dim_param,
442					0, isl_space_dim(space, isl_dim_param));
443	space = isl_space_align_params(space, isl_union_map_get_space(umap));
444	if (!umap || !space)
445		goto error;
446
447	hash = isl_space_get_hash(space);
448	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
449				    &has_dim, space, 0);
450	if (!entry)
451		return isl_map_empty(space);
452	isl_space_free(space);
453	return isl_map_copy(entry->data);
454error:
455	isl_space_free(space);
456	return NULL;
457}
458
459__isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
460	__isl_take isl_space *dim)
461{
462	return (isl_set *)isl_union_map_extract_map(uset, dim);
463}
464
465/* Check if umap contains a map in the given space.
466 */
467__isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
468	__isl_keep isl_space *dim)
469{
470	uint32_t hash;
471	struct isl_hash_table_entry *entry;
472
473	if (!umap || !dim)
474		return -1;
475
476	hash = isl_space_get_hash(dim);
477	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
478				    &has_dim, dim, 0);
479	return !!entry;
480}
481
482__isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
483	__isl_keep isl_space *dim)
484{
485	return isl_union_map_contains(uset, dim);
486}
487
488int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
489	int (*fn)(__isl_take isl_set *set, void *user), void *user)
490{
491	return isl_union_map_foreach_map(uset,
492		(int(*)(__isl_take isl_map *, void*))fn, user);
493}
494
495struct isl_union_set_foreach_point_data {
496	int (*fn)(__isl_take isl_point *pnt, void *user);
497	void *user;
498};
499
500static int foreach_point(__isl_take isl_set *set, void *user)
501{
502	struct isl_union_set_foreach_point_data *data = user;
503	int r;
504
505	r = isl_set_foreach_point(set, data->fn, data->user);
506	isl_set_free(set);
507
508	return r;
509}
510
511int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
512	int (*fn)(__isl_take isl_point *pnt, void *user), void *user)
513{
514	struct isl_union_set_foreach_point_data data = { fn, user };
515	return isl_union_set_foreach_set(uset, &foreach_point, &data);
516}
517
518struct isl_union_map_gen_bin_data {
519	isl_union_map *umap2;
520	isl_union_map *res;
521};
522
523static int subtract_entry(void **entry, void *user)
524{
525	struct isl_union_map_gen_bin_data *data = user;
526	uint32_t hash;
527	struct isl_hash_table_entry *entry2;
528	isl_map *map = *entry;
529
530	hash = isl_space_get_hash(map->dim);
531	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
532				     hash, &has_dim, map->dim, 0);
533	map = isl_map_copy(map);
534	if (entry2) {
535		int empty;
536		map = isl_map_subtract(map, isl_map_copy(entry2->data));
537
538		empty = isl_map_is_empty(map);
539		if (empty < 0) {
540			isl_map_free(map);
541			return -1;
542		}
543		if (empty) {
544			isl_map_free(map);
545			return 0;
546		}
547	}
548	data->res = isl_union_map_add_map(data->res, map);
549
550	return 0;
551}
552
553static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
554	__isl_take isl_union_map *umap2, int (*fn)(void **, void *))
555{
556	struct isl_union_map_gen_bin_data data = { NULL, NULL };
557
558	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
559	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
560
561	if (!umap1 || !umap2)
562		goto error;
563
564	data.umap2 = umap2;
565	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
566				       umap1->table.n);
567	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
568				   fn, &data) < 0)
569		goto error;
570
571	isl_union_map_free(umap1);
572	isl_union_map_free(umap2);
573	return data.res;
574error:
575	isl_union_map_free(umap1);
576	isl_union_map_free(umap2);
577	isl_union_map_free(data.res);
578	return NULL;
579}
580
581__isl_give isl_union_map *isl_union_map_subtract(
582	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
583{
584	return gen_bin_op(umap1, umap2, &subtract_entry);
585}
586
587__isl_give isl_union_set *isl_union_set_subtract(
588	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
589{
590	return isl_union_map_subtract(uset1, uset2);
591}
592
593struct isl_union_map_gen_bin_set_data {
594	isl_set *set;
595	isl_union_map *res;
596};
597
598static int intersect_params_entry(void **entry, void *user)
599{
600	struct isl_union_map_gen_bin_set_data *data = user;
601	isl_map *map = *entry;
602	int empty;
603
604	map = isl_map_copy(map);
605	map = isl_map_intersect_params(map, isl_set_copy(data->set));
606
607	empty = isl_map_is_empty(map);
608	if (empty < 0) {
609		isl_map_free(map);
610		return -1;
611	}
612
613	data->res = isl_union_map_add_map(data->res, map);
614
615	return 0;
616}
617
618static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap,
619	__isl_take isl_set *set, int (*fn)(void **, void *))
620{
621	struct isl_union_map_gen_bin_set_data data = { NULL, NULL };
622
623	umap = isl_union_map_align_params(umap, isl_set_get_space(set));
624	set = isl_set_align_params(set, isl_union_map_get_space(umap));
625
626	if (!umap || !set)
627		goto error;
628
629	data.set = set;
630	data.res = isl_union_map_alloc(isl_space_copy(umap->dim),
631				       umap->table.n);
632	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
633				   fn, &data) < 0)
634		goto error;
635
636	isl_union_map_free(umap);
637	isl_set_free(set);
638	return data.res;
639error:
640	isl_union_map_free(umap);
641	isl_set_free(set);
642	isl_union_map_free(data.res);
643	return NULL;
644}
645
646__isl_give isl_union_map *isl_union_map_intersect_params(
647	__isl_take isl_union_map *umap, __isl_take isl_set *set)
648{
649	return gen_bin_set_op(umap, set, &intersect_params_entry);
650}
651
652__isl_give isl_union_set *isl_union_set_intersect_params(
653	__isl_take isl_union_set *uset, __isl_take isl_set *set)
654{
655	return isl_union_map_intersect_params(uset, set);
656}
657
658static __isl_give isl_union_map *union_map_intersect_params(
659	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
660{
661	return isl_union_map_intersect_params(umap,
662						isl_set_from_union_set(uset));
663}
664
665static __isl_give isl_union_map *union_map_gist_params(
666	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
667{
668	return isl_union_map_gist_params(umap, isl_set_from_union_set(uset));
669}
670
671struct isl_union_map_match_bin_data {
672	isl_union_map *umap2;
673	isl_union_map *res;
674	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*);
675};
676
677static int match_bin_entry(void **entry, void *user)
678{
679	struct isl_union_map_match_bin_data *data = user;
680	uint32_t hash;
681	struct isl_hash_table_entry *entry2;
682	isl_map *map = *entry;
683	int empty;
684
685	hash = isl_space_get_hash(map->dim);
686	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
687				     hash, &has_dim, map->dim, 0);
688	if (!entry2)
689		return 0;
690
691	map = isl_map_copy(map);
692	map = data->fn(map, isl_map_copy(entry2->data));
693
694	empty = isl_map_is_empty(map);
695	if (empty < 0) {
696		isl_map_free(map);
697		return -1;
698	}
699	if (empty) {
700		isl_map_free(map);
701		return 0;
702	}
703
704	data->res = isl_union_map_add_map(data->res, map);
705
706	return 0;
707}
708
709static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
710	__isl_take isl_union_map *umap2,
711	__isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*))
712{
713	struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
714
715	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
716	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
717
718	if (!umap1 || !umap2)
719		goto error;
720
721	data.umap2 = umap2;
722	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
723				       umap1->table.n);
724	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
725				   &match_bin_entry, &data) < 0)
726		goto error;
727
728	isl_union_map_free(umap1);
729	isl_union_map_free(umap2);
730	return data.res;
731error:
732	isl_union_map_free(umap1);
733	isl_union_map_free(umap2);
734	isl_union_map_free(data.res);
735	return NULL;
736}
737
738__isl_give isl_union_map *isl_union_map_intersect(
739	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
740{
741	return match_bin_op(umap1, umap2, &isl_map_intersect);
742}
743
744/* Compute the intersection of the two union_sets.
745 * As a special case, if exactly one of the two union_sets
746 * is a parameter domain, then intersect the parameter domain
747 * of the other one with this set.
748 */
749__isl_give isl_union_set *isl_union_set_intersect(
750	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
751{
752	int p1, p2;
753
754	p1 = isl_union_set_is_params(uset1);
755	p2 = isl_union_set_is_params(uset2);
756	if (p1 < 0 || p2 < 0)
757		goto error;
758	if (!p1 && p2)
759		return union_map_intersect_params(uset1, uset2);
760	if (p1 && !p2)
761		return union_map_intersect_params(uset2, uset1);
762	return isl_union_map_intersect(uset1, uset2);
763error:
764	isl_union_set_free(uset1);
765	isl_union_set_free(uset2);
766	return NULL;
767}
768
769static int gist_params_entry(void **entry, void *user)
770{
771	struct isl_union_map_gen_bin_set_data *data = user;
772	isl_map *map = *entry;
773	int empty;
774
775	map = isl_map_copy(map);
776	map = isl_map_gist_params(map, isl_set_copy(data->set));
777
778	empty = isl_map_is_empty(map);
779	if (empty < 0) {
780		isl_map_free(map);
781		return -1;
782	}
783
784	data->res = isl_union_map_add_map(data->res, map);
785
786	return 0;
787}
788
789__isl_give isl_union_map *isl_union_map_gist_params(
790	__isl_take isl_union_map *umap, __isl_take isl_set *set)
791{
792	return gen_bin_set_op(umap, set, &gist_params_entry);
793}
794
795__isl_give isl_union_set *isl_union_set_gist_params(
796	__isl_take isl_union_set *uset, __isl_take isl_set *set)
797{
798	return isl_union_map_gist_params(uset, set);
799}
800
801__isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap,
802	__isl_take isl_union_map *context)
803{
804	return match_bin_op(umap, context, &isl_map_gist);
805}
806
807__isl_give isl_union_set *isl_union_set_gist(__isl_take isl_union_set *uset,
808	__isl_take isl_union_set *context)
809{
810	if (isl_union_set_is_params(context))
811		return union_map_gist_params(uset, context);
812	return isl_union_map_gist(uset, context);
813}
814
815static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1,
816	__isl_take isl_map *set2)
817{
818	return isl_set_lex_le_set((isl_set *)set1, (isl_set *)set2);
819}
820
821static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1,
822	__isl_take isl_map *set2)
823{
824	return isl_set_lex_lt_set((isl_set *)set1, (isl_set *)set2);
825}
826
827__isl_give isl_union_map *isl_union_set_lex_lt_union_set(
828	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
829{
830	return match_bin_op(uset1, uset2, &lex_lt_set);
831}
832
833__isl_give isl_union_map *isl_union_set_lex_le_union_set(
834	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
835{
836	return match_bin_op(uset1, uset2, &lex_le_set);
837}
838
839__isl_give isl_union_map *isl_union_set_lex_gt_union_set(
840	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
841{
842	return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1));
843}
844
845__isl_give isl_union_map *isl_union_set_lex_ge_union_set(
846	__isl_take isl_union_set *uset1, __isl_take isl_union_set *uset2)
847{
848	return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1));
849}
850
851__isl_give isl_union_map *isl_union_map_lex_gt_union_map(
852	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
853{
854	return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1));
855}
856
857__isl_give isl_union_map *isl_union_map_lex_ge_union_map(
858	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
859{
860	return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1));
861}
862
863static int intersect_domain_entry(void **entry, void *user)
864{
865	struct isl_union_map_gen_bin_data *data = user;
866	uint32_t hash;
867	struct isl_hash_table_entry *entry2;
868	isl_space *dim;
869	isl_map *map = *entry;
870	int empty;
871
872	dim = isl_map_get_space(map);
873	dim = isl_space_domain(dim);
874	hash = isl_space_get_hash(dim);
875	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
876				     hash, &has_dim, dim, 0);
877	isl_space_free(dim);
878	if (!entry2)
879		return 0;
880
881	map = isl_map_copy(map);
882	map = isl_map_intersect_domain(map, isl_set_copy(entry2->data));
883
884	empty = isl_map_is_empty(map);
885	if (empty < 0) {
886		isl_map_free(map);
887		return -1;
888	}
889	if (empty) {
890		isl_map_free(map);
891		return 0;
892	}
893
894	data->res = isl_union_map_add_map(data->res, map);
895
896	return 0;
897}
898
899/* Intersect the domain of "umap" with "uset".
900 * If "uset" is a parameters domain, then intersect the parameter
901 * domain of "umap" with this set.
902 */
903__isl_give isl_union_map *isl_union_map_intersect_domain(
904	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
905{
906	if (isl_union_set_is_params(uset))
907		return union_map_intersect_params(umap, uset);
908	return gen_bin_op(umap, uset, &intersect_domain_entry);
909}
910
911/* Remove the elements of data->umap2 from the domain of *entry
912 * and add the result to data->res.
913 */
914static int subtract_domain_entry(void **entry, void *user)
915{
916	struct isl_union_map_gen_bin_data *data = user;
917	uint32_t hash;
918	struct isl_hash_table_entry *entry2;
919	isl_space *dim;
920	isl_map *map = *entry;
921	int empty;
922
923	dim = isl_map_get_space(map);
924	dim = isl_space_domain(dim);
925	hash = isl_space_get_hash(dim);
926	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
927				     hash, &has_dim, dim, 0);
928	isl_space_free(dim);
929
930	map = isl_map_copy(map);
931
932	if (!entry2) {
933		data->res = isl_union_map_add_map(data->res, map);
934		return 0;
935	}
936
937	map = isl_map_subtract_domain(map, isl_set_copy(entry2->data));
938
939	empty = isl_map_is_empty(map);
940	if (empty < 0) {
941		isl_map_free(map);
942		return -1;
943	}
944	if (empty) {
945		isl_map_free(map);
946		return 0;
947	}
948
949	data->res = isl_union_map_add_map(data->res, map);
950
951	return 0;
952}
953
954/* Remove the elements of "uset" from the domain of "umap".
955 */
956__isl_give isl_union_map *isl_union_map_subtract_domain(
957	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
958{
959	return gen_bin_op(umap, dom, &subtract_domain_entry);
960}
961
962/* Remove the elements of data->umap2 from the range of *entry
963 * and add the result to data->res.
964 */
965static int subtract_range_entry(void **entry, void *user)
966{
967	struct isl_union_map_gen_bin_data *data = user;
968	uint32_t hash;
969	struct isl_hash_table_entry *entry2;
970	isl_space *space;
971	isl_map *map = *entry;
972	int empty;
973
974	space = isl_map_get_space(map);
975	space = isl_space_range(space);
976	hash = isl_space_get_hash(space);
977	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
978				     hash, &has_dim, space, 0);
979	isl_space_free(space);
980
981	map = isl_map_copy(map);
982
983	if (!entry2) {
984		data->res = isl_union_map_add_map(data->res, map);
985		return 0;
986	}
987
988	map = isl_map_subtract_range(map, isl_set_copy(entry2->data));
989
990	empty = isl_map_is_empty(map);
991	if (empty < 0) {
992		isl_map_free(map);
993		return -1;
994	}
995	if (empty) {
996		isl_map_free(map);
997		return 0;
998	}
999
1000	data->res = isl_union_map_add_map(data->res, map);
1001
1002	return 0;
1003}
1004
1005/* Remove the elements of "uset" from the range of "umap".
1006 */
1007__isl_give isl_union_map *isl_union_map_subtract_range(
1008	__isl_take isl_union_map *umap, __isl_take isl_union_set *dom)
1009{
1010	return gen_bin_op(umap, dom, &subtract_range_entry);
1011}
1012
1013static int gist_domain_entry(void **entry, void *user)
1014{
1015	struct isl_union_map_gen_bin_data *data = user;
1016	uint32_t hash;
1017	struct isl_hash_table_entry *entry2;
1018	isl_space *dim;
1019	isl_map *map = *entry;
1020	int empty;
1021
1022	dim = isl_map_get_space(map);
1023	dim = isl_space_domain(dim);
1024	hash = isl_space_get_hash(dim);
1025	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1026				     hash, &has_dim, dim, 0);
1027	isl_space_free(dim);
1028	if (!entry2)
1029		return 0;
1030
1031	map = isl_map_copy(map);
1032	map = isl_map_gist_domain(map, isl_set_copy(entry2->data));
1033
1034	empty = isl_map_is_empty(map);
1035	if (empty < 0) {
1036		isl_map_free(map);
1037		return -1;
1038	}
1039
1040	data->res = isl_union_map_add_map(data->res, map);
1041
1042	return 0;
1043}
1044
1045/* Compute the gist of "umap" with respect to the domain "uset".
1046 * If "uset" is a parameters domain, then compute the gist
1047 * with respect to this parameter domain.
1048 */
1049__isl_give isl_union_map *isl_union_map_gist_domain(
1050	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1051{
1052	if (isl_union_set_is_params(uset))
1053		return union_map_gist_params(umap, uset);
1054	return gen_bin_op(umap, uset, &gist_domain_entry);
1055}
1056
1057static int gist_range_entry(void **entry, void *user)
1058{
1059	struct isl_union_map_gen_bin_data *data = user;
1060	uint32_t hash;
1061	struct isl_hash_table_entry *entry2;
1062	isl_space *space;
1063	isl_map *map = *entry;
1064	int empty;
1065
1066	space = isl_map_get_space(map);
1067	space = isl_space_range(space);
1068	hash = isl_space_get_hash(space);
1069	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1070				     hash, &has_dim, space, 0);
1071	isl_space_free(space);
1072	if (!entry2)
1073		return 0;
1074
1075	map = isl_map_copy(map);
1076	map = isl_map_gist_range(map, isl_set_copy(entry2->data));
1077
1078	empty = isl_map_is_empty(map);
1079	if (empty < 0) {
1080		isl_map_free(map);
1081		return -1;
1082	}
1083
1084	data->res = isl_union_map_add_map(data->res, map);
1085
1086	return 0;
1087}
1088
1089/* Compute the gist of "umap" with respect to the range "uset".
1090 */
1091__isl_give isl_union_map *isl_union_map_gist_range(
1092	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1093{
1094	return gen_bin_op(umap, uset, &gist_range_entry);
1095}
1096
1097static int intersect_range_entry(void **entry, void *user)
1098{
1099	struct isl_union_map_gen_bin_data *data = user;
1100	uint32_t hash;
1101	struct isl_hash_table_entry *entry2;
1102	isl_space *dim;
1103	isl_map *map = *entry;
1104	int empty;
1105
1106	dim = isl_map_get_space(map);
1107	dim = isl_space_range(dim);
1108	hash = isl_space_get_hash(dim);
1109	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
1110				     hash, &has_dim, dim, 0);
1111	isl_space_free(dim);
1112	if (!entry2)
1113		return 0;
1114
1115	map = isl_map_copy(map);
1116	map = isl_map_intersect_range(map, isl_set_copy(entry2->data));
1117
1118	empty = isl_map_is_empty(map);
1119	if (empty < 0) {
1120		isl_map_free(map);
1121		return -1;
1122	}
1123	if (empty) {
1124		isl_map_free(map);
1125		return 0;
1126	}
1127
1128	data->res = isl_union_map_add_map(data->res, map);
1129
1130	return 0;
1131}
1132
1133__isl_give isl_union_map *isl_union_map_intersect_range(
1134	__isl_take isl_union_map *umap, __isl_take isl_union_set *uset)
1135{
1136	return gen_bin_op(umap, uset, &intersect_range_entry);
1137}
1138
1139struct isl_union_map_bin_data {
1140	isl_union_map *umap2;
1141	isl_union_map *res;
1142	isl_map *map;
1143	int (*fn)(void **entry, void *user);
1144};
1145
1146static int apply_range_entry(void **entry, void *user)
1147{
1148	struct isl_union_map_bin_data *data = user;
1149	isl_map *map2 = *entry;
1150	int empty;
1151
1152	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1153				 map2->dim, isl_dim_in))
1154		return 0;
1155
1156	map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2));
1157
1158	empty = isl_map_is_empty(map2);
1159	if (empty < 0) {
1160		isl_map_free(map2);
1161		return -1;
1162	}
1163	if (empty) {
1164		isl_map_free(map2);
1165		return 0;
1166	}
1167
1168	data->res = isl_union_map_add_map(data->res, map2);
1169
1170	return 0;
1171}
1172
1173static int bin_entry(void **entry, void *user)
1174{
1175	struct isl_union_map_bin_data *data = user;
1176	isl_map *map = *entry;
1177
1178	data->map = map;
1179	if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table,
1180				   data->fn, data) < 0)
1181		return -1;
1182
1183	return 0;
1184}
1185
1186static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
1187	__isl_take isl_union_map *umap2, int (*fn)(void **entry, void *user))
1188{
1189	struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
1190
1191	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
1192	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
1193
1194	if (!umap1 || !umap2)
1195		goto error;
1196
1197	data.umap2 = umap2;
1198	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
1199				       umap1->table.n);
1200	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
1201				   &bin_entry, &data) < 0)
1202		goto error;
1203
1204	isl_union_map_free(umap1);
1205	isl_union_map_free(umap2);
1206	return data.res;
1207error:
1208	isl_union_map_free(umap1);
1209	isl_union_map_free(umap2);
1210	isl_union_map_free(data.res);
1211	return NULL;
1212}
1213
1214__isl_give isl_union_map *isl_union_map_apply_range(
1215	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1216{
1217	return bin_op(umap1, umap2, &apply_range_entry);
1218}
1219
1220__isl_give isl_union_map *isl_union_map_apply_domain(
1221	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1222{
1223	umap1 = isl_union_map_reverse(umap1);
1224	umap1 = isl_union_map_apply_range(umap1, umap2);
1225	return isl_union_map_reverse(umap1);
1226}
1227
1228__isl_give isl_union_set *isl_union_set_apply(
1229	__isl_take isl_union_set *uset, __isl_take isl_union_map *umap)
1230{
1231	return isl_union_map_apply_range(uset, umap);
1232}
1233
1234static int map_lex_lt_entry(void **entry, void *user)
1235{
1236	struct isl_union_map_bin_data *data = user;
1237	isl_map *map2 = *entry;
1238
1239	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1240				 map2->dim, isl_dim_out))
1241		return 0;
1242
1243	map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2));
1244
1245	data->res = isl_union_map_add_map(data->res, map2);
1246
1247	return 0;
1248}
1249
1250__isl_give isl_union_map *isl_union_map_lex_lt_union_map(
1251	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1252{
1253	return bin_op(umap1, umap2, &map_lex_lt_entry);
1254}
1255
1256static int map_lex_le_entry(void **entry, void *user)
1257{
1258	struct isl_union_map_bin_data *data = user;
1259	isl_map *map2 = *entry;
1260
1261	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1262				 map2->dim, isl_dim_out))
1263		return 0;
1264
1265	map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2));
1266
1267	data->res = isl_union_map_add_map(data->res, map2);
1268
1269	return 0;
1270}
1271
1272__isl_give isl_union_map *isl_union_map_lex_le_union_map(
1273	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1274{
1275	return bin_op(umap1, umap2, &map_lex_le_entry);
1276}
1277
1278static int product_entry(void **entry, void *user)
1279{
1280	struct isl_union_map_bin_data *data = user;
1281	isl_map *map2 = *entry;
1282
1283	map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2));
1284
1285	data->res = isl_union_map_add_map(data->res, map2);
1286
1287	return 0;
1288}
1289
1290__isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1,
1291	__isl_take isl_union_map *umap2)
1292{
1293	return bin_op(umap1, umap2, &product_entry);
1294}
1295
1296static int set_product_entry(void **entry, void *user)
1297{
1298	struct isl_union_map_bin_data *data = user;
1299	isl_set *set2 = *entry;
1300
1301	set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2));
1302
1303	data->res = isl_union_set_add_set(data->res, set2);
1304
1305	return 0;
1306}
1307
1308__isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
1309	__isl_take isl_union_set *uset2)
1310{
1311	return bin_op(uset1, uset2, &set_product_entry);
1312}
1313
1314static int domain_product_entry(void **entry, void *user)
1315{
1316	struct isl_union_map_bin_data *data = user;
1317	isl_map *map2 = *entry;
1318
1319	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
1320				 map2->dim, isl_dim_out))
1321		return 0;
1322
1323	map2 = isl_map_domain_product(isl_map_copy(data->map),
1324				     isl_map_copy(map2));
1325
1326	data->res = isl_union_map_add_map(data->res, map2);
1327
1328	return 0;
1329}
1330
1331/* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D)
1332 */
1333__isl_give isl_union_map *isl_union_map_domain_product(
1334	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1335{
1336	return bin_op(umap1, umap2, &domain_product_entry);
1337}
1338
1339static int range_product_entry(void **entry, void *user)
1340{
1341	struct isl_union_map_bin_data *data = user;
1342	isl_map *map2 = *entry;
1343
1344	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1345				 map2->dim, isl_dim_in))
1346		return 0;
1347
1348	map2 = isl_map_range_product(isl_map_copy(data->map),
1349				     isl_map_copy(map2));
1350
1351	data->res = isl_union_map_add_map(data->res, map2);
1352
1353	return 0;
1354}
1355
1356__isl_give isl_union_map *isl_union_map_range_product(
1357	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1358{
1359	return bin_op(umap1, umap2, &range_product_entry);
1360}
1361
1362static int flat_range_product_entry(void **entry, void *user)
1363{
1364	struct isl_union_map_bin_data *data = user;
1365	isl_map *map2 = *entry;
1366
1367	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
1368				 map2->dim, isl_dim_in))
1369		return 0;
1370
1371	map2 = isl_map_flat_range_product(isl_map_copy(data->map),
1372					  isl_map_copy(map2));
1373
1374	data->res = isl_union_map_add_map(data->res, map2);
1375
1376	return 0;
1377}
1378
1379__isl_give isl_union_map *isl_union_map_flat_range_product(
1380	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
1381{
1382	return bin_op(umap1, umap2, &flat_range_product_entry);
1383}
1384
1385static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
1386	int (*fn)(void **, void *))
1387{
1388	isl_union_set *res;
1389
1390	if (!umap)
1391		return NULL;
1392
1393	res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
1394	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
1395		goto error;
1396
1397	isl_union_map_free(umap);
1398	return res;
1399error:
1400	isl_union_map_free(umap);
1401	isl_union_set_free(res);
1402	return NULL;
1403}
1404
1405static int from_range_entry(void **entry, void *user)
1406{
1407	isl_map *set = *entry;
1408	isl_union_set **res = user;
1409
1410	*res = isl_union_map_add_map(*res,
1411					isl_map_from_range(isl_set_copy(set)));
1412
1413	return 0;
1414}
1415
1416__isl_give isl_union_map *isl_union_map_from_range(
1417	__isl_take isl_union_set *uset)
1418{
1419	return cond_un_op(uset, &from_range_entry);
1420}
1421
1422__isl_give isl_union_map *isl_union_map_from_domain(
1423	__isl_take isl_union_set *uset)
1424{
1425	return isl_union_map_reverse(isl_union_map_from_range(uset));
1426}
1427
1428__isl_give isl_union_map *isl_union_map_from_domain_and_range(
1429	__isl_take isl_union_set *domain, __isl_take isl_union_set *range)
1430{
1431	return isl_union_map_apply_range(isl_union_map_from_domain(domain),
1432				         isl_union_map_from_range(range));
1433}
1434
1435static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap,
1436	int (*fn)(void **, void *))
1437{
1438	umap = isl_union_map_cow(umap);
1439	if (!umap)
1440		return NULL;
1441
1442	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, NULL) < 0)
1443		goto error;
1444
1445	return umap;
1446error:
1447	isl_union_map_free(umap);
1448	return NULL;
1449}
1450
1451static int affine_entry(void **entry, void *user)
1452{
1453	isl_map **map = (isl_map **)entry;
1454
1455	*map = isl_map_from_basic_map(isl_map_affine_hull(*map));
1456
1457	return *map ? 0 : -1;
1458}
1459
1460__isl_give isl_union_map *isl_union_map_affine_hull(
1461	__isl_take isl_union_map *umap)
1462{
1463	return un_op(umap, &affine_entry);
1464}
1465
1466__isl_give isl_union_set *isl_union_set_affine_hull(
1467	__isl_take isl_union_set *uset)
1468{
1469	return isl_union_map_affine_hull(uset);
1470}
1471
1472static int polyhedral_entry(void **entry, void *user)
1473{
1474	isl_map **map = (isl_map **)entry;
1475
1476	*map = isl_map_from_basic_map(isl_map_polyhedral_hull(*map));
1477
1478	return *map ? 0 : -1;
1479}
1480
1481__isl_give isl_union_map *isl_union_map_polyhedral_hull(
1482	__isl_take isl_union_map *umap)
1483{
1484	return un_op(umap, &polyhedral_entry);
1485}
1486
1487__isl_give isl_union_set *isl_union_set_polyhedral_hull(
1488	__isl_take isl_union_set *uset)
1489{
1490	return isl_union_map_polyhedral_hull(uset);
1491}
1492
1493static int simple_entry(void **entry, void *user)
1494{
1495	isl_map **map = (isl_map **)entry;
1496
1497	*map = isl_map_from_basic_map(isl_map_simple_hull(*map));
1498
1499	return *map ? 0 : -1;
1500}
1501
1502__isl_give isl_union_map *isl_union_map_simple_hull(
1503	__isl_take isl_union_map *umap)
1504{
1505	return un_op(umap, &simple_entry);
1506}
1507
1508__isl_give isl_union_set *isl_union_set_simple_hull(
1509	__isl_take isl_union_set *uset)
1510{
1511	return isl_union_map_simple_hull(uset);
1512}
1513
1514static int inplace_entry(void **entry, void *user)
1515{
1516	__isl_give isl_map *(*fn)(__isl_take isl_map *);
1517	isl_map **map = (isl_map **)entry;
1518	isl_map *copy;
1519
1520	fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
1521	copy = fn(isl_map_copy(*map));
1522	if (!copy)
1523		return -1;
1524
1525	isl_map_free(*map);
1526	*map = copy;
1527
1528	return 0;
1529}
1530
1531static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
1532	__isl_give isl_map *(*fn)(__isl_take isl_map *))
1533{
1534	if (!umap)
1535		return NULL;
1536
1537	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
1538				    &inplace_entry, &fn) < 0)
1539		goto error;
1540
1541	return umap;
1542error:
1543	isl_union_map_free(umap);
1544	return NULL;
1545}
1546
1547__isl_give isl_union_map *isl_union_map_coalesce(
1548	__isl_take isl_union_map *umap)
1549{
1550	return inplace(umap, &isl_map_coalesce);
1551}
1552
1553__isl_give isl_union_set *isl_union_set_coalesce(
1554	__isl_take isl_union_set *uset)
1555{
1556	return isl_union_map_coalesce(uset);
1557}
1558
1559__isl_give isl_union_map *isl_union_map_detect_equalities(
1560	__isl_take isl_union_map *umap)
1561{
1562	return inplace(umap, &isl_map_detect_equalities);
1563}
1564
1565__isl_give isl_union_set *isl_union_set_detect_equalities(
1566	__isl_take isl_union_set *uset)
1567{
1568	return isl_union_map_detect_equalities(uset);
1569}
1570
1571__isl_give isl_union_map *isl_union_map_compute_divs(
1572	__isl_take isl_union_map *umap)
1573{
1574	return inplace(umap, &isl_map_compute_divs);
1575}
1576
1577__isl_give isl_union_set *isl_union_set_compute_divs(
1578	__isl_take isl_union_set *uset)
1579{
1580	return isl_union_map_compute_divs(uset);
1581}
1582
1583static int lexmin_entry(void **entry, void *user)
1584{
1585	isl_map **map = (isl_map **)entry;
1586
1587	*map = isl_map_lexmin(*map);
1588
1589	return *map ? 0 : -1;
1590}
1591
1592__isl_give isl_union_map *isl_union_map_lexmin(
1593	__isl_take isl_union_map *umap)
1594{
1595	return un_op(umap, &lexmin_entry);
1596}
1597
1598__isl_give isl_union_set *isl_union_set_lexmin(
1599	__isl_take isl_union_set *uset)
1600{
1601	return isl_union_map_lexmin(uset);
1602}
1603
1604static int lexmax_entry(void **entry, void *user)
1605{
1606	isl_map **map = (isl_map **)entry;
1607
1608	*map = isl_map_lexmax(*map);
1609
1610	return *map ? 0 : -1;
1611}
1612
1613__isl_give isl_union_map *isl_union_map_lexmax(
1614	__isl_take isl_union_map *umap)
1615{
1616	return un_op(umap, &lexmax_entry);
1617}
1618
1619__isl_give isl_union_set *isl_union_set_lexmax(
1620	__isl_take isl_union_set *uset)
1621{
1622	return isl_union_map_lexmax(uset);
1623}
1624
1625static int universe_entry(void **entry, void *user)
1626{
1627	isl_map *map = *entry;
1628	isl_union_map **res = user;
1629
1630	map = isl_map_universe(isl_map_get_space(map));
1631	*res = isl_union_map_add_map(*res, map);
1632
1633	return 0;
1634}
1635
1636__isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
1637{
1638	return cond_un_op(umap, &universe_entry);
1639}
1640
1641__isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
1642{
1643	return isl_union_map_universe(uset);
1644}
1645
1646static int reverse_entry(void **entry, void *user)
1647{
1648	isl_map *map = *entry;
1649	isl_union_map **res = user;
1650
1651	*res = isl_union_map_add_map(*res, isl_map_reverse(isl_map_copy(map)));
1652
1653	return 0;
1654}
1655
1656__isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap)
1657{
1658	return cond_un_op(umap, &reverse_entry);
1659}
1660
1661static int params_entry(void **entry, void *user)
1662{
1663	isl_map *map = *entry;
1664	isl_union_set **res = user;
1665
1666	*res = isl_union_set_add_set(*res, isl_map_params(isl_map_copy(map)));
1667
1668	return 0;
1669}
1670
1671/* Compute the parameter domain of the given union map.
1672 */
1673__isl_give isl_set *isl_union_map_params(__isl_take isl_union_map *umap)
1674{
1675	int empty;
1676
1677	empty = isl_union_map_is_empty(umap);
1678	if (empty < 0)
1679		return isl_union_map_free(umap);
1680	if (empty) {
1681		isl_space *space;
1682		space = isl_union_map_get_space(umap);
1683		isl_union_map_free(umap);
1684		return isl_set_empty(space);
1685	}
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
1696static 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
1711static 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
1726static 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
1743static 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
1760static 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
1778static 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
1798static 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
1813static 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
1831static 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
1846struct isl_union_map_is_subset_data {
1847	isl_union_map *umap2;
1848	int is_subset;
1849};
1850
1851static 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
1878int 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;
1901error:
1902	isl_union_map_free(umap1);
1903	isl_union_map_free(umap2);
1904	return -1;
1905}
1906
1907int 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
1913int 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
1927int 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
1933int 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
1949int 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
1955static 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;
1986error:
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
1996struct isl_forall_data {
1997	int res;
1998	int (*fn)(__isl_keep isl_map *map);
1999};
2000
2001static 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
2016static 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
2031struct isl_forall_user_data {
2032	int res;
2033	int (*fn)(__isl_keep isl_map *map, void *user);
2034	void *user;
2035};
2036
2037static 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 */
2054static 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
2069int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
2070{
2071	return union_map_forall(umap, &isl_map_is_empty);
2072}
2073
2074int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
2075{
2076	return isl_union_map_is_empty(uset);
2077}
2078
2079static 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 */
2108int 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
2132int 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 */
2150struct isl_fixed_map {
2151	isl_int v;
2152	isl_map *map;
2153};
2154
2155static 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
2169static 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 */
2182static 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 */
2196struct isl_fixed_dim_data {
2197	struct isl_fixed_map *v;
2198	int n;
2199	int pos;
2200};
2201
2202static 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
2211static 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 */
2224static 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;
2263error:
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 */
2275static 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;
2323error:
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 */
2332static 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 */
2348int 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
2370int 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
2381static 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
2399static 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
2420static 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
2441static 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
2456static 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;
2487error:
2488	isl_union_set_free(uset);
2489	isl_union_set_free(res);
2490	return NULL;
2491}
2492
2493static 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;
2531error:
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 */
2543struct 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 */
2553static 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;
2612error:
2613	isl_union_map_free(umap);
2614	isl_multi_aff_free(ma);
2615	return NULL;
2616}
2617