?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_pw_aff_set_rational
[isl.git] / isl_pw_templ.c
blob6830cf20ba7cced6129a772ab21c52bc4d7862f5
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 isl_set *set_i;
806 int empty;
807
808 set_i = isl_set_intersect(isl_set_copy(pw->p[i].set),
809 isl_set_copy(context));
810 empty = isl_set_plain_is_empty(set_i);
811 pw->p[i].FIELD = fn_el(pw->p[i].FIELD, set_i);
812 pw->p[i].set = fn_dom(pw->p[i].set, isl_basic_set_copy(hull));
813 if (!pw->p[i].FIELD || !pw->p[i].set)
814 goto error;
815 if (empty) {
816 isl_set_free(pw->p[i].set);
817 FN(EL,free)(pw->p[i].FIELD);
818 if (i != pw->n - 1)
819 pw->p[i] = pw->p[pw->n - 1];
820 pw->n--;
821 }
822 }
823
824 isl_basic_set_free(hull);
825 isl_set_free(context);
826
827 return pw;
828 error:
829 FN(PW,free)(pw);
830 isl_basic_set_free(hull);
831 isl_set_free(context);
832 return NULL;
833 }
834
835 static __isl_give PW *FN(PW,gist_domain_aligned)(__isl_take PW *pw,
836 __isl_take isl_set *set)
837 {
838 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist),
839 &isl_set_gist_basic_set);
840 }
841
842 __isl_give PW *FN(PW,gist)(__isl_take PW *pw, __isl_take isl_set *context)
843 {
844 return FN(PW,align_params_pw_set_and)(pw, context,
845 &FN(PW,gist_domain_aligned));
846 }
847
848 static __isl_give PW *FN(PW,gist_params_aligned)(__isl_take PW *pw,
849 __isl_take isl_set *set)
850 {
851 return FN(PW,gist_aligned)(pw, set, &FN(EL,gist_params),
852 &isl_set_gist_params_basic_set);
853 }
854
855 __isl_give PW *FN(PW,gist_params)(__isl_take PW *pw,
856 __isl_take isl_set *context)
857 {
858 return FN(PW,align_params_pw_set_and)(pw, context,
859 &FN(PW,gist_params_aligned));
860 }
861
862 __isl_give PW *FN(PW,coalesce)(__isl_take PW *pw)
863 {
864 int i, j;
865
866 if (!pw)
867 return NULL;
868 if (pw->n == 0)
869 return pw;
870
871 for (i = pw->n - 1; i >= 0; --i) {
872 for (j = i - 1; j >= 0; --j) {
873 if (!FN(EL,plain_is_equal)(pw->p[i].FIELD,
874 pw->p[j].FIELD))
875 continue;
876 pw->p[j].set = isl_set_union(pw->p[j].set,
877 pw->p[i].set);
878 FN(EL,free)(pw->p[i].FIELD);
879 if (i != pw->n - 1)
880 pw->p[i] = pw->p[pw->n - 1];
881 pw->n--;
882 break;
883 }
884 if (j >= 0)
885 continue;
886 pw->p[i].set = isl_set_coalesce(pw->p[i].set);
887 if (!pw->p[i].set)
888 goto error;
889 }
890
891 return pw;
892 error:
893 FN(PW,free)(pw);
894 return NULL;
895 }
896
897 isl_ctx *FN(PW,get_ctx)(__isl_keep PW *pw)
898 {
899 return pw ? isl_space_get_ctx(pw->dim) : NULL;
900 }
901
902 #ifndef NO_INVOLVES_DIMS
903 int FN(PW,involves_dims)(__isl_keep PW *pw, enum isl_dim_type type,
904 unsigned first, unsigned n)
905 {
906 int i;
907 enum isl_dim_type set_type;
908
909 if (!pw)
910 return -1;
911 if (pw->n == 0 || n == 0)
912 return 0;
913
914 set_type = type == isl_dim_in ? isl_dim_set : type;
915
916 for (i = 0; i < pw->n; ++i) {
917 int involves = FN(EL,involves_dims)(pw->p[i].FIELD,
918 type, first, n);
919 if (involves < 0 || involves)
920 return involves;
921 involves = isl_set_involves_dims(pw->p[i].set,
922 set_type, first, n);
923 if (involves < 0 || involves)
924 return involves;
925 }
926 return 0;
927 }
928 #endif
929
930 __isl_give PW *FN(PW,set_dim_name)(__isl_take PW *pw,
931 enum isl_dim_type type, unsigned pos, const char *s)
932 {
933 int i;
934 enum isl_dim_type set_type;
935
936 pw = FN(PW,cow)(pw);
937 if (!pw)
938 return NULL;
939
940 set_type = type == isl_dim_in ? isl_dim_set : type;
941
942 pw->dim = isl_space_set_dim_name(pw->dim, type, pos, s);
943 if (!pw->dim)
944 goto error;
945
946 for (i = 0; i < pw->n; ++i) {
947 pw->p[i].set = isl_set_set_dim_name(pw->p[i].set,
948 set_type, pos, s);
949 if (!pw->p[i].set)
950 goto error;
951 pw->p[i].FIELD = FN(EL,set_dim_name)(pw->p[i].FIELD, type, pos, s);
952 if (!pw->p[i].FIELD)
953 goto error;
954 }
955
956 return pw;
957 error:
958 FN(PW,free)(pw);
959 return NULL;
960 }
961
962 #ifndef NO_DROP_DIMS
963 __isl_give PW *FN(PW,drop_dims)(__isl_take PW *pw,
964 enum isl_dim_type type, unsigned first, unsigned n)
965 {
966 int i;
967 enum isl_dim_type set_type;
968
969 if (!pw)
970 return NULL;
971 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
972 return pw;
973
974 set_type = type == isl_dim_in ? isl_dim_set : type;
975
976 pw = FN(PW,cow)(pw);
977 if (!pw)
978 return NULL;
979 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
980 if (!pw->dim)
981 goto error;
982 for (i = 0; i < pw->n; ++i) {
983 pw->p[i].set = isl_set_drop(pw->p[i].set, set_type, first, n);
984 if (!pw->p[i].set)
985 goto error;
986 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
987 if (!pw->p[i].FIELD)
988 goto error;
989 }
990
991 return pw;
992 error:
993 FN(PW,free)(pw);
994 return NULL;
995 }
996
997 /* This function is very similar to drop_dims.
998 * The only difference is that the cells may still involve
999 * the specified dimensions. They are removed using
1000 * isl_set_project_out instead of isl_set_drop.
1001 */
1002 __isl_give PW *FN(PW,project_out)(__isl_take PW *pw,
1003 enum isl_dim_type type, unsigned first, unsigned n)
1004 {
1005 int i;
1006 enum isl_dim_type set_type;
1007
1008 if (!pw)
1009 return NULL;
1010 if (n == 0 && !isl_space_get_tuple_name(pw->dim, type))
1011 return pw;
1012
1013 set_type = type == isl_dim_in ? isl_dim_set : type;
1014
1015 pw = FN(PW,cow)(pw);
1016 if (!pw)
1017 return NULL;
1018 pw->dim = isl_space_drop_dims(pw->dim, type, first, n);
1019 if (!pw->dim)
1020 goto error;
1021 for (i = 0; i < pw->n; ++i) {
1022 pw->p[i].set = isl_set_project_out(pw->p[i].set,
1023 set_type, first, n);
1024 if (!pw->p[i].set)
1025 goto error;
1026 pw->p[i].FIELD = FN(EL,drop_dims)(pw->p[i].FIELD, type, first, n);
1027 if (!pw->p[i].FIELD)
1028 goto error;
1029 }
1030
1031 return pw;
1032 error:
1033 FN(PW,free)(pw);
1034 return NULL;
1035 }
1036
1037 /* Project the domain of pw onto its parameter space.
1038 */
1039 __isl_give PW *FN(PW,project_domain_on_params)(__isl_take PW *pw)
1040 {
1041 isl_space *space;
1042 unsigned n;
1043
1044 n = FN(PW,dim)(pw, isl_dim_in);
1045 pw = FN(PW,project_out)(pw, isl_dim_in, 0, n);
1046 space = FN(PW,get_domain_space)(pw);
1047 space = isl_space_params(space);
1048 pw = FN(PW,reset_domain_space)(pw, space);
1049 return pw;
1050 }
1051 #endif
1052
1053 #ifndef NO_INSERT_DIMS
1054 __isl_give PW *FN(PW,insert_dims)(__isl_take PW *pw, enum isl_dim_type type,
1055 unsigned first, unsigned n)
1056 {
1057 int i;
1058 enum isl_dim_type set_type;
1059
1060 if (!pw)
1061 return NULL;
1062 if (n == 0 && !isl_space_is_named_or_nested(pw->dim, type))
1063 return pw;
1064
1065 set_type = type == isl_dim_in ? isl_dim_set : type;
1066
1067 pw = FN(PW,cow)(pw);
1068 if (!pw)
1069 return NULL;
1070
1071 pw->dim = isl_space_insert_dims(pw->dim, type, first, n);
1072 if (!pw->dim)
1073 goto error;
1074
1075 for (i = 0; i < pw->n; ++i) {
1076 pw->p[i].set = isl_set_insert_dims(pw->p[i].set,
1077 set_type, first, n);
1078 if (!pw->p[i].set)
1079 goto error;
1080 pw->p[i].FIELD = FN(EL,insert_dims)(pw->p[i].FIELD,
1081 type, first, n);
1082 if (!pw->p[i].FIELD)
1083 goto error;
1084 }
1085
1086 return pw;
1087 error:
1088 FN(PW,free)(pw);
1089 return NULL;
1090 }
1091 #endif
1092
1093 __isl_give PW *FN(PW,fix_dim)(__isl_take PW *pw,
1094 enum isl_dim_type type, unsigned pos, isl_int v)
1095 {
1096 int i;
1097
1098 if (!pw)
1099 return NULL;
1100
1101 if (type == isl_dim_in)
1102 type = isl_dim_set;
1103
1104 pw = FN(PW,cow)(pw);
1105 if (!pw)
1106 return NULL;
1107 for (i = 0; i < pw->n; ++i) {
1108 pw->p[i].set = isl_set_fix(pw->p[i].set, type, pos, v);
1109 if (!pw->p[i].set)
1110 goto error;
1111 }
1112
1113 return pw;
1114 error:
1115 FN(PW,free)(pw);
1116 return NULL;
1117 }
1118
1119 unsigned FN(PW,dim)(__isl_keep PW *pw, enum isl_dim_type type)
1120 {
1121 return pw ? isl_space_dim(pw->dim, type) : 0;
1122 }
1123
1124 __isl_give PW *FN(PW,split_dims)(__isl_take PW *pw,
1125 enum isl_dim_type type, unsigned first, unsigned n)
1126 {
1127 int i;
1128
1129 if (!pw)
1130 return NULL;
1131 if (n == 0)
1132 return pw;
1133
1134 if (type == isl_dim_in)
1135 type = isl_dim_set;
1136
1137 pw = FN(PW,cow)(pw);
1138 if (!pw)
1139 return NULL;
1140 if (!pw->dim)
1141 goto error;
1142 for (i = 0; i < pw->n; ++i) {
1143 pw->p[i].set = isl_set_split_dims(pw->p[i].set, type, first, n);
1144 if (!pw->p[i].set)
1145 goto error;
1146 }
1147
1148 return pw;
1149 error:
1150 FN(PW,free)(pw);
1151 return NULL;
1152 }
1153
1154 #ifndef NO_OPT
1155 /* Compute the maximal value attained by the piecewise quasipolynomial
1156 * on its domain or zero if the domain is empty.
1157 * In the worst case, the domain is scanned completely,
1158 * so the domain is assumed to be bounded.
1159 */
1160 __isl_give isl_qpolynomial *FN(PW,opt)(__isl_take PW *pw, int max)
1161 {
1162 int i;
1163 isl_qpolynomial *opt;
1164
1165 if (!pw)
1166 return NULL;
1167
1168 if (pw->n == 0) {
1169 isl_space *dim = isl_space_copy(pw->dim);
1170 FN(PW,free)(pw);
1171 return isl_qpolynomial_zero_on_domain(isl_space_domain(dim));
1172 }
1173
1174 opt = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[0].FIELD),
1175 isl_set_copy(pw->p[0].set), max);
1176 for (i = 1; i < pw->n; ++i) {
1177 isl_qpolynomial *opt_i;
1178 opt_i = FN(EL,opt_on_domain)(FN(EL,copy)(pw->p[i].FIELD),
1179 isl_set_copy(pw->p[i].set), max);
1180 if (max)
1181 opt = isl_qpolynomial_max_cst(opt, opt_i);
1182 else
1183 opt = isl_qpolynomial_min_cst(opt, opt_i);
1184 }
1185
1186 FN(PW,free)(pw);
1187 return opt;
1188 }
1189
1190 __isl_give isl_qpolynomial *FN(PW,max)(__isl_take PW *pw)
1191 {
1192 return FN(PW,opt)(pw, 1);
1193 }
1194
1195 __isl_give isl_qpolynomial *FN(PW,min)(__isl_take PW *pw)
1196 {
1197 return FN(PW,opt)(pw, 0);
1198 }
1199 #endif
1200
1201 __isl_give isl_space *FN(PW,get_space)(__isl_keep PW *pw)
1202 {
1203 return pw ? isl_space_copy(pw->dim) : NULL;
1204 }
1205
1206 __isl_give isl_space *FN(PW,get_domain_space)(__isl_keep PW *pw)
1207 {
1208 return pw ? isl_space_domain(isl_space_copy(pw->dim)) : NULL;
1209 }
1210
1211 #ifndef NO_RESET_DIM
1212 /* Reset the space of "pw". Since we don't know if the elements
1213 * represent the spaces themselves or their domains, we pass along
1214 * both when we call their reset_space_and_domain.
1215 */
1216 static __isl_give PW *FN(PW,reset_space_and_domain)(__isl_take PW *pw,
1217 __isl_take isl_space *space, __isl_take isl_space *domain)
1218 {
1219 int i;
1220
1221 pw = FN(PW,cow)(pw);
1222 if (!pw || !space || !domain)
1223 goto error;
1224
1225 for (i = 0; i < pw->n; ++i) {
1226 pw->p[i].set = isl_set_reset_space(pw->p[i].set,
1227 isl_space_copy(domain));
1228 if (!pw->p[i].set)
1229 goto error;
1230 pw->p[i].FIELD = FN(EL,reset_space_and_domain)(pw->p[i].FIELD,
1231 isl_space_copy(space), isl_space_copy(domain));
1232 if (!pw->p[i].FIELD)
1233 goto error;
1234 }
1235
1236 isl_space_free(domain);
1237
1238 isl_space_free(pw->dim);
1239 pw->dim = space;
1240
1241 return pw;
1242 error:
1243 isl_space_free(domain);
1244 isl_space_free(space);
1245 FN(PW,free)(pw);
1246 return NULL;
1247 }
1248
1249 __isl_give PW *FN(PW,reset_domain_space)(__isl_take PW *pw,
1250 __isl_take isl_space *domain)
1251 {
1252 isl_space *space;
1253
1254 space = isl_space_extend_domain_with_range(isl_space_copy(domain),
1255 FN(PW,get_space)(pw));
1256 return FN(PW,reset_space_and_domain)(pw, space, domain);
1257 }
1258
1259 __isl_give PW *FN(PW,reset_space)(__isl_take PW *pw, __isl_take isl_space *dim)
1260 {
1261 isl_space *domain;
1262
1263 domain = isl_space_domain(isl_space_copy(dim));
1264 return FN(PW,reset_space_and_domain)(pw, dim, domain);
1265 }
1266
1267 __isl_give PW *FN(PW,set_tuple_id)(__isl_keep PW *pw, enum isl_dim_type type,
1268 __isl_take isl_id *id)
1269 {
1270 isl_space *space;
1271
1272 pw = FN(PW,cow)(pw);
1273 if (!pw)
1274 return isl_id_free(id);
1275
1276 space = FN(PW,get_space)(pw);
1277 space = isl_space_set_tuple_id(space, type, id);
1278
1279 return FN(PW,reset_space)(pw, space);
1280 }
1281
1282 __isl_give PW *FN(PW,set_dim_id)(__isl_take PW *pw,
1283 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1284 {
1285 pw = FN(PW,cow)(pw);
1286 if (!pw)
1287 return isl_id_free(id);
1288 pw->dim = isl_space_set_dim_id(pw->dim, type, pos, id);
1289 return FN(PW,reset_space)(pw, isl_space_copy(pw->dim));
1290 }
1291 #endif
1292
1293 int FN(PW,has_equal_space)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1294 {
1295 if (!pw1 || !pw2)
1296 return -1;
1297
1298 return isl_space_is_equal(pw1->dim, pw2->dim);
1299 }
1300
1301 #ifndef NO_MORPH
1302 __isl_give PW *FN(PW,morph_domain)(__isl_take PW *pw,
1303 __isl_take isl_morph *morph)
1304 {
1305 int i;
1306 isl_ctx *ctx;
1307
1308 if (!pw || !morph)
1309 goto error;
1310
1311 ctx = isl_space_get_ctx(pw->dim);
1312 isl_assert(ctx, isl_space_is_domain_internal(morph->dom->dim, pw->dim),
1313 goto error);
1314
1315 pw = FN(PW,cow)(pw);
1316 if (!pw)
1317 goto error;
1318 pw->dim = isl_space_extend_domain_with_range(
1319 isl_space_copy(morph->ran->dim), pw->dim);
1320 if (!pw->dim)
1321 goto error;
1322
1323 for (i = 0; i < pw->n; ++i) {
1324 pw->p[i].set = isl_morph_set(isl_morph_copy(morph), pw->p[i].set);
1325 if (!pw->p[i].set)
1326 goto error;
1327 pw->p[i].FIELD = FN(EL,morph_domain)(pw->p[i].FIELD,
1328 isl_morph_copy(morph));
1329 if (!pw->p[i].FIELD)
1330 goto error;
1331 }
1332
1333 isl_morph_free(morph);
1334
1335 return pw;
1336 error:
1337 FN(PW,free)(pw);
1338 isl_morph_free(morph);
1339 return NULL;
1340 }
1341 #endif
1342
1343 int FN(PW,n_piece)(__isl_keep PW *pw)
1344 {
1345 return pw ? pw->n : 0;
1346 }
1347
1348 int FN(PW,foreach_piece)(__isl_keep PW *pw,
1349 int (*fn)(__isl_take isl_set *set, __isl_take EL *el, void *user),
1350 void *user)
1351 {
1352 int i;
1353
1354 if (!pw)
1355 return -1;
1356
1357 for (i = 0; i < pw->n; ++i)
1358 if (fn(isl_set_copy(pw->p[i].set),
1359 FN(EL,copy)(pw->p[i].FIELD), user) < 0)
1360 return -1;
1361
1362 return 0;
1363 }
1364
1365 #ifndef NO_LIFT
1366 static int any_divs(__isl_keep isl_set *set)
1367 {
1368 int i;
1369
1370 if (!set)
1371 return -1;
1372
1373 for (i = 0; i < set->n; ++i)
1374 if (set->p[i]->n_div > 0)
1375 return 1;
1376
1377 return 0;
1378 }
1379
1380 static int foreach_lifted_subset(__isl_take isl_set *set, __isl_take EL *el,
1381 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1382 void *user), void *user)
1383 {
1384 int i;
1385
1386 if (!set || !el)
1387 goto error;
1388
1389 for (i = 0; i < set->n; ++i) {
1390 isl_set *lift;
1391 EL *copy;
1392
1393 lift = isl_set_from_basic_set(isl_basic_set_copy(set->p[i]));
1394 lift = isl_set_lift(lift);
1395
1396 copy = FN(EL,copy)(el);
1397 copy = FN(EL,lift)(copy, isl_set_get_space(lift));
1398
1399 if (fn(lift, copy, user) < 0)
1400 goto error;
1401 }
1402
1403 isl_set_free(set);
1404 FN(EL,free)(el);
1405
1406 return 0;
1407 error:
1408 isl_set_free(set);
1409 FN(EL,free)(el);
1410 return -1;
1411 }
1412
1413 int FN(PW,foreach_lifted_piece)(__isl_keep PW *pw,
1414 int (*fn)(__isl_take isl_set *set, __isl_take EL *el,
1415 void *user), void *user)
1416 {
1417 int i;
1418
1419 if (!pw)
1420 return -1;
1421
1422 for (i = 0; i < pw->n; ++i) {
1423 isl_set *set;
1424 EL *el;
1425
1426 set = isl_set_copy(pw->p[i].set);
1427 el = FN(EL,copy)(pw->p[i].FIELD);
1428 if (!any_divs(set)) {
1429 if (fn(set, el, user) < 0)
1430 return -1;
1431 continue;
1432 }
1433 if (foreach_lifted_subset(set, el, fn, user) < 0)
1434 return -1;
1435 }
1436
1437 return 0;
1438 }
1439 #endif
1440
1441 #ifndef NO_MOVE_DIMS
1442 __isl_give PW *FN(PW,move_dims)(__isl_take PW *pw,
1443 enum isl_dim_type dst_type, unsigned dst_pos,
1444 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1445 {
1446 int i;
1447
1448 pw = FN(PW,cow)(pw);
1449 if (!pw)
1450 return NULL;
1451
1452 pw->dim = isl_space_move_dims(pw->dim, dst_type, dst_pos, src_type, src_pos, n);
1453 if (!pw->dim)
1454 goto error;
1455
1456 for (i = 0; i < pw->n; ++i) {
1457 pw->p[i].FIELD = FN(EL,move_dims)(pw->p[i].FIELD,
1458 dst_type, dst_pos, src_type, src_pos, n);
1459 if (!pw->p[i].FIELD)
1460 goto error;
1461 }
1462
1463 if (dst_type == isl_dim_in)
1464 dst_type = isl_dim_set;
1465 if (src_type == isl_dim_in)
1466 src_type = isl_dim_set;
1467
1468 for (i = 0; i < pw->n; ++i) {
1469 pw->p[i].set = isl_set_move_dims(pw->p[i].set,
1470 dst_type, dst_pos,
1471 src_type, src_pos, n);
1472 if (!pw->p[i].set)
1473 goto error;
1474 }
1475
1476 return pw;
1477 error:
1478 FN(PW,free)(pw);
1479 return NULL;
1480 }
1481 #endif
1482
1483 __isl_give PW *FN(PW,mul_isl_int)(__isl_take PW *pw, isl_int v)
1484 {
1485 int i;
1486
1487 if (isl_int_is_one(v))
1488 return pw;
1489 if (pw && DEFAULT_IS_ZERO && isl_int_is_zero(v)) {
1490 PW *zero;
1491 isl_space *dim = FN(PW,get_space)(pw);
1492 #ifdef HAS_TYPE
1493 zero = FN(PW,ZERO)(dim, pw->type);
1494 #else
1495 zero = FN(PW,ZERO)(dim);
1496 #endif
1497 FN(PW,free)(pw);
1498 return zero;
1499 }
1500 pw = FN(PW,cow)(pw);
1501 if (!pw)
1502 return NULL;
1503 if (pw->n == 0)
1504 return pw;
1505
1506 #ifdef HAS_TYPE
1507 if (isl_int_is_neg(v))
1508 pw->type = isl_fold_type_negate(pw->type);
1509 #endif
1510 for (i = 0; i < pw->n; ++i) {
1511 pw->p[i].FIELD = FN(EL,scale)(pw->p[i].FIELD, v);
1512 if (!pw->p[i].FIELD)
1513 goto error;
1514 }
1515
1516 return pw;
1517 error:
1518 FN(PW,free)(pw);
1519 return NULL;
1520 }
1521
1522 __isl_give PW *FN(PW,scale)(__isl_take PW *pw, isl_int v)
1523 {
1524 return FN(PW,mul_isl_int)(pw, v);
1525 }
1526
1527 static int FN(PW,qsort_set_cmp)(const void *p1, const void *p2)
1528 {
1529 isl_set *set1 = *(isl_set * const *)p1;
1530 isl_set *set2 = *(isl_set * const *)p2;
1531
1532 return isl_set_plain_cmp(set1, set2);
1533 }
1534
1535 /* We normalize in place, but if anything goes wrong we need
1536 * to return NULL, so we need to make sure we don't change the
1537 * meaning of any possible other copies of map.
1538 */
1539 __isl_give PW *FN(PW,normalize)(__isl_take PW *pw)
1540 {
1541 int i, j;
1542 isl_set *set;
1543
1544 if (!pw)
1545 return NULL;
1546 for (i = 0; i < pw->n; ++i) {
1547 set = isl_set_normalize(isl_set_copy(pw->p[i].set));
1548 if (!set)
1549 return FN(PW,free)(pw);
1550 isl_set_free(pw->p[i].set);
1551 pw->p[i].set = set;
1552 }
1553 qsort(pw->p, pw->n, sizeof(pw->p[0]), &FN(PW,qsort_set_cmp));
1554 for (i = pw->n - 1; i >= 1; --i) {
1555 if (!isl_set_plain_is_equal(pw->p[i - 1].set, pw->p[i].set))
1556 continue;
1557 if (!FN(EL,plain_is_equal)(pw->p[i - 1].FIELD, pw->p[i].FIELD))
1558 continue;
1559 set = isl_set_union(isl_set_copy(pw->p[i - 1].set),
1560 isl_set_copy(pw->p[i].set));
1561 if (!set)
1562 return FN(PW,free)(pw);
1563 isl_set_free(pw->p[i].set);
1564 FN(EL,free)(pw->p[i].FIELD);
1565 isl_set_free(pw->p[i - 1].set);
1566 pw->p[i - 1].set = set;
1567 for (j = i + 1; j < pw->n; ++j)
1568 pw->p[j - 1] = pw->p[j];
1569 pw->n--;
1570 }
1571
1572 return pw;
1573 }
1574
1575 /* Is pw1 obviously equal to pw2?
1576 * That is, do they have obviously identical cells and obviously identical
1577 * elements on each cell?
1578 */
1579 int FN(PW,plain_is_equal)(__isl_keep PW *pw1, __isl_keep PW *pw2)
1580 {
1581 int i;
1582 int equal;
1583
1584 if (!pw1 || !pw2)
1585 return -1;
1586
1587 if (pw1 == pw2)
1588 return 1;
1589 if (!isl_space_is_equal(pw1->dim, pw2->dim))
1590 return 0;
1591
1592 pw1 = FN(PW,copy)(pw1);
1593 pw2 = FN(PW,copy)(pw2);
1594 pw1 = FN(PW,normalize)(pw1);
1595 pw2 = FN(PW,normalize)(pw2);
1596 if (!pw1 || !pw2)
1597 goto error;
1598
1599 equal = pw1->n == pw2->n;
1600 for (i = 0; equal && i < pw1->n; ++i) {
1601 equal = isl_set_plain_is_equal(pw1->p[i].set, pw2->p[i].set);
1602 if (equal < 0)
1603 goto error;
1604 if (!equal)
1605 break;
1606 equal = FN(EL,plain_is_equal)(pw1->p[i].FIELD, pw2->p[i].FIELD);
1607 if (equal < 0)
1608 goto error;
1609 }
1610
1611 FN(PW,free)(pw1);
1612 FN(PW,free)(pw2);
1613 return equal;
1614 error:
1615 FN(PW,free)(pw1);
1616 FN(PW,free)(pw2);
1617 return -1;
1618 }
Integer set library