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