Tsort - Tsort
První vydání | 1979 |
---|---|
Operační systém | Unix, Unixový, PROTI, Peklo |
Typ | Příkaz |
The třídění program je a příkazový řádek nástroj na Unix a Unixový platformy, které provádí a topologické třídění na jeho vstupu. Od roku 2017[Aktualizace], je součástí POSIX.1 standard.[1]
Dějiny
Podle jeho informace[2] Stránka, tento příkaz byl původně napsán pro zajištění uspořádání souborů objektů, které umožňovaly linker zpracovávat je postupně (každý přesně jedenkrát a v pořadí). Stránka manuálu FreeBSD se datuje do Verze 7 Unix.[3]
Všimněte si, že následující popis popisuje chování FreeBSD implementace tsort a zmiňuje funkce GNU tam, kde mohou existovat. Jiné implementace nebo verze se mohou lišit.
Syntax
tsort [-dlq] [SOUBOR]
Možnosti FreeBSD mohou být:
-d zapnout ladění-l vyhledat a zobrazit nejdelší cyklus.-q Nezobrazovat informační zprávy o cyklech.
GNU poskytuje pouze následující možnosti:
- help zobrazit nápovědu a ukončit - verze zobrazit informace o verzi a ukončit
POSIX nepředepisuje žádné možnosti.
Chování
tsort čte svůj vstup (z daného SOUBORU, nebo standardní vstup pokud není zadán žádný vstupní soubor nebo pro SOUBOR '-') jako dvojice řetězců, oddělených mezerami, označující částečné řazení. Výstupem je celkové řazení, které odpovídá danému částečnému řazení.[4]
Jinými slovy: pro a směrovaný acyklický graf (používá se jako graf závislosti ), tsort vytvoří seznam theverices tak, že pro všechny hrany 'a-> b', 'a' přijde před 'b' v seznamu.
Příklady
tsort uvádí vrcholy a směrovaný acyklický graf v takovém pořadí, aby byly respektovány všechny vztahy objednávání / směrování:
$ třídění << EOF> 3 8> 3 10> 5 11> 7 8> 7 11> 8 9> 11 2> 11 9> 11 10> EOF3571181029 | ![]() vzorek DAG |
Volajte graf
tsort může pomoci změnit uspořádání funkcí ve zdrojovém souboru tak, aby bylo definováno co nejvíce před jejich použitím (interpretujte následující jako: hlavní()
hovory parse_options ()
, tail_file ()
a tail_forever ()
; tail_file ()
hovory pěkné jméno()
, a tak dále. Výsledkem je to dump_remainder ()
by mělo být definováno jako první, start_lines ()
druhý atd.):
$ kočka call grafhlavní parse_optionshlavní tail_filehlavní tail_forevertail_file pretty_nametail_file write_headertail_file tailtail_forever znovu zkontrolovattail_forever pretty_nametail_forever write_headertail_forever dump_remainderocas ocas_řádkytail tail_bytestail_lines start_linestail_lines dump_remaindertail_lines file_linestail_lines pipe_linestail_bytes xlseektail_bytes start_bytestail_bytes dump_remaindertail_bytes pipe_bytesfile_lines dump_remainderpřekontrolovat pretty_name | $ # poznámka: 'tac' obrátí pořadí$ tsort call-graph | tacdump_remainderstart_linesfile_linespotrubí_řádkyxlseekstart_bytespipe_bytesocas_řádkytail_bytespěkné jménowrite_headerocaspřekontrolovatparse_optionstail_filetail_foreverhlavní |
Knihovna
Tradiční ld (Unix linker) vyžaduje, aby jeho vstupy do knihovny byly tříděny v topologickém pořadí, protože zpracovává soubory v jednom průchodu. To platí jak pro statické knihovny (*.A
) a dynamické knihovny (*.tak
), a v případě statických knihoven přednostně pro jednotlivé soubory objektů obsažené v.[5]
BSD UNIX používá tsort jako běžnou součást typické ar & ranlib vyvolání příkazů (z /usr/share/mk/bsd.lib.mk):
lib $ {LIB} .a: ${OBJS} ${STATICOBJS} @${ECHO} statická budova ${LIB} knihovna @${AR} CQ ${.CÍLOVÁ} `pán ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD} ${RANLIB} ${.CÍLOVÁ}
Tady pán
("pořadí knihovny") se používá ke generování seznamu závislostí mezi soubory kontrolou tabulky symbolů.
Poznámky k použití
Všimněte si zaměnitelnosti oddělovačů bílého prostoru, takže následující vstupy jsou ekvivalentní:
bb c | a b bc | ab b c | a b b c | abbc |
Dvojice identických položek označuje přítomnost vrcholu, ale ne pořadí (takže následující představuje jeden vrchol bez hran):
a a
Přísně vzato neexistuje topologické uspořádání grafu, který obsahuje jeden nebo více cykly. Tsort však vytiskne varování a GNU tsort vytiskne zjištěné cykly na standardní chyba (řádky začínající na „tsort:“):
$ třídění << EOF> a b> před naším letopočtem> c a> EOFUX: tsort: INFORM: cyklus v datechtsort: atsort: btsort: cAbC
Viz také
Reference
- ^ "třídění". Vydání Open Group Base Specification, vydání 7, 2018. Otevřená skupina.
- ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html
- ^ http://www.freebsd.org/cgi/man.cgi?query=tsort
- ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html
- ^ "c ++ - gcc ld: metoda k určení pořadí propojení statických knihoven". Přetečení zásobníku.
Další čtení
- Knuth, Donald E. (1997). Umění počítačového programování. 1 (3. vyd.). 261–268. ISBN 0-201-89683-4.
- Kahn, A.B. (1962). "Topologické třídění velkých sítí". Komunikace ACM. 5 (11): 558–562. doi:10.1145/368996.369025.
externí odkazy
manuální stránka tsortu na