广度遍历删除文件

Tips

最近遇到一个要删除文件夹的问题,文件夹内有大量文件和子文件夹,而且结构非常复杂,删除特别慢。于是思考了一下如何能加速文件删除的问题。我看到大部分的实现方法都是深度遍历,即遇到新的文件夹就进入文件夹遍历文件,直到结束后返回上一层继续遍历。实际上这种方法存在一个问题,在我们的硬盘上,文件夹和文件一般是B-Tree分布的,所以同一层文件夹的文件的数据都比较相近,而不同的层的文件夹的文件可能差距比较远,于是深度遍历让硬盘磁头从一个文件夹跨越到另外一个文件夹,磁头花的时间更长了,更何况子文件夹遍历结束,还得从子文件夹在移动回父文件夹。而是用广度遍历就不同,他把当前目录遍历完成后才去遍历另外一个,这样磁头移动的总距离肯定更少,遍历速度当然更快。以下代码我的一个实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <vector>
#include <stack>
#include <string>

class AutoFindHandle {
public:
AutoFindHandle(HANDLE find_handle) : find_handle_(find_handle) {}
~AutoFindHandle() {
FindClose(find_handle_);
}

private:
HANDLE find_handle_;
};

BOOL CollectFileAndDir(const std::wstring &dir, std::vector<std::wstring> &file_path, std::vector<std::wstring> &dir_path)
{
HANDLE find_handle;
WIN32_FIND_DATAW data;
std::wstring temp_path;
std::wstring current_dir = dir;
std::stack<std::wstring> temp_dir;

if (current_dir[current_dir.length() - 1] != L'\\') {
current_dir += L"\\";
}

std::wstring path = current_dir + L"*";

find_handle = FindFirstFileW(path.c_str(), &data);
if (find_handle == INVALID_HANDLE_VALUE) {
return TRUE;
}

AutoFindHandle auto_find_handle(find_handle);

if (wcscmp(data.cFileName, L"..") != 0 &&
wcscmp(data.cFileName, L".") != 0) {

temp_path = current_dir;
temp_path += data.cFileName;

if ((data.dwFileAttributes & (FILE_ATTRIBUTE_HIDDEN | FILE_ATTRIBUTE_READONLY | FILE_ATTRIBUTE_SYSTEM)) != 0) {
SetFileAttributesW(temp_path.c_str(), FILE_ATTRIBUTE_NORMAL);
}

if ((data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0) {

temp_dir.push(temp_path);

}
else {

file_path.push_back(temp_path);

}
}

while (FindNextFileW(find_handle, &data)) {

if (wcscmp(data.cFileName, L"..") != 0 &&
wcscmp(data.cFileName, L".") != 0) {

temp_path = current_dir;
temp_path += data.cFileName;

if ((data.dwFileAttributes & (FILE_ATTRIBUTE_HIDDEN | FILE_ATTRIBUTE_READONLY | FILE_ATTRIBUTE_SYSTEM)) != 0) {
SetFileAttributesW(temp_path.c_str(), FILE_ATTRIBUTE_NORMAL);
}

if ((data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) != 0) {

temp_dir.push(temp_path);

}
else {

file_path.push_back(temp_path);

}
}

}

while (!temp_dir.empty()) {

CollectFileAndDir(temp_dir.top(), file_path, dir_path);

temp_dir.pop();
}


dir_path.push_back(dir);
return TRUE;
}


BOOL DeleteFolder(LPCWSTR path)
{
std::vector<std::wstring> file_path;
std::vector<std::wstring> dir_path;
if (!CollectFileAndDir(path, file_path, dir_path)) {
return FALSE;
}


for (std::vector<std::wstring>::iterator it = file_path.begin(); it != file_path.end(); ++it) {
DeleteFileW(it->c_str());
}

for (std::vector<std::wstring>::iterator it = dir_path.begin(); it != dir_path.end(); ++it) {
RemoveDirectoryW(it->c_str());
}

return TRUE;
}

Post Directory

Article directory