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
);