1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.3.1"/>
<title>Open SCAP Library: tsort.h Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">Open SCAP Library
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.3.1 -->
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>Globals</span></a></li>
</ul>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="dir_68267d1309a1af8e8297ef4c3efbcdba.html">src</a></li><li class="navelem"><a class="el" href="dir_fdedb0aba14d44ce9d99bc100e026e6a.html">common</a></li> </ul>
</div>
</div><!-- top -->
<div class="header">
<div class="headertitle">
<div class="title">tsort.h</div> </div>
</div><!--header-->
<div class="contents">
<div class="fragment"><div class="line"><a name="l00001"></a><span class="lineno"> 1</span> <span class="comment">/*</span></div>
<div class="line"><a name="l00002"></a><span class="lineno"> 2</span> <span class="comment"> * Copyright 2010 Red Hat Inc., Durham, North Carolina.</span></div>
<div class="line"><a name="l00003"></a><span class="lineno"> 3</span> <span class="comment"> * All Rights Reserved.</span></div>
<div class="line"><a name="l00004"></a><span class="lineno"> 4</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00005"></a><span class="lineno"> 5</span> <span class="comment"> * This library is free software; you can redistribute it and/or</span></div>
<div class="line"><a name="l00006"></a><span class="lineno"> 6</span> <span class="comment"> * modify it under the terms of the GNU Lesser General Public</span></div>
<div class="line"><a name="l00007"></a><span class="lineno"> 7</span> <span class="comment"> * License as published by the Free Software Foundation; either</span></div>
<div class="line"><a name="l00008"></a><span class="lineno"> 8</span> <span class="comment"> * version 2.1 of the License, or (at your option) any later version.</span></div>
<div class="line"><a name="l00009"></a><span class="lineno"> 9</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00010"></a><span class="lineno"> 10</span> <span class="comment"> * This library is distributed in the hope that it will be useful, </span></div>
<div class="line"><a name="l00011"></a><span class="lineno"> 11</span> <span class="comment"> * but WITHOUT ANY WARRANTY; without even the implied warranty of</span></div>
<div class="line"><a name="l00012"></a><span class="lineno"> 12</span> <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span></div>
<div class="line"><a name="l00013"></a><span class="lineno"> 13</span> <span class="comment"> * Lesser General Public License for more details.</span></div>
<div class="line"><a name="l00014"></a><span class="lineno"> 14</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00015"></a><span class="lineno"> 15</span> <span class="comment"> * You should have received a copy of the GNU Lesser General Public</span></div>
<div class="line"><a name="l00016"></a><span class="lineno"> 16</span> <span class="comment"> * License along with this library; if not, write to the Free Software </span></div>
<div class="line"><a name="l00017"></a><span class="lineno"> 17</span> <span class="comment"> * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA</span></div>
<div class="line"><a name="l00018"></a><span class="lineno"> 18</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00019"></a><span class="lineno"> 19</span> <span class="comment"> * Authors:</span></div>
<div class="line"><a name="l00020"></a><span class="lineno"> 20</span> <span class="comment"> * Lukas Kuklinek <lkuklinek@redhat.com></span></div>
<div class="line"><a name="l00021"></a><span class="lineno"> 21</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00022"></a><span class="lineno"> 22</span> </div>
<div class="line"><a name="l00023"></a><span class="lineno"> 23</span> </div>
<div class="line"><a name="l00024"></a><span class="lineno"> 24</span> <span class="comment">// topological sort</span></div>
<div class="line"><a name="l00025"></a><span class="lineno"> 25</span> </div>
<div class="line"><a name="l00026"></a><span class="lineno"> 26</span> <span class="preprocessor">#include "list.h"</span></div>
<div class="line"><a name="l00027"></a><span class="lineno"> 27</span> </div>
<div class="line"><a name="l00028"></a><span class="lineno"> 28</span> <span class="preprocessor">#ifndef OSCAP_TSORT_H_</span></div>
<div class="line"><a name="l00029"></a><span class="lineno"> 29</span> <span class="preprocessor"></span><span class="preprocessor">#define OSCAP_TSORT_H_</span></div>
<div class="line"><a name="l00030"></a><span class="lineno"> 30</span> <span class="preprocessor"></span></div>
<div class="line"><a name="l00031"></a><span class="lineno"> 31</span> OSCAP_HIDDEN_START;</div>
<div class="line"><a name="l00032"></a><span class="lineno"> 32</span> </div>
<div class="line"><a name="l00033"></a><span class="lineno"> 33</span> <span class="comment">// returns nodest with an edge from given node</span></div>
<div class="line"><a name="l00034"></a><span class="lineno"> 34</span> <span class="keyword">typedef</span> <span class="keyword">struct </span><a class="code" href="structoscap__list.html">oscap_list</a>* (*oscap_tsort_edge_func)(<span class="keywordtype">void</span> *node, <span class="keywordtype">void</span> *userdata);</div>
<div class="line"><a name="l00035"></a><span class="lineno"> 35</span> </div>
<div class="line"><a name="l00036"></a><span class="lineno"> 36</span> <span class="comment">/*</span></div>
<div class="line"><a name="l00037"></a><span class="lineno"> 37</span> <span class="comment"> * Topological sort.</span></div>
<div class="line"><a name="l00038"></a><span class="lineno"> 38</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00039"></a><span class="lineno"> 39</span> <span class="comment"> * Performs a topological sort on a directed graph.</span></div>
<div class="line"><a name="l00040"></a><span class="lineno"> 40</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00041"></a><span class="lineno"> 41</span> <span class="comment"> * @a edge_func is supposed to return an oscap_list of nodes edges coming from the current node</span></div>
<div class="line"><a name="l00042"></a><span class="lineno"> 42</span> <span class="comment"> * (passed to it as an argument) are pointing to. It takes the node as a first argument</span></div>
<div class="line"><a name="l00043"></a><span class="lineno"> 43</span> <span class="comment"> * and a pointer passed as @a userdata as a second argument.</span></div>
<div class="line"><a name="l00044"></a><span class="lineno"> 44</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00045"></a><span class="lineno"> 45</span> <span class="comment"> * The purpose of @a cmp_func is to compare nodes. If it is NULL raw pointer comparison</span></div>
<div class="line"><a name="l00046"></a><span class="lineno"> 46</span> <span class="comment"> * is used, which should be good enough in most cases.</span></div>
<div class="line"><a name="l00047"></a><span class="lineno"> 47</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00048"></a><span class="lineno"> 48</span> <span class="comment"> * Pointer @a output will be set to a list with result. If you want to just check whether</span></div>
<div class="line"><a name="l00049"></a><span class="lineno"> 49</span> <span class="comment"> * there is a topological order defined on the graph (i.e. it is an acyclic graph), pass NULL.</span></div>
<div class="line"><a name="l00050"></a><span class="lineno"> 50</span> <span class="comment"> * If the function manages to find a topological order of the nodes (returns true),</span></div>
<div class="line"><a name="l00051"></a><span class="lineno"> 51</span> <span class="comment"> * it is returned in this variable. Otherwise, it will contain an encountered loop.</span></div>
<div class="line"><a name="l00052"></a><span class="lineno"> 52</span> <span class="comment"> * You are responsible to free this list.</span></div>
<div class="line"><a name="l00053"></a><span class="lineno"> 53</span> <span class="comment"> *</span></div>
<div class="line"><a name="l00054"></a><span class="lineno"> 54</span> <span class="comment"> * @param input set of nodes to sort</span></div>
<div class="line"><a name="l00055"></a><span class="lineno"> 55</span> <span class="comment"> * @param output this pointer will be set to the result of the algorithm</span></div>
<div class="line"><a name="l00056"></a><span class="lineno"> 56</span> <span class="comment"> * @param edge_func function to return target nodes of outgoing edges from the current one</span></div>
<div class="line"><a name="l00057"></a><span class="lineno"> 57</span> <span class="comment"> * @param cmp_func node compasrison function</span></div>
<div class="line"><a name="l00058"></a><span class="lineno"> 58</span> <span class="comment"> * @param userdata arbitrary data pointer to be forwarded to the edge_func</span></div>
<div class="line"><a name="l00059"></a><span class="lineno"> 59</span> <span class="comment"> * @returns whether the algorithm managed to topologically sort the graph</span></div>
<div class="line"><a name="l00060"></a><span class="lineno"> 60</span> <span class="comment"> * @retval true input was sorted, result is in the *output pointer</span></div>
<div class="line"><a name="l00061"></a><span class="lineno"> 61</span> <span class="comment"> * @retval false a loop was detected, *output points to the encountered loop</span></div>
<div class="line"><a name="l00062"></a><span class="lineno"> 62</span> <span class="comment"> */</span></div>
<div class="line"><a name="l00063"></a><span class="lineno"> 63</span> <span class="keywordtype">bool</span> oscap_tsort(<span class="keyword">struct</span> <a class="code" href="structoscap__list.html">oscap_list</a> *input, <span class="keyword">struct</span> <a class="code" href="structoscap__list.html">oscap_list</a> **output, oscap_tsort_edge_func edge_func, oscap_cmp_func cmp_func, <span class="keywordtype">void</span> *userdata);</div>
<div class="line"><a name="l00064"></a><span class="lineno"> 64</span> </div>
<div class="line"><a name="l00065"></a><span class="lineno"> 65</span> OSCAP_HIDDEN_END;</div>
<div class="line"><a name="l00066"></a><span class="lineno"> 66</span> </div>
<div class="line"><a name="l00067"></a><span class="lineno"> 67</span> <span class="preprocessor">#endif // OSCAP_TSORT_H_</span></div>
<div class="line"><a name="l00068"></a><span class="lineno"> 68</span> <span class="preprocessor"></span></div>
</div><!-- fragment --></div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by  <a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.3.1
</small></address>
</body>
</html>
|
