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>
18 #include <isl/printer.h>
20 #define xCAT(A,B) A ## B
21 #define CAT(A,B) xCAT(A,B)
23 #define EL CAT(isl_,BASE)
24 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
25 #define FN(TYPE,NAME) xFN(TYPE,NAME)
26 #define xLIST(EL) EL ## _list
27 #define LIST(EL) xLIST(EL)
28 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
29 #define S(TYPE,NAME) xS(TYPE,NAME)
31 isl_ctx
*FN(LIST(EL
),get_ctx
)(__isl_keep
LIST(EL
) *list
)
33 return list
? list
->ctx
: NULL
;
36 __isl_give
LIST(EL
) *FN(LIST(EL
),alloc
)(isl_ctx
*ctx
, int n
)
41 isl_die(ctx
, isl_error_invalid
,
42 "cannot create list of negative length",
44 list
= isl_alloc(ctx
, LIST(EL
),
45 sizeof(LIST(EL
)) + (n
- 1) * sizeof(struct EL
*));
57 __isl_give
LIST(EL
) *FN(LIST(EL
),copy
)(__isl_keep
LIST(EL
) *list
)
66 __isl_give
LIST(EL
) *FN(LIST(EL
),dup
)(__isl_keep
LIST(EL
) *list
)
74 dup
= FN(LIST(EL
),alloc
)(FN(LIST(EL
),get_ctx
)(list
), list
->n
);
77 for (i
= 0; i
< list
->n
; ++i
)
78 dup
= FN(LIST(EL
),add
)(dup
, FN(EL
,copy
)(list
->p
[i
]));
82 __isl_give
LIST(EL
) *FN(LIST(EL
),cow
)(__isl_take
LIST(EL
) *list
)
90 return FN(LIST(EL
),dup
)(list
);
93 /* Make sure "list" has room for at least "n" more pieces.
94 * Always return a list with a single reference.
96 * If there is only one reference to list, we extend it in place.
97 * Otherwise, we create a new LIST(EL) and copy the elements.
99 static __isl_give
LIST(EL
) *FN(LIST(EL
),grow
)(__isl_take
LIST(EL
) *list
, int n
)
107 if (list
->ref
== 1 && list
->n
+ n
<= list
->size
)
110 ctx
= FN(LIST(EL
),get_ctx
)(list
);
111 new_size
= ((list
->n
+ n
+ 1) * 3) / 2;
112 if (list
->ref
== 1) {
113 res
= isl_realloc(ctx
, list
, LIST(EL
),
114 sizeof(LIST(EL
)) + (new_size
- 1) * sizeof(EL
*));
116 return FN(LIST(EL
),free
)(list
);
117 res
->size
= new_size
;
121 if (list
->n
+ n
<= list
->size
&& list
->size
< new_size
)
122 new_size
= list
->size
;
124 res
= FN(LIST(EL
),alloc
)(ctx
, new_size
);
126 return FN(LIST(EL
),free
)(list
);
128 for (i
= 0; i
< list
->n
; ++i
)
129 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
131 FN(LIST(EL
),free
)(list
);
135 /* Check that "index" is a valid position in "list".
137 static isl_stat
FN(LIST(EL
),check_index
)(__isl_keep
LIST(EL
) *list
, int index
)
140 return isl_stat_error
;
141 if (index
< 0 || index
>= list
->n
)
142 isl_die(FN(LIST(EL
),get_ctx
)(list
), isl_error_invalid
,
143 "index out of bounds", return isl_stat_error
);
147 __isl_give
LIST(EL
) *FN(LIST(EL
),add
)(__isl_take
LIST(EL
) *list
,
148 __isl_take
struct EL
*el
)
150 list
= FN(LIST(EL
),grow
)(list
, 1);
153 list
->p
[list
->n
] = el
;
158 FN(LIST(EL
),free
)(list
);
162 /* Remove the "n" elements starting at "first" from "list".
164 __isl_give
LIST(EL
) *FN(LIST(EL
),drop
)(__isl_take
LIST(EL
) *list
,
165 unsigned first
, unsigned n
)
171 if (first
+ n
> list
->n
|| first
+ n
< first
)
172 isl_die(list
->ctx
, isl_error_invalid
,
173 "index out of bounds", return FN(LIST(EL
),free
)(list
));
176 list
= FN(LIST(EL
),cow
)(list
);
179 for (i
= 0; i
< n
; ++i
)
180 FN(EL
,free
)(list
->p
[first
+ i
]);
181 for (i
= first
; i
+ n
< list
->n
; ++i
)
182 list
->p
[i
] = list
->p
[i
+ n
];
187 /* Insert "el" at position "pos" in "list".
189 * If there is only one reference to "list" and if it already has space
190 * for one extra element, we insert it directly into "list".
191 * Otherwise, we create a new list consisting of "el" and copied
192 * elements from "list".
194 __isl_give
LIST(EL
) *FN(LIST(EL
),insert
)(__isl_take
LIST(EL
) *list
,
195 unsigned pos
, __isl_take
struct EL
*el
)
203 ctx
= FN(LIST(EL
),get_ctx
)(list
);
205 isl_die(ctx
, isl_error_invalid
,
206 "index out of bounds", goto error
);
208 if (list
->ref
== 1 && list
->size
> list
->n
) {
209 for (i
= list
->n
; i
> pos
; --i
)
210 list
->p
[i
] = list
->p
[i
- 1];
216 res
= FN(LIST(EL
),alloc
)(ctx
, list
->n
+ 1);
217 for (i
= 0; i
< pos
; ++i
)
218 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
219 res
= FN(LIST(EL
),add
)(res
, el
);
220 for (i
= pos
; i
< list
->n
; ++i
)
221 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
222 FN(LIST(EL
),free
)(list
);
227 FN(LIST(EL
),free
)(list
);
231 __isl_null
LIST(EL
) *FN(LIST(EL
),free
)(__isl_take
LIST(EL
) *list
)
241 isl_ctx_deref(list
->ctx
);
242 for (i
= 0; i
< list
->n
; ++i
)
243 FN(EL
,free
)(list
->p
[i
]);
249 int FN(FN(LIST(EL
),n
),BASE
)(__isl_keep
LIST(EL
) *list
)
251 return list
? list
->n
: 0;
254 /* Return the element at position "index" in "list".
256 static __isl_keep EL
*FN(LIST(EL
),peek
)(__isl_keep
LIST(EL
) *list
, int index
)
258 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
260 return list
->p
[index
];
263 /* Return a copy of the element at position "index" in "list".
265 __isl_give EL
*FN(LIST(EL
),get_at
)(__isl_keep
LIST(EL
) *list
, int index
)
267 return FN(EL
,copy
)(FN(LIST(EL
),peek
)(list
, index
));
270 /* This is an alternative name for the function above.
272 __isl_give EL
*FN(FN(LIST(EL
),get
),BASE
)(__isl_keep
LIST(EL
) *list
, int index
)
274 return FN(LIST(EL
),get_at
)(list
, index
);
277 /* Replace the element at position "index" in "list" by "el".
279 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),set
),BASE
)(__isl_take
LIST(EL
) *list
,
280 int index
, __isl_take EL
*el
)
284 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
286 if (list
->p
[index
] == el
) {
290 list
= FN(LIST(EL
),cow
)(list
);
293 FN(EL
,free
)(list
->p
[index
]);
298 FN(LIST(EL
),free
)(list
);
302 /* Return the element at position "index" of "list".
303 * This may be either a copy or the element itself
304 * if there is only one reference to "list".
305 * This allows the element to be modified inplace
306 * if both the list and the element have only a single reference.
307 * The caller is not allowed to modify "list" between
308 * this call to isl_list_*_take_* and a subsequent call
309 * to isl_list_*_restore_*.
310 * The only exception is that isl_list_*_free can be called instead.
312 static __isl_give EL
*FN(FN(LIST(EL
),take
),BASE
)(__isl_keep
LIST(EL
) *list
,
317 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
320 return FN(FN(LIST(EL
),get
),BASE
)(list
, index
);
322 list
->p
[index
] = NULL
;
326 /* Set the element at position "index" of "list" to "el",
327 * where the position may be empty due to a previous call
328 * to isl_list_*_take_*.
330 static __isl_give
LIST(EL
) *FN(FN(LIST(EL
),restore
),BASE
)(
331 __isl_take
LIST(EL
) *list
, int index
, __isl_take EL
*el
)
333 return FN(FN(LIST(EL
),set
),BASE
)(list
, index
, el
);
336 isl_stat
FN(LIST(EL
),foreach
)(__isl_keep
LIST(EL
) *list
,
337 isl_stat (*fn
)(__isl_take EL
*el
, void *user
), void *user
)
342 return isl_stat_error
;
344 for (i
= 0; i
< list
->n
; ++i
) {
345 EL
*el
= FN(EL
,copy
)(list
->p
[i
]);
347 return isl_stat_error
;
348 if (fn(el
, user
) < 0)
349 return isl_stat_error
;
355 /* Replace each element in "list" by the result of calling "fn"
358 __isl_give
LIST(EL
) *FN(LIST(EL
),map
)(__isl_keep
LIST(EL
) *list
,
359 __isl_give EL
*(*fn
)(__isl_take EL
*el
, void *user
), void *user
)
367 for (i
= 0; i
< n
; ++i
) {
368 EL
*el
= FN(FN(LIST(EL
),take
),BASE
)(list
, i
);
370 return FN(LIST(EL
),free
)(list
);
372 list
= FN(FN(LIST(EL
),restore
),BASE
)(list
, i
, el
);
378 /* Internal data structure for isl_*_list_sort.
380 * "cmp" is the original comparison function.
381 * "user" is a user provided pointer that should be passed to "cmp".
383 S(LIST(EL
),sort_data
) {
384 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
388 /* Compare two entries of an isl_*_list based on the user provided
389 * comparison function on pairs of isl_* objects.
391 static int FN(LIST(EL
),cmp
)(const void *a
, const void *b
, void *user
)
393 S(LIST(EL
),sort_data
) *data
= user
;
397 return data
->cmp(*el1
, *el2
, data
->user
);
400 /* Sort the elements of "list" in ascending order according to
401 * comparison function "cmp".
403 __isl_give
LIST(EL
) *FN(LIST(EL
),sort
)(__isl_take
LIST(EL
) *list
,
404 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
), void *user
)
406 S(LIST(EL
),sort_data
) data
= { cmp
, user
};
412 list
= FN(LIST(EL
),cow
)(list
);
416 if (isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]),
417 &FN(LIST(EL
),cmp
), &data
) < 0)
418 return FN(LIST(EL
),free
)(list
);
423 /* Internal data structure for isl_*_list_foreach_scc.
425 * "list" is the original list.
426 * "follows" is the user provided callback that defines the edges of the graph.
428 S(LIST(EL
),foreach_scc_data
) {
430 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
434 /* Does element i of data->list follow element j?
436 * Use the user provided callback to find out.
438 static isl_bool
FN(LIST(EL
),follows
)(int i
, int j
, void *user
)
440 S(LIST(EL
),foreach_scc_data
) *data
= user
;
442 return data
->follows(data
->list
->p
[i
], data
->list
->p
[j
],
446 /* Call "fn" on the sublist of "list" that consists of the elements
447 * with indices specified by the "n" elements of "pos".
449 static isl_stat
FN(LIST(EL
),call_on_scc
)(__isl_keep
LIST(EL
) *list
, int *pos
,
450 int n
, isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *user
)
456 ctx
= FN(LIST(EL
),get_ctx
)(list
);
457 slice
= FN(LIST(EL
),alloc
)(ctx
, n
);
458 for (i
= 0; i
< n
; ++i
) {
461 el
= FN(EL
,copy
)(list
->p
[pos
[i
]]);
462 slice
= FN(LIST(EL
),add
)(slice
, el
);
465 return fn(slice
, user
);
468 /* Call "fn" on each of the strongly connected components (SCCs) of
469 * the graph with as vertices the elements of "list" and
470 * a directed edge from node b to node a iff follows(a, b)
471 * returns 1. follows should return -1 on error.
473 * If SCC a contains a node i that follows a node j in another SCC b
474 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
475 * after being called on SCC b.
477 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
478 * call fn on each of them.
480 isl_stat
FN(LIST(EL
),foreach_scc
)(__isl_keep
LIST(EL
) *list
,
481 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
),
483 isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *fn_user
)
485 S(LIST(EL
),foreach_scc_data
) data
= { list
, follows
, follows_user
};
488 struct isl_tarjan_graph
*g
;
491 return isl_stat_error
;
495 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
497 ctx
= FN(LIST(EL
),get_ctx
)(list
);
499 g
= isl_tarjan_graph_init(ctx
, n
, &FN(LIST(EL
),follows
), &data
);
501 return isl_stat_error
;
507 if (g
->order
[i
] == -1)
508 isl_die(ctx
, isl_error_internal
, "cannot happen",
511 while (g
->order
[i
] != -1) {
514 if (first
== 0 && n
== 0) {
515 isl_tarjan_graph_free(g
);
516 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
518 if (FN(LIST(EL
),call_on_scc
)(list
, g
->order
+ first
, i
- first
,
524 isl_tarjan_graph_free(g
);
526 return n
> 0 ? isl_stat_error
: isl_stat_ok
;
529 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),from
),BASE
)(__isl_take EL
*el
)
536 ctx
= FN(EL
,get_ctx
)(el
);
537 list
= FN(LIST(EL
),alloc
)(ctx
, 1);
540 list
= FN(LIST(EL
),add
)(list
, el
);
547 /* Append the elements of "list2" to "list1", where "list1" is known
548 * to have only a single reference and enough room to hold
549 * the extra elements.
551 static __isl_give
LIST(EL
) *FN(LIST(EL
),concat_inplace
)(
552 __isl_take
LIST(EL
) *list1
, __isl_take
LIST(EL
) *list2
)
556 for (i
= 0; i
< list2
->n
; ++i
)
557 list1
= FN(LIST(EL
),add
)(list1
, FN(EL
,copy
)(list2
->p
[i
]));
558 FN(LIST(EL
),free
)(list2
);
562 /* Concatenate "list1" and "list2".
563 * If "list1" has only one reference and has enough room
564 * for the elements of "list2", the add the elements to "list1" itself.
565 * Otherwise, create a new list to store the result.
567 __isl_give
LIST(EL
) *FN(LIST(EL
),concat
)(__isl_take
LIST(EL
) *list1
,
568 __isl_take
LIST(EL
) *list2
)
574 if (!list1
|| !list2
)
577 if (list1
->ref
== 1 && list1
->n
+ list2
->n
<= list1
->size
)
578 return FN(LIST(EL
),concat_inplace
)(list1
, list2
);
580 ctx
= FN(LIST(EL
),get_ctx
)(list1
);
581 res
= FN(LIST(EL
),alloc
)(ctx
, list1
->n
+ list2
->n
);
582 for (i
= 0; i
< list1
->n
; ++i
)
583 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list1
->p
[i
]));
584 for (i
= 0; i
< list2
->n
; ++i
)
585 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list2
->p
[i
]));
587 FN(LIST(EL
),free
)(list1
);
588 FN(LIST(EL
),free
)(list2
);
591 FN(LIST(EL
),free
)(list1
);
592 FN(LIST(EL
),free
)(list2
);
596 __isl_give isl_printer
*CAT(isl_printer_print_
,LIST(BASE
))(
597 __isl_take isl_printer
*p
, __isl_keep
LIST(EL
) *list
)
603 p
= isl_printer_print_str(p
, "(");
604 for (i
= 0; i
< list
->n
; ++i
) {
606 p
= isl_printer_print_str(p
, ",");
607 p
= CAT(isl_printer_print_
,BASE
)(p
, list
->p
[i
]);
609 p
= isl_printer_print_str(p
, ")");
616 void FN(LIST(EL
),dump
)(__isl_keep
LIST(EL
) *list
)
618 isl_printer
*printer
;
623 printer
= isl_printer_to_file(FN(LIST(EL
),get_ctx
)(list
), stderr
);
624 printer
= CAT(isl_printer_print_
,LIST(BASE
))(printer
, list
);
625 printer
= isl_printer_end_line(printer
);
627 isl_printer_free(printer
);