/* * Copyright 2008-2009 Katholieke Universiteit Leuven * Copyright 2011 INRIA Saclay * Copyright 2012-2013 Ecole Normale Superieure * Copyright 2017 Sven Verdoolaege * * Use of this software is governed by the MIT license * * Written by Sven Verdoolaege, K.U.Leuven, Departement * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France */ #include <isl_sort.h> #include <isl_tarjan.h> #include <isl/printer.h> #include <isl_list_macro.h> #define xS(TYPE,NAME) … #define S(TYPE,NAME) … isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list) { … } __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n) { … } __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list) { … } __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list) { … } __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list) { … } /* Make sure "list" has room for at least "n" more pieces. * Always return a list with a single reference. * * If there is only one reference to list, we extend it in place. * Otherwise, we create a new LIST(EL) and copy the elements. */ static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n) { … } /* Check that "index" is a valid position in "list". */ static isl_stat FN(LIST(EL),check_index)(__isl_keep LIST(EL) *list, int index) { … } __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list, __isl_take struct EL *el) { … } /* Remove the "n" elements starting at "first" from "list". */ __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list, unsigned first, unsigned n) { … } /* Remove all elements from "list". */ __isl_give LIST(EL) *FN(LIST(EL),clear)(__isl_take LIST(EL) *list) { … } /* Insert "el" at position "pos" in "list". * * If there is only one reference to "list" and if it already has space * for one extra element, we insert it directly into "list". * Otherwise, we create a new list consisting of "el" and copied * elements from "list". */ __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list, unsigned pos, __isl_take struct EL *el) { … } __isl_null LIST(EL) *FN(LIST(EL),free)(__isl_take LIST(EL) *list) { … } /* Return the number of elements in "list". */ isl_size FN(LIST(EL),size)(__isl_keep LIST(EL) *list) { … } /* This is an alternative name for the function above. */ isl_size FN(FN(LIST(EL),n),EL_BASE)(__isl_keep LIST(EL) *list) { … } /* Return the element at position "index" in "list". */ __isl_keep EL *FN(LIST(EL),peek)(__isl_keep LIST(EL) *list, int index) { … } /* Return a copy of the element at position "index" in "list". */ __isl_give EL *FN(LIST(EL),get_at)(__isl_keep LIST(EL) *list, int index) { … } /* This is an alternative name for the function above. */ __isl_give EL *FN(FN(LIST(EL),get),EL_BASE)(__isl_keep LIST(EL) *list, int index) { … } /* Replace the element at position "index" in "list" by "el". */ __isl_give LIST(EL) *FN(LIST(EL),set_at)(__isl_take LIST(EL) *list, int index, __isl_take EL *el) { … } /* This is an alternative name for the function above. */ __isl_give LIST(EL) *FN(FN(LIST(EL),set),EL_BASE)(__isl_take LIST(EL) *list, int index, __isl_take EL *el) { … } /* Return the element at position "index" of "list". * This may be either a copy or the element itself * if there is only one reference to "list". * This allows the element to be modified inplace * if both the list and the element have only a single reference. * The caller is not allowed to modify "list" between * this call to isl_list_*_take_* and a subsequent call * to isl_list_*_restore_*. * The only exception is that isl_list_*_free can be called instead. */ static __isl_give EL *FN(FN(LIST(EL),take),EL_BASE)(__isl_keep LIST(EL) *list, int index) { … } /* Set the element at position "index" of "list" to "el", * where the position may be empty due to a previous call * to isl_list_*_take_*. */ static __isl_give LIST(EL) *FN(FN(LIST(EL),restore),EL_BASE)( __isl_take LIST(EL) *list, int index, __isl_take EL *el) { … } /* Swap the elements of "list" in positions "pos1" and "pos2". */ __isl_give LIST(EL) *FN(LIST(EL),swap)(__isl_take LIST(EL) *list, unsigned pos1, unsigned pos2) { … } /* Reverse the elements of "list". */ __isl_give LIST(EL) *FN(LIST(EL),reverse)(__isl_take LIST(EL) *list) { … } isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list, isl_stat (*fn)(__isl_take EL *el, void *user), void *user) { … } /* Does "test" succeed on every element of "list"? */ isl_bool FN(LIST(EL),every)(__isl_keep LIST(EL) *list, isl_bool (*test)(__isl_keep EL *el, void *user), void *user) { … } /* Replace each element in "list" by the result of calling "fn" * on the element. */ __isl_give LIST(EL) *FN(LIST(EL),map)(__isl_keep LIST(EL) *list, __isl_give EL *(*fn)(__isl_take EL *el, void *user), void *user) { … } /* Internal data structure for isl_*_list_sort. * * "cmp" is the original comparison function. * "user" is a user provided pointer that should be passed to "cmp". */ S(LIST(EL),sort_data) { … }; /* Compare two entries of an isl_*_list based on the user provided * comparison function on pairs of isl_* objects. */ static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user) { … } /* Sort the elements of "list" in ascending order according to * comparison function "cmp". */ __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list, int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user) { … } /* Internal data structure for isl_*_list_foreach_scc. * * "list" is the original list. * "follows" is the user provided callback that defines the edges of the graph. */ S(LIST(EL),foreach_scc_data) { … }; /* Does element i of data->list follow element j? * * Use the user provided callback to find out. */ static isl_bool FN(LIST(EL),follows)(int i, int j, void *user) { … } /* Call "fn" on the sublist of "list" that consists of the elements * with indices specified by the "n" elements of "pos". */ static isl_stat FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *user) { … } /* Call "fn" on each of the strongly connected components (SCCs) of * the graph with as vertices the elements of "list" and * a directed edge from node b to node a iff follows(a, b) * returns 1. follows should return -1 on error. * * If SCC a contains a node i that follows a node j in another SCC b * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a * after being called on SCC b. * * We simply call isl_tarjan_graph_init, extract the SCCs from the result and * call fn on each of them. */ isl_stat FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list, isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *follows_user, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user) { … } __isl_give LIST(EL) *FN(FN(LIST(EL),from),EL_BASE)(__isl_take EL *el) { … } /* This function performs the same operation as isl_*_list_from_*, * but is considered as a function on the element when exported. */ __isl_give LIST(EL) *FN(EL,to_list)(__isl_take EL *el) { … } /* Append the elements of "list2" to "list1", where "list1" is known * to have only a single reference and enough room to hold * the extra elements. */ static __isl_give LIST(EL) *FN(LIST(EL),concat_inplace)( __isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2) { … } /* Concatenate "list1" and "list2". * If "list1" has only one reference and has enough room * for the elements of "list2", the add the elements to "list1" itself. * Otherwise, create a new list to store the result. */ __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2) { … } __isl_give isl_printer *CAT(isl_printer_print_,LIST(EL_BASE))( __isl_take isl_printer *p, __isl_keep LIST(EL) *list) { … } #undef BASE #define BASE … #define PRINT_DUMP_DEFAULT … #include "print_templ.c" #undef PRINT_DUMP_DEFAULT
Codebase Browser
llvm