isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  * Copyright 2013      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #undef TYPE
  14 #define TYPE    UNION
  15 static
  16 #include "has_single_reference_templ.c"
  17
  18 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  19
  20 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  21 {
  22         return u ? u->space->ctx : NULL;
  23 }
  24
  25 /* Return the space of "u".
  26  */
  27 static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u)
  28 {
  29         if (!u)
  30                 return NULL;
  31         return u->space;
  32 }
  33
  34 /* Return a copy of the space of "u".
  35  */
  36 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
  37 {
  38         return isl_space_copy(FN(UNION,peek_space)(u));
  39 }
  40
  41 /* Return the number of parameters of "u", where "type"
  42  * is required to be set to isl_dim_param.
  43  */
  44 isl_size FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
  45 {
  46         if (!u)
  47                 return isl_size_error;
  48
  49         if (type != isl_dim_param)
  50                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
  51                         "can only reference parameters", return isl_size_error);
  52
  53         return isl_space_dim(u->space, type);
  54 }
  55
  56 /* Return the position of the parameter with the given name
  57  * in "u".
  58  * Return -1 if no such dimension can be found.
  59  */
  60 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
  61         const char *name)
  62 {
  63         if (!u)
  64                 return -1;
  65         return isl_space_find_dim_by_name(u->space, type, name);
  66 }
  67
  68 #ifdef HAS_TYPE
  69 #define OPT_TYPE_PARAM          , enum isl_fold type
  70 #define OPT_TYPE_ARG(loc)       , loc type
  71 #define OPT_SET_TYPE(loc,val)   loc type = (val);
  72 #else
  73 #define OPT_TYPE_PARAM
  74 #define OPT_TYPE_ARG(loc)
  75 #define OPT_SET_TYPE(loc,val)
  76 #endif
  77
  78 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space
  79         OPT_TYPE_PARAM, int size)
  80 {
  81         UNION *u;
  82
  83         space = isl_space_params(space);
  84         if (!space)
  85                 return NULL;
  86
  87         u = isl_calloc_type(space->ctx, UNION);
  88         if (!u)
  89                 goto error;
  90
  91         u->ref = 1;
  92         OPT_SET_TYPE(u->, type);
  93         u->space = space;
  94         if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
  95                 return FN(UNION,free)(u);
  96
  97         return u;
  98 error:
  99         isl_space_free(space);
 100         return NULL;
 101 }
 102
 103 /* Create an empty/zero union without specifying any parameters.
 104  */
 105 __isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM)
 106 {
 107         isl_space *space;
 108
 109         space = isl_space_unit(ctx);
 110         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG());
 111 }
 112
 113 __isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space
 114         OPT_TYPE_PARAM)
 115 {
 116         return FN(UNION,alloc)(space OPT_TYPE_ARG(), 16);
 117 }
 118
 119 /* This is an alternative name for the function above.
 120  */
 121 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
 122 {
 123         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG());
 124 }
 125
 126 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
 127 {
 128         if (!u)
 129                 return NULL;
 130
 131         u->ref++;
 132         return u;
 133 }
 134
 135 /* Extract the element of "u" living in "space" (ignoring parameters).
 136  *
 137  * Return the ZERO element if "u" does not contain any element
 138  * living in "space".
 139  */
 140 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
 141         __isl_take isl_space *space)
 142 {
 143         struct isl_hash_table_entry *entry;
 144
 145         space = isl_space_replace_params(space, FN(UNION,peek_space)(u));
 146
 147         entry = FN(UNION,find_part_entry)(u, space, 0);
 148         if (!entry)
 149                 goto error;
 150         if (entry == isl_hash_table_entry_none)
 151                 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->));
 152         isl_space_free(space);
 153         return FN(PART,copy)(entry->data);
 154 error:
 155         isl_space_free(space);
 156         return NULL;
 157 }
 158
 159 /* Add "part" to "u".
 160  * If "disjoint" is set, then "u" is not allowed to already have
 161  * a part that is defined over a domain that overlaps with the domain
 162  * of "part".
 163  * Otherwise, compute the union sum of "part" and the part in "u"
 164  * defined on the same space.
 165  */
 166 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
 167         __isl_take PART *part, int disjoint)
 168 {
 169         int empty;
 170         struct isl_hash_table_entry *entry;
 171
 172         if (!part)
 173                 goto error;
 174
 175         empty = FN(PART,IS_ZERO)(part);
 176         if (empty < 0)
 177                 goto error;
 178         if (empty) {
 179                 FN(PART,free)(part);
 180                 return u;
 181         }
 182
 183         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 184         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 185
 186         u = FN(UNION,cow)(u);
 187
 188         if (!u)
 189                 goto error;
 190
 191         if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
 192                 goto error;
 193         entry = FN(UNION,find_part_entry)(u, part->dim, 1);
 194         if (!entry)
 195                 goto error;
 196
 197         if (!entry->data)
 198                 entry->data = part;
 199         else {
 200                 if (disjoint &&
 201                     FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
 202                         goto error;
 203                 entry->data = FN(PART,union_add_)(entry->data,
 204                                                 FN(PART,copy)(part));
 205                 if (!entry->data)
 206                         goto error;
 207                 empty = FN(PART,IS_ZERO)(part);
 208                 if (empty < 0)
 209                         goto error;
 210                 if (empty)
 211                         u = FN(UNION,remove_part_entry)(u, entry);
 212                 FN(PART,free)(part);
 213         }
 214
 215         return u;
 216 error:
 217         FN(PART,free)(part);
 218         FN(UNION,free)(u);
 219         return NULL;
 220 }
 221
 222 /* Add "part" to "u", where "u" is assumed not to already have
 223  * a part that is defined on the same space as "part".
 224  */
 225 __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
 226         __isl_take PART *part)
 227 {
 228         return FN(UNION,add_part_generic)(u, part, 1);
 229 }
 230
 231 /* Allocate a UNION with the same type (if any) and the same size as "u" and
 232  * with space "space".
 233  */
 234 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
 235         __isl_take isl_space *space)
 236 {
 237         if (!u)
 238                 goto error;
 239         return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n);
 240 error:
 241         isl_space_free(space);
 242         return NULL;
 243 }
 244
 245 /* Allocate a UNION with the same space, the same type (if any) and
 246  * the same size as "u".
 247  */
 248 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
 249 {
 250         return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
 251 }
 252
 253 /* Internal data structure for isl_union_*_transform_space.
 254  * "fn' is applied to each entry in the input.
 255  * "res" collects the results.
 256  */
 257 S(UNION,transform_data)
 258 {
 259         __isl_give PART *(*fn)(__isl_take PART *part, void *user);
 260         void *user;
 261
 262         UNION *res;
 263 };
 264
 265 /* Apply data->fn to "part" and add the result to data->res.
 266  */
 267 static isl_stat FN(UNION,transform_entry)(__isl_take PART *part, void *user)
 268 {
 269         S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
 270
 271         part = data->fn(part, data->user);
 272         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 273         if (!data->res)
 274                 return isl_stat_error;
 275
 276         return isl_stat_ok;
 277 }
 278
 279 /* Return a UNION living in "space" that is obtained by applying "fn"
 280  * to each of the entries in "u".
 281  */
 282 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
 283         isl_space *space,
 284         __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
 285 {
 286         S(UNION,transform_data) data = { fn, user };
 287
 288         data.res = FN(UNION,alloc_same_size_on_space)(u, space);
 289         if (FN(FN(UNION,foreach),BASE)(u,
 290                                         &FN(UNION,transform_entry), &data) < 0)
 291                 data.res = FN(UNION,free)(data.res);
 292         FN(UNION,free)(u);
 293         return data.res;
 294 }
 295
 296 /* Return a UNION that lives in the same space as "u" and that is obtained
 297  * by applying "fn" to each of the entries in "u".
 298  */
 299 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
 300         __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
 301 {
 302         return FN(UNION,transform_space)(u, FN(UNION,get_space)(u), fn, user);
 303 }
 304
 305 /* Apply data->fn to *part and store the result back into *part.
 306  */
 307 static isl_stat FN(UNION,transform_inplace_entry)(void **part, void *user)
 308 {
 309         S(UNION,transform_data) *data = (S(UNION,transform_data) *) user;
 310
 311         *part = data->fn(*part, data->user);
 312         if (!*part)
 313                 return isl_stat_error;
 314         return isl_stat_ok;
 315 }
 316
 317 /* Update "u" by applying "fn" to each entry.
 318  * This operation is assumed not to change the number of entries nor
 319  * the spaces of the entries.
 320  *
 321  * If there is only one reference to "u", then change "u" inplace.
 322  * Otherwise, create a new UNION from "u" and discard the original.
 323  */
 324 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
 325         __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
 326 {
 327         isl_bool single_ref;
 328
 329         single_ref = FN(UNION,has_single_reference)(u);
 330         if (single_ref < 0)
 331                 return FN(UNION,free)(u);
 332         if (single_ref) {
 333                 S(UNION,transform_data) data = { fn, user };
 334                 if (FN(UNION,foreach_inplace)(u,
 335                                 &FN(UNION,transform_inplace_entry), &data) < 0)
 336                         return FN(UNION,free)(u);
 337                 return u;
 338         }
 339         return FN(UNION,transform)(u, fn, user);
 340 }
 341
 342 /* An isl_union_*_transform callback for use in isl_union_*_dup
 343  * that simply returns "part".
 344  */
 345 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
 346 {
 347         return part;
 348 }
 349
 350 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 351 {
 352         u = FN(UNION,copy)(u);
 353         return FN(UNION,transform)(u, &FN(UNION,copy_part), NULL);
 354 }
 355
 356 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 357 {
 358         if (!u)
 359                 return NULL;
 360
 361         if (u->ref == 1)
 362                 return u;
 363         u->ref--;
 364         return FN(UNION,dup)(u);
 365 }
 366
 367 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 368 {
 369         if (!u)
 370                 return NULL;
 371
 372         if (--u->ref > 0)
 373                 return NULL;
 374
 375         isl_hash_table_foreach(u->space->ctx, &u->table,
 376                                 &FN(UNION,free_u_entry), NULL);
 377         isl_hash_table_clear(&u->table);
 378         isl_space_free(u->space);
 379         free(u);
 380         return NULL;
 381 }
 382
 383 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
 384 {
 385         isl_reordering *exp = user;
 386
 387         exp = isl_reordering_extend_space(isl_reordering_copy(exp),
 388                                     FN(PART,get_domain_space)(part));
 389         return FN(PART,realign_domain)(part, exp);
 390 }
 391
 392 /* Reorder the parameters of "u" according to the given reordering.
 393  */
 394 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
 395         __isl_take isl_reordering *r)
 396 {
 397         isl_space *space;
 398
 399         if (!u || !r)
 400                 goto error;
 401
 402         space = isl_reordering_get_space(r);
 403         u = FN(UNION,transform_space)(u, space, &FN(UNION,align_entry), r);
 404         isl_reordering_free(r);
 405         return u;
 406 error:
 407         FN(UNION,free)(u);
 408         isl_reordering_free(r);
 409         return NULL;
 410 }
 411
 412 /* Align the parameters of "u" to those of "model".
 413  */
 414 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 415         __isl_take isl_space *model)
 416 {
 417         isl_bool equal_params;
 418         isl_reordering *r;
 419
 420         if (!u || !model)
 421                 goto error;
 422
 423         equal_params = isl_space_has_equal_params(u->space, model);
 424         if (equal_params < 0)
 425                 goto error;
 426         if (equal_params) {
 427                 isl_space_free(model);
 428                 return u;
 429         }
 430
 431         r = isl_parameter_alignment_reordering(u->space, model);
 432         isl_space_free(model);
 433
 434         return FN(UNION,realign_domain)(u, r);
 435 error:
 436         isl_space_free(model);
 437         FN(UNION,free)(u);
 438         return NULL;
 439 }
 440
 441 /* Add "part" to *u, taking the union sum if "u" already has
 442  * a part defined on the same space as "part".
 443  */
 444 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
 445 {
 446         UNION **u = (UNION **)user;
 447
 448         *u = FN(UNION,add_part_generic)(*u, part, 0);
 449
 450         return isl_stat_ok;
 451 }
 452
 453 /* Compute the sum of "u1" and "u2" on the union of their domains,
 454  * with the actual sum on the shared domain and
 455  * the defined expression on the symmetric difference of the domains.
 456  *
 457  * This is an internal function that is exposed under different
 458  * names depending on whether the base expressions have a zero default
 459  * value.
 460  * If they do, then this function is called "add".
 461  * Otherwise, it is called "union_add".
 462  */
 463 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
 464         __isl_take UNION *u2)
 465 {
 466         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 467         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 468
 469         u1 = FN(UNION,cow)(u1);
 470
 471         if (!u1 || !u2)
 472                 goto error;
 473
 474         if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
 475                 goto error;
 476
 477         FN(UNION,free)(u2);
 478
 479         return u1;
 480 error:
 481         FN(UNION,free)(u1);
 482         FN(UNION,free)(u2);
 483         return NULL;
 484 }
 485
 486 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
 487 {
 488         isl_space *space;
 489         UNION *u;
 490
 491         if (!part)
 492                 return NULL;
 493
 494         space = FN(PART,get_space)(part);
 495         space = isl_space_drop_dims(space, isl_dim_in, 0,
 496                                         isl_space_dim(space, isl_dim_in));
 497         space = isl_space_drop_dims(space, isl_dim_out, 0,
 498                                         isl_space_dim(space, isl_dim_out));
 499         u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
 500         u = FN(FN(UNION,add),BASE)(u, part);
 501
 502         return u;
 503 }
 504
 505 S(UNION,match_bin_data) {
 506         UNION *u2;
 507         UNION *res;
 508         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 509 };
 510
 511 /* Check if data->u2 has an element living in the same space as "part".
 512  * If so, call data->fn on the two elements and add the result to
 513  * data->res.
 514  */
 515 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
 516 {
 517         S(UNION,match_bin_data) *data = user;
 518         struct isl_hash_table_entry *entry2;
 519         isl_space *space;
 520         PART *part2;
 521
 522         space = FN(PART,get_space)(part);
 523         entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
 524         isl_space_free(space);
 525         if (!entry2)
 526                 goto error;
 527         if (entry2 == isl_hash_table_entry_none) {
 528                 FN(PART,free)(part);
 529                 return isl_stat_ok;
 530         }
 531
 532         part2 = entry2->data;
 533         if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
 534                                         part2->dim, isl_dim_out))
 535                 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
 536                         "entries should have the same range space",
 537                         goto error);
 538
 539         part = data->fn(part, FN(PART, copy)(entry2->data));
 540
 541         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 542         if (!data->res)
 543                 return isl_stat_error;
 544
 545         return isl_stat_ok;
 546 error:
 547         FN(PART,free)(part);
 548         return isl_stat_error;
 549 }
 550
 551 /* This function is currently only used from isl_polynomial.c
 552  * and not from isl_fold.c.
 553  */
 554 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 555         __isl_take UNION *u2,
 556         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 557         __attribute__ ((unused));
 558 /* For each pair of elements in "u1" and "u2" living in the same space,
 559  * call "fn" and collect the results.
 560  */
 561 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 562         __isl_take UNION *u2,
 563         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 564 {
 565         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 566
 567         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 568         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 569
 570         if (!u1 || !u2)
 571                 goto error;
 572
 573         data.u2 = u2;
 574         data.res = FN(UNION,alloc_same_size)(u1);
 575         if (FN(FN(UNION,foreach),BASE)(u1,
 576                                     &FN(UNION,match_bin_entry), &data) < 0)
 577                 goto error;
 578
 579         FN(UNION,free)(u1);
 580         FN(UNION,free)(u2);
 581         return data.res;
 582 error:
 583         FN(UNION,free)(u1);
 584         FN(UNION,free)(u2);
 585         FN(UNION,free)(data.res);
 586         return NULL;
 587 }
 588
 589 /* Compute the sum of "u1" and "u2".
 590  *
 591  * If the base expressions have a default zero value, then the sum
 592  * is computed on the union of the domains of "u1" and "u2".
 593  * Otherwise, it is computed on their shared domains.
 594  */
 595 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 596 {
 597 #if DEFAULT_IS_ZERO
 598         return FN(UNION,union_add_)(u1, u2);
 599 #else
 600         return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
 601 #endif
 602 }
 603
 604 #ifndef NO_SUB
 605 /* Subtract "u2" from "u1" and return the result.
 606  */
 607 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 608 {
 609         return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
 610 }
 611 #endif
 612
 613 S(UNION,any_set_data) {
 614         isl_set *set;
 615         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 616 };
 617
 618 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
 619         void *user)
 620 {
 621         S(UNION,any_set_data) *data = user;
 622
 623         return data->fn(part, isl_set_copy(data->set));
 624 }
 625
 626 /* Update each element of "u" by calling "fn" on the element and "set".
 627  */
 628 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
 629         __isl_take isl_set *set,
 630         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 631 {
 632         S(UNION,any_set_data) data = { NULL, fn };
 633
 634         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 635         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 636
 637         if (!u || !set)
 638                 goto error;
 639
 640         data.set = set;
 641         u = FN(UNION,transform)(u, &FN(UNION,any_set_entry), &data);
 642         isl_set_free(set);
 643         return u;
 644 error:
 645         FN(UNION,free)(u);
 646         isl_set_free(set);
 647         return NULL;
 648 }
 649
 650 /* Intersect the domain of "u" with the parameter domain "context".
 651  */
 652 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 653         __isl_take isl_set *set)
 654 {
 655         return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
 656 }
 657
 658 /* Compute the gist of the domain of "u" with respect to
 659  * the parameter domain "context".
 660  */
 661 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 662         __isl_take isl_set *set)
 663 {
 664         return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
 665 }
 666
 667 S(UNION,match_domain_data) {
 668         isl_union_set *uset;
 669         UNION *res;
 670         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 671 };
 672
 673 static int FN(UNION,set_has_space)(const void *entry, const void *val)
 674 {
 675         isl_set *set = (isl_set *)entry;
 676         isl_space *space = (isl_space *)val;
 677
 678         return isl_space_is_equal(set->dim, space);
 679 }
 680
 681 /* Find the set in data->uset that lives in the same space as the domain
 682  * of "part", apply data->fn to *entry and this set (if any), and add
 683  * the result to data->res.
 684  */
 685 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
 686 {
 687         S(UNION,match_domain_data) *data = user;
 688         uint32_t hash;
 689         struct isl_hash_table_entry *entry2;
 690         isl_space *space;
 691
 692         space = FN(PART,get_domain_space)(part);
 693         hash = isl_space_get_hash(space);
 694         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 695                                      hash, &FN(UNION,set_has_space), space, 0);
 696         isl_space_free(space);
 697         if (!entry2) {
 698                 FN(PART,free)(part);
 699                 return isl_stat_ok;
 700         }
 701
 702         part = data->fn(part, isl_set_copy(entry2->data));
 703
 704         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 705         if (!data->res)
 706                 return isl_stat_error;
 707
 708         return isl_stat_ok;
 709 }
 710
 711 /* Apply fn to each pair of PW in u and set in uset such that
 712  * the set lives in the same space as the domain of PW
 713  * and collect the results.
 714  */
 715 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
 716         __isl_take isl_union_set *uset,
 717         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 718 {
 719         S(UNION,match_domain_data) data = { NULL, NULL, fn };
 720
 721         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
 722         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 723
 724         if (!u || !uset)
 725                 goto error;
 726
 727         data.uset = uset;
 728         data.res = FN(UNION,alloc_same_size)(u);
 729         if (FN(FN(UNION,foreach),BASE)(u,
 730                                    &FN(UNION,match_domain_entry), &data) < 0)
 731                 goto error;
 732
 733         FN(UNION,free)(u);
 734         isl_union_set_free(uset);
 735         return data.res;
 736 error:
 737         FN(UNION,free)(u);
 738         isl_union_set_free(uset);
 739         FN(UNION,free)(data.res);
 740         return NULL;
 741 }
 742
 743 /* Intersect the domain of "u" with "uset".
 744  * If "uset" is a parameters domain, then intersect the parameter
 745  * domain of "u" with this set.
 746  */
 747 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 748         __isl_take isl_union_set *uset)
 749 {
 750         if (isl_union_set_is_params(uset))
 751                 return FN(UNION,intersect_params)(u,
 752                                                 isl_set_from_union_set(uset));
 753         return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
 754 }
 755
 756 /* Take the set (which may be empty) in data->uset that lives
 757  * in the same space as the domain of "pw", subtract it from the domain
 758  * of "part" and return the result.
 759  */
 760 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
 761         void *user)
 762 {
 763         isl_union_set *uset = user;
 764         isl_space *space;
 765         isl_set *set;
 766
 767         space = FN(PART,get_domain_space)(part);
 768         set = isl_union_set_extract_set(uset, space);
 769         return FN(PART,subtract_domain)(part, set);
 770 }
 771
 772 /* Subtract "uset' from the domain of "u".
 773  */
 774 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
 775         __isl_take isl_union_set *uset)
 776 {
 777         u = FN(UNION,transform)(u, &FN(UNION,subtract_domain_entry), uset);
 778         isl_union_set_free(uset);
 779         return u;
 780 }
 781
 782 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 783         __isl_take isl_union_set *uset)
 784 {
 785         if (isl_union_set_is_params(uset))
 786                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 787         return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
 788 }
 789
 790 /* Coalesce an entry in a UNION.  Coalescing is performed in-place.
 791  * Since the UNION may have several references, the entry is only
 792  * replaced if the coalescing is successful.
 793  */
 794 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
 795 {
 796         PART **part_p = (PART **) entry;
 797         PART *part;
 798
 799         part = FN(PART,copy)(*part_p);
 800         part = FN(PW,coalesce)(part);
 801         if (!part)
 802                 return isl_stat_error;
 803         FN(PART,free)(*part_p);
 804         *part_p = part;
 805
 806         return isl_stat_ok;
 807 }
 808
 809 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 810 {
 811         if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
 812                 goto error;
 813
 814         return u;
 815 error:
 816         FN(UNION,free)(u);
 817         return NULL;
 818 }
 819
 820 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
 821 {
 822         isl_union_set **uset = (isl_union_set **)user;
 823
 824         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 825
 826         return isl_stat_ok;
 827 }
 828
 829 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 830 {
 831         isl_union_set *uset;
 832
 833         uset = isl_union_set_empty(FN(UNION,get_space)(u));
 834         if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
 835                 goto error;
 836
 837         FN(UNION,free)(u);
 838
 839         return uset;
 840 error:
 841         isl_union_set_free(uset);
 842         FN(UNION,free)(u);
 843         return NULL;
 844 }
 845
 846 #ifdef HAS_TYPE
 847 /* Negate the type of "u".
 848  */
 849 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
 850 {
 851         u = FN(UNION,cow)(u);
 852         if (!u)
 853                 return NULL;
 854         u->type = isl_fold_type_negate(u->type);
 855         return u;
 856 }
 857 #else
 858 /* Negate the type of "u".
 859  * Since "u" does not have a type, do nothing.
 860  */
 861 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
 862 {
 863         return u;
 864 }
 865 #endif
 866
 867 /* Multiply "part" by the isl_val "user" and return the result.
 868  */
 869 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
 870         void *user)
 871 {
 872         isl_val *v = user;
 873
 874         return FN(PART,scale_val)(part, isl_val_copy(v));
 875 }
 876
 877 /* Multiply "u" by "v" and return the result.
 878  */
 879 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
 880         __isl_take isl_val *v)
 881 {
 882         if (!u || !v)
 883                 goto error;
 884         if (isl_val_is_one(v)) {
 885                 isl_val_free(v);
 886                 return u;
 887         }
 888
 889         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
 890                 UNION *zero;
 891                 isl_space *space = FN(UNION,get_space)(u);
 892                 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
 893                 FN(UNION,free)(u);
 894                 isl_val_free(v);
 895                 return zero;
 896         }
 897
 898         if (!isl_val_is_rat(v))
 899                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 900                         "expecting rational factor", goto error);
 901
 902         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
 903         if (isl_val_is_neg(v))
 904                 u = FN(UNION,negate_type)(u);
 905
 906         isl_val_free(v);
 907         return u;
 908 error:
 909         isl_val_free(v);
 910         FN(UNION,free)(u);
 911         return NULL;
 912 }
 913
 914 /* Divide "part" by the isl_val "user" and return the result.
 915  */
 916 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
 917         void *user)
 918 {
 919         isl_val *v = user;
 920
 921         return FN(PART,scale_down_val)(part, isl_val_copy(v));
 922 }
 923
 924 /* Divide "u" by "v" and return the result.
 925  */
 926 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
 927         __isl_take isl_val *v)
 928 {
 929         if (!u || !v)
 930                 goto error;
 931         if (isl_val_is_one(v)) {
 932                 isl_val_free(v);
 933                 return u;
 934         }
 935
 936         if (!isl_val_is_rat(v))
 937                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 938                         "expecting rational factor", goto error);
 939         if (isl_val_is_zero(v))
 940                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 941                         "cannot scale down by zero", goto error);
 942
 943         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
 944         if (isl_val_is_neg(v))
 945                 u = FN(UNION,negate_type)(u);
 946
 947         isl_val_free(v);
 948         return u;
 949 error:
 950         isl_val_free(v);
 951         FN(UNION,free)(u);
 952         return NULL;
 953 }
 954
 955 S(UNION,plain_is_equal_data)
 956 {
 957         UNION *u2;
 958         isl_bool is_equal;
 959 };
 960
 961 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
 962 {
 963         S(UNION,plain_is_equal_data) *data = user;
 964         struct isl_hash_table_entry *entry2;
 965         PW *pw = *entry;
 966
 967         entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
 968         if (!entry2 || entry2 == isl_hash_table_entry_none) {
 969                 if (!entry2)
 970                         data->is_equal = isl_bool_error;
 971                 else
 972                         data->is_equal = isl_bool_false;
 973                 return isl_stat_error;
 974         }
 975
 976         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
 977         if (data->is_equal < 0 || !data->is_equal)
 978                 return isl_stat_error;
 979
 980         return isl_stat_ok;
 981 }
 982
 983 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 984 {
 985         S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
 986         isl_size n1, n2;
 987
 988         if (!u1 || !u2)
 989                 return isl_bool_error;
 990         if (u1 == u2)
 991                 return isl_bool_true;
 992         if (u1->table.n != u2->table.n)
 993                 return isl_bool_false;
 994         n1 = FN(FN(UNION,n),BASE)(u1);
 995         n2 = FN(FN(UNION,n),BASE)(u2);
 996         if (n1 < 0 || n2 < 0)
 997                 return isl_bool_error;
 998         if (n1 != n2)
 999                 return isl_bool_false;
1000
1001         u1 = FN(UNION,copy)(u1);
1002         u2 = FN(UNION,copy)(u2);
1003         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1004         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1005         if (!u1 || !u2)
1006                 goto error;
1007
1008         data.u2 = u2;
1009         if (FN(UNION,foreach_inplace)(u1,
1010                                &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1011             data.is_equal)
1012                 goto error;
1013
1014         FN(UNION,free)(u1);
1015         FN(UNION,free)(u2);
1016
1017         return data.is_equal;
1018 error:
1019         FN(UNION,free)(u1);
1020         FN(UNION,free)(u2);
1021         return isl_bool_error;
1022 }
1023
1024 /* Check whether the element that "entry" points to involves any NaNs and
1025  * store the result in *nan.
1026  * Abort as soon as one such element has been found.
1027  */
1028 static isl_stat FN(UNION,involves_nan_entry)(void **entry, void *user)
1029 {
1030         isl_bool *nan = user;
1031         PW *pw = *entry;
1032
1033         *nan = FN(PW,involves_nan)(pw);
1034         if (*nan < 0 || !nan)
1035                 return isl_stat_error;
1036
1037         return isl_stat_ok;
1038 }
1039
1040 /* Does "u" involve any NaNs?
1041  */
1042 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1043 {
1044         isl_bool nan = isl_bool_false;
1045
1046         if (!u)
1047                 return isl_bool_error;
1048
1049         if (FN(UNION,foreach_inplace)(u,
1050                                     &FN(UNION,involves_nan_entry), &nan) < 0 &&
1051             !nan)
1052                 return isl_bool_error;
1053
1054         return nan;
1055 }
1056
1057 /* Internal data structure for isl_union_*_drop_dims.
1058  * type, first and n are passed to isl_*_drop_dims.
1059  */
1060 S(UNION,drop_dims_data) {
1061         enum isl_dim_type type;
1062         unsigned first;
1063         unsigned n;
1064 };
1065
1066 /* Drop the parameters specified by "data" from "part" and return the result.
1067  */
1068 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1069         void *user)
1070 {
1071         S(UNION,drop_dims_data) *data = user;
1072
1073         return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1074 }
1075
1076 /* Drop the specified parameters from "u".
1077  * That is, type is required to be isl_dim_param.
1078  */
1079 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1080         enum isl_dim_type type, unsigned first, unsigned n)
1081 {
1082         isl_space *space;
1083         S(UNION,drop_dims_data) data = { type, first, n };
1084
1085         if (!u)
1086                 return NULL;
1087
1088         if (type != isl_dim_param)
1089                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1090                         "can only project out parameters",
1091                         return FN(UNION,free)(u));
1092
1093         space = FN(UNION,get_space)(u);
1094         space = isl_space_drop_dims(space, type, first, n);
1095         return FN(UNION,transform_space)(u, space, &FN(UNION,drop_dims_entry),
1096                                         &data);
1097 }
1098
1099 /* Internal data structure for isl_union_*_set_dim_name.
1100  * pos is the position of the parameter that needs to be renamed.
1101  * s is the new name.
1102  */
1103 S(UNION,set_dim_name_data) {
1104         unsigned pos;
1105         const char *s;
1106 };
1107
1108 /* Change the name of the parameter at position data->pos of "part" to data->s
1109  * and return the result.
1110  */
1111 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1112         void *user)
1113 {
1114         S(UNION,set_dim_name_data) *data = user;
1115
1116         return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1117 }
1118
1119 /* Change the name of the parameter at position "pos" to "s".
1120  * That is, type is required to be isl_dim_param.
1121  */
1122 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1123         enum isl_dim_type type, unsigned pos, const char *s)
1124 {
1125         S(UNION,set_dim_name_data) data = { pos, s };
1126         isl_space *space;
1127
1128         if (!u)
1129                 return NULL;
1130
1131         if (type != isl_dim_param)
1132                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1133                         "can only set parameter names",
1134                         return FN(UNION,free)(u));
1135
1136         space = FN(UNION,get_space)(u);
1137         space = isl_space_set_dim_name(space, type, pos, s);
1138         return FN(UNION,transform_space)(u, space,
1139                                         &FN(UNION,set_dim_name_entry), &data);
1140 }
1141
1142 /* Reset the user pointer on all identifiers of parameters and tuples
1143  * of the space of "part" and return the result.
1144  */
1145 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1146         void *user)
1147 {
1148         return FN(PART,reset_user)(part);
1149 }
1150
1151 /* Reset the user pointer on all identifiers of parameters and tuples
1152  * of the spaces of "u".
1153  */
1154 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1155 {
1156         isl_space *space;
1157
1158         space = FN(UNION,get_space)(u);
1159         space = isl_space_reset_user(space);
1160         return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry),
1161                                         NULL);
1162 }
1163
1164 /* Add the base expression held by "entry" to "list".
1165  */
1166 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1167 {
1168         PW *pw = *entry;
1169         LIST(PART) **list = user;
1170
1171         *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1172         if (!*list)
1173                 return isl_stat_error;
1174
1175         return isl_stat_ok;
1176 }
1177
1178 /* Return a list containing all the base expressions in "u".
1179  *
1180  * First construct a list of the appropriate size and
1181  * then add all the elements.
1182  */
1183 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1184 {
1185         isl_size n;
1186         LIST(PART) *list;
1187
1188         if (!u)
1189                 return NULL;
1190         n = FN(FN(UNION,n),BASE)(u);
1191         if (n < 0)
1192                 return NULL;
1193         list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1194         if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1195                 return FN(LIST(PART),free)(list);
1196
1197         return list;
1198 }