?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_affine_hull.c: construct_column: return isl_stat
[isl.git] / isl_union_templ.c
blob7d5ccad72d5e032ab06834fd94755254dfbba45f
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 /* Return the space of "u".
21 */
22 static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u)
23 {
24 if (!u)
25 return NULL;
26 return u->space;
27 }
28
29 /* Return a copy of the space of "u".
30 */
31 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
32 {
33 return isl_space_copy(FN(UNION,peek_space)(u));
34 }
35
36 /* Return the number of parameters of "u", where "type"
37 * is required to be set to isl_dim_param.
38 */
39 unsigned FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
40 {
41 if (!u)
42 return 0;
43
44 if (type != isl_dim_param)
45 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
46 "can only reference parameters", return 0);
47
48 return isl_space_dim(u->space, type);
49 }
50
51 /* Return the position of the parameter with the given name
52 * in "u".
53 * Return -1 if no such dimension can be found.
54 */
55 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
56 const char *name)
57 {
58 if (!u)
59 return -1;
60 return isl_space_find_dim_by_name(u->space, type, name);
61 }
62
63 #ifdef HAS_TYPE
64 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space,
65 enum isl_fold type, int size)
66 #else
67 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space, int size)
68 #endif
69 {
70 UNION *u;
71
72 space = isl_space_params(space);
73 if (!space)
74 return NULL;
75
76 u = isl_calloc_type(space->ctx, UNION);
77 if (!u)
78 goto error;
79
80 u->ref = 1;
81 #ifdef HAS_TYPE
82 u->type = type;
83 #endif
84 u->space = space;
85 if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
86 return FN(UNION,free)(u);
87
88 return u;
89 error:
90 isl_space_free(space);
91 return NULL;
92 }
93
94 #ifdef HAS_TYPE
95 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
96 {
97 return FN(UNION,alloc)(dim, type, 16);
98 }
99 #else
100 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
101 {
102 return FN(UNION,alloc)(dim, 16);
103 }
104 #endif
105
106 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
107 {
108 if (!u)
109 return NULL;
110
111 u->ref++;
112 return u;
113 }
114
115 /* Extract the element of "u" living in "space" (ignoring parameters).
116 *
117 * Return the ZERO element if "u" does not contain any element
118 * living in "space".
119 */
120 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
121 __isl_take isl_space *space)
122 {
123 struct isl_hash_table_entry *entry;
124
125 space = isl_space_replace_params(space, FN(UNION,peek_space)(u));
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),BASE)(__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),BASE)(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),BASE)(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_reordering_get_space(r);
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_bool equal_params;
417 isl_reordering *r;
418
419 if (!u || !model)
420 goto error;
421
422 equal_params = isl_space_has_equal_params(u->space, model);
423 if (equal_params < 0)
424 goto error;
425 if (equal_params) {
426 isl_space_free(model);
427 return u;
428 }
429
430 r = isl_parameter_alignment_reordering(u->space, model);
431 isl_space_free(model);
432
433 return FN(UNION,realign_domain)(u, r);
434 error:
435 isl_space_free(model);
436 FN(UNION,free)(u);
437 return NULL;
438 }
439
440 /* Add "part" to *u, taking the union sum if "u" already has
441 * a part defined on the same space as "part".
442 */
443 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
444 {
445 UNION **u = (UNION **)user;
446
447 *u = FN(UNION,add_part_generic)(*u, part, 0);
448
449 return isl_stat_ok;
450 }
451
452 /* Compute the sum of "u1" and "u2" on the union of their domains,
453 * with the actual sum on the shared domain and
454 * the defined expression on the symmetric difference of the domains.
455 *
456 * This is an internal function that is exposed under different
457 * names depending on whether the base expressions have a zero default
458 * value.
459 * If they do, then this function is called "add".
460 * Otherwise, it is called "union_add".
461 */
462 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
463 __isl_take UNION *u2)
464 {
465 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
466 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
467
468 u1 = FN(UNION,cow)(u1);
469
470 if (!u1 || !u2)
471 goto error;
472
473 if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
474 goto error;
475
476 FN(UNION,free)(u2);
477
478 return u1;
479 error:
480 FN(UNION,free)(u1);
481 FN(UNION,free)(u2);
482 return NULL;
483 }
484
485 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
486 {
487 isl_space *space;
488 UNION *u;
489
490 if (!part)
491 return NULL;
492
493 space = FN(PART,get_space)(part);
494 space = isl_space_drop_dims(space, isl_dim_in, 0,
495 isl_space_dim(space, isl_dim_in));
496 space = isl_space_drop_dims(space, isl_dim_out, 0,
497 isl_space_dim(space, isl_dim_out));
498 #ifdef HAS_TYPE
499 u = FN(UNION,ZERO)(space, part->type);
500 #else
501 u = FN(UNION,ZERO)(space);
502 #endif
503 u = FN(FN(UNION,add),BASE)(u, part);
504
505 return u;
506 }
507
508 S(UNION,match_bin_data) {
509 UNION *u2;
510 UNION *res;
511 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
512 };
513
514 /* Check if data->u2 has an element living in the same space as "part".
515 * If so, call data->fn on the two elements and add the result to
516 * data->res.
517 */
518 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
519 {
520 S(UNION,match_bin_data) *data = user;
521 struct isl_hash_table_entry *entry2;
522 isl_space *space;
523 PART *part2;
524
525 space = FN(PART,get_space)(part);
526 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
527 isl_space_free(space);
528 if (!entry2)
529 goto error;
530 if (entry2 == isl_hash_table_entry_none) {
531 FN(PART,free)(part);
532 return isl_stat_ok;
533 }
534
535 part2 = entry2->data;
536 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
537 part2->dim, isl_dim_out))
538 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
539 "entries should have the same range space",
540 goto error);
541
542 part = data->fn(part, FN(PART, copy)(entry2->data));
543
544 data->res = FN(FN(UNION,add),BASE)(data->res, part);
545 if (!data->res)
546 return isl_stat_error;
547
548 return isl_stat_ok;
549 error:
550 FN(PART,free)(part);
551 return isl_stat_error;
552 }
553
554 /* This function is currently only used from isl_polynomial.c
555 * and not from isl_fold.c.
556 */
557 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
558 __isl_take UNION *u2,
559 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
560 __attribute__ ((unused));
561 /* For each pair of elements in "u1" and "u2" living in the same space,
562 * call "fn" and collect the results.
563 */
564 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
565 __isl_take UNION *u2,
566 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
567 {
568 S(UNION,match_bin_data) data = { NULL, NULL, fn };
569
570 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
571 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
572
573 if (!u1 || !u2)
574 goto error;
575
576 data.u2 = u2;
577 data.res = FN(UNION,alloc_same_size)(u1);
578 if (FN(FN(UNION,foreach),BASE)(u1,
579 &FN(UNION,match_bin_entry), &data) < 0)
580 goto error;
581
582 FN(UNION,free)(u1);
583 FN(UNION,free)(u2);
584 return data.res;
585 error:
586 FN(UNION,free)(u1);
587 FN(UNION,free)(u2);
588 FN(UNION,free)(data.res);
589 return NULL;
590 }
591
592 /* Compute the sum of "u1" and "u2".
593 *
594 * If the base expressions have a default zero value, then the sum
595 * is computed on the union of the domains of "u1" and "u2".
596 * Otherwise, it is computed on their shared domains.
597 */
598 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
599 {
600 #if DEFAULT_IS_ZERO
601 return FN(UNION,union_add_)(u1, u2);
602 #else
603 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
604 #endif
605 }
606
607 #ifndef NO_SUB
608 /* Subtract "u2" from "u1" and return the result.
609 */
610 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
611 {
612 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
613 }
614 #endif
615
616 S(UNION,any_set_data) {
617 isl_set *set;
618 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
619 };
620
621 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
622 void *user)
623 {
624 S(UNION,any_set_data) *data = user;
625
626 return data->fn(part, isl_set_copy(data->set));
627 }
628
629 /* Update each element of "u" by calling "fn" on the element and "set".
630 */
631 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
632 __isl_take isl_set *set,
633 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
634 {
635 S(UNION,any_set_data) data = { NULL, fn };
636
637 u = FN(UNION,align_params)(u, isl_set_get_space(set));
638 set = isl_set_align_params(set, FN(UNION,get_space)(u));
639
640 if (!u || !set)
641 goto error;
642
643 data.set = set;
644 u = FN(UNION,transform)(u, &FN(UNION,any_set_entry), &data);
645 isl_set_free(set);
646 return u;
647 error:
648 FN(UNION,free)(u);
649 isl_set_free(set);
650 return NULL;
651 }
652
653 /* Intersect the domain of "u" with the parameter domain "context".
654 */
655 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
656 __isl_take isl_set *set)
657 {
658 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
659 }
660
661 /* Compute the gist of the domain of "u" with respect to
662 * the parameter domain "context".
663 */
664 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
665 __isl_take isl_set *set)
666 {
667 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
668 }
669
670 S(UNION,match_domain_data) {
671 isl_union_set *uset;
672 UNION *res;
673 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
674 };
675
676 static int FN(UNION,set_has_space)(const void *entry, const void *val)
677 {
678 isl_set *set = (isl_set *)entry;
679 isl_space *space = (isl_space *)val;
680
681 return isl_space_is_equal(set->dim, space);
682 }
683
684 /* Find the set in data->uset that lives in the same space as the domain
685 * of "part", apply data->fn to *entry and this set (if any), and add
686 * the result to data->res.
687 */
688 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
689 {
690 S(UNION,match_domain_data) *data = user;
691 uint32_t hash;
692 struct isl_hash_table_entry *entry2;
693 isl_space *space;
694
695 space = FN(PART,get_domain_space)(part);
696 hash = isl_space_get_hash(space);
697 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
698 hash, &FN(UNION,set_has_space), space, 0);
699 isl_space_free(space);
700 if (!entry2) {
701 FN(PART,free)(part);
702 return isl_stat_ok;
703 }
704
705 part = data->fn(part, isl_set_copy(entry2->data));
706
707 data->res = FN(FN(UNION,add),BASE)(data->res, part);
708 if (!data->res)
709 return isl_stat_error;
710
711 return isl_stat_ok;
712 }
713
714 /* Apply fn to each pair of PW in u and set in uset such that
715 * the set lives in the same space as the domain of PW
716 * and collect the results.
717 */
718 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
719 __isl_take isl_union_set *uset,
720 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
721 {
722 S(UNION,match_domain_data) data = { NULL, NULL, fn };
723
724 u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
725 uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
726
727 if (!u || !uset)
728 goto error;
729
730 data.uset = uset;
731 data.res = FN(UNION,alloc_same_size)(u);
732 if (FN(FN(UNION,foreach),BASE)(u,
733 &FN(UNION,match_domain_entry), &data) < 0)
734 goto error;
735
736 FN(UNION,free)(u);
737 isl_union_set_free(uset);
738 return data.res;
739 error:
740 FN(UNION,free)(u);
741 isl_union_set_free(uset);
742 FN(UNION,free)(data.res);
743 return NULL;
744 }
745
746 /* Intersect the domain of "u" with "uset".
747 * If "uset" is a parameters domain, then intersect the parameter
748 * domain of "u" with this set.
749 */
750 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
751 __isl_take isl_union_set *uset)
752 {
753 if (isl_union_set_is_params(uset))
754 return FN(UNION,intersect_params)(u,
755 isl_set_from_union_set(uset));
756 return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
757 }
758
759 /* Take the set (which may be empty) in data->uset that lives
760 * in the same space as the domain of "pw", subtract it from the domain
761 * of "part" and return the result.
762 */
763 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
764 void *user)
765 {
766 isl_union_set *uset = user;
767 isl_space *space;
768 isl_set *set;
769
770 space = FN(PART,get_domain_space)(part);
771 set = isl_union_set_extract_set(uset, space);
772 return FN(PART,subtract_domain)(part, set);
773 }
774
775 /* Subtract "uset' from the domain of "u".
776 */
777 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
778 __isl_take isl_union_set *uset)
779 {
780 u = FN(UNION,transform)(u, &FN(UNION,subtract_domain_entry), uset);
781 isl_union_set_free(uset);
782 return u;
783 }
784
785 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
786 __isl_take isl_union_set *uset)
787 {
788 if (isl_union_set_is_params(uset))
789 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
790 return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
791 }
792
793 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
794 * Since the UNION may have several references, the entry is only
795 * replaced if the coalescing is successful.
796 */
797 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
798 {
799 PART **part_p = (PART **) entry;
800 PART *part;
801
802 part = FN(PART,copy)(*part_p);
803 part = FN(PW,coalesce)(part);
804 if (!part)
805 return isl_stat_error;
806 FN(PART,free)(*part_p);
807 *part_p = part;
808
809 return isl_stat_ok;
810 }
811
812 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
813 {
814 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
815 goto error;
816
817 return u;
818 error:
819 FN(UNION,free)(u);
820 return NULL;
821 }
822
823 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
824 {
825 isl_union_set **uset = (isl_union_set **)user;
826
827 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
828
829 return isl_stat_ok;
830 }
831
832 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
833 {
834 isl_union_set *uset;
835
836 uset = isl_union_set_empty(FN(UNION,get_space)(u));
837 if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
838 goto error;
839
840 FN(UNION,free)(u);
841
842 return uset;
843 error:
844 isl_union_set_free(uset);
845 FN(UNION,free)(u);
846 return NULL;
847 }
848
849 #ifdef HAS_TYPE
850 /* Negate the type of "u".
851 */
852 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
853 {
854 u = FN(UNION,cow)(u);
855 if (!u)
856 return NULL;
857 u->type = isl_fold_type_negate(u->type);
858 return u;
859 }
860 #else
861 /* Negate the type of "u".
862 * Since "u" does not have a type, do nothing.
863 */
864 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
865 {
866 return u;
867 }
868 #endif
869
870 /* Multiply "part" by the isl_val "user" and return the result.
871 */
872 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
873 void *user)
874 {
875 isl_val *v = user;
876
877 return FN(PART,scale_val)(part, isl_val_copy(v));
878 }
879
880 /* Multiply "u" by "v" and return the result.
881 */
882 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
883 __isl_take isl_val *v)
884 {
885 if (!u || !v)
886 goto error;
887 if (isl_val_is_one(v)) {
888 isl_val_free(v);
889 return u;
890 }
891
892 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
893 UNION *zero;
894 isl_space *space = FN(UNION,get_space)(u);
895 #ifdef HAS_TYPE
896 zero = FN(UNION,ZERO)(space, u->type);
897 #else
898 zero = FN(UNION,ZERO)(space);
899 #endif
900 FN(UNION,free)(u);
901 isl_val_free(v);
902 return zero;
903 }
904
905 if (!isl_val_is_rat(v))
906 isl_die(isl_val_get_ctx(v), isl_error_invalid,
907 "expecting rational factor", goto error);
908
909 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
910 if (isl_val_is_neg(v))
911 u = FN(UNION,negate_type)(u);
912
913 isl_val_free(v);
914 return u;
915 error:
916 isl_val_free(v);
917 FN(UNION,free)(u);
918 return NULL;
919 }
920
921 /* Divide "part" by the isl_val "user" and return the result.
922 */
923 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
924 void *user)
925 {
926 isl_val *v = user;
927
928 return FN(PART,scale_down_val)(part, isl_val_copy(v));
929 }
930
931 /* Divide "u" by "v" and return the result.
932 */
933 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
934 __isl_take isl_val *v)
935 {
936 if (!u || !v)
937 goto error;
938 if (isl_val_is_one(v)) {
939 isl_val_free(v);
940 return u;
941 }
942
943 if (!isl_val_is_rat(v))
944 isl_die(isl_val_get_ctx(v), isl_error_invalid,
945 "expecting rational factor", goto error);
946 if (isl_val_is_zero(v))
947 isl_die(isl_val_get_ctx(v), isl_error_invalid,
948 "cannot scale down by zero", goto error);
949
950 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
951 if (isl_val_is_neg(v))
952 u = FN(UNION,negate_type)(u);
953
954 isl_val_free(v);
955 return u;
956 error:
957 isl_val_free(v);
958 FN(UNION,free)(u);
959 return NULL;
960 }
961
962 S(UNION,plain_is_equal_data)
963 {
964 UNION *u2;
965 isl_bool is_equal;
966 };
967
968 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
969 {
970 S(UNION,plain_is_equal_data) *data = user;
971 struct isl_hash_table_entry *entry2;
972 PW *pw = *entry;
973
974 entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
975 if (!entry2 || entry2 == isl_hash_table_entry_none) {
976 if (!entry2)
977 data->is_equal = isl_bool_error;
978 else
979 data->is_equal = isl_bool_false;
980 return isl_stat_error;
981 }
982
983 data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
984 if (data->is_equal < 0 || !data->is_equal)
985 return isl_stat_error;
986
987 return isl_stat_ok;
988 }
989
990 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
991 {
992 S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
993 int n1, n2;
994
995 if (!u1 || !u2)
996 return isl_bool_error;
997 if (u1 == u2)
998 return isl_bool_true;
999 if (u1->table.n != u2->table.n)
1000 return isl_bool_false;
1001 n1 = FN(FN(UNION,n),BASE)(u1);
1002 n2 = FN(FN(UNION,n),BASE)(u2);
1003 if (n1 < 0 || n2 < 0)
1004 return isl_bool_error;
1005 if (n1 != n2)
1006 return isl_bool_false;
1007
1008 u1 = FN(UNION,copy)(u1);
1009 u2 = FN(UNION,copy)(u2);
1010 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1011 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1012 if (!u1 || !u2)
1013 goto error;
1014
1015 data.u2 = u2;
1016 if (FN(UNION,foreach_inplace)(u1,
1017 &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1018 data.is_equal)
1019 goto error;
1020
1021 FN(UNION,free)(u1);
1022 FN(UNION,free)(u2);
1023
1024 return data.is_equal;
1025 error:
1026 FN(UNION,free)(u1);
1027 FN(UNION,free)(u2);
1028 return isl_bool_error;
1029 }
1030
1031 /* Check whether the element that "entry" points to involves any NaNs and
1032 * store the result in *nan.
1033 * Abort as soon as one such element has been found.
1034 */
1035 static isl_stat FN(UNION,involves_nan_entry)(void **entry, void *user)
1036 {
1037 isl_bool *nan = user;
1038 PW *pw = *entry;
1039
1040 *nan = FN(PW,involves_nan)(pw);
1041 if (*nan < 0 || !nan)
1042 return isl_stat_error;
1043
1044 return isl_stat_ok;
1045 }
1046
1047 /* Does "u" involve any NaNs?
1048 */
1049 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1050 {
1051 isl_bool nan = isl_bool_false;
1052
1053 if (!u)
1054 return isl_bool_error;
1055
1056 if (FN(UNION,foreach_inplace)(u,
1057 &FN(UNION,involves_nan_entry), &nan) < 0 &&
1058 !nan)
1059 return isl_bool_error;
1060
1061 return nan;
1062 }
1063
1064 /* Internal data structure for isl_union_*_drop_dims.
1065 * type, first and n are passed to isl_*_drop_dims.
1066 */
1067 S(UNION,drop_dims_data) {
1068 enum isl_dim_type type;
1069 unsigned first;
1070 unsigned n;
1071 };
1072
1073 /* Drop the parameters specified by "data" from "part" and return the result.
1074 */
1075 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1076 void *user)
1077 {
1078 S(UNION,drop_dims_data) *data = user;
1079
1080 return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1081 }
1082
1083 /* Drop the specified parameters from "u".
1084 * That is, type is required to be isl_dim_param.
1085 */
1086 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1087 enum isl_dim_type type, unsigned first, unsigned n)
1088 {
1089 isl_space *space;
1090 S(UNION,drop_dims_data) data = { type, first, n };
1091
1092 if (!u)
1093 return NULL;
1094
1095 if (type != isl_dim_param)
1096 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1097 "can only project out parameters",
1098 return FN(UNION,free)(u));
1099
1100 space = FN(UNION,get_space)(u);
1101 space = isl_space_drop_dims(space, type, first, n);
1102 return FN(UNION,transform_space)(u, space, &FN(UNION,drop_dims_entry),
1103 &data);
1104 }
1105
1106 /* Internal data structure for isl_union_*_set_dim_name.
1107 * pos is the position of the parameter that needs to be renamed.
1108 * s is the new name.
1109 */
1110 S(UNION,set_dim_name_data) {
1111 unsigned pos;
1112 const char *s;
1113 };
1114
1115 /* Change the name of the parameter at position data->pos of "part" to data->s
1116 * and return the result.
1117 */
1118 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1119 void *user)
1120 {
1121 S(UNION,set_dim_name_data) *data = user;
1122
1123 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1124 }
1125
1126 /* Change the name of the parameter at position "pos" to "s".
1127 * That is, type is required to be isl_dim_param.
1128 */
1129 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1130 enum isl_dim_type type, unsigned pos, const char *s)
1131 {
1132 S(UNION,set_dim_name_data) data = { pos, s };
1133 isl_space *space;
1134
1135 if (!u)
1136 return NULL;
1137
1138 if (type != isl_dim_param)
1139 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1140 "can only set parameter names",
1141 return FN(UNION,free)(u));
1142
1143 space = FN(UNION,get_space)(u);
1144 space = isl_space_set_dim_name(space, type, pos, s);
1145 return FN(UNION,transform_space)(u, space,
1146 &FN(UNION,set_dim_name_entry), &data);
1147 }
1148
1149 /* Reset the user pointer on all identifiers of parameters and tuples
1150 * of the space of "part" and return the result.
1151 */
1152 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1153 void *user)
1154 {
1155 return FN(PART,reset_user)(part);
1156 }
1157
1158 /* Reset the user pointer on all identifiers of parameters and tuples
1159 * of the spaces of "u".
1160 */
1161 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1162 {
1163 isl_space *space;
1164
1165 space = FN(UNION,get_space)(u);
1166 space = isl_space_reset_user(space);
1167 return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry),
1168 NULL);
1169 }
1170
1171 /* Add the base expression held by "entry" to "list".
1172 */
1173 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1174 {
1175 PW *pw = *entry;
1176 LIST(PART) **list = user;
1177
1178 *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1179 if (!*list)
1180 return isl_stat_error;
1181
1182 return isl_stat_ok;
1183 }
1184
1185 /* Return a list containing all the base expressions in "u".
1186 *
1187 * First construct a list of the appropriate size and
1188 * then add all the elements.
1189 */
1190 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1191 {
1192 int n;
1193 LIST(PART) *list;
1194
1195 if (!u)
1196 return NULL;
1197 n = FN(FN(UNION,n),BASE)(u);
1198 if (n < 0)
1199 return NULL;
1200 list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1201 if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1202 return FN(LIST(PART),free)(list);
1203
1204 return list;
1205 }
Integer set library