From 6a8c0e3b08155458da91d760376e2a531e919c1a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 14 Oct 2013 16:54:32 +0200 Subject: [PATCH] add isl_union_{set,map}_is_disjoint Signed-off-by: Sven Verdoolaege --- doc/user.pod | 13 +++++++++ include/isl/union_map.h | 2 ++ include/isl/union_set.h | 2 ++ isl_union_map.c | 74 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 91 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 6276e33f..375689ab 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -3555,6 +3555,7 @@ return true if the objects are not the same. =item * Disjointness + #include int isl_basic_set_is_disjoint( __isl_keep isl_basic_set *bset1, __isl_keep isl_basic_set *bset2); @@ -3562,12 +3563,24 @@ return true if the objects are not the same. __isl_keep isl_set *set2); int isl_set_is_disjoint(__isl_keep isl_set *set1, __isl_keep isl_set *set2); + + #include int isl_basic_map_is_disjoint( __isl_keep isl_basic_map *bmap1, __isl_keep isl_basic_map *bmap2); int isl_map_is_disjoint(__isl_keep isl_map *map1, __isl_keep isl_map *map2); + #include + int isl_union_set_is_disjoint( + __isl_keep isl_union_set *uset1, + __isl_keep isl_union_set *uset2); + + #include + int isl_union_map_is_disjoint( + __isl_keep isl_union_map *umap1, + __isl_keep isl_union_map *umap2); + =item * Subset int isl_basic_set_is_subset( diff --git a/include/isl/union_map.h b/include/isl/union_map.h index 2d4d94cd..cd495d1c 100644 --- a/include/isl/union_map.h +++ b/include/isl/union_map.h @@ -186,6 +186,8 @@ int isl_union_map_is_subset(__isl_keep isl_union_map *umap1, __isl_export int isl_union_map_is_equal(__isl_keep isl_union_map *umap1, __isl_keep isl_union_map *umap2); +int isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1, + __isl_keep isl_union_map *umap2); __isl_export int isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1, __isl_keep isl_union_map *umap2); diff --git a/include/isl/union_set.h b/include/isl/union_set.h index 616acb80..2dec6b55 100644 --- a/include/isl/union_set.h +++ b/include/isl/union_set.h @@ -94,6 +94,8 @@ int isl_union_set_is_subset(__isl_keep isl_union_set *uset1, __isl_export int isl_union_set_is_equal(__isl_keep isl_union_set *uset1, __isl_keep isl_union_set *uset2); +int isl_union_set_is_disjoint(__isl_keep isl_union_set *uset1, + __isl_keep isl_union_set *uset2); __isl_export int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1, __isl_keep isl_union_set *uset2); diff --git a/isl_union_map.c b/isl_union_map.c index be39088c..7e570e67 100644 --- a/isl_union_map.c +++ b/isl_union_map.c @@ -2174,6 +2174,80 @@ int isl_union_set_is_strict_subset(__isl_keep isl_union_set *uset1, return isl_union_map_is_strict_subset(uset1, uset2); } +/* Internal data structure for isl_union_map_is_disjoint. + * umap2 is the union map with which we are comparing. + * is_disjoint is initialized to 1 and is set to 0 as soon + * as the union maps turn out not to be disjoint. + */ +struct isl_union_map_is_disjoint_data { + isl_union_map *umap2; + int is_disjoint; +}; + +/* Check if "map" is disjoint from data->umap2 and abort + * the search if it is not. + */ +static int is_disjoint_entry(void **entry, void *user) +{ + struct isl_union_map_is_disjoint_data *data = user; + uint32_t hash; + struct isl_hash_table_entry *entry2; + isl_map *map = *entry; + + 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) + return 0; + + data->is_disjoint = isl_map_is_disjoint(map, entry2->data); + if (data->is_disjoint < 0 || !data->is_disjoint) + return -1; + + return 0; +} + +/* Are "umap1" and "umap2" disjoint? + */ +int isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1, + __isl_keep isl_union_map *umap2) +{ + struct isl_union_map_is_disjoint_data data = { NULL, 1 }; + + umap1 = isl_union_map_copy(umap1); + umap2 = isl_union_map_copy(umap2); + 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; + if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, + &is_disjoint_entry, &data) < 0 && + data.is_disjoint) + goto error; + + isl_union_map_free(umap1); + isl_union_map_free(umap2); + + return data.is_disjoint; +error: + isl_union_map_free(umap1); + isl_union_map_free(umap2); + return -1; +} + +/* Are "uset1" and "uset2" disjoint? + */ +int isl_union_set_is_disjoint(__isl_keep isl_union_set *uset1, + __isl_keep isl_union_set *uset2) +{ + return isl_union_map_is_disjoint(uset1, uset2); +} + static int sample_entry(void **entry, void *user) { isl_basic_map **sample = (isl_basic_map **)user; -- 2.11.4.GIT