?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_*_copy_tuple_id: use BASE instead of TYPE to select variant
[isl.git] / isl_union_templ.c
blob06710d2675096e4595d1e5fa52f8a7544957ad2f
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 #include "opt_type.h"
69
70 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space
71 OPT_TYPE_PARAM, int size)
72 {
73 UNION *u;
74
75 space = isl_space_params(space);
76 if (!space)
77 return NULL;
78
79 u = isl_calloc_type(space->ctx, UNION);
80 if (!u)
81 goto error;
82
83 u->ref = 1;
84 OPT_SET_TYPE(u->, type);
85 u->space = space;
86 if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
87 return FN(UNION,free)(u);
88
89 return u;
90 error:
91 isl_space_free(space);
92 return NULL;
93 }
94
95 /* Create an empty/zero union without specifying any parameters.
96 */
97 __isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM)
98 {
99 isl_space *space;
100
101 space = isl_space_unit(ctx);
102 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
103 }
104
105 __isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space
106 OPT_TYPE_PARAM)
107 {
108 return FN(UNION,alloc)(space OPT_TYPE_ARG(NO_LOC), 16);
109 }
110
111 /* This is an alternative name for the function above.
112 */
113 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
114 {
115 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
116 }
117
118 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
119 {
120 if (!u)
121 return NULL;
122
123 u->ref++;
124 return u;
125 }
126
127 /* Do the tuples of "space" correspond to those of the domain of "part"?
128 * That is, is the domain space of "part" equal to "space", ignoring parameters?
129 */
130 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
131 __isl_keep isl_space *space)
132 {
133 return isl_space_has_domain_tuples(space, FN(PART,peek_space)(part));
134 }
135
136 /* Extract the element of "u" living in "space" (ignoring parameters).
137 *
138 * Return the ZERO element if "u" does not contain any element
139 * living in "space".
140 */
141 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
142 __isl_take isl_space *space)
143 {
144 struct isl_hash_table_entry *entry;
145
146 entry = FN(UNION,find_part_entry)(u, space, 0);
147 if (!entry)
148 goto error;
149 if (entry == isl_hash_table_entry_none)
150 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->));
151 isl_space_free(space);
152 return FN(PART,copy)(entry->data);
153 error:
154 isl_space_free(space);
155 return NULL;
156 }
157
158 /* Add "part" to "u".
159 * If "disjoint" is set, then "u" is not allowed to already have
160 * a part that is defined over a domain that overlaps with the domain
161 * of "part".
162 * Otherwise, compute the union sum of "part" and the part in "u"
163 * defined on the same space.
164 */
165 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
166 __isl_take PART *part, int disjoint)
167 {
168 int empty;
169 struct isl_hash_table_entry *entry;
170
171 if (!part)
172 goto error;
173
174 empty = FN(PART,IS_ZERO)(part);
175 if (empty < 0)
176 goto error;
177 if (empty) {
178 FN(PART,free)(part);
179 return u;
180 }
181
182 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
183 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
184
185 u = FN(UNION,cow)(u);
186
187 if (!u)
188 goto error;
189
190 if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
191 goto error;
192 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
193 if (!entry)
194 goto error;
195
196 if (!entry->data)
197 entry->data = part;
198 else {
199 if (disjoint &&
200 FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
201 goto error;
202 entry->data = FN(PART,union_add_)(entry->data,
203 FN(PART,copy)(part));
204 empty = FN(PART,IS_ZERO)(entry->data);
205 if (empty < 0)
206 goto error;
207 if (empty)
208 u = FN(UNION,remove_part_entry)(u, entry);
209 FN(PART,free)(part);
210 }
211
212 return u;
213 error:
214 FN(PART,free)(part);
215 FN(UNION,free)(u);
216 return NULL;
217 }
218
219 /* Add "part" to "u", where "u" is assumed not to already have
220 * a part that is defined on the same space as "part".
221 */
222 __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
223 __isl_take PART *part)
224 {
225 return FN(UNION,add_part_generic)(u, part, 1);
226 }
227
228 /* Allocate a UNION with the same type (if any) and the same size as "u" and
229 * with space "space".
230 */
231 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
232 __isl_take isl_space *space)
233 {
234 if (!u)
235 goto error;
236 return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n);
237 error:
238 isl_space_free(space);
239 return NULL;
240 }
241
242 /* Allocate a UNION with the same space, the same type (if any) and
243 * the same size as "u".
244 */
245 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
246 {
247 return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
248 }
249
250 /* Data structure that specifies how isl_union_*_transform
251 * should modify the base expressions in the union expression.
252 *
253 * If "inplace" is set, then the base expression in the input union
254 * are modified in place. This means that "fn" should not
255 * change the meaning of the union or that the union only
256 * has a single reference.
257 * If "space" is not NULL, then a new union is created in this space.
258 * If "filter" is not NULL, then only the base expressions that satisfy "filter"
259 * are taken into account.
260 * "filter_user" is passed as the second argument to "filter".
261 * If "fn" it not NULL, then it is applied to each entry in the input.
262 * "fn_user" is passed as the second argument to "fn".
263 */
264 S(UNION,transform_control) {
265 int inplace;
266 isl_space *space;
267 isl_bool (*filter)(__isl_keep PART *part, void *user);
268 void *filter_user;
269 __isl_give PART *(*fn)(__isl_take PART *part, void *user);
270 void *fn_user;
271 };
272
273 /* Internal data structure for isl_union_*_transform_space.
274 * "control" specifies how the base expressions should be modified.
275 * "res" collects the results (if control->inplace is not set).
276 */
277 S(UNION,transform_data)
278 {
279 S(UNION,transform_control) *control;
280 UNION *res;
281 };
282
283 /* Apply control->fn to "part" and add the result to data->res or
284 * place it back into the input union if control->inplace is set.
285 */
286 static isl_stat FN(UNION,transform_entry)(void **entry, void *user)
287 {
288 S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
289 S(UNION,transform_control) *control = data->control;
290 PART *part = *entry;
291
292 if (control->filter) {
293 isl_bool handle;
294
295 handle = control->filter(part, control->filter_user);
296 if (handle < 0)
297 return isl_stat_error;
298 if (!handle)
299 return isl_stat_ok;
300 }
301
302 if (!control->inplace)
303 part = FN(PART,copy)(part);
304 if (control->fn)
305 part = control->fn(part, control->fn_user);
306 if (control->inplace)
307 *entry = part;
308 else
309 data->res = FN(FN(UNION,add),BASE)(data->res, part);
310 if (!part || !data->res)
311 return isl_stat_error;
312
313 return isl_stat_ok;
314 }
315
316 /* Return a UNION that is obtained by modifying "u" according to "control".
317 */
318 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
319 S(UNION,transform_control) *control)
320 {
321 S(UNION,transform_data) data = { control };
322 isl_space *space;
323
324 if (control->inplace) {
325 data.res = u;
326 } else {
327 if (control->space)
328 space = isl_space_copy(control->space);
329 else
330 space = FN(UNION,get_space)(u);
331 data.res = FN(UNION,alloc_same_size_on_space)(u, space);
332 }
333 if (FN(UNION,foreach_inplace)(u, &FN(UNION,transform_entry), &data) < 0)
334 data.res = FN(UNION,free)(data.res);
335 if (!control->inplace)
336 FN(UNION,free)(u);
337 return data.res;
338 }
339
340 /* Return a UNION living in "space" that is otherwise obtained by modifying "u"
341 * according to "control".
342 */
343 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
344 __isl_take isl_space *space, S(UNION,transform_control) *control)
345 {
346 if (!space)
347 return FN(UNION,free)(u);
348 control->space = space;
349 u = FN(UNION,transform)(u, control);
350 isl_space_free(space);
351 return u;
352 }
353
354 /* Update "u" by applying "fn" to each entry.
355 * This operation is assumed not to change the number of entries nor
356 * the spaces of the entries.
357 *
358 * If there is only one reference to "u", then change "u" inplace.
359 * Otherwise, create a new UNION from "u" and discard the original.
360 */
361 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
362 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
363 {
364 S(UNION,transform_control) control = { .fn = fn, .fn_user = user };
365 isl_bool single_ref;
366
367 single_ref = FN(UNION,has_single_reference)(u);
368 if (single_ref < 0)
369 return FN(UNION,free)(u);
370 if (single_ref)
371 control.inplace = 1;
372 return FN(UNION,transform)(u, &control);
373 }
374
375 /* An isl_union_*_transform callback for use in isl_union_*_dup
376 * that simply returns "part".
377 */
378 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
379 {
380 return part;
381 }
382
383 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
384 {
385 S(UNION,transform_control) control = { .fn = &FN(UNION,copy_part) };
386
387 u = FN(UNION,copy)(u);
388 return FN(UNION,transform)(u, &control);
389 }
390
391 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
392 {
393 if (!u)
394 return NULL;
395
396 if (u->ref == 1)
397 return u;
398 u->ref--;
399 return FN(UNION,dup)(u);
400 }
401
402 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
403 {
404 if (!u)
405 return NULL;
406
407 if (--u->ref > 0)
408 return NULL;
409
410 isl_hash_table_foreach(u->space->ctx, &u->table,
411 &FN(UNION,free_u_entry), NULL);
412 isl_hash_table_clear(&u->table);
413 isl_space_free(u->space);
414 free(u);
415 return NULL;
416 }
417
418 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
419 {
420 isl_reordering *exp = user;
421
422 exp = isl_reordering_extend_space(isl_reordering_copy(exp),
423 FN(PART,get_domain_space)(part));
424 return FN(PART,realign_domain)(part, exp);
425 }
426
427 /* Reorder the parameters of "u" according to the given reordering.
428 */
429 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
430 __isl_take isl_reordering *r)
431 {
432 S(UNION,transform_control) control = {
433 .fn = &FN(UNION,align_entry),
434 .fn_user = r,
435 };
436 isl_space *space;
437
438 if (!u || !r)
439 goto error;
440
441 space = isl_reordering_get_space(r);
442 u = FN(UNION,transform_space)(u, space, &control);
443 isl_reordering_free(r);
444 return u;
445 error:
446 FN(UNION,free)(u);
447 isl_reordering_free(r);
448 return NULL;
449 }
450
451 /* Align the parameters of "u" to those of "model".
452 */
453 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
454 __isl_take isl_space *model)
455 {
456 isl_bool equal_params;
457 isl_reordering *r;
458
459 if (!u || !model)
460 goto error;
461
462 equal_params = isl_space_has_equal_params(u->space, model);
463 if (equal_params < 0)
464 goto error;
465 if (equal_params) {
466 isl_space_free(model);
467 return u;
468 }
469
470 r = isl_parameter_alignment_reordering(u->space, model);
471 isl_space_free(model);
472
473 return FN(UNION,realign_domain)(u, r);
474 error:
475 isl_space_free(model);
476 FN(UNION,free)(u);
477 return NULL;
478 }
479
480 /* Add "part" to *u, taking the union sum if "u" already has
481 * a part defined on the same space as "part".
482 */
483 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
484 {
485 UNION **u = (UNION **)user;
486
487 *u = FN(UNION,add_part_generic)(*u, part, 0);
488
489 return isl_stat_ok;
490 }
491
492 /* Compute the sum of "u1" and "u2" on the union of their domains,
493 * with the actual sum on the shared domain and
494 * the defined expression on the symmetric difference of the domains.
495 *
496 * This is an internal function that is exposed under different
497 * names depending on whether the base expressions have a zero default
498 * value.
499 * If they do, then this function is called "add".
500 * Otherwise, it is called "union_add".
501 */
502 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
503 __isl_take UNION *u2)
504 {
505 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
506 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
507
508 u1 = FN(UNION,cow)(u1);
509
510 if (!u1 || !u2)
511 goto error;
512
513 if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
514 goto error;
515
516 FN(UNION,free)(u2);
517
518 return u1;
519 error:
520 FN(UNION,free)(u1);
521 FN(UNION,free)(u2);
522 return NULL;
523 }
524
525 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
526 {
527 isl_space *space;
528 UNION *u;
529
530 if (!part)
531 return NULL;
532
533 space = FN(PART,get_space)(part);
534 space = isl_space_drop_dims(space, isl_dim_in, 0,
535 isl_space_dim(space, isl_dim_in));
536 space = isl_space_drop_dims(space, isl_dim_out, 0,
537 isl_space_dim(space, isl_dim_out));
538 u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
539 u = FN(FN(UNION,add),BASE)(u, part);
540
541 return u;
542 }
543
544 /* This function performs the same operation as isl_union_pw_*_from_pw_*,
545 * but is considered as a function on an isl_pw_* when exported.
546 */
547 __isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part)
548 {
549 return FN(FN(UNION,from),BASE)(part);
550 }
551
552 S(UNION,match_bin_data) {
553 UNION *u2;
554 UNION *res;
555 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
556 };
557
558 /* Check if data->u2 has an element living in the same space as "part".
559 * If so, call data->fn on the two elements and add the result to
560 * data->res.
561 */
562 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
563 {
564 S(UNION,match_bin_data) *data = user;
565 struct isl_hash_table_entry *entry2;
566 isl_space *space;
567 PART *part2;
568
569 space = FN(PART,get_space)(part);
570 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
571 isl_space_free(space);
572 if (!entry2)
573 goto error;
574 if (entry2 == isl_hash_table_entry_none) {
575 FN(PART,free)(part);
576 return isl_stat_ok;
577 }
578
579 part2 = entry2->data;
580 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
581 part2->dim, isl_dim_out))
582 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
583 "entries should have the same range space",
584 goto error);
585
586 part = data->fn(part, FN(PART, copy)(entry2->data));
587
588 data->res = FN(FN(UNION,add),BASE)(data->res, part);
589 if (!data->res)
590 return isl_stat_error;
591
592 return isl_stat_ok;
593 error:
594 FN(PART,free)(part);
595 return isl_stat_error;
596 }
597
598 /* This function is currently only used from isl_polynomial.c
599 * and not from isl_fold.c.
600 */
601 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
602 __isl_take UNION *u2,
603 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
604 __attribute__ ((unused));
605 /* For each pair of elements in "u1" and "u2" living in the same space,
606 * call "fn" and collect the results.
607 */
608 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
609 __isl_take UNION *u2,
610 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
611 {
612 S(UNION,match_bin_data) data = { NULL, NULL, fn };
613
614 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
615 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
616
617 if (!u1 || !u2)
618 goto error;
619
620 data.u2 = u2;
621 data.res = FN(UNION,alloc_same_size)(u1);
622 if (FN(FN(UNION,foreach),BASE)(u1,
623 &FN(UNION,match_bin_entry), &data) < 0)
624 goto error;
625
626 FN(UNION,free)(u1);
627 FN(UNION,free)(u2);
628 return data.res;
629 error:
630 FN(UNION,free)(u1);
631 FN(UNION,free)(u2);
632 FN(UNION,free)(data.res);
633 return NULL;
634 }
635
636 /* Compute the sum of "u1" and "u2".
637 *
638 * If the base expressions have a default zero value, then the sum
639 * is computed on the union of the domains of "u1" and "u2".
640 * Otherwise, it is computed on their shared domains.
641 */
642 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
643 {
644 #if DEFAULT_IS_ZERO
645 return FN(UNION,union_add_)(u1, u2);
646 #else
647 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
648 #endif
649 }
650
651 #ifndef NO_SUB
652 /* Subtract "u2" from "u1" and return the result.
653 *
654 * If the base expressions have a default zero value, then
655 * reuse isl_union_*_add to ensure the result
656 * is computed on the union of the domains of "u1" and "u2".
657 * Otherwise, compute the result directly on their shared domain.
658 */
659 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
660 {
661 #if DEFAULT_IS_ZERO
662 return FN(UNION,add)(u1, FN(UNION,neg)(u2));
663 #else
664 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
665 #endif
666 }
667 #endif
668
669 S(UNION,any_set_data) {
670 isl_set *set;
671 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
672 };
673
674 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
675 void *user)
676 {
677 S(UNION,any_set_data) *data = user;
678
679 return data->fn(part, isl_set_copy(data->set));
680 }
681
682 /* Update each element of "u" by calling "fn" on the element and "set".
683 */
684 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
685 __isl_take isl_set *set,
686 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
687 {
688 S(UNION,any_set_data) data = { NULL, fn };
689 S(UNION,transform_control) control = {
690 .fn = &FN(UNION,any_set_entry),
691 .fn_user = &data,
692 };
693
694 u = FN(UNION,align_params)(u, isl_set_get_space(set));
695 set = isl_set_align_params(set, FN(UNION,get_space)(u));
696
697 if (!u || !set)
698 goto error;
699
700 data.set = set;
701 u = FN(UNION,transform)(u, &control);
702 isl_set_free(set);
703 return u;
704 error:
705 FN(UNION,free)(u);
706 isl_set_free(set);
707 return NULL;
708 }
709
710 /* Intersect the domain of "u" with the parameter domain "context".
711 */
712 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
713 __isl_take isl_set *set)
714 {
715 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
716 }
717
718 /* Compute the gist of the domain of "u" with respect to
719 * the parameter domain "context".
720 */
721 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
722 __isl_take isl_set *set)
723 {
724 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
725 }
726
727 /* Data structure that specifies how isl_union_*_match_domain_op
728 * should combine its arguments.
729 *
730 * If "filter" is not NULL, then only parts that pass the given
731 * filter are considered for matching.
732 * "fn" is applied to each part in the union and each corresponding
733 * set in the union set, i.e., such that the set lives in the same space
734 * as the domain of the part.
735 * If "match_space" is not NULL, then the set extracted from the union set
736 * does not live in the same space as the domain of the part,
737 * but rather in the space that results from calling "match_space"
738 * on this domain space.
739 */
740 S(UNION,match_domain_control) {
741 isl_bool (*filter)(__isl_keep PART *part);
742 __isl_give isl_space *(*match_space)(__isl_take isl_space *space);
743 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
744 };
745
746 S(UNION,match_domain_data) {
747 isl_union_set *uset;
748 UNION *res;
749 S(UNION,match_domain_control) *control;
750 };
751
752 /* Find the set in data->uset that lives in the same space as the domain
753 * of "part" (ignoring parameters), apply data->fn to *entry and this set
754 * (if any), and add the result to data->res.
755 */
756 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
757 {
758 S(UNION,match_domain_data) *data = user;
759 struct isl_hash_table_entry *entry2;
760 isl_space *space;
761
762 if (data->control->filter) {
763 isl_bool pass = data->control->filter(part);
764 if (pass < 0 || !pass) {
765 FN(PART,free)(part);
766 return pass < 0 ? isl_stat_error : isl_stat_ok;
767 }
768 }
769
770 space = FN(PART,get_domain_space)(part);
771 if (data->control->match_space)
772 space = data->control->match_space(space);
773 entry2 = isl_union_set_find_entry(data->uset, space, 0);
774 isl_space_free(space);
775 if (!entry2 || entry2 == isl_hash_table_entry_none) {
776 FN(PART,free)(part);
777 return isl_stat_non_null(entry2);
778 }
779
780 part = data->control->fn(part, isl_set_copy(entry2->data));
781
782 data->res = FN(FN(UNION,add),BASE)(data->res, part);
783 if (!data->res)
784 return isl_stat_error;
785
786 return isl_stat_ok;
787 }
788
789 /* Combine "u" and "uset" according to "control"
790 * and collect the results.
791 */
792 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
793 __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control)
794 {
795 S(UNION,match_domain_data) data = { NULL, NULL, control };
796
797 if (!u || !uset)
798 goto error;
799
800 data.uset = uset;
801 data.res = FN(UNION,alloc_same_size)(u);
802 if (FN(FN(UNION,foreach),BASE)(u,
803 &FN(UNION,match_domain_entry), &data) < 0)
804 goto error;
805
806 FN(UNION,free)(u);
807 isl_union_set_free(uset);
808 return data.res;
809 error:
810 FN(UNION,free)(u);
811 isl_union_set_free(uset);
812 FN(UNION,free)(data.res);
813 return NULL;
814 }
815
816 /* Intersect the domain of "u" with "uset".
817 * If "uset" is a parameters domain, then intersect the parameter
818 * domain of "u" with this set.
819 */
820 __isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u,
821 __isl_take isl_union_set *uset)
822 {
823 S(UNION,match_domain_control) control = {
824 .fn = &FN(PW,intersect_domain),
825 };
826
827 if (isl_union_set_is_params(uset))
828 return FN(UNION,intersect_params)(u,
829 isl_set_from_union_set(uset));
830 return FN(UNION,match_domain_op)(u, uset, &control);
831 }
832
833 /* This is an alternative name for the function above.
834 */
835 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
836 __isl_take isl_union_set *uset)
837 {
838 return FN(UNION,intersect_domain_union_set)(u, uset);
839 }
840
841 /* Return true if this part should be kept.
842 *
843 * In particular, it should be kept if its domain space
844 * corresponds to "space".
845 */
846 static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user)
847 {
848 isl_space *space = user;
849
850 return FN(PW,has_domain_space_tuples)(part, space);
851 }
852
853 /* Remove any not element in "space" from the domain of "u".
854 *
855 * In particular, select any part of the function defined
856 * on this domain space.
857 */
858 __isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u,
859 __isl_take isl_space *space)
860 {
861 S(UNION,transform_control) control = {
862 .filter = &FN(UNION,select_entry),
863 .filter_user = space,
864 };
865
866 u = FN(UNION,transform)(u, &control);
867 isl_space_free(space);
868 return u;
869 }
870
871 /* Is the domain of "pw" a wrapped relation?
872 */
873 static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw)
874 {
875 return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw));
876 }
877
878 /* Intersect the domain of the wrapped relation inside the domain of "u"
879 * with "uset".
880 */
881 __isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u,
882 __isl_take isl_union_set *uset)
883 {
884 S(UNION,match_domain_control) control = {
885 .filter = &FN(PART,domain_is_wrapping),
886 .match_space = &isl_space_factor_domain,
887 .fn = &FN(PW,intersect_domain_wrapped_domain),
888 };
889
890 return FN(UNION,match_domain_op)(u, uset, &control);
891 }
892
893 /* Intersect the range of the wrapped relation inside the domain of "u"
894 * with "uset".
895 */
896 __isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u,
897 __isl_take isl_union_set *uset)
898 {
899 S(UNION,match_domain_control) control = {
900 .filter = &FN(PART,domain_is_wrapping),
901 .match_space = &isl_space_factor_range,
902 .fn = &FN(PW,intersect_domain_wrapped_range),
903 };
904
905 return FN(UNION,match_domain_op)(u, uset, &control);
906 }
907
908 /* Take the set (which may be empty) in data->uset that lives
909 * in the same space as the domain of "pw", subtract it from the domain
910 * of "part" and return the result.
911 */
912 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
913 void *user)
914 {
915 isl_union_set *uset = user;
916 isl_space *space;
917 isl_set *set;
918
919 space = FN(PART,get_domain_space)(part);
920 set = isl_union_set_extract_set(uset, space);
921 return FN(PART,subtract_domain)(part, set);
922 }
923
924 /* Subtract "uset" from the domain of "u".
925 */
926 __isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u,
927 __isl_take isl_union_set *uset)
928 {
929 S(UNION,transform_control) control = {
930 .fn = &FN(UNION,subtract_domain_entry),
931 .fn_user = uset,
932 };
933
934 u = FN(UNION,transform)(u, &control);
935 isl_union_set_free(uset);
936 return u;
937 }
938
939 /* This is an alternative name for the function above.
940 */
941 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
942 __isl_take isl_union_set *uset)
943 {
944 return FN(UNION,subtract_domain_union_set)(u, uset);
945 }
946
947 /* Return true if this part should be kept.
948 *
949 * In particular, it should be kept if its domain space
950 * does not correspond to "space".
951 */
952 static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user)
953 {
954 isl_space *space = user;
955
956 return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space));
957 }
958
959 /* Remove any element in "space" from the domain of "u".
960 *
961 * In particular, filter out any part of the function defined
962 * on this domain space.
963 */
964 __isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u,
965 __isl_take isl_space *space)
966 {
967 S(UNION,transform_control) control = {
968 .filter = &FN(UNION,filter_out_entry),
969 .filter_user = space,
970 };
971
972 u = FN(UNION,transform)(u, &control);
973 isl_space_free(space);
974 return u;
975 }
976
977 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
978 __isl_take isl_union_set *uset)
979 {
980 S(UNION,match_domain_control) control = {
981 .fn = &FN(PW,gist),
982 };
983
984 if (isl_union_set_is_params(uset))
985 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
986 return FN(UNION,match_domain_op)(u, uset, &control);
987 }
988
989 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
990 * Since the UNION may have several references, the entry is only
991 * replaced if the coalescing is successful.
992 */
993 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
994 {
995 PART **part_p = (PART **) entry;
996 PART *part;
997
998 part = FN(PART,copy)(*part_p);
999 part = FN(PW,coalesce)(part);
1000 if (!part)
1001 return isl_stat_error;
1002 FN(PART,free)(*part_p);
1003 *part_p = part;
1004
1005 return isl_stat_ok;
1006 }
1007
1008 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
1009 {
1010 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
1011 goto error;
1012
1013 return u;
1014 error:
1015 FN(UNION,free)(u);
1016 return NULL;
1017 }
1018
1019 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
1020 {
1021 isl_union_set **uset = (isl_union_set **)user;
1022
1023 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
1024
1025 return isl_stat_ok;
1026 }
1027
1028 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
1029 {
1030 isl_union_set *uset;
1031
1032 uset = isl_union_set_empty(FN(UNION,get_space)(u));
1033 if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
1034 goto error;
1035
1036 FN(UNION,free)(u);
1037
1038 return uset;
1039 error:
1040 isl_union_set_free(uset);
1041 FN(UNION,free)(u);
1042 return NULL;
1043 }
1044
1045 #ifdef HAS_TYPE
1046 /* Negate the type of "u".
1047 */
1048 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1049 {
1050 u = FN(UNION,cow)(u);
1051 if (!u)
1052 return NULL;
1053 u->type = isl_fold_type_negate(u->type);
1054 return u;
1055 }
1056 #else
1057 /* Negate the type of "u".
1058 * Since "u" does not have a type, do nothing.
1059 */
1060 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1061 {
1062 return u;
1063 }
1064 #endif
1065
1066 /* Multiply "part" by the isl_val "user" and return the result.
1067 */
1068 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1069 void *user)
1070 {
1071 isl_val *v = user;
1072
1073 return FN(PART,scale_val)(part, isl_val_copy(v));
1074 }
1075
1076 /* Multiply "u" by "v" and return the result.
1077 */
1078 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1079 __isl_take isl_val *v)
1080 {
1081 if (!u || !v)
1082 goto error;
1083 if (isl_val_is_one(v)) {
1084 isl_val_free(v);
1085 return u;
1086 }
1087
1088 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1089 UNION *zero;
1090 isl_space *space = FN(UNION,get_space)(u);
1091 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
1092 FN(UNION,free)(u);
1093 isl_val_free(v);
1094 return zero;
1095 }
1096
1097 if (!isl_val_is_rat(v))
1098 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1099 "expecting rational factor", goto error);
1100
1101 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1102 if (isl_val_is_neg(v))
1103 u = FN(UNION,negate_type)(u);
1104
1105 isl_val_free(v);
1106 return u;
1107 error:
1108 isl_val_free(v);
1109 FN(UNION,free)(u);
1110 return NULL;
1111 }
1112
1113 /* Divide "part" by the isl_val "user" and return the result.
1114 */
1115 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
1116 void *user)
1117 {
1118 isl_val *v = user;
1119
1120 return FN(PART,scale_down_val)(part, isl_val_copy(v));
1121 }
1122
1123 /* Divide "u" by "v" and return the result.
1124 */
1125 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1126 __isl_take isl_val *v)
1127 {
1128 if (!u || !v)
1129 goto error;
1130 if (isl_val_is_one(v)) {
1131 isl_val_free(v);
1132 return u;
1133 }
1134
1135 if (!isl_val_is_rat(v))
1136 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1137 "expecting rational factor", goto error);
1138 if (isl_val_is_zero(v))
1139 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1140 "cannot scale down by zero", goto error);
1141
1142 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
1143 if (isl_val_is_neg(v))
1144 u = FN(UNION,negate_type)(u);
1145
1146 isl_val_free(v);
1147 return u;
1148 error:
1149 isl_val_free(v);
1150 FN(UNION,free)(u);
1151 return NULL;
1152 }
1153
1154 /* Internal data structure for isl_union_*_every_*.
1155 *
1156 * "test" is the user-specified callback function.
1157 * "user" is the user-specified callback function argument.
1158 *
1159 * "res" is the final result, initialized to isl_bool_true.
1160 */
1161 S(UNION,every_data) {
1162 isl_bool (*test)(__isl_keep PW *pw, void *user);
1163 void *user;
1164
1165 isl_bool res;
1166 };
1167
1168 /* Call data->test on the piecewise expression at *entry,
1169 * updating the result in data->res.
1170 * Abort if this result is no longer isl_bool_true.
1171 */
1172 static isl_stat FN(UNION,every_entry)(void **entry, void *user)
1173 {
1174 S(UNION,every_data) *data = user;
1175 PW *pw = *entry;
1176
1177 data->res = data->test(pw, data->user);
1178 if (data->res < 0 || !data->res)
1179 return isl_stat_error;
1180
1181 return isl_stat_ok;
1182 }
1183
1184 /* Does "test" succeed on every piecewise expression in "u"?
1185 */
1186 isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u,
1187 isl_bool (*test)(__isl_keep PW *pw, void *user), void *user)
1188 {
1189 S(UNION,every_data) data = { test, user };
1190
1191 data.res = isl_bool_true;
1192 if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 &&
1193 data.res == isl_bool_true)
1194 return isl_bool_error;
1195
1196 return data.res;
1197 }
1198
1199 S(UNION,plain_is_equal_data)
1200 {
1201 UNION *u2;
1202 };
1203
1204 static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user)
1205 {
1206 S(UNION,plain_is_equal_data) *data = user;
1207 struct isl_hash_table_entry *entry;
1208
1209 entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1210 if (!entry)
1211 return isl_bool_error;
1212 if (entry == isl_hash_table_entry_none)
1213 return isl_bool_false;
1214
1215 return FN(PW,plain_is_equal)(pw, entry->data);
1216 }
1217
1218 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1219 {
1220 S(UNION,plain_is_equal_data) data;
1221 isl_size n1, n2;
1222 isl_bool is_equal;
1223
1224 if (!u1 || !u2)
1225 return isl_bool_error;
1226 if (u1 == u2)
1227 return isl_bool_true;
1228 if (u1->table.n != u2->table.n)
1229 return isl_bool_false;
1230 n1 = FN(FN(UNION,n),BASE)(u1);
1231 n2 = FN(FN(UNION,n),BASE)(u2);
1232 if (n1 < 0 || n2 < 0)
1233 return isl_bool_error;
1234 if (n1 != n2)
1235 return isl_bool_false;
1236
1237 u1 = FN(UNION,copy)(u1);
1238 u2 = FN(UNION,copy)(u2);
1239 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1240 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1241 if (!u1 || !u2)
1242 goto error;
1243
1244 data.u2 = u2;
1245 is_equal = FN(FN(UNION,every),BASE)(u1,
1246 &FN(UNION,plain_is_equal_el), &data);
1247
1248 FN(UNION,free)(u1);
1249 FN(UNION,free)(u2);
1250
1251 return is_equal;
1252 error:
1253 FN(UNION,free)(u1);
1254 FN(UNION,free)(u2);
1255 return isl_bool_error;
1256 }
1257
1258 /* An isl_union_*_every_* callback that checks whether "pw"
1259 * does not involve any NaNs.
1260 */
1261 static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user)
1262 {
1263 return isl_bool_not(FN(PW,involves_nan)(pw));
1264 }
1265
1266 /* Does "u" involve any NaNs?
1267 */
1268 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1269 {
1270 isl_bool no_nan;
1271
1272 no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL);
1273
1274 return isl_bool_not(no_nan);
1275 }
1276
1277 /* Internal data structure for isl_union_*_drop_dims.
1278 * type, first and n are passed to isl_*_drop_dims.
1279 */
1280 S(UNION,drop_dims_data) {
1281 enum isl_dim_type type;
1282 unsigned first;
1283 unsigned n;
1284 };
1285
1286 /* Drop the parameters specified by "data" from "part" and return the result.
1287 */
1288 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1289 void *user)
1290 {
1291 S(UNION,drop_dims_data) *data = user;
1292
1293 return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1294 }
1295
1296 /* Drop the specified parameters from "u".
1297 * That is, type is required to be isl_dim_param.
1298 */
1299 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1300 enum isl_dim_type type, unsigned first, unsigned n)
1301 {
1302 isl_space *space;
1303 S(UNION,drop_dims_data) data = { type, first, n };
1304 S(UNION,transform_control) control = {
1305 .fn = &FN(UNION,drop_dims_entry),
1306 .fn_user = &data,
1307 };
1308
1309 if (!u)
1310 return NULL;
1311
1312 if (type != isl_dim_param)
1313 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1314 "can only project out parameters",
1315 return FN(UNION,free)(u));
1316
1317 space = FN(UNION,get_space)(u);
1318 space = isl_space_drop_dims(space, type, first, n);
1319 return FN(UNION,transform_space)(u, space, &control);
1320 }
1321
1322 /* Internal data structure for isl_union_*_set_dim_name.
1323 * pos is the position of the parameter that needs to be renamed.
1324 * s is the new name.
1325 */
1326 S(UNION,set_dim_name_data) {
1327 unsigned pos;
1328 const char *s;
1329 };
1330
1331 /* Change the name of the parameter at position data->pos of "part" to data->s
1332 * and return the result.
1333 */
1334 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1335 void *user)
1336 {
1337 S(UNION,set_dim_name_data) *data = user;
1338
1339 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1340 }
1341
1342 /* Change the name of the parameter at position "pos" to "s".
1343 * That is, type is required to be isl_dim_param.
1344 */
1345 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1346 enum isl_dim_type type, unsigned pos, const char *s)
1347 {
1348 S(UNION,set_dim_name_data) data = { pos, s };
1349 S(UNION,transform_control) control = {
1350 .fn = &FN(UNION,set_dim_name_entry),
1351 .fn_user = &data,
1352 };
1353 isl_space *space;
1354
1355 if (!u)
1356 return NULL;
1357
1358 if (type != isl_dim_param)
1359 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1360 "can only set parameter names",
1361 return FN(UNION,free)(u));
1362
1363 space = FN(UNION,get_space)(u);
1364 space = isl_space_set_dim_name(space, type, pos, s);
1365 return FN(UNION,transform_space)(u, space, &control);
1366 }
1367
1368 /* Reset the user pointer on all identifiers of parameters and tuples
1369 * of the space of "part" and return the result.
1370 */
1371 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1372 void *user)
1373 {
1374 return FN(PART,reset_user)(part);
1375 }
1376
1377 /* Reset the user pointer on all identifiers of parameters and tuples
1378 * of the spaces of "u".
1379 */
1380 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1381 {
1382 S(UNION,transform_control) control = {
1383 .fn = &FN(UNION,reset_user_entry),
1384 };
1385 isl_space *space;
1386
1387 space = FN(UNION,get_space)(u);
1388 space = isl_space_reset_user(space);
1389 return FN(UNION,transform_space)(u, space, &control);
1390 }
1391
1392 /* Add the base expression held by "entry" to "list".
1393 */
1394 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1395 {
1396 PW *pw = *entry;
1397 LIST(PART) **list = user;
1398
1399 *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1400 if (!*list)
1401 return isl_stat_error;
1402
1403 return isl_stat_ok;
1404 }
1405
1406 /* Return a list containing all the base expressions in "u".
1407 *
1408 * First construct a list of the appropriate size and
1409 * then add all the elements.
1410 */
1411 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1412 {
1413 isl_size n;
1414 LIST(PART) *list;
1415
1416 if (!u)
1417 return NULL;
1418 n = FN(FN(UNION,n),BASE)(u);
1419 if (n < 0)
1420 return NULL;
1421 list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1422 if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1423 return FN(LIST(PART),free)(list);
1424
1425 return list;
1426 }
Integer set library