isl_fold.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 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 #include <isl_polynomial_private.h>
  12 #include <isl_point_private.h>
  13 #include <isl_dim_private.h>
  14 #include <isl_map_private.h>
  15
  16 int isl_qpolynomial_fold_involves_dims(__isl_keep isl_qpolynomial_fold *fold,
  17         enum isl_dim_type type, unsigned first, unsigned n)
  18 {
  19         int i;
  20
  21         if (!fold)
  22                 return -1;
  23         if (fold->n == 0 || n == 0)
  24                 return 0;
  25
  26         for (i = 0; i < fold->n; ++i) {
  27                 int involves = isl_qpolynomial_involves_dims(fold->qp[i],
  28                                                             type, first, n);
  29                 if (involves < 0 || involves)
  30                         return involves;
  31         }
  32         return 0;
  33 }
  34
  35 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_drop_dims(
  36         __isl_take isl_qpolynomial_fold *fold,
  37         enum isl_dim_type type, unsigned first, unsigned n)
  38 {
  39         int i;
  40
  41         if (!fold)
  42                 return NULL;
  43         if (n == 0)
  44                 return fold;
  45
  46         fold = isl_qpolynomial_fold_cow(fold);
  47         if (!fold)
  48                 return NULL;
  49         fold->dim = isl_dim_drop(fold->dim, type, first, n);
  50         if (!fold->dim)
  51                 goto error;
  52
  53         for (i = 0; i < fold->n; ++i) {
  54                 fold->qp[i] = isl_qpolynomial_drop_dims(fold->qp[i],
  55                                                             type, first, n);
  56                 if (!fold->qp[i])
  57                         goto error;
  58         }
  59
  60         return fold;
  61 error:
  62         isl_qpolynomial_fold_free(fold);
  63         return NULL;
  64 }
  65
  66 #undef PW
  67 #define PW isl_pw_qpolynomial_fold
  68 #undef EL
  69 #define EL isl_qpolynomial_fold
  70 #undef IS_ZERO
  71 #define IS_ZERO is_empty
  72 #undef FIELD
  73 #define FIELD fold
  74 #undef ADD
  75 #define ADD fold
  76
  77 #include <isl_pw_templ.c>
  78
  79 static __isl_give isl_qpolynomial_fold *qpolynomial_fold_alloc(
  80         enum isl_fold type, __isl_take isl_dim *dim, int n)
  81 {
  82         isl_qpolynomial_fold *fold;
  83
  84         if (!dim)
  85                 goto error;
  86
  87         isl_assert(dim->ctx, n >= 0, goto error);
  88         fold = isl_alloc(dim->ctx, struct isl_qpolynomial_fold,
  89                         sizeof(struct isl_qpolynomial_fold) +
  90                         (n - 1) * sizeof(struct isl_qpolynomial *));
  91         if (!fold)
  92                 goto error;
  93
  94         fold->ref = 1;
  95         fold->size = n;
  96         fold->n = 0;
  97         fold->type = type;
  98         fold->dim = dim;
  99
 100         return fold;
 101 error:
 102         isl_dim_free(dim);
 103         return NULL;
 104 }
 105
 106 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_empty(enum isl_fold type,
 107         __isl_take isl_dim *dim)
 108 {
 109         return qpolynomial_fold_alloc(type, dim, 0);
 110 }
 111
 112 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_alloc(
 113         enum isl_fold type, __isl_take isl_qpolynomial *qp)
 114 {
 115         isl_qpolynomial_fold *fold;
 116
 117         if (!qp)
 118                 return NULL;
 119
 120         fold = qpolynomial_fold_alloc(type, isl_dim_copy(qp->dim), 1);
 121         if (!fold)
 122                 goto error;
 123
 124         fold->qp[0] = qp;
 125         fold->n++;
 126
 127         return fold;
 128 error:
 129         isl_qpolynomial_fold_free(fold);
 130         isl_qpolynomial_free(qp);
 131         return NULL;
 132 }
 133
 134 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
 135         __isl_keep isl_qpolynomial_fold *fold)
 136 {
 137         if (!fold)
 138                 return NULL;
 139
 140         fold->ref++;
 141         return fold;
 142 }
 143
 144 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_dup(
 145         __isl_keep isl_qpolynomial_fold *fold)
 146 {
 147         int i;
 148         isl_qpolynomial_fold *dup;
 149
 150         if (!fold)
 151                 return NULL;
 152         dup = qpolynomial_fold_alloc(fold->type,
 153                                         isl_dim_copy(fold->dim), fold->n);
 154         if (!dup)
 155                 return NULL;
 156
 157         for (i = 0; i < fold->n; ++i) {
 158                 dup->qp[i] = isl_qpolynomial_copy(fold->qp[i]);
 159                 if (!dup->qp[i])
 160                         goto error;
 161         }
 162
 163         return dup;
 164 error:
 165         isl_qpolynomial_fold_free(dup);
 166         return NULL;
 167 }
 168
 169 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_cow(
 170         __isl_take isl_qpolynomial_fold *fold)
 171 {
 172         if (!fold)
 173                 return NULL;
 174
 175         if (fold->ref == 1)
 176                 return fold;
 177         fold->ref--;
 178         return isl_qpolynomial_fold_dup(fold);
 179 }
 180
 181 void isl_qpolynomial_fold_free(__isl_take isl_qpolynomial_fold *fold)
 182 {
 183         int i;
 184
 185         if (!fold)
 186                 return;
 187         if (--fold->ref > 0)
 188                 return;
 189
 190         for (i = 0; i < fold->n; ++i)
 191                 isl_qpolynomial_free(fold->qp[i]);
 192         isl_dim_free(fold->dim);
 193         free(fold);
 194 }
 195
 196 int isl_qpolynomial_fold_is_empty(__isl_keep isl_qpolynomial_fold *fold)
 197 {
 198         if (!fold)
 199                 return -1;
 200
 201         return fold->n == 0;
 202 }
 203
 204 __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_fold(
 205         __isl_take isl_qpolynomial_fold *fold1,
 206         __isl_take isl_qpolynomial_fold *fold2)
 207 {
 208         int i;
 209         struct isl_qpolynomial_fold *res = NULL;
 210
 211         if (!fold1 || !fold2)
 212                 goto error;
 213
 214         isl_assert(fold1->dim->ctx, fold1->type == fold2->type, goto error);
 215         isl_assert(fold1->dim->ctx, isl_dim_equal(fold1->dim, fold2->dim),
 216                         goto error);
 217
 218         if (isl_qpolynomial_fold_is_empty(fold1)) {
 219                 isl_qpolynomial_fold_free(fold1);
 220                 return fold2;
 221         }
 222
 223         if (isl_qpolynomial_fold_is_empty(fold2)) {
 224                 isl_qpolynomial_fold_free(fold2);
 225                 return fold1;
 226         }
 227
 228         res = qpolynomial_fold_alloc(fold1->type, isl_dim_copy(fold1->dim),
 229                                         fold1->n + fold2->n);
 230         if (!res)
 231                 goto error;
 232
 233         for (i = 0; i < fold1->n; ++i) {
 234                 res->qp[res->n] = isl_qpolynomial_copy(fold1->qp[i]);
 235                 if (!res->qp[res->n])
 236                         goto error;
 237                 res->n++;
 238         }
 239
 240         for (i = 0; i < fold2->n; ++i) {
 241                 res->qp[res->n] = isl_qpolynomial_copy(fold2->qp[i]);
 242                 if (!res->qp[res->n])
 243                         goto error;
 244                 res->n++;
 245         }
 246
 247         isl_qpolynomial_fold_free(fold1);
 248         isl_qpolynomial_fold_free(fold2);
 249
 250         return res;
 251 error:
 252         isl_qpolynomial_fold_free(res);
 253         isl_qpolynomial_fold_free(fold1);
 254         isl_qpolynomial_fold_free(fold2);
 255         return NULL;
 256 }
 257
 258 __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_from_pw_qpolynomial(
 259         enum isl_fold type, __isl_take isl_pw_qpolynomial *pwqp)
 260 {
 261         int i;
 262         isl_pw_qpolynomial_fold *pwf;
 263
 264         if (!pwqp)
 265                 return NULL;
 266
 267         pwf = isl_pw_qpolynomial_fold_alloc_(isl_dim_copy(pwqp->dim), pwqp->n);
 268
 269         for (i = 0; i < pwqp->n; ++i)
 270                 pwf = isl_pw_qpolynomial_fold_add_piece(pwf,
 271                         isl_set_copy(pwqp->p[i].set),
 272                         isl_qpolynomial_fold_alloc(type,
 273                                 isl_qpolynomial_copy(pwqp->p[i].qp)));
 274
 275         isl_pw_qpolynomial_free(pwqp);
 276
 277         return pwf;
 278 }
 279
 280 int isl_qpolynomial_fold_is_equal(__isl_keep isl_qpolynomial_fold *fold1,
 281         __isl_keep isl_qpolynomial_fold *fold2)
 282 {
 283         int i;
 284
 285         if (!fold1 || !fold2)
 286                 return -1;
 287
 288         if (fold1->n != fold2->n)
 289                 return 0;
 290
 291         /* We probably want to sort the qps first... */
 292         for (i = 0; i < fold1->n; ++i) {
 293                 int eq = isl_qpolynomial_is_equal(fold1->qp[i], fold2->qp[i]);
 294                 if (eq < 0 || !eq)
 295                         return eq;
 296         }
 297
 298         return 1;
 299 }
 300
 301 __isl_give isl_qpolynomial *isl_qpolynomial_fold_eval(
 302         __isl_take isl_qpolynomial_fold *fold, __isl_take isl_point *pnt)
 303 {
 304         isl_qpolynomial *qp;
 305
 306         if (!fold || !pnt)
 307                 goto error;
 308         isl_assert(pnt->dim->ctx, isl_dim_equal(pnt->dim, fold->dim), goto error);
 309         isl_assert(pnt->dim->ctx,
 310                 fold->type == isl_fold_max || fold->type == isl_fold_min,
 311                 goto error);
 312
 313         if (fold->n == 0)
 314                 qp = isl_qpolynomial_zero(isl_dim_copy(fold->dim));
 315         else {
 316                 int i;
 317                 qp = isl_qpolynomial_eval(isl_qpolynomial_copy(fold->qp[0]),
 318                                                 isl_point_copy(pnt));
 319                 for (i = 1; i < fold->n; ++i) {
 320                         isl_qpolynomial *qp_i;
 321                         qp_i = isl_qpolynomial_eval(
 322                                             isl_qpolynomial_copy(fold->qp[i]),
 323                                             isl_point_copy(pnt));
 324                         if (fold->type == isl_fold_max)
 325                                 qp = isl_qpolynomial_max_cst(qp, qp_i);
 326                         else
 327                                 qp = isl_qpolynomial_min_cst(qp, qp_i);
 328                 }
 329         }
 330         isl_qpolynomial_fold_free(fold);
 331         isl_point_free(pnt);
 332
 333         return qp;
 334 error:
 335         isl_qpolynomial_fold_free(fold);
 336         isl_point_free(pnt);
 337         return NULL;
 338 }