OpenCoverage

tsort.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/src/tsort.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* tsort - topological sort.-
2 Copyright (C) 1998-2018 Free Software Foundation, Inc.-
3-
4 This program is free software: you can redistribute it and/or modify-
5 it under the terms of the GNU General Public License as published by-
6 the Free Software Foundation, either version 3 of the License, or-
7 (at your option) any later version.-
8-
9 This program is distributed in the hope that it will be useful,-
10 but WITHOUT ANY WARRANTY; without even the implied warranty of-
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the-
12 GNU General Public License for more details.-
13-
14 You should have received a copy of the GNU General Public License-
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */-
16-
17/* Written by Mark Kettenis <kettenis@phys.uva.nl>. */-
18-
19/* The topological sort is done according to Algorithm T (Topological-
20 sort) in Donald E. Knuth, The Art of Computer Programming, Volume-
21 1/Fundamental Algorithms, page 262. */-
22-
23#include <config.h>-
24-
25#include <assert.h>-
26#include <getopt.h>-
27#include <sys/types.h>-
28-
29#include "system.h"-
30#include "long-options.h"-
31#include "die.h"-
32#include "error.h"-
33#include "fadvise.h"-
34#include "readtokens.h"-
35#include "stdio--.h"-
36#include "quote.h"-
37-
38/* The official name of this program (e.g., no 'g' prefix). */-
39#define PROGRAM_NAME "tsort"-
40-
41#define AUTHORS proper_name ("Mark Kettenis")-
42-
43static struct option const long_options[] =-
44{-
45 {NULL, 0, NULL, 0}-
46};-
47-
48/* Token delimiters when reading from a file. */-
49#define DELIM " \t\n"-
50-
51/* Members of the list of successors. */-
52struct successor-
53{-
54 struct item *suc;-
55 struct successor *next;-
56};-
57-
58/* Each string is held in core as the head of a list of successors. */-
59struct item-
60{-
61 const char *str;-
62 struct item *left, *right;-
63 int balance; /* -1, 0, or +1 */-
64 size_t count;-
65 struct item *qlink;-
66 struct successor *top;-
67};-
68-
69/* The head of the sorted list. */-
70static struct item *head = NULL;-
71-
72/* The tail of the list of 'zeros', strings that have no predecessors. */-
73static struct item *zeros = NULL;-
74-
75/* Used for loop detection. */-
76static struct item *loop = NULL;-
77-
78/* The number of strings to sort. */-
79static size_t n_strings = 0;-
80-
81void-
82usage (int status)-
83{-
84 if (status != EXIT_SUCCESS)
status != 0Description
TRUEevaluated 4 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 3 times by 1 test
Evaluated by:
  • tsort
3-4
85 emit_try_help ();
executed 4 times by 1 test: end of block
Executed by:
  • tsort
4
86 else-
87 {-
88 printf (_("\-
89Usage: %s [OPTION] [FILE]\n\-
90Write totally ordered list consistent with the partial ordering in FILE.\n\-
91"), program_name);-
92-
93 emit_stdin_note ();-
94-
95 fputs (_("\-
96\n\-
97"), stdout);-
98 fputs (HELP_OPTION_DESCRIPTION, stdout);-
99 fputs (VERSION_OPTION_DESCRIPTION, stdout);-
100 emit_ancillary_info (PROGRAM_NAME);-
101 }
executed 3 times by 1 test: end of block
Executed by:
  • tsort
3
102-
103 exit (status);
executed 7 times by 1 test: exit (status);
Executed by:
  • tsort
7
104}-
105-
106/* Create a new item/node for STR. */-
107static struct item *-
108new_item (const char *str)-
109{-
110 struct item *k = xmalloc (sizeof *k);-
111-
112 k->str = (str ? xstrdup (str): NULL);
strDescription
TRUEevaluated 57 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 10 times by 1 test
Evaluated by:
  • tsort
10-57
113 k->left = k->right = NULL;-
114 k->balance = 0;-
115-
116 /* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */-
117 k->count = 0;-
118 k->qlink = NULL;-
119 k->top = NULL;-
120-
121 return k;
executed 67 times by 1 test: return k;
Executed by:
  • tsort
67
122}-
123-
124/* Search binary tree rooted at *ROOT for STR. Allocate a new tree if-
125 *ROOT is NULL. Insert a node/item for STR if not found. Return-
126 the node/item found/created for STR.-
127-
128 This is done according to Algorithm A (Balanced tree search and-
129 insertion) in Donald E. Knuth, The Art of Computer Programming,-
130 Volume 3/Searching and Sorting, pages 455--457. */-
131-
132static struct item *-
133search_item (struct item *root, const char *str)-
134{-
135 struct item *p, *q, *r, *s, *t;-
136 int a;-
137-
138 assert (root);-
139-
140 /* Make sure the tree is not empty, since that is what the algorithm-
141 below expects. */-
142 if (root->right == NULL)
root->right == ((void *)0)Description
TRUEevaluated 10 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 85 times by 1 test
Evaluated by:
  • tsort
10-85
143 return (root->right = new_item (str));
executed 10 times by 1 test: return (root->right = new_item (str));
Executed by:
  • tsort
10
144-
145 /* A1. Initialize. */-
146 t = root;-
147 s = p = root->right;-
148-
149 while (true)-
150 {-
151 /* A2. Compare. */-
152 a = strcmp (str, p->str);
never executed: __result = (((const unsigned char *) (const char *) ( str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( p->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
153 if (a == 0)
a == 0Description
TRUEevaluated 38 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 180 times by 1 test
Evaluated by:
  • tsort
38-180
154 return p;
executed 38 times by 1 test: return p;
Executed by:
  • tsort
38
155-
156 /* A3 & A4. Move left & right. */-
157 if (a < 0)
a < 0Description
TRUEevaluated 22 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 158 times by 1 test
Evaluated by:
  • tsort
22-158
158 q = p->left;
executed 22 times by 1 test: q = p->left;
Executed by:
  • tsort
22
159 else-
160 q = p->right;
executed 158 times by 1 test: q = p->right;
Executed by:
  • tsort
158
161-
162 if (q == NULL)
q == ((void *)0)Description
TRUEevaluated 47 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 133 times by 1 test
Evaluated by:
  • tsort
47-133
163 {-
164 /* A5. Insert. */-
165 q = new_item (str);-
166-
167 /* A3 & A4. (continued). */-
168 if (a < 0)
a < 0Description
TRUEevaluated 7 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 40 times by 1 test
Evaluated by:
  • tsort
7-40
169 p->left = q;
executed 7 times by 1 test: p->left = q;
Executed by:
  • tsort
7
170 else-
171 p->right = q;
executed 40 times by 1 test: p->right = q;
Executed by:
  • tsort
40
172-
173 /* A6. Adjust balance factors. */-
174 assert (!STREQ (str, s->str));
never executed: __result = (((const unsigned char *) (const char *) ( str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( s->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
175 if (strcmp (str, s->str) < 0)
never executed: __result = (((const unsigned char *) (const char *) ( str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( s->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
__extension__ ...r )))); }) < 0Description
TRUEevaluated 6 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 41 times by 1 test
Evaluated by:
  • tsort
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0-41
176 {-
177 r = p = s->left;-
178 a = -1;-
179 }
executed 6 times by 1 test: end of block
Executed by:
  • tsort
6
180 else-
181 {-
182 r = p = s->right;-
183 a = 1;-
184 }
executed 41 times by 1 test: end of block
Executed by:
  • tsort
41
185-
186 while (p != q)
p != qDescription
TRUEevaluated 50 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 47 times by 1 test
Evaluated by:
  • tsort
47-50
187 {-
188 assert (!STREQ (str, p->str));
never executed: __result = (((const unsigned char *) (const char *) ( str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( p->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
189 if (strcmp (str, p->str) < 0)
never executed: __result = (((const unsigned char *) (const char *) ( str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( p->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
__extension__ ...r )))); }) < 0Description
TRUEevaluated 6 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 44 times by 1 test
Evaluated by:
  • tsort
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0-44
190 {-
191 p->balance = -1;-
192 p = p->left;-
193 }
executed 6 times by 1 test: end of block
Executed by:
  • tsort
6
194 else-
195 {-
196 p->balance = 1;-
197 p = p->right;-
198 }
executed 44 times by 1 test: end of block
Executed by:
  • tsort
44
199 }-
200-
201 /* A7. Balancing act. */-
202 if (s->balance == 0 || s->balance == -a)
s->balance == 0Description
TRUEevaluated 19 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 28 times by 1 test
Evaluated by:
  • tsort
s->balance == -aDescription
TRUEevaluated 3 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 25 times by 1 test
Evaluated by:
  • tsort
3-28
203 {-
204 s->balance += a;-
205 return q;
executed 22 times by 1 test: return q;
Executed by:
  • tsort
22
206 }-
207-
208 if (r->balance == a)
r->balance == aDescription
TRUEevaluated 21 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 4 times by 1 test
Evaluated by:
  • tsort
4-21
209 {-
210 /* A8. Single Rotation. */-
211 p = r;-
212 if (a < 0)
a < 0Description
TRUEnever evaluated
FALSEevaluated 21 times by 1 test
Evaluated by:
  • tsort
0-21
213 {-
214 s->left = r->right;-
215 r->right = s;-
216 }
never executed: end of block
0
217 else-
218 {-
219 s->right = r->left;-
220 r->left = s;-
221 }
executed 21 times by 1 test: end of block
Executed by:
  • tsort
21
222 s->balance = r->balance = 0;-
223 }
executed 21 times by 1 test: end of block
Executed by:
  • tsort
21
224 else-
225 {-
226 /* A9. Double rotation. */-
227 if (a < 0)
a < 0Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2
228 {-
229 p = r->right;-
230 r->right = p->left;-
231 p->left = r;-
232 s->left = p->right;-
233 p->right = s;-
234 }
executed 2 times by 1 test: end of block
Executed by:
  • tsort
2
235 else-
236 {-
237 p = r->left;-
238 r->left = p->right;-
239 p->right = r;-
240 s->right = p->left;-
241 p->left = s;-
242 }
executed 2 times by 1 test: end of block
Executed by:
  • tsort
2
243-
244 s->balance = 0;-
245 r->balance = 0;-
246 if (p->balance == a)
p->balance == aDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • tsort
FALSEevaluated 3 times by 1 test
Evaluated by:
  • tsort
1-3
247 s->balance = -a;
executed 1 time by 1 test: s->balance = -a;
Executed by:
  • tsort
1
248 else if (p->balance == -a)
p->balance == -aDescription
TRUEnever evaluated
FALSEevaluated 3 times by 1 test
Evaluated by:
  • tsort
0-3
249 r->balance = a;
never executed: r->balance = a;
0
250 p->balance = 0;-
251 }
executed 4 times by 1 test: end of block
Executed by:
  • tsort
4
252-
253 /* A10. Finishing touch. */-
254 if (s == t->right)
s == t->rightDescription
TRUEevaluated 24 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 1 time by 1 test
Evaluated by:
  • tsort
1-24
255 t->right = p;
executed 24 times by 1 test: t->right = p;
Executed by:
  • tsort
24
256 else-
257 t->left = p;
executed 1 time by 1 test: t->left = p;
Executed by:
  • tsort
1
258-
259 return q;
executed 25 times by 1 test: return q;
Executed by:
  • tsort
25
260 }-
261-
262 /* A3 & A4. (continued). */-
263 if (q->balance)
q->balanceDescription
TRUEevaluated 35 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 98 times by 1 test
Evaluated by:
  • tsort
35-98
264 {-
265 t = p;-
266 s = q;-
267 }
executed 35 times by 1 test: end of block
Executed by:
  • tsort
35
268-
269 p = q;-
270 }
executed 133 times by 1 test: end of block
Executed by:
  • tsort
133
271-
272 /* NOTREACHED */-
273}
never executed: end of block
0
274-
275/* Record the fact that J precedes K. */-
276-
277static void-
278record_relation (struct item *j, struct item *k)-
279{-
280 struct successor *p;-
281-
282 if (!STREQ (j->str, k->str))
never executed: __result = (((const unsigned char *) (const char *) ( j->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( k->str ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
!( __extension...)))); }) == 0)Description
TRUEevaluated 44 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 3 times by 1 test
Evaluated by:
  • tsort
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0-44
283 {-
284 k->count++;-
285 p = xmalloc (sizeof *p);-
286 p->suc = k;-
287 p->next = j->top;-
288 j->top = p;-
289 }
executed 44 times by 1 test: end of block
Executed by:
  • tsort
44
290}
executed 47 times by 1 test: end of block
Executed by:
  • tsort
47
291-
292static bool-
293count_items (struct item *unused _GL_UNUSED)-
294{-
295 n_strings++;-
296 return false;
executed 56 times by 1 test: return 0 ;
Executed by:
  • tsort
56
297}-
298-
299static bool-
300scan_zeros (struct item *k)-
301{-
302 /* Ignore strings that have already been printed. */-
303 if (k->count == 0 && k->str)
k->count == 0Description
TRUEevaluated 16 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 46 times by 1 test
Evaluated by:
  • tsort
k->strDescription
TRUEevaluated 16 times by 1 test
Evaluated by:
  • tsort
FALSEnever evaluated
0-46
304 {-
305 if (head == NULL)
head == ((void *)0)Description
TRUEevaluated 9 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 7 times by 1 test
Evaluated by:
  • tsort
7-9
306 head = k;
executed 9 times by 1 test: head = k;
Executed by:
  • tsort
9
307 else-
308 zeros->qlink = k;
executed 7 times by 1 test: zeros->qlink = k;
Executed by:
  • tsort
7
309-
310 zeros = k;-
311 }
executed 16 times by 1 test: end of block
Executed by:
  • tsort
16
312-
313 return false;
executed 62 times by 1 test: return 0 ;
Executed by:
  • tsort
62
314}-
315-
316/* Try to detect the loop. If we have detected that K is part of a-
317 loop, print the loop on standard error, remove a relation to break-
318 the loop, and return true.-
319-
320 The loop detection strategy is as follows: Realise that what we're-
321 dealing with is essentially a directed graph. If we find an item-
322 that is part of a graph that contains a cycle we traverse the graph-
323 in backwards direction. In general there is no unique way to do-
324 this, but that is no problem. If we encounter an item that we have-
325 encountered before, we know that we've found a cycle. All we have-
326 to do now is retrace our steps, printing out the items until we-
327 encounter that item again. (This is not necessarily the item that-
328 we started from originally.) Since the order in which the items-
329 are stored in the tree is not related to the specified partial-
330 ordering, we may need to walk the tree several times before the-
331 loop has completely been constructed. If the loop was found, the-
332 global variable LOOP will be NULL. */-
333-
334static bool-
335detect_loop (struct item *k)-
336{-
337 if (k->count > 0)
k->count > 0Description
TRUEevaluated 11 times by 1 test
Evaluated by:
  • tsort
FALSEnever evaluated
0-11
338 {-
339 /* K does not have to be part of a cycle. It is however part of-
340 a graph that contains a cycle. */-
341-
342 if (loop == NULL)
loop == ((void *)0)Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 9 times by 1 test
Evaluated by:
  • tsort
2-9
343 /* Start traversing the graph at K. */-
344 loop = k;
executed 2 times by 1 test: loop = k;
Executed by:
  • tsort
2
345 else-
346 {-
347 struct successor **p = &k->top;-
348-
349 while (*p)
*pDescription
TRUEevaluated 8 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 3 times by 1 test
Evaluated by:
  • tsort
3-8
350 {-
351 if ((*p)->suc == loop)
(*p)->suc == loopDescription
TRUEevaluated 6 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2-6
352 {-
353 if (k->qlink)
k->qlinkDescription
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 4 times by 1 test
Evaluated by:
  • tsort
2-4
354 {-
355 /* We have found a loop. Retrace our steps. */-
356 while (loop)
loopDescription
TRUEevaluated 4 times by 1 test
Evaluated by:
  • tsort
FALSEnever evaluated
0-4
357 {-
358 struct item *tmp = loop->qlink;-
359-
360 error (0, 0, "%s", (loop->str));-
361-
362 /* Until we encounter K again. */-
363 if (loop == k)
loop == kDescription
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2
364 {-
365 /* Remove relation. */-
366 (*p)->suc->count--;-
367 *p = (*p)->next;-
368 break;
executed 2 times by 1 test: break;
Executed by:
  • tsort
2
369 }-
370-
371 /* Tidy things up since we might have to-
372 detect another loop. */-
373 loop->qlink = NULL;-
374 loop = tmp;-
375 }
executed 2 times by 1 test: end of block
Executed by:
  • tsort
2
376-
377 while (loop)
loopDescription
TRUEevaluated 4 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2-4
378 {-
379 struct item *tmp = loop->qlink;-
380-
381 loop->qlink = NULL;-
382 loop = tmp;-
383 }
executed 4 times by 1 test: end of block
Executed by:
  • tsort
4
384-
385 /* Since we have found the loop, stop walking-
386 the tree. */-
387 return true;
executed 2 times by 1 test: return 1 ;
Executed by:
  • tsort
2
388 }-
389 else-
390 {-
391 k->qlink = loop;-
392 loop = k;-
393 break;
executed 4 times by 1 test: break;
Executed by:
  • tsort
4
394 }-
395 }-
396-
397 p = &(*p)->next;-
398 }
executed 2 times by 1 test: end of block
Executed by:
  • tsort
2
399 }
executed 7 times by 1 test: end of block
Executed by:
  • tsort
7
400 }-
401-
402 return false;
executed 9 times by 1 test: return 0 ;
Executed by:
  • tsort
9
403}-
404-
405/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.-
406 Stop when ACTION returns true. */-
407-
408static bool-
409recurse_tree (struct item *root, bool (*action) (struct item *))-
410{-
411 if (root->left == NULL && root->right == NULL)
root->left == ((void *)0)Description
TRUEevaluated 81 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 48 times by 1 test
Evaluated by:
  • tsort
root->right == ((void *)0)Description
TRUEevaluated 69 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 12 times by 1 test
Evaluated by:
  • tsort
12-81
412 return (*action) (root);
executed 69 times by 1 test: return (*action) (root);
Executed by:
  • tsort
69
413 else-
414 {-
415 if (root->left != NULL)
root->left != ((void *)0)Description
TRUEevaluated 48 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 12 times by 1 test
Evaluated by:
  • tsort
12-48
416 if (recurse_tree (root->left, action))
recurse_tree (...>left, action)Description
TRUEnever evaluated
FALSEevaluated 48 times by 1 test
Evaluated by:
  • tsort
0-48
417 return true;
never executed: return 1 ;
0
418 if ((*action) (root))
(*action) (root)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • tsort
FALSEevaluated 59 times by 1 test
Evaluated by:
  • tsort
1-59
419 return true;
executed 1 time by 1 test: return 1 ;
Executed by:
  • tsort
1
420 if (root->right != NULL)
root->right != ((void *)0)Description
TRUEevaluated 57 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2-57
421 if (recurse_tree (root->right, action))
recurse_tree (...right, action)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • tsort
FALSEevaluated 56 times by 1 test
Evaluated by:
  • tsort
1-56
422 return true;
executed 1 time by 1 test: return 1 ;
Executed by:
  • tsort
1
423 }
executed 58 times by 1 test: end of block
Executed by:
  • tsort
58
424-
425 return false;
executed 58 times by 1 test: return 0 ;
Executed by:
  • tsort
58
426}-
427-
428/* Walk the tree specified by the head ROOT, calling ACTION for-
429 each node. */-
430-
431static void-
432walk_tree (struct item *root, bool (*action) (struct item *))-
433{-
434 if (root->right)
root->rightDescription
TRUEevaluated 24 times by 1 test
Evaluated by:
  • tsort
FALSEnever evaluated
0-24
435 recurse_tree (root->right, action);
executed 24 times by 1 test: recurse_tree (root->right, action);
Executed by:
  • tsort
24
436}
executed 24 times by 1 test: end of block
Executed by:
  • tsort
24
437-
438/* Do a topological sort on FILE. Return true if successful. */-
439-
440static bool-
441tsort (const char *file)-
442{-
443 bool ok = true;-
444 struct item *root;-
445 struct item *j = NULL;-
446 struct item *k = NULL;-
447 token_buffer tokenbuffer;-
448 bool is_stdin = STREQ (file, "-");
never executed: __result = (((const unsigned char *) (const char *) ( file ))[3] - __s2[3]);
never executed: end of block
never executed: end of block
never executed: __result = (((const unsigned char *) (const char *) ( "-" ))[3] - __s2[3]);
never executed: end of block
executed 2 times by 1 test: end of block
Executed by:
  • tsort
__s1_len > 0Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 1Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s1_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 0Description
TRUEevaluated 10 times by 1 test
Evaluated by:
  • tsort
FALSEnever evaluated
__result == 0Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 8 times by 1 test
Evaluated by:
  • tsort
__s2_len > 1Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
__s2_len > 2Description
TRUEnever evaluated
FALSEnever evaluated
__result == 0Description
TRUEnever evaluated
FALSEnever evaluated
0-10
449-
450 /* Intialize the head of the tree will hold the strings we're sorting. */-
451 root = new_item (NULL);-
452-
453 if (!is_stdin && ! freopen (file, "r", stdin))
!is_stdinDescription
TRUEevaluated 8 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
! freopen_safe..., "r", stdin )Description
TRUEnever evaluated
FALSEevaluated 8 times by 1 test
Evaluated by:
  • tsort
0-8
454 die (EXIT_FAILURE, errno, "%s", quotef (file));
never executed: ((!!sizeof (struct { _Static_assert ( 1 , "verify_expr (" "1" ", " "(error (1, (*__errno_location ()), \"%s\", quotearg_n_style_colon (0, shell_escape_quoting_style, file)), assume (false))" ")"); int _gl_dummy; })) ? ((error ( 1 , (*__errno_location ()) ...e_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ()))) : ((error ( 1 , (*__errno_location ()) , "%s", quotearg_n_style_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ()))));
0
455-
456 fadvise (stdin, FADVISE_SEQUENTIAL);-
457-
458 init_tokenbuffer (&tokenbuffer);-
459-
460 while (1)-
461 {-
462 /* T2. Next Relation. */-
463 size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer);-
464 if (len == (size_t) -1)
len == (size_t) -1Description
TRUEevaluated 10 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 95 times by 1 test
Evaluated by:
  • tsort
10-95
465 break;
executed 10 times by 1 test: break;
Executed by:
  • tsort
10
466-
467 assert (len != 0);-
468-
469 k = search_item (root, tokenbuffer.buffer);-
470 if (j)
jDescription
TRUEevaluated 47 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 48 times by 1 test
Evaluated by:
  • tsort
47-48
471 {-
472 /* T3. Record the relation. */-
473 record_relation (j, k);-
474 k = NULL;-
475 }
executed 47 times by 1 test: end of block
Executed by:
  • tsort
47
476-
477 j = k;-
478 }
executed 95 times by 1 test: end of block
Executed by:
  • tsort
95
479-
480 if (k != NULL)
k != ((void *)0)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • tsort
FALSEevaluated 9 times by 1 test
Evaluated by:
  • tsort
1-9
481 die (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"),
executed 1 time by 1 test: ((!!sizeof (struct { _Static_assert ( 1 , "verify_expr (" "1" ", " "(error (1, 0, dcgettext (((void *)0), \"%s: input contains an odd number of tokens\", 5), quotearg_n_style_colon (0, shell_escape_quoting_style, file)), assume (false))" ")"); int _gl_dum...( 0 ) ? (void) 0 : __builtin_unreachable ()))) : ((error ( 1 , 0, dcgettext (((void *)0), "%s: input contains an odd number of tokens" , 5) , quotearg_n_style_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ())))) ;
Executed by:
  • tsort
1
482 quotef (file));
executed 1 time by 1 test: ((!!sizeof (struct { _Static_assert ( 1 , "verify_expr (" "1" ", " "(error (1, 0, dcgettext (((void *)0), \"%s: input contains an odd number of tokens\", 5), quotearg_n_style_colon (0, shell_escape_quoting_style, file)), assume (false))" ")"); int _gl_dum...( 0 ) ? (void) 0 : __builtin_unreachable ()))) : ((error ( 1 , 0, dcgettext (((void *)0), "%s: input contains an odd number of tokens" , 5) , quotearg_n_style_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ())))) ;
Executed by:
  • tsort
1
483-
484 /* T1. Initialize (N <- n). */-
485 walk_tree (root, count_items);-
486-
487 while (n_strings > 0)
n_strings > 0Description
TRUEevaluated 11 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 9 times by 1 test
Evaluated by:
  • tsort
9-11
488 {-
489 /* T4. Scan for zeros. */-
490 walk_tree (root, scan_zeros);-
491-
492 while (head)
headDescription
TRUEevaluated 56 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 11 times by 1 test
Evaluated by:
  • tsort
11-56
493 {-
494 struct successor *p = head->top;-
495-
496 /* T5. Output front of queue. */-
497 puts (head->str);-
498#ifdef lint-
499 /* suppress valgrind "definitely lost" warnings. */-
500 void *head_str = (void *) head->str;-
501 free (head_str);-
502#endif-
503 head->str = NULL; /* Avoid printing the same string twice. */-
504 n_strings--;-
505-
506 /* T6. Erase relations. */-
507 while (p)
pDescription
TRUEevaluated 42 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 56 times by 1 test
Evaluated by:
  • tsort
42-56
508 {-
509 p->suc->count--;-
510 if (p->suc->count == 0)
p->suc->count == 0Description
TRUEevaluated 40 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2-40
511 {-
512 zeros->qlink = p->suc;-
513 zeros = p->suc;-
514 }
executed 40 times by 1 test: end of block
Executed by:
  • tsort
40
515-
516 p = p->next;-
517 }
executed 42 times by 1 test: end of block
Executed by:
  • tsort
42
518-
519 /* T7. Remove from queue. */-
520 head = head->qlink;-
521 }
executed 56 times by 1 test: end of block
Executed by:
  • tsort
56
522-
523 /* T8. End of process. */-
524 if (n_strings > 0)
n_strings > 0Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 9 times by 1 test
Evaluated by:
  • tsort
2-9
525 {-
526 /* The input contains a loop. */-
527 error (0, 0, _("%s: input contains a loop:"), quotef (file));-
528 ok = false;-
529-
530 /* Print the loop and remove a relation to break it. */-
531 do-
532 walk_tree (root, detect_loop);
executed 4 times by 1 test: walk_tree (root, detect_loop);
Executed by:
  • tsort
4
533 while (loop);
loopDescription
TRUEevaluated 2 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 2 times by 1 test
Evaluated by:
  • tsort
2
534 }
executed 2 times by 1 test: end of block
Executed by:
  • tsort
2
535 }
executed 11 times by 1 test: end of block
Executed by:
  • tsort
11
536-
537 IF_LINT (free (root));-
538-
539 if (fclose (stdin) != 0)
rpl_fclose ( stdin ) != 0Description
TRUEnever evaluated
FALSEevaluated 9 times by 1 test
Evaluated by:
  • tsort
0-9
540 die (EXIT_FAILURE, errno, "%s",
never executed: ((!!sizeof (struct { _Static_assert ( 1 , "verify_expr (" "1" ", " "(error (1, (*__errno_location ()), \"%s\", is_stdin ? dcgettext (((void *)0), \"standard input\", 5) : quotearg_n_style_colon (0, shell_escape_quoting_style, file)), assume (false))" ")")...id) 0 : __builtin_unreachable ()))) : ((error ( 1 , (*__errno_location ()) , "%s", is_stdin ? dcgettext (((void *)0), "standard input" , 5) : quotearg_n_style_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ())))) ;
0
541 is_stdin ? _("standard input") : quotef (file));
never executed: ((!!sizeof (struct { _Static_assert ( 1 , "verify_expr (" "1" ", " "(error (1, (*__errno_location ()), \"%s\", is_stdin ? dcgettext (((void *)0), \"standard input\", 5) : quotearg_n_style_colon (0, shell_escape_quoting_style, file)), assume (false))" ")")...id) 0 : __builtin_unreachable ()))) : ((error ( 1 , (*__errno_location ()) , "%s", is_stdin ? dcgettext (((void *)0), "standard input" , 5) : quotearg_n_style_colon (0, shell_escape_quoting_style, file)), (( 0 ) ? (void) 0 : __builtin_unreachable ())))) ;
0
542-
543 return ok;
executed 9 times by 1 test: return ok;
Executed by:
  • tsort
9
544}-
545-
546int-
547main (int argc, char **argv)-
548{-
549 bool ok;-
550-
551 initialize_main (&argc, &argv);-
552 set_program_name (argv[0]);-
553 setlocale (LC_ALL, "");-
554 bindtextdomain (PACKAGE, LOCALEDIR);-
555 textdomain (PACKAGE);-
556-
557 atexit (close_stdout);-
558-
559 parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, Version,-
560 usage, AUTHORS, (char const *) NULL);-
561 if (getopt_long (argc, argv, "", long_options, NULL) != -1)
getopt_long (a...d *)0) ) != -1Description
TRUEevaluated 3 times by 1 test
Evaluated by:
  • tsort
FALSEevaluated 11 times by 1 test
Evaluated by:
  • tsort
3-11
562 usage (EXIT_FAILURE);
executed 3 times by 1 test: usage ( 1 );
Executed by:
  • tsort
3
563-
564 if (1 < argc - optind)
1 < argc - optindDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • tsort
FALSEevaluated 10 times by 1 test
Evaluated by:
  • tsort
1-10
565 {-
566 error (0, 0, _("extra operand %s"), quote (argv[optind + 1]));-
567 usage (EXIT_FAILURE);-
568 }
never executed: end of block
0
569-
570 ok = tsort (optind == argc ? "-" : argv[optind]);-
571-
572 return ok ? EXIT_SUCCESS : EXIT_FAILURE;
executed 9 times by 1 test: return ok ? 0 : 1 ;
Executed by:
  • tsort
9
573}-
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.1.2