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