From a6ef0dadaa8f89892ac507217ee0c6e49d153cdb Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Mon, 5 Sep 2011 12:26:23 +0200 Subject: [PATCH] add isl_pw_*_plain_is_equal Signed-off-by: Sven Verdoolaege --- include/isl/polynomial.h | 7 ++++ isl_pw_templ.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+) diff --git a/include/isl/polynomial.h b/include/isl/polynomial.h index 1c88b7b..1c5dcdb 100644 --- a/include/isl/polynomial.h +++ b/include/isl/polynomial.h @@ -134,6 +134,9 @@ void isl_qpolynomial_dump(__isl_keep isl_qpolynomial *qp); isl_ctx *isl_pw_qpolynomial_get_ctx(__isl_keep isl_pw_qpolynomial *pwqp); +int isl_pw_qpolynomial_plain_is_equal(__isl_keep isl_pw_qpolynomial *pwqp1, + __isl_keep isl_pw_qpolynomial *pwqp2); + __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_zero(__isl_take isl_space *dim); __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_alloc(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp); @@ -301,6 +304,10 @@ void isl_qpolynomial_fold_dump(__isl_keep isl_qpolynomial_fold *fold); isl_ctx *isl_pw_qpolynomial_fold_get_ctx(__isl_keep isl_pw_qpolynomial_fold *pwf); +int isl_pw_qpolynomial_fold_plain_is_equal( + __isl_keep isl_pw_qpolynomial_fold *pwf1, + __isl_keep isl_pw_qpolynomial_fold *pwf2); + __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial( enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp); diff --git a/isl_pw_templ.c b/isl_pw_templ.c index ae9328d..7f478a2 100644 --- a/isl_pw_templ.c +++ b/isl_pw_templ.c @@ -1304,3 +1304,96 @@ __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v) { return FN(PW,mul_isl_int)(pw, v); } + +static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2) +{ + const isl_set *set1 = *(const isl_set **)p1; + const isl_set *set2 = *(const isl_set **)p2; + + return isl_set_plain_cmp(set1, set2); +} + +/* We normalize in place, but if anything goes wrong we need + * to return NULL, so we need to make sure we don't change the + * meaning of any possible other copies of map. + */ +__isl_give PW *FN(PW,normalize)(__isl_take PW *pw) +{ + int i, j; + isl_set *set; + + if (!pw) + return NULL; + for (i = 0; i < pw->n; ++i) { + set = isl_set_normalize(isl_set_copy(pw->p[i].set)); + if (!set) + return FN(PW,free)(pw); + isl_set_free(pw->p[i].set); + pw->p[i].set = set; + } + qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp)); + for (i = pw->n - 1; i >= 1; --i) { + if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set)) + continue; + if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD)) + continue; + set = isl_set_union(isl_set_copy(pw->p[i - 1].set), + isl_set_copy(pw->p[i].set)); + if (!set) + return FN(PW,free)(pw); + isl_set_free(pw->p[i].set); + FN(EL,free)(pw->p[i].FIELD); + isl_set_free(pw->p[i - 1].set); + pw->p[i - 1].set = set; + for (j = i + 1; j < pw->n; ++j) + pw->p[j - 1] = pw->p[j]; + pw->n--; + } + + return pw; +} + +/* Is pw1 obviously equal to pw2? + * That is, do they have obviously identical cells and obviously identical + * elements on each cell? + */ +int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2) +{ + int i; + int equal; + + if (!pw1 || !pw2) + return -1; + + if (pw1 == pw2) + return 1; + if (!isl_space_is_equal(pw1->dim, pw2->dim)) + return 0; + + pw1 = FN(PW,copy)(pw1); + pw2 = FN(PW,copy)(pw2); + pw1 = FN(PW,normalize)(pw1); + pw2 = FN(PW,normalize)(pw2); + if (!pw1 || !pw2) + goto error; + + equal = pw1->n == pw2->n; + for (i = 0; equal && i < pw1->n; ++i) { + equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set); + if (equal < 0) + goto error; + if (!equal) + break; + equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD); + if (equal < 0) + goto error; + } + + FN(PW,free)(pw1); + FN(PW,free)(pw2); + return equal; +error: + FN(PW,free)(pw1); + FN(PW,free)(pw2); + return -1; +} -- 2.7.4