1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011      INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 */
14
15#include <isl_sort.h>
16#include <isl_tarjan.h>
17
18#define xCAT(A,B) A ## B
19#define CAT(A,B) xCAT(A,B)
20#undef EL
21#define EL CAT(isl_,BASE)
22#define xFN(TYPE,NAME) TYPE ## _ ## NAME
23#define FN(TYPE,NAME) xFN(TYPE,NAME)
24#define xLIST(EL) EL ## _list
25#define LIST(EL) xLIST(EL)
26#define xS(TYPE,NAME) struct TYPE ## _ ## NAME
27#define S(TYPE,NAME) xS(TYPE,NAME)
28
29isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
30{
31	return list ? list->ctx : NULL;
32}
33
34__isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
35{
36	LIST(EL) *list;
37
38	if (n < 0)
39		isl_die(ctx, isl_error_invalid,
40			"cannot create list of negative length",
41			return NULL);
42	list = isl_alloc(ctx, LIST(EL),
43			 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
44	if (!list)
45		return NULL;
46
47	list->ctx = ctx;
48	isl_ctx_ref(ctx);
49	list->ref = 1;
50	list->size = n;
51	list->n = 0;
52	return list;
53}
54
55__isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
56{
57	if (!list)
58		return NULL;
59
60	list->ref++;
61	return list;
62}
63
64__isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
65{
66	int i;
67	LIST(EL) *dup;
68
69	if (!list)
70		return NULL;
71
72	dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
73	if (!dup)
74		return NULL;
75	for (i = 0; i < list->n; ++i)
76		dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
77	return dup;
78}
79
80__isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
81{
82	if (!list)
83		return NULL;
84
85	if (list->ref == 1)
86		return list;
87	list->ref--;
88	return FN(LIST(EL),dup)(list);
89}
90
91/* Make sure "list" has room for at least "n" more pieces.
92 * Always return a list with a single reference.
93 *
94 * If there is only one reference to list, we extend it in place.
95 * Otherwise, we create a new LIST(EL) and copy the elements.
96 */
97static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
98{
99	isl_ctx *ctx;
100	int i, new_size;
101	LIST(EL) *res;
102
103	if (!list)
104		return NULL;
105	if (list->ref == 1 && list->n + n <= list->size)
106		return list;
107
108	ctx = FN(LIST(EL),get_ctx)(list);
109	new_size = ((list->n + n + 1) * 3) / 2;
110	if (list->ref == 1) {
111		res = isl_realloc(ctx, list, LIST(EL),
112			    sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
113		if (!res)
114			return FN(LIST(EL),free)(list);
115		res->size = new_size;
116		return res;
117	}
118
119	if (list->n + n <= list->size && list->size < new_size)
120		new_size = list->size;
121
122	res = FN(LIST(EL),alloc)(ctx, new_size);
123	if (!res)
124		return FN(LIST(EL),free)(list);
125
126	for (i = 0; i < list->n; ++i)
127		res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
128
129	FN(LIST(EL),free)(list);
130	return res;
131}
132
133__isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
134	__isl_take struct EL *el)
135{
136	list = FN(LIST(EL),grow)(list, 1);
137	if (!list || !el)
138		goto error;
139	list->p[list->n] = el;
140	list->n++;
141	return list;
142error:
143	FN(EL,free)(el);
144	FN(LIST(EL),free)(list);
145	return NULL;
146}
147
148/* Remove the "n" elements starting at "first" from "list".
149 */
150__isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
151	unsigned first, unsigned n)
152{
153	int i;
154
155	if (!list)
156		return NULL;
157	if (first + n > list->n || first + n < first)
158		isl_die(list->ctx, isl_error_invalid,
159			"index out of bounds", return FN(LIST(EL),free)(list));
160	if (n == 0)
161		return list;
162	list = FN(LIST(EL),cow)(list);
163	if (!list)
164		return NULL;
165	for (i = 0; i < n; ++i)
166		FN(EL,free)(list->p[first + i]);
167	for (i = first; i + n < list->n; ++i)
168		list->p[i] = list->p[i + n];
169	list->n -= n;
170	return list;
171}
172
173/* Insert "el" at position "pos" in "list".
174 *
175 * If there is only one reference to "list" and if it already has space
176 * for one extra element, we insert it directly into "list".
177 * Otherwise, we create a new list consisting of "el" and copied
178 * elements from "list".
179 */
180__isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
181	unsigned pos, __isl_take struct EL *el)
182{
183	int i;
184	isl_ctx *ctx;
185	LIST(EL) *res;
186
187	if (!list || !el)
188		goto error;
189	ctx = FN(LIST(EL),get_ctx)(list);
190	if (pos > list->n)
191		isl_die(ctx, isl_error_invalid,
192			"index out of bounds", goto error);
193
194	if (list->ref == 1 && list->size > list->n) {
195		for (i = list->n - 1; i >= pos; --i)
196			list->p[i + 1] = list->p[i];
197		list->n++;
198		list->p[pos] = el;
199		return list;
200	}
201
202	res = FN(LIST(EL),alloc)(ctx, list->n + 1);
203	for (i = 0; i < pos; ++i)
204		res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
205	res = FN(LIST(EL),add)(res, el);
206	for (i = pos; i < list->n; ++i)
207		res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
208	FN(LIST(EL),free)(list);
209
210	return res;
211error:
212	FN(EL,free)(el);
213	FN(LIST(EL),free)(list);
214	return NULL;
215}
216
217void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
218{
219	int i;
220
221	if (!list)
222		return NULL;
223
224	if (--list->ref > 0)
225		return NULL;
226
227	isl_ctx_deref(list->ctx);
228	for (i = 0; i < list->n; ++i)
229		FN(EL,free)(list->p[i]);
230	free(list);
231
232	return NULL;
233}
234
235int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
236{
237	return list ? list->n : 0;
238}
239
240__isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
241{
242	if (!list)
243		return NULL;
244	if (index < 0 || index >= list->n)
245		isl_die(list->ctx, isl_error_invalid,
246			"index out of bounds", return NULL);
247	return FN(EL,copy)(list->p[index]);
248}
249
250/* Replace the element at position "index" in "list" by "el".
251 */
252__isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
253	int index, __isl_take EL *el)
254{
255	if (!list || !el)
256		goto error;
257	if (index < 0 || index >= list->n)
258		isl_die(list->ctx, isl_error_invalid,
259			"index out of bounds", goto error);
260	if (list->p[index] == el) {
261		FN(EL,free)(el);
262		return list;
263	}
264	list = FN(LIST(EL),cow)(list);
265	if (!list)
266		goto error;
267	FN(EL,free)(list->p[index]);
268	list->p[index] = el;
269	return list;
270error:
271	FN(EL,free)(el);
272	FN(LIST(EL),free)(list);
273	return NULL;
274}
275
276int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
277	int (*fn)(__isl_take EL *el, void *user), void *user)
278{
279	int i;
280
281	if (!list)
282		return -1;
283
284	for (i = 0; i < list->n; ++i) {
285		EL *el = FN(EL,copy(list->p[i]));
286		if (!el)
287			return -1;
288		if (fn(el, user) < 0)
289			return -1;
290	}
291
292	return 0;
293}
294
295/* Internal data structure for isl_*_list_sort.
296 *
297 * "cmp" is the original comparison function.
298 * "user" is a user provided pointer that should be passed to "cmp".
299 */
300S(LIST(EL),sort_data) {
301	int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
302	void *user;
303};
304
305/* Compare two entries of an isl_*_list based on the user provided
306 * comparison function on pairs of isl_* objects.
307 */
308static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
309{
310	S(LIST(EL),sort_data) *data = user;
311	EL * const *el1 = a;
312	EL * const *el2 = b;
313
314	return data->cmp(*el1, *el2, data->user);
315}
316
317/* Sort the elements of "list" in ascending order according to
318 * comparison function "cmp".
319 */
320__isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
321	int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
322{
323	S(LIST(EL),sort_data) data = { cmp, user };
324
325	if (!list)
326		return NULL;
327	if (list->n <= 1)
328		return list;
329	list = FN(LIST(EL),cow)(list);
330	if (!list)
331		return NULL;
332
333	if (isl_sort(list->p, list->n, sizeof(list->p[0]),
334			&FN(LIST(EL),cmp), &data) < 0)
335		return FN(LIST(EL),free)(list);
336
337	return list;
338}
339
340/* Internal data structure for isl_*_list_foreach_scc.
341 *
342 * "list" is the original list.
343 * "follows" is the user provided callback that defines the edges of the graph.
344 */
345S(LIST(EL),foreach_scc_data) {
346	LIST(EL) *list;
347	int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
348	void *follows_user;
349};
350
351/* Does element i of data->list follow element j?
352 *
353 * Use the user provided callback to find out.
354 */
355static int FN(LIST(EL),follows)(int i, int j, void *user)
356{
357	S(LIST(EL),foreach_scc_data) *data = user;
358
359	return data->follows(data->list->p[i], data->list->p[j],
360				data->follows_user);
361}
362
363/* Call "fn" on the sublist of "list" that consists of the elements
364 * with indices specified by the "n" elements of "pos".
365 */
366static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n,
367	int (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
368{
369	int i;
370	isl_ctx *ctx;
371	LIST(EL) *slice;
372
373	ctx = FN(LIST(EL),get_ctx)(list);
374	slice = FN(LIST(EL),alloc)(ctx, n);
375	for (i = 0; i < n; ++i) {
376		EL *el;
377
378		el = FN(EL,copy)(list->p[pos[i]]);
379		slice = FN(LIST(EL),add)(slice, el);
380	}
381
382	return fn(slice, user);
383}
384
385/* Call "fn" on each of the strongly connected components (SCCs) of
386 * the graph with as vertices the elements of "list" and
387 * a directed edge from node b to node a iff follows(a, b)
388 * returns 1.  follows should return -1 on error.
389 *
390 * If SCC a contains a node i that follows a node j in another SCC b
391 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
392 * after being called on SCC b.
393 *
394 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
395 * call fn on each of them.
396 */
397int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
398	int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
399	void *follows_user,
400	int (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
401{
402	S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
403	int i, n;
404	isl_ctx *ctx;
405	struct isl_tarjan_graph *g;
406
407	if (!list)
408		return -1;
409	if (list->n == 0)
410		return 0;
411	if (list->n == 1)
412		return fn(FN(LIST(EL),copy)(list), fn_user);
413
414	ctx = FN(LIST(EL),get_ctx)(list);
415	n = list->n;
416	g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
417	if (!g)
418		return -1;
419
420	i = 0;
421	do {
422		int first;
423
424		if (g->order[i] == -1)
425			isl_die(ctx, isl_error_internal, "cannot happen",
426				break);
427		first = i;
428		while (g->order[i] != -1) {
429			++i; --n;
430		}
431		if (first == 0 && n == 0) {
432			isl_tarjan_graph_free(g);
433			return fn(FN(LIST(EL),copy)(list), fn_user);
434		}
435		if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
436					    fn, fn_user) < 0)
437			break;
438		++i;
439	} while (n);
440
441	isl_tarjan_graph_free(g);
442
443	return n > 0 ? -1 : 0;
444}
445
446__isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
447{
448	isl_ctx *ctx;
449	LIST(EL) *list;
450
451	if (!el)
452		return NULL;
453	ctx = FN(EL,get_ctx)(el);
454	list = FN(LIST(EL),alloc)(ctx, 1);
455	if (!list)
456		goto error;
457	list = FN(LIST(EL),add)(list, el);
458	return list;
459error:
460	FN(EL,free)(el);
461	return NULL;
462}
463
464__isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
465	__isl_take LIST(EL) *list2)
466{
467	int i;
468	isl_ctx *ctx;
469	LIST(EL) *res;
470
471	if (!list1 || !list2)
472		goto error;
473
474	ctx = FN(LIST(EL),get_ctx)(list1);
475	res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
476	for (i = 0; i < list1->n; ++i)
477		res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
478	for (i = 0; i < list2->n; ++i)
479		res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
480
481	FN(LIST(EL),free)(list1);
482	FN(LIST(EL),free)(list2);
483	return res;
484error:
485	FN(LIST(EL),free)(list1);
486	FN(LIST(EL),free)(list2);
487	return NULL;
488}
489
490__isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
491	__isl_take isl_printer *p, __isl_keep LIST(EL) *list)
492{
493	int i;
494
495	if (!p || !list)
496		goto error;
497	p = isl_printer_print_str(p, "(");
498	for (i = 0; i < list->n; ++i) {
499		if (i)
500			p = isl_printer_print_str(p, ",");
501		p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
502	}
503	p = isl_printer_print_str(p, ")");
504	return p;
505error:
506	isl_printer_free(p);
507	return NULL;
508}
509
510void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
511{
512	isl_printer *printer;
513
514	if (!list)
515		return;
516
517	printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
518	printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
519	printer = isl_printer_end_line(printer);
520
521	isl_printer_free(printer);
522}
523