Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для локации Плоский мир см. Плоский мир (мир) § Цорт .

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

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

История [ править ]

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

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

Синтаксис [ править ]

tsort [-dlq] [ФАЙЛ]

Опции FreeBSD могут быть:

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

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

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

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

Поведение [ править ]

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

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

Примеры [ править ]

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

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

График звонков [ править ]

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

$ Кошки вызова графа Основные parse_options основной tail_file главный tail_forever tail_file pretty_name tail_file write_header tail_file хвост tail_forever перепроверки tail_forever pretty_name tail_forever write_header tail_forever dump_remainder хвост tail_lines хвост 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 перепроверки pretty_name
$  # note: 'tac' меняет порядок $ tsort call-graph | ТАС dump_remainder start_lines file_lines pipe_lines xlseek start_bytes pipe_bytes tail_lines tail_bytes pretty_name write_header хвост перепроверка parse_options tail_file tail_forever главным

Библиотека [ править ]

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

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

lib $ {LIB} .a : $ { OBJS } $ { STATICOBJS } @ $ { ECHO } создание статической библиотеки $ { LIB } @ $ { AR } cq $ { .TARGET }  ` lorder $ { OBJS }  $ { STATICOBJS }  | tsort -q `  $ { ARADD }  $ { RANLIB }  $ { .TARGET }

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

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

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

abдо н.э
abbc
аBBC
abbc
аббc

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

аа

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

$ tsort << EOF > ab > bc > ca > EOF UX: tsort: INFORM: цикл в данных tsort: a tsort: b tsort: c a b c

См. Также [ править ]

  • Сортировка (Unix)
  • Марка (программное обеспечение)
  • Топологическая сортировка
  • Список команд Unix

Ссылки [ править ]

  1. ^ "цорт" . Открытая группа Базовые характеристики Выпуск 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: метод определения порядка компоновки статических библиотек" . Переполнение стека .

Дальнейшее чтение [ править ]

  • Кнут, Дональд Э. (1997). Искусство программирования . 1 (3-е изд.). С. 261–268. ISBN 0-201-89683-4.
  • Кан, А.Б. (1962). «Топологическая сортировка больших сетей». Коммуникации ACM . 5 (11): 558–562. DOI : 10.1145 / 368996.369025 .

Внешние ссылки [ править ]

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

  • FreeBSD ,
  • OpenBSD ,
  • NetBSD ,
  • AIX ,
  • Солярис ,
  • HP-UX
  • dep-trace Заказывает основные зависимости и разворачивает вложенные. (базовый: без предположения о 2D-графике)