2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2017 Sven Verdoolaege
7 * Use of this software is governed by the MIT license
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
17 #include <isl_tarjan.h>
19 #define xCAT(A,B) A ## B
20 #define CAT(A,B) xCAT(A,B)
22 #define EL CAT(isl_,BASE)
23 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
24 #define FN(TYPE,NAME) xFN(TYPE,NAME)
25 #define xLIST(EL) EL ## _list
26 #define LIST(EL) xLIST(EL)
27 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
28 #define S(TYPE,NAME) xS(TYPE,NAME)
30 isl_ctx
*FN(LIST(EL
),get_ctx
)(__isl_keep
LIST(EL
) *list
)
32 return list
? list
->ctx
: NULL
;
35 __isl_give
LIST(EL
) *FN(LIST(EL
),alloc
)(isl_ctx
*ctx
, int n
)
40 isl_die(ctx
, isl_error_invalid
,
41 "cannot create list of negative length",
43 list
= isl_alloc(ctx
, LIST(EL
),
44 sizeof(LIST(EL
)) + (n
- 1) * sizeof(struct EL
*));
56 __isl_give
LIST(EL
) *FN(LIST(EL
),copy
)(__isl_keep
LIST(EL
) *list
)
65 __isl_give
LIST(EL
) *FN(LIST(EL
),dup
)(__isl_keep
LIST(EL
) *list
)
73 dup
= FN(LIST(EL
),alloc
)(FN(LIST(EL
),get_ctx
)(list
), list
->n
);
76 for (i
= 0; i
< list
->n
; ++i
)
77 dup
= FN(LIST(EL
),add
)(dup
, FN(EL
,copy
)(list
->p
[i
]));
81 __isl_give
LIST(EL
) *FN(LIST(EL
),cow
)(__isl_take
LIST(EL
) *list
)
89 return FN(LIST(EL
),dup
)(list
);
92 /* Make sure "list" has room for at least "n" more pieces.
93 * Always return a list with a single reference.
95 * If there is only one reference to list, we extend it in place.
96 * Otherwise, we create a new LIST(EL) and copy the elements.
98 static __isl_give
LIST(EL
) *FN(LIST(EL
),grow
)(__isl_take
LIST(EL
) *list
, int n
)
106 if (list
->ref
== 1 && list
->n
+ n
<= list
->size
)
109 ctx
= FN(LIST(EL
),get_ctx
)(list
);
110 new_size
= ((list
->n
+ n
+ 1) * 3) / 2;
111 if (list
->ref
== 1) {
112 res
= isl_realloc(ctx
, list
, LIST(EL
),
113 sizeof(LIST(EL
)) + (new_size
- 1) * sizeof(EL
*));
115 return FN(LIST(EL
),free
)(list
);
116 res
->size
= new_size
;
120 if (list
->n
+ n
<= list
->size
&& list
->size
< new_size
)
121 new_size
= list
->size
;
123 res
= FN(LIST(EL
),alloc
)(ctx
, new_size
);
125 return FN(LIST(EL
),free
)(list
);
127 for (i
= 0; i
< list
->n
; ++i
)
128 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
130 FN(LIST(EL
),free
)(list
);
134 /* Check that "index" is a valid position in "list".
136 static isl_stat
FN(LIST(EL
),check_index
)(__isl_keep
LIST(EL
) *list
, int index
)
139 return isl_stat_error
;
140 if (index
< 0 || index
>= list
->n
)
141 isl_die(FN(LIST(EL
),get_ctx
)(list
), isl_error_invalid
,
142 "index out of bounds", return isl_stat_error
);
146 __isl_give
LIST(EL
) *FN(LIST(EL
),add
)(__isl_take
LIST(EL
) *list
,
147 __isl_take
struct EL
*el
)
149 list
= FN(LIST(EL
),grow
)(list
, 1);
152 list
->p
[list
->n
] = el
;
157 FN(LIST(EL
),free
)(list
);
161 /* Remove the "n" elements starting at "first" from "list".
163 __isl_give
LIST(EL
) *FN(LIST(EL
),drop
)(__isl_take
LIST(EL
) *list
,
164 unsigned first
, unsigned n
)
170 if (first
+ n
> list
->n
|| first
+ n
< first
)
171 isl_die(list
->ctx
, isl_error_invalid
,
172 "index out of bounds", return FN(LIST(EL
),free
)(list
));
175 list
= FN(LIST(EL
),cow
)(list
);
178 for (i
= 0; i
< n
; ++i
)
179 FN(EL
,free
)(list
->p
[first
+ i
]);
180 for (i
= first
; i
+ n
< list
->n
; ++i
)
181 list
->p
[i
] = list
->p
[i
+ n
];
186 /* Insert "el" at position "pos" in "list".
188 * If there is only one reference to "list" and if it already has space
189 * for one extra element, we insert it directly into "list".
190 * Otherwise, we create a new list consisting of "el" and copied
191 * elements from "list".
193 __isl_give
LIST(EL
) *FN(LIST(EL
),insert
)(__isl_take
LIST(EL
) *list
,
194 unsigned pos
, __isl_take
struct EL
*el
)
202 ctx
= FN(LIST(EL
),get_ctx
)(list
);
204 isl_die(ctx
, isl_error_invalid
,
205 "index out of bounds", goto error
);
207 if (list
->ref
== 1 && list
->size
> list
->n
) {
208 for (i
= list
->n
; i
> pos
; --i
)
209 list
->p
[i
] = list
->p
[i
- 1];
215 res
= FN(LIST(EL
),alloc
)(ctx
, list
->n
+ 1);
216 for (i
= 0; i
< pos
; ++i
)
217 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
218 res
= FN(LIST(EL
),add
)(res
, el
);
219 for (i
= pos
; i
< list
->n
; ++i
)
220 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
221 FN(LIST(EL
),free
)(list
);
226 FN(LIST(EL
),free
)(list
);
230 __isl_null
LIST(EL
) *FN(LIST(EL
),free
)(__isl_take
LIST(EL
) *list
)
240 isl_ctx_deref(list
->ctx
);
241 for (i
= 0; i
< list
->n
; ++i
)
242 FN(EL
,free
)(list
->p
[i
]);
248 int FN(FN(LIST(EL
),n
),BASE
)(__isl_keep
LIST(EL
) *list
)
250 return list
? list
->n
: 0;
253 __isl_give EL
*FN(FN(LIST(EL
),get
),BASE
)(__isl_keep
LIST(EL
) *list
, int index
)
255 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
257 return FN(EL
,copy
)(list
->p
[index
]);
260 /* Replace the element at position "index" in "list" by "el".
262 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),set
),BASE
)(__isl_take
LIST(EL
) *list
,
263 int index
, __isl_take EL
*el
)
267 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
269 if (list
->p
[index
] == el
) {
273 list
= FN(LIST(EL
),cow
)(list
);
276 FN(EL
,free
)(list
->p
[index
]);
281 FN(LIST(EL
),free
)(list
);
285 /* Return the element at position "index" of "list".
286 * This may be either a copy or the element itself
287 * if there is only one reference to "list".
288 * This allows the element to be modified inplace
289 * if both the list and the element have only a single reference.
290 * The caller is not allowed to modify "list" between
291 * this call to isl_list_*_take_* and a subsequent call
292 * to isl_list_*_restore_*.
293 * The only exception is that isl_list_*_free can be called instead.
295 static __isl_give EL
*FN(FN(LIST(EL
),take
),BASE
)(__isl_keep
LIST(EL
) *list
,
300 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
303 return FN(FN(LIST(EL
),get
),BASE
)(list
, index
);
305 list
->p
[index
] = NULL
;
309 /* Set the element at position "index" of "list" to "el",
310 * where the position may be empty due to a previous call
311 * to isl_list_*_take_*.
313 static __isl_give
LIST(EL
) *FN(FN(LIST(EL
),restore
),BASE
)(
314 __isl_take
LIST(EL
) *list
, int index
, __isl_take EL
*el
)
316 return FN(FN(LIST(EL
),set
),BASE
)(list
, index
, el
);
319 isl_stat
FN(LIST(EL
),foreach
)(__isl_keep
LIST(EL
) *list
,
320 isl_stat (*fn
)(__isl_take EL
*el
, void *user
), void *user
)
325 return isl_stat_error
;
327 for (i
= 0; i
< list
->n
; ++i
) {
328 EL
*el
= FN(EL
,copy
)(list
->p
[i
]);
330 return isl_stat_error
;
331 if (fn(el
, user
) < 0)
332 return isl_stat_error
;
338 /* Replace each element in "list" by the result of calling "fn"
341 __isl_give
LIST(EL
) *FN(LIST(EL
),map
)(__isl_keep
LIST(EL
) *list
,
342 __isl_give EL
*(*fn
)(__isl_take EL
*el
, void *user
), void *user
)
350 for (i
= 0; i
< n
; ++i
) {
351 EL
*el
= FN(FN(LIST(EL
),take
),BASE
)(list
, i
);
353 return FN(LIST(EL
),free
)(list
);
355 list
= FN(FN(LIST(EL
),restore
),BASE
)(list
, i
, el
);
361 /* Internal data structure for isl_*_list_sort.
363 * "cmp" is the original comparison function.
364 * "user" is a user provided pointer that should be passed to "cmp".
366 S(LIST(EL
),sort_data
) {
367 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
371 /* Compare two entries of an isl_*_list based on the user provided
372 * comparison function on pairs of isl_* objects.
374 static int FN(LIST(EL
),cmp
)(const void *a
, const void *b
, void *user
)
376 S(LIST(EL
),sort_data
) *data
= user
;
380 return data
->cmp(*el1
, *el2
, data
->user
);
383 /* Sort the elements of "list" in ascending order according to
384 * comparison function "cmp".
386 __isl_give
LIST(EL
) *FN(LIST(EL
),sort
)(__isl_take
LIST(EL
) *list
,
387 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
), void *user
)
389 S(LIST(EL
),sort_data
) data
= { cmp
, user
};
395 list
= FN(LIST(EL
),cow
)(list
);
399 if (isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]),
400 &FN(LIST(EL
),cmp
), &data
) < 0)
401 return FN(LIST(EL
),free
)(list
);
406 /* Internal data structure for isl_*_list_foreach_scc.
408 * "list" is the original list.
409 * "follows" is the user provided callback that defines the edges of the graph.
411 S(LIST(EL
),foreach_scc_data
) {
413 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
417 /* Does element i of data->list follow element j?
419 * Use the user provided callback to find out.
421 static isl_bool
FN(LIST(EL
),follows
)(int i
, int j
, void *user
)
423 S(LIST(EL
),foreach_scc_data
) *data
= user
;
425 return data
->follows(data
->list
->p
[i
], data
->list
->p
[j
],
429 /* Call "fn" on the sublist of "list" that consists of the elements
430 * with indices specified by the "n" elements of "pos".
432 static isl_stat
FN(LIST(EL
),call_on_scc
)(__isl_keep
LIST(EL
) *list
, int *pos
,
433 int n
, isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *user
)
439 ctx
= FN(LIST(EL
),get_ctx
)(list
);
440 slice
= FN(LIST(EL
),alloc
)(ctx
, n
);
441 for (i
= 0; i
< n
; ++i
) {
444 el
= FN(EL
,copy
)(list
->p
[pos
[i
]]);
445 slice
= FN(LIST(EL
),add
)(slice
, el
);
448 return fn(slice
, user
);
451 /* Call "fn" on each of the strongly connected components (SCCs) of
452 * the graph with as vertices the elements of "list" and
453 * a directed edge from node b to node a iff follows(a, b)
454 * returns 1. follows should return -1 on error.
456 * If SCC a contains a node i that follows a node j in another SCC b
457 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
458 * after being called on SCC b.
460 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
461 * call fn on each of them.
463 isl_stat
FN(LIST(EL
),foreach_scc
)(__isl_keep
LIST(EL
) *list
,
464 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
),
466 isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *fn_user
)
468 S(LIST(EL
),foreach_scc_data
) data
= { list
, follows
, follows_user
};
471 struct isl_tarjan_graph
*g
;
474 return isl_stat_error
;
478 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
480 ctx
= FN(LIST(EL
),get_ctx
)(list
);
482 g
= isl_tarjan_graph_init(ctx
, n
, &FN(LIST(EL
),follows
), &data
);
484 return isl_stat_error
;
490 if (g
->order
[i
] == -1)
491 isl_die(ctx
, isl_error_internal
, "cannot happen",
494 while (g
->order
[i
] != -1) {
497 if (first
== 0 && n
== 0) {
498 isl_tarjan_graph_free(g
);
499 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
501 if (FN(LIST(EL
),call_on_scc
)(list
, g
->order
+ first
, i
- first
,
507 isl_tarjan_graph_free(g
);
509 return n
> 0 ? isl_stat_error
: isl_stat_ok
;
512 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),from
),BASE
)(__isl_take EL
*el
)
519 ctx
= FN(EL
,get_ctx
)(el
);
520 list
= FN(LIST(EL
),alloc
)(ctx
, 1);
523 list
= FN(LIST(EL
),add
)(list
, el
);
530 __isl_give
LIST(EL
) *FN(LIST(EL
),concat
)(__isl_take
LIST(EL
) *list1
,
531 __isl_take
LIST(EL
) *list2
)
537 if (!list1
|| !list2
)
540 ctx
= FN(LIST(EL
),get_ctx
)(list1
);
541 res
= FN(LIST(EL
),alloc
)(ctx
, list1
->n
+ list2
->n
);
542 for (i
= 0; i
< list1
->n
; ++i
)
543 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list1
->p
[i
]));
544 for (i
= 0; i
< list2
->n
; ++i
)
545 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list2
->p
[i
]));
547 FN(LIST(EL
),free
)(list1
);
548 FN(LIST(EL
),free
)(list2
);
551 FN(LIST(EL
),free
)(list1
);
552 FN(LIST(EL
),free
)(list2
);
556 __isl_give isl_printer
*CAT(isl_printer_print_
,LIST(BASE
))(
557 __isl_take isl_printer
*p
, __isl_keep
LIST(EL
) *list
)
563 p
= isl_printer_print_str(p
, "(");
564 for (i
= 0; i
< list
->n
; ++i
) {
566 p
= isl_printer_print_str(p
, ",");
567 p
= CAT(isl_printer_print_
,BASE
)(p
, list
->p
[i
]);
569 p
= isl_printer_print_str(p
, ")");
576 void FN(LIST(EL
),dump
)(__isl_keep
LIST(EL
) *list
)
578 isl_printer
*printer
;
583 printer
= isl_printer_to_file(FN(LIST(EL
),get_ctx
)(list
), stderr
);
584 printer
= CAT(isl_printer_print_
,LIST(BASE
))(printer
, list
);
585 printer
= isl_printer_end_line(printer
);
587 isl_printer_free(printer
);