Duyệt cây thư mục hiệu quả với opendir(), readdir() và closir()

Question

C routines opendir(), readdir() và closir() cung cấp một cách để tôi duyệt qua một cấu trúc thư mục. Tuy nhiên, mỗi cấu trúc dirent được trả về bởi readdir() dường như không cung cấp một cách hữu ích cho tôi để có được tập hợp các con trỏ tới DIR mà tôi sẽ cần phải recurse vào thư mục con thư mục.

Tất nhiên, họ cho tôi tên tệp, vì vậy tôi có thể nối tên đó vào đường dẫn thư mục và chỉ mục() và opendir() hoặc tôi có thể thay đổi thư mục làm việc hiện tại của quá trình qua chdir() và cuộn nó trở lại thông qua chdir ("..").

Vấn đề với cách tiếp cận đầu tiên là nếu chiều dài của đường dẫn thư mục đủ lớn, thì chi phí để chuyển một chuỗi chứa nó tới opendir() sẽ vượt quá chi phí mở thư mục. Nếu bạn có một chút lý thuyết hơn, bạn có thể nói sự phức tạp của bạn có thể tăng vượt quá thời gian tuyến tính (trong tổng số ký tự của các tên tập tin (tương đối) trong cây thư mục).

Ngoài ra, cách tiếp cận thứ hai có vấn đề. Vì mỗi tiến trình có một thư mục làm việc hiện tại, tất cả chỉ một luồng sẽ phải chặn trong một ứng dụng đa luồng. Ngoài ra, tôi không biết nếu thư mục làm việc hiện tại chỉ là một sự thuận tiện đơn thuần (tức là, đường dẫn tương đối sẽ được nối vào nó trước một truy vấn hệ thống tập tin). Nếu có, cách tiếp cận này cũng sẽ không hiệu quả.

Tôi chấp nhận lựa chọn thay thế cho các chức năng này. Vì vậy, làm thế nào nó có thể đi qua một cây thư mục UNIX hiệu quả (thời gian tuyến tính trong tổng số ký tự của các tập tin theo nó)?

Answer 1

Cách sử dụng opendir/readdir/closedir là làm cho hàm đệ quy! Hãy xem đoạn mã tại đây theo số Dreamincode.net.

Hy vọng điều này sẽ hữu ích.

EDIT Cảm ơn R.Sahu, các linky đã hết hạn, tuy nhiên, tìm thấy nó qua wayback archive và mất sự tự do để thêm nó vào gist. Hãy nhớ, để kiểm tra giấy phép cho phù hợp và thuộc tính tác giả ban đầu cho nguồn! :)

Answer 2

Bạn dường như thiếu một điểm cơ bản: truyền tải thư mục liên quan đến việc đọc dữ liệu từ đĩa. Ngay cả khi/nếu dữ liệu đó nằm trong bộ nhớ cache, bạn sẽ phải trải qua một số lượng mã hợp lý để lấy nó từ bộ nhớ cache vào trong tiến trình của bạn. Đường dẫn cũng thường khá ngắn - bất kỳ hơn một vài trăm byte là khá bất thường. Cùng nhau này có nghĩa là bạn có thể khá hợp lý xây dựng dây cho tất cả các đường dẫn bạn cần mà không có bất kỳ vấn đề thực sự. Thời gian xây dựng dây vẫn còn khá nhỏ so với thời gian đọc dữ liệu từ đĩa. Điều đó có nghĩa là bạn thường có thể bỏ qua thời gian dành cho thao tác chuỗi và chỉ làm việc tối ưu hóa việc sử dụng đĩa.

Trải nghiệm của riêng tôi là cho hầu hết các thư mục lướt qua tìm kiếm rộng rãi thường thích hợp hơn - khi bạn duyệt qua thư mục hiện tại, hãy đặt đường dẫn đầy đủ đến tất cả các thư mục con trong một hàng đợi ưu tiên. Khi bạn hoàn thành việc duyệt qua thư mục hiện tại, hãy kéo mục đầu tiên từ hàng đợi và duyệt qua nó, tiếp tục cho đến khi hàng đợi rỗng. Điều này thường cải thiện vị trí bộ nhớ cache, do đó, nó làm giảm lượng thời gian đọc đĩa. Tùy thuộc vào hệ thống (tốc độ đĩa so với tốc độ CPU, tổng bộ nhớ có sẵn, v.v.) nó gần như luôn luôn nhanh nhất là tốc độ truyền tải đầu tiên, và có thể dễ dàng lên tới gấp đôi (hoặc lâu hơn).

Answer 3

Bạn đã thử ftw() hay còn gọi là Tệp Tree Walk Walk?

SNIPPIT từ man 3 ftw:

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

ftw() đi qua cây thư mục bắt đầu từ dir thư mục được chỉ định. Đối với mỗi mục nhập tìm thấy trong cây, nó gọi fn() với tên đường dẫn đầy đủ của mục nhập, con trỏ tới cấu trúc chỉ số (2) cho mục nhập và cờ int

Answer 4

Có thể quá mức cần thiết cho ứng dụng của bạn, nhưng đây là thư viện được thiết kế để duyệt qua một cây thư mục với hàng trăm triệu tệp.

https://github.com/hpc/libcircle