1/*
2 * Copyright 2011      Sven Verdoolaege
3 * Copyright 2012      Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France
9 */
10
11#include <isl_space_private.h>
12#include <isl/set.h>
13#include <isl_reordering.h>
14
15#define xCAT(A,B) A ## B
16#define CAT(A,B) xCAT(A,B)
17#undef EL
18#define EL CAT(isl_,BASE)
19#define xFN(TYPE,NAME) TYPE ## _ ## NAME
20#define FN(TYPE,NAME) xFN(TYPE,NAME)
21#define xMULTI(BASE) isl_multi_ ## BASE
22#define MULTI(BASE) xMULTI(BASE)
23#define MULTI_NAME(BASE) "isl_multi_" #BASE
24#define xLIST(EL) EL ## _list
25#define LIST(EL) xLIST(EL)
26
27isl_ctx *FN(MULTI(BASE),get_ctx)(__isl_keep MULTI(BASE) *multi)
28{
29	return multi ? isl_space_get_ctx(multi->space) : NULL;
30}
31
32__isl_give isl_space *FN(MULTI(BASE),get_space)(__isl_keep MULTI(BASE) *multi)
33{
34	return multi ? isl_space_copy(multi->space) : NULL;
35}
36
37__isl_give isl_space *FN(MULTI(BASE),get_domain_space)(
38	__isl_keep MULTI(BASE) *multi)
39{
40	return multi ? isl_space_domain(isl_space_copy(multi->space)) : NULL;
41}
42
43__isl_give MULTI(BASE) *FN(MULTI(BASE),alloc)(__isl_take isl_space *space)
44{
45	isl_ctx *ctx;
46	int n;
47	MULTI(BASE) *multi;
48
49	if (!space)
50		return NULL;
51
52	ctx = isl_space_get_ctx(space);
53	n = isl_space_dim(space, isl_dim_out);
54	multi = isl_calloc(ctx, MULTI(BASE),
55			 sizeof(MULTI(BASE)) + (n - 1) * sizeof(struct EL *));
56	if (!multi)
57		goto error;
58
59	multi->space = space;
60	multi->n = n;
61	multi->ref = 1;
62	return multi;
63error:
64	isl_space_free(space);
65	return NULL;
66}
67
68__isl_give MULTI(BASE) *FN(MULTI(BASE),dup)(__isl_keep MULTI(BASE) *multi)
69{
70	int i;
71	MULTI(BASE) *dup;
72
73	if (!multi)
74		return NULL;
75
76	dup = FN(MULTI(BASE),alloc)(isl_space_copy(multi->space));
77	if (!dup)
78		return NULL;
79
80	for (i = 0; i < multi->n; ++i)
81		dup = FN(FN(MULTI(BASE),set),BASE)(dup, i,
82						    FN(EL,copy)(multi->p[i]));
83
84	return dup;
85}
86
87__isl_give MULTI(BASE) *FN(MULTI(BASE),cow)(__isl_take MULTI(BASE) *multi)
88{
89	if (!multi)
90		return NULL;
91
92	if (multi->ref == 1)
93		return multi;
94
95	multi->ref--;
96	return FN(MULTI(BASE),dup)(multi);
97}
98
99__isl_give MULTI(BASE) *FN(MULTI(BASE),copy)(__isl_keep MULTI(BASE) *multi)
100{
101	if (!multi)
102		return NULL;
103
104	multi->ref++;
105	return multi;
106}
107
108void *FN(MULTI(BASE),free)(__isl_take MULTI(BASE) *multi)
109{
110	int i;
111
112	if (!multi)
113		return NULL;
114
115	if (--multi->ref > 0)
116		return NULL;
117
118	isl_space_free(multi->space);
119	for (i = 0; i < multi->n; ++i)
120		FN(EL,free)(multi->p[i]);
121	free(multi);
122
123	return NULL;
124}
125
126__isl_give MULTI(BASE) *FN(MULTI(BASE),insert_dims)(
127	__isl_take MULTI(BASE) *multi,
128	enum isl_dim_type type, unsigned first, unsigned n)
129{
130	int i;
131
132	if (!multi)
133		return NULL;
134	if (type == isl_dim_out)
135		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
136			"cannot insert output/set dimensions",
137			return FN(MULTI(BASE),free)(multi));
138	if (n == 0 && !isl_space_is_named_or_nested(multi->space, type))
139		return multi;
140
141	multi = FN(MULTI(BASE),cow)(multi);
142	if (!multi)
143		return NULL;
144
145	multi->space = isl_space_insert_dims(multi->space, type, first, n);
146	if (!multi->space)
147		return FN(MULTI(BASE),free)(multi);
148
149	for (i = 0; i < multi->n; ++i) {
150		multi->p[i] = FN(EL,insert_dims)(multi->p[i], type, first, n);
151		if (!multi->p[i])
152			return FN(MULTI(BASE),free)(multi);
153	}
154
155	return multi;
156}
157
158__isl_give MULTI(BASE) *FN(MULTI(BASE),add_dims)(__isl_take MULTI(BASE) *multi,
159	enum isl_dim_type type, unsigned n)
160{
161	unsigned pos;
162
163	pos = FN(MULTI(BASE),dim)(multi, type);
164
165	return FN(MULTI(BASE),insert_dims)(multi, type, pos, n);
166}
167
168unsigned FN(MULTI(BASE),dim)(__isl_keep MULTI(BASE) *multi,
169	enum isl_dim_type type)
170{
171	return multi ? isl_space_dim(multi->space, type) : 0;
172}
173
174__isl_give MULTI(BASE) *FN(MULTI(BASE),set_dim_name)(
175	__isl_take MULTI(BASE) *multi,
176	enum isl_dim_type type, unsigned pos, const char *s)
177{
178	int i;
179
180	multi = FN(MULTI(BASE),cow)(multi);
181	if (!multi)
182		return NULL;
183
184	multi->space = isl_space_set_dim_name(multi->space, type, pos, s);
185	if (!multi->space)
186		return FN(MULTI(BASE),free)(multi);
187
188	if (type == isl_dim_out)
189		return multi;
190	for (i = 0; i < multi->n; ++i) {
191		multi->p[i] = FN(EL,set_dim_name)(multi->p[i], type, pos, s);
192		if (!multi->p[i])
193			return FN(MULTI(BASE),free)(multi);
194	}
195
196	return multi;
197}
198
199const char *FN(MULTI(BASE),get_tuple_name)(__isl_keep MULTI(BASE) *multi,
200	enum isl_dim_type type)
201{
202	return multi ? isl_space_get_tuple_name(multi->space, type) : NULL;
203}
204
205__isl_give EL *FN(FN(MULTI(BASE),get),BASE)(__isl_keep MULTI(BASE) *multi,
206	int pos)
207{
208	isl_ctx *ctx;
209
210	if (!multi)
211		return NULL;
212	ctx = FN(MULTI(BASE),get_ctx)(multi);
213	if (pos < 0 || pos >= multi->n)
214		isl_die(ctx, isl_error_invalid,
215			"index out of bounds", return NULL);
216	return FN(EL,copy)(multi->p[pos]);
217}
218
219__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),set),BASE)(
220	__isl_take MULTI(BASE) *multi, int pos, __isl_take EL *el)
221{
222	isl_space *multi_space = NULL;
223	isl_space *el_space = NULL;
224
225	multi = FN(MULTI(BASE),cow)(multi);
226	if (!multi || !el)
227		goto error;
228
229	multi_space = FN(MULTI(BASE),get_space)(multi);
230	if (FN(EL,check_match_domain_space)(el, multi_space) < 0)
231		goto error;
232
233	if (pos < 0 || pos >= multi->n)
234		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
235			"index out of bounds", goto error);
236
237	FN(EL,free)(multi->p[pos]);
238	multi->p[pos] = el;
239
240	isl_space_free(multi_space);
241	isl_space_free(el_space);
242
243	return multi;
244error:
245	FN(MULTI(BASE),free)(multi);
246	FN(EL,free)(el);
247	isl_space_free(multi_space);
248	isl_space_free(el_space);
249	return NULL;
250}
251
252/* Reset the space of "multi".  This function is called from isl_pw_templ.c
253 * and doesn't know if the space of an element object is represented
254 * directly or through its domain.  It therefore passes along both,
255 * which we pass along to the element function since we don't how
256 * that is represented either.
257 */
258__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space_and_domain)(
259	__isl_take MULTI(BASE) *multi, __isl_take isl_space *space,
260	__isl_take isl_space *domain)
261{
262	int i;
263
264	multi = FN(MULTI(BASE),cow)(multi);
265	if (!multi || !space || !domain)
266		goto error;
267
268	for (i = 0; i < multi->n; ++i) {
269		multi->p[i] = FN(EL,reset_domain_space)(multi->p[i],
270				 isl_space_copy(domain));
271		if (!multi->p[i])
272			goto error;
273	}
274	isl_space_free(domain);
275	isl_space_free(multi->space);
276	multi->space = space;
277
278	return multi;
279error:
280	isl_space_free(domain);
281	isl_space_free(space);
282	FN(MULTI(BASE),free)(multi);
283	return NULL;
284}
285
286__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_domain_space)(
287	__isl_take MULTI(BASE) *multi, __isl_take isl_space *domain)
288{
289	isl_space *space;
290
291	space = isl_space_extend_domain_with_range(isl_space_copy(domain),
292						isl_space_copy(multi->space));
293	return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
294}
295
296__isl_give MULTI(BASE) *FN(MULTI(BASE),reset_space)(
297	__isl_take MULTI(BASE) *multi, __isl_take isl_space *space)
298{
299	isl_space *domain;
300
301	domain = isl_space_domain(isl_space_copy(space));
302	return FN(MULTI(BASE),reset_space_and_domain)(multi, space, domain);
303}
304
305__isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_name)(
306	__isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
307	const char *s)
308{
309	isl_space *space;
310
311	multi = FN(MULTI(BASE),cow)(multi);
312	if (!multi)
313		return NULL;
314
315	space = FN(MULTI(BASE),get_space)(multi);
316	space = isl_space_set_tuple_name(space, type, s);
317
318	return FN(MULTI(BASE),reset_space)(multi, space);
319}
320
321__isl_give MULTI(BASE) *FN(MULTI(BASE),set_tuple_id)(
322	__isl_keep MULTI(BASE) *multi, enum isl_dim_type type,
323	__isl_take isl_id *id)
324{
325	isl_space *space;
326
327	multi = FN(MULTI(BASE),cow)(multi);
328	if (!multi)
329		return isl_id_free(id);
330
331	space = FN(MULTI(BASE),get_space)(multi);
332	space = isl_space_set_tuple_id(space, type, id);
333
334	return FN(MULTI(BASE),reset_space)(multi, space);
335}
336
337__isl_give MULTI(BASE) *FN(MULTI(BASE),realign_domain)(
338	__isl_take MULTI(BASE) *multi, __isl_take isl_reordering *exp)
339{
340	int i;
341
342	multi = FN(MULTI(BASE),cow)(multi);
343	if (!multi || !exp)
344		goto error;
345
346	for (i = 0; i < multi->n; ++i) {
347		multi->p[i] = FN(EL,realign_domain)(multi->p[i],
348						isl_reordering_copy(exp));
349		if (!multi->p[i])
350			goto error;
351	}
352
353	multi = FN(MULTI(BASE),reset_domain_space)(multi,
354						    isl_space_copy(exp->dim));
355
356	isl_reordering_free(exp);
357	return multi;
358error:
359	isl_reordering_free(exp);
360	FN(MULTI(BASE),free)(multi);
361	return NULL;
362}
363
364/* Align the parameters of "multi" to those of "model".
365 */
366__isl_give MULTI(BASE) *FN(MULTI(BASE),align_params)(
367	__isl_take MULTI(BASE) *multi, __isl_take isl_space *model)
368{
369	isl_ctx *ctx;
370
371	if (!multi || !model)
372		goto error;
373
374	ctx = isl_space_get_ctx(model);
375	if (!isl_space_has_named_params(model))
376		isl_die(ctx, isl_error_invalid,
377			"model has unnamed parameters", goto error);
378	if (!isl_space_has_named_params(multi->space))
379		isl_die(ctx, isl_error_invalid,
380			"input has unnamed parameters", goto error);
381	if (!isl_space_match(multi->space, isl_dim_param,
382			     model, isl_dim_param)) {
383		isl_reordering *exp;
384
385		model = isl_space_params(model);
386		exp = isl_parameter_alignment_reordering(multi->space, model);
387		exp = isl_reordering_extend_space(exp,
388				    FN(MULTI(BASE),get_domain_space)(multi));
389		multi = FN(MULTI(BASE),realign_domain)(multi, exp);
390	}
391
392	isl_space_free(model);
393	return multi;
394error:
395	isl_space_free(model);
396	FN(MULTI(BASE),free)(multi);
397	return NULL;
398}
399
400#ifndef NO_GIST
401static __isl_give MULTI(BASE) *FN(MULTI(BASE),align_params_multi_set_and)(
402	__isl_take MULTI(BASE) *multi, __isl_take isl_set *set,
403	__isl_give MULTI(BASE) *(*fn)(__isl_take MULTI(BASE) *multi,
404					__isl_take isl_set *set))
405{
406	isl_ctx *ctx;
407
408	if (!multi || !set)
409		goto error;
410	if (isl_space_match(multi->space, isl_dim_param,
411			    set->dim, isl_dim_param))
412		return fn(multi, set);
413	ctx = FN(MULTI(BASE),get_ctx)(multi);
414	if (!isl_space_has_named_params(multi->space) ||
415	    !isl_space_has_named_params(set->dim))
416		isl_die(ctx, isl_error_invalid,
417			"unaligned unnamed parameters", goto error);
418	multi = FN(MULTI(BASE),align_params)(multi, isl_set_get_space(set));
419	set = isl_set_align_params(set, FN(MULTI(BASE),get_space)(multi));
420	return fn(multi, set);
421error:
422	FN(MULTI(BASE),free)(multi);
423	isl_set_free(set);
424	return NULL;
425}
426
427__isl_give MULTI(BASE) *FN(MULTI(BASE),gist_aligned)(
428	__isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
429{
430	int i;
431
432	multi = FN(MULTI(BASE),cow)(multi);
433	if (!multi || !context)
434		goto error;
435
436	for (i = 0; i < multi->n; ++i) {
437		multi->p[i] = FN(EL,gist)(multi->p[i], isl_set_copy(context));
438		if (!multi->p[i])
439			goto error;
440	}
441
442	isl_set_free(context);
443	return multi;
444error:
445	isl_set_free(context);
446	FN(MULTI(BASE),free)(multi);
447	return NULL;
448}
449
450__isl_give MULTI(BASE) *FN(MULTI(BASE),gist)(__isl_take MULTI(BASE) *multi,
451	__isl_take isl_set *context)
452{
453	return FN(MULTI(BASE),align_params_multi_set_and)(multi, context,
454						&FN(MULTI(BASE),gist_aligned));
455}
456
457__isl_give MULTI(BASE) *FN(MULTI(BASE),gist_params)(
458	__isl_take MULTI(BASE) *multi, __isl_take isl_set *context)
459{
460	isl_space *space = FN(MULTI(BASE),get_domain_space)(multi);
461	isl_set *dom_context = isl_set_universe(space);
462	dom_context = isl_set_intersect_params(dom_context, context);
463	return FN(MULTI(BASE),gist)(multi, dom_context);
464}
465#endif
466
467__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),LIST(BASE))(
468	__isl_take isl_space *space, __isl_take LIST(EL) *list)
469{
470	int i;
471	int n;
472	isl_ctx *ctx;
473	MULTI(BASE) *multi;
474
475	if (!space || !list)
476		goto error;
477
478	ctx = isl_space_get_ctx(space);
479	n = FN(FN(LIST(EL),n),BASE)(list);
480	if (n != isl_space_dim(space, isl_dim_out))
481		isl_die(ctx, isl_error_invalid,
482			"invalid number of elements in list", goto error);
483
484	multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
485	for (i = 0; i < n; ++i) {
486		multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
487					FN(FN(LIST(EL),get),BASE)(list, i));
488	}
489
490	isl_space_free(space);
491	FN(LIST(EL),free)(list);
492	return multi;
493error:
494	isl_space_free(space);
495	FN(LIST(EL),free)(list);
496	return NULL;
497}
498
499#ifndef NO_IDENTITY
500/* Create a multi expression in the given space that maps each
501 * input dimension to the corresponding output dimension.
502 */
503__isl_give MULTI(BASE) *FN(MULTI(BASE),identity)(__isl_take isl_space *space)
504{
505	int i, n;
506	isl_local_space *ls;
507	MULTI(BASE) *multi;
508
509	if (!space)
510		return NULL;
511
512	if (isl_space_is_set(space))
513		isl_die(isl_space_get_ctx(space), isl_error_invalid,
514			"expecting map space", goto error);
515
516	n = isl_space_dim(space, isl_dim_out);
517	if (n != isl_space_dim(space, isl_dim_in))
518		isl_die(isl_space_get_ctx(space), isl_error_invalid,
519			"number of input and output dimensions needs to be "
520			"the same", goto error);
521
522	multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
523
524	if (!n) {
525		isl_space_free(space);
526		return multi;
527	}
528
529	space = isl_space_domain(space);
530	ls = isl_local_space_from_space(space);
531
532	for (i = 0; i < n; ++i) {
533		EL *el;
534		el = FN(EL,var_on_domain)(isl_local_space_copy(ls),
535						isl_dim_set, i);
536		multi = FN(FN(MULTI(BASE),set),BASE)(multi, i, el);
537	}
538
539	isl_local_space_free(ls);
540
541	return multi;
542error:
543	isl_space_free(space);
544	return NULL;
545}
546#endif
547
548/* Construct a multi expression in the given space with value zero in
549 * each of the output dimensions.
550 */
551__isl_give MULTI(BASE) *FN(MULTI(BASE),zero)(__isl_take isl_space *space)
552{
553	int n;
554	MULTI(BASE) *multi;
555
556	if (!space)
557		return NULL;
558
559	n = isl_space_dim(space , isl_dim_out);
560	multi = FN(MULTI(BASE),alloc)(isl_space_copy(space));
561
562	if (!n)
563		isl_space_free(space);
564	else {
565		int i;
566		isl_local_space *ls;
567		EL *el;
568
569		space = isl_space_domain(space);
570		ls = isl_local_space_from_space(space);
571		el = FN(EL,zero_on_domain)(ls);
572
573		for (i = 0; i < n; ++i)
574			multi = FN(FN(MULTI(BASE),set),BASE)(multi, i,
575							    FN(EL,copy)(el));
576
577		FN(EL,free)(el);
578	}
579
580	return multi;
581}
582
583#ifndef NO_FROM_BASE
584__isl_give MULTI(BASE) *FN(FN(MULTI(BASE),from),BASE)(__isl_take EL *el)
585{
586	MULTI(BASE) *multi;
587
588	multi = FN(MULTI(BASE),alloc)(FN(EL,get_space)(el));
589	multi = FN(FN(MULTI(BASE),set),BASE)(multi, 0, el);
590
591	return multi;
592}
593#endif
594
595__isl_give MULTI(BASE) *FN(MULTI(BASE),drop_dims)(
596	__isl_take MULTI(BASE) *multi,
597	enum isl_dim_type type, unsigned first, unsigned n)
598{
599	int i;
600	unsigned dim;
601
602	multi = FN(MULTI(BASE),cow)(multi);
603	if (!multi)
604		return NULL;
605
606	dim = FN(MULTI(BASE),dim)(multi, type);
607	if (first + n > dim || first + n < first)
608		isl_die(FN(MULTI(BASE),get_ctx)(multi), isl_error_invalid,
609			"index out of bounds",
610			return FN(MULTI(BASE),cow)(multi));
611
612	multi->space = isl_space_drop_dims(multi->space, type, first, n);
613	if (!multi->space)
614		return FN(MULTI(BASE),cow)(multi);
615
616	if (type == isl_dim_out) {
617		for (i = 0; i < n; ++i)
618			FN(EL,free)(multi->p[first + i]);
619		for (i = first; i + n < multi->n; ++i)
620			multi->p[i] = multi->p[i + n];
621		multi->n -= n;
622
623		return multi;
624	}
625
626	for (i = 0; i < multi->n; ++i) {
627		multi->p[i] = FN(EL,drop_dims)(multi->p[i], type, first, n);
628		if (!multi->p[i])
629			return FN(MULTI(BASE),cow)(multi);
630	}
631
632	return multi;
633}
634
635/* Given two MULTI(BASE)s A -> B and C -> D,
636 * construct a MULTI(BASE) (A * C) -> (B, D).
637 */
638__isl_give MULTI(BASE) *FN(MULTI(BASE),range_product)(
639	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
640{
641	int i, n1, n2;
642	EL *el;
643	isl_space *space;
644	MULTI(BASE) *res;
645
646	if (!multi1 || !multi2)
647		goto error;
648
649	space = isl_space_range_product(FN(MULTI(BASE),get_space)(multi1),
650					FN(MULTI(BASE),get_space)(multi2));
651	res = FN(MULTI(BASE),alloc)(space);
652
653	n1 = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
654	n2 = FN(MULTI(BASE),dim)(multi2, isl_dim_out);
655
656	for (i = 0; i < n1; ++i) {
657		el = FN(FN(MULTI(BASE),get),BASE)(multi1, i);
658		res = FN(FN(MULTI(BASE),set),BASE)(res, i, el);
659	}
660
661	for (i = 0; i < n2; ++i) {
662		el = FN(FN(MULTI(BASE),get),BASE)(multi2, i);
663		res = FN(FN(MULTI(BASE),set),BASE)(res, n1 + i, el);
664	}
665
666	FN(MULTI(BASE),free)(multi1);
667	FN(MULTI(BASE),free)(multi2);
668	return res;
669error:
670	FN(MULTI(BASE),free)(multi1);
671	FN(MULTI(BASE),free)(multi2);
672	return NULL;
673}
674
675__isl_give MULTI(BASE) *FN(MULTI(BASE),flatten_range)(
676	__isl_take MULTI(BASE) *multi)
677{
678	if (!multi)
679		return NULL;
680
681	if (!multi->space->nested[1])
682		return multi;
683
684	multi = FN(MULTI(BASE),cow)(multi);
685	if (!multi)
686		return NULL;
687
688	multi->space = isl_space_flatten_range(multi->space);
689	if (!multi->space)
690		return FN(MULTI(BASE),free)(multi);
691
692	return multi;
693}
694
695/* Given two MULTI(BASE)s A -> B and C -> D,
696 * construct a MULTI(BASE) (A * C) -> [B -> D].
697 */
698__isl_give MULTI(BASE) *FN(MULTI(BASE),flat_range_product)(
699	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2)
700{
701	MULTI(BASE) *multi;
702
703	multi = FN(MULTI(BASE),range_product)(multi1, multi2);
704	multi = FN(MULTI(BASE),flatten_range)(multi);
705	return multi;
706}
707
708/* Given two multi expressions, "multi1"
709 *
710 *	[A] -> [B1 B2]
711 *
712 * where B2 starts at position "pos", and "multi2"
713 *
714 *	[A] -> [D]
715 *
716 * return the multi expression
717 *
718 *	[A] -> [B1 D B2]
719 */
720__isl_give MULTI(BASE) *FN(MULTI(BASE),range_splice)(
721	__isl_take MULTI(BASE) *multi1, unsigned pos,
722	__isl_take MULTI(BASE) *multi2)
723{
724	MULTI(BASE) *res;
725	unsigned dim;
726
727	if (!multi1 || !multi2)
728		goto error;
729
730	dim = FN(MULTI(BASE),dim)(multi1, isl_dim_out);
731	if (pos > dim)
732		isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
733			"index out of bounds", goto error);
734
735	res = FN(MULTI(BASE),copy)(multi1);
736	res = FN(MULTI(BASE),drop_dims)(res, isl_dim_out, pos, dim - pos);
737	multi1 = FN(MULTI(BASE),drop_dims)(multi1, isl_dim_out, 0, pos);
738
739	res = FN(MULTI(BASE),flat_range_product)(res, multi2);
740	res = FN(MULTI(BASE),flat_range_product)(res, multi1);
741
742	return res;
743error:
744	FN(MULTI(BASE),free)(multi1);
745	FN(MULTI(BASE),free)(multi2);
746	return NULL;
747}
748
749/* Given two multi expressions, "multi1"
750 *
751 *	[A1 A2] -> [B1 B2]
752 *
753 * where A2 starts at position "in_pos" and B2 starts at position "out_pos",
754 * and "multi2"
755 *
756 *	[C] -> [D]
757 *
758 * return the multi expression
759 *
760 *	[A1 C A2] -> [B1 D B2]
761 *
762 * We first insert input dimensions to obtain
763 *
764 *	[A1 C A2] -> [B1 B2]
765 *
766 * and
767 *
768 *	[A1 C A2] -> [D]
769 *
770 * and then apply range_splice.
771 */
772__isl_give MULTI(BASE) *FN(MULTI(BASE),splice)(
773	__isl_take MULTI(BASE) *multi1, unsigned in_pos, unsigned out_pos,
774	__isl_take MULTI(BASE) *multi2)
775{
776	unsigned n_in1;
777	unsigned n_in2;
778
779	if (!multi1 || !multi2)
780		goto error;
781
782	n_in1 = FN(MULTI(BASE),dim)(multi1, isl_dim_in);
783	if (in_pos > n_in1)
784		isl_die(FN(MULTI(BASE),get_ctx)(multi1), isl_error_invalid,
785			"index out of bounds", goto error);
786
787	n_in2 = FN(MULTI(BASE),dim)(multi2, isl_dim_in);
788
789	multi1 = FN(MULTI(BASE),insert_dims)(multi1, isl_dim_in, in_pos, n_in2);
790	multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, n_in2,
791						n_in1 - in_pos);
792	multi2 = FN(MULTI(BASE),insert_dims)(multi2, isl_dim_in, 0, in_pos);
793
794	return FN(MULTI(BASE),range_splice)(multi1, out_pos, multi2);
795error:
796	FN(MULTI(BASE),free)(multi1);
797	FN(MULTI(BASE),free)(multi2);
798	return NULL;
799}
800
801/* This function is currently only used from isl_aff.c
802 */
803static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
804	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
805	__isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
806	__attribute__ ((unused));
807
808/* Pairwise perform "fn" to the elements of "multi1" and "multi2" and
809 * return the result.
810 */
811static __isl_give MULTI(BASE) *FN(MULTI(BASE),bin_op)(
812	__isl_take MULTI(BASE) *multi1, __isl_take MULTI(BASE) *multi2,
813	__isl_give EL *(*fn)(__isl_take EL *, __isl_take EL *))
814{
815	int i;
816	isl_ctx *ctx;
817
818	multi1 = FN(MULTI(BASE),cow)(multi1);
819	if (!multi1 || !multi2)
820		goto error;
821
822	ctx = FN(MULTI(BASE),get_ctx)(multi1);
823	if (!isl_space_is_equal(multi1->space, multi2->space))
824		isl_die(ctx, isl_error_invalid,
825			"spaces don't match", goto error);
826
827	for (i = 0; i < multi1->n; ++i) {
828		multi1->p[i] = fn(multi1->p[i], FN(EL,copy)(multi2->p[i]));
829		if (!multi1->p[i])
830			goto error;
831	}
832
833	FN(MULTI(BASE),free)(multi2);
834	return multi1;
835error:
836	FN(MULTI(BASE),free)(multi1);
837	FN(MULTI(BASE),free)(multi2);
838	return NULL;
839}
840
841/* Multiply the elements of "multi" by "v" and return the result.
842 */
843__isl_give MULTI(BASE) *FN(MULTI(BASE),scale_val)(__isl_take MULTI(BASE) *multi,
844	__isl_take isl_val *v)
845{
846	int i;
847
848	if (!multi || !v)
849		goto error;
850
851	if (isl_val_is_one(v)) {
852		isl_val_free(v);
853		return multi;
854	}
855
856	if (!isl_val_is_rat(v))
857		isl_die(isl_val_get_ctx(v), isl_error_invalid,
858			"expecting rational factor", goto error);
859
860	multi = FN(MULTI(BASE),cow)(multi);
861	if (!multi)
862		return NULL;
863
864	for (i = 0; i < multi->n; ++i) {
865		multi->p[i] = FN(EL,scale_val)(multi->p[i], isl_val_copy(v));
866		if (!multi->p[i])
867			goto error;
868	}
869
870	isl_val_free(v);
871	return multi;
872error:
873	isl_val_free(v);
874	return FN(MULTI(BASE),free)(multi);
875}
876
877/* Multiply the elements of "multi" by the corresponding element of "mv"
878 * and return the result.
879 */
880__isl_give MULTI(BASE) *FN(MULTI(BASE),scale_multi_val)(
881	__isl_take MULTI(BASE) *multi, __isl_take isl_multi_val *mv)
882{
883	int i;
884
885	if (!multi || !mv)
886		goto error;
887
888	if (!isl_space_tuple_match(multi->space, isl_dim_out,
889					mv->space, isl_dim_set))
890		isl_die(isl_multi_val_get_ctx(mv), isl_error_invalid,
891			"spaces don't match", goto error);
892
893	multi = FN(MULTI(BASE),cow)(multi);
894	if (!multi)
895		return NULL;
896
897	for (i = 0; i < multi->n; ++i) {
898		isl_val *v;
899
900		v = isl_multi_val_get_val(mv, i);
901		multi->p[i] = FN(EL,scale_val)(multi->p[i], v);
902		if (!multi->p[i])
903			goto error;
904	}
905
906	isl_multi_val_free(mv);
907	return multi;
908error:
909	isl_multi_val_free(mv);
910	return FN(MULTI(BASE),free)(multi);
911}
912