2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
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
16 #include <isl_tarjan.h>
18 #define xCAT(A,B) A ## B
19 #define CAT(A,B) xCAT(A,B)
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)
29 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
31 return list ? list->ctx : NULL;
34 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
39 isl_die(ctx, isl_error_invalid,
40 "cannot create list of negative length",
42 list = isl_alloc(ctx, LIST(EL),
43 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
55 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
64 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
72 dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
75 for (i = 0; i < list->n; ++i)
76 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
80 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
88 return FN(LIST(EL),dup)(list);
91 /* Make sure "list" has room for at least "n" more pieces.
93 * If there is only one reference to list, we extend it in place.
94 * Otherwise, we create a new LIST(EL) and copy the elements.
96 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
104 if (list->n + n <= list->size)
107 ctx = FN(LIST(EL),get_ctx)(list);
108 new_size = ((list->n + n + 1) * 3) / 2;
109 if (list->ref == 1) {
110 res = isl_realloc(ctx, list, LIST(EL),
111 sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
113 return FN(LIST(EL),free)(list);
114 res->size = new_size;
118 res = FN(LIST(EL),alloc)(ctx, new_size);
120 return FN(LIST(EL),free)(list);
122 for (i = 0; i < list->n; ++i)
123 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
125 FN(LIST(EL),free)(list);
129 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
130 __isl_take struct EL *el)
132 list = FN(LIST(EL),grow)(list, 1);
135 list->p[list->n] = el;
140 FN(LIST(EL),free)(list);
144 /* Remove the "n" elements starting at "first" from "list".
146 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
147 unsigned first, unsigned n)
153 if (first + n > list->n || first + n < first)
154 isl_die(list->ctx, isl_error_invalid,
155 "index out of bounds", return FN(LIST(EL),free)(list));
158 list = FN(LIST(EL),cow)(list);
161 for (i = 0; i < n; ++i)
162 FN(EL,free)(list->p[first + i]);
163 for (i = first; i + n < list->n; ++i)
164 list->p[i] = list->p[i + n];
169 /* Insert "el" at position "pos" in "list".
171 * If there is only one reference to "list" and if it already has space
172 * for one extra element, we insert it directly into "list".
173 * Otherwise, we create a new list consisting of "el" and copied
174 * elements from "list".
176 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
177 unsigned pos, __isl_take struct EL *el)
185 ctx = FN(LIST(EL),get_ctx)(list);
187 isl_die(ctx, isl_error_invalid,
188 "index out of bounds", goto error);
190 if (list->ref == 1 && list->size > list->n) {
191 for (i = list->n - 1; i >= pos; --i)
192 list->p[i + 1] = list->p[i];
198 res = FN(LIST(EL),alloc)(ctx, list->n + 1);
199 for (i = 0; i < pos; ++i)
200 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
201 res = FN(LIST(EL),add)(res, el);
202 for (i = pos; i < list->n; ++i)
203 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
204 FN(LIST(EL),free)(list);
209 FN(LIST(EL),free)(list);
213 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
223 isl_ctx_deref(list->ctx);
224 for (i = 0; i < list->n; ++i)
225 FN(EL,free)(list->p[i]);
231 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
233 return list ? list->n : 0;
236 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
240 if (index < 0 || index >= list->n)
241 isl_die(list->ctx, isl_error_invalid,
242 "index out of bounds", return NULL);
243 return FN(EL,copy)(list->p[index]);
246 /* Replace the element at position "index" in "list" by "el".
248 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
249 int index, __isl_take EL *el)
253 if (index < 0 || index >= list->n)
254 isl_die(list->ctx, isl_error_invalid,
255 "index out of bounds", goto error);
256 if (list->p[index] == el) {
260 list = FN(LIST(EL),cow)(list);
263 FN(EL,free)(list->p[index]);
268 FN(LIST(EL),free)(list);
272 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
273 int (*fn)(__isl_take EL *el, void *user), void *user)
280 for (i = 0; i < list->n; ++i) {
281 EL *el = FN(EL,copy(list->p[i]));
284 if (fn(el, user) < 0)
291 /* Internal data structure for isl_*_list_sort.
293 * "cmp" is the original comparison function.
294 * "user" is a user provided pointer that should be passed to "cmp".
296 S(LIST(EL),sort_data) {
297 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
301 /* Compare two entries of an isl_*_list based on the user provided
302 * comparison function on pairs of isl_* objects.
304 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
306 S(LIST(EL),sort_data) *data = user;
310 return data->cmp(*el1, *el2, data->user);
313 /* Sort the elements of "list" in ascending order according to
314 * comparison function "cmp".
316 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
317 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
319 S(LIST(EL),sort_data) data = { cmp, user };
325 list = FN(LIST(EL),cow)(list);
329 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
330 &FN(LIST(EL),cmp), &data) < 0)
331 return FN(LIST(EL),free)(list);
336 /* Internal data structure for isl_*_list_foreach_scc.
338 * "list" is the original list.
339 * "follows" is the user provided callback that defines the edges of the graph.
341 S(LIST(EL),foreach_scc_data) {
343 int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
347 /* Does element i of data->list follow element j?
349 * Use the user provided callback to find out.
351 static int FN(LIST(EL),follows)(int i, int j, void *user)
353 S(LIST(EL),foreach_scc_data) *data = user;
355 return data->follows(data->list->p[i], data->list->p[j],
359 /* Call "fn" on the sublist of "list" that consists of the elements
360 * with indices specified by the "n" elements of "pos".
362 static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n,
363 int (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
369 ctx = FN(LIST(EL),get_ctx)(list);
370 slice = FN(LIST(EL),alloc)(ctx, n);
371 for (i = 0; i < n; ++i) {
374 el = FN(EL,copy)(list->p[pos[i]]);
375 slice = FN(LIST(EL),add)(slice, el);
378 return fn(slice, user);
381 /* Call "fn" on each of the strongly connected components (SCCs) of
382 * the graph with as vertices the elements of "list" and
383 * a directed edge from node b to node a iff follows(a, b)
384 * returns 1. follows should return -1 on error.
386 * If SCC a contains a node i that follows a node j in another SCC b
387 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
388 * after being called on SCC b.
390 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
391 * call fn on each of them.
393 int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
394 int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
396 int (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
398 S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
401 struct isl_tarjan_graph *g;
408 return fn(FN(LIST(EL),copy)(list), fn_user);
410 ctx = FN(LIST(EL),get_ctx)(list);
412 g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
420 if (g->order[i] == -1)
421 isl_die(ctx, isl_error_internal, "cannot happen",
424 while (g->order[i] != -1) {
427 if (first == 0 && n == 0) {
428 isl_tarjan_graph_free(g);
429 return fn(FN(LIST(EL),copy)(list), fn_user);
431 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
437 isl_tarjan_graph_free(g);
439 return n > 0 ? -1 : 0;
442 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
449 ctx = FN(EL,get_ctx)(el);
450 list = FN(LIST(EL),alloc)(ctx, 1);
453 list = FN(LIST(EL),add)(list, el);
460 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
461 __isl_take LIST(EL) *list2)
467 if (!list1 || !list2)
470 ctx = FN(LIST(EL),get_ctx)(list1);
471 res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
472 for (i = 0; i < list1->n; ++i)
473 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
474 for (i = 0; i < list2->n; ++i)
475 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
477 FN(LIST(EL),free)(list1);
478 FN(LIST(EL),free)(list2);
481 FN(LIST(EL),free)(list1);
482 FN(LIST(EL),free)(list2);
486 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
487 __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
493 p = isl_printer_print_str(p, "(");
494 for (i = 0; i < list->n; ++i) {
496 p = isl_printer_print_str(p, ",");
497 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
499 p = isl_printer_print_str(p, ")");
506 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
508 isl_printer *printer;
513 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
514 printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
515 printer = isl_printer_end_line(printer);
517 isl_printer_free(printer);