{
    "mode": "info",
    "parameter": "tsort",
    "section": "",
    "url": "https://www.chedong.com/phpMan.php/info/tsort/json",
    "generated": "2026-11-09T21:20:32Z",
    "sections": {
        "File: coreutils.info,  Node: tsort invocation,  Prev: ptx invocation,  Up: Operating on sorted files": {
            "content": "",
            "subsections": [
                {
                    "name": "7.6 'tsort': Topological sort",
                    "content": "'tsort' performs a topological sort on the given FILE, or standard input\nif no input file is given or for a FILE of '-'.  For more details and\nsome history, see *note tsort background::.  Synopsis:\n\ntsort [OPTION] [FILE]\n\n'tsort' reads its input as pairs of strings, separated by blanks,\nindicating a partial ordering.  The output is a total ordering that\ncorresponds to the given partial ordering.\n\nFor example\n\ntsort <<EOF\na b c\nd\ne f\nb c d e\nEOF\n\nwill produce the output\n\na\nb\nc\nd\ne\nf\n\nConsider a more realistic example.  You have a large set of functions\nall in one file, and they may all be declared static except one."
                }
            ]
        },
        "Currently that one (say 'main') is the first function defined in the": {
            "content": "file, and the ones it calls directly follow it, followed by those they\ncall, etc.  Let's say that you are determined to take advantage of\nprototypes, so you have to choose between declaring all of those\nfunctions (which means duplicating a lot of information from the\ndefinitions) and rearranging the functions so that as many as possible\nare defined before they are used.  One way to automate the latter\nprocess is to get a list for each function of the functions it calls\ndirectly.  Many programs can generate such lists.  They describe a call\ngraph.  Consider the following list, in which a given line indicates\nthat the function on the left calls the one on the right directly.\n\nmain parseoptions\nmain tailfile\nmain tailforever\ntailfile prettyname\ntailfile writeheader\ntailfile tail\ntailforever recheck\ntailforever prettyname\ntailforever writeheader\ntailforever dumpremainder\ntail taillines\ntail tailbytes\ntaillines startlines\ntaillines dumpremainder\ntaillines filelines\ntaillines pipelines\ntailbytes xlseek\ntailbytes startbytes\ntailbytes dumpremainder\ntailbytes pipebytes\nfilelines dumpremainder\nrecheck prettyname\n\nthen you can use 'tsort' to produce an ordering of those functions\nthat satisfies your requirement.\n\nexample$ tsort call-graph | tac\ndumpremainder\nstartlines\nfilelines\npipelines\nxlseek\nstartbytes\npipebytes\ntaillines\ntailbytes\nprettyname\nwriteheader\ntail\nrecheck\nparseoptions\ntailfile\ntailforever\nmain\n\n'tsort' detects any cycles in the input and writes the first cycle\nencountered to standard error.\n\nNote that for a given partial ordering, generally there is no unique\ntotal ordering.  In the context of the call graph above, the function\n'parseoptions' may be placed anywhere in the list as long as it\nprecedes 'main'.\n\nThe only options are '--help' and '--version'.  *Note Common\noptions::.\n\nAn exit status of zero indicates success, and a nonzero value\nindicates failure.\n\n* Menu:\n\n* tsort background::            Where tsort came from.\n",
            "subsections": []
        },
        "File: coreutils.info,  Node: tsort background,  Up: tsort invocation": {
            "content": "'tsort' exists because very early versions of the Unix linker processed\nan archive file exactly once, and in order.  As 'ld' read each object in\nthe archive, it decided whether it was needed in the program based on\nwhether it defined any symbols which were undefined at that point in the\nlink.\n\nThis meant that dependencies within the archive had to be handled\nspecially.  For example, 'scanf' probably calls 'read'.  That means that\nin a single pass through an archive, it was important for 'scanf.o' to\nappear before read.o, because otherwise a program which calls 'scanf'\nbut not 'read' might end up with an unexpected unresolved reference to\n'read'.\n\nThe way to address this problem was to first generate a set of\ndependencies of one object file on another.  This was done by a shell\nscript called 'lorder'.  The GNU tools don't provide a version of\nlorder, as far as I know, but you can still find it in BSD\ndistributions.\n\nThen you ran 'tsort' over the 'lorder' output, and you used the\nresulting sort to define the order in which you added objects to the\narchive.\n\nThis whole procedure has been obsolete since about 1980, because Unix\narchives now contain a symbol table (traditionally built by 'ranlib',\nnow generally built by 'ar' itself), and the Unix linker uses the symbol\ntable to effectively make multiple passes over an archive file.\n\nAnyhow, that's where tsort came from.  To solve an old problem with\nthe way the linker handled archive files, which has since been solved in\ndifferent ways.\n",
            "subsections": []
        }
    },
    "flags": [],
    "examples": [],
    "see_also": []
}