?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
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
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 */
12
13 #include <isl_hash_private.h>
14 #include <isl_union_macro.h>
15
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.
19 */
20 struct UNION {
21 int ref;
22 #ifdef HAS_TYPE
23 enum isl_fold type;
24 #endif
25 isl_space *space;
26
27 struct isl_hash_table table;
28 };
29
30 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
31
32 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
33 {
34 return u ? u->space->ctx : NULL;
35 }
36
37 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
38 {
39 if (!u)
40 return NULL;
41 return isl_space_copy(u->space);
42 }
43
44 /* Return the number of parameters of "u", where "type"
45 * is required to be set to isl_dim_param.
46 */
47 unsigned FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
48 {
49 if (!u)
50 return 0;
51
52 if (type != isl_dim_param)
53 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
54 "can only reference parameters", return 0);
55
56 return isl_space_dim(u->space, type);
57 }
58
59 /* Return the position of the parameter with the given name
60 * in "u".
61 * Return -1 if no such dimension can be found.
62 */
63 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
64 const char *name)
65 {
66 if (!u)
67 return -1;
68 return isl_space_find_dim_by_name(u->space, type, name);
69 }
70
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
77 {
78 UNION *u;
79
80 dim = isl_space_params(dim);
81 if (!dim)
82 return NULL;
83
84 u = isl_calloc_type(dim->ctx, UNION);
85 if (!u)
86 goto error;
87
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);
95
96 return u;
97 error:
98 isl_space_free(dim);
99 return NULL;
100 }
101
102 #ifdef HAS_TYPE
103 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
104 {
105 return FN(UNION,alloc)(dim, type, 16);
106 }
107 #else
108 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
109 {
110 return FN(UNION,alloc)(dim, 16);
111 }
112 #endif
113
114 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
115 {
116 if (!u)
117 return NULL;
118
119 u->ref++;
120 return u;
121 }
122
123 /* Return the number of base expressions in "u".
124 */
125 int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
126 {
127 return u ? u->table.n : 0;
128 }
129
130 S(UNION,foreach_data)
131 {
132 isl_stat (*fn)(__isl_take PART *part, void *user);
133 void *user;
134 };
135
136 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
137 {
138 PART *part = *entry;
139 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
140
141 return data->fn(FN(PART,copy)(part), data->user);
142 }
143
144 isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
145 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
146 {
147 S(UNION,foreach_data) data = { fn, user };
148
149 if (!u)
150 return isl_stat_error;
151
152 return isl_hash_table_foreach(u->space->ctx, &u->table,
153 &FN(UNION,call_on_copy), &data);
154 }
155
156 /* Is the domain space of "entry" equal to the domain of "space"?
157 */
158 static int FN(UNION,has_same_domain_space)(const void *entry, const void *val)
159 {
160 PART *part = (PART *)entry;
161 isl_space *space = (isl_space *) val;
162
163 if (isl_space_is_set(space))
164 return isl_space_is_set(part->dim);
165
166 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
167 space, isl_dim_in);
168 }
169
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.
175 *
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.
178 */
179 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
180 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
181 {
182 isl_ctx *ctx;
183 uint32_t hash;
184 struct isl_hash_table_entry *entry;
185 isl_bool equal;
186 PART *part;
187
188 if (!u || !space)
189 return NULL;
190
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);
211 }
212
213 /* Extract the element of "u" living in "space" (ignoring parameters).
214 *
215 * Return the ZERO element if "u" does not contain any element
216 * living in "space".
217 */
218 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
219 __isl_take isl_space *space)
220 {
221 struct isl_hash_table_entry *entry;
222
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;
232 }
233
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;
248 }
249
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.
255 */
256 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
257 __isl_take PART *part, int disjoint)
258 {
259 int empty;
260 struct isl_hash_table_entry *entry;
261
262 if (!part)
263 goto error;
264
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;
271 }
272
273 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
274 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
275
276 u = FN(UNION,cow)(u);
277
278 if (!u)
279 goto error;
280
281 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
282 if (!entry)
283 goto error;
284
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);
302 }
303 FN(PART,free)(part);
304 }
305
306 return u;
307 error:
308 FN(PART,free)(part);
309 FN(UNION,free)(u);
310 return NULL;
311 }
312
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".
315 */
316 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
317 __isl_take PART *part)
318 {
319 return FN(UNION,add_part_generic)(u, part, 1);
320 }
321
322 static isl_stat FN(UNION,add_part)(__isl_take PART *part, void *user)
323 {
324 UNION **u = (UNION **)user;
325
326 *u = FN(FN(UNION,add),PARTS)(*u, part);
327
328 return isl_stat_ok;
329 }
330
331 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
332 {
333 UNION *dup;
334
335 if (!u)
336 return NULL;
337
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;
349 }
350
351 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
352 {
353 if (!u)
354 return NULL;
355
356 if (u->ref == 1)
357 return u;
358 u->ref--;
359 return FN(UNION,dup)(u);
360 }
361
362 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
363 {
364 PART *part = *entry;
365 FN(PART,free)(part);
366 return isl_stat_ok;
367 }
368
369 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
370 {
371 if (!u)
372 return NULL;
373
374 if (--u->ref > 0)
375 return NULL;
376
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;
383 }
384
385 S(UNION,align) {
386 isl_reordering *exp;
387 UNION *res;
388 };
389
390 static isl_stat FN(UNION,align_entry)(__isl_take PART *part, void *user)
391 {
392 isl_reordering *exp;
393 S(UNION,align) *data = user;
394
395 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
396 FN(PART,get_domain_space)(part));
397
398 data->res = FN(FN(UNION,add),PARTS)(data->res,
399 FN(PART,realign_domain)(part, exp));
400
401 return isl_stat_ok;
402 }
403
404 /* Reorder the parameters of "u" according to the given reordering.
405 */
406 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
407 __isl_take isl_reordering *r)
408 {
409 S(UNION,align) data = { NULL, NULL };
410
411 if (!u || !r)
412 goto error;
413
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);
422
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;
430 }
431
432 /* Align the parameters of "u" to those of "model".
433 */
434 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
435 __isl_take isl_space *model)
436 {
437 isl_reordering *r;
438
439 if (!u || !model)
440 goto error;
441
442 if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
443 isl_space_free(model);
444 return u;
445 }
446
447 model = isl_space_params(model);
448 r = isl_parameter_alignment_reordering(u->space, model);
449 isl_space_free(model);
450
451 return FN(UNION,realign_domain)(u, r);
452 error:
453 isl_space_free(model);
454 FN(UNION,free)(u);
455 return NULL;
456 }
457
458 /* Add "part" to *u, taking the union sum if "u" already has
459 * a part defined on the same space as "part".
460 */
461 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
462 {
463 UNION **u = (UNION **)user;
464
465 *u = FN(UNION,add_part_generic)(*u, part, 0);
466
467 return isl_stat_ok;
468 }
469
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.
473 *
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".
479 */
480 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
481 __isl_take UNION *u2)
482 {
483 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
484 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
485
486 u1 = FN(UNION,cow)(u1);
487
488 if (!u1 || !u2)
489 goto error;
490
491 if (FN(FN(UNION,foreach),PARTS)(u2, &FN(UNION,union_add_part), &u1) < 0)
492 goto error;
493
494 FN(UNION,free)(u2);
495
496 return u1;
497 error:
498 FN(UNION,free)(u1);
499 FN(UNION,free)(u2);
500 return NULL;
501 }
502
503 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
504 {
505 isl_space *dim;
506 UNION *u;
507
508 if (!part)
509 return NULL;
510
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);
520
521 return u;
522 }
523
524 S(UNION,match_bin_data) {
525 UNION *u2;
526 UNION *res;
527 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
528 };
529
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.
533 */
534 static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user)
535 {
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;
541
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;
549
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);
556
557 part = FN(PART, copy)(part);
558 part = data->fn(part, FN(PART, copy)(entry2->data));
559
560 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
561 if (!data->res)
562 return isl_stat_error;
563
564 return isl_stat_ok;
565 }
566
567 /* This function is currently only used from isl_polynomial.c
568 * and not from isl_fold.c.
569 */
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.
576 */
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 *))
580 {
581 S(UNION,match_bin_data) data = { NULL, NULL, fn };
582
583 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
584 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
585
586 if (!u1 || !u2)
587 goto error;
588
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;
599
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;
608 }
609
610 /* Compute the sum of "u1" and "u2".
611 *
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.
615 */
616 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
617 {
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
623 }
624
625 #ifndef NO_SUB
626 /* Subtract "u2" from "u1" and return the result.
627 */
628 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
629 {
630 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
631 }
632 #endif
633
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*);
638 };
639
640 static isl_stat FN(UNION,any_set_entry)(void **entry, void *user)
641 {
642 S(UNION,any_set_data) *data = user;
643 PW *pw = *entry;
644
645 pw = FN(PW,copy)(pw);
646 pw = data->fn(pw, isl_set_copy(data->set));
647
648 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
649 if (!data->res)
650 return isl_stat_error;
651
652 return isl_stat_ok;
653 }
654
655 /* Update each element of "u" by calling "fn" on the element and "set".
656 */
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*))
660 {
661 S(UNION,any_set_data) data = { NULL, NULL, fn };
662
663 u = FN(UNION,align_params)(u, isl_set_get_space(set));
664 set = isl_set_align_params(set, FN(UNION,get_space)(u));
665
666 if (!u || !set)
667 goto error;
668
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;
679
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;
688 }
689
690 /* Intersect the domain of "u" with the parameter domain "context".
691 */
692 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
693 __isl_take isl_set *set)
694 {
695 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
696 }
697
698 /* Compute the gist of the domain of "u" with respect to
699 * the parameter domain "context".
700 */
701 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
702 __isl_take isl_set *set)
703 {
704 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
705 }
706
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*);
711 };
712
713 static int FN(UNION,set_has_dim)(const void *entry, const void *val)
714 {
715 isl_set *set = (isl_set *)entry;
716 isl_space *dim = (isl_space *)val;
717
718 return isl_space_is_equal(set->dim, dim);
719 }
720
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.
724 */
725 static isl_stat FN(UNION,match_domain_entry)(void **entry, void *user)
726 {
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;
732
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;
740
741 pw = FN(PW,copy)(pw);
742 pw = data->fn(pw, isl_set_copy(entry2->data));
743
744 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
745 if (!data->res)
746 return isl_stat_error;
747
748 return isl_stat_ok;
749 }
750
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.
754 */
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*))
758 {
759 S(UNION,match_domain_data) data = { NULL, NULL, fn };
760
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));
763
764 if (!u || !uset)
765 goto error;
766
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;
777
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;
786 }
787
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.
791 */
792 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
793 __isl_take isl_union_set *uset)
794 {
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));
799 }
800
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.
804 */
805 S(UNION,subtract_domain_data) {
806 isl_union_set *uset;
807 UNION *res;
808 };
809
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.
813 */
814 static isl_stat FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user)
815 {
816 S(UNION,subtract_domain_data) *data = user;
817 isl_space *space;
818 isl_set *set;
819
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);
824
825 return isl_stat_ok;
826 }
827
828 /* Subtract "uset' from the domain of "u".
829 */
830 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
831 __isl_take isl_union_set *uset)
832 {
833 S(UNION,subtract_domain_data) data;
834
835 if (!u || !uset)
836 goto error;
837
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);
848
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;
856 }
857
858 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
859 __isl_take isl_union_set *uset)
860 {
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));
864 }
865
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.
869 */
870 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
871 {
872 PART **part_p = (PART **) entry;
873 PART *part;
874
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;
881
882 return isl_stat_ok;
883 }
884
885 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
886 {
887 if (!u)
888 return NULL;
889
890 if (isl_hash_table_foreach(u->space->ctx, &u->table,
891 &FN(UNION,coalesce_entry), NULL) < 0)
892 goto error;
893
894 return u;
895 error:
896 FN(UNION,free)(u);
897 return NULL;
898 }
899
900 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
901 {
902 isl_union_set **uset = (isl_union_set **)user;
903
904 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
905
906 return isl_stat_ok;
907 }
908
909 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
910 {
911 isl_union_set *uset;
912
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;
916
917 FN(UNION,free)(u);
918
919 return uset;
920 error:
921 isl_union_set_free(uset);
922 FN(UNION,free)(u);
923 return NULL;
924 }
925
926 static isl_stat FN(UNION,mul_isl_int_entry)(void **entry, void *user)
927 {
928 PW **pw = (PW **)entry;
929 isl_int *v = user;
930
931 *pw = FN(PW,mul_isl_int)(*pw, *v);
932 if (!*pw)
933 return isl_stat_error;
934
935 return isl_stat_ok;
936 }
937
938 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
939 {
940 if (isl_int_is_one(v))
941 return u;
942
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;
953 }
954
955 u = FN(UNION,cow)(u);
956 if (!u)
957 return NULL;
958
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;
966
967 return u;
968 error:
969 FN(UNION,free)(u);
970 return NULL;
971 }
972
973 /* Multiply *entry by the isl_val "user".
974 *
975 * Return 0 on success and -1 on error.
976 */
977 static isl_stat FN(UNION,scale_val_entry)(void **entry, void *user)
978 {
979 PW **pw = (PW **)entry;
980 isl_val *v = user;
981
982 *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
983 if (!*pw)
984 return isl_stat_error;
985
986 return isl_stat_ok;
987 }
988
989 /* Multiply "u" by "v" and return the result.
990 */
991 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
992 __isl_take isl_val *v)
993 {
994 if (!u || !v)
995 goto error;
996 if (isl_val_is_one(v)) {
997 isl_val_free(v);
998 return u;
999 }
1000
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;
1012 }
1013
1014 if (!isl_val_is_rat(v))
1015 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1016 "expecting rational factor", goto error);
1017
1018 u = FN(UNION,cow)(u);
1019 if (!u)
1020 return NULL;
1021
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;
1029
1030 isl_val_free(v);
1031 return u;
1032 error:
1033 isl_val_free(v);
1034 FN(UNION,free)(u);
1035 return NULL;
1036 }
1037
1038 /* Divide *entry by the isl_val "user".
1039 *
1040 * Return 0 on success and -1 on error.
1041 */
1042 static isl_stat FN(UNION,scale_down_val_entry)(void **entry, void *user)
1043 {
1044 PW **pw = (PW **)entry;
1045 isl_val *v = user;
1046
1047 *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v));
1048 if (!*pw)
1049 return isl_stat_error;
1050
1051 return isl_stat_ok;
1052 }
1053
1054 /* Divide "u" by "v" and return the result.
1055 */
1056 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1057 __isl_take isl_val *v)
1058 {
1059 if (!u || !v)
1060 goto error;
1061 if (isl_val_is_one(v)) {
1062 isl_val_free(v);
1063 return u;
1064 }
1065
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);
1072
1073 u = FN(UNION,cow)(u);
1074 if (!u)
1075 return NULL;
1076
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;
1084
1085 isl_val_free(v);
1086 return u;
1087 error:
1088 isl_val_free(v);
1089 FN(UNION,free)(u);
1090 return NULL;
1091 }
1092
1093 S(UNION,plain_is_equal_data)
1094 {
1095 UNION *u2;
1096 isl_bool is_equal;
1097 };
1098
1099 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
1100 {
1101 S(UNION,plain_is_equal_data) *data = user;
1102 struct isl_hash_table_entry *entry2;
1103 PW *pw = *entry;
1104
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;
1112 }
1113
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;
1117
1118 return isl_stat_ok;
1119 }
1120
1121 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1122 {
1123 S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
1124
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;
1131
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;
1138
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;
1144
1145 FN(UNION,free)(u1);
1146 FN(UNION,free)(u2);
1147
1148 return data.is_equal;
1149 error:
1150 FN(UNION,free)(u1);
1151 FN(UNION,free)(u2);
1152 return isl_bool_error;
1153 }
1154
1155 #ifndef NO_NEG
1156 /* Replace *entry by its opposite.
1157 *
1158 * Return 0 on success and -1 on error.
1159 */
1160 static isl_stat FN(UNION,neg_entry)(void **entry, void *user)
1161 {
1162 PW **pw = (PW **) entry;
1163
1164 *pw = FN(PW,neg)(*pw);
1165
1166 return *pw ? isl_stat_ok : isl_stat_error;
1167 }
1168
1169 /* Return the opposite of "u".
1170 */
1171 __isl_give UNION *FN(UNION,neg)(__isl_take UNION *u)
1172 {
1173 u = FN(UNION,cow)(u);
1174 if (!u)
1175 return NULL;
1176
1177 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1178 &FN(UNION,neg_entry), NULL) < 0)
1179 return FN(UNION,free)(u);
1180
1181 return u;
1182 }
1183 #endif
1184
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.
1188 */
1189 S(UNION,drop_dims_data) {
1190 enum isl_dim_type type;
1191 unsigned first;
1192 unsigned n;
1193
1194 UNION *res;
1195 };
1196
1197 /* Drop the parameters specified by "data" from "part" and
1198 * add the results to data->res.
1199 */
1200 static isl_stat FN(UNION,drop_dims_entry)(__isl_take PART *part, void *user)
1201 {
1202 S(UNION,drop_dims_data) *data = user;
1203
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;
1208
1209 return isl_stat_ok;
1210 }
1211
1212 /* Drop the specified parameters from "u".
1213 * That is, type is required to be isl_dim_param.
1214 */
1215 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1216 enum isl_dim_type type, unsigned first, unsigned n)
1217 {
1218 isl_space *space;
1219 S(UNION,drop_dims_data) data = { type, first, n };
1220
1221 if (!u)
1222 return NULL;
1223
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));
1228
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);
1239
1240 FN(UNION,free)(u);
1241
1242 return data.res;
1243 }
1244
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.
1249 */
1250 S(UNION,set_dim_name_data) {
1251 unsigned pos;
1252 const char *s;
1253
1254 UNION *res;
1255 };
1256
1257 /* Change the name of the parameter at position data->pos of "part" to data->s
1258 * and add the result to data->res.
1259 */
1260 static isl_stat FN(UNION,set_dim_name_entry)(__isl_take PART *part, void *user)
1261 {
1262 S(UNION,set_dim_name_data) *data = user;
1263
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;
1268
1269 return isl_stat_ok;
1270 }
1271
1272 /* Change the name of the parameter at position "pos" to "s".
1273 * That is, type is required to be isl_dim_param.
1274 */
1275 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1276 enum isl_dim_type type, unsigned pos, const char *s)
1277 {
1278 S(UNION,set_dim_name_data) data = { pos, s };
1279 isl_space *space;
1280
1281 if (!u)
1282 return NULL;
1283
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));
1288
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
1296
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);
1300
1301 FN(UNION,free)(u);
1302
1303 return data.res;
1304 }
1305
1306 /* Reset the user pointer on all identifiers of parameters and tuples
1307 * of the space of "part" and add the result to *res.
1308 */
1309 static isl_stat FN(UNION,reset_user_entry)(__isl_take PART *part, void *user)
1310 {
1311 UNION **res = user;
1312
1313 part = FN(PART,reset_user)(part);
1314 *res = FN(FN(UNION,add),PARTS)(*res, part);
1315 if (!*res)
1316 return isl_stat_error;
1317
1318 return isl_stat_ok;
1319 }
1320
1321 /* Reset the user pointer on all identifiers of parameters and tuples
1322 * of the spaces of "u".
1323 */
1324 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1325 {
1326 isl_space *space;
1327 UNION *res;
1328
1329 if (!u)
1330 return NULL;
1331
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);
1342
1343 FN(UNION,free)(u);
1344
1345 return res;
1346 }
Integer set library