「tsort(1)」-

  LINUX MANUAL PAGES

执行拓扑排序

命令语法格式

tsort [OPTION] [FILE]

命令描述

tsort对给定文件FILE执行拓扑排序。如果没有指定参数FILE或者参数FILE为’-‘,则从标准输入中读取。

tsort读取它的输入,并将其做为字符串的一部分,由空白分隔,表明部分排序。输出则是对应于给定的部分排序的总排序。

tsort检测输入中的任何环形拓扑,并将遇到的第一个环形拓扑写入标准错误。

命令支持的选项及含义

–help
显示帮助信息并退出。

–version
显示版本信息并退出。

退出状态

退出状态为零表示成功,非零值表示失败。

使用示例

如下示例,对于命令:

# 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

请注意,对于给定的部分排序,通常不存在唯一的总排序。在上述调用图的上下文中,只要parse_options位于main的前面,parse_options就可以放在列表中的任何位置。

tsort的由来

tsort的存在是因为Unix链接器的早期版本只处理一次档案文件,并按顺序处理。当ld读取档案中的每个对象时,它会根据是否定义链接中未定义的任何符号来决定程序是否需要它。

这意味着档案中的依赖关系必须专门处理。例如,scanf可能会调用read。这意味着,在一次存档中,scanf.o在read.o之前出现很重要,否则调用scanf但未读取的程序可能最终会导致意外的未解析的读取引用。

解决这个问题的方法是首先在另一个目标文件上生成一组依赖关系。这是通过名为lorder的shell脚本完成的。据我们所知,GNU工具不提供lorder版本,但你仍然可以在BSD发行版中找到它。

然后,你在lorder输出上运行tsort,并使用结果排序来定义将对象添加到存档的顺序。

自1980年以来,整个过程已经过时,因为Unix存档现在包含一个符号表(传统上由ranlib构建,现在通常由ar本身构建),Unix链接器使用符号表有效地对存档文件进行多次传递。

无论如何,这是tsort从何而来。用连接器处理归档文件的方式解决一个老问题,这个问题已经以不同的方式解决了。

相关手册

查看在线手册:http://www.gnu.org/software/coreutils/tsort

查看info手册:info ‘(coreutils) tsort invocation’

参考文献

更新日志

  • 06/26/2018 创建文章