2 * Copyright 2010 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 * Copyright 2015 INRIA Paris-Rocquencourt
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
13 * 78153 Le Chesnay Cedex France
17 #include <isl_union_macro.h>
19 /* A group of expressions defined over the same domain space "domain_space".
20 * The entries of "part_table" are the individual expressions,
21 * keyed on the entire space of the expression.
23 * Each UNION has its own groups, so there can only ever be a single
24 * reference to each group.
27 isl_space
*domain_space
;
28 struct isl_hash_table part_table
;
31 /* A union of expressions defined over different disjoint domains.
32 * "space" describes the parameters.
33 * The entries of "table" are keyed on the domain space of the entry and
34 * contain groups of expressions that are defined over the same domain space.
40 struct isl_hash_table table
;
43 /* Internal data structure for isl_union_*_foreach_group.
44 * "fn" is the function that needs to be called on each group.
46 S(UNION
,foreach_group_data
)
48 isl_stat (*fn
)(__isl_keep
S(UNION
,group
) *group
, void *user
);
52 /* Call data->fn on the group stored at *entry.
54 static isl_stat
FN(UNION
,call_on_group
)(void **entry
, void *user
)
56 S(UNION
,group
) *group
= *entry
;
57 S(UNION
,foreach_group_data
) *data
;
59 data
= (S(UNION
,foreach_group_data
) *) user
;
60 return data
->fn(group
, data
->user
);
63 /* Call "fn" on each group of expressions in "u".
65 static isl_stat
FN(UNION
,foreach_group
)(__isl_keep UNION
*u
,
66 isl_stat (*fn
)(__isl_keep
S(UNION
,group
) *group
, void *user
),
69 S(UNION
,foreach_group_data
) data
= { fn
, user
};
72 return isl_stat_error
;
74 return isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
75 &FN(UNION
,call_on_group
), &data
);
78 /* A isl_union_*_foreach_group callback for counting the total number
79 * of expressions in a UNION. Add the number of expressions in "group"
82 static isl_stat
FN(UNION
,count_part
)(__isl_keep
S(UNION
,group
) *group
,
88 return isl_stat_error
;
90 *n
+= group
->part_table
.n
;
94 /* Return the number of base expressions in "u".
96 isl_size
FN(FN(UNION
,n
),BASE
)(__isl_keep UNION
*u
)
101 if (FN(UNION
,foreach_group
)(u
, &FN(UNION
,count_part
), &n
) < 0)
102 return isl_size_error
;
106 /* Free an entry in a group of expressions.
107 * Each entry in such a group is a single expression.
109 static isl_stat
FN(UNION
,free_group_entry
)(void **entry
, void *user
)
117 /* Free all memory allocated for "group" and return NULL.
119 static __isl_null
S(UNION
,group
) *FN(UNION
,group_free
)(
120 __isl_take
S(UNION
,group
) *group
)
127 ctx
= isl_space_get_ctx(group
->domain_space
);
128 isl_hash_table_foreach(ctx
, &group
->part_table
,
129 &FN(UNION
,free_group_entry
), NULL
);
130 isl_hash_table_clear(&group
->part_table
);
131 isl_space_free(group
->domain_space
);
136 /* Allocate a group of expressions defined over the same domain space
137 * with domain space "domain_space" and initial size "size".
139 static __isl_give
S(UNION
,group
) *FN(UNION
,group_alloc
)(
140 __isl_take isl_space
*domain_space
, int size
)
143 S(UNION
,group
) *group
;
147 ctx
= isl_space_get_ctx(domain_space
);
148 group
= isl_calloc_type(ctx
, S(UNION
,group
));
151 group
->domain_space
= domain_space
;
152 if (isl_hash_table_init(ctx
, &group
->part_table
, size
) < 0)
153 return FN(UNION
,group_free
)(group
);
157 isl_space_free(domain_space
);
161 /* Is the space of "entry" equal to "space"?
163 static isl_bool
FN(UNION
,has_space
)(const void *entry
, const void *val
)
165 PART
*part
= (PART
*) entry
;
166 isl_space
*space
= (isl_space
*) val
;
167 isl_space
*part_space
;
169 part_space
= FN(PART
,peek_space
)(part
);
170 return isl_space_is_equal(part_space
, space
);
173 /* Return a group equal to "group", but with a single reference.
174 * Since all groups have only a single reference, simply return "group".
176 static __isl_give
S(UNION
,group
) *FN(UNION
,group_cow
)(
177 __isl_take
S(UNION
,group
) *group
)
182 S(UNION
,foreach_data
)
184 isl_stat (*fn
)(__isl_take PART
*part
, void *user
);
188 static isl_stat
FN(UNION
,call_on_copy
)(void **entry
, void *user
)
191 S(UNION
,foreach_data
) *data
= (S(UNION
,foreach_data
) *) user
;
193 part
= FN(PART
,copy
)(part
);
195 return isl_stat_error
;
196 return data
->fn(part
, data
->user
);
199 /* Call data->fn on a copy of each expression in "group".
201 static isl_stat
FN(UNION
,group_call_on_copy
)(__isl_keep
S(UNION
,group
) *group
,
207 return isl_stat_error
;
209 ctx
= isl_space_get_ctx(group
->domain_space
);
210 return isl_hash_table_foreach(ctx
, &group
->part_table
,
211 &FN(UNION
,call_on_copy
), user
);
214 isl_stat
FN(FN(UNION
,foreach
),BASE
)(__isl_keep UNION
*u
,
215 isl_stat (*fn
)(__isl_take PART
*part
, void *user
), void *user
)
217 S(UNION
,foreach_data
) data
= { fn
, user
};
220 return isl_stat_error
;
222 return FN(UNION
,foreach_group
)(u
, &FN(UNION
,group_call_on_copy
), &data
);
225 /* Is the domain space of the group of expressions at "entry"
226 * equal to that of "space"?
228 static isl_bool
FN(UNION
,group_has_same_domain_space
)(const void *entry
,
231 S(UNION
,group
) *group
= (S(UNION
,group
) *) entry
;
232 isl_space
*space
= (isl_space
*) val
;
234 return isl_space_is_domain_internal(group
->domain_space
, space
);
237 /* Return the entry, if any, in "u" that lives in "space".
238 * If "reserve" is set, then an entry is created if it does not exist yet.
239 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
240 * Note that when "reserve" is set, the function will never return
241 * isl_hash_table_entry_none.
243 * First look for the group of expressions with the same domain space,
244 * creating one if needed.
245 * Then look for the expression living in the specified space in that group.
247 static struct isl_hash_table_entry
*FN(UNION
,find_part_entry
)(
248 __isl_keep UNION
*u
, __isl_keep isl_space
*space
, int reserve
)
252 struct isl_hash_table_entry
*group_entry
;
253 S(UNION
,group
) *group
;
258 ctx
= FN(UNION
,get_ctx
)(u
);
259 hash
= isl_space_get_full_domain_hash(space
);
260 group_entry
= isl_hash_table_find(ctx
, &u
->table
, hash
,
261 &FN(UNION
,group_has_same_domain_space
), space
, reserve
);
262 if (!group_entry
|| group_entry
== isl_hash_table_entry_none
)
264 if (reserve
&& !group_entry
->data
) {
265 isl_space
*domain
= isl_space_domain(isl_space_copy(space
));
266 group
= FN(UNION
,group_alloc
)(domain
, 1);
267 group_entry
->data
= group
;
269 group
= group_entry
->data
;
271 group
= FN(UNION
,group_cow
)(group
);
275 hash
= isl_space_get_full_hash(space
);
276 return isl_hash_table_find(ctx
, &group
->part_table
, hash
,
277 &FN(UNION
,has_space
), space
, reserve
);
280 /* Remove "part_entry" from the hash table of "u".
282 * First look the group_entry in "u" holding the group that
283 * contains "part_entry". Remove "part_entry" from that group.
284 * If the group becomes empty, then also remove the group_entry from "u".
286 static __isl_give UNION
*FN(UNION
,remove_part_entry
)(__isl_take UNION
*u
,
287 struct isl_hash_table_entry
*part_entry
)
293 struct isl_hash_table_entry
*group_entry
;
294 S(UNION
,group
) *group
;
296 if (!u
|| !part_entry
)
297 return FN(UNION
,free
)(u
);
299 part
= part_entry
->data
;
300 ctx
= FN(UNION
,get_ctx
)(u
);
301 space
= FN(PART
,peek_space
)(part
);
302 hash
= isl_space_get_full_domain_hash(space
);
303 group_entry
= isl_hash_table_find(ctx
, &u
->table
, hash
,
304 &FN(UNION
,group_has_same_domain_space
), space
, 0);
306 return FN(UNION
,free
)(u
);
307 if (group_entry
== isl_hash_table_entry_none
)
308 isl_die(ctx
, isl_error_internal
, "missing group",
309 return FN(UNION
,free
)(u
));
310 group
= group_entry
->data
;
311 isl_hash_table_remove(ctx
, &group
->part_table
, part_entry
);
314 if (group
->part_table
.n
!= 0)
317 isl_hash_table_remove(ctx
, &u
->table
, group_entry
);
318 FN(UNION
,group_free
)(group
);
323 /* Are the domains of "part1" and "part2" disjoint?
325 static isl_bool
FN(UNION
,disjoint_domain
)(__isl_keep PART
*part1
,
326 __isl_keep PART
*part2
)
328 isl_set
*dom1
, *dom2
;
331 if (!part1
|| !part2
)
332 return isl_bool_error
;
333 dom1
= FN(PART
,domain
)(FN(PART
,copy
)(part1
));
334 dom2
= FN(PART
,domain
)(FN(PART
,copy
)(part2
));
335 disjoint
= isl_set_is_disjoint(dom1
, dom2
);
342 /* Check that the expression at *entry has a domain that is disjoint
343 * from that of "part", unless they also have the same target space.
345 static isl_stat
FN(UNION
,check_disjoint_domain_entry
)(void **entry
, void *user
)
348 PART
*other
= *entry
;
352 equal
= isl_space_is_equal(part
->dim
, other
->dim
);
354 return isl_stat_error
;
358 disjoint
= FN(UNION
,disjoint_domain
)(part
, other
);
360 return isl_stat_error
;
362 isl_die(FN(PART
,get_ctx
)(part
), isl_error_invalid
,
363 "overlapping domain with other part",
364 return isl_stat_error
);
368 /* Check that the domain of "part" is disjoint from the domain of the entries
369 * in "u" that are defined on the same domain space, but have a different
371 * If there is no group of expressions in "u" with the same domain space,
372 * then everything is fine. Otherwise, check the individual expressions
375 static isl_stat
FN(UNION
,check_disjoint_domain_other
)(__isl_keep UNION
*u
,
376 __isl_keep PART
*part
)
381 struct isl_hash_table_entry
*group_entry
;
382 S(UNION
,group
) *group
;
385 return isl_stat_error
;
386 ctx
= FN(UNION
,get_ctx
)(u
);
387 space
= FN(PART
,peek_space
)(part
);
388 hash
= isl_space_get_full_domain_hash(space
);
389 group_entry
= isl_hash_table_find(ctx
, &u
->table
, hash
,
390 &FN(UNION
,group_has_same_domain_space
), space
, 0);
392 return isl_stat_error
;
393 if (group_entry
== isl_hash_table_entry_none
)
395 group
= group_entry
->data
;
396 return isl_hash_table_foreach(ctx
, &group
->part_table
,
397 &FN(UNION
,check_disjoint_domain_entry
), part
);
400 /* Check that the domain of "part1" is disjoint from the domain of "part2".
401 * This check is performed before "part2" is added to a UNION to ensure
402 * that the UNION expression remains a function.
404 static isl_stat
FN(UNION
,check_disjoint_domain
)(__isl_keep PART
*part1
,
405 __isl_keep PART
*part2
)
409 disjoint
= FN(UNION
,disjoint_domain
)(part1
, part2
);
411 return isl_stat_error
;
413 isl_die(FN(PART
,get_ctx
)(part1
), isl_error_invalid
,
414 "domain of additional part should be disjoint",
415 return isl_stat_error
);
419 /* Internal data structure for isl_union_*_foreach_inplace.
420 * "fn" is the function that needs to be called on each entry.
422 S(UNION
,foreach_inplace_data
)
424 isl_stat (*fn
)(void **entry
, void *user
);
428 /* isl_union_*_foreach_group callback for calling data->fn on
429 * each part entry in the group.
431 static isl_stat
FN(UNION
,group_call_inplace
)(__isl_keep
S(UNION
,group
) *group
,
435 S(UNION
,foreach_inplace_data
) *data
;
438 return isl_stat_error
;
440 data
= (S(UNION
,foreach_inplace_data
) *) user
;
441 ctx
= isl_space_get_ctx(group
->domain_space
);
442 return isl_hash_table_foreach(ctx
, &group
->part_table
,
443 data
->fn
, data
->user
);
446 /* Call "fn" on each part entry of "u".
448 static isl_stat
FN(UNION
,foreach_inplace
)(__isl_keep UNION
*u
,
449 isl_stat (*fn
)(void **part
, void *user
), void *user
)
451 S(UNION
,foreach_inplace_data
) data
= { fn
, user
};
453 return FN(UNION
,foreach_group
)(u
, &FN(UNION
,group_call_inplace
), &data
);
456 static isl_stat
FN(UNION
,free_u_entry
)(void **entry
, void *user
)
458 S(UNION
,group
) *group
= *entry
;
459 FN(UNION
,group_free
)(group
);
463 /* Does "u" have an obviously empty definition domain?
465 isl_bool
FN(UNION
,plain_is_empty
)(__isl_take UNION
*u
)
468 return isl_bool_error
;
469 return isl_bool_ok(u
->table
.n
== 0);
472 /* Set "single" to true if this group of expressions
473 * contains an expression living in exactly one space.
475 static isl_stat
FN(UNION
,group_single_space
)(__isl_keep
S(UNION
,group
) *group
,
478 isl_bool
*single
= user
;
481 return isl_stat_error
;
482 *single
= isl_bool_ok(group
->part_table
.n
== 1);
486 /* Can this union expression be converted to a single base expression?
487 * That is, does it contain a base expression in exactly one space?
488 * In particular, is only one domain space involved and
489 * is only a single expression associated to that domain?
491 isl_bool
FN(FN(UNION
,isa
),BASE
)(__isl_take UNION
*u
)
496 return isl_bool_error
;
498 return isl_bool_false
;
499 if (FN(UNION
,foreach_group
)(u
,
500 &FN(UNION
,group_single_space
), &single
) < 0)
501 return isl_bool_error
;
505 /* Callback for isl_union_*_foreach_inplace call
506 * on a union expression with a single base expression.
507 * Store that base expression in "user".
508 * This callback should only be called once
509 * for any given isl_union_*_foreach_inplace call.
511 static isl_stat
FN(UNION
,extract_part
)(void **entry
, void *user
)
513 PART
**part_p
= user
;
517 isl_die(FN(PART
,get_ctx
)(part
), isl_error_internal
,
518 "more than one part", return isl_stat_error
);
519 *part_p
= FN(PART
,copy
)(part
);
521 return isl_stat_error
;
525 /* Convert the union expression to its single base expression.
527 __isl_give PART
*FN(FN(UNION
,as
),BASE
)(__isl_take UNION
*u
)
529 isl_bool has_single_space
;
532 has_single_space
= FN(FN(UNION
,isa
),BASE
)(u
);
533 if (has_single_space
< 0)
535 if (!has_single_space
)
536 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
537 "expecting elements in exactly one space",
539 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,extract_part
), &part
) < 0)
540 part
= FN(PART
,free
)(part
);
548 #include <isl_union_templ.c>