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