add packaging
[platform/upstream/isl.git] / isl_union_templ.c
1 /*
2  * Copyright 2010      INRIA Saclay
3  *
4  * Use of this software is governed by the MIT license
5  *
6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8  * 91893 Orsay, France 
9  */
10
11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
14 #define S(TYPE,NAME) xS(TYPE,NAME)
15
16 struct UNION {
17         int ref;
18 #ifdef HAS_TYPE
19         enum isl_fold type;
20 #endif
21         isl_space *dim;
22
23         struct isl_hash_table   table;
24 };
25
26 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
27
28 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
29 {
30         return u ? u->dim->ctx : NULL;
31 }
32
33 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
34 {
35         if (!u)
36                 return NULL;
37         return isl_space_copy(u->dim);
38 }
39
40 #ifdef HAS_TYPE
41 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
42         enum isl_fold type, int size)
43 #else
44 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
45 #endif
46 {
47         UNION *u;
48
49         dim = isl_space_params(dim);
50         if (!dim)
51                 return NULL;
52
53         u = isl_calloc_type(dim->ctx, UNION);
54         if (!u)
55                 return NULL;
56
57         u->ref = 1;
58 #ifdef HAS_TYPE
59         u->type = type;
60 #endif
61         u->dim = dim;
62         if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
63                 goto error;
64
65         return u;
66 error:
67         isl_space_free(dim);
68         FN(UNION,free)(u);
69         return NULL;
70 }
71
72 #ifdef HAS_TYPE
73 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
74 {
75         return FN(UNION,alloc)(dim, type, 16);
76 }
77 #else
78 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
79 {
80         return FN(UNION,alloc)(dim, 16);
81 }
82 #endif
83
84 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
85 {
86         if (!u)
87                 return NULL;
88
89         u->ref++;
90         return u;
91 }
92
93 S(UNION,foreach_data)
94 {
95         int (*fn)(__isl_take PART *part, void *user);
96         void *user;
97 };
98
99 static int call_on_copy(void **entry, void *user)
100 {
101         PART *part = *entry;
102         S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
103
104         return data->fn(FN(PART,copy)(part), data->user);
105 }
106
107 int FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
108         int (*fn)(__isl_take PART *part, void *user), void *user)
109 {
110         S(UNION,foreach_data) data = { fn, user };
111
112         if (!u)
113                 return -1;
114
115         return isl_hash_table_foreach(u->dim->ctx, &u->table,
116                                       &call_on_copy, &data);
117 }
118
119 static int has_dim(const void *entry, const void *val)
120 {
121         PART *part = (PART *)entry;
122         isl_space *dim = (isl_space *)val;
123
124         return isl_space_is_equal(part->dim, dim);
125 }
126
127 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
128         __isl_take isl_space *dim)
129 {
130         uint32_t hash;
131         struct isl_hash_table_entry *entry;
132
133         if (!u || !dim)
134                 goto error;
135
136         hash = isl_space_get_hash(dim);
137         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
138                                     &has_dim, dim, 0);
139         if (!entry)
140 #ifdef HAS_TYPE
141                 return FN(PART,ZERO)(dim, u->type);
142 #else
143                 return FN(PART,ZERO)(dim);
144 #endif
145         isl_space_free(dim);
146         return FN(PART,copy)(entry->data);
147 error:
148         isl_space_free(dim);
149         return NULL;
150 }
151
152 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
153         __isl_take PART *part)
154 {
155         uint32_t hash;
156         struct isl_hash_table_entry *entry;
157
158         if (!part)
159                 goto error;
160
161         if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(part)) {
162                 FN(PART,free)(part);
163                 return u;
164         }
165
166         u = FN(UNION,cow)(u);
167
168         if (!u)
169                 goto error;
170
171         isl_assert(u->dim->ctx, isl_space_match(part->dim, isl_dim_param, u->dim,
172                                               isl_dim_param), goto error);
173
174         hash = isl_space_get_hash(part->dim);
175         entry = isl_hash_table_find(u->dim->ctx, &u->table, hash,
176                                     &has_dim, part->dim, 1);
177         if (!entry)
178                 goto error;
179
180         if (!entry->data)
181                 entry->data = part;
182         else {
183                 entry->data = FN(PART,add)(entry->data, FN(PART,copy)(part));
184                 if (!entry->data)
185                         goto error;
186                 FN(PART,free)(part);
187                 if (DEFAULT_IS_ZERO && FN(PART,IS_ZERO)(entry->data)) {
188                         FN(PART,free)(entry->data);
189                         isl_hash_table_remove(u->dim->ctx, &u->table, entry);
190                 }
191         }
192
193         return u;
194 error:
195         FN(PART,free)(part);
196         FN(UNION,free)(u);
197         return NULL;
198 }
199
200 static int add_part(__isl_take PART *part, void *user)
201 {
202         UNION **u = (UNION **)user;
203
204         *u = FN(FN(UNION,add),PARTS)(*u, part);
205
206         return 0;
207 }
208
209 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
210 {
211         UNION *dup;
212
213         if (!u)
214                 return NULL;
215
216 #ifdef HAS_TYPE
217         dup = FN(UNION,ZERO)(isl_space_copy(u->dim), u->type);
218 #else
219         dup = FN(UNION,ZERO)(isl_space_copy(u->dim));
220 #endif
221         if (FN(FN(UNION,foreach),PARTS)(u, &add_part, &dup) < 0)
222                 goto error;
223         return dup;
224 error:
225         FN(UNION,free)(dup);
226         return NULL;
227 }
228
229 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
230 {
231         if (!u)
232                 return NULL;
233
234         if (u->ref == 1)
235                 return u;
236         u->ref--;
237         return FN(UNION,dup)(u);
238 }
239
240 static int free_u_entry(void **entry, void *user)
241 {
242         PART *part = *entry;
243         FN(PART,free)(part);
244         return 0;
245 }
246
247 void *FN(UNION,free)(__isl_take UNION *u)
248 {
249         if (!u)
250                 return NULL;
251
252         if (--u->ref > 0)
253                 return NULL;
254
255         isl_hash_table_foreach(u->dim->ctx, &u->table, &free_u_entry, NULL);
256         isl_hash_table_clear(&u->table);
257         isl_space_free(u->dim);
258         free(u);
259         return NULL;
260 }
261
262 S(UNION,align) {
263         isl_reordering *exp;
264         UNION *res;
265 };
266
267 #ifdef ALIGN_DOMAIN
268 static int align_entry(__isl_take PART *part, void *user)
269 {
270         isl_reordering *exp;
271         S(UNION,align) *data = user;
272
273         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
274                                     FN(PART,get_domain_space)(part));
275
276         data->res = FN(FN(UNION,add),PARTS)(data->res,
277                                             FN(PART,realign_domain)(part, exp));
278
279         return 0;
280 }
281 #else
282 static int align_entry(__isl_take PART *part, void *user)
283 {
284         isl_reordering *exp;
285         S(UNION,align) *data = user;
286
287         exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
288                                     FN(PART,get_space)(part));
289
290         data->res = FN(FN(UNION,add),PARTS)(data->res,
291                                             FN(PART,realign)(part, exp));
292
293         return 0;
294 }
295 #endif
296
297 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
298         __isl_take isl_space *model)
299 {
300         S(UNION,align) data = { NULL, NULL };
301
302         if (!u || !model)
303                 goto error;
304
305         if (isl_space_match(u->dim, isl_dim_param, model, isl_dim_param)) {
306                 isl_space_free(model);
307                 return u;
308         }
309
310         data.exp = isl_parameter_alignment_reordering(u->dim, model);
311         if (!data.exp)
312                 goto error;
313
314 #ifdef HAS_TYPE
315         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
316                                                 u->type, u->table.n);
317 #else
318         data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
319 #endif
320         if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
321                 goto error;
322
323         isl_reordering_free(data.exp);
324         FN(UNION,free)(u);
325         isl_space_free(model);
326         return data.res;
327 error:
328         isl_reordering_free(data.exp);
329         FN(UNION,free)(u);
330         FN(UNION,free)(data.res);
331         isl_space_free(model);
332         return NULL;
333 }
334
335 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
336 {
337         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
338         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
339
340         u1 = FN(UNION,cow)(u1);
341
342         if (!u1 || !u2)
343                 goto error;
344
345         if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
346                 goto error;
347
348         FN(UNION,free)(u2);
349
350         return u1;
351 error:
352         FN(UNION,free)(u1);
353         FN(UNION,free)(u2);
354         return NULL;
355 }
356
357 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
358 {
359         isl_space *dim;
360         UNION *u;
361
362         if (!part)
363                 return NULL;
364
365         dim = FN(PART,get_space)(part);
366         dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
367         dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
368 #ifdef HAS_TYPE
369         u = FN(UNION,ZERO)(dim, part->type);
370 #else
371         u = FN(UNION,ZERO)(dim);
372 #endif
373         u = FN(FN(UNION,add),PARTS)(u, part);
374
375         return u;
376 }
377
378 S(UNION,match_bin_data) {
379         UNION *u2;
380         UNION *res;
381         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
382 };
383
384 /* Check if data->u2 has an element living in the same space as *entry.
385  * If so, call data->fn on the two elements and add the result to
386  * data->res.
387  */
388 static int match_bin_entry(void **entry, void *user)
389 {
390         S(UNION,match_bin_data) *data = user;
391         uint32_t hash;
392         struct isl_hash_table_entry *entry2;
393         isl_space *space;
394         PART *part = *entry;
395
396         space = FN(PART,get_space)(part);
397         hash = isl_space_get_hash(space);
398         entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
399                                      hash, &has_dim, space, 0);
400         isl_space_free(space);
401         if (!entry2)
402                 return 0;
403
404         part = FN(PART, copy)(part);
405         part = data->fn(part, FN(PART, copy)(entry2->data));
406
407         if (DEFAULT_IS_ZERO) {
408                 int empty;
409
410                 empty = FN(PART,IS_ZERO)(part);
411                 if (empty < 0) {
412                         FN(PART,free)(part);
413                         return -1;
414                 }
415                 if (empty) {
416                         FN(PART,free)(part);
417                         return 0;
418                 }
419         }
420
421         data->res = FN(FN(UNION,add),PARTS)(data->res, part);
422
423         return 0;
424 }
425
426 /* This function is currently only used from isl_polynomial.c
427  * and not from isl_fold.c.
428  */
429 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
430         __isl_take UNION *u2,
431         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
432         __attribute__ ((unused));
433 /* For each pair of elements in "u1" and "u2" living in the same space,
434  * call "fn" and collect the results.
435  */
436 static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
437         __isl_take UNION *u2,
438         __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
439 {
440         S(UNION,match_bin_data) data = { NULL, NULL, fn };
441
442         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
443         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
444
445         if (!u1 || !u2)
446                 goto error;
447
448         data.u2 = u2;
449 #ifdef HAS_TYPE
450         data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->type, u1->table.n);
451 #else
452         data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->table.n);
453 #endif
454         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
455                                     &match_bin_entry, &data) < 0)
456                 goto error;
457
458         FN(UNION,free)(u1);
459         FN(UNION,free)(u2);
460         return data.res;
461 error:
462         FN(UNION,free)(u1);
463         FN(UNION,free)(u2);
464         FN(UNION,free)(data.res);
465         return NULL;
466 }
467
468 #ifndef NO_SUB
469 /* Subtract "u2" from "u1" and return the result.
470  */
471 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
472 {
473         return match_bin_op(u1, u2, &FN(PART,sub));
474 }
475 #endif
476
477 S(UNION,any_set_data) {
478         isl_set *set;
479         UNION *res;
480         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
481 };
482
483 static int any_set_entry(void **entry, void *user)
484 {
485         S(UNION,any_set_data) *data = user;
486         PW *pw = *entry;
487
488         pw = FN(PW,copy)(pw);
489         pw = data->fn(pw, isl_set_copy(data->set));
490
491         if (DEFAULT_IS_ZERO) {
492                 int empty;
493
494                 empty = FN(PW,IS_ZERO)(pw);
495                 if (empty < 0) {
496                         FN(PW,free)(pw);
497                         return -1;
498                 }
499                 if (empty) {
500                         FN(PW,free)(pw);
501                         return 0;
502                 }
503         }
504
505         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
506
507         return 0;
508 }
509
510 /* Update each element of "u" by calling "fn" on the element and "set".
511  */
512 static __isl_give UNION *any_set_op(__isl_take UNION *u,
513         __isl_take isl_set *set,
514         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
515 {
516         S(UNION,any_set_data) data = { NULL, NULL, fn };
517
518         u = FN(UNION,align_params)(u, isl_set_get_space(set));
519         set = isl_set_align_params(set, FN(UNION,get_space)(u));
520
521         if (!u || !set)
522                 goto error;
523
524         data.set = set;
525 #ifdef HAS_TYPE
526         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
527 #else
528         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
529 #endif
530         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
531                                    &any_set_entry, &data) < 0)
532                 goto error;
533
534         FN(UNION,free)(u);
535         isl_set_free(set);
536         return data.res;
537 error:
538         FN(UNION,free)(u);
539         isl_set_free(set);
540         FN(UNION,free)(data.res);
541         return NULL;
542 }
543
544 /* Intersect the domain of "u" with the parameter domain "context".
545  */
546 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
547         __isl_take isl_set *set)
548 {
549         return any_set_op(u, set, &FN(PW,intersect_params));
550 }
551
552 /* Compute the gist of the domain of "u" with respect to
553  * the parameter domain "context".
554  */
555 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
556         __isl_take isl_set *set)
557 {
558         return any_set_op(u, set, &FN(PW,gist_params));
559 }
560
561 S(UNION,match_domain_data) {
562         isl_union_set *uset;
563         UNION *res;
564         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
565 };
566
567 static int set_has_dim(const void *entry, const void *val)
568 {
569         isl_set *set = (isl_set *)entry;
570         isl_space *dim = (isl_space *)val;
571
572         return isl_space_is_equal(set->dim, dim);
573 }
574
575 /* Find the set in data->uset that live in the same space as the domain
576  * of *entry, apply data->fn to *entry and this set (if any), and add
577  * the result to data->res.
578  */
579 static int match_domain_entry(void **entry, void *user)
580 {
581         S(UNION,match_domain_data) *data = user;
582         uint32_t hash;
583         struct isl_hash_table_entry *entry2;
584         PW *pw = *entry;
585         isl_space *space;
586
587         space = FN(PW,get_domain_space)(pw);
588         hash = isl_space_get_hash(space);
589         entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
590                                      hash, &set_has_dim, space, 0);
591         isl_space_free(space);
592         if (!entry2)
593                 return 0;
594
595         pw = FN(PW,copy)(pw);
596         pw = data->fn(pw, isl_set_copy(entry2->data));
597
598         if (DEFAULT_IS_ZERO) {
599                 int empty;
600
601                 empty = FN(PW,IS_ZERO)(pw);
602                 if (empty < 0) {
603                         FN(PW,free)(pw);
604                         return -1;
605                 }
606                 if (empty) {
607                         FN(PW,free)(pw);
608                         return 0;
609                 }
610         }
611
612         data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
613
614         return 0;
615 }
616
617 /* Apply fn to each pair of PW in u and set in uset such that
618  * the set lives in the same space as the domain of PW
619  * and collect the results.
620  */
621 static __isl_give UNION *match_domain_op(__isl_take UNION *u,
622         __isl_take isl_union_set *uset,
623         __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
624 {
625         S(UNION,match_domain_data) data = { NULL, NULL, fn };
626
627         u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
628         uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
629
630         if (!u || !uset)
631                 goto error;
632
633         data.uset = uset;
634 #ifdef HAS_TYPE
635         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
636 #else
637         data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
638 #endif
639         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
640                                    &match_domain_entry, &data) < 0)
641                 goto error;
642
643         FN(UNION,free)(u);
644         isl_union_set_free(uset);
645         return data.res;
646 error:
647         FN(UNION,free)(u);
648         isl_union_set_free(uset);
649         FN(UNION,free)(data.res);
650         return NULL;
651 }
652
653 /* Intersect the domain of "u" with "uset".
654  * If "uset" is a parameters domain, then intersect the parameter
655  * domain of "u" with this set.
656  */
657 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
658         __isl_take isl_union_set *uset)
659 {
660         if (isl_union_set_is_params(uset))
661                 return FN(UNION,intersect_params)(u,
662                                                 isl_set_from_union_set(uset));
663         return match_domain_op(u, uset, &FN(PW,intersect_domain));
664 }
665
666 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
667         __isl_take isl_union_set *uset)
668 {
669         if (isl_union_set_is_params(uset))
670                 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
671         return match_domain_op(u, uset, &FN(PW,gist));
672 }
673
674 #ifndef NO_EVAL
675 __isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
676         __isl_take isl_point *pnt)
677 {
678         uint32_t hash;
679         struct isl_hash_table_entry *entry;
680         isl_space *space;
681         isl_qpolynomial *qp;
682
683         if (!u || !pnt)
684                 goto error;
685
686         space = isl_space_copy(pnt->dim);
687         space = isl_space_from_domain(space);
688         space = isl_space_add_dims(space, isl_dim_out, 1);
689         if (!space)
690                 goto error;
691         hash = isl_space_get_hash(space);
692         entry = isl_hash_table_find(u->dim->ctx, &u->table,
693                                     hash, &has_dim, space, 0);
694         isl_space_free(space);
695         if (!entry) {
696                 qp = isl_qpolynomial_zero_on_domain(isl_space_copy(pnt->dim));
697                 isl_point_free(pnt);
698         } else {
699                 qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
700         }
701         FN(UNION,free)(u);
702         return qp;
703 error:
704         FN(UNION,free)(u);
705         isl_point_free(pnt);
706         return NULL;
707 }
708 #endif
709
710 static int coalesce_entry(void **entry, void *user)
711 {
712         PW **pw = (PW **)entry;
713
714         *pw = FN(PW,coalesce)(*pw);
715         if (!*pw)
716                 return -1;
717
718         return 0;
719 }
720
721 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
722 {
723         if (!u)
724                 return NULL;
725
726         if (isl_hash_table_foreach(u->dim->ctx, &u->table,
727                                    &coalesce_entry, NULL) < 0)
728                 goto error;
729
730         return u;
731 error:
732         FN(UNION,free)(u);
733         return NULL;
734 }
735
736 static int domain(__isl_take PART *part, void *user)
737 {
738         isl_union_set **uset = (isl_union_set **)user;
739
740         *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
741
742         return 0;
743 }
744
745 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
746 {
747         isl_union_set *uset;
748
749         uset = isl_union_set_empty(FN(UNION,get_space)(u));
750         if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
751                 goto error;
752
753         FN(UNION,free)(u);
754         
755         return uset;
756 error:
757         isl_union_set_free(uset);
758         FN(UNION,free)(u);
759         return NULL;
760 }
761
762 static int mul_isl_int(void **entry, void *user)
763 {
764         PW **pw = (PW **)entry;
765         isl_int *v = user;
766
767         *pw = FN(PW,mul_isl_int)(*pw, *v);
768         if (!*pw)
769                 return -1;
770
771         return 0;
772 }
773
774 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
775 {
776         if (isl_int_is_one(v))
777                 return u;
778
779         if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
780                 UNION *zero;
781                 isl_space *dim = FN(UNION,get_space)(u);
782 #ifdef HAS_TYPE
783                 zero = FN(UNION,ZERO)(dim, u->type);
784 #else
785                 zero = FN(UNION,ZERO)(dim);
786 #endif
787                 FN(UNION,free)(u);
788                 return zero;
789         }
790
791         u = FN(UNION,cow)(u);
792         if (!u)
793                 return NULL;
794
795 #ifdef HAS_TYPE
796         if (isl_int_is_neg(v))
797                 u->type = isl_fold_type_negate(u->type);
798 #endif
799         if (isl_hash_table_foreach(u->dim->ctx, &u->table, &mul_isl_int, v) < 0)
800                 goto error;
801
802         return u;
803 error:
804         FN(UNION,free)(u);
805         return NULL;
806 }
807
808 /* Multiply *entry by the isl_val "user".
809  *
810  * Return 0 on success and -1 on error.
811  */
812 static int scale_val(void **entry, void *user)
813 {
814         PW **pw = (PW **)entry;
815         isl_val *v = user;
816
817         *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
818         if (!*pw)
819                 return -1;
820
821         return 0;
822 }
823
824 /* Multiply "u" by "v" and return the result.
825  */
826 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
827         __isl_take isl_val *v)
828 {
829         if (!u || !v)
830                 goto error;
831         if (isl_val_is_one(v)) {
832                 isl_val_free(v);
833                 return u;
834         }
835
836         if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
837                 UNION *zero;
838                 isl_space *space = FN(UNION,get_space)(u);
839 #ifdef HAS_TYPE
840                 zero = FN(UNION,ZERO)(space, u->type);
841 #else
842                 zero = FN(UNION,ZERO)(space);
843 #endif
844                 FN(UNION,free)(u);
845                 isl_val_free(v);
846                 return zero;
847         }
848
849         if (!isl_val_is_rat(v))
850                 isl_die(isl_val_get_ctx(v), isl_error_invalid,
851                         "expecting rational factor", goto error);
852
853         u = FN(UNION,cow)(u);
854         if (!u)
855                 return NULL;
856
857 #ifdef HAS_TYPE
858         if (isl_val_is_neg(v))
859                 u->type = isl_fold_type_negate(u->type);
860 #endif
861         if (isl_hash_table_foreach(u->dim->ctx, &u->table, &scale_val, v) < 0)
862                 goto error;
863
864         isl_val_free(v);
865         return u;
866 error:
867         isl_val_free(v);
868         FN(UNION,free)(u);
869         return NULL;
870 }
871
872 S(UNION,plain_is_equal_data)
873 {
874         UNION *u2;
875         int is_equal;
876 };
877
878 static int plain_is_equal_entry(void **entry, void *user)
879 {
880         S(UNION,plain_is_equal_data) *data = user;
881         uint32_t hash;
882         struct isl_hash_table_entry *entry2;
883         PW *pw = *entry;
884
885         hash = isl_space_get_hash(pw->dim);
886         entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
887                                      hash, &has_dim, pw->dim, 0);
888         if (!entry2) {
889                 data->is_equal = 0;
890                 return -1;
891         }
892
893         data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
894         if (data->is_equal < 0 || !data->is_equal)
895                 return -1;
896
897         return 0;
898 }
899
900 int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
901 {
902         S(UNION,plain_is_equal_data) data = { NULL, 1 };
903
904         if (!u1 || !u2)
905                 return -1;
906         if (u1 == u2)
907                 return 1;
908         if (u1->table.n != u2->table.n)
909                 return 0;
910
911         u1 = FN(UNION,copy)(u1);
912         u2 = FN(UNION,copy)(u2);
913         u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
914         u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
915         if (!u1 || !u2)
916                 goto error;
917
918         data.u2 = u2;
919         if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
920                                    &plain_is_equal_entry, &data) < 0 &&
921             data.is_equal)
922                 goto error;
923
924         FN(UNION,free)(u1);
925         FN(UNION,free)(u2);
926
927         return data.is_equal;
928 error:
929         FN(UNION,free)(u1);
930         FN(UNION,free)(u2);
931         return -1;
932 }