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