X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_union_map.c;h=f12fd97056d5dbb3027c2b127ffac5cbb1cb5ac3;hb=3280c051ef3dc4b05fbe855340547ace629071c6;hp=550666c302bbcd520e02ed31baca4e283858e5e4;hpb=1e2c039132d11a12fc55b04784a7a67fee765c75;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_union_map.c b/isl_union_map.c
index 550666c..f12fd97 100644
--- a/isl_union_map.c
+++ b/isl_union_map.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2010      INRIA Saclay
+ * Copyright 2010-2011 INRIA Saclay
  *
  * Use of this software is governed by the GNU LGPLv2.1 license
  *
@@ -8,16 +8,17 @@
  * 91893 Orsay, France 
  */
 
+#define ISL_DIM_H
+#include <isl_map_private.h>
 #include <isl/ctx.h>
 #include <isl/hash.h>
 #include <isl/map.h>
 #include <isl/set.h>
-#include <isl_dim_private.h>
-#include <isl_map_private.h>
+#include <isl_space_private.h>
 #include <isl_union_map_private.h>
 #include <isl/union_set.h>
 
-static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
+static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_space *dim,
 	int size)
 {
 	isl_union_map *umap;
@@ -36,17 +37,17 @@ static __isl_give isl_union_map *isl_union_map_alloc(__isl_take isl_dim *dim,
 
 	return umap;
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	isl_union_map_free(umap);
 	return NULL;
 }
 
-__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_dim *dim)
+__isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *dim)
 {
 	return isl_union_map_alloc(dim, 16);
 }
 
-__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_dim *dim)
+__isl_give isl_union_set *isl_union_set_empty(__isl_take isl_space *dim)
 {
 	return isl_union_map_empty(dim);
 }
@@ -61,16 +62,16 @@ isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_set *uset)
 	return uset ? uset->dim->ctx : NULL;
 }
 
-__isl_give isl_dim *isl_union_map_get_dim(__isl_keep isl_union_map *umap)
+__isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap)
 {
 	if (!umap)
 		return NULL;
-	return isl_dim_copy(umap->dim);
+	return isl_space_copy(umap->dim);
 }
 
-__isl_give isl_dim *isl_union_set_get_dim(__isl_keep isl_union_set *uset)
+__isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_set *uset)
 {
-	return isl_union_map_get_dim(uset);
+	return isl_union_map_get_space(uset);
 }
 
 static int free_umap_entry(void **entry, void *user)
@@ -96,7 +97,7 @@ __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap)
 	if (!umap)
 		return NULL;
 
-	dup = isl_union_map_empty(isl_dim_copy(umap->dim));
+	dup = isl_union_map_empty(isl_space_copy(umap->dim));
 	if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0)
 		goto error;
 	return dup;
@@ -127,8 +128,8 @@ static int align_entry(void **entry, void *user)
 	isl_reordering *exp;
 	struct isl_union_align *data = user;
 
-	exp = isl_reordering_extend_dim(isl_reordering_copy(data->exp),
-				    isl_map_get_dim(map));
+	exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
+				    isl_map_get_space(map));
 
 	data->res = isl_union_map_add_map(data->res,
 					isl_map_realign(isl_map_copy(map), exp));
@@ -142,23 +143,24 @@ static int align_entry(void **entry, void *user)
  * umap that do not appear in model.
  */
 __isl_give isl_union_map *isl_union_map_align_params(
-	__isl_take isl_union_map *umap, __isl_take isl_dim *model)
+	__isl_take isl_union_map *umap, __isl_take isl_space *model)
 {
 	struct isl_union_align data = { NULL, NULL };
 
 	if (!umap || !model)
 		goto error;
 
-	if (isl_dim_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
-		isl_dim_free(model);
+	if (isl_space_match(umap->dim, isl_dim_param, model, isl_dim_param)) {
+		isl_space_free(model);
 		return umap;
 	}
 
+	model = isl_space_params(model);
 	data.exp = isl_parameter_alignment_reordering(umap->dim, model);
 	if (!data.exp)
 		goto error;
 
-	data.res = isl_union_map_alloc(isl_dim_copy(data.exp->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(data.exp->dim),
 					umap->table.n);
 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 					&align_entry, &data) < 0)
@@ -166,18 +168,18 @@ __isl_give isl_union_map *isl_union_map_align_params(
 
 	isl_reordering_free(data.exp);
 	isl_union_map_free(umap);
-	isl_dim_free(model);
+	isl_space_free(model);
 	return data.res;
 error:
 	isl_reordering_free(data.exp);
 	isl_union_map_free(umap);
 	isl_union_map_free(data.res);
-	isl_dim_free(model);
+	isl_space_free(model);
 	return NULL;
 }
 
 __isl_give isl_union_set *isl_union_set_align_params(
-	__isl_take isl_union_set *uset, __isl_take isl_dim *model)
+	__isl_take isl_union_set *uset, __isl_take isl_space *model)
 {
 	return isl_union_map_align_params(uset, model);
 }
@@ -185,8 +187,8 @@ __isl_give isl_union_set *isl_union_set_align_params(
 __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1,
 	__isl_take isl_union_map *umap2)
 {
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	umap1 = isl_union_map_cow(umap1);
 
@@ -225,32 +227,33 @@ __isl_give isl_union_set *isl_union_set_copy(__isl_keep isl_union_set *uset)
 	return isl_union_map_copy(uset);
 }
 
-void isl_union_map_free(__isl_take isl_union_map *umap)
+void *isl_union_map_free(__isl_take isl_union_map *umap)
 {
 	if (!umap)
-		return;
+		return NULL;
 
 	if (--umap->ref > 0)
-		return;
+		return NULL;
 
 	isl_hash_table_foreach(umap->dim->ctx, &umap->table,
 			       &free_umap_entry, NULL);
 	isl_hash_table_clear(&umap->table);
-	isl_dim_free(umap->dim);
+	isl_space_free(umap->dim);
 	free(umap);
+	return NULL;
 }
 
-void isl_union_set_free(__isl_take isl_union_set *uset)
+void *isl_union_set_free(__isl_take isl_union_set *uset)
 {
-	isl_union_map_free(uset);
+	return isl_union_map_free(uset);
 }
 
 static int has_dim(const void *entry, const void *val)
 {
 	isl_map *map = (isl_map *)entry;
-	isl_dim *dim = (isl_dim *)val;
+	isl_space *dim = (isl_space *)val;
 
-	return isl_dim_equal(map->dim, dim);
+	return isl_space_is_equal(map->dim, dim);
 }
 
 __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
@@ -259,20 +262,25 @@ __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap,
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
 
-	if (isl_map_fast_is_empty(map)) {
+	if (!map || !umap)
+		goto error;
+
+	if (isl_map_plain_is_empty(map)) {
 		isl_map_free(map);
 		return umap;
 	}
 
+	if (!isl_space_match(map->dim, isl_dim_param, umap->dim, isl_dim_param)) {
+		umap = isl_union_map_align_params(umap, isl_map_get_space(map));
+		map = isl_map_align_params(map, isl_union_map_get_space(umap));
+	}
+
 	umap = isl_union_map_cow(umap);
 
 	if (!map || !umap)
 		goto error;
 
-	isl_assert(map->ctx, isl_dim_match(map->dim, isl_dim_param, umap->dim,
-					   isl_dim_param), goto error);
-
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 				    &has_dim, map->dim, 1);
 	if (!entry)
@@ -302,15 +310,14 @@ __isl_give isl_union_set *isl_union_set_add_set(__isl_take isl_union_set *uset,
 
 __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map)
 {
-	isl_dim *dim;
+	isl_space *dim;
 	isl_union_map *umap;
 
 	if (!map)
 		return NULL;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_drop(dim, isl_dim_in, 0, isl_dim_size(dim, isl_dim_in));
-	dim = isl_dim_drop(dim, isl_dim_out, 0, isl_dim_size(dim, isl_dim_out));
+	dim = isl_map_get_space(map);
+	dim = isl_space_params(dim);
 	umap = isl_union_map_empty(dim);
 	umap = isl_union_map_add_map(umap, map);
 
@@ -359,8 +366,43 @@ int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
 				      &call_on_copy, &data);
 }
 
+static int copy_map(void **entry, void *user)
+{
+	isl_map *map = *entry;
+	isl_map **map_p = user;
+
+	*map_p = isl_map_copy(map);
+
+	return -1;
+}
+
+__isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap)
+{
+	isl_ctx *ctx;
+	isl_map *map = NULL;
+
+	if (!umap)
+		return NULL;
+	ctx = isl_union_map_get_ctx(umap);
+	if (umap->table.n != 1)
+		isl_die(ctx, isl_error_invalid,
+			"union map needs to contain elements in exactly "
+			"one space", return isl_union_map_free(umap));
+
+	isl_hash_table_foreach(ctx, &umap->table, &copy_map, &map);
+
+	isl_union_map_free(umap);
+
+	return map;
+}
+
+__isl_give isl_set *isl_set_from_union_set(__isl_take isl_union_set *uset)
+{
+	return isl_map_from_union_map(uset);
+}
+
 __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
-	__isl_take isl_dim *dim)
+	__isl_take isl_space *dim)
 {
 	uint32_t hash;
 	struct isl_hash_table_entry *entry;
@@ -368,24 +410,47 @@ __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap,
 	if (!umap || !dim)
 		goto error;
 
-	hash = isl_dim_get_hash(dim);
+	hash = isl_space_get_hash(dim);
 	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
 				    &has_dim, dim, 0);
 	if (!entry)
 		return isl_map_empty(dim);
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return isl_map_copy(entry->data);
 error:
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	return NULL;
 }
 
 __isl_give isl_set *isl_union_set_extract_set(__isl_keep isl_union_set *uset,
-	__isl_take isl_dim *dim)
+	__isl_take isl_space *dim)
 {
 	return (isl_set *)isl_union_map_extract_map(uset, dim);
 }
 
+/* Check if umap contains a map in the given space.
+ */
+__isl_give int isl_union_map_contains(__isl_keep isl_union_map *umap,
+	__isl_keep isl_space *dim)
+{
+	uint32_t hash;
+	struct isl_hash_table_entry *entry;
+
+	if (!umap || !dim)
+		return -1;
+
+	hash = isl_space_get_hash(dim);
+	entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash,
+				    &has_dim, dim, 0);
+	return !!entry;
+}
+
+__isl_give int isl_union_set_contains(__isl_keep isl_union_set *uset,
+	__isl_keep isl_space *dim)
+{
+	return isl_union_map_contains(uset, dim);
+}
+
 int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
 	int (*fn)(__isl_take isl_set *set, void *user), void *user)
 {
@@ -428,7 +493,7 @@ static int subtract_entry(void **entry, void *user)
 	struct isl_hash_table_entry *entry2;
 	isl_map *map = *entry;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, map->dim, 0);
 	map = isl_map_copy(map);
@@ -456,14 +521,14 @@ static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_gen_bin_data data = { NULL, NULL };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   fn, &data) < 0)
@@ -505,7 +570,7 @@ static int match_bin_entry(void **entry, void *user)
 	isl_map *map = *entry;
 	int empty;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, map->dim, 0);
 	if (!entry2)
@@ -535,14 +600,14 @@ static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_match_bin_data data = { NULL, NULL, fn };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   &match_bin_entry, &data) < 0)
@@ -635,16 +700,16 @@ static int intersect_domain_entry(void **entry, void *user)
 	struct isl_union_map_gen_bin_data *data = user;
 	uint32_t hash;
 	struct isl_hash_table_entry *entry2;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_map *map = *entry;
 	int empty;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_domain(dim);
-	hash = isl_dim_get_hash(dim);
+	dim = isl_map_get_space(map);
+	dim = isl_space_domain(dim);
+	hash = isl_space_get_hash(dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, dim, 0);
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	if (!entry2)
 		return 0;
 
@@ -677,16 +742,16 @@ static int intersect_range_entry(void **entry, void *user)
 	struct isl_union_map_gen_bin_data *data = user;
 	uint32_t hash;
 	struct isl_hash_table_entry *entry2;
-	isl_dim *dim;
+	isl_space *dim;
 	isl_map *map = *entry;
 	int empty;
 
-	dim = isl_map_get_dim(map);
-	dim = isl_dim_range(dim);
-	hash = isl_dim_get_hash(dim);
+	dim = isl_map_get_space(map);
+	dim = isl_space_range(dim);
+	hash = isl_space_get_hash(dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, dim, 0);
-	isl_dim_free(dim);
+	isl_space_free(dim);
 	if (!entry2)
 		return 0;
 
@@ -727,7 +792,7 @@ static int apply_range_entry(void **entry, void *user)
 	isl_map *map2 = *entry;
 	int empty;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_in))
 		return 0;
 
@@ -766,14 +831,14 @@ static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1,
 {
 	struct isl_union_map_bin_data data = { NULL, NULL, NULL, fn };
 
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
 
 	data.umap2 = umap2;
-	data.res = isl_union_map_alloc(isl_dim_copy(umap1->dim),
+	data.res = isl_union_map_alloc(isl_space_copy(umap1->dim),
 				       umap1->table.n);
 	if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table,
 				   &bin_entry, &data) < 0)
@@ -814,7 +879,7 @@ static int map_lex_lt_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_out))
 		return 0;
 
@@ -836,7 +901,7 @@ static int map_lex_le_entry(void **entry, void *user)
 	struct isl_union_map_bin_data *data = user;
 	isl_map *map2 = *entry;
 
-	if (!isl_dim_tuple_match(data->map->dim, isl_dim_out,
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_out,
 				 map2->dim, isl_dim_out))
 		return 0;
 
@@ -877,10 +942,87 @@ __isl_give isl_union_set *isl_union_set_product(__isl_take isl_union_set *uset1,
 	return isl_union_map_product(uset1, uset2);
 }
 
+static int range_product_entry(void **entry, void *user)
+{
+	struct isl_union_map_bin_data *data = user;
+	isl_map *map2 = *entry;
+
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
+				 map2->dim, isl_dim_in))
+		return 0;
+
+	map2 = isl_map_range_product(isl_map_copy(data->map),
+				     isl_map_copy(map2));
+
+	data->res = isl_union_map_add_map(data->res, map2);
+
+	return 0;
+}
+
+__isl_give isl_union_map *isl_union_map_range_product(
+	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
+{
+	return bin_op(umap1, umap2, &range_product_entry);
+}
+
+static int flat_range_product_entry(void **entry, void *user)
+{
+	struct isl_union_map_bin_data *data = user;
+	isl_map *map2 = *entry;
+
+	if (!isl_space_tuple_match(data->map->dim, isl_dim_in,
+				 map2->dim, isl_dim_in))
+		return 0;
+
+	map2 = isl_map_flat_range_product(isl_map_copy(data->map),
+					  isl_map_copy(map2));
+
+	data->res = isl_union_map_add_map(data->res, map2);
+
+	return 0;
+}
+
+__isl_give isl_union_map *isl_union_map_flat_range_product(
+	__isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2)
+{
+	return bin_op(umap1, umap2, &flat_range_product_entry);
+}
+
+static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
+	int (*fn)(void **, void *))
+{
+	isl_union_set *res;
+
+	if (!umap)
+		return NULL;
+
+	res = isl_union_map_alloc(isl_space_copy(umap->dim), umap->table.n);
+	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
+		goto error;
+
+	isl_union_map_free(umap);
+	return res;
+error:
+	isl_union_map_free(umap);
+	isl_union_set_free(res);
+	return NULL;
+}
+
+static int from_range_entry(void **entry, void *user)
+{
+	isl_map *set = *entry;
+	isl_union_set **res = user;
+
+	*res = isl_union_map_add_map(*res,
+					isl_map_from_range(isl_set_copy(set)));
+
+	return 0;
+}
+
 __isl_give isl_union_map *isl_union_map_from_range(
 	__isl_take isl_union_set *uset)
 {
-	return uset;
+	return cond_un_op(uset, &from_range_entry);
 }
 
 __isl_give isl_union_map *isl_union_map_from_domain(
@@ -954,12 +1096,34 @@ __isl_give isl_union_set *isl_union_set_polyhedral_hull(
 	return isl_union_map_polyhedral_hull(uset);
 }
 
+static int simple_entry(void **entry, void *user)
+{
+	isl_map **map = (isl_map **)entry;
+
+	*map = isl_map_from_basic_map(isl_map_simple_hull(*map));
+
+	return *map ? 0 : -1;
+}
+
+__isl_give isl_union_map *isl_union_map_simple_hull(
+	__isl_take isl_union_map *umap)
+{
+	return un_op(umap, &simple_entry);
+}
+
+__isl_give isl_union_set *isl_union_set_simple_hull(
+	__isl_take isl_union_set *uset)
+{
+	return isl_union_map_simple_hull(uset);
+}
+
 static int inplace_entry(void **entry, void *user)
 {
-	__isl_give isl_map *(*fn)(__isl_take isl_map *) = user;
+	__isl_give isl_map *(*fn)(__isl_take isl_map *);
 	isl_map **map = (isl_map **)entry;
 	isl_map *copy;
 
+	fn = *(__isl_give isl_map *(**)(__isl_take isl_map *)) user;
 	copy = fn(isl_map_copy(*map));
 	if (!copy)
 		return -1;
@@ -977,7 +1141,7 @@ static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap,
 		return NULL;
 
 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
-				    &inplace_entry, fn) < 0)
+				    &inplace_entry, &fn) < 0)
 		goto error;
 
 	return umap;
@@ -998,6 +1162,18 @@ __isl_give isl_union_set *isl_union_set_coalesce(
 	return isl_union_map_coalesce(uset);
 }
 
+__isl_give isl_union_map *isl_union_map_detect_equalities(
+	__isl_take isl_union_map *umap)
+{
+	return inplace(umap, &isl_map_detect_equalities);
+}
+
+__isl_give isl_union_set *isl_union_set_detect_equalities(
+	__isl_take isl_union_set *uset)
+{
+	return isl_union_map_detect_equalities(uset);
+}
+
 __isl_give isl_union_map *isl_union_map_compute_divs(
 	__isl_take isl_union_map *umap)
 {
@@ -1052,24 +1228,25 @@ __isl_give isl_union_set *isl_union_set_lexmax(
 	return isl_union_map_lexmax(uset);
 }
 
-static __isl_give isl_union_set *cond_un_op(__isl_take isl_union_map *umap,
-	int (*fn)(void **, void *))
+static int universe_entry(void **entry, void *user)
 {
-	isl_union_set *res;
+	isl_map *map = *entry;
+	isl_union_map **res = user;
 
-	if (!umap)
-		return NULL;
+	map = isl_map_universe(isl_map_get_space(map));
+	*res = isl_union_map_add_map(*res, map);
 
-	res = isl_union_map_alloc(isl_dim_copy(umap->dim), umap->table.n);
-	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, fn, &res) < 0)
-		goto error;
+	return 0;
+}
 
-	isl_union_map_free(umap);
-	return res;
-error:
-	isl_union_map_free(umap);
-	isl_union_set_free(res);
-	return NULL;
+__isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap)
+{
+	return cond_un_op(umap, &universe_entry);
+}
+
+__isl_give isl_union_set *isl_union_set_universe(__isl_take isl_union_set *uset)
+{
+	return isl_union_map_universe(uset);
 }
 
 static int reverse_entry(void **entry, void *user)
@@ -1156,7 +1333,7 @@ static int deltas_entry(void **entry, void *user)
 	isl_map *map = *entry;
 	isl_union_set **res = user;
 
-	if (!isl_dim_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
 		return 0;
 
 	*res = isl_union_set_add_set(*res, isl_map_deltas(isl_map_copy(map)));
@@ -1169,6 +1346,26 @@ __isl_give isl_union_set *isl_union_map_deltas(__isl_take isl_union_map *umap)
 	return cond_un_op(umap, &deltas_entry);
 }
 
+static int deltas_map_entry(void **entry, void *user)
+{
+	isl_map *map = *entry;
+	isl_union_map **res = user;
+
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+		return 0;
+
+	*res = isl_union_map_add_map(*res,
+				     isl_map_deltas_map(isl_map_copy(map)));
+
+	return 0;
+}
+
+__isl_give isl_union_map *isl_union_map_deltas_map(
+	__isl_take isl_union_map *umap)
+{
+	return cond_un_op(umap, &deltas_map_entry);
+}
+
 static int identity_entry(void **entry, void *user)
 {
 	isl_set *set = *entry;
@@ -1229,7 +1426,7 @@ static int is_subset_entry(void **entry, void *user)
 	struct isl_hash_table_entry *entry2;
 	isl_map *map = *entry;
 
-	hash = isl_dim_get_hash(map->dim);
+	hash = isl_space_get_hash(map->dim);
 	entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table,
 				     hash, &has_dim, map->dim, 0);
 	if (!entry2) {
@@ -1251,8 +1448,8 @@ int isl_union_map_is_subset(__isl_keep isl_union_map *umap1,
 
 	umap1 = isl_union_map_copy(umap1);
 	umap2 = isl_union_map_copy(umap2);
-	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_dim(umap2));
-	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_dim(umap1));
+	umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2));
+	umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1));
 
 	if (!umap1 || !umap2)
 		goto error;
@@ -1329,7 +1526,7 @@ static int sample_entry(void **entry, void *user)
 	*sample = isl_map_sample(isl_map_copy(map));
 	if (!*sample)
 		return -1;
-	if (!isl_basic_map_fast_is_empty(*sample))
+	if (!isl_basic_map_plain_is_empty(*sample))
 		return -1;
 	return 0;
 }
@@ -1346,6 +1543,9 @@ __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap)
 	    !sample)
 		goto error;
 
+	if (!sample)
+		sample = isl_basic_map_empty(isl_union_map_get_space(umap));
+
 	isl_union_map_free(umap);
 
 	return sample;
@@ -1359,34 +1559,501 @@ __isl_give isl_basic_set *isl_union_set_sample(__isl_take isl_union_set *uset)
 	return (isl_basic_set *)isl_union_map_sample(uset);
 }
 
-static int empty_entry(void **entry, void *user)
+struct isl_forall_data {
+	int res;
+	int (*fn)(__isl_keep isl_map *map);
+};
+
+static int forall_entry(void **entry, void *user)
 {
-	int *empty = user;
+	struct isl_forall_data *data = user;
 	isl_map *map = *entry;
 
-	if (isl_map_is_empty(map))
-		return 0;
+	data->res = data->fn(map);
+	if (data->res < 0)
+		return -1;
 
-	*empty = 0;
+	if (!data->res)
+		return -1;
 
-	return -1;
+	return 0;
+}
+
+static int union_map_forall(__isl_keep isl_union_map *umap,
+	int (*fn)(__isl_keep isl_map *map))
+{
+	struct isl_forall_data data = { 1, fn };
+
+	if (!umap)
+		return -1;
+
+	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
+				   &forall_entry, &data) < 0 && data.res)
+		return -1;
+
+	return data.res;
 }
 
-__isl_give int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
+struct isl_forall_user_data {
+	int res;
+	int (*fn)(__isl_keep isl_map *map, void *user);
+	void *user;
+};
+
+static int forall_user_entry(void **entry, void *user)
 {
-	int empty = 1;
+	struct isl_forall_user_data *data = user;
+	isl_map *map = *entry;
+
+	data->res = data->fn(map, data->user);
+	if (data->res < 0)
+		return -1;
+
+	if (!data->res)
+		return -1;
+
+	return 0;
+}
+
+/* Check if fn(map, user) returns true for all maps "map" in umap.
+ */
+static int union_map_forall_user(__isl_keep isl_union_map *umap,
+	int (*fn)(__isl_keep isl_map *map, void *user), void *user)
+{
+	struct isl_forall_user_data data = { 1, fn, user };
 
 	if (!umap)
 		return -1;
 
 	if (isl_hash_table_foreach(umap->dim->ctx, &umap->table,
-				   &empty_entry, &empty) < 0 && empty)
+				   &forall_user_entry, &data) < 0 && data.res)
 		return -1;
 
-	return empty;
+	return data.res;
+}
+
+int isl_union_map_is_empty(__isl_keep isl_union_map *umap)
+{
+	return union_map_forall(umap, &isl_map_is_empty);
 }
 
 int isl_union_set_is_empty(__isl_keep isl_union_set *uset)
 {
 	return isl_union_map_is_empty(uset);
 }
+
+static int is_subset_of_identity(__isl_keep isl_map *map)
+{
+	int is_subset;
+	isl_space *dim;
+	isl_map *id;
+
+	if (!map)
+		return -1;
+
+	if (!isl_space_tuple_match(map->dim, isl_dim_in, map->dim, isl_dim_out))
+		return 0;
+
+	dim = isl_map_get_space(map);
+	id = isl_map_identity(dim);
+
+	is_subset = isl_map_is_subset(map, id);
+
+	isl_map_free(id);
+
+	return is_subset;
+}
+
+/* Check if the given map is single-valued.
+ * We simply compute
+ *
+ *	M \circ M^-1
+ *
+ * and check if the result is a subset of the identity mapping.
+ */
+int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap)
+{
+	isl_union_map *test;
+	int sv;
+
+	if (isl_union_map_n_map(umap) == 1) {
+		isl_map *map;
+		umap = isl_union_map_copy(umap);
+		map = isl_map_from_union_map(umap);
+		sv = isl_map_is_single_valued(map);
+		isl_map_free(map);
+		return sv;
+	}
+
+	test = isl_union_map_reverse(isl_union_map_copy(umap));
+	test = isl_union_map_apply_range(test, isl_union_map_copy(umap));
+
+	sv = union_map_forall(test, &is_subset_of_identity);
+
+	isl_union_map_free(test);
+
+	return sv;
+}
+
+int isl_union_map_is_injective(__isl_keep isl_union_map *umap)
+{
+	int in;
+
+	umap = isl_union_map_copy(umap);
+	umap = isl_union_map_reverse(umap);
+	in = isl_union_map_is_single_valued(umap);
+	isl_union_map_free(umap);
+
+	return in;
+}
+
+/* Represents a map that has a fixed value (v) for one of its
+ * range dimensions.
+ * The map in this structure is not reference counted, so it
+ * is only valid while the isl_union_map from which it was
+ * obtained is still alive.
+ */
+struct isl_fixed_map {
+	isl_int v;
+	isl_map *map;
+};
+
+static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx,
+	int n)
+{
+	int i;
+	struct isl_fixed_map *v;
+
+	v = isl_calloc_array(ctx, struct isl_fixed_map, n);
+	if (!v)
+		return NULL;
+	for (i = 0; i < n; ++i)
+		isl_int_init(v[i].v);
+	return v;
+}
+
+static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n)
+{
+	int i;
+
+	if (!v)
+		return;
+	for (i = 0; i < n; ++i)
+		isl_int_clear(v[i].v);
+	free(v);
+}
+
+/* Compare the "v" field of two isl_fixed_map structs.
+ */
+static int qsort_fixed_map_cmp(const void *p1, const void *p2)
+{
+	const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1;
+	const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2;
+
+	return isl_int_cmp(e1->v, e2->v);
+}
+
+/* Internal data structure used while checking whether all maps
+ * in a union_map have a fixed value for a given output dimension.
+ * v is the list of maps, with the fixed value for the dimension
+ * n is the number of maps considered so far
+ * pos is the output dimension under investigation
+ */
+struct isl_fixed_dim_data {
+	struct isl_fixed_map *v;
+	int n;
+	int pos;
+};
+
+static int fixed_at_pos(__isl_keep isl_map *map, void *user)
+{
+	struct isl_fixed_dim_data *data = user;
+
+	data->v[data->n].map = map;
+	return isl_map_plain_is_fixed(map, isl_dim_out, data->pos,
+				      &data->v[data->n++].v);
+}
+
+static int plain_injective_on_range(__isl_take isl_union_map *umap,
+	int first, int n_range);
+
+/* Given a list of the maps, with their fixed values at output dimension "pos",
+ * check whether the ranges of the maps form an obvious partition.
+ *
+ * We first sort the maps according to their fixed values.
+ * If all maps have a different value, then we know the ranges form
+ * a partition.
+ * Otherwise, we collect the maps with the same fixed value and
+ * check whether each such collection is obviously injective
+ * based on later dimensions.
+ */
+static int separates(struct isl_fixed_map *v, int n,
+	__isl_take isl_space *dim, int pos, int n_range)
+{
+	int i;
+
+	if (!v)
+		goto error;
+
+	qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp);
+
+	for (i = 0; i + 1 < n; ++i) {
+		int j, k;
+		isl_union_map *part;
+		int injective;
+
+		for (j = i + 1; j < n; ++j)
+			if (isl_int_ne(v[i].v, v[j].v))
+				break;
+
+		if (j == i + 1)
+			continue;
+
+		part = isl_union_map_alloc(isl_space_copy(dim), j - i);
+		for (k = i; k < j; ++k)
+			part = isl_union_map_add_map(part,
+						     isl_map_copy(v[k].map));
+
+		injective = plain_injective_on_range(part, pos + 1, n_range);
+		if (injective < 0)
+			goto error;
+		if (!injective)
+			break;
+
+		i = j - 1;
+	}
+
+	isl_space_free(dim);
+	free_isl_fixed_map_array(v, n);
+	return i + 1 >= n;
+error:
+	isl_space_free(dim);
+	free_isl_fixed_map_array(v, n);
+	return -1;
+}
+
+/* Check whether the maps in umap have obviously distinct ranges.
+ * In particular, check for an output dimension in the range
+ * [first,n_range) for which all maps have a fixed value
+ * and then check if these values, possibly along with fixed values
+ * at later dimensions, entail distinct ranges.
+ */
+static int plain_injective_on_range(__isl_take isl_union_map *umap,
+	int first, int n_range)
+{
+	isl_ctx *ctx;
+	int n;
+	struct isl_fixed_dim_data data = { NULL };
+
+	ctx = isl_union_map_get_ctx(umap);
+
+	if (!umap)
+		goto error;
+
+	n = isl_union_map_n_map(umap);
+	if (n <= 1) {
+		isl_union_map_free(umap);
+		return 1;
+	}
+
+	if (first >= n_range) {
+		isl_union_map_free(umap);
+		return 0;
+	}
+
+	data.v = alloc_isl_fixed_map_array(ctx, n);
+	if (!data.v)
+		goto error;
+
+	for (data.pos = first; data.pos < n_range; ++data.pos) {
+		int fixed;
+		int injective;
+		isl_space *dim;
+
+		data.n = 0;
+		fixed = union_map_forall_user(umap, &fixed_at_pos, &data);
+		if (fixed < 0)
+			goto error;
+		if (!fixed)
+			continue;
+		dim = isl_union_map_get_space(umap);
+		injective = separates(data.v, n, dim, data.pos, n_range);
+		isl_union_map_free(umap);
+		return injective;
+	}
+
+	free_isl_fixed_map_array(data.v, n);
+	isl_union_map_free(umap);
+
+	return 0;
+error:
+	free_isl_fixed_map_array(data.v, n);
+	isl_union_map_free(umap);
+	return -1;
+}
+
+/* Check whether the maps in umap that map to subsets of "ran"
+ * have obviously distinct ranges.
+ */
+static int plain_injective_on_range_wrap(__isl_keep isl_set *ran, void *user)
+{
+	isl_union_map *umap = user;
+
+	umap = isl_union_map_copy(umap);
+	umap = isl_union_map_intersect_range(umap,
+			isl_union_set_from_set(isl_set_copy(ran)));
+	return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set));
+}
+
+/* Check if the given union_map is obviously injective.
+ *
+ * In particular, we first check if all individual maps are obviously
+ * injective and then check if all the ranges of these maps are
+ * obviously disjoint.
+ */
+int isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap)
+{
+	int in;
+	isl_union_map *univ;
+	isl_union_set *ran;
+
+	in = union_map_forall(umap, &isl_map_plain_is_injective);
+	if (in < 0)
+		return -1;
+	if (!in)
+		return 0;
+
+	univ = isl_union_map_universe(isl_union_map_copy(umap));
+	ran = isl_union_map_range(univ);
+
+	in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap);
+
+	isl_union_set_free(ran);
+
+	return in;
+}
+
+int isl_union_map_is_bijective(__isl_keep isl_union_map *umap)
+{
+	int sv;
+
+	sv = isl_union_map_is_single_valued(umap);
+	if (sv < 0 || !sv)
+		return sv;
+
+	return isl_union_map_is_injective(umap);
+}
+
+static int zip_entry(void **entry, void *user)
+{
+	isl_map *map = *entry;
+	isl_union_map **res = user;
+
+	if (!isl_map_can_zip(map))
+		return 0;
+
+	*res = isl_union_map_add_map(*res, isl_map_zip(isl_map_copy(map)));
+
+	return 0;
+}
+
+__isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap)
+{
+	return cond_un_op(umap, &zip_entry);
+}
+
+static int lift_entry(void **entry, void *user)
+{
+	isl_set *set = *entry;
+	isl_union_set **res = user;
+
+	*res = isl_union_set_add_set(*res, isl_set_lift(isl_set_copy(set)));
+
+	return 0;
+}
+
+__isl_give isl_union_set *isl_union_set_lift(__isl_take isl_union_set *uset)
+{
+	return cond_un_op(uset, &lift_entry);
+}
+
+static int coefficients_entry(void **entry, void *user)
+{
+	isl_set *set = *entry;
+	isl_union_set **res = user;
+
+	set = isl_set_copy(set);
+	set = isl_set_from_basic_set(isl_set_coefficients(set));
+	*res = isl_union_set_add_set(*res, set);
+
+	return 0;
+}
+
+__isl_give isl_union_set *isl_union_set_coefficients(
+	__isl_take isl_union_set *uset)
+{
+	isl_ctx *ctx;
+	isl_space *dim;
+	isl_union_set *res;
+
+	if (!uset)
+		return NULL;
+
+	ctx = isl_union_set_get_ctx(uset);
+	dim = isl_space_set_alloc(ctx, 0, 0);
+	res = isl_union_map_alloc(dim, uset->table.n);
+	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
+				   &coefficients_entry, &res) < 0)
+		goto error;
+
+	isl_union_set_free(uset);
+	return res;
+error:
+	isl_union_set_free(uset);
+	isl_union_set_free(res);
+	return NULL;
+}
+
+static int solutions_entry(void **entry, void *user)
+{
+	isl_set *set = *entry;
+	isl_union_set **res = user;
+
+	set = isl_set_copy(set);
+	set = isl_set_from_basic_set(isl_set_solutions(set));
+	if (!*res)
+		*res = isl_union_set_from_set(set);
+	else
+		*res = isl_union_set_add_set(*res, set);
+
+	if (!*res)
+		return -1;
+
+	return 0;
+}
+
+__isl_give isl_union_set *isl_union_set_solutions(
+	__isl_take isl_union_set *uset)
+{
+	isl_union_set *res = NULL;
+
+	if (!uset)
+		return NULL;
+
+	if (uset->table.n == 0) {
+		res = isl_union_set_empty(isl_union_set_get_space(uset));
+		isl_union_set_free(uset);
+		return res;
+	}
+
+	if (isl_hash_table_foreach(uset->dim->ctx, &uset->table,
+				   &solutions_entry, &res) < 0)
+		goto error;
+
+	isl_union_set_free(uset);
+	return res;
+error:
+	isl_union_set_free(uset);
+	isl_union_set_free(res);
+	return NULL;
+}