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 #include "opt_type.h"
  69
  70 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space
  71         OPT_TYPE_PARAM, int size)
  72 {
  73         UNION *u;
  74
  75         space = isl_space_params(space);
  76         if (!space)
  77                 return NULL;
  78
  79         u = isl_calloc_type(space->ctx, UNION);
  80         if (!u)
  81                 goto error;
  82
  83         u->ref = 1;
  84         OPT_SET_TYPE(u->, type);
  85         u->space = space;
  86         if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
  87                 return FN(UNION,free)(u);
  88
  89         return u;
  90 error:
  91         isl_space_free(space);
  92         return NULL;
  93 }
  94
  95 /* Create an empty/zero union without specifying any parameters.
  96  */
  97 __isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM)
  98 {
  99         isl_space *space;
 100
 101         space = isl_space_unit(ctx);
 102         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
 103 }
 104
 105 __isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space
 106         OPT_TYPE_PARAM)
 107 {
 108         return FN(UNION,alloc)(space OPT_TYPE_ARG(NO_LOC), 16);
 109 }
 110
 111 /* This is an alternative name for the function above.
 112  */
 113 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
 114 {
 115         return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
 116 }
 117
 118 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
 119 {
 120         if (!u)
 121                 return NULL;
 122
 123         u->ref++;
 124         return u;
 125 }
 126
 127 /* Do the tuples of "space" correspond to those of the domain of "part"?
 128  * That is, is the domain space of "part" equal to "space", ignoring parameters?
 129  */
 130 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
 131         __isl_keep isl_space *space)
 132 {
 133         return isl_space_has_domain_tuples(space, FN(PART,peek_space)(part));
 134 }
 135
 136 /* Extract the element of "u" living in "space" (ignoring parameters).
 137  *
 138  * Return the ZERO element if "u" does not contain any element
 139  * living in "space".
 140  */
 141 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
 142         __isl_take isl_space *space)
 143 {
 144         struct isl_hash_table_entry *entry;
 145
 146         entry = FN(UNION,find_part_entry)(u, space, 0);
 147         if (!entry)
 148                 goto error;
 149         if (entry == isl_hash_table_entry_none)
 150                 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->));
 151         isl_space_free(space);
 152         return FN(PART,copy)(entry->data);
 153 error:
 154         isl_space_free(space);
 155         return NULL;
 156 }
 157
 158 /* Add "part" to "u".
 159  * If "disjoint" is set, then "u" is not allowed to already have
 160  * a part that is defined over a domain that overlaps with the domain
 161  * of "part".
 162  * Otherwise, compute the union sum of "part" and the part in "u"
 163  * defined on the same space.
 164  */
 165 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
 166         __isl_take PART *part, int disjoint)
 167 {
 168         int empty;
 169         struct isl_hash_table_entry *entry;
 170
 171         if (!part)
 172                 goto error;
 173
 174         empty = FN(PART,IS_ZERO)(part);
 175         if (empty < 0)
 176                 goto error;
 177         if (empty) {
 178                 FN(PART,free)(part);
 179                 return u;
 180         }
 181
 182         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 183         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 184
 185         u = FN(UNION,cow)(u);
 186
 187         if (!u)
 188                 goto error;
 189
 190         if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
 191                 goto error;
 192         entry = FN(UNION,find_part_entry)(u, part->dim, 1);
 193         if (!entry)
 194                 goto error;
 195
 196         if (!entry->data)
 197                 entry->data = part;
 198         else {
 199                 if (disjoint &&
 200                     FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
 201                         goto error;
 202                 entry->data = FN(PART,union_add_)(entry->data,
 203                                                 FN(PART,copy)(part));
 204                 if (!entry->data)
 205                         goto error;
 206                 empty = FN(PART,IS_ZERO)(part);
 207                 if (empty < 0)
 208                         goto error;
 209                 if (empty)
 210                         u = FN(UNION,remove_part_entry)(u, entry);
 211                 FN(PART,free)(part);
 212         }
 213
 214         return u;
 215 error:
 216         FN(PART,free)(part);
 217         FN(UNION,free)(u);
 218         return NULL;
 219 }
 220
 221 /* Add "part" to "u", where "u" is assumed not to already have
 222  * a part that is defined on the same space as "part".
 223  */
 224 __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
 225         __isl_take PART *part)
 226 {
 227         return FN(UNION,add_part_generic)(u, part, 1);
 228 }
 229
 230 /* Allocate a UNION with the same type (if any) and the same size as "u" and
 231  * with space "space".
 232  */
 233 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
 234         __isl_take isl_space *space)
 235 {
 236         if (!u)
 237                 goto error;
 238         return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n);
 239 error:
 240         isl_space_free(space);
 241         return NULL;
 242 }
 243
 244 /* Allocate a UNION with the same space, the same type (if any) and
 245  * the same size as "u".
 246  */
 247 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
 248 {
 249         return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
 250 }
 251
 252 /* Data structure that specifies how isl_union_*_transform
 253  * should modify the base expressions in the union expression.
 254  *
 255  * If "inplace" is set, then the base expression in the input union
 256  * are modified in place.  This means that "fn" should not
 257  * change the meaning of the union or that the union only
 258  * has a single reference.
 259  * If "space" is not NULL, then a new union is created in this space.
 260  * If "filter" is not NULL, then only the base expressions that satisfy "filter"
 261  * are taken into account.
 262  * "filter_user" is passed as the second argument to "filter".
 263  * If "fn" it not NULL, then it is applied to each entry in the input.
 264  * "fn_user" is passed as the second argument to "fn".
 265  */
 266 S(UNION,transform_control) {
 267         int inplace;
 268         isl_space *space;
 269         isl_bool (*filter)(__isl_keep PART *part, void *user);
 270         void *filter_user;
 271         __isl_give PART *(*fn)(__isl_take PART *part, void *user);
 272         void *fn_user;
 273 };
 274
 275 /* Internal data structure for isl_union_*_transform_space.
 276  * "control" specifies how the base expressions should be modified.
 277  * "res" collects the results (if control->inplace is not set).
 278  */
 279 S(UNION,transform_data)
 280 {
 281         S(UNION,transform_control) *control;
 282         UNION *res;
 283 };
 284
 285 /* Apply control->fn to "part" and add the result to data->res or
 286  * place it back into the input union if control->inplace is set.
 287  */
 288 static isl_stat FN(UNION,transform_entry)(void **entry, void *user)
 289 {
 290         S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
 291         S(UNION,transform_control) *control = data->control;
 292         PART *part = *entry;
 293
 294         if (control->filter) {
 295                 isl_bool handle;
 296
 297                 handle = control->filter(part, control->filter_user);
 298                 if (handle < 0)
 299                         return isl_stat_error;
 300                 if (!handle)
 301                         return isl_stat_ok;
 302         }
 303
 304         if (!control->inplace)
 305                 part = FN(PART,copy)(part);
 306         if (control->fn)
 307                 part = control->fn(part, control->fn_user);
 308         if (control->inplace)
 309                 *entry = part;
 310         else
 311                 data->res = FN(FN(UNION,add),BASE)(data->res, part);
 312         if (!part || !data->res)
 313                 return isl_stat_error;
 314
 315         return isl_stat_ok;
 316 }
 317
 318 /* Return a UNION that is obtained by modifying "u" according to "control".
 319  */
 320 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
 321         S(UNION,transform_control) *control)
 322 {
 323         S(UNION,transform_data) data = { control };
 324         isl_space *space;
 325
 326         if (control->inplace) {
 327                 data.res = u;
 328         } else {
 329                 if (control->space)
 330                         space = isl_space_copy(control->space);
 331                 else
 332                         space = FN(UNION,get_space)(u);
 333                 data.res = FN(UNION,alloc_same_size_on_space)(u, space);
 334         }
 335         if (FN(UNION,foreach_inplace)(u, &FN(UNION,transform_entry), &data) < 0)
 336                 data.res = FN(UNION,free)(data.res);
 337         if (!control->inplace)
 338                 FN(UNION,free)(u);
 339         return data.res;
 340 }
 341
 342 /* Return a UNION living in "space" that is otherwise obtained by modifying "u"
 343  * according to "control".
 344  */
 345 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
 346         __isl_take isl_space *space, S(UNION,transform_control) *control)
 347 {
 348         if (!space)
 349                 return FN(UNION,free)(u);
 350         control->space = space;
 351         u = FN(UNION,transform)(u, control);
 352         isl_space_free(space);
 353         return u;
 354 }
 355
 356 /* Update "u" by applying "fn" to each entry.
 357  * This operation is assumed not to change the number of entries nor
 358  * the spaces of the entries.
 359  *
 360  * If there is only one reference to "u", then change "u" inplace.
 361  * Otherwise, create a new UNION from "u" and discard the original.
 362  */
 363 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
 364         __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
 365 {
 366         S(UNION,transform_control) control = { .fn = fn, .fn_user = user };
 367         isl_bool single_ref;
 368
 369         single_ref = FN(UNION,has_single_reference)(u);
 370         if (single_ref < 0)
 371                 return FN(UNION,free)(u);
 372         if (single_ref)
 373                 control.inplace = 1;
 374         return FN(UNION,transform)(u, &control);
 375 }
 376
 377 /* An isl_union_*_transform callback for use in isl_union_*_dup
 378  * that simply returns "part".
 379  */
 380 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
 381 {
 382         return part;
 383 }
 384
 385 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 386 {
 387         S(UNION,transform_control) control = { .fn = &FN(UNION,copy_part) };
 388
 389         u = FN(UNION,copy)(u);
 390         return FN(UNION,transform)(u, &control);
 391 }
 392
 393 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 394 {
 395         if (!u)
 396                 return NULL;
 397
 398         if (u->ref == 1)
 399                 return u;
 400         u->ref--;
 401         return FN(UNION,dup)(u);
 402 }
 403
 404 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 405 {
 406         if (!u)
 407                 return NULL;
 408
 409         if (--u->ref > 0)
 410                 return NULL;
 411
 412         isl_hash_table_foreach(u->space->ctx, &u->table,
 413                                 &FN(UNION,free_u_entry), NULL);
 414         isl_hash_table_clear(&u->table);
 415         isl_space_free(u->space);
 416         free(u);
 417         return NULL;
 418 }
 419
 420 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
 421 {
 422         isl_reordering *exp = user;
 423
 424         exp = isl_reordering_extend_space(isl_reordering_copy(exp),
 425                                     FN(PART,get_domain_space)(part));
 426         return FN(PART,realign_domain)(part, exp);
 427 }
 428
 429 /* Reorder the parameters of "u" according to the given reordering.
 430  */
 431 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
 432         __isl_take isl_reordering *r)
 433 {
 434         S(UNION,transform_control) control = {
 435                 .fn = &FN(UNION,align_entry),
 436                 .fn_user = r,
 437         };
 438         isl_space *space;
 439
 440         if (!u || !r)
 441                 goto error;
 442
 443         space = isl_reordering_get_space(r);
 444         u = FN(UNION,transform_space)(u, space, &control);
 445         isl_reordering_free(r);
 446         return u;
 447 error:
 448         FN(UNION,free)(u);
 449         isl_reordering_free(r);
 450         return NULL;
 451 }
 452
 453 /* Align the parameters of "u" to those of "model".
 454  */
 455 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 456         __isl_take isl_space *model)
 457 {
 458         isl_space *space;
 459         isl_bool equal_params;
 460         isl_reordering *r;
 461
 462         space = FN(UNION,peek_space)(u);
 463         equal_params = isl_space_has_equal_params(space, model);
 464         if (equal_params < 0)
 465                 goto error;
 466         if (equal_params) {
 467                 isl_space_free(model);
 468                 return u;
 469         }
 470
 471         r = isl_parameter_alignment_reordering(space, model);
 472         isl_space_free(model);
 473
 474         return FN(UNION,realign_domain)(u, r);
 475 error:
 476         isl_space_free(model);
 477         FN(UNION,free)(u);
 478         return NULL;
 479 }
 480
 481 /* Add "part" to *u, taking the union sum if "u" already has
 482  * a part defined on the same space as "part".
 483  */
 484 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
 485 {
 486         UNION **u = (UNION **)user;
 487
 488         *u = FN(UNION,add_part_generic)(*u, part, 0);
 489
 490         return isl_stat_ok;
 491 }
 492
 493 /* Compute the sum of "u1" and "u2" on the union of their domains,
 494  * with the actual sum on the shared domain and
 495  * the defined expression on the symmetric difference of the domains.
 496  *
 497  * This is an internal function that is exposed under different
 498  * names depending on whether the base expressions have a zero default
 499  * value.
 500  * If they do, then this function is called "add".
 501  * Otherwise, it is called "union_add".
 502  */
 503 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
 504         __isl_take UNION *u2)
 505 {
 506         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 507         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 508
 509         u1 = FN(UNION,cow)(u1);
 510
 511         if (!u1 || !u2)
 512                 goto error;
 513
 514         if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
 515                 goto error;
 516
 517         FN(UNION,free)(u2);
 518
 519         return u1;
 520 error:
 521         FN(UNION,free)(u1);
 522         FN(UNION,free)(u2);
 523         return NULL;
 524 }
 525
 526 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
 527 {
 528         isl_space *space;
 529         UNION *u;
 530
 531         if (!part)
 532                 return NULL;
 533
 534         space = FN(PART,get_space)(part);
 535         space = isl_space_drop_dims(space, isl_dim_in, 0,
 536                                         isl_space_dim(space, isl_dim_in));
 537         space = isl_space_drop_dims(space, isl_dim_out, 0,
 538                                         isl_space_dim(space, isl_dim_out));
 539         u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
 540         u = FN(FN(UNION,add),BASE)(u, part);
 541
 542         return u;
 543 }
 544
 545 /* This function performs the same operation as isl_union_pw_*_from_pw_*,
 546  * but is considered as a function on an isl_pw_* when exported.
 547  */
 548 __isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part)
 549 {
 550         return FN(FN(UNION,from),BASE)(part);
 551 }
 552
 553 S(UNION,match_bin_data) {
 554         UNION *u2;
 555         UNION *res;
 556         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 557 };
 558
 559 /* Check if data->u2 has an element living in the same space as "part".
 560  * If so, call data->fn on the two elements and add the result to
 561  * data->res.
 562  */
 563 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
 564 {
 565         S(UNION,match_bin_data) *data = user;
 566         struct isl_hash_table_entry *entry2;
 567         isl_space *space;
 568         PART *part2;
 569
 570         space = FN(PART,get_space)(part);
 571         entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
 572         isl_space_free(space);
 573         if (!entry2)
 574                 goto error;
 575         if (entry2 == isl_hash_table_entry_none) {
 576                 FN(PART,free)(part);
 577                 return isl_stat_ok;
 578         }
 579
 580         part2 = entry2->data;
 581         if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
 582                                         part2->dim, isl_dim_out))
 583                 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
 584                         "entries should have the same range space",
 585                         goto error);
 586
 587         part = data->fn(part, FN(PART, copy)(entry2->data));
 588
 589         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 590         if (!data->res)
 591                 return isl_stat_error;
 592
 593         return isl_stat_ok;
 594 error:
 595         FN(PART,free)(part);
 596         return isl_stat_error;
 597 }
 598
 599 /* This function is currently only used from isl_polynomial.c
 600  * and not from isl_fold.c.
 601  */
 602 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 603         __isl_take UNION *u2,
 604         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 605         __attribute__ ((unused));
 606 /* For each pair of elements in "u1" and "u2" living in the same space,
 607  * call "fn" and collect the results.
 608  */
 609 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
 610         __isl_take UNION *u2,
 611         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 612 {
 613         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 614
 615         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 616         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 617
 618         if (!u1 || !u2)
 619                 goto error;
 620
 621         data.u2 = u2;
 622         data.res = FN(UNION,alloc_same_size)(u1);
 623         if (FN(FN(UNION,foreach),BASE)(u1,
 624                                     &FN(UNION,match_bin_entry), &data) < 0)
 625                 goto error;
 626
 627         FN(UNION,free)(u1);
 628         FN(UNION,free)(u2);
 629         return data.res;
 630 error:
 631         FN(UNION,free)(u1);
 632         FN(UNION,free)(u2);
 633         FN(UNION,free)(data.res);
 634         return NULL;
 635 }
 636
 637 /* Compute the sum of "u1" and "u2".
 638  *
 639  * If the base expressions have a default zero value, then the sum
 640  * is computed on the union of the domains of "u1" and "u2".
 641  * Otherwise, it is computed on their shared domains.
 642  */
 643 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 644 {
 645 #if DEFAULT_IS_ZERO
 646         return FN(UNION,union_add_)(u1, u2);
 647 #else
 648         return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
 649 #endif
 650 }
 651
 652 #ifndef NO_SUB
 653 /* Subtract "u2" from "u1" and return the result.
 654  */
 655 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 656 {
 657         return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
 658 }
 659 #endif
 660
 661 S(UNION,any_set_data) {
 662         isl_set *set;
 663         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 664 };
 665
 666 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
 667         void *user)
 668 {
 669         S(UNION,any_set_data) *data = user;
 670
 671         return data->fn(part, isl_set_copy(data->set));
 672 }
 673
 674 /* Update each element of "u" by calling "fn" on the element and "set".
 675  */
 676 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
 677         __isl_take isl_set *set,
 678         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 679 {
 680         S(UNION,any_set_data) data = { NULL, fn };
 681         S(UNION,transform_control) control = {
 682                 .fn = &FN(UNION,any_set_entry),
 683                 .fn_user = &data,
 684         };
 685
 686         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 687         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 688
 689         if (!u || !set)
 690                 goto error;
 691
 692         data.set = set;
 693         u = FN(UNION,transform)(u, &control);
 694         isl_set_free(set);
 695         return u;
 696 error:
 697         FN(UNION,free)(u);
 698         isl_set_free(set);
 699         return NULL;
 700 }
 701
 702 /* Intersect the domain of "u" with the parameter domain "context".
 703  */
 704 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 705         __isl_take isl_set *set)
 706 {
 707         return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
 708 }
 709
 710 /* Compute the gist of the domain of "u" with respect to
 711  * the parameter domain "context".
 712  */
 713 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 714         __isl_take isl_set *set)
 715 {
 716         return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
 717 }
 718
 719 /* Data structure that specifies how isl_union_*_match_domain_op
 720  * should combine its arguments.
 721  *
 722  * If "filter" is not NULL, then only parts that pass the given
 723  * filter are considered for matching.
 724  * "fn" is applied to each part in the union and each corresponding
 725  * set in the union set, i.e., such that the set lives in the same space
 726  * as the domain of the part.
 727  * If "match_space" is not NULL, then the set extracted from the union set
 728  * does not live in the same space as the domain of the part,
 729  * but rather in the space that results from calling "match_space"
 730  * on this domain space.
 731  */
 732 S(UNION,match_domain_control) {
 733         isl_bool (*filter)(__isl_keep PART *part);
 734         __isl_give isl_space *(*match_space)(__isl_take isl_space *space);
 735         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 736 };
 737
 738 S(UNION,match_domain_data) {
 739         isl_union_set *uset;
 740         UNION *res;
 741         S(UNION,match_domain_control) *control;
 742 };
 743
 744 /* Find the set in data->uset that lives in the same space as the domain
 745  * of "part" (ignoring parameters), apply data->fn to *entry and this set
 746  * (if any), and add the result to data->res.
 747  */
 748 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
 749 {
 750         S(UNION,match_domain_data) *data = user;
 751         struct isl_hash_table_entry *entry2;
 752         isl_space *space;
 753
 754         if (data->control->filter) {
 755                 isl_bool pass = data->control->filter(part);
 756                 if (pass < 0 || !pass) {
 757                         FN(PART,free)(part);
 758                         return pass < 0 ? isl_stat_error : isl_stat_ok;
 759                 }
 760         }
 761
 762         space = FN(PART,get_domain_space)(part);
 763         if (data->control->match_space)
 764                 space = data->control->match_space(space);
 765         entry2 = isl_union_set_find_entry(data->uset, space, 0);
 766         isl_space_free(space);
 767         if (!entry2 || entry2 == isl_hash_table_entry_none) {
 768                 FN(PART,free)(part);
 769                 return isl_stat_non_null(entry2);
 770         }
 771
 772         part = data->control->fn(part, isl_set_copy(entry2->data));
 773
 774         data->res = FN(FN(UNION,add),BASE)(data->res, part);
 775         if (!data->res)
 776                 return isl_stat_error;
 777
 778         return isl_stat_ok;
 779 }
 780
 781 /* Combine "u" and "uset" according to "control"
 782  * and collect the results.
 783  */
 784 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
 785         __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control)
 786 {
 787         S(UNION,match_domain_data) data = { NULL, NULL, control };
 788
 789         if (!u || !uset)
 790                 goto error;
 791
 792         data.uset = uset;
 793         data.res = FN(UNION,alloc_same_size)(u);
 794         if (FN(FN(UNION,foreach),BASE)(u,
 795                                    &FN(UNION,match_domain_entry), &data) < 0)
 796                 goto error;
 797
 798         FN(UNION,free)(u);
 799         isl_union_set_free(uset);
 800         return data.res;
 801 error:
 802         FN(UNION,free)(u);
 803         isl_union_set_free(uset);
 804         FN(UNION,free)(data.res);
 805         return NULL;
 806 }
 807
 808 /* Intersect the domain of "u" with "uset".
 809  * If "uset" is a parameters domain, then intersect the parameter
 810  * domain of "u" with this set.
 811  */
 812 __isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u,
 813         __isl_take isl_union_set *uset)
 814 {
 815         S(UNION,match_domain_control) control = {
 816                 .fn = &FN(PW,intersect_domain),
 817         };
 818
 819         if (isl_union_set_is_params(uset))
 820                 return FN(UNION,intersect_params)(u,
 821                                                 isl_set_from_union_set(uset));
 822         return FN(UNION,match_domain_op)(u, uset, &control);
 823 }
 824
 825 /* This is an alternative name for the function above.
 826  */
 827 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 828         __isl_take isl_union_set *uset)
 829 {
 830         return FN(UNION,intersect_domain_union_set)(u, uset);
 831 }
 832
 833 /* Return true if this part should be kept.
 834  *
 835  * In particular, it should be kept if its domain space
 836  * corresponds to "space".
 837  */
 838 static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user)
 839 {
 840         isl_space *space = user;
 841
 842         return FN(PW,has_domain_space_tuples)(part, space);
 843 }
 844
 845 /* Remove any not element in "space" from the domain of "u".
 846  *
 847  * In particular, select any part of the function defined
 848  * on this domain space.
 849  */
 850 __isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u,
 851         __isl_take isl_space *space)
 852 {
 853         S(UNION,transform_control) control = {
 854                 .filter = &FN(UNION,select_entry),
 855                 .filter_user = space,
 856         };
 857
 858         u = FN(UNION,transform)(u, &control);
 859         isl_space_free(space);
 860         return u;
 861 }
 862
 863 /* Is the domain of "pw" a wrapped relation?
 864  */
 865 static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw)
 866 {
 867         return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw));
 868 }
 869
 870 /* Intersect the domain of the wrapped relation inside the domain of "u"
 871  * with "uset".
 872  */
 873 __isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u,
 874         __isl_take isl_union_set *uset)
 875 {
 876         S(UNION,match_domain_control) control = {
 877                 .filter = &FN(PART,domain_is_wrapping),
 878                 .match_space = &isl_space_factor_domain,
 879                 .fn = &FN(PW,intersect_domain_wrapped_domain),
 880         };
 881
 882         return FN(UNION,match_domain_op)(u, uset, &control);
 883 }
 884
 885 /* Intersect the range of the wrapped relation inside the domain of "u"
 886  * with "uset".
 887  */
 888 __isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u,
 889         __isl_take isl_union_set *uset)
 890 {
 891         S(UNION,match_domain_control) control = {
 892                 .filter = &FN(PART,domain_is_wrapping),
 893                 .match_space = &isl_space_factor_range,
 894                 .fn = &FN(PW,intersect_domain_wrapped_range),
 895         };
 896
 897         return FN(UNION,match_domain_op)(u, uset, &control);
 898 }
 899
 900 /* Take the set (which may be empty) in data->uset that lives
 901  * in the same space as the domain of "pw", subtract it from the domain
 902  * of "part" and return the result.
 903  */
 904 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
 905         void *user)
 906 {
 907         isl_union_set *uset = user;
 908         isl_space *space;
 909         isl_set *set;
 910
 911         space = FN(PART,get_domain_space)(part);
 912         set = isl_union_set_extract_set(uset, space);
 913         return FN(PART,subtract_domain)(part, set);
 914 }
 915
 916 /* Subtract "uset" from the domain of "u".
 917  */
 918 __isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u,
 919         __isl_take isl_union_set *uset)
 920 {
 921         S(UNION,transform_control) control = {
 922                 .fn = &FN(UNION,subtract_domain_entry),
 923                 .fn_user = uset,
 924         };
 925
 926         u = FN(UNION,transform)(u, &control);
 927         isl_union_set_free(uset);
 928         return u;
 929 }
 930
 931 /* This is an alternative name for the function above.
 932  */
 933 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
 934         __isl_take isl_union_set *uset)
 935 {
 936         return FN(UNION,subtract_domain_union_set)(u, uset);
 937 }
 938
 939 /* Return true if this part should be kept.
 940  *
 941  * In particular, it should be kept if its domain space
 942  * does not correspond to "space".
 943  */
 944 static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user)
 945 {
 946         isl_space *space = user;
 947
 948         return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space));
 949 }
 950
 951 /* Remove any element in "space" from the domain of "u".
 952  *
 953  * In particular, filter out any part of the function defined
 954  * on this domain space.
 955  */
 956 __isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u,
 957         __isl_take isl_space *space)
 958 {
 959         S(UNION,transform_control) control = {
 960                 .filter = &FN(UNION,filter_out_entry),
 961                 .filter_user = space,
 962         };
 963
 964         u = FN(UNION,transform)(u, &control);
 965         isl_space_free(space);
 966         return u;
 967 }
 968
 969 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 970         __isl_take isl_union_set *uset)
 971 {
 972         S(UNION,match_domain_control) control = {
 973                 .fn = &FN(PW,gist),
 974         };
 975
 976         if (isl_union_set_is_params(uset))
 977                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 978         return FN(UNION,match_domain_op)(u, uset, &control);
 979 }
 980
 981 /* Coalesce an entry in a UNION.  Coalescing is performed in-place.
 982  * Since the UNION may have several references, the entry is only
 983  * replaced if the coalescing is successful.
 984  */
 985 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
 986 {
 987         PART **part_p = (PART **) entry;
 988         PART *part;
 989
 990         part = FN(PART,copy)(*part_p);
 991         part = FN(PW,coalesce)(part);
 992         if (!part)
 993                 return isl_stat_error;
 994         FN(PART,free)(*part_p);
 995         *part_p = part;
 996
 997         return isl_stat_ok;
 998 }
 999
1000 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
1001 {
1002         if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
1003                 goto error;
1004
1005         return u;
1006 error:
1007         FN(UNION,free)(u);
1008         return NULL;
1009 }
1010
1011 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
1012 {
1013         isl_union_set **uset = (isl_union_set **)user;
1014
1015         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
1016
1017         return isl_stat_ok;
1018 }
1019
1020 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
1021 {
1022         isl_union_set *uset;
1023
1024         uset = isl_union_set_empty(FN(UNION,get_space)(u));
1025         if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
1026                 goto error;
1027
1028         FN(UNION,free)(u);
1029
1030         return uset;
1031 error:
1032         isl_union_set_free(uset);
1033         FN(UNION,free)(u);
1034         return NULL;
1035 }
1036
1037 #ifdef HAS_TYPE
1038 /* Negate the type of "u".
1039  */
1040 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1041 {
1042         u = FN(UNION,cow)(u);
1043         if (!u)
1044                 return NULL;
1045         u->type = isl_fold_type_negate(u->type);
1046         return u;
1047 }
1048 #else
1049 /* Negate the type of "u".
1050  * Since "u" does not have a type, do nothing.
1051  */
1052 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1053 {
1054         return u;
1055 }
1056 #endif
1057
1058 /* Multiply "part" by the isl_val "user" and return the result.
1059  */
1060 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1061         void *user)
1062 {
1063         isl_val *v = user;
1064
1065         return FN(PART,scale_val)(part, isl_val_copy(v));
1066 }
1067
1068 /* Multiply "u" by "v" and return the result.
1069  */
1070 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1071         __isl_take isl_val *v)
1072 {
1073         if (!u || !v)
1074                 goto error;
1075         if (isl_val_is_one(v)) {
1076                 isl_val_free(v);
1077                 return u;
1078         }
1079
1080         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1081                 UNION *zero;
1082                 isl_space *space = FN(UNION,get_space)(u);
1083                 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
1084                 FN(UNION,free)(u);
1085                 isl_val_free(v);
1086                 return zero;
1087         }
1088
1089         if (!isl_val_is_rat(v))
1090                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1091                         "expecting rational factor", goto error);
1092
1093         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1094         if (isl_val_is_neg(v))
1095                 u = FN(UNION,negate_type)(u);
1096
1097         isl_val_free(v);
1098         return u;
1099 error:
1100         isl_val_free(v);
1101         FN(UNION,free)(u);
1102         return NULL;
1103 }
1104
1105 /* Divide "part" by the isl_val "user" and return the result.
1106  */
1107 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
1108         void *user)
1109 {
1110         isl_val *v = user;
1111
1112         return FN(PART,scale_down_val)(part, isl_val_copy(v));
1113 }
1114
1115 /* Divide "u" by "v" and return the result.
1116  */
1117 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1118         __isl_take isl_val *v)
1119 {
1120         if (!u || !v)
1121                 goto error;
1122         if (isl_val_is_one(v)) {
1123                 isl_val_free(v);
1124                 return u;
1125         }
1126
1127         if (!isl_val_is_rat(v))
1128                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1129                         "expecting rational factor", goto error);
1130         if (isl_val_is_zero(v))
1131                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1132                         "cannot scale down by zero", goto error);
1133
1134         u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
1135         if (isl_val_is_neg(v))
1136                 u = FN(UNION,negate_type)(u);
1137
1138         isl_val_free(v);
1139         return u;
1140 error:
1141         isl_val_free(v);
1142         FN(UNION,free)(u);
1143         return NULL;
1144 }
1145
1146 /* Internal data structure for isl_union_*_every_*.
1147  *
1148  * "test" is the user-specified callback function.
1149  * "user" is the user-specified callback function argument.
1150  *
1151  * "res" is the final result, initialized to isl_bool_true.
1152  */
1153 S(UNION,every_data) {
1154         isl_bool (*test)(__isl_keep PW *pw, void *user);
1155         void *user;
1156
1157         isl_bool res;
1158 };
1159
1160 /* Call data->test on the piecewise expression at *entry,
1161  * updating the result in data->res.
1162  * Abort if this result is no longer isl_bool_true.
1163  */
1164 static isl_stat FN(UNION,every_entry)(void **entry, void *user)
1165 {
1166         S(UNION,every_data) *data = user;
1167         PW *pw = *entry;
1168
1169         data->res = data->test(pw, data->user);
1170         if (data->res < 0 || !data->res)
1171                 return isl_stat_error;
1172
1173         return isl_stat_ok;
1174 }
1175
1176 /* Does "test" succeed on every piecewise expression in "u"?
1177  */
1178 isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u,
1179         isl_bool (*test)(__isl_keep PW *pw, void *user), void *user)
1180 {
1181         S(UNION,every_data) data = { test, user };
1182
1183         data.res = isl_bool_true;
1184         if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 &&
1185             data.res == isl_bool_true)
1186                 return isl_bool_error;
1187
1188         return data.res;
1189 }
1190
1191 S(UNION,plain_is_equal_data)
1192 {
1193         UNION *u2;
1194 };
1195
1196 static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user)
1197 {
1198         S(UNION,plain_is_equal_data) *data = user;
1199         struct isl_hash_table_entry *entry;
1200
1201         entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1202         if (!entry)
1203                 return isl_bool_error;
1204         if (entry == isl_hash_table_entry_none)
1205                 return isl_bool_false;
1206
1207         return FN(PW,plain_is_equal)(pw, entry->data);
1208 }
1209
1210 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1211 {
1212         S(UNION,plain_is_equal_data) data;
1213         isl_size n1, n2;
1214         isl_bool is_equal;
1215
1216         if (!u1 || !u2)
1217                 return isl_bool_error;
1218         if (u1 == u2)
1219                 return isl_bool_true;
1220         if (u1->table.n != u2->table.n)
1221                 return isl_bool_false;
1222         n1 = FN(FN(UNION,n),BASE)(u1);
1223         n2 = FN(FN(UNION,n),BASE)(u2);
1224         if (n1 < 0 || n2 < 0)
1225                 return isl_bool_error;
1226         if (n1 != n2)
1227                 return isl_bool_false;
1228
1229         u1 = FN(UNION,copy)(u1);
1230         u2 = FN(UNION,copy)(u2);
1231         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1232         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1233         if (!u1 || !u2)
1234                 goto error;
1235
1236         data.u2 = u2;
1237         is_equal = FN(FN(UNION,every),BASE)(u1,
1238                                           &FN(UNION,plain_is_equal_el), &data);
1239
1240         FN(UNION,free)(u1);
1241         FN(UNION,free)(u2);
1242
1243         return is_equal;
1244 error:
1245         FN(UNION,free)(u1);
1246         FN(UNION,free)(u2);
1247         return isl_bool_error;
1248 }
1249
1250 /* An isl_union_*_every_* callback that checks whether "pw"
1251  * does not involve any NaNs.
1252  */
1253 static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user)
1254 {
1255         return isl_bool_not(FN(PW,involves_nan)(pw));
1256 }
1257
1258 /* Does "u" involve any NaNs?
1259  */
1260 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1261 {
1262         isl_bool no_nan;
1263
1264         no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL);
1265
1266         return isl_bool_not(no_nan);
1267 }
1268
1269 /* Internal data structure for isl_union_*_drop_dims.
1270  * type, first and n are passed to isl_*_drop_dims.
1271  */
1272 S(UNION,drop_dims_data) {
1273         enum isl_dim_type type;
1274         unsigned first;
1275         unsigned n;
1276 };
1277
1278 /* Drop the parameters specified by "data" from "part" and return the result.
1279  */
1280 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1281         void *user)
1282 {
1283         S(UNION,drop_dims_data) *data = user;
1284
1285         return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1286 }
1287
1288 /* Drop the specified parameters from "u".
1289  * That is, type is required to be isl_dim_param.
1290  */
1291 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1292         enum isl_dim_type type, unsigned first, unsigned n)
1293 {
1294         isl_space *space;
1295         S(UNION,drop_dims_data) data = { type, first, n };
1296         S(UNION,transform_control) control = {
1297                 .fn = &FN(UNION,drop_dims_entry),
1298                 .fn_user = &data,
1299         };
1300
1301         if (!u)
1302                 return NULL;
1303
1304         if (type != isl_dim_param)
1305                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1306                         "can only project out parameters",
1307                         return FN(UNION,free)(u));
1308
1309         space = FN(UNION,get_space)(u);
1310         space = isl_space_drop_dims(space, type, first, n);
1311         return FN(UNION,transform_space)(u, space, &control);
1312 }
1313
1314 /* Internal data structure for isl_union_*_set_dim_name.
1315  * pos is the position of the parameter that needs to be renamed.
1316  * s is the new name.
1317  */
1318 S(UNION,set_dim_name_data) {
1319         unsigned pos;
1320         const char *s;
1321 };
1322
1323 /* Change the name of the parameter at position data->pos of "part" to data->s
1324  * and return the result.
1325  */
1326 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1327         void *user)
1328 {
1329         S(UNION,set_dim_name_data) *data = user;
1330
1331         return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1332 }
1333
1334 /* Change the name of the parameter at position "pos" to "s".
1335  * That is, type is required to be isl_dim_param.
1336  */
1337 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1338         enum isl_dim_type type, unsigned pos, const char *s)
1339 {
1340         S(UNION,set_dim_name_data) data = { pos, s };
1341         S(UNION,transform_control) control = {
1342                 .fn = &FN(UNION,set_dim_name_entry),
1343                 .fn_user = &data,
1344         };
1345         isl_space *space;
1346
1347         if (!u)
1348                 return NULL;
1349
1350         if (type != isl_dim_param)
1351                 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1352                         "can only set parameter names",
1353                         return FN(UNION,free)(u));
1354
1355         space = FN(UNION,get_space)(u);
1356         space = isl_space_set_dim_name(space, type, pos, s);
1357         return FN(UNION,transform_space)(u, space, &control);
1358 }
1359
1360 /* Reset the user pointer on all identifiers of parameters and tuples
1361  * of the space of "part" and return the result.
1362  */
1363 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1364         void *user)
1365 {
1366         return FN(PART,reset_user)(part);
1367 }
1368
1369 /* Reset the user pointer on all identifiers of parameters and tuples
1370  * of the spaces of "u".
1371  */
1372 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1373 {
1374         S(UNION,transform_control) control = {
1375                 .fn = &FN(UNION,reset_user_entry),
1376         };
1377         isl_space *space;
1378
1379         space = FN(UNION,get_space)(u);
1380         space = isl_space_reset_user(space);
1381         return FN(UNION,transform_space)(u, space, &control);
1382 }
1383
1384 /* Add the base expression held by "entry" to "list".
1385  */
1386 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1387 {
1388         PW *pw = *entry;
1389         LIST(PART) **list = user;
1390
1391         *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1392         if (!*list)
1393                 return isl_stat_error;
1394
1395         return isl_stat_ok;
1396 }
1397
1398 /* Return a list containing all the base expressions in "u".
1399  *
1400  * First construct a list of the appropriate size and
1401  * then add all the elements.
1402  */
1403 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1404 {
1405         isl_size n;
1406         LIST(PART) *list;
1407
1408         if (!u)
1409                 return NULL;
1410         n = FN(FN(UNION,n),BASE)(u);
1411         if (n < 0)
1412                 return NULL;
1413         list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1414         if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1415                 return FN(LIST(PART),free)(list);
1416
1417         return list;
1418 }