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