?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
include/isl/hmap_templ.c: update foreach_data documentation
[isl.git] / isl_union_templ.c
blob5b9352e576bc1cd45c211b313e3e334e1908296e
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_space *space;
457 isl_bool equal_params;
458 isl_reordering *r;
459
460 space = FN(UNION,peek_space)(u);
461 equal_params = isl_space_has_equal_params(space, model);
462 if (equal_params < 0)
463 goto error;
464 if (equal_params) {
465 isl_space_free(model);
466 return u;
467 }
468
469 r = isl_parameter_alignment_reordering(space, model);
470 isl_space_free(model);
471
472 return FN(UNION,realign_domain)(u, r);
473 error:
474 isl_space_free(model);
475 FN(UNION,free)(u);
476 return NULL;
477 }
478
479 /* Add "part" to *u, taking the union sum if "u" already has
480 * a part defined on the same space as "part".
481 */
482 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
483 {
484 UNION **u = (UNION **)user;
485
486 *u = FN(UNION,add_part_generic)(*u, part, 0);
487
488 return isl_stat_ok;
489 }
490
491 /* Compute the sum of "u1" and "u2" on the union of their domains,
492 * with the actual sum on the shared domain and
493 * the defined expression on the symmetric difference of the domains.
494 *
495 * This is an internal function that is exposed under different
496 * names depending on whether the base expressions have a zero default
497 * value.
498 * If they do, then this function is called "add".
499 * Otherwise, it is called "union_add".
500 */
501 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
502 __isl_take UNION *u2)
503 {
504 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
505 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
506
507 u1 = FN(UNION,cow)(u1);
508
509 if (!u1 || !u2)
510 goto error;
511
512 if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
513 goto error;
514
515 FN(UNION,free)(u2);
516
517 return u1;
518 error:
519 FN(UNION,free)(u1);
520 FN(UNION,free)(u2);
521 return NULL;
522 }
523
524 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
525 {
526 isl_space *space;
527 UNION *u;
528
529 if (!part)
530 return NULL;
531
532 space = FN(PART,get_space)(part);
533 space = isl_space_drop_dims(space, isl_dim_in, 0,
534 isl_space_dim(space, isl_dim_in));
535 space = isl_space_drop_dims(space, isl_dim_out, 0,
536 isl_space_dim(space, isl_dim_out));
537 u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
538 u = FN(FN(UNION,add),BASE)(u, part);
539
540 return u;
541 }
542
543 /* This function performs the same operation as isl_union_pw_*_from_pw_*,
544 * but is considered as a function on an isl_pw_* when exported.
545 */
546 __isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part)
547 {
548 return FN(FN(UNION,from),BASE)(part);
549 }
550
551 S(UNION,match_bin_data) {
552 UNION *u2;
553 UNION *res;
554 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
555 };
556
557 /* Check if data->u2 has an element living in the same space as "part".
558 * If so, call data->fn on the two elements and add the result to
559 * data->res.
560 */
561 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
562 {
563 S(UNION,match_bin_data) *data = user;
564 struct isl_hash_table_entry *entry2;
565 isl_space *space;
566 PART *part2;
567
568 space = FN(PART,get_space)(part);
569 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
570 isl_space_free(space);
571 if (!entry2)
572 goto error;
573 if (entry2 == isl_hash_table_entry_none) {
574 FN(PART,free)(part);
575 return isl_stat_ok;
576 }
577
578 part2 = entry2->data;
579 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
580 part2->dim, isl_dim_out))
581 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
582 "entries should have the same range space",
583 goto error);
584
585 part = data->fn(part, FN(PART, copy)(entry2->data));
586
587 data->res = FN(FN(UNION,add),BASE)(data->res, part);
588 if (!data->res)
589 return isl_stat_error;
590
591 return isl_stat_ok;
592 error:
593 FN(PART,free)(part);
594 return isl_stat_error;
595 }
596
597 /* This function is currently only used from isl_polynomial.c
598 * and not from isl_fold.c.
599 */
600 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
601 __isl_take UNION *u2,
602 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
603 __attribute__ ((unused));
604 /* For each pair of elements in "u1" and "u2" living in the same space,
605 * call "fn" and collect the results.
606 */
607 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
608 __isl_take UNION *u2,
609 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
610 {
611 S(UNION,match_bin_data) data = { NULL, NULL, fn };
612
613 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
614 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
615
616 if (!u1 || !u2)
617 goto error;
618
619 data.u2 = u2;
620 data.res = FN(UNION,alloc_same_size)(u1);
621 if (FN(FN(UNION,foreach),BASE)(u1,
622 &FN(UNION,match_bin_entry), &data) < 0)
623 goto error;
624
625 FN(UNION,free)(u1);
626 FN(UNION,free)(u2);
627 return data.res;
628 error:
629 FN(UNION,free)(u1);
630 FN(UNION,free)(u2);
631 FN(UNION,free)(data.res);
632 return NULL;
633 }
634
635 /* Compute the sum of "u1" and "u2".
636 *
637 * If the base expressions have a default zero value, then the sum
638 * is computed on the union of the domains of "u1" and "u2".
639 * Otherwise, it is computed on their shared domains.
640 */
641 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
642 {
643 #if DEFAULT_IS_ZERO
644 return FN(UNION,union_add_)(u1, u2);
645 #else
646 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
647 #endif
648 }
649
650 S(UNION,any_set_data) {
651 isl_set *set;
652 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
653 };
654
655 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
656 void *user)
657 {
658 S(UNION,any_set_data) *data = user;
659
660 return data->fn(part, isl_set_copy(data->set));
661 }
662
663 /* Update each element of "u" by calling "fn" on the element and "set".
664 */
665 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
666 __isl_take isl_set *set,
667 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
668 {
669 S(UNION,any_set_data) data = { NULL, fn };
670 S(UNION,transform_control) control = {
671 .fn = &FN(UNION,any_set_entry),
672 .fn_user = &data,
673 };
674
675 u = FN(UNION,align_params)(u, isl_set_get_space(set));
676 set = isl_set_align_params(set, FN(UNION,get_space)(u));
677
678 if (!u || !set)
679 goto error;
680
681 data.set = set;
682 u = FN(UNION,transform)(u, &control);
683 isl_set_free(set);
684 return u;
685 error:
686 FN(UNION,free)(u);
687 isl_set_free(set);
688 return NULL;
689 }
690
691 /* Intersect the domain of "u" with the parameter domain "context".
692 */
693 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
694 __isl_take isl_set *set)
695 {
696 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
697 }
698
699 /* Compute the gist of the domain of "u" with respect to
700 * the parameter domain "context".
701 */
702 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
703 __isl_take isl_set *set)
704 {
705 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
706 }
707
708 /* Data structure that specifies how isl_union_*_match_domain_op
709 * should combine its arguments.
710 *
711 * If "filter" is not NULL, then only parts that pass the given
712 * filter are considered for matching.
713 * "fn" is applied to each part in the union and each corresponding
714 * set in the union set, i.e., such that the set lives in the same space
715 * as the domain of the part.
716 * If "match_space" is not NULL, then the set extracted from the union set
717 * does not live in the same space as the domain of the part,
718 * but rather in the space that results from calling "match_space"
719 * on this domain space.
720 */
721 S(UNION,match_domain_control) {
722 isl_bool (*filter)(__isl_keep PART *part);
723 __isl_give isl_space *(*match_space)(__isl_take isl_space *space);
724 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
725 };
726
727 S(UNION,match_domain_data) {
728 isl_union_set *uset;
729 UNION *res;
730 S(UNION,match_domain_control) *control;
731 };
732
733 /* Find the set in data->uset that lives in the same space as the domain
734 * of "part" (ignoring parameters), apply data->fn to *entry and this set
735 * (if any), and add the result to data->res.
736 */
737 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
738 {
739 S(UNION,match_domain_data) *data = user;
740 struct isl_hash_table_entry *entry2;
741 isl_space *space;
742
743 if (data->control->filter) {
744 isl_bool pass = data->control->filter(part);
745 if (pass < 0 || !pass) {
746 FN(PART,free)(part);
747 return pass < 0 ? isl_stat_error : isl_stat_ok;
748 }
749 }
750
751 space = FN(PART,get_domain_space)(part);
752 if (data->control->match_space)
753 space = data->control->match_space(space);
754 entry2 = isl_union_set_find_entry(data->uset, space, 0);
755 isl_space_free(space);
756 if (!entry2 || entry2 == isl_hash_table_entry_none) {
757 FN(PART,free)(part);
758 return isl_stat_non_null(entry2);
759 }
760
761 part = data->control->fn(part, isl_set_copy(entry2->data));
762
763 data->res = FN(FN(UNION,add),BASE)(data->res, part);
764 if (!data->res)
765 return isl_stat_error;
766
767 return isl_stat_ok;
768 }
769
770 /* Combine "u" and "uset" according to "control"
771 * and collect the results.
772 */
773 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
774 __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control)
775 {
776 S(UNION,match_domain_data) data = { NULL, NULL, control };
777
778 if (!u || !uset)
779 goto error;
780
781 data.uset = uset;
782 data.res = FN(UNION,alloc_same_size)(u);
783 if (FN(FN(UNION,foreach),BASE)(u,
784 &FN(UNION,match_domain_entry), &data) < 0)
785 goto error;
786
787 FN(UNION,free)(u);
788 isl_union_set_free(uset);
789 return data.res;
790 error:
791 FN(UNION,free)(u);
792 isl_union_set_free(uset);
793 FN(UNION,free)(data.res);
794 return NULL;
795 }
796
797 /* Intersect the domain of "u" with "uset".
798 * If "uset" is a parameters domain, then intersect the parameter
799 * domain of "u" with this set.
800 */
801 __isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u,
802 __isl_take isl_union_set *uset)
803 {
804 S(UNION,match_domain_control) control = {
805 .fn = &FN(PW,intersect_domain),
806 };
807
808 if (isl_union_set_is_params(uset))
809 return FN(UNION,intersect_params)(u,
810 isl_set_from_union_set(uset));
811 return FN(UNION,match_domain_op)(u, uset, &control);
812 }
813
814 /* This is an alternative name for the function above.
815 */
816 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
817 __isl_take isl_union_set *uset)
818 {
819 return FN(UNION,intersect_domain_union_set)(u, uset);
820 }
821
822 /* Return true if this part should be kept.
823 *
824 * In particular, it should be kept if its domain space
825 * corresponds to "space".
826 */
827 static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user)
828 {
829 isl_space *space = user;
830
831 return FN(PW,has_domain_space_tuples)(part, space);
832 }
833
834 /* Remove any not element in "space" from the domain of "u".
835 *
836 * In particular, select any part of the function defined
837 * on this domain space.
838 */
839 __isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u,
840 __isl_take isl_space *space)
841 {
842 S(UNION,transform_control) control = {
843 .filter = &FN(UNION,select_entry),
844 .filter_user = space,
845 };
846
847 u = FN(UNION,transform)(u, &control);
848 isl_space_free(space);
849 return u;
850 }
851
852 /* Is the domain of "pw" a wrapped relation?
853 */
854 static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw)
855 {
856 return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw));
857 }
858
859 /* Intersect the domain of the wrapped relation inside the domain of "u"
860 * with "uset".
861 */
862 __isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u,
863 __isl_take isl_union_set *uset)
864 {
865 S(UNION,match_domain_control) control = {
866 .filter = &FN(PART,domain_is_wrapping),
867 .match_space = &isl_space_factor_domain,
868 .fn = &FN(PW,intersect_domain_wrapped_domain),
869 };
870
871 return FN(UNION,match_domain_op)(u, uset, &control);
872 }
873
874 /* Intersect the range of the wrapped relation inside the domain of "u"
875 * with "uset".
876 */
877 __isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u,
878 __isl_take isl_union_set *uset)
879 {
880 S(UNION,match_domain_control) control = {
881 .filter = &FN(PART,domain_is_wrapping),
882 .match_space = &isl_space_factor_range,
883 .fn = &FN(PW,intersect_domain_wrapped_range),
884 };
885
886 return FN(UNION,match_domain_op)(u, uset, &control);
887 }
888
889 /* Take the set (which may be empty) in data->uset that lives
890 * in the same space as the domain of "pw", subtract it from the domain
891 * of "part" and return the result.
892 */
893 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
894 void *user)
895 {
896 isl_union_set *uset = user;
897 isl_space *space;
898 isl_set *set;
899
900 space = FN(PART,get_domain_space)(part);
901 set = isl_union_set_extract_set(uset, space);
902 return FN(PART,subtract_domain)(part, set);
903 }
904
905 /* Subtract "uset" from the domain of "u".
906 */
907 __isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u,
908 __isl_take isl_union_set *uset)
909 {
910 S(UNION,transform_control) control = {
911 .fn = &FN(UNION,subtract_domain_entry),
912 .fn_user = uset,
913 };
914
915 u = FN(UNION,transform)(u, &control);
916 isl_union_set_free(uset);
917 return u;
918 }
919
920 /* This is an alternative name for the function above.
921 */
922 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
923 __isl_take isl_union_set *uset)
924 {
925 return FN(UNION,subtract_domain_union_set)(u, uset);
926 }
927
928 /* Return true if this part should be kept.
929 *
930 * In particular, it should be kept if its domain space
931 * does not correspond to "space".
932 */
933 static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user)
934 {
935 isl_space *space = user;
936
937 return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space));
938 }
939
940 /* Remove any element in "space" from the domain of "u".
941 *
942 * In particular, filter out any part of the function defined
943 * on this domain space.
944 */
945 __isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u,
946 __isl_take isl_space *space)
947 {
948 S(UNION,transform_control) control = {
949 .filter = &FN(UNION,filter_out_entry),
950 .filter_user = space,
951 };
952
953 u = FN(UNION,transform)(u, &control);
954 isl_space_free(space);
955 return u;
956 }
957
958 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
959 __isl_take isl_union_set *uset)
960 {
961 S(UNION,match_domain_control) control = {
962 .fn = &FN(PW,gist),
963 };
964
965 if (isl_union_set_is_params(uset))
966 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
967 return FN(UNION,match_domain_op)(u, uset, &control);
968 }
969
970 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
971 * Since the UNION may have several references, the entry is only
972 * replaced if the coalescing is successful.
973 */
974 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
975 {
976 PART **part_p = (PART **) entry;
977 PART *part;
978
979 part = FN(PART,copy)(*part_p);
980 part = FN(PW,coalesce)(part);
981 if (!part)
982 return isl_stat_error;
983 FN(PART,free)(*part_p);
984 *part_p = part;
985
986 return isl_stat_ok;
987 }
988
989 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
990 {
991 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
992 goto error;
993
994 return u;
995 error:
996 FN(UNION,free)(u);
997 return NULL;
998 }
999
1000 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
1001 {
1002 isl_union_set **uset = (isl_union_set **)user;
1003
1004 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
1005
1006 return isl_stat_ok;
1007 }
1008
1009 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
1010 {
1011 isl_union_set *uset;
1012
1013 uset = isl_union_set_empty(FN(UNION,get_space)(u));
1014 if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
1015 goto error;
1016
1017 FN(UNION,free)(u);
1018
1019 return uset;
1020 error:
1021 isl_union_set_free(uset);
1022 FN(UNION,free)(u);
1023 return NULL;
1024 }
1025
1026 #ifdef HAS_TYPE
1027 /* Negate the type of "u".
1028 */
1029 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1030 {
1031 u = FN(UNION,cow)(u);
1032 if (!u)
1033 return NULL;
1034 u->type = isl_fold_type_negate(u->type);
1035 return u;
1036 }
1037 #else
1038 /* Negate the type of "u".
1039 * Since "u" does not have a type, do nothing.
1040 */
1041 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1042 {
1043 return u;
1044 }
1045 #endif
1046
1047 /* Multiply "part" by the isl_val "user" and return the result.
1048 */
1049 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1050 void *user)
1051 {
1052 isl_val *v = user;
1053
1054 return FN(PART,scale_val)(part, isl_val_copy(v));
1055 }
1056
1057 /* Multiply "u" by "v" and return the result.
1058 */
1059 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1060 __isl_take isl_val *v)
1061 {
1062 if (!u || !v)
1063 goto error;
1064 if (isl_val_is_one(v)) {
1065 isl_val_free(v);
1066 return u;
1067 }
1068
1069 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1070 UNION *zero;
1071 isl_space *space = FN(UNION,get_space)(u);
1072 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
1073 FN(UNION,free)(u);
1074 isl_val_free(v);
1075 return zero;
1076 }
1077
1078 if (!isl_val_is_rat(v))
1079 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1080 "expecting rational factor", goto error);
1081
1082 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1083 if (isl_val_is_neg(v))
1084 u = FN(UNION,negate_type)(u);
1085
1086 isl_val_free(v);
1087 return u;
1088 error:
1089 isl_val_free(v);
1090 FN(UNION,free)(u);
1091 return NULL;
1092 }
1093
1094 /* Divide "part" by the isl_val "user" and return the result.
1095 */
1096 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
1097 void *user)
1098 {
1099 isl_val *v = user;
1100
1101 return FN(PART,scale_down_val)(part, isl_val_copy(v));
1102 }
1103
1104 /* Divide "u" by "v" and return the result.
1105 */
1106 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1107 __isl_take isl_val *v)
1108 {
1109 if (!u || !v)
1110 goto error;
1111 if (isl_val_is_one(v)) {
1112 isl_val_free(v);
1113 return u;
1114 }
1115
1116 if (!isl_val_is_rat(v))
1117 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1118 "expecting rational factor", goto error);
1119 if (isl_val_is_zero(v))
1120 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1121 "cannot scale down by zero", goto error);
1122
1123 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
1124 if (isl_val_is_neg(v))
1125 u = FN(UNION,negate_type)(u);
1126
1127 isl_val_free(v);
1128 return u;
1129 error:
1130 isl_val_free(v);
1131 FN(UNION,free)(u);
1132 return NULL;
1133 }
1134
1135 /* Internal data structure for isl_union_*_every_*.
1136 *
1137 * "test" is the user-specified callback function.
1138 * "user" is the user-specified callback function argument.
1139 *
1140 * "res" is the final result, initialized to isl_bool_true.
1141 */
1142 S(UNION,every_data) {
1143 isl_bool (*test)(__isl_keep PW *pw, void *user);
1144 void *user;
1145
1146 isl_bool res;
1147 };
1148
1149 /* Call data->test on the piecewise expression at *entry,
1150 * updating the result in data->res.
1151 * Abort if this result is no longer isl_bool_true.
1152 */
1153 static isl_stat FN(UNION,every_entry)(void **entry, void *user)
1154 {
1155 S(UNION,every_data) *data = user;
1156 PW *pw = *entry;
1157
1158 data->res = data->test(pw, data->user);
1159 if (data->res < 0 || !data->res)
1160 return isl_stat_error;
1161
1162 return isl_stat_ok;
1163 }
1164
1165 /* Does "test" succeed on every piecewise expression in "u"?
1166 */
1167 isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u,
1168 isl_bool (*test)(__isl_keep PW *pw, void *user), void *user)
1169 {
1170 S(UNION,every_data) data = { test, user };
1171
1172 data.res = isl_bool_true;
1173 if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 &&
1174 data.res == isl_bool_true)
1175 return isl_bool_error;
1176
1177 return data.res;
1178 }
1179
1180 S(UNION,plain_is_equal_data)
1181 {
1182 UNION *u2;
1183 };
1184
1185 static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user)
1186 {
1187 S(UNION,plain_is_equal_data) *data = user;
1188 struct isl_hash_table_entry *entry;
1189
1190 entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1191 if (!entry)
1192 return isl_bool_error;
1193 if (entry == isl_hash_table_entry_none)
1194 return isl_bool_false;
1195
1196 return FN(PW,plain_is_equal)(pw, entry->data);
1197 }
1198
1199 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1200 {
1201 S(UNION,plain_is_equal_data) data;
1202 isl_size n1, n2;
1203 isl_bool is_equal;
1204
1205 if (!u1 || !u2)
1206 return isl_bool_error;
1207 if (u1 == u2)
1208 return isl_bool_true;
1209 if (u1->table.n != u2->table.n)
1210 return isl_bool_false;
1211 n1 = FN(FN(UNION,n),BASE)(u1);
1212 n2 = FN(FN(UNION,n),BASE)(u2);
1213 if (n1 < 0 || n2 < 0)
1214 return isl_bool_error;
1215 if (n1 != n2)
1216 return isl_bool_false;
1217
1218 u1 = FN(UNION,copy)(u1);
1219 u2 = FN(UNION,copy)(u2);
1220 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1221 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1222 if (!u1 || !u2)
1223 goto error;
1224
1225 data.u2 = u2;
1226 is_equal = FN(FN(UNION,every),BASE)(u1,
1227 &FN(UNION,plain_is_equal_el), &data);
1228
1229 FN(UNION,free)(u1);
1230 FN(UNION,free)(u2);
1231
1232 return is_equal;
1233 error:
1234 FN(UNION,free)(u1);
1235 FN(UNION,free)(u2);
1236 return isl_bool_error;
1237 }
1238
1239 /* An isl_union_*_every_* callback that checks whether "pw"
1240 * does not involve any NaNs.
1241 */
1242 static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user)
1243 {
1244 return isl_bool_not(FN(PW,involves_nan)(pw));
1245 }
1246
1247 /* Does "u" involve any NaNs?
1248 */
1249 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1250 {
1251 isl_bool no_nan;
1252
1253 no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL);
1254
1255 return isl_bool_not(no_nan);
1256 }
1257
1258 /* Internal data structure for isl_union_*_drop_dims.
1259 * type, first and n are passed to isl_*_drop_dims.
1260 */
1261 S(UNION,drop_dims_data) {
1262 enum isl_dim_type type;
1263 unsigned first;
1264 unsigned n;
1265 };
1266
1267 /* Drop the parameters specified by "data" from "part" and return the result.
1268 */
1269 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1270 void *user)
1271 {
1272 S(UNION,drop_dims_data) *data = user;
1273
1274 return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1275 }
1276
1277 /* Drop the specified parameters from "u".
1278 * That is, type is required to be isl_dim_param.
1279 */
1280 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1281 enum isl_dim_type type, unsigned first, unsigned n)
1282 {
1283 isl_space *space;
1284 S(UNION,drop_dims_data) data = { type, first, n };
1285 S(UNION,transform_control) control = {
1286 .fn = &FN(UNION,drop_dims_entry),
1287 .fn_user = &data,
1288 };
1289
1290 if (!u)
1291 return NULL;
1292
1293 if (type != isl_dim_param)
1294 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1295 "can only project out parameters",
1296 return FN(UNION,free)(u));
1297
1298 space = FN(UNION,get_space)(u);
1299 space = isl_space_drop_dims(space, type, first, n);
1300 return FN(UNION,transform_space)(u, space, &control);
1301 }
1302
1303 /* Internal data structure for isl_union_*_set_dim_name.
1304 * pos is the position of the parameter that needs to be renamed.
1305 * s is the new name.
1306 */
1307 S(UNION,set_dim_name_data) {
1308 unsigned pos;
1309 const char *s;
1310 };
1311
1312 /* Change the name of the parameter at position data->pos of "part" to data->s
1313 * and return the result.
1314 */
1315 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1316 void *user)
1317 {
1318 S(UNION,set_dim_name_data) *data = user;
1319
1320 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1321 }
1322
1323 /* Change the name of the parameter at position "pos" to "s".
1324 * That is, type is required to be isl_dim_param.
1325 */
1326 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1327 enum isl_dim_type type, unsigned pos, const char *s)
1328 {
1329 S(UNION,set_dim_name_data) data = { pos, s };
1330 S(UNION,transform_control) control = {
1331 .fn = &FN(UNION,set_dim_name_entry),
1332 .fn_user = &data,
1333 };
1334 isl_space *space;
1335
1336 if (!u)
1337 return NULL;
1338
1339 if (type != isl_dim_param)
1340 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1341 "can only set parameter names",
1342 return FN(UNION,free)(u));
1343
1344 space = FN(UNION,get_space)(u);
1345 space = isl_space_set_dim_name(space, type, pos, s);
1346 return FN(UNION,transform_space)(u, space, &control);
1347 }
1348
1349 /* Reset the user pointer on all identifiers of parameters and tuples
1350 * of the space of "part" and return the result.
1351 */
1352 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1353 void *user)
1354 {
1355 return FN(PART,reset_user)(part);
1356 }
1357
1358 /* Reset the user pointer on all identifiers of parameters and tuples
1359 * of the spaces of "u".
1360 */
1361 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1362 {
1363 S(UNION,transform_control) control = {
1364 .fn = &FN(UNION,reset_user_entry),
1365 };
1366 isl_space *space;
1367
1368 space = FN(UNION,get_space)(u);
1369 space = isl_space_reset_user(space);
1370 return FN(UNION,transform_space)(u, space, &control);
1371 }
1372
1373 /* Add the base expression held by "entry" to "list".
1374 */
1375 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1376 {
1377 PW *pw = *entry;
1378 LIST(PART) **list = user;
1379
1380 *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1381 if (!*list)
1382 return isl_stat_error;
1383
1384 return isl_stat_ok;
1385 }
1386
1387 /* Return a list containing all the base expressions in "u".
1388 *
1389 * First construct a list of the appropriate size and
1390 * then add all the elements.
1391 */
1392 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1393 {
1394 isl_size n;
1395 LIST(PART) *list;
1396
1397 if (!u)
1398 return NULL;
1399 n = FN(FN(UNION,n),BASE)(u);
1400 if (n < 0)
1401 return NULL;
1402 list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1403 if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1404 return FN(LIST(PART),free)(list);
1405
1406 return list;
1407 }
Integer set library