모든 POSIX 함수 또는 glibc 확장이 폭 우선 파일 트리 워크를 구현합니까?

필자는 파일 액세스를 모니터링하기 위해 inotify를 사용하는 데몬을 작성 중이며 재귀 검색에서 아무 것도 놓치지 않는 것이 중요합니다. 나는 this interesting idea을 발견하고 그것을 구현하기 시작했습니다.모든 POSIX 함수 또는 glibc 확장이 폭 우선 파일 트리 워크를 구현합니까?

ftw() 및 ftw64()는 너비 우선 알고리즘을 사용하지 않으며 더 많은 "선주문"을 사용합니다. nftw()는 깊이 우선 옵션을 제공하지만 위쪽 나뭇잎의 경주가 걱정됩니다.

나는 아마도 GNU 확장 기능을 놓치고 싶다. 아니면 타입 안전 콜백 (실제로는하지 않을 것)으로 내 자신을 구현하는 것을보고 있습니까?

또는 너비 우선의 이점을 처음으로 잘못 이해 한 것입니까?

2009-10-30 Tim Post

아마도 더 이상 필요하지 않지만 nftw (3)의 변형을 먼저 구현했습니다. https://github.com/tavianator/bfs/blob/master/bftw.c –

@TavianBarnes 상당히 훌륭하고 자급적일 것입니다. 아마도 [CCAN] (http://ccodearchive.net/)으로 보낼 것을 고려해보십시오. 이 특별한 경우에, 나는 막 깊이 우선 동작을 한계로 삼았고, 지금 코드를 다시 살펴볼 것이다 : –

허, CCAN에 관해서. 내가 몇 가지 변경 사항을 작성하고 몇 가지 테스트를 작성 후 그것을 업로드에 대해 생각할 것입니다 :) –

'nftw()'의 스펙을 보면, FTW_DEPTH 플래그는 디렉토리 노드를 방문하기 전에 서브 디렉토리를 방문하여 포스트 오더 (깊이 우선) 순회를 수행합니다.

표준 알고리즘이 너비 우선 검색을 수행하지 않는다고 생각합니다.

아마도 nftw() 인터페이스를 기반으로 bfftw()를 작성해야합니다. 검색을 수행하는 동안 재귀 적으로 (디렉토리에) 방문 할 항목을 대기열에 넣어야합니다.

2009-10-30 03:39:51

답변