?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_pw_multi_aff_identity
[isl.git] / isl_pw_templ.c
blobb80e084f9bd1fe587f58c1dfac9d662d4d26988e
1 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
2 #define FN(TYPE,NAME) xFN(TYPE,NAME)
3 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
4 #define S(TYPE,NAME) xS(TYPE,NAME)
5
6 #ifdef HAS_TYPE
7 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim,
8 enum isl_fold type, int n)
9 #else
10 __isl_give PW *FN(PW,alloc_size)(__isl_take isl_space *dim, int n)
11 #endif
12 {
13 isl_ctx *ctx;
14 struct PW *pw;
15
16 if (!dim)
17 return NULL;
18 ctx = isl_space_get_ctx(dim);
19 isl_assert(ctx, n >= 0, goto error);
20 pw = isl_alloc(ctx, struct PW,
21 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
22 if (!pw)
23 goto error;
24
25 pw->ref = 1;
26 #ifdef HAS_TYPE
27 pw->type = type;
28 #endif
29 pw->size = n;
30 pw->n = 0;
31 pw->dim = dim;
32 return pw;
33 error:
34 isl_space_free(dim);
35 return NULL;
36 }
37
38 #ifdef HAS_TYPE
39 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
40 {
41 return FN(PW,alloc_size)(dim, type, 0);
42 }
43 #else
44 __isl_give PW *FN(PW,ZERO)(__isl_take isl_space *dim)
45 {
46 return FN(PW,alloc_size)(dim, 0);
47 }
48 #endif
49
50 __isl_give PW *FN(PW,add_piece)(__isl_take PW *pw,
51 __isl_take isl_set *set, __isl_take EL *el)
52 {
53 isl_ctx *ctx;
54 isl_space *el_dim = NULL;
55
56 if (!pw || !set || !el)
57 goto error;
58
59 if (isl_set_plain_is_empty(set) || FN(EL,EL_IS_ZERO)(el)) {
60 isl_set_free(set);
61 FN(EL,free)(el);
62 return pw;
63 }
64
65 ctx = isl_set_get_ctx(set);
66 #ifdef HAS_TYPE
67 if (pw->type != el->type)
68 isl_die(ctx, isl_error_invalid, "fold types don't match",
69 goto error);
70 #endif
71 el_dim = FN(EL,get_space(el));
72 isl_assert(ctx, isl_space_is_equal(pw->dim, el_dim), goto error);
73 isl_assert(ctx, pw->n < pw->size, goto error);
74
75 pw->p[pw->n].set = set;
76 pw->p[pw->n].FIELD = el;
77 pw->n++;
78
79 isl_space_free(el_dim);
80 return pw;
81 error:
82 isl_space_free(el_dim);
83 FN(PW,free)(pw);
84 isl_set_free(set);
85 FN(EL,free)(el);
86 return NULL;
87 }
88
89 #ifdef HAS_TYPE
90 __isl_give PW *FN(PW,alloc)(enum isl_fold type,
91 __isl_take isl_set *set, __isl_take EL *el)
92 #else
93 __isl_give PW *FN(PW,alloc)(__isl_take isl_set *set, __isl_take EL *el)
94 #endif
95 {
96 PW *pw;
97
98 if (!set || !el)
99 goto error;
100
101 #ifdef HAS_TYPE
102 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), type, 1);
103 #else
104 pw = FN(PW,alloc_size)(FN(EL,get_space)(el), 1);
105 #endif
106
107 return FN(PW,add_piece)(pw, set, el);
108 error:
109 isl_set_free(set);
110 FN(EL,free)(el);
111 return NULL;
112 }
113
114 __isl_give PW *FN(PW,dup)(__isl_keep PW *pw)
115 {
116 int i;
117 PW *dup;
118
119 if (!pw)
120 return NULL;
121
122 #ifdef HAS_TYPE
123 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, pw->n);
124 #else
125 dup = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->n);
126 #endif
127 if (!dup)
128 return NULL;
129
130 for (i = 0; i < pw->n; ++i)
131 dup = FN(PW,add_piece)(dup, isl_set_copy(pw->p[i].set),
132 FN(EL,copy)(pw->p[i].FIELD));
133
134 return dup;
135 }
136
137 __isl_give PW *FN(PW,cow)(__isl_take PW *pw)
138 {
139 if (!pw)
140 return NULL;
141
142 if (pw->ref == 1)
143 return pw;
144 pw->ref--;
145 return FN(PW,dup)(pw);
146 }
147
148 __isl_give PW *FN(PW,copy)(__isl_keep PW *pw)
149 {
150 if (!pw)
151 return NULL;
152
153 pw->ref++;
154 return pw;
155 }
156
157 void *FN(PW,free)(__isl_take PW *pw)
158 {
159 int i;
160
161 if (!pw)
162 return NULL;
163 if (--pw->ref > 0)
164 return NULL;
165
166 for (i = 0; i < pw->n; ++i) {
167 isl_set_free(pw->p[i].set);
168 FN(EL,free)(pw->p[i].FIELD);
169 }
170 isl_space_free(pw->dim);
171 free(pw);
172
173 return NULL;
174 }
175
176 const char *FN(PW,get_dim_name)(__isl_keep PW *pw, enum isl_dim_type type,
177 unsigned pos)
178 {
179 return pw ? isl_space_get_dim_name(pw->dim, type, pos) : NULL;
180 }
181
182 int FN(PW,has_dim_id)(__isl_keep PW *pw, enum isl_dim_type type, unsigned pos)
183 {
184 return pw ? isl_space_has_dim_id(pw->dim, type, pos) : -1;
185 }
186
187 __isl_give isl_id *FN(PW,get_dim_id)(__isl_keep PW *pw, enum isl_dim_type type,
188 unsigned pos)
189 {
190 return pw ? isl_space_get_dim_id(pw->dim, type, pos) : NULL;
191 }
192
193 int FN(PW,has_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
194 {
195 return pw ? isl_space_has_tuple_name(pw->dim, type) : -1;
196 }
197
198 const char *FN(PW,get_tuple_name)(__isl_keep PW *pw, enum isl_dim_type type)
199 {
200 return pw ? isl_space_get_tuple_name(pw->dim, type) : NULL;
201 }
202
203 int FN(PW,has_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
204 {
205 return pw ? isl_space_has_tuple_id(pw->dim, type) : -1;
206 }
207
208 __isl_give isl_id *FN(PW,get_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type)
209 {
210 return pw ? isl_space_get_tuple_id(pw->dim, type) : NULL;
211 }
212
213 int FN(PW,IS_ZERO)(__isl_keep PW *pw)
214 {
215 if (!pw)
216 return -1;
217
218 return pw->n == 0;
219 }
220
221 #ifndef NO_REALIGN
222 __isl_give PW *FN(PW,realign_domain)(__isl_take PW *pw,
223 __isl_take isl_reordering *exp)
224 {
225 int i;
226
227 pw = FN(PW,cow)(pw);
228 if (!pw || !exp)
229 goto error;
230
231 for (i = 0; i < pw->n; ++i) {
232 pw->p[i].set = isl_set_realign(pw->p[i].set,
233 isl_reordering_copy(exp));
234 if (!pw->p[i].set)
235 goto error;
236 pw->p[i].FIELD = FN(EL,realign_domain)(pw->p[i].FIELD,
237 isl_reordering_copy(exp));
238 if (!pw->p[i].FIELD)
239 goto error;
240 }
241
242 pw = FN(PW,reset_domain_space)(pw, isl_space_copy(exp->dim));
243
244 isl_reordering_free(exp);
245 return pw;
246 error:
247 isl_reordering_free(exp);
248 FN(PW,free)(pw);
249 return NULL;
250 }
251
252 /* Align the parameters of "pw" to those of "model".
253 */
254 __isl_give PW *FN(PW,align_params)(__isl_take PW *pw, __isl_take isl_space *model)
255 {
256 isl_ctx *ctx;
257
258 if (!pw || !model)
259 goto error;
260
261 ctx = isl_space_get_ctx(model);
262 if (!isl_space_has_named_params(model))
263 isl_die(ctx, isl_error_invalid,
264 "model has unnamed parameters", goto error);
265 if (!isl_space_has_named_params(pw->dim))
266 isl_die(ctx, isl_error_invalid,
267 "input has unnamed parameters", goto error);
268 if (!isl_space_match(pw->dim, isl_dim_param, model, isl_dim_param)) {
269 isl_reordering *exp;
270
271 model = isl_space_drop_dims(model, isl_dim_in,
272 0, isl_space_dim(model, isl_dim_in));
273 model = isl_space_drop_dims(model, isl_dim_out,
274 0, isl_space_dim(model, isl_dim_out));
275 exp = isl_parameter_alignment_reordering(pw->dim, model);
276 exp = isl_reordering_extend_space(exp,
277 FN(PW,get_domain_space)(pw));
278 pw = FN(PW,realign_domain)(pw, exp);
279 }
280
281 isl_space_free(model);
282 return pw;
283 error:
284 isl_space_free(model);
285 FN(PW,free)(pw);
286 return NULL;
287 }
288
289 static __isl_give PW *FN(PW,align_params_pw_pw_and)(__isl_take PW *pw1,
290 __isl_take PW *pw2,
291 __isl_give PW *(*fn)(__isl_take PW *pw1, __isl_take PW *pw2))
292 {
293 isl_ctx *ctx;
294
295 if (!pw1 || !pw2)
296 goto error;
297 if (isl_space_match(pw1->dim, isl_dim_param, pw2->dim, isl_dim_param))
298 return fn(pw1, pw2);
299 ctx = FN(PW,get_ctx)(pw1);
300 if (!isl_space_has_named_params(pw1->dim) ||
301 !isl_space_has_named_params(pw2->dim))
302 isl_die(ctx, isl_error_invalid,
303 "unaligned unnamed parameters", goto error);
304 pw1 = FN(PW,align_params)(pw1, FN(PW,get_space)(pw2));
305 pw2 = FN(PW,align_params)(pw2, FN(PW,get_space)(pw1));
306 return fn(pw1, pw2);
307 error:
308 FN(PW,free)(pw1);
309 FN(PW,free)(pw2);
310 return NULL;
311 }
312
313 static __isl_give PW *FN(PW,align_params_pw_set_and)(__isl_take PW *pw,
314 __isl_take isl_set *set,
315 __isl_give PW *(*fn)(__isl_take PW *pw, __isl_take isl_set *set))
316 {
317 isl_ctx *ctx;
318
319 if (!pw || !set)
320 goto error;
321 if (isl_space_match(pw->dim, isl_dim_param, set->dim, isl_dim_param))
322 return fn(pw, set);
323 ctx = FN(PW,get_ctx)(pw);
324 if (!isl_space_has_named_params(pw->dim) ||
325 !isl_space_has_named_params(set->dim))
326 isl_die(ctx, isl_error_invalid,
327 "unaligned unnamed parameters", goto error);
328 pw = FN(PW,align_params)(pw, isl_set_get_space(set));
329 set = isl_set_align_params(set, FN(PW,get_space)(pw));
330 return fn(pw, set);
331 error:
332 FN(PW,free)(pw);
333 isl_set_free(set);
334 return NULL;
335 }
336 #endif
337
338 static __isl_give PW *FN(PW,union_add_aligned)(__isl_take PW *pw1,
339 __isl_take PW *pw2)
340 {
341 int i, j, n;
342 struct PW *res;
343 isl_ctx *ctx;
344 isl_set *set;
345
346 if (!pw1 || !pw2)
347 goto error;
348
349 ctx = isl_space_get_ctx(pw1->dim);
350 #ifdef HAS_TYPE
351 if (pw1->type != pw2->type)
352 isl_die(ctx, isl_error_invalid,
353 "fold types don't match", goto error);
354 #endif
355 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
356
357 if (FN(PW,IS_ZERO)(pw1)) {
358 FN(PW,free)(pw1);
359 return pw2;
360 }
361
362 if (FN(PW,IS_ZERO)(pw2)) {
363 FN(PW,free)(pw2);
364 return pw1;
365 }
366
367 n = (pw1->n + 1) * (pw2->n + 1);
368 #ifdef HAS_TYPE
369 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), pw1->type, n);
370 #else
371 res = FN(PW,alloc_size)(isl_space_copy(pw1->dim), n);
372 #endif
373
374 for (i = 0; i < pw1->n; ++i) {
375 set = isl_set_copy(pw1->p[i].set);
376 for (j = 0; j < pw2->n; ++j) {
377 struct isl_set *common;
378 EL *sum;
379 common = isl_set_intersect(isl_set_copy(pw1->p[i].set),
380 isl_set_copy(pw2->p[j].set));
381 if (isl_set_plain_is_empty(common)) {
382 isl_set_free(common);
383 continue;
384 }
385 set = isl_set_subtract(set,
386 isl_set_copy(pw2->p[j].set));
387
388 sum = FN(EL,add_on_domain)(common,
389 FN(EL,copy)(pw1->p[i].FIELD),
390 FN(EL,copy)(pw2->p[j].FIELD));
391
392 res = FN(PW,add_piece)(res, common, sum);
393 }
394 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw1->p[i].FIELD));
395 }
396
397 for (j = 0; j < pw2->n; ++j) {
398 set = isl_set_copy(pw2->p[j].set);
399 for (i = 0; i < pw1->n; ++i)
400 set = isl_set_subtract(set,
401 isl_set_copy(pw1->p[i].set));
402 res = FN(PW,add_piece)(res, set, FN(EL,copy)(pw2->p[j].FIELD));
403 }
404
405 FN(PW,free)(pw1);
406 FN(PW,free)(pw2);
407
408 return res;
409 error:
410 FN(PW,free)(pw1);
411 FN(PW,free)(pw2);
412 return NULL;
413 }
414
415 /* Private version of "union_add". For isl_pw_qpolynomial and
416 * isl_pw_qpolynomial_fold, we prefer to simply call it "add".
417 */
418 static __isl_give PW *FN(PW,union_add_)(__isl_take PW *pw1, __isl_take PW *pw2)
419 {
420 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
421 &FN(PW,union_add_aligned));
422 }
423
424 /* Make sure "pw" has room for at least "n" more pieces.
425 *
426 * If there is only one reference to pw, we extend it in place.
427 * Otherwise, we create a new PW and copy the pieces.
428 */
429 static __isl_give PW *FN(PW,grow)(__isl_take PW *pw, int n)
430 {
431 int i;
432 isl_ctx *ctx;
433 PW *res;
434
435 if (!pw)
436 return NULL;
437 if (pw->n + n <= pw->size)
438 return pw;
439 ctx = FN(PW,get_ctx)(pw);
440 n += pw->n;
441 if (pw->ref == 1) {
442 res = isl_realloc(ctx, pw, struct PW,
443 sizeof(struct PW) + (n - 1) * sizeof(S(PW,piece)));
444 if (!res)
445 return FN(PW,free)(pw);
446 res->size = n;
447 return res;
448 }
449 #ifdef HAS_TYPE
450 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), pw->type, n);
451 #else
452 res = FN(PW,alloc_size)(isl_space_copy(pw->dim), n);
453 #endif
454 if (!res)
455 return FN(PW,free)(pw);
456 for (i = 0; i < pw->n; ++i)
457 res = FN(PW,add_piece)(res, isl_set_copy(pw->p[i].set),
458 FN(EL,copy)(pw->p[i].FIELD));
459 FN(PW,free)(pw);
460 return res;
461 }
462
463 static __isl_give PW *FN(PW,add_disjoint_aligned)(__isl_take PW *pw1,
464 __isl_take PW *pw2)
465 {
466 int i;
467 isl_ctx *ctx;
468
469 if (!pw1 || !pw2)
470 goto error;
471
472 if (pw1->size < pw1->n + pw2->n && pw1->n < pw2->n)
473 return FN(PW,add_disjoint_aligned)(pw2, pw1);
474
475 ctx = isl_space_get_ctx(pw1->dim);
476 #ifdef HAS_TYPE
477 if (pw1->type != pw2->type)
478 isl_die(ctx, isl_error_invalid,
479 "fold types don't match", goto error);
480 #endif
481 isl_assert(ctx, isl_space_is_equal(pw1->dim, pw2->dim), goto error);
482
483 if (FN(PW,IS_ZERO)(pw1)) {
484 FN(PW,free)(pw1);
485 return pw2;
486 }
487
488 if (FN(PW,IS_ZERO)(pw2)) {
489 FN(PW,free)(pw2);
490 return pw1;
491 }
492
493 pw1 = FN(PW,grow)(pw1, pw2->n);
494 if (!pw1)
495 goto error;
496
497 for (i = 0; i < pw2->n; ++i)
498 pw1 = FN(PW,add_piece)(pw1,
499 isl_set_copy(pw2->p[i].set),
500 FN(EL,copy)(pw2->p[i].FIELD));
501
502 FN(PW,free)(pw2);
503
504 return pw1;
505 error:
506 FN(PW,free)(pw1);
507 FN(PW,free)(pw2);
508 return NULL;
509 }
510
511 __isl_give PW *FN(PW,add_disjoint)(__isl_take PW *pw1, __isl_take PW *pw2)
512 {
513 return FN(PW,align_params_pw_pw_and)(pw1, pw2,
514 &FN(PW,add_disjoint_aligned));
515 }
516
517 /* This function is currently only used from isl_aff.c
518 */
519 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
520 __isl_take PW *pw2, __isl_take isl_space *space,
521 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
522 __attribute__ ((unused));
523
524 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
525 * The result of "fn" (and therefore also of this function) lives in "space".
526 */
527 static __isl_give PW *FN(PW,on_shared_domain_in)(__isl_take PW *pw1,
528 __isl_take PW *pw2, __isl_take isl_space *space,
529 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
530 {
531 int i, j, n;
532 PW *res = NULL;
533
534 if (!pw1 || !pw2)
535 goto error;
536
537 n = pw1->n * pw2->n;
538 #ifdef HAS_TYPE
539 res = FN(PW,alloc_size)(space, pw1->type, n);
540 #else
541 res = FN(PW,alloc_size)(space, n);
542 #endif
543
544 for (i = 0; i < pw1->n; ++i) {
545 for (j = 0; j < pw2->n; ++j) {
546 isl_set *common;
547 EL *res_ij;
548 int empty;
549
550 common = isl_set_intersect(
551 isl_set_copy(pw1->p[i].set),
552 isl_set_copy(pw2->p[j].set));
553 empty = isl_set_plain_is_empty(common);
554 if (empty < 0 || empty) {
555 isl_set_free(common);
556 if (empty < 0)
557 goto error;
558 continue;
559 }
560
561 res_ij = fn(FN(EL,copy)(pw1->p[i].FIELD),
562 FN(EL,copy)(pw2->p[j].FIELD));
563 res_ij = FN(EL,gist)(res_ij, isl_set_copy(common));
564
565 res = FN(PW,add_piece)(res, common, res_ij);
566 }
567 }
568
569 FN(PW,free)(pw1);
570 FN(PW,free)(pw2);
571 return res;
572 error:
573 isl_space_free(space);
574 FN(PW,free)(pw1);
575 FN(PW,free)(pw2);
576 FN(PW,free)(res);
577 return NULL;
578 }
579
580 /* This function is currently only used from isl_aff.c
581 */
582 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
583 __isl_take PW *pw2,
584 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
585 __attribute__ ((unused));
586
587 /* Apply "fn" to pairs of elements from pw1 and pw2 on shared domains.
588 * The result of "fn" is assumed to live in the same space as "pw1" and "pw2".
589 */
590 static __isl_give PW *FN(PW,on_shared_domain)(__isl_take PW *pw1,
591 __isl_take PW *pw2,
592 __isl_give EL *(*fn)(__isl_take EL *el1, __isl_take EL *el2))
593 {
594 isl_space *space;
595
596 if (!pw1 || !pw2)
597 goto error;
598
599 space = isl_space_copy(pw1->dim);
600 return FN(PW,on_shared_domain_in)(pw1, pw2, space, fn);
601 error:
602 FN(PW,free)(pw1);
603 FN(PW,free)(pw2);
604 return NULL;
605 }
606
607 #ifndef NO_NEG
608 __isl_give PW *FN(PW,neg)(__isl_take PW *pw)
609 {
610 int i;
611
612 if (!pw)
613 return NULL;
614
615 if (FN(PW,IS_ZERO)(pw))
616 return pw;
617
618 pw = FN(PW,cow)(pw);
619 if (!pw)
620 return NULL;
621
622 for (i = 0; i < pw->n; ++i) {
623 pw->p[i].FIELD = FN(EL,neg)(pw->p[i].FIELD);
624 if (!pw->p[i].FIELD)
625 return FN(PW,free)(pw);
626 }
627
628 return pw;
629 }
630
631 __isl_give PW *FN(PW,sub)(__isl_take PW *pw1, __isl_take PW *pw2)
632 {
633 return FN(PW,add)(pw1, FN(PW,neg)(pw2));
634 }
635 #endif
636
637 #ifndef NO_EVAL
638 __isl_give isl_qpolynomial *FN(PW,eval)(__isl_take PW *pw,
639 __isl_take isl_point *pnt)
640 {
641 int i;
642 int found = 0;
643 isl_ctx *ctx;
644 isl_space *pnt_dim = NULL;
645 isl_qpolynomial *qp;
646
647 if (!pw || !pnt)
648 goto error;
649 ctx = isl_point_get_ctx(pnt);
650 pnt_dim = isl_point_get_space(pnt);
651 isl_assert(ctx, isl_space_is_domain_internal(pnt_dim, pw->dim),
652 goto error);
653
654 for (i = 0; i < pw->n; ++i) {
655 found = isl_set_contains_point(pw->p[i].set, pnt);
656 if (found < 0)
657 goto error;
658 if (found)
659 break;
660 }
661 if (found)
662 qp = FN(EL,eval)(FN(EL,copy)(pw->p[i].FIELD),
663 isl_point_copy(pnt));
664 else
665 qp = isl_qpolynomial_zero_on_domain(FN(PW,get_domain_space)(pw));
666 FN(PW,free)(pw);
667 isl_space_free(pnt_dim);
668 isl_point_free(pnt);
669 return qp;
670 error:
671 FN(PW,free)(pw);
672 isl_space_free(pnt_dim);
673 isl_point_free(pnt);
674 return NULL;
675 }
676 #endif
677
678 __isl_give isl_set *FN(PW,domain)(__isl_take PW *pw)
679 {
680 int i;
681 isl_set *dom;
682
683 if (!pw)
684 return NULL;
685
686 dom = isl_set_empty(FN(PW,get_domain_space)(pw));
687 for (i = 0; i < pw->n; ++i)
688 dom = isl_set_union_disjoint(dom, isl_set_copy(pw->p[i].set));
689
690 FN(PW,free)(pw);
691
692 return dom;
693 }
694
695 /* Restrict the domain of "pw" by combining each cell
696 * with "set" through a call to "fn", where "fn" may be
697 * isl_set_intersect or isl_set_intersect_params.
698 */
699 static __isl_give PW *FN(PW,intersect_aligned)(__isl_take PW *pw,
700 __isl_take isl_set *set,
701 __isl_give isl_set *(*fn)(__isl_take isl_set *set1,
702 __isl_take isl_set *set2))
703 {
704 int i;
705
706 if (!pw || !set)
707 goto error;
708
709 if (pw->n == 0) {
710 isl_set_free(set);
711 return pw;
712 }
713
714 pw = FN(PW,cow)(pw);
715 if (!pw)
716 goto error;
717
718 for (i = pw->n - 1; i >= 0; --i) {
719 isl_basic_set *aff;
720 pw->p[i].set = fn(pw->p[i].set, isl_set_copy(set));
721 if (!pw->p[i].set)
722 goto error;
723 aff = isl_set_affine_hull(isl_set_copy(pw->p[i].set));
724 pw->p[i].FIELD = FN(EL,substitute_equalities)(pw->p[i].FIELD,
725 aff);
726 if (!pw->p[i].FIELD)
727 goto error;
728 if (isl_set_plain_is_empty(pw->p[i].set)) {
729 isl_set_free(pw->p[i].set);
730 FN(EL,free)(pw->p[i].FIELD);
731 if (i != pw->n - 1)
732 pw->p[i] = pw->p[pw->n - 1];
733 pw->n--;
734 }
735 }
736
737 isl_set_free(set);
738 return pw;
739 error:
740 isl_set_free(set);
741 FN(PW,free)(pw);
742 return NULL;
743 }
744
745 static __isl_give PW *FN(PW,intersect_domain_aligned)(__isl_take PW *pw,
746 __isl_take isl_set *set)
747 {
748 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect);
749 }
750
751 __isl_give PW *FN(PW,intersect_domain)(__isl_take PW *pw,
752 __isl_take isl_set *context)
753 {
754 return FN(PW,align_params_pw_set_and)(pw, context,
755 &FN(PW,intersect_domain_aligned));
756 }
757
758 static __isl_give PW *FN(PW,intersect_params_aligned)(__isl_take PW *pw,
759 __isl_take isl_set *set)
760 {
761 return FN(PW,intersect_aligned)(pw, set, &isl_set_intersect_params);
762 }
763
764 /* Intersect the domain of "pw" with the parameter domain "context".
765 */
766 __isl_give PW *FN(PW,intersect_params)(__isl_take PW *pw,
767 __isl_take isl_set *context)
768 {
769 return FN(PW,align_params_pw_set_and)(pw, context,
770 &FN(PW,intersect_params_aligned));
771 }
772
773 static __isl_give PW *FN(PW,gist_aligned)(__isl_take PW *pw,
774 __isl_take isl_set *context,
775 __isl_give EL *(*fn_el)(__isl_take EL *el,
776 __isl_take isl_set *set),
777 __isl_give isl_set *(*fn_dom)(__isl_take isl_set *set,
778 __isl_take isl_basic_set *bset))
779 {
780 int i;
781 isl_basic_set *hull = NULL;
782
783 if (!pw || !context)
784 goto error;
785
786 if (pw->n == 0) {
787 isl_set_free(context);
788 return pw;
789 }
790
791 if (!isl_space_match(pw->dim, isl_dim_param,
792 context->dim, isl_dim_param)) {
793 pw = FN(PW,align_params)(pw, isl_set_get_space(context));
794 context = isl_set_align_params(context, FN(PW,get_space)(pw));
795 }
796
797 context = isl_set_compute_divs(context);
798 hull = isl_set_simple_hull(isl_set_copy(context));
799
800 pw = FN(PW,cow)(pw);
801 if (!pw)
802 goto error;
803
804 for (i = pw->n - 1; i >= 0; --i) {
805 pw->p[i].set = isl_set_intersect(pw->p[i].set,
806 isl_set_copy(context));
807 if (!pw->p[i].set)
808 goto error;
809 pw->p[i].FIELD = fn_el(pw->p[i].FIELD,
810 isl_set_copy(pw->p[i].set));
811 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
812 if (!pw->p[i].set)
813 goto error;
814 if (isl_set_plain_is_empty(pw->p[i].set)) {
815 isl_set_free(pw->p[i].set);
816 FN(EL,free)(pw->p[i].FIELD);
817 if (i != pw->n - 1)
818 pw->p[i] = pw->p[pw->n - 1];
819 pw->n--;
820 }
821 }
822
823 isl_basic_set_free(hull);
824 isl_set_free(context);
825
826 return pw;
827 error:
828 FN(PW,free)(pw);
829 isl_basic_set_free(hull);
830 isl_set_free(context);
831 return NULL;
832 }
833
834 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
835 __isl_take isl_set *set)
836 {
837 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
838 &isl_set_gist_basic_set);
839 }
840
841 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
842 {
843 return FN(PW,align_params_pw_set_and)(pw, context,
844 &FN(PW,gist_domain_aligned));
845 }
846
847 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
848 __isl_take isl_set *set)
849 {
850 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
851 &isl_set_gist_params_basic_set);
852 }
853
854 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
855 __isl_take isl_set *context)
856 {
857 return FN(PW,align_params_pw_set_and)(pw, context,
858 &FN(PW,gist_params_aligned));
859 }
860
861 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
862 {
863 int i, j;
864
865 if (!pw)
866 return NULL;
867 if (pw->n == 0)
868 return pw;
869
870 for (i = pw->n - 1; i >= 0; --i) {
871 for (j = i - 1; j >= 0; --j) {
872 if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
873 pw->p[j].FIELD))
874 continue;
875 pw->p[j].set = isl_set_union(pw->p[j].set,
876 pw->p[i].set);
877 FN(EL,free)(pw->p[i].FIELD);
878 if (i != pw->n - 1)
879 pw->p[i] = pw->p[pw->n - 1];
880 pw->n--;
881 break;
882 }
883 if (j >= 0)
884 continue;
885 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
886 if (!pw->p[i].set)
887 goto error;
888 }
889
890 return pw;
891 error:
892 FN(PW,free)(pw);
893 return NULL;
894 }
895
896 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
897 {
898 return pw ? isl_space_get_ctx(pw->dim) : NULL;
899 }
900
901 #ifndef NO_INVOLVES_DIMS
902 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
903 unsigned first, unsigned n)
904 {
905 int i;
906 enum isl_dim_type set_type;
907
908 if (!pw)
909 return -1;
910 if (pw->n == 0 || n == 0)
911 return 0;
912
913 set_type = type == isl_dim_in ? isl_dim_set : type;
914
915 for (i = 0; i < pw->n; ++i) {
916 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
917 type, first, n);
918 if (involves < 0 || involves)
919 return involves;
920 involves = isl_set_involves_dims(pw->p[i].set,
921 set_type, first, n);
922 if (involves < 0 || involves)
923 return involves;
924 }
925 return 0;
926 }
927 #endif
928
929 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
930 enum isl_dim_type type, unsigned pos, const char *s)
931 {
932 int i;
933 enum isl_dim_type set_type;
934
935 pw = FN(PW,cow)(pw);
936 if (!pw)
937 return NULL;
938
939 set_type = type == isl_dim_in ? isl_dim_set : type;
940
941 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
942 if (!pw->dim)
943 goto error;
944
945 for (i = 0; i < pw->n; ++i) {
946 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
947 set_type, pos, s);
948 if (!pw->p[i].set)
949 goto error;
950 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
951 if (!pw->p[i].FIELD)
952 goto error;
953 }
954
955 return pw;
956 error:
957 FN(PW,free)(pw);
958 return NULL;
959 }
960
961 #ifndef NO_DROP_DIMS
962 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
963 enum isl_dim_type type, unsigned first, unsigned n)
964 {
965 int i;
966 enum isl_dim_type set_type;
967
968 if (!pw)
969 return NULL;
970 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
971 return pw;
972
973 set_type = type == isl_dim_in ? isl_dim_set : type;
974
975 pw = FN(PW,cow)(pw);
976 if (!pw)
977 return NULL;
978 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
979 if (!pw->dim)
980 goto error;
981 for (i = 0; i < pw->n; ++i) {
982 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
983 if (!pw->p[i].set)
984 goto error;
985 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
986 if (!pw->p[i].FIELD)
987 goto error;
988 }
989
990 return pw;
991 error:
992 FN(PW,free)(pw);
993 return NULL;
994 }
995
996 /* This function is very similar to drop_dims.
997 * The only difference is that the cells may still involve
998 * the specified dimensions. They are removed using
999 * isl_set_project_out instead of isl_set_drop.
1000 */
1001 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1002 enum isl_dim_type type, unsigned first, unsigned n)
1003 {
1004 int i;
1005 enum isl_dim_type set_type;
1006
1007 if (!pw)
1008 return NULL;
1009 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1010 return pw;
1011
1012 set_type = type == isl_dim_in ? isl_dim_set : type;
1013
1014 pw = FN(PW,cow)(pw);
1015 if (!pw)
1016 return NULL;
1017 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1018 if (!pw->dim)
1019 goto error;
1020 for (i = 0; i < pw->n; ++i) {
1021 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1022 set_type, first, n);
1023 if (!pw->p[i].set)
1024 goto error;
1025 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1026 if (!pw->p[i].FIELD)
1027 goto error;
1028 }
1029
1030 return pw;
1031 error:
1032 FN(PW,free)(pw);
1033 return NULL;
1034 }
1035
1036 /* Project the domain of pw onto its parameter space.
1037 */
1038 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1039 {
1040 isl_space *space;
1041 unsigned n;
1042
1043 n = FN(PW,dim)(pw, isl_dim_in);
1044 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1045 space = FN(PW,get_domain_space)(pw);
1046 space = isl_space_params(space);
1047 pw = FN(PW,reset_domain_space)(pw, space);
1048 return pw;
1049 }
1050 #endif
1051
1052 #ifndef NO_INSERT_DIMS
1053 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1054 unsigned first, unsigned n)
1055 {
1056 int i;
1057 enum isl_dim_type set_type;
1058
1059 if (!pw)
1060 return NULL;
1061 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1062 return pw;
1063
1064 set_type = type == isl_dim_in ? isl_dim_set : type;
1065
1066 pw = FN(PW,cow)(pw);
1067 if (!pw)
1068 return NULL;
1069
1070 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1071 if (!pw->dim)
1072 goto error;
1073
1074 for (i = 0; i < pw->n; ++i) {
1075 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1076 set_type, first, n);
1077 if (!pw->p[i].set)
1078 goto error;
1079 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1080 type, first, n);
1081 if (!pw->p[i].FIELD)
1082 goto error;
1083 }
1084
1085 return pw;
1086 error:
1087 FN(PW,free)(pw);
1088 return NULL;
1089 }
1090 #endif
1091
1092 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1093 enum isl_dim_type type, unsigned pos, isl_int v)
1094 {
1095 int i;
1096
1097 if (!pw)
1098 return NULL;
1099
1100 if (type == isl_dim_in)
1101 type = isl_dim_set;
1102
1103 pw = FN(PW,cow)(pw);
1104 if (!pw)
1105 return NULL;
1106 for (i = 0; i < pw->n; ++i) {
1107 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1108 if (!pw->p[i].set)
1109 goto error;
1110 }
1111
1112 return pw;
1113 error:
1114 FN(PW,free)(pw);
1115 return NULL;
1116 }
1117
1118 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1119 {
1120 return pw ? isl_space_dim(pw->dim, type) : 0;
1121 }
1122
1123 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1124 enum isl_dim_type type, unsigned first, unsigned n)
1125 {
1126 int i;
1127
1128 if (!pw)
1129 return NULL;
1130 if (n == 0)
1131 return pw;
1132
1133 if (type == isl_dim_in)
1134 type = isl_dim_set;
1135
1136 pw = FN(PW,cow)(pw);
1137 if (!pw)
1138 return NULL;
1139 if (!pw->dim)
1140 goto error;
1141 for (i = 0; i < pw->n; ++i) {
1142 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1143 if (!pw->p[i].set)
1144 goto error;
1145 }
1146
1147 return pw;
1148 error:
1149 FN(PW,free)(pw);
1150 return NULL;
1151 }
1152
1153 #ifndef NO_OPT
1154 /* Compute the maximal value attained by the piecewise quasipolynomial
1155 * on its domain or zero if the domain is empty.
1156 * In the worst case, the domain is scanned completely,
1157 * so the domain is assumed to be bounded.
1158 */
1159 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
1160 {
1161 int i;
1162 isl_qpolynomial *opt;
1163
1164 if (!pw)
1165 return NULL;
1166
1167 if (pw->n == 0) {
1168 isl_space *dim = isl_space_copy(pw->dim);
1169 FN(PW,free)(pw);
1170 return isl_qpolynomial_zero_on_domain(isl_space_domain(dim));
1171 }
1172
1173 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1174 isl_set_copy(pw->p[0].set), max);
1175 for (i = 1; i < pw->n; ++i) {
1176 isl_qpolynomial *opt_i;
1177 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1178 isl_set_copy(pw->p[i].set), max);
1179 if (max)
1180 opt = isl_qpolynomial_max_cst(opt, opt_i);
1181 else
1182 opt = isl_qpolynomial_min_cst(opt, opt_i);
1183 }
1184
1185 FN(PW,free)(pw);
1186 return opt;
1187 }
1188
1189 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
1190 {
1191 return FN(PW,opt)(pw, 1);
1192 }
1193
1194 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
1195 {
1196 return FN(PW,opt)(pw, 0);
1197 }
1198 #endif
1199
1200 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1201 {
1202 return pw ? isl_space_copy(pw->dim) : NULL;
1203 }
1204
1205 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1206 {
1207 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1208 }
1209
1210 #ifndef NO_RESET_DIM
1211 /* Reset the space of "pw". Since we don't know if the elements
1212 * represent the spaces themselves or their domains, we pass along
1213 * both when we call their reset_space_and_domain.
1214 */
1215 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1216 __isl_take isl_space *space, __isl_take isl_space *domain)
1217 {
1218 int i;
1219
1220 pw = FN(PW,cow)(pw);
1221 if (!pw || !space || !domain)
1222 goto error;
1223
1224 for (i = 0; i < pw->n; ++i) {
1225 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1226 isl_space_copy(domain));
1227 if (!pw->p[i].set)
1228 goto error;
1229 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1230 isl_space_copy(space), isl_space_copy(domain));
1231 if (!pw->p[i].FIELD)
1232 goto error;
1233 }
1234
1235 isl_space_free(domain);
1236
1237 isl_space_free(pw->dim);
1238 pw->dim = space;
1239
1240 return pw;
1241 error:
1242 isl_space_free(domain);
1243 isl_space_free(space);
1244 FN(PW,free)(pw);
1245 return NULL;
1246 }
1247
1248 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1249 __isl_take isl_space *domain)
1250 {
1251 isl_space *space;
1252
1253 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1254 FN(PW,get_space)(pw));
1255 return FN(PW,reset_space_and_domain)(pw, space, domain);
1256 }
1257
1258 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1259 {
1260 isl_space *domain;
1261
1262 domain = isl_space_domain(isl_space_copy(dim));
1263 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1264 }
1265
1266 __isl_give PW *FN(PW,set_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type,
1267 __isl_take isl_id *id)
1268 {
1269 isl_space *space;
1270
1271 pw = FN(PW,cow)(pw);
1272 if (!pw)
1273 return isl_id_free(id);
1274
1275 space = FN(PW,get_space)(pw);
1276 space = isl_space_set_tuple_id(space, type, id);
1277
1278 return FN(PW,reset_space)(pw, space);
1279 }
1280
1281 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1282 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1283 {
1284 pw = FN(PW,cow)(pw);
1285 if (!pw)
1286 return isl_id_free(id);
1287 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1288 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1289 }
1290 #endif
1291
1292 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1293 {
1294 if (!pw1 || !pw2)
1295 return -1;
1296
1297 return isl_space_is_equal(pw1->dim, pw2->dim);
1298 }
1299
1300 #ifndef NO_MORPH
1301 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1302 __isl_take isl_morph *morph)
1303 {
1304 int i;
1305 isl_ctx *ctx;
1306
1307 if (!pw || !morph)
1308 goto error;
1309
1310 ctx = isl_space_get_ctx(pw->dim);
1311 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim),
1312 goto error);
1313
1314 pw = FN(PW,cow)(pw);
1315 if (!pw)
1316 goto error;
1317 pw->dim = isl_space_extend_domain_with_range(
1318 isl_space_copy(morph->ran->dim), pw->dim);
1319 if (!pw->dim)
1320 goto error;
1321
1322 for (i = 0; i < pw->n; ++i) {
1323 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1324 if (!pw->p[i].set)
1325 goto error;
1326 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1327 isl_morph_copy(morph));
1328 if (!pw->p[i].FIELD)
1329 goto error;
1330 }
1331
1332 isl_morph_free(morph);
1333
1334 return pw;
1335 error:
1336 FN(PW,free)(pw);
1337 isl_morph_free(morph);
1338 return NULL;
1339 }
1340 #endif
1341
1342 int FN(PW,n_piece)(__isl_keep PW *pw)
1343 {
1344 return pw ? pw->n : 0;
1345 }
1346
1347 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1348 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1349 void *user)
1350 {
1351 int i;
1352
1353 if (!pw)
1354 return -1;
1355
1356 for (i = 0; i < pw->n; ++i)
1357 if (fn(isl_set_copy(pw->p[i].set),
1358 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1359 return -1;
1360
1361 return 0;
1362 }
1363
1364 #ifndef NO_LIFT
1365 static int any_divs(__isl_keep isl_set *set)
1366 {
1367 int i;
1368
1369 if (!set)
1370 return -1;
1371
1372 for (i = 0; i < set->n; ++i)
1373 if (set->p[i]->n_div > 0)
1374 return 1;
1375
1376 return 0;
1377 }
1378
1379 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1380 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1381 void *user), void *user)
1382 {
1383 int i;
1384
1385 if (!set || !el)
1386 goto error;
1387
1388 for (i = 0; i < set->n; ++i) {
1389 isl_set *lift;
1390 EL *copy;
1391
1392 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1393 lift = isl_set_lift(lift);
1394
1395 copy = FN(EL,copy)(el);
1396 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1397
1398 if (fn(lift, copy, user) < 0)
1399 goto error;
1400 }
1401
1402 isl_set_free(set);
1403 FN(EL,free)(el);
1404
1405 return 0;
1406 error:
1407 isl_set_free(set);
1408 FN(EL,free)(el);
1409 return -1;
1410 }
1411
1412 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1413 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1414 void *user), void *user)
1415 {
1416 int i;
1417
1418 if (!pw)
1419 return -1;
1420
1421 for (i = 0; i < pw->n; ++i) {
1422 isl_set *set;
1423 EL *el;
1424
1425 set = isl_set_copy(pw->p[i].set);
1426 el = FN(EL,copy)(pw->p[i].FIELD);
1427 if (!any_divs(set)) {
1428 if (fn(set, el, user) < 0)
1429 return -1;
1430 continue;
1431 }
1432 if (foreach_lifted_subset(set, el, fn, user) < 0)
1433 return -1;
1434 }
1435
1436 return 0;
1437 }
1438 #endif
1439
1440 #ifndef NO_MOVE_DIMS
1441 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1442 enum isl_dim_type dst_type, unsigned dst_pos,
1443 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1444 {
1445 int i;
1446
1447 pw = FN(PW,cow)(pw);
1448 if (!pw)
1449 return NULL;
1450
1451 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1452 if (!pw->dim)
1453 goto error;
1454
1455 for (i = 0; i < pw->n; ++i) {
1456 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1457 dst_type, dst_pos, src_type, src_pos, n);
1458 if (!pw->p[i].FIELD)
1459 goto error;
1460 }
1461
1462 if (dst_type == isl_dim_in)
1463 dst_type = isl_dim_set;
1464 if (src_type == isl_dim_in)
1465 src_type = isl_dim_set;
1466
1467 for (i = 0; i < pw->n; ++i) {
1468 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1469 dst_type, dst_pos,
1470 src_type, src_pos, n);
1471 if (!pw->p[i].set)
1472 goto error;
1473 }
1474
1475 return pw;
1476 error:
1477 FN(PW,free)(pw);
1478 return NULL;
1479 }
1480 #endif
1481
1482 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1483 {
1484 int i;
1485
1486 if (isl_int_is_one(v))
1487 return pw;
1488 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1489 PW *zero;
1490 isl_space *dim = FN(PW,get_space)(pw);
1491 #ifdef HAS_TYPE
1492 zero = FN(PW,ZERO)(dim, pw->type);
1493 #else
1494 zero = FN(PW,ZERO)(dim);
1495 #endif
1496 FN(PW,free)(pw);
1497 return zero;
1498 }
1499 pw = FN(PW,cow)(pw);
1500 if (!pw)
1501 return NULL;
1502 if (pw->n == 0)
1503 return pw;
1504
1505 #ifdef HAS_TYPE
1506 if (isl_int_is_neg(v))
1507 pw->type = isl_fold_type_negate(pw->type);
1508 #endif
1509 for (i = 0; i < pw->n; ++i) {
1510 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1511 if (!pw->p[i].FIELD)
1512 goto error;
1513 }
1514
1515 return pw;
1516 error:
1517 FN(PW,free)(pw);
1518 return NULL;
1519 }
1520
1521 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1522 {
1523 return FN(PW,mul_isl_int)(pw, v);
1524 }
1525
1526 static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2)
1527 {
1528 const isl_set *set1 = *(const isl_set **)p1;
1529 const isl_set *set2 = *(const isl_set **)p2;
1530
1531 return isl_set_plain_cmp(set1, set2);
1532 }
1533
1534 /* We normalize in place, but if anything goes wrong we need
1535 * to return NULL, so we need to make sure we don't change the
1536 * meaning of any possible other copies of map.
1537 */
1538 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1539 {
1540 int i, j;
1541 isl_set *set;
1542
1543 if (!pw)
1544 return NULL;
1545 for (i = 0; i < pw->n; ++i) {
1546 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1547 if (!set)
1548 return FN(PW,free)(pw);
1549 isl_set_free(pw->p[i].set);
1550 pw->p[i].set = set;
1551 }
1552 qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp));
1553 for (i = pw->n - 1; i >= 1; --i) {
1554 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set))
1555 continue;
1556 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1557 continue;
1558 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1559 isl_set_copy(pw->p[i].set));
1560 if (!set)
1561 return FN(PW,free)(pw);
1562 isl_set_free(pw->p[i].set);
1563 FN(EL,free)(pw->p[i].FIELD);
1564 isl_set_free(pw->p[i - 1].set);
1565 pw->p[i - 1].set = set;
1566 for (j = i + 1; j < pw->n; ++j)
1567 pw->p[j - 1] = pw->p[j];
1568 pw->n--;
1569 }
1570
1571 return pw;
1572 }
1573
1574 /* Is pw1 obviously equal to pw2?
1575 * That is, do they have obviously identical cells and obviously identical
1576 * elements on each cell?
1577 */
1578 int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1579 {
1580 int i;
1581 int equal;
1582
1583 if (!pw1 || !pw2)
1584 return -1;
1585
1586 if (pw1 == pw2)
1587 return 1;
1588 if (!isl_space_is_equal(pw1->dim, pw2->dim))
1589 return 0;
1590
1591 pw1 = FN(PW,copy)(pw1);
1592 pw2 = FN(PW,copy)(pw2);
1593 pw1 = FN(PW,normalize)(pw1);
1594 pw2 = FN(PW,normalize)(pw2);
1595 if (!pw1 || !pw2)
1596 goto error;
1597
1598 equal = pw1->n == pw2->n;
1599 for (i = 0; equal && i < pw1->n; ++i) {
1600 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1601 if (equal < 0)
1602 goto error;
1603 if (!equal)
1604 break;
1605 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1606 if (equal < 0)
1607 goto error;
1608 }
1609
1610 FN(PW,free)(pw1);
1611 FN(PW,free)(pw2);
1612 return equal;
1613 error:
1614 FN(PW,free)(pw1);
1615 FN(PW,free)(pw2);
1616 return -1;
1617 }
Integer set library