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 *dim;
  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->dim->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->dim);
  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->dim = 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->dim->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 *dim)
 128 {
 129         uint32_t hash;
 130         struct isl_hash_table_entry *entry;
 131
 132         if (!u || !dim)
 133                 goto error;
 134
 135         hash = isl_space_get_hash(dim);
 136         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
 137                                     &has_dim, dim, 0);
 138         if (!entry)
 139 #ifdef HAS_TYPE
 140                 return FN(PART,ZERO)(dim, u->type);
 141 #else
 142                 return FN(PART,ZERO)(dim);
 143 #endif
 144         isl_space_free(dim);
 145         return FN(PART,copy)(entry->data);
 146 error:
 147         isl_space_free(dim);
 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->dim->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->dim->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->dim), u->type);
 224 #else
 225         dup = FN(UNION,ZERO)(isl_space_copy(u->dim));
 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->dim->ctx, &u->table, &free_u_entry, NULL);
 262         isl_hash_table_clear(&u->table);
 263         isl_space_free(u->dim);
 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->dim, 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->dim, 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->dim->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->dim), u1->type, u1->table.n);
 446 #else
 447         data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->table.n);
 448 #endif
 449         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
 450                                     &match_bin_entry, &data) < 0)
 451                 goto error;
 452
 453         FN(UNION,free)(u1);
 454         FN(UNION,free)(u2);
 455         return data.res;
 456 error:
 457         FN(UNION,free)(u1);
 458         FN(UNION,free)(u2);
 459         FN(UNION,free)(data.res);
 460         return NULL;
 461 }
 462
 463 #ifndef NO_SUB
 464 /* Subtract "u2" from "u1" and return the result.
 465  */
 466 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
 467 {
 468         return match_bin_op(u1, u2, &FN(PART,sub));
 469 }
 470 #endif
 471
 472 S(UNION,any_set_data) {
 473         isl_set *set;
 474         UNION *res;
 475         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 476 };
 477
 478 static int any_set_entry(void **entry, void *user)
 479 {
 480         S(UNION,any_set_data) *data = user;
 481         PW *pw = *entry;
 482
 483         pw = FN(PW,copy)(pw);
 484         pw = data->fn(pw, isl_set_copy(data->set));
 485
 486         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 487         if (!data->res)
 488                 return -1;
 489
 490         return 0;
 491 }
 492
 493 /* Update each element of "u" by calling "fn" on the element and "set".
 494  */
 495 static __isl_give UNION *any_set_op(__isl_take UNION *u,
 496         __isl_take isl_set *set,
 497         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 498 {
 499         S(UNION,any_set_data) data = { NULL, NULL, fn };
 500
 501         u = FN(UNION,align_params)(u, isl_set_get_space(set));
 502         set = isl_set_align_params(set, FN(UNION,get_space)(u));
 503
 504         if (!u || !set)
 505                 goto error;
 506
 507         data.set = set;
 508 #ifdef HAS_TYPE
 509         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
 510 #else
 511         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
 512 #endif
 513         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 514                                    &any_set_entry, &data) < 0)
 515                 goto error;
 516
 517         FN(UNION,free)(u);
 518         isl_set_free(set);
 519         return data.res;
 520 error:
 521         FN(UNION,free)(u);
 522         isl_set_free(set);
 523         FN(UNION,free)(data.res);
 524         return NULL;
 525 }
 526
 527 /* Intersect the domain of "u" with the parameter domain "context".
 528  */
 529 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
 530         __isl_take isl_set *set)
 531 {
 532         return any_set_op(u, set, &FN(PW,intersect_params));
 533 }
 534
 535 /* Compute the gist of the domain of "u" with respect to
 536  * the parameter domain "context".
 537  */
 538 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
 539         __isl_take isl_set *set)
 540 {
 541         return any_set_op(u, set, &FN(PW,gist_params));
 542 }
 543
 544 S(UNION,match_domain_data) {
 545         isl_union_set *uset;
 546         UNION *res;
 547         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
 548 };
 549
 550 static int set_has_dim(const void *entry, const void *val)
 551 {
 552         isl_set *set = (isl_set *)entry;
 553         isl_space *dim = (isl_space *)val;
 554
 555         return isl_space_is_equal(set->dim, dim);
 556 }
 557
 558 /* Find the set in data->uset that lives in the same space as the domain
 559  * of *entry, apply data->fn to *entry and this set (if any), and add
 560  * the result to data->res.
 561  */
 562 static int match_domain_entry(void **entry, void *user)
 563 {
 564         S(UNION,match_domain_data) *data = user;
 565         uint32_t hash;
 566         struct isl_hash_table_entry *entry2;
 567         PW *pw = *entry;
 568         isl_space *space;
 569
 570         space = FN(PW,get_domain_space)(pw);
 571         hash = isl_space_get_hash(space);
 572         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
 573                                      hash, &set_has_dim, space, 0);
 574         isl_space_free(space);
 575         if (!entry2)
 576                 return 0;
 577
 578         pw = FN(PW,copy)(pw);
 579         pw = data->fn(pw, isl_set_copy(entry2->data));
 580
 581         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
 582         if (!data->res)
 583                 return -1;
 584
 585         return 0;
 586 }
 587
 588 /* Apply fn to each pair of PW in u and set in uset such that
 589  * the set lives in the same space as the domain of PW
 590  * and collect the results.
 591  */
 592 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
 593         __isl_take isl_union_set *uset,
 594         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
 595 {
 596         S(UNION,match_domain_data) data = { NULL, NULL, fn };
 597
 598         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
 599         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
 600
 601         if (!u || !uset)
 602                 goto error;
 603
 604         data.uset = uset;
 605 #ifdef HAS_TYPE
 606         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
 607 #else
 608         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
 609 #endif
 610         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 611                                    &match_domain_entry, &data) < 0)
 612                 goto error;
 613
 614         FN(UNION,free)(u);
 615         isl_union_set_free(uset);
 616         return data.res;
 617 error:
 618         FN(UNION,free)(u);
 619         isl_union_set_free(uset);
 620         FN(UNION,free)(data.res);
 621         return NULL;
 622 }
 623
 624 /* Intersect the domain of "u" with "uset".
 625  * If "uset" is a parameters domain, then intersect the parameter
 626  * domain of "u" with this set.
 627  */
 628 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
 629         __isl_take isl_union_set *uset)
 630 {
 631         if (isl_union_set_is_params(uset))
 632                 return FN(UNION,intersect_params)(u,
 633                                                 isl_set_from_union_set(uset));
 634         return match_domain_op(u, uset, &FN(PW,intersect_domain));
 635 }
 636
 637 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
 638         __isl_take isl_union_set *uset)
 639 {
 640         if (isl_union_set_is_params(uset))
 641                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
 642         return match_domain_op(u, uset, &FN(PW,gist));
 643 }
 644
 645 #ifndef NO_EVAL
 646 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
 647         __isl_take isl_point *pnt)
 648 {
 649         uint32_t hash;
 650         struct isl_hash_table_entry *entry;
 651         isl_space *space;
 652         isl_val *v;
 653
 654         if (!u || !pnt)
 655                 goto error;
 656
 657         space = isl_space_copy(pnt->dim);
 658         space = isl_space_from_domain(space);
 659         space = isl_space_add_dims(space, isl_dim_out, 1);
 660         if (!space)
 661                 goto error;
 662         hash = isl_space_get_hash(space);
 663         entry = isl_hash_table_find(u->dim->ctx, &u->table,
 664                                     hash, &has_dim, space, 0);
 665         isl_space_free(space);
 666         if (!entry) {
 667                 v = isl_val_zero(isl_point_get_ctx(pnt));
 668                 isl_point_free(pnt);
 669         } else {
 670                 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
 671         }
 672         FN(UNION,free)(u);
 673         return v;
 674 error:
 675         FN(UNION,free)(u);
 676         isl_point_free(pnt);
 677         return NULL;
 678 }
 679 #endif
 680
 681 static int coalesce_entry(void **entry, void *user)
 682 {
 683         PW **pw = (PW **)entry;
 684
 685         *pw = FN(PW,coalesce)(*pw);
 686         if (!*pw)
 687                 return -1;
 688
 689         return 0;
 690 }
 691
 692 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
 693 {
 694         if (!u)
 695                 return NULL;
 696
 697         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 698                                    &coalesce_entry, NULL) < 0)
 699                 goto error;
 700
 701         return u;
 702 error:
 703         FN(UNION,free)(u);
 704         return NULL;
 705 }
 706
 707 static int domain(__isl_take PART *part, void *user)
 708 {
 709         isl_union_set **uset = (isl_union_set **)user;
 710
 711         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
 712
 713         return 0;
 714 }
 715
 716 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
 717 {
 718         isl_union_set *uset;
 719
 720         uset = isl_union_set_empty(FN(UNION,get_space)(u));
 721         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
 722                 goto error;
 723
 724         FN(UNION,free)(u);
 725
 726         return uset;
 727 error:
 728         isl_union_set_free(uset);
 729         FN(UNION,free)(u);
 730         return NULL;
 731 }
 732
 733 static int mul_isl_int(void **entry, void *user)
 734 {
 735         PW **pw = (PW **)entry;
 736         isl_int *v = user;
 737
 738         *pw = FN(PW,mul_isl_int)(*pw, *v);
 739         if (!*pw)
 740                 return -1;
 741
 742         return 0;
 743 }
 744
 745 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
 746 {
 747         if (isl_int_is_one(v))
 748                 return u;
 749
 750         if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
 751                 UNION *zero;
 752                 isl_space *dim = FN(UNION,get_space)(u);
 753 #ifdef HAS_TYPE
 754                 zero = FN(UNION,ZERO)(dim, u->type);
 755 #else
 756                 zero = FN(UNION,ZERO)(dim);
 757 #endif
 758                 FN(UNION,free)(u);
 759                 return zero;
 760         }
 761
 762         u = FN(UNION,cow)(u);
 763         if (!u)
 764                 return NULL;
 765
 766 #ifdef HAS_TYPE
 767         if (isl_int_is_neg(v))
 768                 u->type = isl_fold_type_negate(u->type);
 769 #endif
 770         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
 771                                     &mul_isl_int, &v) < 0)
 772                 goto error;
 773
 774         return u;
 775 error:
 776         FN(UNION,free)(u);
 777         return NULL;
 778 }
 779
 780 /* Multiply *entry by the isl_val "user".
 781  *
 782  * Return 0 on success and -1 on error.
 783  */
 784 static int scale_val(void **entry, void *user)
 785 {
 786         PW **pw = (PW **)entry;
 787         isl_val *v = user;
 788
 789         *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
 790         if (!*pw)
 791                 return -1;
 792
 793         return 0;
 794 }
 795
 796 /* Multiply "u" by "v" and return the result.
 797  */
 798 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
 799         __isl_take isl_val *v)
 800 {
 801         if (!u || !v)
 802                 goto error;
 803         if (isl_val_is_one(v)) {
 804                 isl_val_free(v);
 805                 return u;
 806         }
 807
 808         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
 809                 UNION *zero;
 810                 isl_space *space = FN(UNION,get_space)(u);
 811 #ifdef HAS_TYPE
 812                 zero = FN(UNION,ZERO)(space, u->type);
 813 #else
 814                 zero = FN(UNION,ZERO)(space);
 815 #endif
 816                 FN(UNION,free)(u);
 817                 isl_val_free(v);
 818                 return zero;
 819         }
 820
 821         if (!isl_val_is_rat(v))
 822                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
 823                         "expecting rational factor", goto error);
 824
 825         u = FN(UNION,cow)(u);
 826         if (!u)
 827                 return NULL;
 828
 829 #ifdef HAS_TYPE
 830         if (isl_val_is_neg(v))
 831                 u->type = isl_fold_type_negate(u->type);
 832 #endif
 833         if (isl_hash_table_foreach(u->dim->ctx, &u->table, &scale_val, v) < 0)
 834                 goto error;
 835
 836         isl_val_free(v);
 837         return u;
 838 error:
 839         isl_val_free(v);
 840         FN(UNION,free)(u);
 841         return NULL;
 842 }
 843
 844 S(UNION,plain_is_equal_data)
 845 {
 846         UNION *u2;
 847         int is_equal;
 848 };
 849
 850 static int plain_is_equal_entry(void **entry, void *user)
 851 {
 852         S(UNION,plain_is_equal_data) *data = user;
 853         uint32_t hash;
 854         struct isl_hash_table_entry *entry2;
 855         PW *pw = *entry;
 856
 857         hash = isl_space_get_hash(pw->dim);
 858         entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
 859                                      hash, &has_dim, pw->dim, 0);
 860         if (!entry2) {
 861                 data->is_equal = 0;
 862                 return -1;
 863         }
 864
 865         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
 866         if (data->is_equal < 0 || !data->is_equal)
 867                 return -1;
 868
 869         return 0;
 870 }
 871
 872 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
 873 {
 874         S(UNION,plain_is_equal_data) data = { NULL, 1 };
 875
 876         if (!u1 || !u2)
 877                 return -1;
 878         if (u1 == u2)
 879                 return 1;
 880         if (u1->table.n != u2->table.n)
 881                 return 0;
 882
 883         u1 = FN(UNION,copy)(u1);
 884         u2 = FN(UNION,copy)(u2);
 885         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
 886         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
 887         if (!u1 || !u2)
 888                 goto error;
 889
 890         data.u2 = u2;
 891         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
 892                                    &plain_is_equal_entry, &data) < 0 &&
 893             data.is_equal)
 894                 goto error;
 895
 896         FN(UNION,free)(u1);
 897         FN(UNION,free)(u2);
 898
 899         return data.is_equal;
 900 error:
 901         FN(UNION,free)(u1);
 902         FN(UNION,free)(u2);
 903         return -1;
 904 }