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