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