extract out isl_union_eval.c
[isl.git] / isl_union_templ.c
blob9b1d5179bf9f7762664876d1225d129f4130950b
1 /*
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,
9 * 91893 Orsay, France
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.
20 struct UNION {
21 int ref;
22 #ifdef HAS_TYPE
23 enum isl_fold type;
24 #endif
25 isl_space *space;
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)
39 if (!u)
40 return NULL;
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)
49 if (!u)
50 return 0;
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
60 * in "u".
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,
64 const char *name)
66 if (!u)
67 return -1;
68 return isl_space_find_dim_by_name(u->space, type, name);
71 #ifdef HAS_TYPE
72 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
73 enum isl_fold type, int size)
74 #else
75 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
76 #endif
78 UNION *u;
80 dim = isl_space_params(dim);
81 if (!dim)
82 return NULL;
84 u = isl_calloc_type(dim->ctx, UNION);
85 if (!u)
86 goto error;
88 u->ref = 1;
89 #ifdef HAS_TYPE
90 u->type = type;
91 #endif
92 u->space = dim;
93 if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
94 return FN(UNION,free)(u);
96 return u;
97 error:
98 isl_space_free(dim);
99 return NULL;
102 #ifdef HAS_TYPE
103 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
105 return FN(UNION,alloc)(dim, type, 16);
107 #else
108 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
110 return FN(UNION,alloc)(dim, 16);
112 #endif
114 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
116 if (!u)
117 return NULL;
119 u->ref++;
120 return 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);
133 void *user;
136 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
138 PART *part = *entry;
139 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
141 return data->fn(FN(PART,copy)(part), data->user);
144 isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
145 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
147 S(UNION,foreach_data) data = { fn, user };
149 if (!u)
150 return isl_stat_error;
152 return isl_hash_table_foreach(u->space->ctx, &u->table,
153 &FN(UNION,call_on_copy), &data);
156 /* Is the domain space of "entry" equal to the domain of "space"?
158 static int FN(UNION,has_same_domain_space)(const void *entry, const void *val)
160 PART *part = (PART *)entry;
161 isl_space *space = (isl_space *) val;
163 if (isl_space_is_set(space))
164 return isl_space_is_set(part->dim);
166 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
167 space, isl_dim_in);
170 /* Return the entry, if any, in "u" that lives in "space".
171 * If "reserve" is set, then an entry is created if it does not exist yet.
172 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
173 * Note that when "reserve" is set, the function will never return
174 * isl_hash_table_entry_none.
176 * First look for the entry (if any) with the same domain space.
177 * If it exists, then check if the range space also matches.
179 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
180 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
182 isl_ctx *ctx;
183 uint32_t hash;
184 struct isl_hash_table_entry *entry;
185 isl_bool equal;
186 PART *part;
188 if (!u || !space)
189 return NULL;
191 ctx = FN(UNION,get_ctx)(u);
192 hash = isl_space_get_domain_hash(space);
193 entry = isl_hash_table_find(ctx, &u->table, hash,
194 &FN(UNION,has_same_domain_space), space, reserve);
195 if (!entry)
196 return reserve ? NULL : isl_hash_table_entry_none;
197 if (reserve && !entry->data)
198 return entry;
199 part = entry->data;
200 equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
201 space, isl_dim_out);
202 if (equal < 0)
203 return NULL;
204 if (equal)
205 return entry;
206 if (!reserve)
207 return isl_hash_table_entry_none;
208 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
209 "union expression can only contain a single "
210 "expression over a given domain", return NULL);
213 /* Extract the element of "u" living in "space" (ignoring parameters).
215 * Return the ZERO element if "u" does not contain any element
216 * living in "space".
218 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
219 __isl_take isl_space *space)
221 struct isl_hash_table_entry *entry;
223 if (!u || !space)
224 goto error;
225 if (!isl_space_match(u->space, isl_dim_param, space, isl_dim_param)) {
226 space = isl_space_drop_dims(space, isl_dim_param,
227 0, isl_space_dim(space, isl_dim_param));
228 space = isl_space_align_params(space,
229 FN(UNION,get_space)(u));
230 if (!space)
231 goto error;
234 entry = FN(UNION,find_part_entry)(u, space, 0);
235 if (!entry)
236 goto error;
237 if (entry == isl_hash_table_entry_none)
238 #ifdef HAS_TYPE
239 return FN(PART,ZERO)(space, u->type);
240 #else
241 return FN(PART,ZERO)(space);
242 #endif
243 isl_space_free(space);
244 return FN(PART,copy)(entry->data);
245 error:
246 isl_space_free(space);
247 return NULL;
250 /* Add "part" to "u".
251 * If "disjoint" is set, then "u" is not allowed to already have
252 * a part that is defined on the same space as "part".
253 * Otherwise, compute the union sum of "part" and the part in "u"
254 * defined on the same space.
256 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
257 __isl_take PART *part, int disjoint)
259 int empty;
260 struct isl_hash_table_entry *entry;
262 if (!part)
263 goto error;
265 empty = FN(PART,IS_ZERO)(part);
266 if (empty < 0)
267 goto error;
268 if (empty) {
269 FN(PART,free)(part);
270 return u;
273 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
274 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
276 u = FN(UNION,cow)(u);
278 if (!u)
279 goto error;
281 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
282 if (!entry)
283 goto error;
285 if (!entry->data)
286 entry->data = part;
287 else {
288 if (disjoint)
289 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
290 "additional part should live on separate "
291 "space", goto error);
292 entry->data = FN(PART,union_add_)(entry->data,
293 FN(PART,copy)(part));
294 if (!entry->data)
295 goto error;
296 empty = FN(PART,IS_ZERO)(part);
297 if (empty < 0)
298 goto error;
299 if (empty) {
300 FN(PART,free)(entry->data);
301 isl_hash_table_remove(u->space->ctx, &u->table, entry);
303 FN(PART,free)(part);
306 return u;
307 error:
308 FN(PART,free)(part);
309 FN(UNION,free)(u);
310 return NULL;
313 /* Add "part" to "u", where "u" is assumed not to already have
314 * a part that is defined on the same space as "part".
316 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
317 __isl_take PART *part)
319 return FN(UNION,add_part_generic)(u, part, 1);
322 static isl_stat FN(UNION,add_part)(__isl_take PART *part, void *user)
324 UNION **u = (UNION **)user;
326 *u = FN(FN(UNION,add),PARTS)(*u, part);
328 return isl_stat_ok;
331 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
333 UNION *dup;
335 if (!u)
336 return NULL;
338 #ifdef HAS_TYPE
339 dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type);
340 #else
341 dup = FN(UNION,ZERO)(isl_space_copy(u->space));
342 #endif
343 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,add_part), &dup) < 0)
344 goto error;
345 return dup;
346 error:
347 FN(UNION,free)(dup);
348 return NULL;
351 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
353 if (!u)
354 return NULL;
356 if (u->ref == 1)
357 return u;
358 u->ref--;
359 return FN(UNION,dup)(u);
362 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
364 PART *part = *entry;
365 FN(PART,free)(part);
366 return isl_stat_ok;
369 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
371 if (!u)
372 return NULL;
374 if (--u->ref > 0)
375 return NULL;
377 isl_hash_table_foreach(u->space->ctx, &u->table,
378 &FN(UNION,free_u_entry), NULL);
379 isl_hash_table_clear(&u->table);
380 isl_space_free(u->space);
381 free(u);
382 return NULL;
385 S(UNION,align) {
386 isl_reordering *exp;
387 UNION *res;
390 static isl_stat FN(UNION,align_entry)(__isl_take PART *part, void *user)
392 isl_reordering *exp;
393 S(UNION,align) *data = user;
395 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
396 FN(PART,get_domain_space)(part));
398 data->res = FN(FN(UNION,add),PARTS)(data->res,
399 FN(PART,realign_domain)(part, exp));
401 return isl_stat_ok;
404 /* Reorder the parameters of "u" according to the given reordering.
406 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
407 __isl_take isl_reordering *r)
409 S(UNION,align) data = { NULL, NULL };
411 if (!u || !r)
412 goto error;
414 #ifdef HAS_TYPE
415 data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->type, u->table.n);
416 #else
417 data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->table.n);
418 #endif
419 data.exp = r;
420 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,align_entry), &data) < 0)
421 data.res = FN(UNION,free)(data.res);
423 isl_reordering_free(data.exp);
424 FN(UNION,free)(u);
425 return data.res;
426 error:
427 FN(UNION,free)(u);
428 isl_reordering_free(r);
429 return NULL;
432 /* Align the parameters of "u" to those of "model".
434 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
435 __isl_take isl_space *model)
437 isl_reordering *r;
439 if (!u || !model)
440 goto error;
442 if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
443 isl_space_free(model);
444 return u;
447 model = isl_space_params(model);
448 r = isl_parameter_alignment_reordering(u->space, model);
449 isl_space_free(model);
451 return FN(UNION,realign_domain)(u, r);
452 error:
453 isl_space_free(model);
454 FN(UNION,free)(u);
455 return NULL;
458 /* Add "part" to *u, taking the union sum if "u" already has
459 * a part defined on the same space as "part".
461 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
463 UNION **u = (UNION **)user;
465 *u = FN(UNION,add_part_generic)(*u, part, 0);
467 return isl_stat_ok;
470 /* Compute the sum of "u1" and "u2" on the union of their domains,
471 * with the actual sum on the shared domain and
472 * the defined expression on the symmetric difference of the domains.
474 * This is an internal function that is exposed under different
475 * names depending on whether the base expressions have a zero default
476 * value.
477 * If they do, then this function is called "add".
478 * Otherwise, it is called "union_add".
480 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
481 __isl_take UNION *u2)
483 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
484 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
486 u1 = FN(UNION,cow)(u1);
488 if (!u1 || !u2)
489 goto error;
491 if (FN(FN(UNION,foreach),PARTS)(u2, &FN(UNION,union_add_part), &u1) < 0)
492 goto error;
494 FN(UNION,free)(u2);
496 return u1;
497 error:
498 FN(UNION,free)(u1);
499 FN(UNION,free)(u2);
500 return NULL;
503 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
505 isl_space *dim;
506 UNION *u;
508 if (!part)
509 return NULL;
511 dim = FN(PART,get_space)(part);
512 dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
513 dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
514 #ifdef HAS_TYPE
515 u = FN(UNION,ZERO)(dim, part->type);
516 #else
517 u = FN(UNION,ZERO)(dim);
518 #endif
519 u = FN(FN(UNION,add),PARTS)(u, part);
521 return u;
524 S(UNION,match_bin_data) {
525 UNION *u2;
526 UNION *res;
527 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
530 /* Check if data->u2 has an element living in the same space as *entry.
531 * If so, call data->fn on the two elements and add the result to
532 * data->res.
534 static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user)
536 S(UNION,match_bin_data) *data = user;
537 struct isl_hash_table_entry *entry2;
538 isl_space *space;
539 PART *part = *entry;
540 PART *part2;
542 space = FN(PART,get_space)(part);
543 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
544 isl_space_free(space);
545 if (!entry2)
546 return isl_stat_error;
547 if (entry2 == isl_hash_table_entry_none)
548 return isl_stat_ok;
550 part2 = entry2->data;
551 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
552 part2->dim, isl_dim_out))
553 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
554 "entries should have the same range space",
555 return isl_stat_error);
557 part = FN(PART, copy)(part);
558 part = data->fn(part, FN(PART, copy)(entry2->data));
560 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
561 if (!data->res)
562 return isl_stat_error;
564 return isl_stat_ok;
567 /* This function is currently only used from isl_polynomial.c
568 * and not from isl_fold.c.
570 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
571 __isl_take UNION *u2,
572 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
573 __attribute__ ((unused));
574 /* For each pair of elements in "u1" and "u2" living in the same space,
575 * call "fn" and collect the results.
577 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
578 __isl_take UNION *u2,
579 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
581 S(UNION,match_bin_data) data = { NULL, NULL, fn };
583 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
584 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
586 if (!u1 || !u2)
587 goto error;
589 data.u2 = u2;
590 #ifdef HAS_TYPE
591 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type,
592 u1->table.n);
593 #else
594 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n);
595 #endif
596 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
597 &FN(UNION,match_bin_entry), &data) < 0)
598 goto error;
600 FN(UNION,free)(u1);
601 FN(UNION,free)(u2);
602 return data.res;
603 error:
604 FN(UNION,free)(u1);
605 FN(UNION,free)(u2);
606 FN(UNION,free)(data.res);
607 return NULL;
610 /* Compute the sum of "u1" and "u2".
612 * If the base expressions have a default zero value, then the sum
613 * is computed on the union of the domains of "u1" and "u2".
614 * Otherwise, it is computed on their shared domains.
616 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
618 #if DEFAULT_IS_ZERO
619 return FN(UNION,union_add_)(u1, u2);
620 #else
621 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
622 #endif
625 #ifndef NO_SUB
626 /* Subtract "u2" from "u1" and return the result.
628 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
630 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
632 #endif
634 S(UNION,any_set_data) {
635 isl_set *set;
636 UNION *res;
637 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
640 static isl_stat FN(UNION,any_set_entry)(void **entry, void *user)
642 S(UNION,any_set_data) *data = user;
643 PW *pw = *entry;
645 pw = FN(PW,copy)(pw);
646 pw = data->fn(pw, isl_set_copy(data->set));
648 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
649 if (!data->res)
650 return isl_stat_error;
652 return isl_stat_ok;
655 /* Update each element of "u" by calling "fn" on the element and "set".
657 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
658 __isl_take isl_set *set,
659 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
661 S(UNION,any_set_data) data = { NULL, NULL, fn };
663 u = FN(UNION,align_params)(u, isl_set_get_space(set));
664 set = isl_set_align_params(set, FN(UNION,get_space)(u));
666 if (!u || !set)
667 goto error;
669 data.set = set;
670 #ifdef HAS_TYPE
671 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
672 u->table.n);
673 #else
674 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
675 #endif
676 if (isl_hash_table_foreach(u->space->ctx, &u->table,
677 &FN(UNION,any_set_entry), &data) < 0)
678 goto error;
680 FN(UNION,free)(u);
681 isl_set_free(set);
682 return data.res;
683 error:
684 FN(UNION,free)(u);
685 isl_set_free(set);
686 FN(UNION,free)(data.res);
687 return NULL;
690 /* Intersect the domain of "u" with the parameter domain "context".
692 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
693 __isl_take isl_set *set)
695 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
698 /* Compute the gist of the domain of "u" with respect to
699 * the parameter domain "context".
701 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
702 __isl_take isl_set *set)
704 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
707 S(UNION,match_domain_data) {
708 isl_union_set *uset;
709 UNION *res;
710 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
713 static int FN(UNION,set_has_dim)(const void *entry, const void *val)
715 isl_set *set = (isl_set *)entry;
716 isl_space *dim = (isl_space *)val;
718 return isl_space_is_equal(set->dim, dim);
721 /* Find the set in data->uset that lives in the same space as the domain
722 * of *entry, apply data->fn to *entry and this set (if any), and add
723 * the result to data->res.
725 static isl_stat FN(UNION,match_domain_entry)(void **entry, void *user)
727 S(UNION,match_domain_data) *data = user;
728 uint32_t hash;
729 struct isl_hash_table_entry *entry2;
730 PW *pw = *entry;
731 isl_space *space;
733 space = FN(PW,get_domain_space)(pw);
734 hash = isl_space_get_hash(space);
735 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
736 hash, &FN(UNION,set_has_dim), space, 0);
737 isl_space_free(space);
738 if (!entry2)
739 return isl_stat_ok;
741 pw = FN(PW,copy)(pw);
742 pw = data->fn(pw, isl_set_copy(entry2->data));
744 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
745 if (!data->res)
746 return isl_stat_error;
748 return isl_stat_ok;
751 /* Apply fn to each pair of PW in u and set in uset such that
752 * the set lives in the same space as the domain of PW
753 * and collect the results.
755 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
756 __isl_take isl_union_set *uset,
757 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
759 S(UNION,match_domain_data) data = { NULL, NULL, fn };
761 u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
762 uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
764 if (!u || !uset)
765 goto error;
767 data.uset = uset;
768 #ifdef HAS_TYPE
769 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
770 u->table.n);
771 #else
772 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
773 #endif
774 if (isl_hash_table_foreach(u->space->ctx, &u->table,
775 &FN(UNION,match_domain_entry), &data) < 0)
776 goto error;
778 FN(UNION,free)(u);
779 isl_union_set_free(uset);
780 return data.res;
781 error:
782 FN(UNION,free)(u);
783 isl_union_set_free(uset);
784 FN(UNION,free)(data.res);
785 return NULL;
788 /* Intersect the domain of "u" with "uset".
789 * If "uset" is a parameters domain, then intersect the parameter
790 * domain of "u" with this set.
792 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
793 __isl_take isl_union_set *uset)
795 if (isl_union_set_is_params(uset))
796 return FN(UNION,intersect_params)(u,
797 isl_set_from_union_set(uset));
798 return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
801 /* Internal data structure for isl_union_*_subtract_domain.
802 * uset is the set that needs to be removed from the domain.
803 * res collects the results.
805 S(UNION,subtract_domain_data) {
806 isl_union_set *uset;
807 UNION *res;
810 /* Take the set (which may be empty) in data->uset that lives
811 * in the same space as the domain of "pw", subtract it from the domain
812 * of "pw" and add the result to data->res.
814 static isl_stat FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user)
816 S(UNION,subtract_domain_data) *data = user;
817 isl_space *space;
818 isl_set *set;
820 space = FN(PW,get_domain_space)(pw);
821 set = isl_union_set_extract_set(data->uset, space);
822 pw = FN(PW,subtract_domain)(pw, set);
823 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
825 return isl_stat_ok;
828 /* Subtract "uset' from the domain of "u".
830 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
831 __isl_take isl_union_set *uset)
833 S(UNION,subtract_domain_data) data;
835 if (!u || !uset)
836 goto error;
838 data.uset = uset;
839 #ifdef HAS_TYPE
840 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
841 u->table.n);
842 #else
843 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
844 #endif
845 if (FN(FN(UNION,foreach),PARTS)(u,
846 &FN(UNION,subtract_domain_entry), &data) < 0)
847 data.res = FN(UNION,free)(data.res);
849 FN(UNION,free)(u);
850 isl_union_set_free(uset);
851 return data.res;
852 error:
853 FN(UNION,free)(u);
854 isl_union_set_free(uset);
855 return NULL;
858 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
859 __isl_take isl_union_set *uset)
861 if (isl_union_set_is_params(uset))
862 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
863 return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
866 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
867 * Since the UNION may have several references, the entry is only
868 * replaced if the coalescing is successful.
870 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
872 PART **part_p = (PART **) entry;
873 PART *part;
875 part = FN(PART,copy)(*part_p);
876 part = FN(PW,coalesce)(part);
877 if (!part)
878 return isl_stat_error;
879 FN(PART,free)(*part_p);
880 *part_p = part;
882 return isl_stat_ok;
885 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
887 if (!u)
888 return NULL;
890 if (isl_hash_table_foreach(u->space->ctx, &u->table,
891 &FN(UNION,coalesce_entry), NULL) < 0)
892 goto error;
894 return u;
895 error:
896 FN(UNION,free)(u);
897 return NULL;
900 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
902 isl_union_set **uset = (isl_union_set **)user;
904 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
906 return isl_stat_ok;
909 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
911 isl_union_set *uset;
913 uset = isl_union_set_empty(FN(UNION,get_space)(u));
914 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,domain_entry), &uset) < 0)
915 goto error;
917 FN(UNION,free)(u);
919 return uset;
920 error:
921 isl_union_set_free(uset);
922 FN(UNION,free)(u);
923 return NULL;
926 static isl_stat FN(UNION,mul_isl_int_entry)(void **entry, void *user)
928 PW **pw = (PW **)entry;
929 isl_int *v = user;
931 *pw = FN(PW,mul_isl_int)(*pw, *v);
932 if (!*pw)
933 return isl_stat_error;
935 return isl_stat_ok;
938 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
940 if (isl_int_is_one(v))
941 return u;
943 if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
944 UNION *zero;
945 isl_space *dim = FN(UNION,get_space)(u);
946 #ifdef HAS_TYPE
947 zero = FN(UNION,ZERO)(dim, u->type);
948 #else
949 zero = FN(UNION,ZERO)(dim);
950 #endif
951 FN(UNION,free)(u);
952 return zero;
955 u = FN(UNION,cow)(u);
956 if (!u)
957 return NULL;
959 #ifdef HAS_TYPE
960 if (isl_int_is_neg(v))
961 u->type = isl_fold_type_negate(u->type);
962 #endif
963 if (isl_hash_table_foreach(u->space->ctx, &u->table,
964 &FN(UNION,mul_isl_int_entry), &v) < 0)
965 goto error;
967 return u;
968 error:
969 FN(UNION,free)(u);
970 return NULL;
973 /* Multiply *entry by the isl_val "user".
975 * Return 0 on success and -1 on error.
977 static isl_stat FN(UNION,scale_val_entry)(void **entry, void *user)
979 PW **pw = (PW **)entry;
980 isl_val *v = user;
982 *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
983 if (!*pw)
984 return isl_stat_error;
986 return isl_stat_ok;
989 /* Multiply "u" by "v" and return the result.
991 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
992 __isl_take isl_val *v)
994 if (!u || !v)
995 goto error;
996 if (isl_val_is_one(v)) {
997 isl_val_free(v);
998 return u;
1001 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1002 UNION *zero;
1003 isl_space *space = FN(UNION,get_space)(u);
1004 #ifdef HAS_TYPE
1005 zero = FN(UNION,ZERO)(space, u->type);
1006 #else
1007 zero = FN(UNION,ZERO)(space);
1008 #endif
1009 FN(UNION,free)(u);
1010 isl_val_free(v);
1011 return zero;
1014 if (!isl_val_is_rat(v))
1015 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1016 "expecting rational factor", goto error);
1018 u = FN(UNION,cow)(u);
1019 if (!u)
1020 return NULL;
1022 #ifdef HAS_TYPE
1023 if (isl_val_is_neg(v))
1024 u->type = isl_fold_type_negate(u->type);
1025 #endif
1026 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1027 &FN(UNION,scale_val_entry), v) < 0)
1028 goto error;
1030 isl_val_free(v);
1031 return u;
1032 error:
1033 isl_val_free(v);
1034 FN(UNION,free)(u);
1035 return NULL;
1038 /* Divide *entry by the isl_val "user".
1040 * Return 0 on success and -1 on error.
1042 static isl_stat FN(UNION,scale_down_val_entry)(void **entry, void *user)
1044 PW **pw = (PW **)entry;
1045 isl_val *v = user;
1047 *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v));
1048 if (!*pw)
1049 return isl_stat_error;
1051 return isl_stat_ok;
1054 /* Divide "u" by "v" and return the result.
1056 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1057 __isl_take isl_val *v)
1059 if (!u || !v)
1060 goto error;
1061 if (isl_val_is_one(v)) {
1062 isl_val_free(v);
1063 return u;
1066 if (!isl_val_is_rat(v))
1067 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1068 "expecting rational factor", goto error);
1069 if (isl_val_is_zero(v))
1070 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1071 "cannot scale down by zero", goto error);
1073 u = FN(UNION,cow)(u);
1074 if (!u)
1075 return NULL;
1077 #ifdef HAS_TYPE
1078 if (isl_val_is_neg(v))
1079 u->type = isl_fold_type_negate(u->type);
1080 #endif
1081 if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table,
1082 &FN(UNION,scale_down_val_entry), v) < 0)
1083 goto error;
1085 isl_val_free(v);
1086 return u;
1087 error:
1088 isl_val_free(v);
1089 FN(UNION,free)(u);
1090 return NULL;
1093 S(UNION,plain_is_equal_data)
1095 UNION *u2;
1096 isl_bool is_equal;
1099 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
1101 S(UNION,plain_is_equal_data) *data = user;
1102 struct isl_hash_table_entry *entry2;
1103 PW *pw = *entry;
1105 entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1106 if (!entry2 || entry2 == isl_hash_table_entry_none) {
1107 if (!entry2)
1108 data->is_equal = isl_bool_error;
1109 else
1110 data->is_equal = isl_bool_false;
1111 return isl_stat_error;
1114 data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
1115 if (data->is_equal < 0 || !data->is_equal)
1116 return isl_stat_error;
1118 return isl_stat_ok;
1121 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1123 S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
1125 if (!u1 || !u2)
1126 return isl_bool_error;
1127 if (u1 == u2)
1128 return isl_bool_true;
1129 if (u1->table.n != u2->table.n)
1130 return isl_bool_false;
1132 u1 = FN(UNION,copy)(u1);
1133 u2 = FN(UNION,copy)(u2);
1134 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1135 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1136 if (!u1 || !u2)
1137 goto error;
1139 data.u2 = u2;
1140 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
1141 &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1142 data.is_equal)
1143 goto error;
1145 FN(UNION,free)(u1);
1146 FN(UNION,free)(u2);
1148 return data.is_equal;
1149 error:
1150 FN(UNION,free)(u1);
1151 FN(UNION,free)(u2);
1152 return isl_bool_error;
1155 #ifndef NO_NEG
1156 /* Replace *entry by its opposite.
1158 * Return 0 on success and -1 on error.
1160 static isl_stat FN(UNION,neg_entry)(void **entry, void *user)
1162 PW **pw = (PW **) entry;
1164 *pw = FN(PW,neg)(*pw);
1166 return *pw ? isl_stat_ok : isl_stat_error;
1169 /* Return the opposite of "u".
1171 __isl_give UNION *FN(UNION,neg)(__isl_take UNION *u)
1173 u = FN(UNION,cow)(u);
1174 if (!u)
1175 return NULL;
1177 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1178 &FN(UNION,neg_entry), NULL) < 0)
1179 return FN(UNION,free)(u);
1181 return u;
1183 #endif
1185 /* Internal data structure for isl_union_*_drop_dims.
1186 * type, first and n are passed to isl_*_drop_dims.
1187 * res collects the results.
1189 S(UNION,drop_dims_data) {
1190 enum isl_dim_type type;
1191 unsigned first;
1192 unsigned n;
1194 UNION *res;
1197 /* Drop the parameters specified by "data" from "part" and
1198 * add the results to data->res.
1200 static isl_stat FN(UNION,drop_dims_entry)(__isl_take PART *part, void *user)
1202 S(UNION,drop_dims_data) *data = user;
1204 part = FN(PART,drop_dims)(part, data->type, data->first, data->n);
1205 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
1206 if (!data->res)
1207 return isl_stat_error;
1209 return isl_stat_ok;
1212 /* Drop the specified parameters from "u".
1213 * That is, type is required to be isl_dim_param.
1215 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1216 enum isl_dim_type type, unsigned first, unsigned n)
1218 isl_space *space;
1219 S(UNION,drop_dims_data) data = { type, first, n };
1221 if (!u)
1222 return NULL;
1224 if (type != isl_dim_param)
1225 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1226 "can only project out parameters",
1227 return FN(UNION,free)(u));
1229 space = FN(UNION,get_space)(u);
1230 space = isl_space_drop_dims(space, type, first, n);
1231 #ifdef HAS_TYPE
1232 data.res = FN(UNION,alloc)(space, u->type, u->table.n);
1233 #else
1234 data.res = FN(UNION,alloc)(space, u->table.n);
1235 #endif
1236 if (FN(FN(UNION,foreach),PARTS)(u,
1237 &FN(UNION,drop_dims_entry), &data) < 0)
1238 data.res = FN(UNION,free)(data.res);
1240 FN(UNION,free)(u);
1242 return data.res;
1245 /* Internal data structure for isl_union_*_set_dim_name.
1246 * pos is the position of the parameter that needs to be renamed.
1247 * s is the new name.
1248 * res collects the results.
1250 S(UNION,set_dim_name_data) {
1251 unsigned pos;
1252 const char *s;
1254 UNION *res;
1257 /* Change the name of the parameter at position data->pos of "part" to data->s
1258 * and add the result to data->res.
1260 static isl_stat FN(UNION,set_dim_name_entry)(__isl_take PART *part, void *user)
1262 S(UNION,set_dim_name_data) *data = user;
1264 part = FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1265 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
1266 if (!data->res)
1267 return isl_stat_error;
1269 return isl_stat_ok;
1272 /* Change the name of the parameter at position "pos" to "s".
1273 * That is, type is required to be isl_dim_param.
1275 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1276 enum isl_dim_type type, unsigned pos, const char *s)
1278 S(UNION,set_dim_name_data) data = { pos, s };
1279 isl_space *space;
1281 if (!u)
1282 return NULL;
1284 if (type != isl_dim_param)
1285 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1286 "can only set parameter names",
1287 return FN(UNION,free)(u));
1289 space = FN(UNION,get_space)(u);
1290 space = isl_space_set_dim_name(space, type, pos, s);
1291 #ifdef HAS_TYPE
1292 data.res = FN(UNION,alloc)(space, u->type, u->table.n);
1293 #else
1294 data.res = FN(UNION,alloc)(space, u->table.n);
1295 #endif
1297 if (FN(FN(UNION,foreach),PARTS)(u,
1298 &FN(UNION,set_dim_name_entry), &data) < 0)
1299 data.res = FN(UNION,free)(data.res);
1301 FN(UNION,free)(u);
1303 return data.res;
1306 /* Reset the user pointer on all identifiers of parameters and tuples
1307 * of the space of "part" and add the result to *res.
1309 static isl_stat FN(UNION,reset_user_entry)(__isl_take PART *part, void *user)
1311 UNION **res = user;
1313 part = FN(PART,reset_user)(part);
1314 *res = FN(FN(UNION,add),PARTS)(*res, part);
1315 if (!*res)
1316 return isl_stat_error;
1318 return isl_stat_ok;
1321 /* Reset the user pointer on all identifiers of parameters and tuples
1322 * of the spaces of "u".
1324 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1326 isl_space *space;
1327 UNION *res;
1329 if (!u)
1330 return NULL;
1332 space = FN(UNION,get_space)(u);
1333 space = isl_space_reset_user(space);
1334 #ifdef HAS_TYPE
1335 res = FN(UNION,alloc)(space, u->type, u->table.n);
1336 #else
1337 res = FN(UNION,alloc)(space, u->table.n);
1338 #endif
1339 if (FN(FN(UNION,foreach),PARTS)(u,
1340 &FN(UNION,reset_user_entry), &res) < 0)
1341 res = FN(UNION,free)(res);
1343 FN(UNION,free)(u);
1345 return res;