tsort:拓扑排序
tsort 对给定文件执行拓扑排序，如果没有给定输入文件，则执行标准输入排序，或者对` - `文件执行拓扑排序。有关更多细节和历史，请参阅7.6.1节[tsort背景]，第71页。
简介:
tsort [option] [file]
Tsort将其输入读取为由空格分隔的字符串对，表示偏序。输出是与给定的偏序相对应的总序。
例如
tsort << EOF
A b c
d
e f
B c d e
EOF
将产生输出
a
b
c
d
e
f
考虑一个更现实的例子。你在一个文件中有一大堆函数，除了一个函数外，其他函数都可能被声明为静态函数。
目前，这个函数(比如main)是文件中定义的第一个函数，它调用的函数紧随其后，然后是它们调用的函数，以此类推。假设你决心利用原型，那么你必须在声明所有这些函数(这意味着从定义中复制大量信息)和重新排列这些函数之间做出选择，以便尽可能多地在使用它们之前定义。
自动化后一个过程的一种方法是直接获取它调用的每个函数的列表。许多程序都可以生成这样的列表。
它们描述了一个调用图。考虑下面的列表，其中给定的一行表明左边的函数直接调用了右边的函数。
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
然后，你可以使用 tsort 来生成满足需求的函数排序。
示例
$ 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检测输入中的任何循环，并将遇到的第一个循环写入标准错误。
对于给定的偏序，一般没有唯一的全序。在上述调用图的上下文中，函数 parse_options 可以放在列表中的任何位置，只要它在main之前。
唯一的选项是--help和--version。参见第2章[常见选项]，第2页。
退出状态为零表示成功，非零值表示失败。tsort:后台排序
之所以存在tsort，是因为Unix链接器的早期版本只处理一次归档文件，而且是按顺序处理的。当ld读取存档中的每个对象时，它根据该对象是否定义了在链接中未定义的任何符号来决定该对象是否在程序中需要。
这意味着必须特别处理归档文件中的依赖关系。例如，Scanf可能调用read。这意味着在对存档的一次遍历中，scanf.o出现在read.o之前是很重要的，，因为否则，调用scanf而不调用read的程序可能会以一个意外的未解决的引用结束。
解决这个问题的方法是首先在一个目标文件上生成一组依赖关系。这是通过一个名为lorder的shell脚本完成的。据我所知，GNU工具没有提供lorder的版本，但您仍然可以在BSD发行版中找到它。
然后对lorder输出运行tsort，并使用得到的排序来定义将对象添加到归档中的顺序。
整个过程在1980年左右就已经过时了，因为Unix存档现在包含一个符号表(传统上由ranlib构建，现在一般由ar自身构建)，Unix链接器使用符号表有效地对存档文件进行多次传递。总之，tsort就是这么来的。来解决链接器处理归档文件方式的一个旧问题，该问题已经以不同的方式解决了。