Эффективно пройти через дерево каталогов с помощью opendir (), readdir () и closedir ()

Question

Подпрограммы C opendir (), readdir () и closedir () позволяют мне пройти через структуру каталогов. Тем не менее, каждая структура dirent, возвращаемая readdir (), по-видимому, не дает мне полезного способа получить набор указателей на DIR, которые мне нужно было бы использовать в подкаталогах каталога.

Конечно, они дают мне имена файлов, так что я могу либо добавить это имя к пути к каталогу и stat () и opendir () к ним, либо изменить текущий рабочий каталог процесса с помощью chdir ( ) и откатите его через chdir ("..").

Проблема с первым подходом заключается в том, что если длина пути к каталогу достаточно велика, то стоимость передачи строки, содержащей ее, в opendir () будет чрезмерной, чем стоимость открытия каталога. Если вы немного более теоретичны, вы можете сказать, что ваша сложность может возрасти за пределы линейного времени (в общем количестве символов (относительных) имен файлов в дереве каталогов).

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

Я принимаю альтернативы этим функциям. Так как же эффективно обходить дерево каталогов UNIX (линейное время в общем количестве символов в файлах под ним)?

Answer 1

Вы пробовали ftw() aka File Tree Walk ?

Snippit от man 3 ftw:

int ftw(const char *dir, int (*fn)(const char *file, const struct stat *sb, int flag), int nopenfd);

ftw () проходит по дереву каталогов, начиная с указанного каталога. Для каждой найденной записи в дереве он вызывает fn () с полным путем к записи, указателем на структуру stat (2) для записи и флагом int

Answer 2

Кажется, вам не хватает одного базового момента: обратный путь в каталогах предполагает чтение данных с диска. Даже когда / если эти данные находятся в кеше, вы в конечном итоге просматриваете изрядное количество кода, чтобы получить его из кеша в свой процесс. Пути также, как правило, довольно короткие - не более пары сотен байтов довольно необычно. Вместе это означает, что вы можете довольно разумно создавать строки для всех путей, без каких-либо проблем. Время, затрачиваемое на создание строк, по-прежнему довольно незначительно по сравнению со временем чтения данных с диска. Это означает, что вы обычно можете игнорировать время, затрачиваемое на манипуляции со строками, и работать исключительно над оптимизацией использования диска.

Мой собственный опыт показывает, что для большинства прохождений по каталогам поиск в ширину обычно предпочтительнее - когда вы пересекаете текущий каталог, поместите полные пути ко всем подкаталогам в нечто вроде очереди с приоритетами. Когда вы закончите обход текущего каталога, извлеките первый элемент из очереди и пройдите его, продолжая до тех пор, пока очередь не станет пустой. Это обычно улучшает локальность кэша, поэтому сокращает время, затрачиваемое на чтение диска. В зависимости от системы (скорость диска относительно скорости процессора, доступная общая память и т. Д.) Она почти всегда по крайней мере так же быстро, как обход в глубину, и может быть в два раза быстрее (или около того).

Answer 3

Способ использования opendir / readdir / closedir - сделать функцию рекурсивной! Взгляните на фрагмент здесь Dreamincode.net .

Надеюсь, это поможет.

РЕДАКТИРОВАТЬ Спасибо R.Sahu, срок действия ссылки истек, однако он нашел ее через архив обратной связи и взял на себя смелость добавить ее в суть . Пожалуйста, помните, чтобы соответственно проверить лицензию и указать оригинального автора в качестве источника! :)

Answer 4

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

https://github.com/hpc/libcircle