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 #include <isl_list_macro.h>
22 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
23 #define S(TYPE,NAME) xS(TYPE,NAME)
25 isl_ctx
*FN(LIST(EL
),get_ctx
)(__isl_keep
LIST(EL
) *list
)
27 return list
? list
->ctx
: NULL
;
30 __isl_give
LIST(EL
) *FN(LIST(EL
),alloc
)(isl_ctx
*ctx
, int n
)
35 isl_die(ctx
, isl_error_invalid
,
36 "cannot create list of negative length",
38 list
= isl_alloc(ctx
, LIST(EL
),
39 sizeof(LIST(EL
)) + (n
- 1) * sizeof(struct EL
*));
51 __isl_give
LIST(EL
) *FN(LIST(EL
),copy
)(__isl_keep
LIST(EL
) *list
)
60 __isl_give
LIST(EL
) *FN(LIST(EL
),dup
)(__isl_keep
LIST(EL
) *list
)
68 dup
= FN(LIST(EL
),alloc
)(FN(LIST(EL
),get_ctx
)(list
), list
->n
);
71 for (i
= 0; i
< list
->n
; ++i
)
72 dup
= FN(LIST(EL
),add
)(dup
, FN(EL
,copy
)(list
->p
[i
]));
76 __isl_give
LIST(EL
) *FN(LIST(EL
),cow
)(__isl_take
LIST(EL
) *list
)
84 return FN(LIST(EL
),dup
)(list
);
87 /* Make sure "list" has room for at least "n" more pieces.
88 * Always return a list with a single reference.
90 * If there is only one reference to list, we extend it in place.
91 * Otherwise, we create a new LIST(EL) and copy the elements.
93 static __isl_give
LIST(EL
) *FN(LIST(EL
),grow
)(__isl_take
LIST(EL
) *list
, int n
)
101 if (list
->ref
== 1 && list
->n
+ n
<= list
->size
)
104 ctx
= FN(LIST(EL
),get_ctx
)(list
);
105 new_size
= ((list
->n
+ n
+ 1) * 3) / 2;
106 if (list
->ref
== 1) {
107 res
= isl_realloc(ctx
, list
, LIST(EL
),
108 sizeof(LIST(EL
)) + (new_size
- 1) * sizeof(EL
*));
110 return FN(LIST(EL
),free
)(list
);
111 res
->size
= new_size
;
115 if (list
->n
+ n
<= list
->size
&& list
->size
< new_size
)
116 new_size
= list
->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 /* Check that "index" is a valid position in "list".
131 static isl_stat
FN(LIST(EL
),check_index
)(__isl_keep
LIST(EL
) *list
, int index
)
134 return isl_stat_error
;
135 if (index
< 0 || index
>= list
->n
)
136 isl_die(FN(LIST(EL
),get_ctx
)(list
), isl_error_invalid
,
137 "index out of bounds", return isl_stat_error
);
141 __isl_give
LIST(EL
) *FN(LIST(EL
),add
)(__isl_take
LIST(EL
) *list
,
142 __isl_take
struct EL
*el
)
144 list
= FN(LIST(EL
),grow
)(list
, 1);
147 list
->p
[list
->n
] = el
;
152 FN(LIST(EL
),free
)(list
);
156 /* Remove the "n" elements starting at "first" from "list".
158 __isl_give
LIST(EL
) *FN(LIST(EL
),drop
)(__isl_take
LIST(EL
) *list
,
159 unsigned first
, unsigned n
)
165 if (first
+ n
> list
->n
|| first
+ n
< first
)
166 isl_die(list
->ctx
, isl_error_invalid
,
167 "index out of bounds", return FN(LIST(EL
),free
)(list
));
170 list
= FN(LIST(EL
),cow
)(list
);
173 for (i
= 0; i
< n
; ++i
)
174 FN(EL
,free
)(list
->p
[first
+ i
]);
175 for (i
= first
; i
+ n
< list
->n
; ++i
)
176 list
->p
[i
] = list
->p
[i
+ n
];
181 /* Insert "el" at position "pos" in "list".
183 * If there is only one reference to "list" and if it already has space
184 * for one extra element, we insert it directly into "list".
185 * Otherwise, we create a new list consisting of "el" and copied
186 * elements from "list".
188 __isl_give
LIST(EL
) *FN(LIST(EL
),insert
)(__isl_take
LIST(EL
) *list
,
189 unsigned pos
, __isl_take
struct EL
*el
)
197 ctx
= FN(LIST(EL
),get_ctx
)(list
);
199 isl_die(ctx
, isl_error_invalid
,
200 "index out of bounds", goto error
);
202 if (list
->ref
== 1 && list
->size
> list
->n
) {
203 for (i
= list
->n
; i
> pos
; --i
)
204 list
->p
[i
] = list
->p
[i
- 1];
210 res
= FN(LIST(EL
),alloc
)(ctx
, list
->n
+ 1);
211 for (i
= 0; i
< pos
; ++i
)
212 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
213 res
= FN(LIST(EL
),add
)(res
, el
);
214 for (i
= pos
; i
< list
->n
; ++i
)
215 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list
->p
[i
]));
216 FN(LIST(EL
),free
)(list
);
221 FN(LIST(EL
),free
)(list
);
225 __isl_null
LIST(EL
) *FN(LIST(EL
),free
)(__isl_take
LIST(EL
) *list
)
235 isl_ctx_deref(list
->ctx
);
236 for (i
= 0; i
< list
->n
; ++i
)
237 FN(EL
,free
)(list
->p
[i
]);
243 /* Return the number of elements in "list".
245 isl_size
FN(LIST(EL
),size
)(__isl_keep
LIST(EL
) *list
)
247 return list
? list
->n
: isl_size_error
;
250 /* This is an alternative name for the function above.
252 isl_size
FN(FN(LIST(EL
),n
),EL_BASE
)(__isl_keep
LIST(EL
) *list
)
254 return FN(LIST(EL
),size
)(list
);
257 /* Return the element at position "index" in "list".
259 static __isl_keep EL
*FN(LIST(EL
),peek
)(__isl_keep
LIST(EL
) *list
, int index
)
261 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
263 return list
->p
[index
];
266 /* Return a copy of the element at position "index" in "list".
268 __isl_give EL
*FN(LIST(EL
),get_at
)(__isl_keep
LIST(EL
) *list
, int index
)
270 return FN(EL
,copy
)(FN(LIST(EL
),peek
)(list
, index
));
273 /* This is an alternative name for the function above.
275 __isl_give EL
*FN(FN(LIST(EL
),get
),EL_BASE
)(__isl_keep
LIST(EL
) *list
,
278 return FN(LIST(EL
),get_at
)(list
, index
);
281 /* Replace the element at position "index" in "list" by "el".
283 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),set
),EL_BASE
)(__isl_take
LIST(EL
) *list
,
284 int index
, __isl_take EL
*el
)
288 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
290 if (list
->p
[index
] == el
) {
294 list
= FN(LIST(EL
),cow
)(list
);
297 FN(EL
,free
)(list
->p
[index
]);
302 FN(LIST(EL
),free
)(list
);
306 /* Return the element at position "index" of "list".
307 * This may be either a copy or the element itself
308 * if there is only one reference to "list".
309 * This allows the element to be modified inplace
310 * if both the list and the element have only a single reference.
311 * The caller is not allowed to modify "list" between
312 * this call to isl_list_*_take_* and a subsequent call
313 * to isl_list_*_restore_*.
314 * The only exception is that isl_list_*_free can be called instead.
316 static __isl_give EL
*FN(FN(LIST(EL
),take
),EL_BASE
)(__isl_keep
LIST(EL
) *list
,
321 if (FN(LIST(EL
),check_index
)(list
, index
) < 0)
324 return FN(FN(LIST(EL
),get
),EL_BASE
)(list
, index
);
326 list
->p
[index
] = NULL
;
330 /* Set the element at position "index" of "list" to "el",
331 * where the position may be empty due to a previous call
332 * to isl_list_*_take_*.
334 static __isl_give
LIST(EL
) *FN(FN(LIST(EL
),restore
),EL_BASE
)(
335 __isl_take
LIST(EL
) *list
, int index
, __isl_take EL
*el
)
337 return FN(FN(LIST(EL
),set
),EL_BASE
)(list
, index
, el
);
340 /* Swap the elements of "list" in positions "pos1" and "pos2".
342 __isl_give
LIST(EL
) *FN(LIST(EL
),swap
)(__isl_take
LIST(EL
) *list
,
343 unsigned pos1
, unsigned pos2
)
349 el1
= FN(FN(LIST(EL
),take
),EL_BASE
)(list
, pos1
);
350 el2
= FN(FN(LIST(EL
),take
),EL_BASE
)(list
, pos2
);
351 list
= FN(FN(LIST(EL
),restore
),EL_BASE
)(list
, pos1
, el2
);
352 list
= FN(FN(LIST(EL
),restore
),EL_BASE
)(list
, pos2
, el1
);
356 /* Reverse the elements of "list".
358 __isl_give
LIST(EL
) *FN(LIST(EL
),reverse
)(__isl_take
LIST(EL
) *list
)
362 n
= FN(LIST(EL
),size
)(list
);
363 for (i
= 0; i
< n
- 1 - i
; ++i
)
364 list
= FN(LIST(EL
),swap
)(list
, i
, n
- 1 - i
);
368 isl_stat
FN(LIST(EL
),foreach
)(__isl_keep
LIST(EL
) *list
,
369 isl_stat (*fn
)(__isl_take EL
*el
, void *user
), void *user
)
374 return isl_stat_error
;
376 for (i
= 0; i
< list
->n
; ++i
) {
377 EL
*el
= FN(EL
,copy
)(list
->p
[i
]);
379 return isl_stat_error
;
380 if (fn(el
, user
) < 0)
381 return isl_stat_error
;
387 /* Replace each element in "list" by the result of calling "fn"
390 __isl_give
LIST(EL
) *FN(LIST(EL
),map
)(__isl_keep
LIST(EL
) *list
,
391 __isl_give EL
*(*fn
)(__isl_take EL
*el
, void *user
), void *user
)
399 for (i
= 0; i
< n
; ++i
) {
400 EL
*el
= FN(FN(LIST(EL
),take
),EL_BASE
)(list
, i
);
402 return FN(LIST(EL
),free
)(list
);
404 list
= FN(FN(LIST(EL
),restore
),EL_BASE
)(list
, i
, el
);
410 /* Internal data structure for isl_*_list_sort.
412 * "cmp" is the original comparison function.
413 * "user" is a user provided pointer that should be passed to "cmp".
415 S(LIST(EL
),sort_data
) {
416 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
420 /* Compare two entries of an isl_*_list based on the user provided
421 * comparison function on pairs of isl_* objects.
423 static int FN(LIST(EL
),cmp
)(const void *a
, const void *b
, void *user
)
425 S(LIST(EL
),sort_data
) *data
= user
;
429 return data
->cmp(*el1
, *el2
, data
->user
);
432 /* Sort the elements of "list" in ascending order according to
433 * comparison function "cmp".
435 __isl_give
LIST(EL
) *FN(LIST(EL
),sort
)(__isl_take
LIST(EL
) *list
,
436 int (*cmp
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
), void *user
)
438 S(LIST(EL
),sort_data
) data
= { cmp
, user
};
444 list
= FN(LIST(EL
),cow
)(list
);
448 if (isl_sort(list
->p
, list
->n
, sizeof(list
->p
[0]),
449 &FN(LIST(EL
),cmp
), &data
) < 0)
450 return FN(LIST(EL
),free
)(list
);
455 /* Internal data structure for isl_*_list_foreach_scc.
457 * "list" is the original list.
458 * "follows" is the user provided callback that defines the edges of the graph.
460 S(LIST(EL
),foreach_scc_data
) {
462 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
);
466 /* Does element i of data->list follow element j?
468 * Use the user provided callback to find out.
470 static isl_bool
FN(LIST(EL
),follows
)(int i
, int j
, void *user
)
472 S(LIST(EL
),foreach_scc_data
) *data
= user
;
474 return data
->follows(data
->list
->p
[i
], data
->list
->p
[j
],
478 /* Call "fn" on the sublist of "list" that consists of the elements
479 * with indices specified by the "n" elements of "pos".
481 static isl_stat
FN(LIST(EL
),call_on_scc
)(__isl_keep
LIST(EL
) *list
, int *pos
,
482 int n
, isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *user
)
488 ctx
= FN(LIST(EL
),get_ctx
)(list
);
489 slice
= FN(LIST(EL
),alloc
)(ctx
, n
);
490 for (i
= 0; i
< n
; ++i
) {
493 el
= FN(EL
,copy
)(list
->p
[pos
[i
]]);
494 slice
= FN(LIST(EL
),add
)(slice
, el
);
497 return fn(slice
, user
);
500 /* Call "fn" on each of the strongly connected components (SCCs) of
501 * the graph with as vertices the elements of "list" and
502 * a directed edge from node b to node a iff follows(a, b)
503 * returns 1. follows should return -1 on error.
505 * If SCC a contains a node i that follows a node j in another SCC b
506 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
507 * after being called on SCC b.
509 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
510 * call fn on each of them.
512 isl_stat
FN(LIST(EL
),foreach_scc
)(__isl_keep
LIST(EL
) *list
,
513 isl_bool (*follows
)(__isl_keep EL
*a
, __isl_keep EL
*b
, void *user
),
515 isl_stat (*fn
)(__isl_take
LIST(EL
) *scc
, void *user
), void *fn_user
)
517 S(LIST(EL
),foreach_scc_data
) data
= { list
, follows
, follows_user
};
520 struct isl_tarjan_graph
*g
;
523 return isl_stat_error
;
527 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
529 ctx
= FN(LIST(EL
),get_ctx
)(list
);
531 g
= isl_tarjan_graph_init(ctx
, n
, &FN(LIST(EL
),follows
), &data
);
533 return isl_stat_error
;
539 if (g
->order
[i
] == -1)
540 isl_die(ctx
, isl_error_internal
, "cannot happen",
543 while (g
->order
[i
] != -1) {
546 if (first
== 0 && n
== 0) {
547 isl_tarjan_graph_free(g
);
548 return fn(FN(LIST(EL
),copy
)(list
), fn_user
);
550 if (FN(LIST(EL
),call_on_scc
)(list
, g
->order
+ first
, i
- first
,
556 isl_tarjan_graph_free(g
);
558 return n
> 0 ? isl_stat_error
: isl_stat_ok
;
561 __isl_give
LIST(EL
) *FN(FN(LIST(EL
),from
),EL_BASE
)(__isl_take EL
*el
)
568 ctx
= FN(EL
,get_ctx
)(el
);
569 list
= FN(LIST(EL
),alloc
)(ctx
, 1);
572 list
= FN(LIST(EL
),add
)(list
, el
);
579 /* Append the elements of "list2" to "list1", where "list1" is known
580 * to have only a single reference and enough room to hold
581 * the extra elements.
583 static __isl_give
LIST(EL
) *FN(LIST(EL
),concat_inplace
)(
584 __isl_take
LIST(EL
) *list1
, __isl_take
LIST(EL
) *list2
)
588 for (i
= 0; i
< list2
->n
; ++i
)
589 list1
= FN(LIST(EL
),add
)(list1
, FN(EL
,copy
)(list2
->p
[i
]));
590 FN(LIST(EL
),free
)(list2
);
594 /* Concatenate "list1" and "list2".
595 * If "list1" has only one reference and has enough room
596 * for the elements of "list2", the add the elements to "list1" itself.
597 * Otherwise, create a new list to store the result.
599 __isl_give
LIST(EL
) *FN(LIST(EL
),concat
)(__isl_take
LIST(EL
) *list1
,
600 __isl_take
LIST(EL
) *list2
)
606 if (!list1
|| !list2
)
609 if (list1
->ref
== 1 && list1
->n
+ list2
->n
<= list1
->size
)
610 return FN(LIST(EL
),concat_inplace
)(list1
, list2
);
612 ctx
= FN(LIST(EL
),get_ctx
)(list1
);
613 res
= FN(LIST(EL
),alloc
)(ctx
, list1
->n
+ list2
->n
);
614 for (i
= 0; i
< list1
->n
; ++i
)
615 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list1
->p
[i
]));
616 for (i
= 0; i
< list2
->n
; ++i
)
617 res
= FN(LIST(EL
),add
)(res
, FN(EL
,copy
)(list2
->p
[i
]));
619 FN(LIST(EL
),free
)(list1
);
620 FN(LIST(EL
),free
)(list2
);
623 FN(LIST(EL
),free
)(list1
);
624 FN(LIST(EL
),free
)(list2
);
628 __isl_give isl_printer
*CAT(isl_printer_print_
,LIST(EL_BASE
))(
629 __isl_take isl_printer
*p
, __isl_keep
LIST(EL
) *list
)
635 p
= isl_printer_print_str(p
, "(");
636 for (i
= 0; i
< list
->n
; ++i
) {
638 p
= isl_printer_print_str(p
, ",");
639 p
= CAT(isl_printer_print_
,EL_BASE
)(p
, list
->p
[i
]);
641 p
= isl_printer_print_str(p
, ")");
649 #define BASE LIST(EL_BASE)
651 #define PRINT_DUMP_DEFAULT 0
652 #include "print_templ.c"
653 #undef PRINT_DUMP_DEFAULT