Эффективный способ перемещения дерева каталогов, содержащего циклы ссылок

Question

Есть ли более эффективный способ перехода к дереву каталогов, содержащему циклы ссылок, чем отслеживание файлов, которые уже были посещены?

Для примера рассмотрит ходьбу каталога, содержащий эти файлы:

symlink "parent" -> ".." 
symlink "uh_oh" -> "/" 
regular file "reg" 
symlink "reg2" -> "reg" 

Answer 1

Вы должны также отслеживать, какие каталогов которые были посещены, согласно вашему первому примеру, но в противном случае нет лучшего решения, чем сохранение посещенных флагов для каждого файла.

Поддержание флагов было бы проще, если бы был переносимый способ получения короткого уникального идентификатора для смонтированной файловой системы. Даже тогда вам нужно подумать о последствиях операций mount и umount, возникающих во время сканирования, в частности, поскольку такое сканирование может занять довольно много времени, если дерево файловой системы включает в себя удаленные файловые системы.

В теории вы можете получить «идентификатор файловой системы» с интерфейса stafvfs, но на практике это не полностью переносимо. Цитирование man statfs из дистрибутива:

Никто не знает, что f_fsid должен содержать & hellip;

& hellip; Общая идея состоит в том, что f_fsid содержит некоторые случайные вещи, так что пара (f_fsid,ino) однозначно определяет файл. Некоторые операционные системы используют (вариант) номер устройства или номер устройства в сочетании с типом файловой системы. Несколько ОС ограничивают выделение поля f_fsid только суперпользователю (и нулевое значение для непривилегированных пользователей), поскольку это поле используется в дескрипторе файла файловой системы при экспорте NFS и выдает его из соображений безопасности.

Это последнее ограничение - что f_fsid представлен как 0 для непривилегированных пользователей - не нарушает стандарт Posix упоминавшегося выше, потому что стандарт включает в себя очень общий disclaimer: «Не определен ли все члены структура statvfs имеет значимые значения для всех файловых систем ».

Answer 2

Древа ходьбы алгоритм гарантирует, что вы будете посещать каждый файл в директории, поэтому вместо того, чтобы отслеживать отдельные файлы, которые вы можете сохранить список поиска «корни»:

• Добавить начальный каталог в список корней
• Прогулка по дереву каталогов для каждого корня поиска
• Для каждой найденной символической ссылки проверьте, содержится ли она в корне пользователя поиска. Если это не так, добавьте его в качестве нового корня поиска.

Таким образом, вы посетите каждый файл и каталог, никогда не застрянете в цикле, но можете посещать файлы и каталоги более одного раза. Это может произойти только тогда, когда вы найдете символическую ссылку на предка существующего корня. Чтобы этого не произошло, вы можете проверить, является ли каталог корнем поиска, прежде чем вводить его.