2 * Copyright 2010 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
13 #include <isl_hash_private.h>
14 #include <isl_union_macro.h>
16 /* A union of expressions defined over different domain spaces.
17 * "space" describes the parameters.
18 * The entries of "table" are keyed on the domain space of the entry.
27 struct isl_hash_table table
;
30 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
);
32 isl_ctx
*FN(UNION
,get_ctx
)(__isl_keep UNION
*u
)
34 return u
? u
->space
->ctx
: NULL
;
37 __isl_give isl_space
*FN(UNION
,get_space
)(__isl_keep UNION
*u
)
41 return isl_space_copy(u
->space
);
44 /* Return the number of parameters of "u", where "type"
45 * is required to be set to isl_dim_param.
47 unsigned FN(UNION
,dim
)(__isl_keep UNION
*u
, enum isl_dim_type type
)
52 if (type
!= isl_dim_param
)
53 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
54 "can only reference parameters", return 0);
56 return isl_space_dim(u
->space
, type
);
59 /* Return the position of the parameter with the given name
61 * Return -1 if no such dimension can be found.
63 int FN(UNION
,find_dim_by_name
)(__isl_keep UNION
*u
, enum isl_dim_type type
,
68 return isl_space_find_dim_by_name(u
->space
, type
, name
);
72 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
,
73 enum isl_fold type
, int size
)
75 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
, int size
)
80 dim
= isl_space_params(dim
);
84 u
= isl_calloc_type(dim
->ctx
, UNION
);
93 if (isl_hash_table_init(dim
->ctx
, &u
->table
, size
) < 0)
94 return FN(UNION
,free
)(u
);
103 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
, enum isl_fold type
)
105 return FN(UNION
,alloc
)(dim
, type
, 16);
108 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
)
110 return FN(UNION
,alloc
)(dim
, 16);
114 __isl_give UNION
*FN(UNION
,copy
)(__isl_keep UNION
*u
)
123 /* Return the number of base expressions in "u".
125 int FN(FN(UNION
,n
),PARTS
)(__isl_keep UNION
*u
)
127 return u
? u
->table
.n
: 0;
130 S(UNION
,foreach_data
)
132 isl_stat (*fn
)(__isl_take PART
*part
, void *user
);
136 static isl_stat
FN(UNION
,call_on_copy
)(void **entry
, void *user
)
139 S(UNION
,foreach_data
) *data
= (S(UNION
,foreach_data
) *)user
;
141 part
= FN(PART
,copy
)(part
);
143 return isl_stat_error
;
144 return data
->fn(part
, data
->user
);
147 isl_stat
FN(FN(UNION
,foreach
),PARTS
)(__isl_keep UNION
*u
,
148 isl_stat (*fn
)(__isl_take PART
*part
, void *user
), void *user
)
150 S(UNION
,foreach_data
) data
= { fn
, user
};
153 return isl_stat_error
;
155 return isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
156 &FN(UNION
,call_on_copy
), &data
);
159 /* Is the domain space of "entry" equal to the domain of "space"?
161 static int FN(UNION
,has_same_domain_space
)(const void *entry
, const void *val
)
163 PART
*part
= (PART
*)entry
;
164 isl_space
*space
= (isl_space
*) val
;
166 if (isl_space_is_set(space
))
167 return isl_space_is_set(part
->dim
);
169 return isl_space_tuple_is_equal(part
->dim
, isl_dim_in
,
173 /* Return the entry, if any, in "u" that lives in "space".
174 * If "reserve" is set, then an entry is created if it does not exist yet.
175 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
176 * Note that when "reserve" is set, the function will never return
177 * isl_hash_table_entry_none.
179 * First look for the entry (if any) with the same domain space.
180 * If it exists, then check if the range space also matches.
182 static struct isl_hash_table_entry
*FN(UNION
,find_part_entry
)(
183 __isl_keep UNION
*u
, __isl_keep isl_space
*space
, int reserve
)
187 struct isl_hash_table_entry
*entry
;
194 ctx
= FN(UNION
,get_ctx
)(u
);
195 hash
= isl_space_get_domain_hash(space
);
196 entry
= isl_hash_table_find(ctx
, &u
->table
, hash
,
197 &FN(UNION
,has_same_domain_space
), space
, reserve
);
199 return reserve
? NULL
: isl_hash_table_entry_none
;
200 if (reserve
&& !entry
->data
)
203 equal
= isl_space_tuple_is_equal(part
->dim
, isl_dim_out
,
210 return isl_hash_table_entry_none
;
211 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
212 "union expression can only contain a single "
213 "expression over a given domain", return NULL
);
216 /* Remove "part_entry" from the hash table of "u".
218 static __isl_give UNION
*FN(UNION
,remove_part_entry
)(__isl_take UNION
*u
,
219 struct isl_hash_table_entry
*part_entry
)
223 if (!u
|| !part_entry
)
224 return FN(UNION
,free
)(u
);
226 ctx
= FN(UNION
,get_ctx
)(u
);
227 isl_hash_table_remove(ctx
, &u
->table
, part_entry
);
228 FN(PART
,free
)(part_entry
->data
);
233 /* Extract the element of "u" living in "space" (ignoring parameters).
235 * Return the ZERO element if "u" does not contain any element
238 __isl_give PART
*FN(FN(UNION
,extract
),PARTS
)(__isl_keep UNION
*u
,
239 __isl_take isl_space
*space
)
241 struct isl_hash_table_entry
*entry
;
245 if (!isl_space_match(u
->space
, isl_dim_param
, space
, isl_dim_param
)) {
246 space
= isl_space_drop_dims(space
, isl_dim_param
,
247 0, isl_space_dim(space
, isl_dim_param
));
248 space
= isl_space_align_params(space
,
249 FN(UNION
,get_space
)(u
));
254 entry
= FN(UNION
,find_part_entry
)(u
, space
, 0);
257 if (entry
== isl_hash_table_entry_none
)
259 return FN(PART
,ZERO
)(space
, u
->type
);
261 return FN(PART
,ZERO
)(space
);
263 isl_space_free(space
);
264 return FN(PART
,copy
)(entry
->data
);
266 isl_space_free(space
);
270 /* Add "part" to "u".
271 * If "disjoint" is set, then "u" is not allowed to already have
272 * a part that is defined on the same space as "part".
273 * Otherwise, compute the union sum of "part" and the part in "u"
274 * defined on the same space.
276 static __isl_give UNION
*FN(UNION
,add_part_generic
)(__isl_take UNION
*u
,
277 __isl_take PART
*part
, int disjoint
)
280 struct isl_hash_table_entry
*entry
;
285 empty
= FN(PART
,IS_ZERO
)(part
);
293 u
= FN(UNION
,align_params
)(u
, FN(PART
,get_space
)(part
));
294 part
= FN(PART
,align_params
)(part
, FN(UNION
,get_space
)(u
));
296 u
= FN(UNION
,cow
)(u
);
301 entry
= FN(UNION
,find_part_entry
)(u
, part
->dim
, 1);
309 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
310 "additional part should live on separate "
311 "space", goto error
);
312 entry
->data
= FN(PART
,union_add_
)(entry
->data
,
313 FN(PART
,copy
)(part
));
316 empty
= FN(PART
,IS_ZERO
)(part
);
320 u
= FN(UNION
,remove_part_entry
)(u
, entry
);
331 /* Add "part" to "u", where "u" is assumed not to already have
332 * a part that is defined on the same space as "part".
334 __isl_give UNION
*FN(FN(UNION
,add
),PARTS
)(__isl_take UNION
*u
,
335 __isl_take PART
*part
)
337 return FN(UNION
,add_part_generic
)(u
, part
, 1);
341 /* Allocate a UNION with the same type and the same size as "u" and
342 * with space "space".
344 static __isl_give UNION
*FN(UNION
,alloc_same_size_on_space
)(__isl_keep UNION
*u
,
345 __isl_take isl_space
*space
)
348 space
= isl_space_free(space
);
349 return FN(UNION
,alloc
)(space
, u
->type
, u
->table
.n
);
352 /* Allocate a UNION with the same size as "u" and with space "space".
354 static __isl_give UNION
*FN(UNION
,alloc_same_size_on_space
)(__isl_keep UNION
*u
,
355 __isl_take isl_space
*space
)
358 space
= isl_space_free(space
);
359 return FN(UNION
,alloc
)(space
, u
->table
.n
);
363 /* Allocate a UNION with the same space, the same type (if any) and
364 * the same size as "u".
366 static __isl_give UNION
*FN(UNION
,alloc_same_size
)(__isl_keep UNION
*u
)
368 return FN(UNION
,alloc_same_size_on_space
)(u
, FN(UNION
,get_space
)(u
));
371 /* Call "fn" on each part entry of "u".
373 static isl_stat
FN(UNION
,foreach_inplace
)(__isl_keep UNION
*u
,
374 isl_stat (*fn
)(void **part
, void *user
), void *user
)
379 return isl_stat_error
;
380 ctx
= FN(UNION
,get_ctx
)(u
);
381 return isl_hash_table_foreach(ctx
, &u
->table
, fn
, user
);
384 /* Does "u" have a single reference?
385 * That is, can we change "u" inplace?
387 static isl_bool
FN(UNION
,has_single_reference
)(__isl_keep UNION
*u
)
390 return isl_bool_error
;
394 /* Internal data structure for isl_union_*_transform_space.
395 * "fn' is applied to each entry in the input.
396 * "res" collects the results.
398 S(UNION
,transform_data
)
400 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
);
406 /* Apply data->fn to "part" and add the result to data->res.
408 static isl_stat
FN(UNION
,transform_entry
)(__isl_take PART
*part
, void *user
)
410 S(UNION
,transform_data
) *data
= (S(UNION
,transform_data
) *)user
;
412 part
= data
->fn(part
, data
->user
);
413 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
415 return isl_stat_error
;
420 /* Return a UNION living in "space" that is obtained by applying "fn"
421 * to each of the entries in "u".
423 static __isl_give UNION
*FN(UNION
,transform_space
)(__isl_take UNION
*u
,
425 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
427 S(UNION
,transform_data
) data
= { fn
, user
};
429 data
.res
= FN(UNION
,alloc_same_size_on_space
)(u
, space
);
430 if (FN(FN(UNION
,foreach
),PARTS
)(u
,
431 &FN(UNION
,transform_entry
), &data
) < 0)
432 data
.res
= FN(UNION
,free
)(data
.res
);
437 /* Return a UNION that lives in the same space as "u" and that is obtained
438 * by applying "fn" to each of the entries in "u".
440 static __isl_give UNION
*FN(UNION
,transform
)(__isl_take UNION
*u
,
441 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
443 return FN(UNION
,transform_space
)(u
, FN(UNION
,get_space
)(u
), fn
, user
);
446 /* Apply data->fn to *part and store the result back into *part.
448 static isl_stat
FN(UNION
,transform_inplace_entry
)(void **part
, void *user
)
450 S(UNION
,transform_data
) *data
= (S(UNION
,transform_data
) *) user
;
452 *part
= data
->fn(*part
, data
->user
);
454 return isl_stat_error
;
458 /* Update "u" by applying "fn" to each entry.
459 * This operation is assumed not to change the number of entries nor
460 * the spaces of the entries.
462 * If there is only one reference to "u", then change "u" inplace.
463 * Otherwise, create a new UNION from "u" and discard the original.
465 static __isl_give UNION
*FN(UNION
,transform_inplace
)(__isl_take UNION
*u
,
466 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
470 single_ref
= FN(UNION
,has_single_reference
)(u
);
472 return FN(UNION
,free
)(u
);
474 S(UNION
,transform_data
) data
= { fn
, user
};
475 if (FN(UNION
,foreach_inplace
)(u
,
476 &FN(UNION
,transform_inplace_entry
), &data
) < 0)
477 return FN(UNION
,free
)(u
);
480 return FN(UNION
,transform
)(u
, fn
, user
);
483 /* An isl_union_*_transform callback for use in isl_union_*_dup
484 * that simply returns "part".
486 static __isl_give PART
*FN(UNION
,copy_part
)(__isl_take PART
*part
, void *user
)
491 __isl_give UNION
*FN(UNION
,dup
)(__isl_keep UNION
*u
)
493 u
= FN(UNION
,copy
)(u
);
494 return FN(UNION
,transform
)(u
, &FN(UNION
,copy_part
), NULL
);
497 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
)
505 return FN(UNION
,dup
)(u
);
508 static isl_stat
FN(UNION
,free_u_entry
)(void **entry
, void *user
)
515 __isl_null UNION
*FN(UNION
,free
)(__isl_take UNION
*u
)
523 isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
524 &FN(UNION
,free_u_entry
), NULL
);
525 isl_hash_table_clear(&u
->table
);
526 isl_space_free(u
->space
);
531 static __isl_give PART
*FN(UNION
,align_entry
)(__isl_take PART
*part
, void *user
)
533 isl_reordering
*exp
= user
;
535 exp
= isl_reordering_extend_space(isl_reordering_copy(exp
),
536 FN(PART
,get_domain_space
)(part
));
537 return FN(PART
,realign_domain
)(part
, exp
);
540 /* Reorder the parameters of "u" according to the given reordering.
542 static __isl_give UNION
*FN(UNION
,realign_domain
)(__isl_take UNION
*u
,
543 __isl_take isl_reordering
*r
)
550 space
= isl_space_copy(r
->dim
);
551 u
= FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,align_entry
), r
);
552 isl_reordering_free(r
);
556 isl_reordering_free(r
);
560 /* Align the parameters of "u" to those of "model".
562 __isl_give UNION
*FN(UNION
,align_params
)(__isl_take UNION
*u
,
563 __isl_take isl_space
*model
)
570 if (isl_space_match(u
->space
, isl_dim_param
, model
, isl_dim_param
)) {
571 isl_space_free(model
);
575 model
= isl_space_params(model
);
576 r
= isl_parameter_alignment_reordering(u
->space
, model
);
577 isl_space_free(model
);
579 return FN(UNION
,realign_domain
)(u
, r
);
581 isl_space_free(model
);
586 /* Add "part" to *u, taking the union sum if "u" already has
587 * a part defined on the same space as "part".
589 static isl_stat
FN(UNION
,union_add_part
)(__isl_take PART
*part
, void *user
)
591 UNION
**u
= (UNION
**)user
;
593 *u
= FN(UNION
,add_part_generic
)(*u
, part
, 0);
598 /* Compute the sum of "u1" and "u2" on the union of their domains,
599 * with the actual sum on the shared domain and
600 * the defined expression on the symmetric difference of the domains.
602 * This is an internal function that is exposed under different
603 * names depending on whether the base expressions have a zero default
605 * If they do, then this function is called "add".
606 * Otherwise, it is called "union_add".
608 static __isl_give UNION
*FN(UNION
,union_add_
)(__isl_take UNION
*u1
,
609 __isl_take UNION
*u2
)
611 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
612 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
614 u1
= FN(UNION
,cow
)(u1
);
619 if (FN(FN(UNION
,foreach
),PARTS
)(u2
, &FN(UNION
,union_add_part
), &u1
) < 0)
631 __isl_give UNION
*FN(FN(UNION
,from
),PARTS
)(__isl_take PART
*part
)
639 dim
= FN(PART
,get_space
)(part
);
640 dim
= isl_space_drop_dims(dim
, isl_dim_in
, 0, isl_space_dim(dim
, isl_dim_in
));
641 dim
= isl_space_drop_dims(dim
, isl_dim_out
, 0, isl_space_dim(dim
, isl_dim_out
));
643 u
= FN(UNION
,ZERO
)(dim
, part
->type
);
645 u
= FN(UNION
,ZERO
)(dim
);
647 u
= FN(FN(UNION
,add
),PARTS
)(u
, part
);
652 S(UNION
,match_bin_data
) {
655 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*);
658 /* Check if data->u2 has an element living in the same space as "part".
659 * If so, call data->fn on the two elements and add the result to
662 static isl_stat
FN(UNION
,match_bin_entry
)(__isl_take PART
*part
, void *user
)
664 S(UNION
,match_bin_data
) *data
= user
;
665 struct isl_hash_table_entry
*entry2
;
669 space
= FN(PART
,get_space
)(part
);
670 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, space
, 0);
671 isl_space_free(space
);
674 if (entry2
== isl_hash_table_entry_none
) {
679 part2
= entry2
->data
;
680 if (!isl_space_tuple_is_equal(part
->dim
, isl_dim_out
,
681 part2
->dim
, isl_dim_out
))
682 isl_die(FN(UNION
,get_ctx
)(data
->u2
), isl_error_invalid
,
683 "entries should have the same range space",
686 part
= data
->fn(part
, FN(PART
, copy
)(entry2
->data
));
688 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
690 return isl_stat_error
;
695 return isl_stat_error
;
698 /* This function is currently only used from isl_polynomial.c
699 * and not from isl_fold.c.
701 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
702 __isl_take UNION
*u2
,
703 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
704 __attribute__ ((unused
));
705 /* For each pair of elements in "u1" and "u2" living in the same space,
706 * call "fn" and collect the results.
708 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
709 __isl_take UNION
*u2
,
710 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
712 S(UNION
,match_bin_data
) data
= { NULL
, NULL
, fn
};
714 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
715 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
721 data
.res
= FN(UNION
,alloc_same_size
)(u1
);
722 if (FN(FN(UNION
,foreach
),PARTS
)(u1
,
723 &FN(UNION
,match_bin_entry
), &data
) < 0)
732 FN(UNION
,free
)(data
.res
);
736 /* Compute the sum of "u1" and "u2".
738 * If the base expressions have a default zero value, then the sum
739 * is computed on the union of the domains of "u1" and "u2".
740 * Otherwise, it is computed on their shared domains.
742 __isl_give UNION
*FN(UNION
,add
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
745 return FN(UNION
,union_add_
)(u1
, u2
);
747 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,add
));
752 /* Subtract "u2" from "u1" and return the result.
754 __isl_give UNION
*FN(UNION
,sub
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
756 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,sub
));
760 S(UNION
,any_set_data
) {
762 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
765 static __isl_give PART
*FN(UNION
,any_set_entry
)(__isl_take PART
*part
,
768 S(UNION
,any_set_data
) *data
= user
;
770 return data
->fn(part
, isl_set_copy(data
->set
));
773 /* Update each element of "u" by calling "fn" on the element and "set".
775 static __isl_give UNION
*FN(UNION
,any_set_op
)(__isl_take UNION
*u
,
776 __isl_take isl_set
*set
,
777 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
779 S(UNION
,any_set_data
) data
= { NULL
, fn
};
781 u
= FN(UNION
,align_params
)(u
, isl_set_get_space(set
));
782 set
= isl_set_align_params(set
, FN(UNION
,get_space
)(u
));
788 u
= FN(UNION
,transform
)(u
, &FN(UNION
,any_set_entry
), &data
);
797 /* Intersect the domain of "u" with the parameter domain "context".
799 __isl_give UNION
*FN(UNION
,intersect_params
)(__isl_take UNION
*u
,
800 __isl_take isl_set
*set
)
802 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,intersect_params
));
805 /* Compute the gist of the domain of "u" with respect to
806 * the parameter domain "context".
808 __isl_give UNION
*FN(UNION
,gist_params
)(__isl_take UNION
*u
,
809 __isl_take isl_set
*set
)
811 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,gist_params
));
814 S(UNION
,match_domain_data
) {
817 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
820 static int FN(UNION
,set_has_dim
)(const void *entry
, const void *val
)
822 isl_set
*set
= (isl_set
*)entry
;
823 isl_space
*dim
= (isl_space
*)val
;
825 return isl_space_is_equal(set
->dim
, dim
);
828 /* Find the set in data->uset that lives in the same space as the domain
829 * of "part", apply data->fn to *entry and this set (if any), and add
830 * the result to data->res.
832 static isl_stat
FN(UNION
,match_domain_entry
)(__isl_take PART
*part
, void *user
)
834 S(UNION
,match_domain_data
) *data
= user
;
836 struct isl_hash_table_entry
*entry2
;
839 space
= FN(PART
,get_domain_space
)(part
);
840 hash
= isl_space_get_hash(space
);
841 entry2
= isl_hash_table_find(data
->uset
->dim
->ctx
, &data
->uset
->table
,
842 hash
, &FN(UNION
,set_has_dim
), space
, 0);
843 isl_space_free(space
);
849 part
= data
->fn(part
, isl_set_copy(entry2
->data
));
851 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
853 return isl_stat_error
;
858 /* Apply fn to each pair of PW in u and set in uset such that
859 * the set lives in the same space as the domain of PW
860 * and collect the results.
862 static __isl_give UNION
*FN(UNION
,match_domain_op
)(__isl_take UNION
*u
,
863 __isl_take isl_union_set
*uset
,
864 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
866 S(UNION
,match_domain_data
) data
= { NULL
, NULL
, fn
};
868 u
= FN(UNION
,align_params
)(u
, isl_union_set_get_space(uset
));
869 uset
= isl_union_set_align_params(uset
, FN(UNION
,get_space
)(u
));
875 data
.res
= FN(UNION
,alloc_same_size
)(u
);
876 if (FN(FN(UNION
,foreach
),PARTS
)(u
,
877 &FN(UNION
,match_domain_entry
), &data
) < 0)
881 isl_union_set_free(uset
);
885 isl_union_set_free(uset
);
886 FN(UNION
,free
)(data
.res
);
890 /* Intersect the domain of "u" with "uset".
891 * If "uset" is a parameters domain, then intersect the parameter
892 * domain of "u" with this set.
894 __isl_give UNION
*FN(UNION
,intersect_domain
)(__isl_take UNION
*u
,
895 __isl_take isl_union_set
*uset
)
897 if (isl_union_set_is_params(uset
))
898 return FN(UNION
,intersect_params
)(u
,
899 isl_set_from_union_set(uset
));
900 return FN(UNION
,match_domain_op
)(u
, uset
, &FN(PW
,intersect_domain
));
903 /* Take the set (which may be empty) in data->uset that lives
904 * in the same space as the domain of "pw", subtract it from the domain
905 * of "part" and return the result.
907 static __isl_give PART
*FN(UNION
,subtract_domain_entry
)(__isl_take PART
*part
,
910 isl_union_set
*uset
= user
;
914 space
= FN(PART
,get_domain_space
)(part
);
915 set
= isl_union_set_extract_set(uset
, space
);
916 return FN(PART
,subtract_domain
)(part
, set
);
919 /* Subtract "uset' from the domain of "u".
921 __isl_give UNION
*FN(UNION
,subtract_domain
)(__isl_take UNION
*u
,
922 __isl_take isl_union_set
*uset
)
924 u
= FN(UNION
,transform
)(u
, &FN(UNION
,subtract_domain_entry
), uset
);
925 isl_union_set_free(uset
);
929 __isl_give UNION
*FN(UNION
,gist
)(__isl_take UNION
*u
,
930 __isl_take isl_union_set
*uset
)
932 if (isl_union_set_is_params(uset
))
933 return FN(UNION
,gist_params
)(u
, isl_set_from_union_set(uset
));
934 return FN(UNION
,match_domain_op
)(u
, uset
, &FN(PW
,gist
));
937 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
938 * Since the UNION may have several references, the entry is only
939 * replaced if the coalescing is successful.
941 static isl_stat
FN(UNION
,coalesce_entry
)(void **entry
, void *user
)
943 PART
**part_p
= (PART
**) entry
;
946 part
= FN(PART
,copy
)(*part_p
);
947 part
= FN(PW
,coalesce
)(part
);
949 return isl_stat_error
;
950 FN(PART
,free
)(*part_p
);
956 __isl_give UNION
*FN(UNION
,coalesce
)(__isl_take UNION
*u
)
958 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,coalesce_entry
), NULL
) < 0)
967 static isl_stat
FN(UNION
,domain_entry
)(__isl_take PART
*part
, void *user
)
969 isl_union_set
**uset
= (isl_union_set
**)user
;
971 *uset
= isl_union_set_add_set(*uset
, FN(PART
,domain
)(part
));
976 __isl_give isl_union_set
*FN(UNION
,domain
)(__isl_take UNION
*u
)
980 uset
= isl_union_set_empty(FN(UNION
,get_space
)(u
));
981 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &FN(UNION
,domain_entry
), &uset
) < 0)
988 isl_union_set_free(uset
);
994 /* Negate the type of "u".
996 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
998 u
= FN(UNION
,cow
)(u
);
1001 u
->type
= isl_fold_type_negate(u
->type
);
1005 /* Negate the type of "u".
1006 * Since "u" does not have a type, do nothing.
1008 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
1014 static __isl_give PART
*FN(UNION
,mul_isl_int_entry
)(__isl_take PART
*part
,
1019 return FN(PW
,mul_isl_int
)(part
, *v
);
1022 __isl_give UNION
*FN(UNION
,mul_isl_int
)(__isl_take UNION
*u
, isl_int v
)
1024 if (isl_int_is_one(v
))
1027 if (DEFAULT_IS_ZERO
&& u
&& isl_int_is_zero(v
)) {
1029 isl_space
*dim
= FN(UNION
,get_space
)(u
);
1031 zero
= FN(UNION
,ZERO
)(dim
, u
->type
);
1033 zero
= FN(UNION
,ZERO
)(dim
);
1039 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,mul_isl_int_entry
), &v
);
1040 if (isl_int_is_neg(v
))
1041 u
= FN(UNION
,negate_type
)(u
);
1046 /* Multiply "part" by the isl_val "user" and return the result.
1048 static __isl_give PART
*FN(UNION
,scale_val_entry
)(__isl_take PART
*part
,
1053 return FN(PART
,scale_val
)(part
, isl_val_copy(v
));
1056 /* Multiply "u" by "v" and return the result.
1058 __isl_give UNION
*FN(UNION
,scale_val
)(__isl_take UNION
*u
,
1059 __isl_take isl_val
*v
)
1063 if (isl_val_is_one(v
)) {
1068 if (DEFAULT_IS_ZERO
&& u
&& isl_val_is_zero(v
)) {
1070 isl_space
*space
= FN(UNION
,get_space
)(u
);
1072 zero
= FN(UNION
,ZERO
)(space
, u
->type
);
1074 zero
= FN(UNION
,ZERO
)(space
);
1081 if (!isl_val_is_rat(v
))
1082 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1083 "expecting rational factor", goto error
);
1085 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_val_entry
), v
);
1086 if (isl_val_is_neg(v
))
1087 u
= FN(UNION
,negate_type
)(u
);
1097 /* Divide "part" by the isl_val "user" and return the result.
1099 static __isl_give PART
*FN(UNION
,scale_down_val_entry
)(__isl_take PART
*part
,
1104 return FN(PART
,scale_down_val
)(part
, isl_val_copy(v
));
1107 /* Divide "u" by "v" and return the result.
1109 __isl_give UNION
*FN(UNION
,scale_down_val
)(__isl_take UNION
*u
,
1110 __isl_take isl_val
*v
)
1114 if (isl_val_is_one(v
)) {
1119 if (!isl_val_is_rat(v
))
1120 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1121 "expecting rational factor", goto error
);
1122 if (isl_val_is_zero(v
))
1123 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1124 "cannot scale down by zero", goto error
);
1126 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_down_val_entry
), v
);
1127 if (isl_val_is_neg(v
))
1128 u
= FN(UNION
,negate_type
)(u
);
1138 S(UNION
,plain_is_equal_data
)
1144 static isl_stat
FN(UNION
,plain_is_equal_entry
)(void **entry
, void *user
)
1146 S(UNION
,plain_is_equal_data
) *data
= user
;
1147 struct isl_hash_table_entry
*entry2
;
1150 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, pw
->dim
, 0);
1151 if (!entry2
|| entry2
== isl_hash_table_entry_none
) {
1153 data
->is_equal
= isl_bool_error
;
1155 data
->is_equal
= isl_bool_false
;
1156 return isl_stat_error
;
1159 data
->is_equal
= FN(PW
,plain_is_equal
)(pw
, entry2
->data
);
1160 if (data
->is_equal
< 0 || !data
->is_equal
)
1161 return isl_stat_error
;
1166 isl_bool
FN(UNION
,plain_is_equal
)(__isl_keep UNION
*u1
, __isl_keep UNION
*u2
)
1168 S(UNION
,plain_is_equal_data
) data
= { NULL
, isl_bool_true
};
1172 return isl_bool_error
;
1174 return isl_bool_true
;
1175 if (u1
->table
.n
!= u2
->table
.n
)
1176 return isl_bool_false
;
1177 n1
= FN(FN(UNION
,n
),PARTS
)(u1
);
1178 n2
= FN(FN(UNION
,n
),PARTS
)(u2
);
1179 if (n1
< 0 || n2
< 0)
1180 return isl_bool_error
;
1182 return isl_bool_false
;
1184 u1
= FN(UNION
,copy
)(u1
);
1185 u2
= FN(UNION
,copy
)(u2
);
1186 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
1187 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
1192 if (FN(UNION
,foreach_inplace
)(u1
,
1193 &FN(UNION
,plain_is_equal_entry
), &data
) < 0 &&
1200 return data
.is_equal
;
1204 return isl_bool_error
;
1207 /* Internal data structure for isl_union_*_drop_dims.
1208 * type, first and n are passed to isl_*_drop_dims.
1210 S(UNION
,drop_dims_data
) {
1211 enum isl_dim_type type
;
1216 /* Drop the parameters specified by "data" from "part" and return the result.
1218 static __isl_give PART
*FN(UNION
,drop_dims_entry
)(__isl_take PART
*part
,
1221 S(UNION
,drop_dims_data
) *data
= user
;
1223 return FN(PART
,drop_dims
)(part
, data
->type
, data
->first
, data
->n
);
1226 /* Drop the specified parameters from "u".
1227 * That is, type is required to be isl_dim_param.
1229 __isl_give UNION
*FN(UNION
,drop_dims
)( __isl_take UNION
*u
,
1230 enum isl_dim_type type
, unsigned first
, unsigned n
)
1233 S(UNION
,drop_dims_data
) data
= { type
, first
, n
};
1238 if (type
!= isl_dim_param
)
1239 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1240 "can only project out parameters",
1241 return FN(UNION
,free
)(u
));
1243 space
= FN(UNION
,get_space
)(u
);
1244 space
= isl_space_drop_dims(space
, type
, first
, n
);
1245 return FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,drop_dims_entry
),
1249 /* Internal data structure for isl_union_*_set_dim_name.
1250 * pos is the position of the parameter that needs to be renamed.
1251 * s is the new name.
1253 S(UNION
,set_dim_name_data
) {
1258 /* Change the name of the parameter at position data->pos of "part" to data->s
1259 * and return the result.
1261 static __isl_give PART
*FN(UNION
,set_dim_name_entry
)(__isl_take PART
*part
,
1264 S(UNION
,set_dim_name_data
) *data
= user
;
1266 return FN(PART
,set_dim_name
)(part
, isl_dim_param
, data
->pos
, data
->s
);
1269 /* Change the name of the parameter at position "pos" to "s".
1270 * That is, type is required to be isl_dim_param.
1272 __isl_give UNION
*FN(UNION
,set_dim_name
)(__isl_take UNION
*u
,
1273 enum isl_dim_type type
, unsigned pos
, const char *s
)
1275 S(UNION
,set_dim_name_data
) data
= { pos
, s
};
1281 if (type
!= isl_dim_param
)
1282 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1283 "can only set parameter names",
1284 return FN(UNION
,free
)(u
));
1286 space
= FN(UNION
,get_space
)(u
);
1287 space
= isl_space_set_dim_name(space
, type
, pos
, s
);
1288 return FN(UNION
,transform_space
)(u
, space
,
1289 &FN(UNION
,set_dim_name_entry
), &data
);
1292 /* Reset the user pointer on all identifiers of parameters and tuples
1293 * of the space of "part" and return the result.
1295 static __isl_give PART
*FN(UNION
,reset_user_entry
)(__isl_take PART
*part
,
1298 return FN(PART
,reset_user
)(part
);
1301 /* Reset the user pointer on all identifiers of parameters and tuples
1302 * of the spaces of "u".
1304 __isl_give UNION
*FN(UNION
,reset_user
)(__isl_take UNION
*u
)
1308 space
= FN(UNION
,get_space
)(u
);
1309 space
= isl_space_reset_user(space
);
1310 return FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,reset_user_entry
),