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