coreutils: tsort invocation
1
1 7.6 ‘tsort’: Topological sort
1 =============================
1
1 ‘tsort’ performs a topological sort on the given FILE, or standard input
1 if no input file is given or for a FILE of ‘-’. For more details and
1 some history, see ⇒tsort background. Synopsis:
1
1 tsort [OPTION] [FILE]
1
1 ‘tsort’ reads its input as pairs of strings, separated by blanks,
1 indicating a partial ordering. The output is a total ordering that
1 corresponds to the given partial ordering.
1
1 For example
1
1 tsort <<EOF
1 a b c
1 d
1 e f
1 b c d e
1 EOF
1
1 will produce the output
1
1 a
1 b
1 c
1 d
1 e
1 f
1
1 Consider a more realistic example. You have a large set of functions
1 all in one file, and they may all be declared static except one.
1 Currently that one (say ‘main’) is the first function defined in the
1 file, and the ones it calls directly follow it, followed by those they
1 call, etc. Let’s say that you are determined to take advantage of
1 prototypes, so you have to choose between declaring all of those
1 functions (which means duplicating a lot of information from the
1 definitions) and rearranging the functions so that as many as possible
1 are defined before they are used. One way to automate the latter
1 process is to get a list for each function of the functions it calls
1 directly. Many programs can generate such lists. They describe a call
1 graph. Consider the following list, in which a given line indicates
1 that the function on the left calls the one on the right directly.
1
1 main parse_options
1 main tail_file
1 main tail_forever
1 tail_file pretty_name
1 tail_file write_header
1 tail_file tail
1 tail_forever recheck
1 tail_forever pretty_name
1 tail_forever write_header
1 tail_forever dump_remainder
1 tail tail_lines
1 tail tail_bytes
1 tail_lines start_lines
1 tail_lines dump_remainder
1 tail_lines file_lines
1 tail_lines pipe_lines
1 tail_bytes xlseek
1 tail_bytes start_bytes
1 tail_bytes dump_remainder
1 tail_bytes pipe_bytes
1 file_lines dump_remainder
1 recheck pretty_name
1
1 then you can use ‘tsort’ to produce an ordering of those functions
1 that satisfies your requirement.
1
1 example$ tsort call-graph | tac
1 dump_remainder
1 start_lines
1 file_lines
1 pipe_lines
1 xlseek
1 start_bytes
1 pipe_bytes
1 tail_lines
1 tail_bytes
1 pretty_name
1 write_header
1 tail
1 recheck
1 parse_options
1 tail_file
1 tail_forever
1 main
1
1 ‘tsort’ detects any cycles in the input and writes the first cycle
1 encountered to standard error.
1
1 Note that for a given partial ordering, generally there is no unique
1 total ordering. In the context of the call graph above, the function
1 ‘parse_options’ may be placed anywhere in the list as long as it
1 precedes ‘main’.
1
11 The only options are ‘--help’ and ‘--version’. ⇒Common
options.
1
1 An exit status of zero indicates success, and a nonzero value
1 indicates failure.
1
Menu