Цорт - Tsort

Чтобы узнать о местонахождении Плоского мира, см. Плоский мир (мир) § Цорт.

цорт
изначальный выпуск1979; 41 год назад (1979)
Операционная системаUnix, Unix-подобный, V, Inferno
ТипКоманда

В цорт программа - это командная строка утилита на Unix и Unix-подобный платформы, которая выполняет топологическая сортировка на его входе. По состоянию на 2017 год, это часть POSIX.1 стандарт.[1]

История

Согласно его Информация[2] страница, эта команда изначально была написана для упорядочивания объектных файлов, что позволило компоновщик обрабатывать их последовательно (каждый ровно один раз и по порядку). Страница руководства FreeBSD появилась в Версия 7 Unix.[3]

Обратите внимание, что следующее описание описывает поведение FreeBSD реализация tsort и упоминает возможности GNU, где они могут существовать. Другие реализации или версии могут отличаться.

Синтаксис

tsort [-dlq] [ФАЙЛ]

Возможные варианты FreeBSD:

-d включить отладку -l искать и отображать самый длинный цикл. -q не отображать информационные сообщения о циклах.

GNU предоставляет только следующие возможности:

--help отобразить справочное сообщение и выйти - версия отобразить информацию о версии и выйти

POSIX не предписывает никаких опций.

Поведение

tsort читает свой ввод (из данного ФАЙЛА или стандартный ввод если входной файл не указан или для ФАЙЛА '-') в виде пар строк, разделенных пробелами, что указывает на частичный порядок. На выходе получается полный порядок, соответствующий данному частичному порядку.[4]

Другими словами: для ориентированный ациклический граф (используется как граф зависимостей ), tsort создает список вершин, так что для всех ребер 'a-> b', 'a' стоит перед 'b' в списке.

Примеры

tsort перечисляет вершины ориентированный ациклический граф в таком порядке, чтобы соблюдались все отношения упорядочения / направления:

$ цорт << EOF> 3 8> 3 10> 5 11> 7 8> 7 11> 8 9> 11 2> 11 9> 11 10> EOF3571181029
образец DAG

График звонков

tsort может помочь переупорядочить функции в исходном файле так, чтобы до их использования было определено как можно больше функций (интерпретируйте следующее как: главный() звонки parse_options (), tail_file () и tail_forever (); tail_file () звонки красивое имя(), и так далее. В результате dump_remainder () должен быть определен первым, start_lines () второй и т. д.):

$ граф вызовов кошекосновной parse_optionsосновной файл tailmain tail_forevertail_file pretty_nametail_file write_headertail_file хвостtail_forever перепроверьтеtail_forever pretty_nametail_forever write_headertail_forever dump_remainderхвост tail_linesхвост 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_remainderперепроверьте pretty_name
$ # примечание: 'tac' меняет порядок$ график вызовов tsort | таксdump_remainderstart_linesfile_linespipe_linesxlseekstart_bytespipe_bytestail_linestail_bytesкрасивое имяwrite_headerхвостперепроверитьparse_optionstail_filetail_foreverглавный

Библиотека

Традиционный ld (Компоновщик Unix) требует, чтобы входные данные его библиотеки были отсортированы в топологическом порядке, поскольку он обрабатывает файлы за один проход. Это касается как статических библиотек (* .a) и динамические библиотеки (*.так), а в случае статических библиотек предпочтительно для отдельных объектных файлов, содержащихся внутри.[5]

BSD UNIX использует tsort как общую часть типичного ар & ранлиб вызовы команд (из /usr/share/mk/bsd.lib.mk):

lib $ {LIB} .a: ${OBJS} ${STATICOBJS}    @${ЭХО} статика здания ${LIB} библиотека @${AR} cq ${.ЦЕЛЬ} `лорд ${OBJS} ${STATICOBJS} | tsort -q` ${ARADD}    ${РАНЛИБ} ${.ЦЕЛЬ}

Здесь лорд ("библиотечный порядок") используется для создания списка межфайловых зависимостей путем проверки таблицы символов.

Примечания по использованию

Обратите внимание на взаимозаменяемость разделителей пробелов, поэтому следующие входные данные эквивалентны:

а бб в
а б до н.э.
ab b c
а б б в
abbc

Пары одинаковых элементов указывают на наличие вершины, но не на порядок (так что следующее представляет собой одну вершину без ребер):

а а

Строго говоря, не существует топологического упорядочения графа, содержащего один или несколько циклы. Однако tsort выводит предупреждение, а GNU tsort выводит обнаруженные циклы к стандартная ошибка (строки, начинающиеся с 'tsort:'):

$ цорт << EOF> а б> до н.э> c a> EOFUX: tsort: INFORM: цикл данныхцорт: ацорт: бtsort: cабc

Смотрите также

Рекомендации

  1. ^ "цорт". Базовые спецификации Open Group, выпуск 7, издание 2018 г.. Открытая группа.
  2. ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-background.html
  3. ^ http://www.freebsd.org/cgi/man.cgi?query=tsort
  4. ^ https://www.gnu.org/software/coreutils/manual/html_node/tsort-invocation.html
  5. ^ "c ++ - gcc ld: метод определения порядка компоновки статических библиотек". Переполнение стека.

дальнейшее чтение

внешняя ссылка

справочная страница цорта на