From fe7284963999cecd86bc5a9b18019af8caecf3d5 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 6 Mar 2010 16:57:09 +0100 Subject: [PATCH] add isl_pw_qpolynomial_foreach_piece --- doc/user.pod | 44 ++++++++ include/isl_polynomial.h | 21 ++++ isl_polynomial.c | 257 +++++++++++++++++++++++++++++++++++++++++++++++ isl_polynomial_private.h | 12 +++ 4 files changed, 334 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 08641f9..b8fe52f 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -1184,6 +1184,50 @@ functions. void isl_pw_qpolynomial_free( __isl_take isl_pw_qpolynomial *pwqp); +=head3 Inspecting (Piecewise) Quasipolynomials + +To iterate over the cells in a piecewise quasipolynomial, +use the following function + + int isl_pw_qpolynomial_foreach_piece( + __isl_keep isl_pw_qpolynomial *pwqp, + int (*fn)(__isl_take isl_set *set, + __isl_take isl_qpolynomial *qp, + void *user), void *user); + +As usual, the function C should return C<0> on success +and C<-1> on failure. + +To iterate over all terms in a quasipolynomial, +use + + int isl_qpolynomial_foreach_term( + __isl_keep isl_qpolynomial *qp, + int (*fn)(__isl_take isl_term *term, + void *user), void *user); + +The terms themselves can be inspected and freed using +these functions + + unsigned isl_term_dim(__isl_keep isl_term *term, + enum isl_dim_type type); + void isl_term_get_num(__isl_keep isl_term *term, + isl_int *n); + void isl_term_get_den(__isl_keep isl_term *term, + isl_int *d); + int isl_term_get_exp(__isl_keep isl_term *term, + enum isl_dim_type type, unsigned pos); + __isl_give isl_div *isl_term_get_div( + __isl_keep isl_term *term, unsigned pos); + void isl_term_free(__isl_take isl_term *term); + +Each term is a product of parameters, set variables and +integer divisions. The function C +returns the exponent of a given dimensions in the given term. +The Cs in the arguments of C +and C need to have been initialized +using C before calling these functions. + =head3 Properties of (Piecewise) Quasipolynomials To check whether a quasipolynomial is actually a constant, diff --git a/include/isl_polynomial.h b/include/isl_polynomial.h index e2b158c..886f71f 100644 --- a/include/isl_polynomial.h +++ b/include/isl_polynomial.h @@ -34,6 +34,23 @@ __isl_give isl_qpolynomial *isl_qpolynomial_add(__isl_take isl_qpolynomial *qp1, __isl_give isl_qpolynomial *isl_qpolynomial_mul(__isl_take isl_qpolynomial *qp1, __isl_take isl_qpolynomial *qp2); +struct isl_term; +typedef struct isl_term isl_term; + +isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term); + +void isl_term_free(__isl_take isl_term *term); + +unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type); +void isl_term_get_num(__isl_keep isl_term *term, isl_int *n); +void isl_term_get_den(__isl_keep isl_term *term, isl_int *d); +int isl_term_get_exp(__isl_keep isl_term *term, + enum isl_dim_type type, unsigned pos); +__isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos); + +int isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp, + int (*fn)(__isl_take isl_term *term, void *user), void *user); + void isl_qpolynomial_print(__isl_keep isl_qpolynomial *qp, FILE *out, unsigned output_format); @@ -73,6 +90,10 @@ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_move( __isl_give isl_qpolynomial *isl_pw_qpolynomial_eval( __isl_take isl_pw_qpolynomial *pwqp, __isl_take isl_point *pnt); +int isl_pw_qpolynomial_foreach_piece(__isl_keep isl_pw_qpolynomial *pwqp, + int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, + void *user), void *user); + void isl_pw_qpolynomial_print(__isl_keep isl_pw_qpolynomial *pwqp, FILE *out, unsigned output_format); diff --git a/isl_polynomial.c b/isl_polynomial.c index 785ce5f..446a96a 100644 --- a/isl_polynomial.c +++ b/isl_polynomial.c @@ -1835,3 +1835,260 @@ __isl_give isl_dim *isl_pw_qpolynomial_get_dim( return isl_dim_copy(pwqp->dim); } + +__isl_give isl_term *isl_term_alloc(__isl_take isl_dim *dim, + __isl_take isl_mat *div) +{ + isl_term *term; + int n; + + if (!dim || !div) + goto error; + + n = isl_dim_total(dim) + div->n_row; + + term = isl_calloc(dim->ctx, struct isl_term, + sizeof(struct isl_term) + (n - 1) * sizeof(int)); + if (!term) + goto error; + + term->ref = 1; + term->dim = dim; + term->div = div; + isl_int_init(term->n); + isl_int_init(term->d); + + return term; +error: + isl_dim_free(dim); + isl_mat_free(div); + return NULL; +} + +__isl_give isl_term *isl_term_copy(__isl_keep isl_term *term) +{ + if (!term) + return NULL; + + term->ref++; + return term; +} + +__isl_give isl_term *isl_term_dup(__isl_keep isl_term *term) +{ + int i; + isl_term *dup; + unsigned total; + + if (term) + return NULL; + + total = isl_dim_total(term->dim) + term->div->n_row; + + dup = isl_term_alloc(isl_dim_copy(term->dim), isl_mat_copy(term->div)); + if (!dup) + return NULL; + + isl_int_set(dup->n, term->n); + isl_int_set(dup->d, term->d); + + for (i = 0; i < total; ++i) + dup->pow[i] = term->pow[i]; + + return dup; +} + +__isl_give isl_term *isl_term_cow(__isl_take isl_term *term) +{ + if (!term) + return NULL; + + if (term->ref == 1) + return term; + term->ref--; + return isl_term_dup(term); +} + +void isl_term_free(__isl_take isl_term *term) +{ + if (!term) + return; + + if (--term->ref > 0) + return; + + isl_dim_free(term->dim); + isl_mat_free(term->div); + isl_int_clear(term->n); + isl_int_clear(term->d); + free(term); +} + +unsigned isl_term_dim(__isl_keep isl_term *term, enum isl_dim_type type) +{ + if (!term) + return 0; + + switch (type) { + case isl_dim_param: + case isl_dim_in: + case isl_dim_out: return isl_dim_size(term->dim, type); + case isl_dim_div: return term->div->n_row; + case isl_dim_all: return isl_dim_total(term->dim) + term->div->n_row; + } +} + +isl_ctx *isl_term_get_ctx(__isl_keep isl_term *term) +{ + return term ? term->dim->ctx : NULL; +} + +void isl_term_get_num(__isl_keep isl_term *term, isl_int *n) +{ + if (!term) + return; + isl_int_set(*n, term->n); +} + +void isl_term_get_den(__isl_keep isl_term *term, isl_int *d) +{ + if (!term) + return; + isl_int_set(*d, term->d); +} + +int isl_term_get_exp(__isl_keep isl_term *term, + enum isl_dim_type type, unsigned pos) +{ + if (!term) + return -1; + + isl_assert(term->dim->ctx, pos < isl_term_dim(term, type), return -1); + + if (type >= isl_dim_set) + pos += isl_dim_size(term->dim, isl_dim_param); + if (type >= isl_dim_div) + pos += isl_dim_size(term->dim, isl_dim_set); + + return term->pow[pos]; +} + +__isl_give isl_div *isl_term_get_div(__isl_keep isl_term *term, unsigned pos) +{ + isl_basic_map *bmap; + unsigned total; + int k; + + if (!term) + return NULL; + + isl_assert(term->dim->ctx, pos < isl_term_dim(term, isl_dim_div), + return NULL); + + total = term->div->n_col - term->div->n_row - 2; + /* No nested divs for now */ + isl_assert(term->dim->ctx, + isl_seq_first_non_zero(term->div->row[pos] + 2 + total, + term->div->n_row) == -1, + return NULL); + + bmap = isl_basic_map_alloc_dim(isl_dim_copy(term->dim), 1, 0, 0); + if ((k = isl_basic_map_alloc_div(bmap)) < 0) + goto error; + + isl_seq_cpy(bmap->div[k], term->div->row[pos], 2 + total); + + return isl_basic_map_div(bmap, k); +error: + isl_basic_map_free(bmap); + return NULL; +} + +__isl_give isl_term *isl_upoly_foreach_term(__isl_keep struct isl_upoly *up, + int (*fn)(__isl_take isl_term *term, void *user), + __isl_take isl_term *term, void *user) +{ + int i; + struct isl_upoly_rec *rec; + + if (!up || !term) + goto error; + + if (isl_upoly_is_zero(up)) + return term; + + isl_assert(up->ctx, !isl_upoly_is_nan(up), goto error); + isl_assert(up->ctx, !isl_upoly_is_infty(up), goto error); + isl_assert(up->ctx, !isl_upoly_is_neginfty(up), goto error); + + if (isl_upoly_is_cst(up)) { + struct isl_upoly_cst *cst; + cst = isl_upoly_as_cst(up); + if (!cst) + goto error; + term = isl_term_cow(term); + if (!term) + goto error; + isl_int_set(term->n, cst->n); + isl_int_set(term->d, cst->d); + if (fn(isl_term_copy(term), user) < 0) + goto error; + return term; + } + + rec = isl_upoly_as_rec(up); + if (!rec) + goto error; + + for (i = 0; i < rec->n; ++i) { + term = isl_term_cow(term); + if (!term) + goto error; + term->pow[up->var] = i; + term = isl_upoly_foreach_term(rec->p[i], fn, term, user); + if (!term) + goto error; + } + term->pow[up->var] = 0; + + return term; +error: + isl_term_free(term); + return NULL; +} + +int isl_qpolynomial_foreach_term(__isl_keep isl_qpolynomial *qp, + int (*fn)(__isl_take isl_term *term, void *user), void *user) +{ + isl_term *term; + + if (!qp) + return -1; + + term = isl_term_alloc(isl_dim_copy(qp->dim), isl_mat_copy(qp->div)); + if (!term) + return -1; + + term = isl_upoly_foreach_term(qp->upoly, fn, term, user); + + isl_term_free(term); + + return term ? 0 : -1; +} + +int isl_pw_qpolynomial_foreach_piece(__isl_keep isl_pw_qpolynomial *pwqp, + int (*fn)(__isl_take isl_set *set, __isl_take isl_qpolynomial *qp, + void *user), void *user) +{ + int i; + + if (!pwqp) + return -1; + + for (i = 0; i < pwqp->n; ++i) + if (fn(isl_set_copy(pwqp->p[i].set), + isl_qpolynomial_copy(pwqp->p[i].qp), user) < 0) + return -1; + + return 0; +} diff --git a/isl_polynomial_private.h b/isl_polynomial_private.h index 3f351af..9052d96 100644 --- a/isl_polynomial_private.h +++ b/isl_polynomial_private.h @@ -33,6 +33,18 @@ struct isl_qpolynomial { struct isl_upoly *upoly; }; +struct isl_term { + int ref; + + isl_int n; + isl_int d; + + struct isl_dim *dim; + struct isl_mat *div; + + int pow[1]; +}; + struct isl_pw_qpolynomial_piece { struct isl_set *set; struct isl_qpolynomial *qp; -- 2.7.4