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