File: coreutils.info, Node: tsort invocation, Prev: ptx invocation, Up: Operating on sorted files 7.6 `tsort': Topological sort ============================= `tsort' performs a topological sort on the given FILE, or standard input if no input file is given or for a FILE of `-'. For more details and some history, see *note tsort background::. Synopsis: tsort [OPTION] [FILE] `tsort' reads its input as pairs of strings, separated by blanks, indicating a partial ordering. The output is a total ordering that corresponds to the given partial ordering. For example tsort <<EOF a b c d e f b c d e EOF will produce the output a b c d e f Consider a more realistic example. You have a large set of functions all in one file, and they may all be declared static except one. Currently that one (say `main') is the first function defined in the file, and the ones it calls directly follow it, followed by those they call, etc. Let's say that you are determined to take advantage of prototypes, so you have to choose between declaring all of those functions (which means duplicating a lot of information from the definitions) and rearranging the functions so that as many as possible are defined before they are used. One way to automate the latter process is to get a list for each function of the functions it calls directly. Many programs can generate such lists. They describe a call graph. Consider the following list, in which a given line indicates that the function on the left calls the one on the right directly. main parse_options main tail_file main tail_forever tail_file pretty_name tail_file write_header tail_file tail tail_forever recheck tail_forever pretty_name tail_forever write_header tail_forever dump_remainder tail tail_lines tail tail_bytes tail_lines start_lines tail_lines dump_remainder tail_lines file_lines tail_lines pipe_lines tail_bytes xlseek tail_bytes start_bytes tail_bytes dump_remainder tail_bytes pipe_bytes file_lines dump_remainder recheck pretty_name then you can use `tsort' to produce an ordering of those functions that satisfies your requirement. example$ tsort call-graph | tac dump_remainder start_lines file_lines pipe_lines xlseek start_bytes pipe_bytes tail_lines tail_bytes pretty_name write_header tail recheck parse_options tail_file tail_forever main `tsort' detects any cycles in the input and writes the first cycle encountered to standard error. Note that for a given partial ordering, generally there is no unique total ordering. In the context of the call graph above, the function `parse_options' may be placed anywhere in the list as long as it precedes `main'. The only options are `--help' and `--version'. *Note Common options::. An exit status of zero indicates success, and a nonzero value indicates failure. * Menu: * tsort background:: Where tsort came from. File: coreutils.info, Node: tsort background, Up: tsort invocation 7.6.1 `tsort': Background ------------------------- `tsort' exists because very early versions of the Unix linker processed an archive file exactly once, and in order. As `ld' read each object in the archive, it decided whether it was needed in the program based on whether it defined any symbols which were undefined at that point in the link. This meant that dependencies within the archive had to be handled specially. For example, `scanf' probably calls `read'. That means that in a single pass through an archive, it was important for `scanf.o' to appear before read.o, because otherwise a program which calls `scanf' but not `read' might end up with an unexpected unresolved reference to `read'. The way to address this problem was to first generate a set of dependencies of one object file on another. This was done by a shell script called `lorder'. The GNU tools don't provide a version of lorder, as far as I know, but you can still find it in BSD distributions. Then you ran `tsort' over the `lorder' output, and you used the resulting sort to define the order in which you added objects to the archive. This whole procedure has been obsolete since about 1980, because Unix archives now contain a symbol table (traditionally built by `ranlib', now generally built by `ar' itself), and the Unix linker uses the symbol table to effectively make multiple passes over an archive file. Anyhow, that's where tsort came from. To solve an old problem with the way the linker handled archive files, which has since been solved in different ways.