Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/coreutils/src/src/tsort.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
43 | static 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. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
52 | struct 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. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
59 | struct 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. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
70 | static struct item *head = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
71 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
72 | /* The tail of the list of 'zeros', strings that have no predecessors. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
73 | static struct item *zeros = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
74 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
75 | /* Used for loop detection. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
76 | static struct item *loop = NULL; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
77 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
78 | /* The number of strings to sort. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
79 | static size_t n_strings = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
80 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
81 | void | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
82 | usage (int status) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
83 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
84 | if (status != EXIT_SUCCESS)
| 3-4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
85 | emit_try_help (); executed 4 times by 1 test: end of block Executed by:
| 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
86 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
87 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
88 | printf (_("\ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
89 | Usage: %s [OPTION] [FILE]\n\ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
90 | Write 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:
| 3 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
102 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
103 | exit (status); executed 7 times by 1 test: exit (status); Executed by:
| 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
104 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
105 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
106 | /* Create a new item/node for STR. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
107 | static struct item * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
108 | new_item (const char *str) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
109 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
110 | struct item *k = xmalloc (sizeof *k); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
111 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
112 | k->str = (str ? xstrdup (str): NULL);
| 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:
| 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 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
132 | static struct item * | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
133 | search_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)
| 10-85 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
143 | return (root->right = new_item (str)); executed 10 times by 1 test: return (root->right = new_item (str)); Executed by:
| 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
| 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
153 | if (a == 0)
| 38-180 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
154 | return p; executed 38 times by 1 test: return p; Executed by:
| 38 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
155 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
156 | /* A3 & A4. Move left & right. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
157 | if (a < 0)
| 22-158 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
158 | q = p->left; executed 22 times by 1 test: q = p->left; Executed by:
| 22 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
159 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
160 | q = p->right; executed 158 times by 1 test: q = p->right; Executed by:
| 158 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
161 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
162 | if (q == NULL)
| 47-133 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
163 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
164 | /* A5. Insert. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
165 | q = new_item (str); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
166 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
167 | /* A3 & A4. (continued). */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
168 | if (a < 0)
| 7-40 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
169 | p->left = q; executed 7 times by 1 test: p->left = q; Executed by:
| 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
170 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
171 | p->right = q; executed 40 times by 1 test: p->right = q; Executed by:
| 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
| 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
| 0-41 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
176 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
177 | r = p = s->left; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
178 | a = -1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
179 | } executed 6 times by 1 test: end of block Executed by:
| 6 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
180 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
181 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
182 | r = p = s->right; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
183 | a = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
184 | } executed 41 times by 1 test: end of block Executed by:
| 41 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
185 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
186 | while (p != q)
| 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
| 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
| 0-44 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
190 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
191 | p->balance = -1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
192 | p = p->left; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
193 | } executed 6 times by 1 test: end of block Executed by:
| 6 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
194 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
195 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
196 | p->balance = 1; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
197 | p = p->right; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
198 | } executed 44 times by 1 test: end of block Executed by:
| 44 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
199 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
200 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
201 | /* A7. Balancing act. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
202 | if (s->balance == 0 || s->balance == -a)
| 3-28 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
203 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
204 | s->balance += a; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
205 | return q; executed 22 times by 1 test: return q; Executed by:
| 22 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
206 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
207 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
208 | if (r->balance == a)
| 4-21 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
209 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
210 | /* A8. Single Rotation. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
211 | p = r; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
212 | if (a < 0)
| 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:
| 21 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
222 | s->balance = r->balance = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
223 | } executed 21 times by 1 test: end of block Executed by:
| 21 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
224 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
225 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
226 | /* A9. Double rotation. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
227 | if (a < 0)
| 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:
| 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:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
243 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
244 | s->balance = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
245 | r->balance = 0; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
246 | if (p->balance == a)
| 1-3 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
247 | s->balance = -a; executed 1 time by 1 test: s->balance = -a; Executed by:
| 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
248 | else if (p->balance == -a)
| 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:
| 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
252 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
253 | /* A10. Finishing touch. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
254 | if (s == t->right)
| 1-24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
255 | t->right = p; executed 24 times by 1 test: t->right = p; Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
256 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
257 | t->left = p; executed 1 time by 1 test: t->left = p; Executed by:
| 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
258 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
259 | return q; executed 25 times by 1 test: return q; Executed by:
| 25 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
260 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
261 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
262 | /* A3 & A4. (continued). */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
263 | if (q->balance)
| 35-98 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
264 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
265 | t = p; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
266 | s = q; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
267 | } executed 35 times by 1 test: end of block Executed by:
| 35 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
268 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
269 | p = q; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
270 | } executed 133 times by 1 test: end of block Executed by:
| 133 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
271 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
272 | /* NOTREACHED */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
273 | } never executed: end of block | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
274 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
275 | /* Record the fact that J precedes K. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
276 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
277 | static void | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
278 | record_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
| 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:
| 44 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
290 | } executed 47 times by 1 test: end of block Executed by:
| 47 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
291 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
292 | static bool | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
293 | count_items (struct item *unused _GL_UNUSED) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
294 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
295 | n_strings++; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
296 | return false; executed 56 times by 1 test: return 0 ; Executed by:
| 56 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
297 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
298 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
299 | static bool | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
300 | scan_zeros (struct item *k) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
301 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
302 | /* Ignore strings that have already been printed. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
303 | if (k->count == 0 && k->str)
| 0-46 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
304 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
305 | if (head == NULL)
| 7-9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
306 | head = k; executed 9 times by 1 test: head = k; Executed by:
| 9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
307 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
308 | zeros->qlink = k; executed 7 times by 1 test: zeros->qlink = k; Executed by:
| 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
309 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
310 | zeros = k; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
311 | } executed 16 times by 1 test: end of block Executed by:
| 16 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
312 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
313 | return false; executed 62 times by 1 test: return 0 ; Executed by:
| 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 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
334 | static bool | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
335 | detect_loop (struct item *k) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
336 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
337 | if (k->count > 0)
| 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)
| 2-9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
343 | /* Start traversing the graph at K. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
344 | loop = k; executed 2 times by 1 test: loop = k; Executed by:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
345 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
346 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
347 | struct successor **p = &k->top; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
348 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
349 | while (*p)
| 3-8 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
350 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
351 | if ((*p)->suc == loop)
| 2-6 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
352 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
353 | if (k->qlink)
| 2-4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
354 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
355 | /* We have found a loop. Retrace our steps. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
356 | while (loop)
| 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)
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
364 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
365 | /* Remove relation. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
366 | (*p)->suc->count--; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
367 | *p = (*p)->next; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
368 | break; executed 2 times by 1 test: break; Executed by:
| 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:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
376 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
377 | while (loop)
| 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:
| 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:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
388 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
389 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
390 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
391 | k->qlink = loop; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
392 | loop = k; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
393 | break; executed 4 times by 1 test: break; Executed by:
| 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
394 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
395 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
396 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
397 | p = &(*p)->next; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
398 | } executed 2 times by 1 test: end of block Executed by:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
399 | } executed 7 times by 1 test: end of block Executed by:
| 7 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
400 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
401 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
402 | return false; executed 9 times by 1 test: return 0 ; Executed by:
| 9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
403 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
404 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
405 | /* Recurse (sub)tree rooted at ROOT, calling ACTION for each node. | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
406 | Stop when ACTION returns true. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
407 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
408 | static bool | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
409 | recurse_tree (struct item *root, bool (*action) (struct item *)) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
410 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
411 | if (root->left == NULL && root->right == NULL)
| 12-81 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
412 | return (*action) (root); executed 69 times by 1 test: return (*action) (root); Executed by:
| 69 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
413 | else | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
414 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
415 | if (root->left != NULL)
| 12-48 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
416 | if (recurse_tree (root->left, action))
| 0-48 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
417 | return true; never executed: return 1 ; | 0 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
418 | if ((*action) (root))
| 1-59 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
419 | return true; executed 1 time by 1 test: return 1 ; Executed by:
| 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
420 | if (root->right != NULL)
| 2-57 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
421 | if (recurse_tree (root->right, action))
| 1-56 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
422 | return true; executed 1 time by 1 test: return 1 ; Executed by:
| 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
423 | } executed 58 times by 1 test: end of block Executed by:
| 58 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
424 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
425 | return false; executed 58 times by 1 test: return 0 ; Executed by:
| 58 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
426 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
427 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
428 | /* Walk the tree specified by the head ROOT, calling ACTION for | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
429 | each node. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
430 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
431 | static void | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
432 | walk_tree (struct item *root, bool (*action) (struct item *)) | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
433 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
434 | if (root->right)
| 0-24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
435 | recurse_tree (root->right, action); executed 24 times by 1 test: recurse_tree (root->right, action); Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
436 | } executed 24 times by 1 test: end of block Executed by:
| 24 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
437 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
438 | /* Do a topological sort on FILE. Return true if successful. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
439 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
440 | static bool | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
441 | tsort (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:
| 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))
| 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)
| 10-95 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
465 | break; executed 10 times by 1 test: break; Executed by:
| 10 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
466 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
467 | assert (len != 0); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
468 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
469 | k = search_item (root, tokenbuffer.buffer); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
470 | if (j)
| 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:
| 47 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
476 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
477 | j = k; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
478 | } executed 95 times by 1 test: end of block Executed by:
| 95 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
479 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
480 | if (k != NULL)
| 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:
| 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:
| 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
483 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
484 | /* T1. Initialize (N <- n). */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
485 | walk_tree (root, count_items); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
486 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
487 | while (n_strings > 0)
| 9-11 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
488 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
489 | /* T4. Scan for zeros. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
490 | walk_tree (root, scan_zeros); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
491 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
492 | while (head)
| 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)
| 42-56 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
508 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
509 | p->suc->count--; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
510 | if (p->suc->count == 0)
| 2-40 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
511 | { | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
512 | zeros->qlink = p->suc; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
513 | zeros = p->suc; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
514 | } executed 40 times by 1 test: end of block Executed by:
| 40 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
515 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
516 | p = p->next; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
517 | } executed 42 times by 1 test: end of block Executed by:
| 42 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
518 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
519 | /* T7. Remove from queue. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
520 | head = head->qlink; | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
521 | } executed 56 times by 1 test: end of block Executed by:
| 56 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
522 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
523 | /* T8. End of process. */ | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
524 | if (n_strings > 0)
| 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:
| 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
533 | while (loop);
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
534 | } executed 2 times by 1 test: end of block Executed by:
| 2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
535 | } executed 11 times by 1 test: end of block Executed by:
| 11 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
536 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
537 | IF_LINT (free (root)); | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
538 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
539 | if (fclose (stdin) != 0)
| 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:
| 9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
544 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
545 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
546 | int | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
547 | main (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)
| 3-11 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
562 | usage (EXIT_FAILURE); executed 3 times by 1 test: usage ( 1 ); Executed by:
| 3 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
563 | - | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
564 | if (1 < argc - optind)
| 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:
| 9 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
573 | } | - | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Source code | Switch to Preprocessed file |