/* tsort - topological sort. This is the tsort utility
Copyright (C) 1998-2018 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>. */ The GNUv3 license
/* Written by Mark Kettenis <kettenis@phys.uva.nl>. */
/* The topological sort is done according to Algorithm T (Topological
sort) in Donald E. Knuth, The Art of Computer Programming, Volume
1/Fundamental Algorithms, page 262. */
#include <config.h> Provides system specific information
#include <assert.h> ...!includes auto-comment...
#include <getopt.h> ...!includes auto-comment...
#include <sys/types.h> Provides system data types
#include "system.h" ...!includes auto-comment...
#include "long-options.h" ...!includes auto-comment...
#include "die.h" ...!includes auto-comment...
#include "error.h" ...!includes auto-comment...
#include "fadvise.h" ...!includes auto-comment...
#include "readtokens.h" ...!includes auto-comment...
#include "stdio--.h" ...!includes auto-comment...
#include "quote.h" ...!includes auto-comment...
/* The official name of this program (e.g., no 'g' prefix). */
#define PROGRAM_NAME "tsort" Line 39
#define AUTHORS proper_name ("Mark Kettenis") Line 41
static struct option const long_options[] = Line 43
{
{NULL, 0, NULL, 0} Line 45
}; Block 1
/* Token delimiters when reading from a file. */
#define DELIM " \t\n" Line 49
/* Members of the list of successors. */
struct successor Line 52
{
struct item *suc; Line 54
struct successor *next; Line 55
}; Block 2
/* Each string is held in core as the head of a list of successors. */
struct item Line 59
{
const char *str; Line 61
struct item *left, *right; Line 62
int balance; /* -1, 0, or +1 */ Line 63
size_t count; Line 64
struct item *qlink; Line 65
struct successor *top; Line 66
}; Block 3
/* The head of the sorted list. */
static struct item *head = NULL; Line 70
/* The tail of the list of 'zeros', strings that have no predecessors. */
static struct item *zeros = NULL; Line 73
/* Used for loop detection. */
static struct item *loop = NULL; Line 76
/* The number of strings to sort. */
static size_t n_strings = 0; Line 79
void Line 81
usage (int status) Line 82
{
if (status != EXIT_SUCCESS) Line 84
emit_try_help (); ...!common auto-comment...
else Line 86
{
printf (_("\ Line 88
Usage: %s [OPTION] [FILE]\n\ Line 89
Write totally ordered list consistent with the partial ordering in FILE.\n\ Line 90
"), program_name); Line 91
emit_stdin_note (); ...!common auto-comment...
fputs (_("\ Line 95
\n\
"), stdout); Line 97
fputs (HELP_OPTION_DESCRIPTION, stdout); Line 98
fputs (VERSION_OPTION_DESCRIPTION, stdout); Line 99
emit_ancillary_info (PROGRAM_NAME); Line 100
}
exit (status); Line 103
} Block 4
/* Create a new item/node for STR. */
static struct item * Line 107
new_item (const char *str) Line 108
{
struct item *k = xmalloc (sizeof *k); Line 110
k->str = (str ? xstrdup (str): NULL); Line 112
k->left = k->right = NULL; Line 113
k->balance = 0; Line 114
/* T1. Initialize (COUNT[k] <- 0 and TOP[k] <- ^). */
k->count = 0; Line 117
k->qlink = NULL; Line 118
k->top = NULL; Line 119
return k; Line 121
} Block 5
/* Search binary tree rooted at *ROOT for STR. Allocate a new tree if
*ROOT is NULL. Insert a node/item for STR if not found. Return
the node/item found/created for STR.
This is done according to Algorithm A (Balanced tree search and
insertion) in Donald E. Knuth, The Art of Computer Programming,
Volume 3/Searching and Sorting, pages 455--457. */
static struct item * Line 132
search_item (struct item *root, const char *str) Line 133
{
struct item *p, *q, *r, *s, *t; Line 135
int a; Line 136
assert (root); Line 138
/* Make sure the tree is not empty, since that is what the algorithm
below expects. */
if (root->right == NULL) Line 142
return (root->right = new_item (str)); Line 143
/* A1. Initialize. */
t = root; Line 146
s = p = root->right; Line 147
while (true) Line 149
{
/* A2. Compare. */
a = strcmp (str, p->str); Line 152
if (a == 0) Line 153
return p; Line 154
/* A3 & A4. Move left & right. */
if (a < 0) Line 157
q = p->left; Line 158
else Line 159
q = p->right; Line 160
if (q == NULL) Line 162
{
/* A5. Insert. */
q = new_item (str); Line 165
/* A3 & A4. (continued). */
if (a < 0) Line 168
p->left = q; Line 169
else Line 170
p->right = q; Line 171
/* A6. Adjust balance factors. */
assert (!STREQ (str, s->str)); Line 174
if (strcmp (str, s->str) < 0) Line 175
{
r = p = s->left; Line 177
a = -1; Line 178
}
else Line 180
{
r = p = s->right; Line 182
a = 1; Line 183
}
while (p != q) Line 186
{
assert (!STREQ (str, p->str)); Line 188
if (strcmp (str, p->str) < 0) Line 189
{
p->balance = -1; Line 191
p = p->left; Line 192
}
else Line 194
{
p->balance = 1; Line 196
p = p->right; Line 197
}
}
/* A7. Balancing act. */
if (s->balance == 0 || s->balance == -a) Line 202
{
s->balance += a; Line 204
return q; Line 205
}
if (r->balance == a) Line 208
{
/* A8. Single Rotation. */
p = r; Line 211
if (a < 0) Line 212
{
s->left = r->right; Line 214
r->right = s; Line 215
}
else Line 217
{
s->right = r->left; Line 219
r->left = s; Line 220
}
s->balance = r->balance = 0; Line 222
}
else Line 224
{
/* A9. Double rotation. */
if (a < 0) Line 227
{
p = r->right; Line 229
r->right = p->left; Line 230
p->left = r; Line 231
s->left = p->right; Line 232
p->right = s; Line 233
}
else Line 235
{
p = r->left; Line 237
r->left = p->right; Line 238
p->right = r; Line 239
s->right = p->left; Line 240
p->left = s; Line 241
}
s->balance = 0; Line 244
r->balance = 0; Line 245
if (p->balance == a) Line 246
s->balance = -a; Line 247
else if (p->balance == -a) Line 248
r->balance = a; Line 249
p->balance = 0; Line 250
}
/* A10. Finishing touch. */
if (s == t->right) Line 254
t->right = p; Line 255
else Line 256
t->left = p; Line 257
return q; Line 259
}
/* A3 & A4. (continued). */
if (q->balance) Line 263
{
t = p; Line 265
s = q; Line 266
}
p = q; Line 269
}
/* NOTREACHED */
} Block 6
/* Record the fact that J precedes K. */
static void Line 277
record_relation (struct item *j, struct item *k) Line 278
{
struct successor *p; Line 280
if (!STREQ (j->str, k->str)) Line 282
{
k->count++; Line 284
p = xmalloc (sizeof *p); Line 285
p->suc = k; Line 286
p->next = j->top; Line 287
j->top = p; Line 288
}
} Block 7
static bool Line 292
count_items (struct item *unused _GL_UNUSED) Line 293
{
n_strings++; Line 295
return false; Line 296
} Block 8
static bool Line 299
scan_zeros (struct item *k) Line 300
{
/* Ignore strings that have already been printed. */
if (k->count == 0 && k->str) Line 303
{
if (head == NULL) Line 305
head = k; Line 306
else Line 307
zeros->qlink = k; Line 308
zeros = k; Line 310
}
return false; Line 313
}
/* Try to detect the loop. If we have detected that K is part of a
loop, print the loop on standard error, remove a relation to break
the loop, and return true.
The loop detection strategy is as follows: Realise that what we're
dealing with is essentially a directed graph. If we find an item
that is part of a graph that contains a cycle we traverse the graph
in backwards direction. In general there is no unique way to do
this, but that is no problem. If we encounter an item that we have
encountered before, we know that we've found a cycle. All we have
to do now is retrace our steps, printing out the items until we
encounter that item again. (This is not necessarily the item that
we started from originally.) Since the order in which the items
are stored in the tree is not related to the specified partial
ordering, we may need to walk the tree several times before the
loop has completely been constructed. If the loop was found, the
global variable LOOP will be NULL. */
static bool Line 334
detect_loop (struct item *k) Line 335
{
if (k->count > 0) Line 337
{
/* K does not have to be part of a cycle. It is however part of
a graph that contains a cycle. */
if (loop == NULL) Line 342
/* Start traversing the graph at K. */
loop = k; Line 344
else Line 345
{
struct successor **p = &k->top; Line 347
while (*p) Line 349
{
if ((*p)->suc == loop) Line 351
{
if (k->qlink) Line 353
{
/* We have found a loop. Retrace our steps. */
while (loop) Line 356
{
struct item *tmp = loop->qlink; Line 358
error (0, 0, "%s", (loop->str)); Line 360
/* Until we encounter K again. */
if (loop == k) Line 363
{
/* Remove relation. */
(*p)->suc->count--; Line 366
*p = (*p)->next; Line 367
break; Line 368
}
/* Tidy things up since we might have to
detect another loop. */
loop->qlink = NULL; Line 373
loop = tmp; Line 374
}
while (loop) Line 377
{
struct item *tmp = loop->qlink; Line 379
loop->qlink = NULL; Line 381
loop = tmp; Line 382
}
/* Since we have found the loop, stop walking
the tree. */
return true; Line 387
}
else Line 389
{
k->qlink = loop; Line 391
loop = k; Line 392
break; Line 393
}
}
p = &(*p)->next; Line 397
}
}
}
return false; Line 402
} Block 10
/* Recurse (sub)tree rooted at ROOT, calling ACTION for each node.
Stop when ACTION returns true. */
static bool Line 408
recurse_tree (struct item *root, bool (*action) (struct item *)) Line 409
{
if (root->left == NULL && root->right == NULL) Line 411
return (*action) (root); Line 412
else Line 413
{
if (root->left != NULL) Line 415
if (recurse_tree (root->left, action)) Line 416
return true; Line 417
if ((*action) (root)) Line 418
return true; Line 419
if (root->right != NULL) Line 420
if (recurse_tree (root->right, action)) Line 421
return true; Line 422
}
return false; Line 425
} Block 11
/* Walk the tree specified by the head ROOT, calling ACTION for
each node. */
static void Line 431
walk_tree (struct item *root, bool (*action) (struct item *)) Line 432
{
if (root->right) Line 434
recurse_tree (root->right, action); Line 435
} Block 12
/* Do a topological sort on FILE. Return true if successful. */
static bool Line 440
tsort (const char *file) Line 441
{
bool ok = true; Line 443
struct item *root; Line 444
struct item *j = NULL; Line 445
struct item *k = NULL; Line 446
token_buffer tokenbuffer; Line 447
bool is_stdin = STREQ (file, "-"); Line 448
/* Intialize the head of the tree will hold the strings we're sorting. */
root = new_item (NULL); Line 451
if (!is_stdin && ! freopen (file, "r", stdin)) Line 453...!syscalls auto-comment...
die (EXIT_FAILURE, errno, "%s", quotef (file)); Line 454
fadvise (stdin, FADVISE_SEQUENTIAL); Line 456...!syscalls auto-comment...
init_tokenbuffer (&tokenbuffer); Line 458
while (1) Line 460
{
/* T2. Next Relation. */
size_t len = readtoken (stdin, DELIM, sizeof (DELIM) - 1, &tokenbuffer); Line 463
if (len == (size_t) -1) Line 464
break; Line 465
assert (len != 0); Line 467
k = search_item (root, tokenbuffer.buffer); Line 469
if (j) Line 470
{
/* T3. Record the relation. */
record_relation (j, k); Line 473
k = NULL; Line 474
}
j = k; Line 477
}
if (k != NULL) Line 480
die (EXIT_FAILURE, 0, _("%s: input contains an odd number of tokens"), Line 481
quotef (file)); Line 482
/* T1. Initialize (N <- n). */
walk_tree (root, count_items); Line 485
while (n_strings > 0) Line 487
{
/* T4. Scan for zeros. */
walk_tree (root, scan_zeros); Line 490
while (head) Line 492
{
struct successor *p = head->top; Line 494
/* T5. Output front of queue. */
puts (head->str); Line 497
#ifdef lint Line 498
/* suppress valgrind "definitely lost" warnings. */
void *head_str = (void *) head->str; Line 500
free (head_str); Line 501
#endif Line 502
head->str = NULL; /* Avoid printing the same string twice. */ Line 503
n_strings--; Line 504
/* T6. Erase relations. */
while (p) Line 507
{
p->suc->count--; Line 509
if (p->suc->count == 0) Line 510
{
zeros->qlink = p->suc; Line 512
zeros = p->suc; Line 513
}
p = p->next; Line 516
}
/* T7. Remove from queue. */
head = head->qlink; Line 520
}
/* T8. End of process. */
if (n_strings > 0) Line 524
{
/* The input contains a loop. */
error (0, 0, _("%s: input contains a loop:"), quotef (file)); Line 527
ok = false; Line 528
/* Print the loop and remove a relation to break it. */
do
walk_tree (root, detect_loop); Line 532
while (loop); Line 533
}
}
IF_LINT (free (root)); Line 537
if (fclose (stdin) != 0) Line 539...!syscalls auto-comment...
die (EXIT_FAILURE, errno, "%s", Line 540
is_stdin ? _("standard input") : quotef (file)); Line 541
return ok; Line 543
} Block 13
int
main (int argc, char **argv) Line 547
{
bool ok; Line 549
initialize_main (&argc, &argv); VMS-specific entry point handling wildcard expansion
set_program_name (argv[0]); Retains program name and discards path
setlocale (LC_ALL, ""); Sets up internationalization (i18n)
bindtextdomain (PACKAGE, LOCALEDIR); Assigns i18n directorySets text domain for _() [gettext()] function
textdomain (PACKAGE); Sets text domain for _() [gettext()] function
atexit (close_stdout); Close stdout on exit (see gnulib)
parse_long_options (argc, argv, PROGRAM_NAME, PACKAGE, Version, ...!common auto-comment...
usage, AUTHORS, (char const *) NULL); Line 560
if (getopt_long (argc, argv, "", long_options, NULL) != -1) Line 561
usage (EXIT_FAILURE); Line 562
if (1 < argc - optind) Line 564
{
error (0, 0, _("extra operand %s"), quote (argv[optind + 1])); Line 566
usage (EXIT_FAILURE); Line 567
}
ok = tsort (optind == argc ? "-" : argv[optind]); Line 570
return ok ? EXIT_SUCCESS : EXIT_FAILURE; Line 572
} Block 14