isl_union_templ.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT 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 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  14 #define S(TYPE,NAME) xS(TYPE,NAME)
  15
  16 struct UNION {
  17         int ref;
  18 #ifdef HAS_TYPE
  19         enum isl_fold type;
  20 #endif
  21         isl_space *space;
  22
  23         struct isl_hash_table   table;
  24 };
  25
  26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
  27
  28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
  29 {
  30         return u ? u->space->ctx : NULL;
  31 }
  32
  33 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
  34 {
  35         if (!u)
  36                 return NULL;
  37         return isl_space_copy(u->space);
  38 }
  39
  40 #ifdef HAS_TYPE
  41 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
  42         enum isl_fold type, int size)
  43 #else
  44 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
  45 #endif
  46 {
  47         UNION *u;
  48
  49         dim = isl_space_params(dim);
  50         if (!dim)
  51                 return NULL;
  52
  53         u = isl_calloc_type(dim->ctx, UNION);
  54         if (!u)
  55                 goto error;
  56
  57         u->ref = 1;
  58 #ifdef HAS_TYPE
  59         u->type = type;
  60 #endif
  61         u->space = dim;
  62         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
  63                 return FN(UNION,free)(u);
  64
  65         return u;
  66 error:
  67         isl_space_free(dim);
  68         return NULL;
  69 }
  70
  71 #ifdef HAS_TYPE
  72 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
  73 {
  74         return FN(UNION,alloc)(dim, type, 16);
  75 }
  76 #else
  77 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
  78 {
  79         return FN(UNION,alloc)(dim, 16);
  80 }
  81 #endif
  82
  83 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
  84 {
  85         if (!u)
  86                 return NULL;
  87
  88         u->ref++;
  89         return u;
  90 }
  91
  92 S(UNION,foreach_data)
  93 {
  94         int (*fn)(__isl_take PART *part, void *user);
  95         void *user;
  96 };
  97
  98 static int call_on_copy(void **entry, void *user)
  99 {
 100         PART *part = *entry;
 101         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
 102
 103         return data->fn(FN(PART,copy)(part), data->user);
 104 }
 105
 106 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
 107         int (*fn)(__isl_take PART *part, void *user), void *user)
 108 {
 109         S(UNION,foreach_data) data = { fn, user };
 110
 111         if (!u)
 112                 return -1;
 113
 114         return isl_hash_table_foreach(u->space->ctx, &u->table,
 115                                       &call_on_copy, &data);
 116 }
 117
 118 /* Is the space of "entry" equal to "space"?
 119  */
 120 static int has_space(const void *entry, const void *val)
 121 {
 122         PART *part = (PART *)entry;
 123         isl_space *space = (isl_space *) val;
 124
 125         return isl_space_is_equal(part->dim, space);
 126 }
 127
 128 /* This function is not currently used by isl_aff.c.
 129  */
 130 static int has_domain_space(const void *entry, const void *val)
 131         __attribute__ ((unused));
 132
 133 /* Is the domain space of "entry" equal to "space"?
 134  */
 135 static int has_domain_space(const void *entry, const void *val)
 136 {
 137         PART *part = (PART *)entry;
 138         isl_space *space = (isl_space *) val;
 139
 140         if (isl_space_is_params(space))
 141                 return isl_space_is_set(part->dim);
 142
 143         return isl_space_tuple_is_equal(part->dim, isl_dim_in,
 144                                         space, isl_dim_set);
 145 }
 146
 147 /* Is the domain space of "entry" equal to the domain of "space"?
 148  */
 149 static int has_same_domain_space(const void *entry, const void *val)
 150 {
 151         PART *part = (PART *)entry;
 152         isl_space *space = (isl_space *) val;
 153
 154         if (isl_space_is_set(space))
 155                 return isl_space_is_set(part->dim);
 156
 157         return isl_space_tuple_is_equal(part->dim, isl_dim_in,
 158                                         space, isl_dim_in);
 159 }
 160
 161 /* Extract the element of "u" living in "space" (ignoring parameters).
 162  *
 163  * Return the ZERO element if "u" does not contain any element
 164  * living in "space".
 165  */
 166 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
 167         __isl_take isl_space *space)
 168 {
 169         uint32_t hash;
 170         struct isl_hash_table_entry *entry;
 171
 172         if (!u || !space)
 173                 goto error;
 174         if (!isl_space_match(u->space, isl_dim_param, space, isl_dim_param)) {
 175                 space = isl_space_drop_dims(space, isl_dim_param,
 176                                         0, isl_space_dim(space, isl_dim_param));
 177                 space = isl_space_align_params(space,
 178                                         FN(UNION,get_space)(u));
 179                 if (!space)
 180                         goto error;
 181         }
 182
 183         hash = isl_space_get_hash(space);
 184         entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
 185                                     &has_space, space, 0);
 186         if (!entry)
 187 #ifdef HAS_TYPE
 188                 return FN(PART,ZERO)(space, u->type);
 189 #else
 190                 return FN(PART,ZERO)(space);
 191 #endif
 192         isl_space_free(space);
 193         return FN(PART,copy)(entry->data);
 194 error:
 195         isl_space_free(space);
 196         return NULL;
 197 }
 198
 199 /* Add "part" to "u".
 200  * If "disjoint" is set, then "u" is not allowed to already have
 201  * a part that is defined on the same space as "part".
 202  * Otherwise, compute the union sum of "part" and the part in "u"
 203  * defined on the same space.
 204  */
 205 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
 206         __isl_take PART *part, int disjoint)
 207 {
 208         int empty;
 209         uint32_t hash;
 210         struct isl_hash_table_entry *entry;
 211
 212         if (!part)
 213                 goto error;
 214
 215         empty = FN(PART,IS_ZERO)(part);
 216         if (empty < 0)
 217                 goto error;
 218         if (empty) {
 219                 FN(PART,free)(part);
 220                 return u;
 221         }
 222
 223         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 224         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 225
 226         u = FN(UNION,cow)(u);
 227
 228         if (!u)
 229                 goto error;
 230
 231         hash = isl_space_get_hash(part->dim);
 232         entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
 233                                     &has_same_domain_space, part->dim, 1);
 234         if (!entry)
 235                 goto error;
 236
 237         if (!entry->data)
 238                 entry->data = part;
 239         else {
 240                 PART *entry_part = entry->data;
 241                 if (disjoint)
 242                         isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
 243                                 "additional part should live on separate "
 244                                 "space", goto error);
 245                 if (!isl_space_tuple_is_equal(entry_part->dim, isl_dim_out,
 246                                                 part->dim, isl_dim_out))
 247                         isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
 248                                 "union expression can only contain a single "
 249                                 "expression over a given domain", goto error);
 250                 entry->data = FN(PART,union_add_)(entry->data,
 251                                                 FN(PART,copy)(part));
 252                 if (!entry->data)
 253                         goto error;
 254                 empty = FN(PART,IS_ZERO)(part);
 255                 if (empty < 0)
 256                         goto error;
 257                 if (empty) {
 258                         FN(PART,free)(entry->data);
 259                         isl_hash_table_remove(u->space->ctx, &u->table, entry);
 260                 }
 261                 FN(PART,free)(part);
 262         }
 263
 264         return u;
 265 error:
 266         FN(PART,free)(part);
 267         FN(UNION,free)(u);
 268         return NULL;
 269 }
 270
 271 /* Add "part" to "u", where "u" is assumed not to already have
 272  * a part that is defined on the same space as "part".
 273  */
 274 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 275         __isl_take PART *part)
 276 {
 277         return FN(UNION,add_part_generic)(u, part, 1);
 278 }
 279
 280 static int add_part(__isl_take PART *part, void *user)
 281 {
 282         UNION **u = (UNION **)user;
 283
 284         *u = FN(FN(UNION,add),PARTS)(*u, part);
 285
 286         return 0;
 287 }
 288
 289 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 290 {
 291         UNION *dup;
 292
 293         if (!u)
 294                 return NULL;
 295
 296 #ifdef HAS_TYPE
 297         dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type);
 298 #else
 299         dup = FN(UNION,ZERO)(isl_space_copy(u->space));
 300 #endif
 301         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 302                 goto error;
 303         return dup;
 304 error:
 305         FN(UNION,free)(dup);
 306         return NULL;
 307 }
 308
 309 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 310 {
 311         if (!u)
 312                 return NULL;
 313
 314         if (u->ref == 1)
 315                 return u;
 316         u->ref--;
 317         return FN(UNION,dup)(u);
 318 }
 319
 320 static int free_u_entry(void **entry, void *user)
 321 {
 322         PART *part = *entry;
 323         FN(PART,free)(part);
 324         return 0;
 325 }
 326
 327 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 328 {
 329         if (!u)
 330                 return NULL;
 331
 332         if (--u->ref > 0)
 333                 return NULL;
 334
 335         isl_hash_table_foreach(u->space->ctx, &u->table, &free_u_entry, NULL);
 336         isl_hash_table_clear(&u->table);
 337         isl_space_free(u->space);
 338         free(u);
 339         return NULL;
 340 }
 341
 342 S(UNION,align) {
 343         isl_reordering *exp;
 344         UNION *res;
 345 };
 346
 347 #ifdef ALIGN_DOMAIN
 348 static int align_entry(__isl_take PART *part, void *user)
 349 {
 350         isl_reordering *exp;
 351         S(UNION,align) *data = user;
 352
 353         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 354                                     FN(PART,get_domain_space)(part));
 355
 356         data->res = FN(FN(UNION,add),PARTS)(data->res,
 357                                             FN(PART,realign_domain)(part, exp));
 358
 359         return 0;
 360 }
 361 #else
 362 static int align_entry(__isl_take PART *part, void *user)
 363 {
 364         isl_reordering *exp;
 365         S(UNION,align) *data = user;
 366
 367         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 368                                     FN(PART,get_space)(part));
 369
 370         data->res = FN(FN(UNION,add),PARTS)(data->res,
 371                                             FN(PART,realign)(part, exp));
 372
 373         return 0;
 374 }
 375 #endif
 376
 377 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 378         __isl_take isl_space *model)
 379 {
 380         S(UNION,align) data = { NULL, NULL };
 381
 382         if (!u || !model)
 383                 goto error;
 384
 385         if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
 386                 isl_space_free(model);
 387                 return u;
 388         }
 389
 390         model = isl_space_params(model);
 391         data.exp = isl_parameter_alignment_reordering(u->space, model);
 392         if (!data.exp)
 393                 goto error;
 394
 395 #ifdef HAS_TYPE
 396         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
 397                                                 u->type, u->table.n);
 398 #else
 399         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
 400 #endif
 401         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
 402                 goto error;
 403
 404         isl_reordering_free(data.exp);
 405         FN(UNION,free)(u);
 406         isl_space_free(model);
 407         return data.res;
 408 error:
 409         isl_reordering_free(data.exp);
 410         FN(UNION,free)(u);
 411         FN(UNION,free)(data.res);
 412         isl_space_free(model);
 413         return NULL;
 414 }
 415
 416 /* Add "part" to *u, taking the union sum if "u" already has
 417  * a part defined on the same space as "part".
 418  */
 419 static int union_add_part(__isl_take PART *part, void *user)
 420 {
 421         UNION **u = (UNION **)user;
 422
 423         *u = FN(UNION,add_part_generic)(*u, part, 0);
 424
 425         return 0;
 426 }
 427
 428 /* Compute the sum of "u1" and "u2" on the union of their domains,
 429  * with the actual sum on the shared domain and
 430  * the defined expression on the symmetric difference of the domains.
 431  *
 432  * This is an internal function that is exposed under different
 433  * names depending on whether the base expressions have a zero default
 434  * value.
 435  * If they do, then this function is called "add".
 436  * Otherwise, it is called "union_add".
 437  */
 438 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
 439         __isl_take UNION *u2)
 440 {
 441         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 442         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 443
 444         u1 = FN(UNION,cow)(u1);
 445
 446         if (!u1 || !u2)
 447                 goto error;
 448
 449         if (FN(FN(UNION,foreach),PARTS)(u2, &union_add_part, &u1) < 0)
 450                 goto error;
 451
 452         FN(UNION,free)(u2);
 453
 454         return u1;
 455 error:
 456         FN(UNION,free)(u1);
 457         FN(UNION,free)(u2);
 458         return NULL;
 459 }
 460
 461 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 462 {
 463         isl_space *dim;
 464         UNION *u;
 465
 466         if (!part)
 467                 return NULL;
 468
 469         dim = FN(PART,get_space)(part);
 470         dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
 471         dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
 472 #ifdef HAS_TYPE
 473         u = FN(UNION,ZERO)(dim, part->type);
 474 #else
 475         u = FN(UNION,ZERO)(dim);
 476 #endif
 477         u = FN(FN(UNION,add),PARTS)(u, part);
 478
 479         return u;
 480 }
 481
 482 S(UNION,match_bin_data) {
 483         UNION *u2;
 484         UNION *res;
 485         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 486 };
 487
 488 /* Check if data->u2 has an element living in the same space as *entry.
 489  * If so, call data->fn on the two elements and add the result to
 490  * data->res.
 491  */
 492 static int match_bin_entry(void **entry, void *user)
 493 {
 494         S(UNION,match_bin_data) *data = user;
 495         uint32_t hash;
 496         struct isl_hash_table_entry *entry2;
 497         isl_space *space;
 498         PART *part = *entry;
 499         PART *part2;
 500
 501         space = FN(PART,get_space)(part);
 502         hash = isl_space_get_hash(space);
 503         entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
 504                                      hash, &has_same_domain_space, space, 0);
 505         isl_space_free(space);
 506         if (!entry2)
 507                 return 0;
 508
 509         part2 = entry2->data;
 510         if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
 511                                         part2->dim, isl_dim_out))
 512                 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
 513                         "entries should have the same range space",
 514                         return -1);
 515
 516         part = FN(PART, copy)(part);
 517         part = data->fn(part, FN(PART, copy)(entry2->data));
 518
 519         data->res = FN(FN(UNION,add),PARTS)(data->res, part);
 520         if (!data->res)
 521                 return -1;
 522
 523         return 0;
 524 }
 525
 526 /* This function is currently only used from isl_polynomial.c
 527  * and not from isl_fold.c.
 528  */
 529 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 530         __isl_take UNION *u2,
 531         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 532         __attribute__ ((unused));
 533 /* For each pair of elements in "u1" and "u2" living in the same space,
 534  * call "fn" and collect the results.
 535  */
 536 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 537         __isl_take UNION *u2,
 538         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 539 {
 540         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 541
 542         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 543         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 544
 545         if (!u1 || !u2)
 546                 goto error;
 547
 548         data.u2 = u2;
 549 #ifdef HAS_TYPE
 550         data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type,
 551                                     u1->table.n);
 552 #else
 553         data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n);
 554 #endif
 555         if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
 556                                     &match_bin_entry, &data) < 0)
 557                 goto error;
 558
 559         FN(UNION,free)(u1);
 560         FN(UNION,free)(u2);
 561         return data.res;
 562 error:
 563         FN(UNION,free)(u1);
 564         FN(UNION,free)(u2);
 565         FN(UNION,free)(data.res);
 566         return NULL;
 567 }
 568
 569 /* Compute the sum of "u1" and "u2".
 570  *
 571  * If the base expressions have a default zero value, then the sum
 572  * is computed on the union of the domains of "u1" and "u2".
 573  * Otherwise, it is computed on their shared domains.
 574  */
 575 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 576 {
 577 #if DEFAULT_IS_ZERO
 578         return FN(UNION,union_add_)(u1, u2);
 579 #else
 580         return match_bin_op(u1, u2, &FN(PART,add));
 581 #endif
 582 }
 583
 584 #ifndef NO_SUB
 585 /* Subtract "u2" from "u1" and return the result.
 586  */
 587 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 588 {
 589         return match_bin_op(u1, u2, &FN(PART,sub));
 590 }
 591 #endif
 592
 593 S(UNION,any_set_data) {
 594         isl_set *set;
 595         UNION *res;
 596         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 597 };
 598
 599 static int any_set_entry(void **entry, void *user)
 600 {
 601         S(UNION,any_set_data) *data = user;
 602         PW *pw = *entry;
 603
 604         pw = FN(PW,copy)(pw);
 605         pw = data->fn(pw, isl_set_copy(data->set));
 606
 607         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 608         if (!data->res)
 609                 return -1;
 610
 611         return 0;
 612 }
 613
 614 /* Update each element of "u" by calling "fn" on the element and "set".
 615  */
 616 static __isl_give UNION *any_set_op(__isl_take UNION *u,
 617         __isl_take isl_set *set,
 618         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 619 {
 620         S(UNION,any_set_data) data = { NULL, NULL, fn };
 621
 622         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 623         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 624
 625         if (!u || !set)
 626                 goto error;
 627
 628         data.set = set;
 629 #ifdef HAS_TYPE
 630         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
 631                                         u->table.n);
 632 #else
 633         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
 634 #endif
 635         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 636                                    &any_set_entry, &data) < 0)
 637                 goto error;
 638
 639         FN(UNION,free)(u);
 640         isl_set_free(set);
 641         return data.res;
 642 error:
 643         FN(UNION,free)(u);
 644         isl_set_free(set);
 645         FN(UNION,free)(data.res);
 646         return NULL;
 647 }
 648
 649 /* Intersect the domain of "u" with the parameter domain "context".
 650  */
 651 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 652         __isl_take isl_set *set)
 653 {
 654         return any_set_op(u, set, &FN(PW,intersect_params));
 655 }
 656
 657 /* Compute the gist of the domain of "u" with respect to
 658  * the parameter domain "context".
 659  */
 660 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 661         __isl_take isl_set *set)
 662 {
 663         return any_set_op(u, set, &FN(PW,gist_params));
 664 }
 665
 666 S(UNION,match_domain_data) {
 667         isl_union_set *uset;
 668         UNION *res;
 669         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 670 };
 671
 672 static int set_has_dim(const void *entry, const void *val)
 673 {
 674         isl_set *set = (isl_set *)entry;
 675         isl_space *dim = (isl_space *)val;
 676
 677         return isl_space_is_equal(set->dim, dim);
 678 }
 679
 680 /* Find the set in data->uset that lives in the same space as the domain
 681  * of *entry, apply data->fn to *entry and this set (if any), and add
 682  * the result to data->res.
 683  */
 684 static int match_domain_entry(void **entry, void *user)
 685 {
 686         S(UNION,match_domain_data) *data = user;
 687         uint32_t hash;
 688         struct isl_hash_table_entry *entry2;
 689         PW *pw = *entry;
 690         isl_space *space;
 691
 692         space = FN(PW,get_domain_space)(pw);
 693         hash = isl_space_get_hash(space);
 694         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 695                                      hash, &set_has_dim, space, 0);
 696         isl_space_free(space);
 697         if (!entry2)
 698                 return 0;
 699
 700         pw = FN(PW,copy)(pw);
 701         pw = data->fn(pw, isl_set_copy(entry2->data));
 702
 703         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 704         if (!data->res)
 705                 return -1;
 706
 707         return 0;
 708 }
 709
 710 /* Apply fn to each pair of PW in u and set in uset such that
 711  * the set lives in the same space as the domain of PW
 712  * and collect the results.
 713  */
 714 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
 715         __isl_take isl_union_set *uset,
 716         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 717 {
 718         S(UNION,match_domain_data) data = { NULL, NULL, fn };
 719
 720         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
 721         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 722
 723         if (!u || !uset)
 724                 goto error;
 725
 726         data.uset = uset;
 727 #ifdef HAS_TYPE
 728         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
 729                                         u->table.n);
 730 #else
 731         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
 732 #endif
 733         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 734                                    &match_domain_entry, &data) < 0)
 735                 goto error;
 736
 737         FN(UNION,free)(u);
 738         isl_union_set_free(uset);
 739         return data.res;
 740 error:
 741         FN(UNION,free)(u);
 742         isl_union_set_free(uset);
 743         FN(UNION,free)(data.res);
 744         return NULL;
 745 }
 746
 747 /* Intersect the domain of "u" with "uset".
 748  * If "uset" is a parameters domain, then intersect the parameter
 749  * domain of "u" with this set.
 750  */
 751 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 752         __isl_take isl_union_set *uset)
 753 {
 754         if (isl_union_set_is_params(uset))
 755                 return FN(UNION,intersect_params)(u,
 756                                                 isl_set_from_union_set(uset));
 757         return match_domain_op(u, uset, &FN(PW,intersect_domain));
 758 }
 759
 760 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 761         __isl_take isl_union_set *uset)
 762 {
 763         if (isl_union_set_is_params(uset))
 764                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 765         return match_domain_op(u, uset, &FN(PW,gist));
 766 }
 767
 768 #ifndef NO_EVAL
 769 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
 770         __isl_take isl_point *pnt)
 771 {
 772         uint32_t hash;
 773         struct isl_hash_table_entry *entry;
 774         isl_space *space;
 775         isl_val *v;
 776
 777         if (!u || !pnt)
 778                 goto error;
 779
 780         space = isl_space_copy(pnt->dim);
 781         if (!space)
 782                 goto error;
 783         hash = isl_space_get_hash(space);
 784         entry = isl_hash_table_find(u->space->ctx, &u->table,
 785                                     hash, &has_domain_space, space, 0);
 786         isl_space_free(space);
 787         if (!entry) {
 788                 v = isl_val_zero(isl_point_get_ctx(pnt));
 789                 isl_point_free(pnt);
 790         } else {
 791                 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 792         }
 793         FN(UNION,free)(u);
 794         return v;
 795 error:
 796         FN(UNION,free)(u);
 797         isl_point_free(pnt);
 798         return NULL;
 799 }
 800 #endif
 801
 802 static int coalesce_entry(void **entry, void *user)
 803 {
 804         PW **pw = (PW **)entry;
 805
 806         *pw = FN(PW,coalesce)(*pw);
 807         if (!*pw)
 808                 return -1;
 809
 810         return 0;
 811 }
 812
 813 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 814 {
 815         if (!u)
 816                 return NULL;
 817
 818         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 819                                    &coalesce_entry, NULL) < 0)
 820                 goto error;
 821
 822         return u;
 823 error:
 824         FN(UNION,free)(u);
 825         return NULL;
 826 }
 827
 828 static int domain(__isl_take PART *part, void *user)
 829 {
 830         isl_union_set **uset = (isl_union_set **)user;
 831
 832         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 833
 834         return 0;
 835 }
 836
 837 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 838 {
 839         isl_union_set *uset;
 840
 841         uset = isl_union_set_empty(FN(UNION,get_space)(u));
 842         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 843                 goto error;
 844
 845         FN(UNION,free)(u);
 846
 847         return uset;
 848 error:
 849         isl_union_set_free(uset);
 850         FN(UNION,free)(u);
 851         return NULL;
 852 }
 853
 854 static int mul_isl_int(void **entry, void *user)
 855 {
 856         PW **pw = (PW **)entry;
 857         isl_int *v = user;
 858
 859         *pw = FN(PW,mul_isl_int)(*pw, *v);
 860         if (!*pw)
 861                 return -1;
 862
 863         return 0;
 864 }
 865
 866 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
 867 {
 868         if (isl_int_is_one(v))
 869                 return u;
 870
 871         if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
 872                 UNION *zero;
 873                 isl_space *dim = FN(UNION,get_space)(u);
 874 #ifdef HAS_TYPE
 875                 zero = FN(UNION,ZERO)(dim, u->type);
 876 #else
 877                 zero = FN(UNION,ZERO)(dim);
 878 #endif
 879                 FN(UNION,free)(u);
 880                 return zero;
 881         }
 882
 883         u = FN(UNION,cow)(u);
 884         if (!u)
 885                 return NULL;
 886
 887 #ifdef HAS_TYPE
 888         if (isl_int_is_neg(v))
 889                 u->type = isl_fold_type_negate(u->type);
 890 #endif
 891         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 892                                     &mul_isl_int, &v) < 0)
 893                 goto error;
 894
 895         return u;
 896 error:
 897         FN(UNION,free)(u);
 898         return NULL;
 899 }
 900
 901 /* Multiply *entry by the isl_val "user".
 902  *
 903  * Return 0 on success and -1 on error.
 904  */
 905 static int scale_val(void **entry, void *user)
 906 {
 907         PW **pw = (PW **)entry;
 908         isl_val *v = user;
 909
 910         *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
 911         if (!*pw)
 912                 return -1;
 913
 914         return 0;
 915 }
 916
 917 /* Multiply "u" by "v" and return the result.
 918  */
 919 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
 920         __isl_take isl_val *v)
 921 {
 922         if (!u || !v)
 923                 goto error;
 924         if (isl_val_is_one(v)) {
 925                 isl_val_free(v);
 926                 return u;
 927         }
 928
 929         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
 930                 UNION *zero;
 931                 isl_space *space = FN(UNION,get_space)(u);
 932 #ifdef HAS_TYPE
 933                 zero = FN(UNION,ZERO)(space, u->type);
 934 #else
 935                 zero = FN(UNION,ZERO)(space);
 936 #endif
 937                 FN(UNION,free)(u);
 938                 isl_val_free(v);
 939                 return zero;
 940         }
 941
 942         if (!isl_val_is_rat(v))
 943                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 944                         "expecting rational factor", goto error);
 945
 946         u = FN(UNION,cow)(u);
 947         if (!u)
 948                 return NULL;
 949
 950 #ifdef HAS_TYPE
 951         if (isl_val_is_neg(v))
 952                 u->type = isl_fold_type_negate(u->type);
 953 #endif
 954         if (isl_hash_table_foreach(u->space->ctx, &u->table, &scale_val, v) < 0)
 955                 goto error;
 956
 957         isl_val_free(v);
 958         return u;
 959 error:
 960         isl_val_free(v);
 961         FN(UNION,free)(u);
 962         return NULL;
 963 }
 964
 965 S(UNION,plain_is_equal_data)
 966 {
 967         UNION *u2;
 968         int is_equal;
 969 };
 970
 971 static int plain_is_equal_entry(void **entry, void *user)
 972 {
 973         S(UNION,plain_is_equal_data) *data = user;
 974         uint32_t hash;
 975         struct isl_hash_table_entry *entry2;
 976         PW *pw = *entry;
 977
 978         hash = isl_space_get_hash(pw->dim);
 979         entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
 980                                      hash, &has_same_domain_space, pw->dim, 0);
 981         if (!entry2) {
 982                 data->is_equal = 0;
 983                 return -1;
 984         }
 985
 986         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
 987         if (data->is_equal < 0 || !data->is_equal)
 988                 return -1;
 989
 990         return 0;
 991 }
 992
 993 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 994 {
 995         S(UNION,plain_is_equal_data) data = { NULL, 1 };
 996
 997         if (!u1 || !u2)
 998                 return -1;
 999         if (u1 == u2)
1000                 return 1;
1001         if (u1->table.n != u2->table.n)
1002                 return 0;
1003
1004         u1 = FN(UNION,copy)(u1);
1005         u2 = FN(UNION,copy)(u2);
1006         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1007         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1008         if (!u1 || !u2)
1009                 goto error;
1010
1011         data.u2 = u2;
1012         if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
1013                                    &plain_is_equal_entry, &data) < 0 &&
1014             data.is_equal)
1015                 goto error;
1016
1017         FN(UNION,free)(u1);
1018         FN(UNION,free)(u2);
1019
1020         return data.is_equal;
1021 error:
1022         FN(UNION,free)(u1);
1023         FN(UNION,free)(u2);
1024         return -1;
1025 }