isl_union_*_scale_val: use isl_union_*_transform_inplace
[isl.git] / isl_union_templ.c
blob7901c7cf04b78e1502613829bf4030f4d98e45f7
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 /* Remove "part_entry" from the hash table of "u".
215 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
216 struct isl_hash_table_entry *part_entry)
218 isl_ctx *ctx;
220 if (!u || !part_entry)
221 return FN(UNION,free)(u);
223 ctx = FN(UNION,get_ctx)(u);
224 isl_hash_table_remove(ctx, &u->table, part_entry);
225 FN(PART,free)(part_entry->data);
227 return u;
230 /* Extract the element of "u" living in "space" (ignoring parameters).
232 * Return the ZERO element if "u" does not contain any element
233 * living in "space".
235 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
236 __isl_take isl_space *space)
238 struct isl_hash_table_entry *entry;
240 if (!u || !space)
241 goto error;
242 if (!isl_space_match(u->space, isl_dim_param, space, isl_dim_param)) {
243 space = isl_space_drop_dims(space, isl_dim_param,
244 0, isl_space_dim(space, isl_dim_param));
245 space = isl_space_align_params(space,
246 FN(UNION,get_space)(u));
247 if (!space)
248 goto error;
251 entry = FN(UNION,find_part_entry)(u, space, 0);
252 if (!entry)
253 goto error;
254 if (entry == isl_hash_table_entry_none)
255 #ifdef HAS_TYPE
256 return FN(PART,ZERO)(space, u->type);
257 #else
258 return FN(PART,ZERO)(space);
259 #endif
260 isl_space_free(space);
261 return FN(PART,copy)(entry->data);
262 error:
263 isl_space_free(space);
264 return NULL;
267 /* Add "part" to "u".
268 * If "disjoint" is set, then "u" is not allowed to already have
269 * a part that is defined on the same space as "part".
270 * Otherwise, compute the union sum of "part" and the part in "u"
271 * defined on the same space.
273 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
274 __isl_take PART *part, int disjoint)
276 int empty;
277 struct isl_hash_table_entry *entry;
279 if (!part)
280 goto error;
282 empty = FN(PART,IS_ZERO)(part);
283 if (empty < 0)
284 goto error;
285 if (empty) {
286 FN(PART,free)(part);
287 return u;
290 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
291 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
293 u = FN(UNION,cow)(u);
295 if (!u)
296 goto error;
298 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
299 if (!entry)
300 goto error;
302 if (!entry->data)
303 entry->data = part;
304 else {
305 if (disjoint)
306 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
307 "additional part should live on separate "
308 "space", goto error);
309 entry->data = FN(PART,union_add_)(entry->data,
310 FN(PART,copy)(part));
311 if (!entry->data)
312 goto error;
313 empty = FN(PART,IS_ZERO)(part);
314 if (empty < 0)
315 goto error;
316 if (empty)
317 u = FN(UNION,remove_part_entry)(u, entry);
318 FN(PART,free)(part);
321 return u;
322 error:
323 FN(PART,free)(part);
324 FN(UNION,free)(u);
325 return NULL;
328 /* Add "part" to "u", where "u" is assumed not to already have
329 * a part that is defined on the same space as "part".
331 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
332 __isl_take PART *part)
334 return FN(UNION,add_part_generic)(u, part, 1);
337 #ifdef HAS_TYPE
338 /* Allocate a UNION with the same type and the same size as "u" and
339 * with space "space".
341 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
342 __isl_take isl_space *space)
344 if (!u)
345 space = isl_space_free(space);
346 return FN(UNION,alloc)(space, u->type, u->table.n);
348 #else
349 /* Allocate a UNION with the same size as "u" and with space "space".
351 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
352 __isl_take isl_space *space)
354 if (!u)
355 space = isl_space_free(space);
356 return FN(UNION,alloc)(space, u->table.n);
358 #endif
360 /* Allocate a UNION with the same space, the same type (if any) and
361 * the same size as "u".
363 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
365 return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
368 /* Call "fn" on each part entry of "u".
370 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
371 isl_stat (*fn)(void **part, void *user), void *user)
373 isl_ctx *ctx;
375 if (!u)
376 return isl_stat_error;
377 ctx = FN(UNION,get_ctx)(u);
378 return isl_hash_table_foreach(ctx, &u->table, fn, user);
381 /* Does "u" have a single reference?
382 * That is, can we change "u" inplace?
384 static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
386 if (!u)
387 return isl_bool_error;
388 return u->ref == 1;
391 /* Internal data structure for isl_union_*_transform_space.
392 * "fn' is applied to each entry in the input.
393 * "res" collects the results.
395 S(UNION,transform_data)
397 __isl_give PART *(*fn)(__isl_take PART *part, void *user);
398 void *user;
400 UNION *res;
403 /* Apply data->fn to "part" and add the result to data->res.
405 static isl_stat FN(UNION,transform_entry)(__isl_take PART *part, void *user)
407 S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
409 part = data->fn(part, data->user);
410 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
411 if (!data->res)
412 return isl_stat_error;
414 return isl_stat_ok;
417 /* Return a UNION living in "space" that is obtained by applying "fn"
418 * to each of the entries in "u".
420 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
421 isl_space *space,
422 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
424 S(UNION,transform_data) data = { fn, user };
426 data.res = FN(UNION,alloc_same_size_on_space)(u, space);
427 if (FN(FN(UNION,foreach),PARTS)(u,
428 &FN(UNION,transform_entry), &data) < 0)
429 data.res = FN(UNION,free)(data.res);
430 FN(UNION,free)(u);
431 return data.res;
434 /* Return a UNION that lives in the same space as "u" and that is obtained
435 * by applying "fn" to each of the entries in "u".
437 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
438 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
440 return FN(UNION,transform_space)(u, FN(UNION,get_space)(u), fn, user);
443 /* Apply data->fn to *part and store the result back into *part.
445 static isl_stat FN(UNION,transform_inplace_entry)(void **part, void *user)
447 S(UNION,transform_data) *data = (S(UNION,transform_data) *) user;
449 *part = data->fn(*part, data->user);
450 if (!*part)
451 return isl_stat_error;
452 return isl_stat_ok;
455 /* Update "u" by applying "fn" to each entry.
456 * This operation is assumed not to change the number of entries nor
457 * the spaces of the entries.
459 * If there is only one reference to "u", then change "u" inplace.
460 * Otherwise, create a new UNION from "u" and discard the original.
462 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
463 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
465 isl_bool single_ref;
467 single_ref = FN(UNION,has_single_reference)(u);
468 if (single_ref < 0)
469 return FN(UNION,free)(u);
470 if (single_ref) {
471 S(UNION,transform_data) data = { fn, user };
472 if (FN(UNION,foreach_inplace)(u,
473 &FN(UNION,transform_inplace_entry), &data) < 0)
474 return FN(UNION,free)(u);
475 return u;
477 return FN(UNION,transform)(u, fn, user);
480 /* An isl_union_*_transform callback for use in isl_union_*_dup
481 * that simply returns "part".
483 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
485 return part;
488 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
490 u = FN(UNION,copy)(u);
491 return FN(UNION,transform)(u, &FN(UNION,copy_part), NULL);
494 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
496 if (!u)
497 return NULL;
499 if (u->ref == 1)
500 return u;
501 u->ref--;
502 return FN(UNION,dup)(u);
505 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
507 PART *part = *entry;
508 FN(PART,free)(part);
509 return isl_stat_ok;
512 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
514 if (!u)
515 return NULL;
517 if (--u->ref > 0)
518 return NULL;
520 isl_hash_table_foreach(u->space->ctx, &u->table,
521 &FN(UNION,free_u_entry), NULL);
522 isl_hash_table_clear(&u->table);
523 isl_space_free(u->space);
524 free(u);
525 return NULL;
528 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
530 isl_reordering *exp = user;
532 exp = isl_reordering_extend_space(isl_reordering_copy(exp),
533 FN(PART,get_domain_space)(part));
534 return FN(PART,realign_domain)(part, exp);
537 /* Reorder the parameters of "u" according to the given reordering.
539 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
540 __isl_take isl_reordering *r)
542 isl_space *space;
544 if (!u || !r)
545 goto error;
547 space = isl_space_copy(r->dim);
548 u = FN(UNION,transform_space)(u, space, &FN(UNION,align_entry), r);
549 isl_reordering_free(r);
550 return u;
551 error:
552 FN(UNION,free)(u);
553 isl_reordering_free(r);
554 return NULL;
557 /* Align the parameters of "u" to those of "model".
559 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
560 __isl_take isl_space *model)
562 isl_reordering *r;
564 if (!u || !model)
565 goto error;
567 if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
568 isl_space_free(model);
569 return u;
572 model = isl_space_params(model);
573 r = isl_parameter_alignment_reordering(u->space, model);
574 isl_space_free(model);
576 return FN(UNION,realign_domain)(u, r);
577 error:
578 isl_space_free(model);
579 FN(UNION,free)(u);
580 return NULL;
583 /* Add "part" to *u, taking the union sum if "u" already has
584 * a part defined on the same space as "part".
586 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
588 UNION **u = (UNION **)user;
590 *u = FN(UNION,add_part_generic)(*u, part, 0);
592 return isl_stat_ok;
595 /* Compute the sum of "u1" and "u2" on the union of their domains,
596 * with the actual sum on the shared domain and
597 * the defined expression on the symmetric difference of the domains.
599 * This is an internal function that is exposed under different
600 * names depending on whether the base expressions have a zero default
601 * value.
602 * If they do, then this function is called "add".
603 * Otherwise, it is called "union_add".
605 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
606 __isl_take UNION *u2)
608 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
609 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
611 u1 = FN(UNION,cow)(u1);
613 if (!u1 || !u2)
614 goto error;
616 if (FN(FN(UNION,foreach),PARTS)(u2, &FN(UNION,union_add_part), &u1) < 0)
617 goto error;
619 FN(UNION,free)(u2);
621 return u1;
622 error:
623 FN(UNION,free)(u1);
624 FN(UNION,free)(u2);
625 return NULL;
628 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
630 isl_space *dim;
631 UNION *u;
633 if (!part)
634 return NULL;
636 dim = FN(PART,get_space)(part);
637 dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
638 dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
639 #ifdef HAS_TYPE
640 u = FN(UNION,ZERO)(dim, part->type);
641 #else
642 u = FN(UNION,ZERO)(dim);
643 #endif
644 u = FN(FN(UNION,add),PARTS)(u, part);
646 return u;
649 S(UNION,match_bin_data) {
650 UNION *u2;
651 UNION *res;
652 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
655 /* Check if data->u2 has an element living in the same space as *entry.
656 * If so, call data->fn on the two elements and add the result to
657 * data->res.
659 static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user)
661 S(UNION,match_bin_data) *data = user;
662 struct isl_hash_table_entry *entry2;
663 isl_space *space;
664 PART *part = *entry;
665 PART *part2;
667 space = FN(PART,get_space)(part);
668 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
669 isl_space_free(space);
670 if (!entry2)
671 return isl_stat_error;
672 if (entry2 == isl_hash_table_entry_none)
673 return isl_stat_ok;
675 part2 = entry2->data;
676 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
677 part2->dim, isl_dim_out))
678 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
679 "entries should have the same range space",
680 return isl_stat_error);
682 part = FN(PART, copy)(part);
683 part = data->fn(part, FN(PART, copy)(entry2->data));
685 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
686 if (!data->res)
687 return isl_stat_error;
689 return isl_stat_ok;
692 /* This function is currently only used from isl_polynomial.c
693 * and not from isl_fold.c.
695 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
696 __isl_take UNION *u2,
697 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
698 __attribute__ ((unused));
699 /* For each pair of elements in "u1" and "u2" living in the same space,
700 * call "fn" and collect the results.
702 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
703 __isl_take UNION *u2,
704 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
706 S(UNION,match_bin_data) data = { NULL, NULL, fn };
708 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
709 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
711 if (!u1 || !u2)
712 goto error;
714 data.u2 = u2;
715 data.res = FN(UNION,alloc_same_size)(u1);
716 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
717 &FN(UNION,match_bin_entry), &data) < 0)
718 goto error;
720 FN(UNION,free)(u1);
721 FN(UNION,free)(u2);
722 return data.res;
723 error:
724 FN(UNION,free)(u1);
725 FN(UNION,free)(u2);
726 FN(UNION,free)(data.res);
727 return NULL;
730 /* Compute the sum of "u1" and "u2".
732 * If the base expressions have a default zero value, then the sum
733 * is computed on the union of the domains of "u1" and "u2".
734 * Otherwise, it is computed on their shared domains.
736 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
738 #if DEFAULT_IS_ZERO
739 return FN(UNION,union_add_)(u1, u2);
740 #else
741 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
742 #endif
745 #ifndef NO_SUB
746 /* Subtract "u2" from "u1" and return the result.
748 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
750 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
752 #endif
754 S(UNION,any_set_data) {
755 isl_set *set;
756 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
759 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
760 void *user)
762 S(UNION,any_set_data) *data = user;
764 return data->fn(part, isl_set_copy(data->set));
767 /* Update each element of "u" by calling "fn" on the element and "set".
769 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
770 __isl_take isl_set *set,
771 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
773 S(UNION,any_set_data) data = { NULL, fn };
775 u = FN(UNION,align_params)(u, isl_set_get_space(set));
776 set = isl_set_align_params(set, FN(UNION,get_space)(u));
778 if (!u || !set)
779 goto error;
781 data.set = set;
782 u = FN(UNION,transform)(u, &FN(UNION,any_set_entry), &data);
783 isl_set_free(set);
784 return u;
785 error:
786 FN(UNION,free)(u);
787 isl_set_free(set);
788 return NULL;
791 /* Intersect the domain of "u" with the parameter domain "context".
793 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
794 __isl_take isl_set *set)
796 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
799 /* Compute the gist of the domain of "u" with respect to
800 * the parameter domain "context".
802 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
803 __isl_take isl_set *set)
805 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
808 S(UNION,match_domain_data) {
809 isl_union_set *uset;
810 UNION *res;
811 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
814 static int FN(UNION,set_has_dim)(const void *entry, const void *val)
816 isl_set *set = (isl_set *)entry;
817 isl_space *dim = (isl_space *)val;
819 return isl_space_is_equal(set->dim, dim);
822 /* Find the set in data->uset that lives in the same space as the domain
823 * of *entry, apply data->fn to *entry and this set (if any), and add
824 * the result to data->res.
826 static isl_stat FN(UNION,match_domain_entry)(void **entry, void *user)
828 S(UNION,match_domain_data) *data = user;
829 uint32_t hash;
830 struct isl_hash_table_entry *entry2;
831 PW *pw = *entry;
832 isl_space *space;
834 space = FN(PW,get_domain_space)(pw);
835 hash = isl_space_get_hash(space);
836 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
837 hash, &FN(UNION,set_has_dim), space, 0);
838 isl_space_free(space);
839 if (!entry2)
840 return isl_stat_ok;
842 pw = FN(PW,copy)(pw);
843 pw = data->fn(pw, isl_set_copy(entry2->data));
845 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
846 if (!data->res)
847 return isl_stat_error;
849 return isl_stat_ok;
852 /* Apply fn to each pair of PW in u and set in uset such that
853 * the set lives in the same space as the domain of PW
854 * and collect the results.
856 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
857 __isl_take isl_union_set *uset,
858 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
860 S(UNION,match_domain_data) data = { NULL, NULL, fn };
862 u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
863 uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
865 if (!u || !uset)
866 goto error;
868 data.uset = uset;
869 data.res = FN(UNION,alloc_same_size)(u);
870 if (isl_hash_table_foreach(u->space->ctx, &u->table,
871 &FN(UNION,match_domain_entry), &data) < 0)
872 goto error;
874 FN(UNION,free)(u);
875 isl_union_set_free(uset);
876 return data.res;
877 error:
878 FN(UNION,free)(u);
879 isl_union_set_free(uset);
880 FN(UNION,free)(data.res);
881 return NULL;
884 /* Intersect the domain of "u" with "uset".
885 * If "uset" is a parameters domain, then intersect the parameter
886 * domain of "u" with this set.
888 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
889 __isl_take isl_union_set *uset)
891 if (isl_union_set_is_params(uset))
892 return FN(UNION,intersect_params)(u,
893 isl_set_from_union_set(uset));
894 return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
897 /* Take the set (which may be empty) in data->uset that lives
898 * in the same space as the domain of "pw", subtract it from the domain
899 * of "part" and return the result.
901 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
902 void *user)
904 isl_union_set *uset = user;
905 isl_space *space;
906 isl_set *set;
908 space = FN(PART,get_domain_space)(part);
909 set = isl_union_set_extract_set(uset, space);
910 return FN(PART,subtract_domain)(part, set);
913 /* Subtract "uset' from the domain of "u".
915 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
916 __isl_take isl_union_set *uset)
918 u = FN(UNION,transform)(u, &FN(UNION,subtract_domain_entry), uset);
919 isl_union_set_free(uset);
920 return u;
923 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
924 __isl_take isl_union_set *uset)
926 if (isl_union_set_is_params(uset))
927 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
928 return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
931 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
932 * Since the UNION may have several references, the entry is only
933 * replaced if the coalescing is successful.
935 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
937 PART **part_p = (PART **) entry;
938 PART *part;
940 part = FN(PART,copy)(*part_p);
941 part = FN(PW,coalesce)(part);
942 if (!part)
943 return isl_stat_error;
944 FN(PART,free)(*part_p);
945 *part_p = part;
947 return isl_stat_ok;
950 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
952 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
953 goto error;
955 return u;
956 error:
957 FN(UNION,free)(u);
958 return NULL;
961 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
963 isl_union_set **uset = (isl_union_set **)user;
965 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
967 return isl_stat_ok;
970 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
972 isl_union_set *uset;
974 uset = isl_union_set_empty(FN(UNION,get_space)(u));
975 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,domain_entry), &uset) < 0)
976 goto error;
978 FN(UNION,free)(u);
980 return uset;
981 error:
982 isl_union_set_free(uset);
983 FN(UNION,free)(u);
984 return NULL;
987 #ifdef HAS_TYPE
988 /* Negate the type of "u".
990 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
992 u = FN(UNION,cow)(u);
993 if (!u)
994 return NULL;
995 u->type = isl_fold_type_negate(u->type);
996 return u;
998 #else
999 /* Negate the type of "u".
1000 * Since "u" does not have a type, do nothing.
1002 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1004 return u;
1006 #endif
1008 static __isl_give PART *FN(UNION,mul_isl_int_entry)(__isl_take PART *part,
1009 void *user)
1011 isl_int *v = user;
1013 return FN(PW,mul_isl_int)(part, *v);
1016 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
1018 if (isl_int_is_one(v))
1019 return u;
1021 if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
1022 UNION *zero;
1023 isl_space *dim = FN(UNION,get_space)(u);
1024 #ifdef HAS_TYPE
1025 zero = FN(UNION,ZERO)(dim, u->type);
1026 #else
1027 zero = FN(UNION,ZERO)(dim);
1028 #endif
1029 FN(UNION,free)(u);
1030 return zero;
1033 u = FN(UNION,transform_inplace)(u, &FN(UNION,mul_isl_int_entry), &v);
1034 if (isl_int_is_neg(v))
1035 u = FN(UNION,negate_type)(u);
1037 return u;
1040 /* Multiply "part" by the isl_val "user" and return the result.
1042 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1043 void *user)
1045 isl_val *v = user;
1047 return FN(PART,scale_val)(part, isl_val_copy(v));
1050 /* Multiply "u" by "v" and return the result.
1052 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1053 __isl_take isl_val *v)
1055 if (!u || !v)
1056 goto error;
1057 if (isl_val_is_one(v)) {
1058 isl_val_free(v);
1059 return u;
1062 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1063 UNION *zero;
1064 isl_space *space = FN(UNION,get_space)(u);
1065 #ifdef HAS_TYPE
1066 zero = FN(UNION,ZERO)(space, u->type);
1067 #else
1068 zero = FN(UNION,ZERO)(space);
1069 #endif
1070 FN(UNION,free)(u);
1071 isl_val_free(v);
1072 return zero;
1075 if (!isl_val_is_rat(v))
1076 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1077 "expecting rational factor", goto error);
1079 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1080 if (isl_val_is_neg(v))
1081 u = FN(UNION,negate_type)(u);
1083 isl_val_free(v);
1084 return u;
1085 error:
1086 isl_val_free(v);
1087 FN(UNION,free)(u);
1088 return NULL;
1091 /* Divide *entry by the isl_val "user".
1093 * Return 0 on success and -1 on error.
1095 static isl_stat FN(UNION,scale_down_val_entry)(void **entry, void *user)
1097 PW **pw = (PW **)entry;
1098 isl_val *v = user;
1100 *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v));
1101 if (!*pw)
1102 return isl_stat_error;
1104 return isl_stat_ok;
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)
1112 if (!u || !v)
1113 goto error;
1114 if (isl_val_is_one(v)) {
1115 isl_val_free(v);
1116 return u;
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,cow)(u);
1127 if (isl_val_is_neg(v))
1128 u = FN(UNION,negate_type)(u);
1129 if (!u)
1130 return NULL;
1132 if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table,
1133 &FN(UNION,scale_down_val_entry), v) < 0)
1134 goto error;
1136 isl_val_free(v);
1137 return u;
1138 error:
1139 isl_val_free(v);
1140 FN(UNION,free)(u);
1141 return NULL;
1144 S(UNION,plain_is_equal_data)
1146 UNION *u2;
1147 isl_bool is_equal;
1150 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
1152 S(UNION,plain_is_equal_data) *data = user;
1153 struct isl_hash_table_entry *entry2;
1154 PW *pw = *entry;
1156 entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1157 if (!entry2 || entry2 == isl_hash_table_entry_none) {
1158 if (!entry2)
1159 data->is_equal = isl_bool_error;
1160 else
1161 data->is_equal = isl_bool_false;
1162 return isl_stat_error;
1165 data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
1166 if (data->is_equal < 0 || !data->is_equal)
1167 return isl_stat_error;
1169 return isl_stat_ok;
1172 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1174 S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
1176 if (!u1 || !u2)
1177 return isl_bool_error;
1178 if (u1 == u2)
1179 return isl_bool_true;
1180 if (u1->table.n != u2->table.n)
1181 return isl_bool_false;
1183 u1 = FN(UNION,copy)(u1);
1184 u2 = FN(UNION,copy)(u2);
1185 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1186 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1187 if (!u1 || !u2)
1188 goto error;
1190 data.u2 = u2;
1191 if (FN(UNION,foreach_inplace)(u1,
1192 &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1193 data.is_equal)
1194 goto error;
1196 FN(UNION,free)(u1);
1197 FN(UNION,free)(u2);
1199 return data.is_equal;
1200 error:
1201 FN(UNION,free)(u1);
1202 FN(UNION,free)(u2);
1203 return isl_bool_error;
1206 /* Internal data structure for isl_union_*_drop_dims.
1207 * type, first and n are passed to isl_*_drop_dims.
1209 S(UNION,drop_dims_data) {
1210 enum isl_dim_type type;
1211 unsigned first;
1212 unsigned n;
1215 /* Drop the parameters specified by "data" from "part" and return the result.
1217 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1218 void *user)
1220 S(UNION,drop_dims_data) *data = user;
1222 return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1225 /* Drop the specified parameters from "u".
1226 * That is, type is required to be isl_dim_param.
1228 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1229 enum isl_dim_type type, unsigned first, unsigned n)
1231 isl_space *space;
1232 S(UNION,drop_dims_data) data = { type, first, n };
1234 if (!u)
1235 return NULL;
1237 if (type != isl_dim_param)
1238 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1239 "can only project out parameters",
1240 return FN(UNION,free)(u));
1242 space = FN(UNION,get_space)(u);
1243 space = isl_space_drop_dims(space, type, first, n);
1244 return FN(UNION,transform_space)(u, space, &FN(UNION,drop_dims_entry),
1245 &data);
1248 /* Internal data structure for isl_union_*_set_dim_name.
1249 * pos is the position of the parameter that needs to be renamed.
1250 * s is the new name.
1252 S(UNION,set_dim_name_data) {
1253 unsigned pos;
1254 const char *s;
1257 /* Change the name of the parameter at position data->pos of "part" to data->s
1258 * and return the result.
1260 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1261 void *user)
1263 S(UNION,set_dim_name_data) *data = user;
1265 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1268 /* Change the name of the parameter at position "pos" to "s".
1269 * That is, type is required to be isl_dim_param.
1271 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1272 enum isl_dim_type type, unsigned pos, const char *s)
1274 S(UNION,set_dim_name_data) data = { pos, s };
1275 isl_space *space;
1277 if (!u)
1278 return NULL;
1280 if (type != isl_dim_param)
1281 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1282 "can only set parameter names",
1283 return FN(UNION,free)(u));
1285 space = FN(UNION,get_space)(u);
1286 space = isl_space_set_dim_name(space, type, pos, s);
1287 return FN(UNION,transform_space)(u, space,
1288 &FN(UNION,set_dim_name_entry), &data);
1291 /* Reset the user pointer on all identifiers of parameters and tuples
1292 * of the space of "part" and return the result.
1294 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1295 void *user)
1297 return FN(PART,reset_user)(part);
1300 /* Reset the user pointer on all identifiers of parameters and tuples
1301 * of the spaces of "u".
1303 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1305 isl_space *space;
1307 space = FN(UNION,get_space)(u);
1308 space = isl_space_reset_user(space);
1309 return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry),
1310 NULL);