통곡하다

tsort 프로그램은 유닉스 및 유닉스 유사 플랫폼의 명령줄 유틸리티로, 입력에서 위상학적 정렬을 수행한다.2017년^[update] 현재 POSIX.1 표준의 일부다.^[1]

역사

그것의 정보^[2] 페이지에 따르면, 이 명령은 처음에 링크커가 그것들을 순차적으로 (각각 정확히 한 번, 그리고 순서대로) 처리할 수 있도록 하는 객체 파일의 순서를 제공하기 위해 작성되었다.프리비SD 수동 페이지는 버전 7 Unix로 표시된다.^[3]

다음 설명은 FreeB의 동작을 설명하고 있다는 점에 유의하십시오.SD 구현의 tsort 및 GNU 기능이 존재할 수 있는 곳에 언급한다.다른 구현 또는 버전은 다를 수 있다.

구문

tsort [-dlq] [FILE] 

FreeBSD 옵션은 다음과 같을 수 있다.

-d 디버깅 켜기 -l 검색하여 가장 긴 사이클을 표시함. -q 사이클에 대한 정보 메시지를 표시하지 않음. 

GNU는 다음 옵션만 제공한다.

--도움말 표시 도움말 메시지 및 종료 --버전 표시 버전 정보 및 종료

POSIX에서 규정하는 옵션은 없다.

행동

tsort는 입력(주어진 FILE 또는 입력 파일이 없는 경우 표준 입력에서 또는 '-')의 FILE을 문자열 쌍으로 읽으며, 공백으로 구분하여 부분 순서를 나타낸다.출력은 주어진 부분 순서에 해당하는 총 순서다.^[4]

즉, 지시된 아세클릭 그래프(상속성 그래프로 사용)의 경우 tsort는 정점 목록을 생성하여 모든 에지 'a-'b'에 대해 'a'가 목록에서 'b'보다 앞에 오도록 한다.

예

tsort는 모든 순서/방향 관계를 존중하는 순서로 지시된 아세클릭 그래프의 정점을 나열한다.

$ tsort <<3 8 > 3 10 > 5 11 > 7 8 > 8 > 8 9 > 11 2 > 11 10 > 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()두 번째 등:

$cat call-graph 메인 tail_file main tail_file main tail_tail_file prety_name tail_file tail_file tail_file tail_file tail_filename tail_reat_name tail_wit_weat_line tail_lines file_lieatt_lieatt_lieatt_limpip_lieater_lines.nes tail_sky xlseek tail_limit start_limit tail_limits dump_limits dump_lines dump_limit_name 재점검

$ # note: $ tsort call-graph tac dump_start_lines file_lines_lines_lines_lines xlseek start_lines_lines pipe_write_name tailseck parse_file tail_file_file_main main main.

도서관

기존의 ld(유닉스 링커)는 한 번의 통과로 파일을 처리하기 때문에 라이브러리 입력을 위상학적 순서로 정렬할 것을 요구한다.이는 정적 라이브러리 모두에 적용된다(*.a) 및 동적 라이브러리(*.so(), 그리고 가급적 안에 포함된 개별 객체 파일에 대해 정적 라이브러리의 경우.^[5]

BSD UNIX는 tsort를 일반적인 ar & ranlib 명령 호출의 일반적인 부분으로 사용한다( /usr/share/mk/bsd.lib.mk).

lib${LIB}.a: ${OBJS} ${STICOBJS} @${ECHO} 빌딩 정적 ${LIB} 라이브러리 @${{$}AR} cq ${.대상} '주문 ${OBJS} ${STICOBJS} tsort -q' ${ARADD}${RANLIB}${RANLIB}${{RANJS}${{RONIB}${}}}}}${}}}.대상}

여기lorder("순서 순서")는 기호 표를 검사하여 파일 간 종속성 목록을 생성하는 데 사용된다.

사용 참고 사항

화이트 스페이스 분리기의 호환성에 주목하여 다음 입력이 동일하도록 하십시오.

b b b c

b b b c

b b b c

b b b c

b b b c

동일한 항목 쌍은 정점이 존재하지만 순서가 아니다. 따라서 다음은 가장자리가 없는 하나의 정점을 나타낸다.

a의

엄밀히 말하면, 한 개 이상의 사이클을 포함하는 그래프의 위상학적 순서는 없다.그러나 tsort는 경고를 인쇄하고 GNU tsort는 탐지된 사이클을 표준 오차('tort:'로 시작하는 라인)로 인쇄한다.

$ tsort <<<EOF > a b > c > a > EOF UX: tsort: INFORM: 데이터 tsort: tsort: b tsort: c a b c

참고 항목

• 정렬(유닉스)
• 만들기(소프트웨어)
• 위상 분류
• Unix 명령 목록
• 통화 그래프

참조

추가 읽기

• Knuth, Donald E. (1997). The Art of Computer Programming. Vol. 1 (3rd ed.). pp. 261–268. ISBN 0-201-89683-4.
• Kahn, A.B. (1962). "Topological sorting of large networks". Communications of the ACM. 5 (11): 558–562. doi:10.1145/368996.369025. S2CID 16728233.

외부 링크

에 관한 토막글.

• FreeBSD,
• 오픈BSD,
• NetBSD,
• AIX,
• Solaris,
• HP-UX
• 추적 방지 기본 종속성을 주문하고 중첩된 종속성을 전개한다. (기본: 2D 그래픽 추정 없이)