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
16struct 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
28isl_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
41static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
42	enum isl_fold type, int size)
43#else
44static __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;
66error:
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
93S(UNION,foreach_data)
94{
95	int (*fn)(__isl_take PART *part, void *user);
96	void *user;
97};
98
99static 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
107int 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
119static 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);
147error:
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;
194error:
195	FN(PART,free)(part);
196	FN(UNION,free)(u);
197	return NULL;
198}
199
200static 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;
224error:
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
240static int free_u_entry(void **entry, void *user)
241{
242	PART *part = *entry;
243	FN(PART,free)(part);
244	return 0;
245}
246
247void *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
262S(UNION,align) {
263	isl_reordering *exp;
264	UNION *res;
265};
266
267#ifdef ALIGN_DOMAIN
268static 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
282static 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	model = isl_space_params(model);
311	data.exp = isl_parameter_alignment_reordering(u->dim, model);
312	if (!data.exp)
313		goto error;
314
315#ifdef HAS_TYPE
316	data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim),
317						u->type, u->table.n);
318#else
319	data.res = FN(UNION,alloc)(isl_space_copy(data.exp->dim), u->table.n);
320#endif
321	if (FN(FN(UNION,foreach),PARTS)(u, &align_entry, &data) < 0)
322		goto error;
323
324	isl_reordering_free(data.exp);
325	FN(UNION,free)(u);
326	isl_space_free(model);
327	return data.res;
328error:
329	isl_reordering_free(data.exp);
330	FN(UNION,free)(u);
331	FN(UNION,free)(data.res);
332	isl_space_free(model);
333	return NULL;
334}
335
336__isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
337{
338	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
339	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
340
341	u1 = FN(UNION,cow)(u1);
342
343	if (!u1 || !u2)
344		goto error;
345
346	if (FN(FN(UNION,foreach),PARTS)(u2, &add_part, &u1) < 0)
347		goto error;
348
349	FN(UNION,free)(u2);
350
351	return u1;
352error:
353	FN(UNION,free)(u1);
354	FN(UNION,free)(u2);
355	return NULL;
356}
357
358__isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
359{
360	isl_space *dim;
361	UNION *u;
362
363	if (!part)
364		return NULL;
365
366	dim = FN(PART,get_space)(part);
367	dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
368	dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
369#ifdef HAS_TYPE
370	u = FN(UNION,ZERO)(dim, part->type);
371#else
372	u = FN(UNION,ZERO)(dim);
373#endif
374	u = FN(FN(UNION,add),PARTS)(u, part);
375
376	return u;
377}
378
379S(UNION,match_bin_data) {
380	UNION *u2;
381	UNION *res;
382	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
383};
384
385/* Check if data->u2 has an element living in the same space as *entry.
386 * If so, call data->fn on the two elements and add the result to
387 * data->res.
388 */
389static int match_bin_entry(void **entry, void *user)
390{
391	S(UNION,match_bin_data) *data = user;
392	uint32_t hash;
393	struct isl_hash_table_entry *entry2;
394	isl_space *space;
395	PART *part = *entry;
396
397	space = FN(PART,get_space)(part);
398	hash = isl_space_get_hash(space);
399	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
400				     hash, &has_dim, space, 0);
401	isl_space_free(space);
402	if (!entry2)
403		return 0;
404
405	part = FN(PART, copy)(part);
406	part = data->fn(part, FN(PART, copy)(entry2->data));
407
408	if (DEFAULT_IS_ZERO) {
409		int empty;
410
411		empty = FN(PART,IS_ZERO)(part);
412		if (empty < 0) {
413			FN(PART,free)(part);
414			return -1;
415		}
416		if (empty) {
417			FN(PART,free)(part);
418			return 0;
419		}
420	}
421
422	data->res = FN(FN(UNION,add),PARTS)(data->res, part);
423
424	return 0;
425}
426
427/* This function is currently only used from isl_polynomial.c
428 * and not from isl_fold.c.
429 */
430static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
431	__isl_take UNION *u2,
432	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
433	__attribute__ ((unused));
434/* For each pair of elements in "u1" and "u2" living in the same space,
435 * call "fn" and collect the results.
436 */
437static __isl_give UNION *match_bin_op(__isl_take UNION *u1,
438	__isl_take UNION *u2,
439	__isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
440{
441	S(UNION,match_bin_data) data = { NULL, NULL, fn };
442
443	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
444	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
445
446	if (!u1 || !u2)
447		goto error;
448
449	data.u2 = u2;
450#ifdef HAS_TYPE
451	data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->type, u1->table.n);
452#else
453	data.res = FN(UNION,alloc)(isl_space_copy(u1->dim), u1->table.n);
454#endif
455	if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
456				    &match_bin_entry, &data) < 0)
457		goto error;
458
459	FN(UNION,free)(u1);
460	FN(UNION,free)(u2);
461	return data.res;
462error:
463	FN(UNION,free)(u1);
464	FN(UNION,free)(u2);
465	FN(UNION,free)(data.res);
466	return NULL;
467}
468
469#ifndef NO_SUB
470/* Subtract "u2" from "u1" and return the result.
471 */
472__isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
473{
474	return match_bin_op(u1, u2, &FN(PART,sub));
475}
476#endif
477
478S(UNION,any_set_data) {
479	isl_set *set;
480	UNION *res;
481	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
482};
483
484static int any_set_entry(void **entry, void *user)
485{
486	S(UNION,any_set_data) *data = user;
487	PW *pw = *entry;
488
489	pw = FN(PW,copy)(pw);
490	pw = data->fn(pw, isl_set_copy(data->set));
491
492	if (DEFAULT_IS_ZERO) {
493		int empty;
494
495		empty = FN(PW,IS_ZERO)(pw);
496		if (empty < 0) {
497			FN(PW,free)(pw);
498			return -1;
499		}
500		if (empty) {
501			FN(PW,free)(pw);
502			return 0;
503		}
504	}
505
506	data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
507
508	return 0;
509}
510
511/* Update each element of "u" by calling "fn" on the element and "set".
512 */
513static __isl_give UNION *any_set_op(__isl_take UNION *u,
514	__isl_take isl_set *set,
515	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
516{
517	S(UNION,any_set_data) data = { NULL, NULL, fn };
518
519	u = FN(UNION,align_params)(u, isl_set_get_space(set));
520	set = isl_set_align_params(set, FN(UNION,get_space)(u));
521
522	if (!u || !set)
523		goto error;
524
525	data.set = set;
526#ifdef HAS_TYPE
527	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
528#else
529	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
530#endif
531	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
532				   &any_set_entry, &data) < 0)
533		goto error;
534
535	FN(UNION,free)(u);
536	isl_set_free(set);
537	return data.res;
538error:
539	FN(UNION,free)(u);
540	isl_set_free(set);
541	FN(UNION,free)(data.res);
542	return NULL;
543}
544
545/* Intersect the domain of "u" with the parameter domain "context".
546 */
547__isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
548	__isl_take isl_set *set)
549{
550	return any_set_op(u, set, &FN(PW,intersect_params));
551}
552
553/* Compute the gist of the domain of "u" with respect to
554 * the parameter domain "context".
555 */
556__isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
557	__isl_take isl_set *set)
558{
559	return any_set_op(u, set, &FN(PW,gist_params));
560}
561
562S(UNION,match_domain_data) {
563	isl_union_set *uset;
564	UNION *res;
565	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
566};
567
568static int set_has_dim(const void *entry, const void *val)
569{
570	isl_set *set = (isl_set *)entry;
571	isl_space *dim = (isl_space *)val;
572
573	return isl_space_is_equal(set->dim, dim);
574}
575
576/* Find the set in data->uset that live in the same space as the domain
577 * of *entry, apply data->fn to *entry and this set (if any), and add
578 * the result to data->res.
579 */
580static int match_domain_entry(void **entry, void *user)
581{
582	S(UNION,match_domain_data) *data = user;
583	uint32_t hash;
584	struct isl_hash_table_entry *entry2;
585	PW *pw = *entry;
586	isl_space *space;
587
588	space = FN(PW,get_domain_space)(pw);
589	hash = isl_space_get_hash(space);
590	entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
591				     hash, &set_has_dim, space, 0);
592	isl_space_free(space);
593	if (!entry2)
594		return 0;
595
596	pw = FN(PW,copy)(pw);
597	pw = data->fn(pw, isl_set_copy(entry2->data));
598
599	if (DEFAULT_IS_ZERO) {
600		int empty;
601
602		empty = FN(PW,IS_ZERO)(pw);
603		if (empty < 0) {
604			FN(PW,free)(pw);
605			return -1;
606		}
607		if (empty) {
608			FN(PW,free)(pw);
609			return 0;
610		}
611	}
612
613	data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
614
615	return 0;
616}
617
618/* Apply fn to each pair of PW in u and set in uset such that
619 * the set lives in the same space as the domain of PW
620 * and collect the results.
621 */
622static __isl_give UNION *match_domain_op(__isl_take UNION *u,
623	__isl_take isl_union_set *uset,
624	__isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
625{
626	S(UNION,match_domain_data) data = { NULL, NULL, fn };
627
628	u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
629	uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
630
631	if (!u || !uset)
632		goto error;
633
634	data.uset = uset;
635#ifdef HAS_TYPE
636	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->type, u->table.n);
637#else
638	data.res = FN(UNION,alloc)(isl_space_copy(u->dim), u->table.n);
639#endif
640	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
641				   &match_domain_entry, &data) < 0)
642		goto error;
643
644	FN(UNION,free)(u);
645	isl_union_set_free(uset);
646	return data.res;
647error:
648	FN(UNION,free)(u);
649	isl_union_set_free(uset);
650	FN(UNION,free)(data.res);
651	return NULL;
652}
653
654/* Intersect the domain of "u" with "uset".
655 * If "uset" is a parameters domain, then intersect the parameter
656 * domain of "u" with this set.
657 */
658__isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
659	__isl_take isl_union_set *uset)
660{
661	if (isl_union_set_is_params(uset))
662		return FN(UNION,intersect_params)(u,
663						isl_set_from_union_set(uset));
664	return match_domain_op(u, uset, &FN(PW,intersect_domain));
665}
666
667__isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
668	__isl_take isl_union_set *uset)
669{
670	if (isl_union_set_is_params(uset))
671		return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
672	return match_domain_op(u, uset, &FN(PW,gist));
673}
674
675#ifndef NO_EVAL
676__isl_give isl_qpolynomial *FN(UNION,eval)(__isl_take UNION *u,
677	__isl_take isl_point *pnt)
678{
679	uint32_t hash;
680	struct isl_hash_table_entry *entry;
681	isl_space *space;
682	isl_qpolynomial *qp;
683
684	if (!u || !pnt)
685		goto error;
686
687	space = isl_space_copy(pnt->dim);
688	space = isl_space_from_domain(space);
689	space = isl_space_add_dims(space, isl_dim_out, 1);
690	if (!space)
691		goto error;
692	hash = isl_space_get_hash(space);
693	entry = isl_hash_table_find(u->dim->ctx, &u->table,
694				    hash, &has_dim, space, 0);
695	isl_space_free(space);
696	if (!entry) {
697		qp = isl_qpolynomial_zero_on_domain(isl_space_copy(pnt->dim));
698		isl_point_free(pnt);
699	} else {
700		qp = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
701	}
702	FN(UNION,free)(u);
703	return qp;
704error:
705	FN(UNION,free)(u);
706	isl_point_free(pnt);
707	return NULL;
708}
709#endif
710
711static int coalesce_entry(void **entry, void *user)
712{
713	PW **pw = (PW **)entry;
714
715	*pw = FN(PW,coalesce)(*pw);
716	if (!*pw)
717		return -1;
718
719	return 0;
720}
721
722__isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
723{
724	if (!u)
725		return NULL;
726
727	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
728				   &coalesce_entry, NULL) < 0)
729		goto error;
730
731	return u;
732error:
733	FN(UNION,free)(u);
734	return NULL;
735}
736
737static int domain(__isl_take PART *part, void *user)
738{
739	isl_union_set **uset = (isl_union_set **)user;
740
741	*uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
742
743	return 0;
744}
745
746__isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
747{
748	isl_union_set *uset;
749
750	uset = isl_union_set_empty(FN(UNION,get_space)(u));
751	if (FN(FN(UNION,foreach),PARTS)(u, &domain, &uset) < 0)
752		goto error;
753
754	FN(UNION,free)(u);
755
756	return uset;
757error:
758	isl_union_set_free(uset);
759	FN(UNION,free)(u);
760	return NULL;
761}
762
763static int mul_isl_int(void **entry, void *user)
764{
765	PW **pw = (PW **)entry;
766	isl_int *v = user;
767
768	*pw = FN(PW,mul_isl_int)(*pw, *v);
769	if (!*pw)
770		return -1;
771
772	return 0;
773}
774
775__isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
776{
777	if (isl_int_is_one(v))
778		return u;
779
780	if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
781		UNION *zero;
782		isl_space *dim = FN(UNION,get_space)(u);
783#ifdef HAS_TYPE
784		zero = FN(UNION,ZERO)(dim, u->type);
785#else
786		zero = FN(UNION,ZERO)(dim);
787#endif
788		FN(UNION,free)(u);
789		return zero;
790	}
791
792	u = FN(UNION,cow)(u);
793	if (!u)
794		return NULL;
795
796#ifdef HAS_TYPE
797	if (isl_int_is_neg(v))
798		u->type = isl_fold_type_negate(u->type);
799#endif
800	if (isl_hash_table_foreach(u->dim->ctx, &u->table,
801				    &mul_isl_int, &v) < 0)
802		goto error;
803
804	return u;
805error:
806	FN(UNION,free)(u);
807	return NULL;
808}
809
810/* Multiply *entry by the isl_val "user".
811 *
812 * Return 0 on success and -1 on error.
813 */
814static int scale_val(void **entry, void *user)
815{
816	PW **pw = (PW **)entry;
817	isl_val *v = user;
818
819	*pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
820	if (!*pw)
821		return -1;
822
823	return 0;
824}
825
826/* Multiply "u" by "v" and return the result.
827 */
828__isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
829	__isl_take isl_val *v)
830{
831	if (!u || !v)
832		goto error;
833	if (isl_val_is_one(v)) {
834		isl_val_free(v);
835		return u;
836	}
837
838	if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
839		UNION *zero;
840		isl_space *space = FN(UNION,get_space)(u);
841#ifdef HAS_TYPE
842		zero = FN(UNION,ZERO)(space, u->type);
843#else
844		zero = FN(UNION,ZERO)(space);
845#endif
846		FN(UNION,free)(u);
847		isl_val_free(v);
848		return zero;
849	}
850
851	if (!isl_val_is_rat(v))
852		isl_die(isl_val_get_ctx(v), isl_error_invalid,
853			"expecting rational factor", goto error);
854
855	u = FN(UNION,cow)(u);
856	if (!u)
857		return NULL;
858
859#ifdef HAS_TYPE
860	if (isl_val_is_neg(v))
861		u->type = isl_fold_type_negate(u->type);
862#endif
863	if (isl_hash_table_foreach(u->dim->ctx, &u->table, &scale_val, v) < 0)
864		goto error;
865
866	isl_val_free(v);
867	return u;
868error:
869	isl_val_free(v);
870	FN(UNION,free)(u);
871	return NULL;
872}
873
874S(UNION,plain_is_equal_data)
875{
876	UNION *u2;
877	int is_equal;
878};
879
880static int plain_is_equal_entry(void **entry, void *user)
881{
882	S(UNION,plain_is_equal_data) *data = user;
883	uint32_t hash;
884	struct isl_hash_table_entry *entry2;
885	PW *pw = *entry;
886
887	hash = isl_space_get_hash(pw->dim);
888	entry2 = isl_hash_table_find(data->u2->dim->ctx, &data->u2->table,
889				     hash, &has_dim, pw->dim, 0);
890	if (!entry2) {
891		data->is_equal = 0;
892		return -1;
893	}
894
895	data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
896	if (data->is_equal < 0 || !data->is_equal)
897		return -1;
898
899	return 0;
900}
901
902int FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
903{
904	S(UNION,plain_is_equal_data) data = { NULL, 1 };
905
906	if (!u1 || !u2)
907		return -1;
908	if (u1 == u2)
909		return 1;
910	if (u1->table.n != u2->table.n)
911		return 0;
912
913	u1 = FN(UNION,copy)(u1);
914	u2 = FN(UNION,copy)(u2);
915	u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
916	u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
917	if (!u1 || !u2)
918		goto error;
919
920	data.u2 = u2;
921	if (isl_hash_table_foreach(u1->dim->ctx, &u1->table,
922				   &plain_is_equal_entry, &data) < 0 &&
923	    data.is_equal)
924		goto error;
925
926	FN(UNION,free)(u1);
927	FN(UNION,free)(u2);
928
929	return data.is_equal;
930error:
931	FN(UNION,free)(u1);
932	FN(UNION,free)(u2);
933	return -1;
934}
935