00001 /* 00002 * Copyright 2010 Red Hat Inc., Durham, North Carolina. 00003 * All Rights Reserved. 00004 * 00005 * This library is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU Lesser General Public 00007 * License as published by the Free Software Foundation; either 00008 * version 2.1 of the License, or (at your option) any later version. 00009 * 00010 * This library is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00013 * Lesser General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU Lesser General Public 00016 * License along with this library; if not, write to the Free Software 00017 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 00018 * 00019 * Authors: 00020 * Lukas Kuklinek <lkuklinek@redhat.com> 00021 */ 00022 00023 00024 // topological sort 00025 00026 #include "list.h" 00027 00028 #ifndef OSCAP_TSORT_H_ 00029 #define OSCAP_TSORT_H_ 00030 00031 OSCAP_HIDDEN_START; 00032 00033 // returns nodest with an edge from given node 00034 typedef struct oscap_list* (*oscap_tsort_edge_func)(void *node, void *userdata); 00035 00036 /* 00037 * Topological sort. 00038 * 00039 * Performs a topological sort on a directed graph. 00040 * 00041 * @a edge_func is supposed to return an oscap_list of nodes edges coming from the current node 00042 * (passed to it as an argument) are pointing to. It takes the node as a first argument 00043 * and a pointer passed as @a userdata as a second argument. 00044 * 00045 * The purpose of @a cmp_func is to compare nodes. If it is NULL raw pointer comparison 00046 * is used, which should be good enough in most cases. 00047 * 00048 * Pointer @a output will be set to a list with result. If you want to just check whether 00049 * there is a topological order defined on the graph (i.e. it is an acyclic graph), pass NULL. 00050 * If the function manages to find a topological order of the nodes (returns true), 00051 * it is returned in this variable. Otherwise, it will contain an encountered loop. 00052 * You are responsible to free this list. 00053 * 00054 * @param input set of nodes to sort 00055 * @param output this pointer will be set to the result of the algorithm 00056 * @param edge_func function to return target nodes of outgoing edges from the current one 00057 * @param cmp_func node compasrison function 00058 * @param userdata arbitrary data pointer to be forwarded to the edge_func 00059 * @returns whether the algorithm managed to topologically sort the graph 00060 * @retval true input was sorted, result is in the *output pointer 00061 * @retval false a loop was detected, *output points to the encountered loop 00062 */ 00063 bool oscap_tsort(struct oscap_list *input, struct oscap_list **output, oscap_tsort_edge_func edge_func, oscap_cmp_func cmp_func, void *userdata); 00064 00065 OSCAP_HIDDEN_END; 00066 00067 #endif // OSCAP_TSORT_H_ 00068