?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_union_pw_*_n_pw_*
[isl.git] / isl_union_templ.c
blobd478d4b62e27eff2c8ccee2158a70778756a20f5
1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the MIT license
5 *
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8 * 91893 Orsay, France
9 */
10
11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
14 #define S(TYPE,NAME) xS(TYPE,NAME)
15
16 struct UNION {
17 int ref;
18 #ifdef HAS_TYPE
19 enum isl_fold type;
20 #endif
21 isl_space *space;
22
23 struct isl_hash_table table;
24 };
25
26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
27
28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
29 {
30 return u ? u->space->ctx : NULL;
31 }
32
33 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
34 {
35 if (!u)
36 return NULL;
37 return isl_space_copy(u->space);
38 }
39
40 /* Return the number of parameters of "u", where "type"
41 * is required to be set to isl_dim_param.
42 */
43 unsigned FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
44 {
45 if (!u)
46 return 0;
47
48 if (type != isl_dim_param)
49 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
50 "can only reference parameters", return 0);
51
52 return isl_space_dim(u->space, type);
53 }
54
55 /* Return the position of the parameter with the given name
56 * in "u".
57 * Return -1 if no such dimension can be found.
58 */
59 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
60 const char *name)
61 {
62 if (!u)
63 return -1;
64 return isl_space_find_dim_by_name(u->space, type, name);
65 }
66
67 #ifdef HAS_TYPE
68 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
69 enum isl_fold type, int size)
70 #else
71 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
72 #endif
73 {
74 UNION *u;
75
76 dim = isl_space_params(dim);
77 if (!dim)
78 return NULL;
79
80 u = isl_calloc_type(dim->ctx, UNION);
81 if (!u)
82 goto error;
83
84 u->ref = 1;
85 #ifdef HAS_TYPE
86 u->type = type;
87 #endif
88 u->space = dim;
89 if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
90 return FN(UNION,free)(u);
91
92 return u;
93 error:
94 isl_space_free(dim);
95 return NULL;
96 }
97
98 #ifdef HAS_TYPE
99 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
100 {
101 return FN(UNION,alloc)(dim, type, 16);
102 }
103 #else
104 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
105 {
106 return FN(UNION,alloc)(dim, 16);
107 }
108 #endif
109
110 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
111 {
112 if (!u)
113 return NULL;
114
115 u->ref++;
116 return u;
117 }
118
119 /* Return the number of base expressions in "u".
120 */
121 int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
122 {
123 return u ? u->table.n : 0;
124 }
125
126 S(UNION,foreach_data)
127 {
128 int (*fn)(__isl_take PART *part, void *user);
129 void *user;
130 };
131
132 static int call_on_copy(void **entry, void *user)
133 {
134 PART *part = *entry;
135 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
136
137 return data->fn(FN(PART,copy)(part), data->user);
138 }
139
140 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
141 int (*fn)(__isl_take PART *part, void *user), void *user)
142 {
143 S(UNION,foreach_data) data = { fn, user };
144
145 if (!u)
146 return -1;
147
148 return isl_hash_table_foreach(u->space->ctx, &u->table,
149 &call_on_copy, &data);
150 }
151
152 /* Is the space of "entry" equal to "space"?
153 */
154 static int has_space(const void *entry, const void *val)
155 {
156 PART *part = (PART *)entry;
157 isl_space *space = (isl_space *) val;
158
159 return isl_space_is_equal(part->dim, space);
160 }
161
162 /* This function is not currently used by isl_aff.c.
163 */
164 static int has_domain_space(const void *entry, const void *val)
165 __attribute__ ((unused));
166
167 /* Is the domain space of "entry" equal to "space"?
168 */
169 static int has_domain_space(const void *entry, const void *val)
170 {
171 PART *part = (PART *)entry;
172 isl_space *space = (isl_space *) val;
173
174 if (isl_space_is_params(space))
175 return isl_space_is_set(part->dim);
176
177 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
178 space, isl_dim_set);
179 }
180
181 /* Is the domain space of "entry" equal to the domain of "space"?
182 */
183 static int has_same_domain_space(const void *entry, const void *val)
184 {
185 PART *part = (PART *)entry;
186 isl_space *space = (isl_space *) val;
187
188 if (isl_space_is_set(space))
189 return isl_space_is_set(part->dim);
190
191 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
192 space, isl_dim_in);
193 }
194
195 /* Extract the element of "u" living in "space" (ignoring parameters).
196 *
197 * Return the ZERO element if "u" does not contain any element
198 * living in "space".
199 */
200 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
201 __isl_take isl_space *space)
202 {
203 uint32_t hash;
204 struct isl_hash_table_entry *entry;
205
206 if (!u || !space)
207 goto error;
208 if (!isl_space_match(u->space, isl_dim_param, space, isl_dim_param)) {
209 space = isl_space_drop_dims(space, isl_dim_param,
210 0, isl_space_dim(space, isl_dim_param));
211 space = isl_space_align_params(space,
212 FN(UNION,get_space)(u));
213 if (!space)
214 goto error;
215 }
216
217 hash = isl_space_get_hash(space);
218 entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
219 &has_space, space, 0);
220 if (!entry)
221 #ifdef HAS_TYPE
222 return FN(PART,ZERO)(space, u->type);
223 #else
224 return FN(PART,ZERO)(space);
225 #endif
226 isl_space_free(space);
227 return FN(PART,copy)(entry->data);
228 error:
229 isl_space_free(space);
230 return NULL;
231 }
232
233 /* Add "part" to "u".
234 * If "disjoint" is set, then "u" is not allowed to already have
235 * a part that is defined on the same space as "part".
236 * Otherwise, compute the union sum of "part" and the part in "u"
237 * defined on the same space.
238 */
239 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
240 __isl_take PART *part, int disjoint)
241 {
242 int empty;
243 uint32_t hash;
244 struct isl_hash_table_entry *entry;
245
246 if (!part)
247 goto error;
248
249 empty = FN(PART,IS_ZERO)(part);
250 if (empty < 0)
251 goto error;
252 if (empty) {
253 FN(PART,free)(part);
254 return u;
255 }
256
257 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
258 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
259
260 u = FN(UNION,cow)(u);
261
262 if (!u)
263 goto error;
264
265 hash = isl_space_get_hash(part->dim);
266 entry = isl_hash_table_find(u->space->ctx, &u->table, hash,
267 &has_same_domain_space, part->dim, 1);
268 if (!entry)
269 goto error;
270
271 if (!entry->data)
272 entry->data = part;
273 else {
274 PART *entry_part = entry->data;
275 if (disjoint)
276 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
277 "additional part should live on separate "
278 "space", goto error);
279 if (!isl_space_tuple_is_equal(entry_part->dim, isl_dim_out,
280 part->dim, isl_dim_out))
281 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
282 "union expression can only contain a single "
283 "expression over a given domain", goto error);
284 entry->data = FN(PART,union_add_)(entry->data,
285 FN(PART,copy)(part));
286 if (!entry->data)
287 goto error;
288 empty = FN(PART,IS_ZERO)(part);
289 if (empty < 0)
290 goto error;
291 if (empty) {
292 FN(PART,free)(entry->data);
293 isl_hash_table_remove(u->space->ctx, &u->table, entry);
294 }
295 FN(PART,free)(part);
296 }
297
298 return u;
299 error:
300 FN(PART,free)(part);
301 FN(UNION,free)(u);
302 return NULL;
303 }
304
305 /* Add "part" to "u", where "u" is assumed not to already have
306 * a part that is defined on the same space as "part".
307 */
308 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
309 __isl_take PART *part)
310 {
311 return FN(UNION,add_part_generic)(u, part, 1);
312 }
313
314 static int add_part(__isl_take PART *part, void *user)
315 {
316 UNION **u = (UNION **)user;
317
318 *u = FN(FN(UNION,add),PARTS)(*u, part);
319
320 return 0;
321 }
322
323 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
324 {
325 UNION *dup;
326
327 if (!u)
328 return NULL;
329
330 #ifdef HAS_TYPE
331 dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type);
332 #else
333 dup = FN(UNION,ZERO)(isl_space_copy(u->space));
334 #endif
335 if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
336 goto error;
337 return dup;
338 error:
339 FN(UNION,free)(dup);
340 return NULL;
341 }
342
343 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
344 {
345 if (!u)
346 return NULL;
347
348 if (u->ref == 1)
349 return u;
350 u->ref--;
351 return FN(UNION,dup)(u);
352 }
353
354 static int free_u_entry(void **entry, void *user)
355 {
356 PART *part = *entry;
357 FN(PART,free)(part);
358 return 0;
359 }
360
361 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
362 {
363 if (!u)
364 return NULL;
365
366 if (--u->ref > 0)
367 return NULL;
368
369 isl_hash_table_foreach(u->space->ctx, &u->table, &free_u_entry, NULL);
370 isl_hash_table_clear(&u->table);
371 isl_space_free(u->space);
372 free(u);
373 return NULL;
374 }
375
376 S(UNION,align) {
377 isl_reordering *exp;
378 UNION *res;
379 };
380
381 #ifdef ALIGN_DOMAIN
382 static int align_entry(__isl_take PART *part, void *user)
383 {
384 isl_reordering *exp;
385 S(UNION,align) *data = user;
386
387 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
388 FN(PART,get_domain_space)(part));
389
390 data->res = FN(FN(UNION,add),PARTS)(data->res,
391 FN(PART,realign_domain)(part, exp));
392
393 return 0;
394 }
395 #else
396 static int align_entry(__isl_take PART *part, void *user)
397 {
398 isl_reordering *exp;
399 S(UNION,align) *data = user;
400
401 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
402 FN(PART,get_space)(part));
403
404 data->res = FN(FN(UNION,add),PARTS)(data->res,
405 FN(PART,realign)(part, exp));
406
407 return 0;
408 }
409 #endif
410
411 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
412 __isl_take isl_space *model)
413 {
414 S(UNION,align) data = { NULL, NULL };
415
416 if (!u || !model)
417 goto error;
418
419 if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
420 isl_space_free(model);
421 return u;
422 }
423
424 model = isl_space_params(model);
425 data.exp = isl_parameter_alignment_reordering(u->space, model);
426 if (!data.exp)
427 goto error;
428
429 #ifdef HAS_TYPE
430 data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
431 u->type, u->table.n);
432 #else
433 data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
434 #endif
435 if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
436 goto error;
437
438 isl_reordering_free(data.exp);
439 FN(UNION,free)(u);
440 isl_space_free(model);
441 return data.res;
442 error:
443 isl_reordering_free(data.exp);
444 FN(UNION,free)(u);
445 FN(UNION,free)(data.res);
446 isl_space_free(model);
447 return NULL;
448 }
449
450 /* Add "part" to *u, taking the union sum if "u" already has
451 * a part defined on the same space as "part".
452 */
453 static int union_add_part(__isl_take PART *part, void *user)
454 {
455 UNION **u = (UNION **)user;
456
457 *u = FN(UNION,add_part_generic)(*u, part, 0);
458
459 return 0;
460 }
461
462 /* Compute the sum of "u1" and "u2" on the union of their domains,
463 * with the actual sum on the shared domain and
464 * the defined expression on the symmetric difference of the domains.
465 *
466 * This is an internal function that is exposed under different
467 * names depending on whether the base expressions have a zero default
468 * value.
469 * If they do, then this function is called "add".
470 * Otherwise, it is called "union_add".
471 */
472 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
473 __isl_take UNION *u2)
474 {
475 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
476 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
477
478 u1 = FN(UNION,cow)(u1);
479
480 if (!u1 || !u2)
481 goto error;
482
483 if (FN(FN(UNION,foreach),PARTS)(u2, &union_add_part, &u1) < 0)
484 goto error;
485
486 FN(UNION,free)(u2);
487
488 return u1;
489 error:
490 FN(UNION,free)(u1);
491 FN(UNION,free)(u2);
492 return NULL;
493 }
494
495 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
496 {
497 isl_space *dim;
498 UNION *u;
499
500 if (!part)
501 return NULL;
502
503 dim = FN(PART,get_space)(part);
504 dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
505 dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
506 #ifdef HAS_TYPE
507 u = FN(UNION,ZERO)(dim, part->type);
508 #else
509 u = FN(UNION,ZERO)(dim);
510 #endif
511 u = FN(FN(UNION,add),PARTS)(u, part);
512
513 return u;
514 }
515
516 S(UNION,match_bin_data) {
517 UNION *u2;
518 UNION *res;
519 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
520 };
521
522 /* Check if data->u2 has an element living in the same space as *entry.
523 * If so, call data->fn on the two elements and add the result to
524 * data->res.
525 */
526 static int match_bin_entry(void **entry, void *user)
527 {
528 S(UNION,match_bin_data) *data = user;
529 uint32_t hash;
530 struct isl_hash_table_entry *entry2;
531 isl_space *space;
532 PART *part = *entry;
533 PART *part2;
534
535 space = FN(PART,get_space)(part);
536 hash = isl_space_get_hash(space);
537 entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
538 hash, &has_same_domain_space, space, 0);
539 isl_space_free(space);
540 if (!entry2)
541 return 0;
542
543 part2 = entry2->data;
544 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
545 part2->dim, isl_dim_out))
546 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
547 "entries should have the same range space",
548 return -1);
549
550 part = FN(PART, copy)(part);
551 part = data->fn(part, FN(PART, copy)(entry2->data));
552
553 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
554 if (!data->res)
555 return -1;
556
557 return 0;
558 }
559
560 /* This function is currently only used from isl_polynomial.c
561 * and not from isl_fold.c.
562 */
563 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
564 __isl_take UNION *u2,
565 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
566 __attribute__ ((unused));
567 /* For each pair of elements in "u1" and "u2" living in the same space,
568 * call "fn" and collect the results.
569 */
570 static __isl_give 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 {
574 S(UNION,match_bin_data) data = { NULL, NULL, fn };
575
576 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
577 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
578
579 if (!u1 || !u2)
580 goto error;
581
582 data.u2 = u2;
583 #ifdef HAS_TYPE
584 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type,
585 u1->table.n);
586 #else
587 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n);
588 #endif
589 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
590 &match_bin_entry, &data) < 0)
591 goto error;
592
593 FN(UNION,free)(u1);
594 FN(UNION,free)(u2);
595 return data.res;
596 error:
597 FN(UNION,free)(u1);
598 FN(UNION,free)(u2);
599 FN(UNION,free)(data.res);
600 return NULL;
601 }
602
603 /* Compute the sum of "u1" and "u2".
604 *
605 * If the base expressions have a default zero value, then the sum
606 * is computed on the union of the domains of "u1" and "u2".
607 * Otherwise, it is computed on their shared domains.
608 */
609 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
610 {
611 #if DEFAULT_IS_ZERO
612 return FN(UNION,union_add_)(u1, u2);
613 #else
614 return match_bin_op(u1, u2, &FN(PART,add));
615 #endif
616 }
617
618 #ifndef NO_SUB
619 /* Subtract "u2" from "u1" and return the result.
620 */
621 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
622 {
623 return match_bin_op(u1, u2, &FN(PART,sub));
624 }
625 #endif
626
627 S(UNION,any_set_data) {
628 isl_set *set;
629 UNION *res;
630 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
631 };
632
633 static int any_set_entry(void **entry, void *user)
634 {
635 S(UNION,any_set_data) *data = user;
636 PW *pw = *entry;
637
638 pw = FN(PW,copy)(pw);
639 pw = data->fn(pw, isl_set_copy(data->set));
640
641 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
642 if (!data->res)
643 return -1;
644
645 return 0;
646 }
647
648 /* Update each element of "u" by calling "fn" on the element and "set".
649 */
650 static __isl_give UNION *any_set_op(__isl_take UNION *u,
651 __isl_take isl_set *set,
652 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
653 {
654 S(UNION,any_set_data) data = { NULL, NULL, fn };
655
656 u = FN(UNION,align_params)(u, isl_set_get_space(set));
657 set = isl_set_align_params(set, FN(UNION,get_space)(u));
658
659 if (!u || !set)
660 goto error;
661
662 data.set = set;
663 #ifdef HAS_TYPE
664 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
665 u->table.n);
666 #else
667 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
668 #endif
669 if (isl_hash_table_foreach(u->space->ctx, &u->table,
670 &any_set_entry, &data) < 0)
671 goto error;
672
673 FN(UNION,free)(u);
674 isl_set_free(set);
675 return data.res;
676 error:
677 FN(UNION,free)(u);
678 isl_set_free(set);
679 FN(UNION,free)(data.res);
680 return NULL;
681 }
682
683 /* Intersect the domain of "u" with the parameter domain "context".
684 */
685 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
686 __isl_take isl_set *set)
687 {
688 return any_set_op(u, set, &FN(PW,intersect_params));
689 }
690
691 /* Compute the gist of the domain of "u" with respect to
692 * the parameter domain "context".
693 */
694 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
695 __isl_take isl_set *set)
696 {
697 return any_set_op(u, set, &FN(PW,gist_params));
698 }
699
700 S(UNION,match_domain_data) {
701 isl_union_set *uset;
702 UNION *res;
703 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
704 };
705
706 static int set_has_dim(const void *entry, const void *val)
707 {
708 isl_set *set = (isl_set *)entry;
709 isl_space *dim = (isl_space *)val;
710
711 return isl_space_is_equal(set->dim, dim);
712 }
713
714 /* Find the set in data->uset that lives in the same space as the domain
715 * of *entry, apply data->fn to *entry and this set (if any), and add
716 * the result to data->res.
717 */
718 static int match_domain_entry(void **entry, void *user)
719 {
720 S(UNION,match_domain_data) *data = user;
721 uint32_t hash;
722 struct isl_hash_table_entry *entry2;
723 PW *pw = *entry;
724 isl_space *space;
725
726 space = FN(PW,get_domain_space)(pw);
727 hash = isl_space_get_hash(space);
728 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
729 hash, &set_has_dim, space, 0);
730 isl_space_free(space);
731 if (!entry2)
732 return 0;
733
734 pw = FN(PW,copy)(pw);
735 pw = data->fn(pw, isl_set_copy(entry2->data));
736
737 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
738 if (!data->res)
739 return -1;
740
741 return 0;
742 }
743
744 /* Apply fn to each pair of PW in u and set in uset such that
745 * the set lives in the same space as the domain of PW
746 * and collect the results.
747 */
748 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
749 __isl_take isl_union_set *uset,
750 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
751 {
752 S(UNION,match_domain_data) data = { NULL, NULL, fn };
753
754 u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
755 uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
756
757 if (!u || !uset)
758 goto error;
759
760 data.uset = uset;
761 #ifdef HAS_TYPE
762 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
763 u->table.n);
764 #else
765 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
766 #endif
767 if (isl_hash_table_foreach(u->space->ctx, &u->table,
768 &match_domain_entry, &data) < 0)
769 goto error;
770
771 FN(UNION,free)(u);
772 isl_union_set_free(uset);
773 return data.res;
774 error:
775 FN(UNION,free)(u);
776 isl_union_set_free(uset);
777 FN(UNION,free)(data.res);
778 return NULL;
779 }
780
781 /* Intersect the domain of "u" with "uset".
782 * If "uset" is a parameters domain, then intersect the parameter
783 * domain of "u" with this set.
784 */
785 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
786 __isl_take isl_union_set *uset)
787 {
788 if (isl_union_set_is_params(uset))
789 return FN(UNION,intersect_params)(u,
790 isl_set_from_union_set(uset));
791 return match_domain_op(u, uset, &FN(PW,intersect_domain));
792 }
793
794 /* Internal data structure for isl_union_*_subtract_domain.
795 * uset is the set that needs to be removed from the domain.
796 * res collects the results.
797 */
798 S(UNION,subtract_domain_data) {
799 isl_union_set *uset;
800 UNION *res;
801 };
802
803 /* Take the set (which may be empty) in data->uset that lives
804 * in the same space as the domain of "pw", subtract it from the domain
805 * of "pw" and add the result to data->res.
806 */
807 static int FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user)
808 {
809 S(UNION,subtract_domain_data) *data = user;
810 isl_space *space;
811 isl_set *set;
812
813 space = FN(PW,get_domain_space)(pw);
814 set = isl_union_set_extract_set(data->uset, space);
815 pw = FN(PW,subtract_domain)(pw, set);
816 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
817
818 return 0;
819 }
820
821 /* Subtract "uset' from the domain of "u".
822 */
823 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
824 __isl_take isl_union_set *uset)
825 {
826 S(UNION,subtract_domain_data) data;
827
828 if (!u || !uset)
829 goto error;
830
831 data.uset = uset;
832 #ifdef HAS_TYPE
833 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
834 u->table.n);
835 #else
836 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
837 #endif
838 if (FN(FN(UNION,foreach),PARTS)(u,
839 &FN(UNION,subtract_domain_entry), &data) < 0)
840 data.res = FN(UNION,free)(data.res);
841
842 FN(UNION,free)(u);
843 isl_union_set_free(uset);
844 return data.res;
845 error:
846 FN(UNION,free)(u);
847 isl_union_set_free(uset);
848 return NULL;
849 }
850
851 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
852 __isl_take isl_union_set *uset)
853 {
854 if (isl_union_set_is_params(uset))
855 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
856 return match_domain_op(u, uset, &FN(PW,gist));
857 }
858
859 #ifndef NO_EVAL
860 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
861 __isl_take isl_point *pnt)
862 {
863 uint32_t hash;
864 struct isl_hash_table_entry *entry;
865 isl_space *space;
866 isl_val *v;
867
868 if (!u || !pnt)
869 goto error;
870
871 space = isl_space_copy(pnt->dim);
872 if (!space)
873 goto error;
874 hash = isl_space_get_hash(space);
875 entry = isl_hash_table_find(u->space->ctx, &u->table,
876 hash, &has_domain_space, space, 0);
877 isl_space_free(space);
878 if (!entry) {
879 v = isl_val_zero(isl_point_get_ctx(pnt));
880 isl_point_free(pnt);
881 } else {
882 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
883 }
884 FN(UNION,free)(u);
885 return v;
886 error:
887 FN(UNION,free)(u);
888 isl_point_free(pnt);
889 return NULL;
890 }
891 #endif
892
893 static int coalesce_entry(void **entry, void *user)
894 {
895 PW **pw = (PW **)entry;
896
897 *pw = FN(PW,coalesce)(*pw);
898 if (!*pw)
899 return -1;
900
901 return 0;
902 }
903
904 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
905 {
906 if (!u)
907 return NULL;
908
909 if (isl_hash_table_foreach(u->space->ctx, &u->table,
910 &coalesce_entry, NULL) < 0)
911 goto error;
912
913 return u;
914 error:
915 FN(UNION,free)(u);
916 return NULL;
917 }
918
919 static int domain(__isl_take PART *part, void *user)
920 {
921 isl_union_set **uset = (isl_union_set **)user;
922
923 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
924
925 return 0;
926 }
927
928 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
929 {
930 isl_union_set *uset;
931
932 uset = isl_union_set_empty(FN(UNION,get_space)(u));
933 if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
934 goto error;
935
936 FN(UNION,free)(u);
937
938 return uset;
939 error:
940 isl_union_set_free(uset);
941 FN(UNION,free)(u);
942 return NULL;
943 }
944
945 static int mul_isl_int(void **entry, void *user)
946 {
947 PW **pw = (PW **)entry;
948 isl_int *v = user;
949
950 *pw = FN(PW,mul_isl_int)(*pw, *v);
951 if (!*pw)
952 return -1;
953
954 return 0;
955 }
956
957 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
958 {
959 if (isl_int_is_one(v))
960 return u;
961
962 if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
963 UNION *zero;
964 isl_space *dim = FN(UNION,get_space)(u);
965 #ifdef HAS_TYPE
966 zero = FN(UNION,ZERO)(dim, u->type);
967 #else
968 zero = FN(UNION,ZERO)(dim);
969 #endif
970 FN(UNION,free)(u);
971 return zero;
972 }
973
974 u = FN(UNION,cow)(u);
975 if (!u)
976 return NULL;
977
978 #ifdef HAS_TYPE
979 if (isl_int_is_neg(v))
980 u->type = isl_fold_type_negate(u->type);
981 #endif
982 if (isl_hash_table_foreach(u->space->ctx, &u->table,
983 &mul_isl_int, &v) < 0)
984 goto error;
985
986 return u;
987 error:
988 FN(UNION,free)(u);
989 return NULL;
990 }
991
992 /* Multiply *entry by the isl_val "user".
993 *
994 * Return 0 on success and -1 on error.
995 */
996 static int scale_val(void **entry, void *user)
997 {
998 PW **pw = (PW **)entry;
999 isl_val *v = user;
1000
1001 *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
1002 if (!*pw)
1003 return -1;
1004
1005 return 0;
1006 }
1007
1008 /* Multiply "u" by "v" and return the result.
1009 */
1010 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1011 __isl_take isl_val *v)
1012 {
1013 if (!u || !v)
1014 goto error;
1015 if (isl_val_is_one(v)) {
1016 isl_val_free(v);
1017 return u;
1018 }
1019
1020 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1021 UNION *zero;
1022 isl_space *space = FN(UNION,get_space)(u);
1023 #ifdef HAS_TYPE
1024 zero = FN(UNION,ZERO)(space, u->type);
1025 #else
1026 zero = FN(UNION,ZERO)(space);
1027 #endif
1028 FN(UNION,free)(u);
1029 isl_val_free(v);
1030 return zero;
1031 }
1032
1033 if (!isl_val_is_rat(v))
1034 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1035 "expecting rational factor", goto error);
1036
1037 u = FN(UNION,cow)(u);
1038 if (!u)
1039 return NULL;
1040
1041 #ifdef HAS_TYPE
1042 if (isl_val_is_neg(v))
1043 u->type = isl_fold_type_negate(u->type);
1044 #endif
1045 if (isl_hash_table_foreach(u->space->ctx, &u->table, &scale_val, v) < 0)
1046 goto error;
1047
1048 isl_val_free(v);
1049 return u;
1050 error:
1051 isl_val_free(v);
1052 FN(UNION,free)(u);
1053 return NULL;
1054 }
1055
1056 /* Divide *entry by the isl_val "user".
1057 *
1058 * Return 0 on success and -1 on error.
1059 */
1060 static int FN(UNION,scale_down_val_entry)(void **entry, void *user)
1061 {
1062 PW **pw = (PW **)entry;
1063 isl_val *v = user;
1064
1065 *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v));
1066 if (!*pw)
1067 return -1;
1068
1069 return 0;
1070 }
1071
1072 /* Divide "u" by "v" and return the result.
1073 */
1074 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1075 __isl_take isl_val *v)
1076 {
1077 if (!u || !v)
1078 goto error;
1079 if (isl_val_is_one(v)) {
1080 isl_val_free(v);
1081 return u;
1082 }
1083
1084 if (!isl_val_is_rat(v))
1085 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1086 "expecting rational factor", goto error);
1087 if (isl_val_is_zero(v))
1088 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1089 "cannot scale down by zero", goto error);
1090
1091 u = FN(UNION,cow)(u);
1092 if (!u)
1093 return NULL;
1094
1095 #ifdef HAS_TYPE
1096 if (isl_val_is_neg(v))
1097 u->type = isl_fold_type_negate(u->type);
1098 #endif
1099 if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table,
1100 &FN(UNION,scale_down_val_entry), v) < 0)
1101 goto error;
1102
1103 isl_val_free(v);
1104 return u;
1105 error:
1106 isl_val_free(v);
1107 FN(UNION,free)(u);
1108 return NULL;
1109 }
1110
1111 S(UNION,plain_is_equal_data)
1112 {
1113 UNION *u2;
1114 int is_equal;
1115 };
1116
1117 static int plain_is_equal_entry(void **entry, void *user)
1118 {
1119 S(UNION,plain_is_equal_data) *data = user;
1120 uint32_t hash;
1121 struct isl_hash_table_entry *entry2;
1122 PW *pw = *entry;
1123
1124 hash = isl_space_get_hash(pw->dim);
1125 entry2 = isl_hash_table_find(data->u2->space->ctx, &data->u2->table,
1126 hash, &has_same_domain_space, pw->dim, 0);
1127 if (!entry2) {
1128 data->is_equal = 0;
1129 return -1;
1130 }
1131
1132 data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
1133 if (data->is_equal < 0 || !data->is_equal)
1134 return -1;
1135
1136 return 0;
1137 }
1138
1139 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1140 {
1141 S(UNION,plain_is_equal_data) data = { NULL, 1 };
1142
1143 if (!u1 || !u2)
1144 return -1;
1145 if (u1 == u2)
1146 return 1;
1147 if (u1->table.n != u2->table.n)
1148 return 0;
1149
1150 u1 = FN(UNION,copy)(u1);
1151 u2 = FN(UNION,copy)(u2);
1152 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1153 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1154 if (!u1 || !u2)
1155 goto error;
1156
1157 data.u2 = u2;
1158 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
1159 &plain_is_equal_entry, &data) < 0 &&
1160 data.is_equal)
1161 goto error;
1162
1163 FN(UNION,free)(u1);
1164 FN(UNION,free)(u2);
1165
1166 return data.is_equal;
1167 error:
1168 FN(UNION,free)(u1);
1169 FN(UNION,free)(u2);
1170 return -1;
1171 }
1172
1173 #ifndef NO_NEG
1174 /* Replace *entry by its opposite.
1175 *
1176 * Return 0 on success and -1 on error.
1177 */
1178 static int FN(UNION,neg_entry)(void **entry, void *user)
1179 {
1180 PW **pw = (PW **) entry;
1181
1182 *pw = FN(PW,neg)(*pw);
1183
1184 return *pw ? 0 : -1;
1185 }
1186
1187 /* Return the opposite of "u".
1188 */
1189 __isl_give UNION *FN(UNION,neg)(__isl_take UNION *u)
1190 {
1191 u = FN(UNION,cow)(u);
1192 if (!u)
1193 return NULL;
1194
1195 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1196 &FN(UNION,neg_entry), NULL) < 0)
1197 return FN(UNION,free)(u);
1198
1199 return u;
1200 }
1201 #endif
1202
1203 /* Reset the user pointer on all identifiers of parameters and tuples
1204 * of the space of "part" and add the result to *res.
1205 */
1206 static int FN(UNION,reset_user_entry)(__isl_take PART *part, void *user)
1207 {
1208 UNION **res = user;
1209
1210 part = FN(PART,reset_user)(part);
1211 *res = FN(FN(UNION,add),PARTS)(*res, part);
1212 if (!*res)
1213 return -1;
1214
1215 return 0;
1216 }
1217
1218 /* Reset the user pointer on all identifiers of parameters and tuples
1219 * of the spaces of "u".
1220 */
1221 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1222 {
1223 isl_space *space;
1224 UNION *res;
1225
1226 if (!u)
1227 return NULL;
1228
1229 space = FN(UNION,get_space)(u);
1230 space = isl_space_reset_user(space);
1231 #ifdef HAS_TYPE
1232 res = FN(UNION,alloc)(space, u->type, u->table.n);
1233 #else
1234 res = FN(UNION,alloc)(space, u->table.n);
1235 #endif
1236 if (FN(FN(UNION,foreach),PARTS)(u,
1237 &FN(UNION,reset_user_entry), &res) < 0)
1238 res = FN(UNION,free)(res);
1239
1240 FN(UNION,free)(u);
1241
1242 return res;
1243 }
Integer set library