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 static int has_dim(const void *entry, const void *val)
 119 {
 120         PART *part = (PART *)entry;
 121         isl_space *dim = (isl_space *)val;
 122
 123         return isl_space_is_equal(part->dim, dim);
 124 }
 125
 126 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
 127         __isl_take isl_space *space)
 128 {
 129         uint32_t hash;
 130         struct isl_hash_table_entry *entry;
 131
 132         if (!u || !space)
 133                 goto error;
 134
 135         hash = isl_space_get_hash(space);
 136         entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
 137                                     &has_dim, space, 0);
 138         if (!entry)
 139 #ifdef HAS_TYPE
 140                 return FN(PART,ZERO)(space, u->type);
 141 #else
 142                 return FN(PART,ZERO)(space);
 143 #endif
 144         isl_space_free(space);
 145         return FN(PART,copy)(entry->data);
 146 error:
 147         isl_space_free(space);
 148         return NULL;
 149 }
 150
 151 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
 152         __isl_take PART *part)
 153 {
 154         int empty;
 155         uint32_t hash;
 156         struct isl_hash_table_entry *entry;
 157
 158         if (!part)
 159                 goto error;
 160
 161         empty = FN(PART,IS_ZERO)(part);
 162         if (empty < 0)
 163                 goto error;
 164         if (empty) {
 165                 FN(PART,free)(part);
 166                 return u;
 167         }
 168
 169         u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
 170         part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
 171
 172         u = FN(UNION,cow)(u);
 173
 174         if (!u)
 175                 goto error;
 176
 177         hash = isl_space_get_hash(part->dim);
 178         entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
 179                                     &has_dim, part->dim, 1);
 180         if (!entry)
 181                 goto error;
 182
 183         if (!entry->data)
 184                 entry->data = part;
 185         else {
 186                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
 187                 if (!entry->data)
 188                         goto error;
 189                 empty = FN(PART,IS_ZERO)(part);
 190                 if (empty < 0)
 191                         goto error;
 192                 if (empty) {
 193                         FN(PART,free)(entry->data);
 194                         isl_hash_table_remove(u->space->ctx, &u->table, entry);
 195                 }
 196                 FN(PART,free)(part);
 197         }
 198
 199         return u;
 200 error:
 201         FN(PART,free)(part);
 202         FN(UNION,free)(u);
 203         return NULL;
 204 }
 205
 206 static int add_part(__isl_take PART *part, void *user)
 207 {
 208         UNION **u = (UNION **)user;
 209
 210         *u = FN(FN(UNION,add),PARTS)(*u, part);
 211
 212         return 0;
 213 }
 214
 215 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
 216 {
 217         UNION *dup;
 218
 219         if (!u)
 220                 return NULL;
 221
 222 #ifdef HAS_TYPE
 223         dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type);
 224 #else
 225         dup = FN(UNION,ZERO)(isl_space_copy(u->space));
 226 #endif
 227         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
 228                 goto error;
 229         return dup;
 230 error:
 231         FN(UNION,free)(dup);
 232         return NULL;
 233 }
 234
 235 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
 236 {
 237         if (!u)
 238                 return NULL;
 239
 240         if (u->ref == 1)
 241                 return u;
 242         u->ref--;
 243         return FN(UNION,dup)(u);
 244 }
 245
 246 static int free_u_entry(void **entry, void *user)
 247 {
 248         PART *part = *entry;
 249         FN(PART,free)(part);
 250         return 0;
 251 }
 252
 253 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
 254 {
 255         if (!u)
 256                 return NULL;
 257
 258         if (--u->ref > 0)
 259                 return NULL;
 260
 261         isl_hash_table_foreach(u->space->ctx, &u->table, &free_u_entry, NULL);
 262         isl_hash_table_clear(&u->table);
 263         isl_space_free(u->space);
 264         free(u);
 265         return NULL;
 266 }
 267
 268 S(UNION,align) {
 269         isl_reordering *exp;
 270         UNION *res;
 271 };
 272
 273 #ifdef ALIGN_DOMAIN
 274 static int align_entry(__isl_take PART *part, void *user)
 275 {
 276         isl_reordering *exp;
 277         S(UNION,align) *data = user;
 278
 279         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 280                                     FN(PART,get_domain_space)(part));
 281
 282         data->res = FN(FN(UNION,add),PARTS)(data->res,
 283                                             FN(PART,realign_domain)(part, exp));
 284
 285         return 0;
 286 }
 287 #else
 288 static int align_entry(__isl_take PART *part, void *user)
 289 {
 290         isl_reordering *exp;
 291         S(UNION,align) *data = user;
 292
 293         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
 294                                     FN(PART,get_space)(part));
 295
 296         data->res = FN(FN(UNION,add),PARTS)(data->res,
 297                                             FN(PART,realign)(part, exp));
 298
 299         return 0;
 300 }
 301 #endif
 302
 303 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
 304         __isl_take isl_space *model)
 305 {
 306         S(UNION,align) data = { NULL, NULL };
 307
 308         if (!u || !model)
 309                 goto error;
 310
 311         if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
 312                 isl_space_free(model);
 313                 return u;
 314         }
 315
 316         model = isl_space_params(model);
 317         data.exp = isl_parameter_alignment_reordering(u->space, model);
 318         if (!data.exp)
 319                 goto error;
 320
 321 #ifdef HAS_TYPE
 322         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
 323                                                 u->type, u->table.n);
 324 #else
 325         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
 326 #endif
 327         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
 328                 goto error;
 329
 330         isl_reordering_free(data.exp);
 331         FN(UNION,free)(u);
 332         isl_space_free(model);
 333         return data.res;
 334 error:
 335         isl_reordering_free(data.exp);
 336         FN(UNION,free)(u);
 337         FN(UNION,free)(data.res);
 338         isl_space_free(model);
 339         return NULL;
 340 }
 341
 342 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
 343 {
 344         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 345         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 346
 347         u1 = FN(UNION,cow)(u1);
 348
 349         if (!u1 || !u2)
 350                 goto error;
 351
 352         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
 353                 goto error;
 354
 355         FN(UNION,free)(u2);
 356
 357         return u1;
 358 error:
 359         FN(UNION,free)(u1);
 360         FN(UNION,free)(u2);
 361         return NULL;
 362 }
 363
 364 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
 365 {
 366         isl_space *dim;
 367         UNION *u;
 368
 369         if (!part)
 370                 return NULL;
 371
 372         dim = FN(PART,get_space)(part);
 373         dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
 374         dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
 375 #ifdef HAS_TYPE
 376         u = FN(UNION,ZERO)(dim, part->type);
 377 #else
 378         u = FN(UNION,ZERO)(dim);
 379 #endif
 380         u = FN(FN(UNION,add),PARTS)(u, part);
 381
 382         return u;
 383 }
 384
 385 S(UNION,match_bin_data) {
 386         UNION *u2;
 387         UNION *res;
 388         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
 389 };
 390
 391 /* Check if data->u2 has an element living in the same space as *entry.
 392  * If so, call data->fn on the two elements and add the result to
 393  * data->res.
 394  */
 395 static int match_bin_entry(void **entry, void *user)
 396 {
 397         S(UNION,match_bin_data) *data = user;
 398         uint32_t hash;
 399         struct isl_hash_table_entry *entry2;
 400         isl_space *space;
 401         PART *part = *entry;
 402
 403         space = FN(PART,get_space)(part);
 404         hash = isl_space_get_hash(space);
 405         entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
 406                                      hash, &has_dim, space, 0);
 407         isl_space_free(space);
 408         if (!entry2)
 409                 return 0;
 410
 411         part = FN(PART, copy)(part);
 412         part = data->fn(part, FN(PART, copy)(entry2->data));
 413
 414         data->res = FN(FN(UNION,add),PARTS)(data->res, part);
 415         if (!data->res)
 416                 return -1;
 417
 418         return 0;
 419 }
 420
 421 /* This function is currently only used from isl_polynomial.c
 422  * and not from isl_fold.c.
 423  */
 424 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 425         __isl_take UNION *u2,
 426         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 427         __attribute__ ((unused));
 428 /* For each pair of elements in "u1" and "u2" living in the same space,
 429  * call "fn" and collect the results.
 430  */
 431 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
 432         __isl_take UNION *u2,
 433         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
 434 {
 435         S(UNION,match_bin_data) data = { NULL, NULL, fn };
 436
 437         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 438         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 439
 440         if (!u1 || !u2)
 441                 goto error;
 442
 443         data.u2 = u2;
 444 #ifdef HAS_TYPE
 445         data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type,
 446                                     u1->table.n);
 447 #else
 448         data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n);
 449 #endif
 450         if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
 451                                     &match_bin_entry, &data) < 0)
 452                 goto error;
 453
 454         FN(UNION,free)(u1);
 455         FN(UNION,free)(u2);
 456         return data.res;
 457 error:
 458         FN(UNION,free)(u1);
 459         FN(UNION,free)(u2);
 460         FN(UNION,free)(data.res);
 461         return NULL;
 462 }
 463
 464 #ifndef NO_SUB
 465 /* Subtract "u2" from "u1" and return the result.
 466  */
 467 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 468 {
 469         return match_bin_op(u1, u2, &FN(PART,sub));
 470 }
 471 #endif
 472
 473 S(UNION,any_set_data) {
 474         isl_set *set;
 475         UNION *res;
 476         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 477 };
 478
 479 static int any_set_entry(void **entry, void *user)
 480 {
 481         S(UNION,any_set_data) *data = user;
 482         PW *pw = *entry;
 483
 484         pw = FN(PW,copy)(pw);
 485         pw = data->fn(pw, isl_set_copy(data->set));
 486
 487         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 488         if (!data->res)
 489                 return -1;
 490
 491         return 0;
 492 }
 493
 494 /* Update each element of "u" by calling "fn" on the element and "set".
 495  */
 496 static __isl_give UNION *any_set_op(__isl_take UNION *u,
 497         __isl_take isl_set *set,
 498         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 499 {
 500         S(UNION,any_set_data) data = { NULL, NULL, fn };
 501
 502         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 503         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 504
 505         if (!u || !set)
 506                 goto error;
 507
 508         data.set = set;
 509 #ifdef HAS_TYPE
 510         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
 511                                         u->table.n);
 512 #else
 513         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
 514 #endif
 515         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 516                                    &any_set_entry, &data) < 0)
 517                 goto error;
 518
 519         FN(UNION,free)(u);
 520         isl_set_free(set);
 521         return data.res;
 522 error:
 523         FN(UNION,free)(u);
 524         isl_set_free(set);
 525         FN(UNION,free)(data.res);
 526         return NULL;
 527 }
 528
 529 /* Intersect the domain of "u" with the parameter domain "context".
 530  */
 531 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 532         __isl_take isl_set *set)
 533 {
 534         return any_set_op(u, set, &FN(PW,intersect_params));
 535 }
 536
 537 /* Compute the gist of the domain of "u" with respect to
 538  * the parameter domain "context".
 539  */
 540 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 541         __isl_take isl_set *set)
 542 {
 543         return any_set_op(u, set, &FN(PW,gist_params));
 544 }
 545
 546 S(UNION,match_domain_data) {
 547         isl_union_set *uset;
 548         UNION *res;
 549         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 550 };
 551
 552 static int set_has_dim(const void *entry, const void *val)
 553 {
 554         isl_set *set = (isl_set *)entry;
 555         isl_space *dim = (isl_space *)val;
 556
 557         return isl_space_is_equal(set->dim, dim);
 558 }
 559
 560 /* Find the set in data->uset that lives in the same space as the domain
 561  * of *entry, apply data->fn to *entry and this set (if any), and add
 562  * the result to data->res.
 563  */
 564 static int match_domain_entry(void **entry, void *user)
 565 {
 566         S(UNION,match_domain_data) *data = user;
 567         uint32_t hash;
 568         struct isl_hash_table_entry *entry2;
 569         PW *pw = *entry;
 570         isl_space *space;
 571
 572         space = FN(PW,get_domain_space)(pw);
 573         hash = isl_space_get_hash(space);
 574         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 575                                      hash, &set_has_dim, space, 0);
 576         isl_space_free(space);
 577         if (!entry2)
 578                 return 0;
 579
 580         pw = FN(PW,copy)(pw);
 581         pw = data->fn(pw, isl_set_copy(entry2->data));
 582
 583         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 584         if (!data->res)
 585                 return -1;
 586
 587         return 0;
 588 }
 589
 590 /* Apply fn to each pair of PW in u and set in uset such that
 591  * the set lives in the same space as the domain of PW
 592  * and collect the results.
 593  */
 594 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
 595         __isl_take isl_union_set *uset,
 596         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 597 {
 598         S(UNION,match_domain_data) data = { NULL, NULL, fn };
 599
 600         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
 601         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 602
 603         if (!u || !uset)
 604                 goto error;
 605
 606         data.uset = uset;
 607 #ifdef HAS_TYPE
 608         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
 609                                         u->table.n);
 610 #else
 611         data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
 612 #endif
 613         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 614                                    &match_domain_entry, &data) < 0)
 615                 goto error;
 616
 617         FN(UNION,free)(u);
 618         isl_union_set_free(uset);
 619         return data.res;
 620 error:
 621         FN(UNION,free)(u);
 622         isl_union_set_free(uset);
 623         FN(UNION,free)(data.res);
 624         return NULL;
 625 }
 626
 627 /* Intersect the domain of "u" with "uset".
 628  * If "uset" is a parameters domain, then intersect the parameter
 629  * domain of "u" with this set.
 630  */
 631 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 632         __isl_take isl_union_set *uset)
 633 {
 634         if (isl_union_set_is_params(uset))
 635                 return FN(UNION,intersect_params)(u,
 636                                                 isl_set_from_union_set(uset));
 637         return match_domain_op(u, uset, &FN(PW,intersect_domain));
 638 }
 639
 640 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 641         __isl_take isl_union_set *uset)
 642 {
 643         if (isl_union_set_is_params(uset))
 644                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 645         return match_domain_op(u, uset, &FN(PW,gist));
 646 }
 647
 648 #ifndef NO_EVAL
 649 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
 650         __isl_take isl_point *pnt)
 651 {
 652         uint32_t hash;
 653         struct isl_hash_table_entry *entry;
 654         isl_space *space;
 655         isl_val *v;
 656
 657         if (!u || !pnt)
 658                 goto error;
 659
 660         space = isl_space_copy(pnt->dim);
 661         space = isl_space_from_domain(space);
 662         space = isl_space_add_dims(space, isl_dim_out, 1);
 663         if (!space)
 664                 goto error;
 665         hash = isl_space_get_hash(space);
 666         entry = isl_hash_table_find(u->space->ctx, &u->table,
 667                                     hash, &has_dim, space, 0);
 668         isl_space_free(space);
 669         if (!entry) {
 670                 v = isl_val_zero(isl_point_get_ctx(pnt));
 671                 isl_point_free(pnt);
 672         } else {
 673                 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 674         }
 675         FN(UNION,free)(u);
 676         return v;
 677 error:
 678         FN(UNION,free)(u);
 679         isl_point_free(pnt);
 680         return NULL;
 681 }
 682 #endif
 683
 684 static int coalesce_entry(void **entry, void *user)
 685 {
 686         PW **pw = (PW **)entry;
 687
 688         *pw = FN(PW,coalesce)(*pw);
 689         if (!*pw)
 690                 return -1;
 691
 692         return 0;
 693 }
 694
 695 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 696 {
 697         if (!u)
 698                 return NULL;
 699
 700         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 701                                    &coalesce_entry, NULL) < 0)
 702                 goto error;
 703
 704         return u;
 705 error:
 706         FN(UNION,free)(u);
 707         return NULL;
 708 }
 709
 710 static int domain(__isl_take PART *part, void *user)
 711 {
 712         isl_union_set **uset = (isl_union_set **)user;
 713
 714         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 715
 716         return 0;
 717 }
 718
 719 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 720 {
 721         isl_union_set *uset;
 722
 723         uset = isl_union_set_empty(FN(UNION,get_space)(u));
 724         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 725                 goto error;
 726
 727         FN(UNION,free)(u);
 728
 729         return uset;
 730 error:
 731         isl_union_set_free(uset);
 732         FN(UNION,free)(u);
 733         return NULL;
 734 }
 735
 736 static int mul_isl_int(void **entry, void *user)
 737 {
 738         PW **pw = (PW **)entry;
 739         isl_int *v = user;
 740
 741         *pw = FN(PW,mul_isl_int)(*pw, *v);
 742         if (!*pw)
 743                 return -1;
 744
 745         return 0;
 746 }
 747
 748 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
 749 {
 750         if (isl_int_is_one(v))
 751                 return u;
 752
 753         if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
 754                 UNION *zero;
 755                 isl_space *dim = FN(UNION,get_space)(u);
 756 #ifdef HAS_TYPE
 757                 zero = FN(UNION,ZERO)(dim, u->type);
 758 #else
 759                 zero = FN(UNION,ZERO)(dim);
 760 #endif
 761                 FN(UNION,free)(u);
 762                 return zero;
 763         }
 764
 765         u = FN(UNION,cow)(u);
 766         if (!u)
 767                 return NULL;
 768
 769 #ifdef HAS_TYPE
 770         if (isl_int_is_neg(v))
 771                 u->type = isl_fold_type_negate(u->type);
 772 #endif
 773         if (isl_hash_table_foreach(u->space->ctx, &u->table,
 774                                     &mul_isl_int, &v) < 0)
 775                 goto error;
 776
 777         return u;
 778 error:
 779         FN(UNION,free)(u);
 780         return NULL;
 781 }
 782
 783 /* Multiply *entry by the isl_val "user".
 784  *
 785  * Return 0 on success and -1 on error.
 786  */
 787 static int scale_val(void **entry, void *user)
 788 {
 789         PW **pw = (PW **)entry;
 790         isl_val *v = user;
 791
 792         *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
 793         if (!*pw)
 794                 return -1;
 795
 796         return 0;
 797 }
 798
 799 /* Multiply "u" by "v" and return the result.
 800  */
 801 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
 802         __isl_take isl_val *v)
 803 {
 804         if (!u || !v)
 805                 goto error;
 806         if (isl_val_is_one(v)) {
 807                 isl_val_free(v);
 808                 return u;
 809         }
 810
 811         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
 812                 UNION *zero;
 813                 isl_space *space = FN(UNION,get_space)(u);
 814 #ifdef HAS_TYPE
 815                 zero = FN(UNION,ZERO)(space, u->type);
 816 #else
 817                 zero = FN(UNION,ZERO)(space);
 818 #endif
 819                 FN(UNION,free)(u);
 820                 isl_val_free(v);
 821                 return zero;
 822         }
 823
 824         if (!isl_val_is_rat(v))
 825                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 826                         "expecting rational factor", goto error);
 827
 828         u = FN(UNION,cow)(u);
 829         if (!u)
 830                 return NULL;
 831
 832 #ifdef HAS_TYPE
 833         if (isl_val_is_neg(v))
 834                 u->type = isl_fold_type_negate(u->type);
 835 #endif
 836         if (isl_hash_table_foreach(u->space->ctx, &u->table, &scale_val, v) < 0)
 837                 goto error;
 838
 839         isl_val_free(v);
 840         return u;
 841 error:
 842         isl_val_free(v);
 843         FN(UNION,free)(u);
 844         return NULL;
 845 }
 846
 847 S(UNION,plain_is_equal_data)
 848 {
 849         UNION *u2;
 850         int is_equal;
 851 };
 852
 853 static int plain_is_equal_entry(void **entry, void *user)
 854 {
 855         S(UNION,plain_is_equal_data) *data = user;
 856         uint32_t hash;
 857         struct isl_hash_table_entry *entry2;
 858         PW *pw = *entry;
 859
 860         hash = isl_space_get_hash(pw->dim);
 861         entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
 862                                      hash, &has_dim, pw->dim, 0);
 863         if (!entry2) {
 864                 data->is_equal = 0;
 865                 return -1;
 866         }
 867
 868         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
 869         if (data->is_equal < 0 || !data->is_equal)
 870                 return -1;
 871
 872         return 0;
 873 }
 874
 875 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 876 {
 877         S(UNION,plain_is_equal_data) data = { NULL, 1 };
 878
 879         if (!u1 || !u2)
 880                 return -1;
 881         if (u1 == u2)
 882                 return 1;
 883         if (u1->table.n != u2->table.n)
 884                 return 0;
 885
 886         u1 = FN(UNION,copy)(u1);
 887         u2 = FN(UNION,copy)(u2);
 888         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 889         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 890         if (!u1 || !u2)
 891                 goto error;
 892
 893         data.u2 = u2;
 894         if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
 895                                    &plain_is_equal_entry, &data) < 0 &&
 896             data.is_equal)
 897                 goto error;
 898
 899         FN(UNION,free)(u1);
 900         FN(UNION,free)(u2);
 901
 902         return data.is_equal;
 903 error:
 904         FN(UNION,free)(u1);
 905         FN(UNION,free)(u2);
 906         return -1;
 907 }