time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C++基础 > 非递归遍历指定文件夹下的所有文件及其子文件夹

非递归遍历指定文件夹下的所有文件及其子文件夹

时间:2010-07-12 00:55 点击:2946次 字体:[ ]




一、递归的实现

遍历文件在Windows下可以用 FindFirstFile/FindNextFile 这组API(另外貌似可以使用SHGetDataFromIDList,也可以使用boost),一般是通过递归实现,比如:

#include "strsafe.h"

bool EnumerateFolder(LPCTSTR lpcszFolder, int nLevel = 0)
{
	WIN32_FIND_DATA ffd;
	TCHAR szDir[MAX_PATH];
	HANDLE hFind = INVALID_HANDLE_VALUE;

	StringCchCopy(szDir, MAX_PATH, lpcszFolder);
	StringCchCat(szDir, MAX_PATH, TEXT("\\*"));
	
	// Find the first file in the directory.
	
	hFind = FindFirstFile(szDir, &ffd);
	
	if (INVALID_HANDLE_VALUE == hFind) 
	{
		return false;
	} 
	
	// List all the files in the directory with some info about them.

	TCHAR szOutLine[MAX_PATH] = {0};
	for (int ii = 0; ii < nLevel;   ii)
		szOutLine[ii] = _T('\t');
	
	do
	{
		if (ffd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
		{
			if ( _T('.') != ffd.cFileName[0] )
			{
				_tprintf(TEXT("%s%s   <DIR>\n"), szOutLine, ffd.cFileName);
				StringCchCopy(szDir _tcslen(lpcszFolder) 1, MAX_PATH, ffd.cFileName);

				EnumerateFolder(szDir, nLevel 1);	// recursion here
			}
		}
		else
		{
			_tprintf(TEXT("%s%s\n"), szOutLine, ffd.cFileName);
		}
	}
	while (FindNextFile(hFind, &ffd) != 0);

	FindClose(hFind);
	return true;
}

 

二、递归的潜在问题

可以看到,递归代码的可读性非常好,递归在很多时候的表现也不错,性能不会太差,其实递归和迭代的差别在很多时候不会很大,但每每要用到递归,还是不免想到可能会因使用栈的空间来保存局部变量(还有参数、返回地址等)而导致的stack overflow的问题。

 

系统给程序分配的内存有一部分是用来作栈使用的,栈在最大的地址开始,需要“申请”栈的时候就让栈顶指针也就是esp指向更低(往下“走”)的空间,当栈增长太大乃至超过堆(堆是往上“走”的)的范围时就是所谓stack overflow/collide,可以想象的是要么栈破坏堆上存储的数据,要么就是程序“返回”到非法的地址去执行指令,多么可怕啊,不过现在堆栈貌似是被分配在不同内存页上的,操作系统尽了最大的努力对堆栈进行保护,所以其实也不是很恐怖,大不了就是整个进程被操作系统kill掉。

 

尽管如此,谁也不希望自己的程序这么死掉,那多不给力啊!stack overflow的异常即使用try/catch也不行(C 不能catch这种异常,必须用Windows自己的)递归需要额外的函数调用开销,如果代码是在多线程环境下执行,那还会面临一个系统分配给每个线程的堆栈大小限制的问题,Windows下每个线程默认分配1M的空间

 

那看看上面那个递归版本的函数会需要多少局部空间:WIN32_FIND_DATA 的大小是 320,MAX_PATH的buffer是260,其余变量和参数忽略,那么一次函数调用需要580个字节(ANSI环境),也就是说最大能递归多少层?

答案是 1808 层。

换句话说,从根目录开始,最多只能遍历到1907层深的文件夹结构,再深层的文件就遍历不了了。而实际上,我们是没办法创建这么深层次的目录树结构的,试试看就知道Windows会提示超出限制。

其实看看 MAX_PATH 的值就知道了,不是才260么,哪有可能给你弄到1800多层?

NTFS不是据称很先进么,莫非也这么不给力?在多字节字符环境下,这个限制将使得我们最多只能创建一百多层深的文件夹结构。

 

尽管有人说260个字节在大多情况下都够用了,但也难保会有些BT人士埋怨这个限制,这严重影响了筒子们通过多层文件夹保藏“爱国教育影片”的热情。
 

翻翻MSDN上关于FindFirstFile的说明,原来微软还留有一手:

In the ANSI version of this function, the name is limited to MAX_PATH characters. To extend this limit to 32,767 widecharacters, call the Unicode version of the function and prepend "\\?\" to the path. For more information, see Naming a File.

简单说为了让这个限制突破到32767个宽字节字符(说了是宽字符了,那当然得是UNICODE环境下了),就要在路径前加上 \\?\ (这个办法有个缺点,那就是不能访问根目录)。

 

这下,我们完全有机会遇到1M的线程堆栈限制,虽然搞不懂为什么既然微软已经考虑到并提供了增加文件路径长度的方案,而我们仍然不能创建那么长的路径,但这至少给写个非递归版本的遍历文件函数提供了个理由。

三、迭代(非递归)的实现

 

那就动手写个非递归的吧!既然决定不用递归,那保存和恢复遍历信息的工作就交给程序员自己实现了,也就是说要自己模拟一个“栈”,只不过这个“栈”是在堆上的(很显然堆比栈大的多了)。

STL提供了stack,如果每次push/pop都要申请/释放内存空间,那效率自然不好,我不是很清楚STL对于stack的内部实现,如果它足够聪明应该是可以避免这种情况的。

由于不肯定,我选择了用vector来实现,重点就是在需要pop的时候不删除空间,在需要push的时候使用类似SetAtGrow的机制。

首先写个类来稍微封装一下:

 

// http://msdn.microsoft.com/en-us/library/aa364418(VS.85).aspx
#define EXTEND_FILE_PATH_PREFIX		_T("\\\\?\\")

#ifdef _UNICODE
	#define EXTEND_FILE_PATH_LIMIT
#endif // _UNICODE

#ifdef EXTEND_FILE_PATH_LIMIT
	#define ENUMERATE_PATH_BUFFER_SIZE		32767
#else
	#define ENUMERATE_PATH_BUFFER_SIZE		MAX_PATH
#endif // EXTEND_FILE_PATH_LIMIT

/*----------------------------------------------------------------------------*/
/* CBasicFileEnumerateHelper
/*----------------------------------------------------------------------------*/

class CBasicFileEnumerateHelper
{
public:
	CBasicFileEnumerateHelper()
	{
	}
	virtual ~CBasicFileEnumerateHelper()
	{
	}
public:
	virtual bool FindFirst(LPCTSTR lpcszInitDir)
	{
		m_nFolderLen = _tcslen(lpcszInitDir);
#ifdef EXTEND_FILE_PATH_LIMIT
		// MSDN stated:
		// Note  Prepending the string "\\?\" does not allow access to the root directory.
		_tcscpy(m_szPathBuffer, EXTEND_FILE_PATH_PREFIX);
		_tcscat(m_szPathBuffer, lpcszInitDir);
		m_nFolderLen  = 4;	// for "\\?\"
#else
		_tcscpy(m_szPathBuffer, lpcszInitDir);
#endif // EXTEND_FILE_PATH_LIMIT
		// For FindFirstFile to work, the path can't be end in a trailing backslash (\).
		if ( m_szPathBuffer[m_nFolderLen-1] == _T('\\') )
		{
			m_szPathBuffer[m_nFolderLen-1] = _T('\0');
			--m_nFolderLen;
		}
		return EnumCurDirFirst();
	}

	inline bool FindCurDirNext()
	{
		bool bRet = ::FindNextFile(m_hFind, &m_fileInfo) != FALSE;
		if ( bRet )
		{
			_tcscpy(m_szPathBuffer m_nFolderLen, m_fileInfo.cFileName);
		}
		else
		{
			::FindClose(m_hFind);
			m_hFind = INVALID_HANDLE_VALUE;
		}
		return bRet;
	}

	virtual bool FindSubDirFirst()		{ return false; }
	virtual bool FindParentDirNext()	{ return false; }

	virtual bool Finish() const			{ return INVALID_HANDLE_VALUE == m_hFind; }

	inline LPCTSTR GetPath() const
	{
#ifdef EXTEND_FILE_PATH_LIMIT
		return m_szPathBuffer 4;	// for EXTEND_FILE_PATH_PREFIX
#else
		return m_szPathBuffer;
#endif // EXTEND_FILE_PATH_LIMIT
	}
	inline const FindFileData& GetFileInfo() const	{ return m_fileInfo; }

	inline bool IsFolder() const				{ return (m_fileInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) == FILE_ATTRIBUTE_DIRECTORY; }
	inline bool IsDot() const					{ return (m_fileInfo.cFileName[0] == '.') && ((m_fileInfo.cFileName[1] == '.') || (m_fileInfo.cFileName[1] == '\0')); }
protected:
	virtual bool EnumCurDirFirst()
	{
		m_szPathBuffer[m_nFolderLen  ]	= _T('\\');
		m_szPathBuffer[m_nFolderLen]	= _T('*');
		m_szPathBuffer[m_nFolderLen 1]	= _T('\0');
		HANDLE hFind = ::FindFirstFile(m_szPathBuffer, &m_fileInfo);
		bool bRet = hFind != INVALID_HANDLE_VALUE;
		if ( bRet )
		{
			m_hFind = hFind;
			_tcscpy(m_szPathBuffer m_nFolderLen, m_fileInfo.cFileName);
		}
		return bRet;
	}
protected:
	FindFileData	m_fileInfo;
	TCHAR			m_szPathBuffer[ENUMERATE_PATH_BUFFER_SIZE];
	int				m_nFolderLen;
	HANDLE			m_hFind;
};

class CRecursiveFileEnumerateHelper : public CBasicFileEnumerateHelper
{
public:
	CRecursiveFileEnumerateHelper()
		: m_nFolderLevel(0)
	{
	}
	~CRecursiveFileEnumerateHelper()
	{
		CFE_ASSERT(m_nFolderLevel <= static_cast<int>(m_arrEnumFolderCtx.size()));
		// Don't forget to close these find handles!
		for (int ii = 0; ii < m_nFolderLevel;   ii)
		{
			EnumFolderCtx& efc = m_arrEnumFolderCtx[ii];
			CFE_ASSERT(efc.hFind != INVALID_HANDLE_VALUE);
			::FindClose(efc.hFind);
		}
	}
public:
	virtual bool FindSubDirFirst()
	{
		CFE_ASSERT( IsFolder() && !IsDot() );
		int nCurFolderLen = m_nFolderLen;
		m_nFolderLen  = _tcslen(m_fileInfo.cFileName);
		bool bRet = EnumCurDirFirst();
		if ( !bRet )
		{
			m_nFolderLen = nCurFolderLen;
		}
		return bRet;
	}

	virtual bool FindParentDirNext()
	{
		--m_nFolderLevel;
		if ( m_nFolderLevel > 0 )
		{
			CFE_ASSERT( m_nFolderLevel < static_cast<int>(m_arrEnumFolderCtx.size()) );
			// Retrieve (pop) the info saved inside the array to continue searching.
			EnumFolderCtx& efcParent	= m_arrEnumFolderCtx[m_nFolderLevel-1];
			CFE_ASSERT(m_nFolderLen > efcParent.nFolderPathLen);
			m_nFolderLen				= efcParent.nFolderPathLen;
			m_hFind						= efcParent.hFind;
			return FindCurDirNext();
		}
		return false;
	}

	virtual bool Finish() const
	{
		return CBasicFileEnumerateHelper::Finish() && 0 == m_nFolderLevel;
	}
protected:
	virtual bool EnumCurDirFirst()
	{
		bool bRet = CBasicFileEnumerateHelper::EnumCurDirFirst();
		if ( bRet )
		{
			// Save (push) the current find handle into the array for future backtracking
			EnumFolderCtx efc(m_hFind, m_nFolderLen);
			if ( m_nFolderLevel >= static_cast<int>(m_arrEnumFolderCtx.size()) )
				m_arrEnumFolderCtx.push_back( efc );
			else
				m_arrEnumFolderCtx[m_nFolderLevel] = efc;
			  m_nFolderLevel;
		}
		return bRet;
	}
protected:
	struct EnumFolderCtx 
	{
		EnumFolderCtx(HANDLE _hFind = NULL, int _nFolderPathLen = -1)
			: hFind(_hFind)
			, nFolderPathLen(_nFolderPathLen)
		{
		}
		HANDLE hFind;
		int nFolderPathLen;
	};
	std::vector<EnumFolderCtx>	m_arrEnumFolderCtx;
	int							m_nFolderLevel;
};

然后就是用它们做实事了:

 

bool CFileEnumeratorBase::Enumerate( LPCTSTR lpcszInitDir, bool bFindSubDir /*= true*/ )
{
	if ( !lpcszInitDir || !*lpcszInitDir )
		return false;
	if ( m_hStopEvent )
	{
		::ResetEvent(m_hStopEvent);
	}
	else
	{
		m_hStopEvent = ::CreateEvent(NULL, TRUE, FALSE, NULL);
		if ( !m_hStopEvent )
		{
			m_dwLastError = ::GetLastError();
			OnError();
			return false;
		}
	}
	
	m_bEnumerating	= true;
	bool bRet		= true;

#ifdef FILEENUMERATOR_RECURSION
	bRet = EnumerateSubDir(lpcszInitDir, bFindSubDir);
#else
	CBasicFileEnumerateHelper* pEnumerateHelper = bFindSubDir ? new CRecursiveFileEnumerateHelper() : new CBasicFileEnumerateHelper();
	if ( !pEnumerateHelper->FindFirst(lpcszInitDir) )
	{
		m_dwLastError = ::GetLastError();
		OnError(lpcszInitDir);
	}
	else
	{
		while ( !pEnumerateHelper->Finish() && !IsStopEventSignaled() )
		{
			const FindFileData& fileInfo = pEnumerateHelper->GetFileInfo();
			if ( pEnumerateHelper->IsFolder() )
			{
				if ( !pEnumerateHelper->IsDot() && bFindSubDir )
				{
					IncreaseFindFolderCounter();
					if ( CheckUseDir(pEnumerateHelper->GetPath(), fileInfo) )
					{
						HandleDir(pEnumerateHelper->GetPath(), fileInfo);
						IncreaseAcceptedFolderCounter();
						if ( !pEnumerateHelper->FindSubDirFirst() && !OnError(pEnumerateHelper->GetPath()) )
							break;
					}
				}
			}
			else
			{
				if ( CheckUseFile(pEnumerateHelper->GetPath(), fileInfo) )
				{
					HandleFile(pEnumerateHelper->GetPath(), fileInfo);
					IncreaseFindFileCounter();
				}
			}
			// Continue searching current directory
			if ( !pEnumerateHelper->FindCurDirNext() )
			{
				// We finish a directory! Now we need to backtrack to the parent directory.
				do 
				{
					FinishedDir( pEnumerateHelper->GetPath() );
				} while ( !pEnumerateHelper->FindParentDirNext() && !pEnumerateHelper->Finish() && !IsStopEventSignaled() );
			}
		}
	}
	delete pEnumerateHelper;
#endif // FILEENUMERATOR_RECURSION

	m_hStopEvent	= NULL;
	m_bEnumerating	= false;
	return bRet;
}

 

“很干净的代码”,没多少注释,这点很是羞愧啊,但限于时间关系只好这样了。

 

最后想想实际应用,既然已经用AHK做了个文件查找,那就试试看用VC实现吧,和AHK的精短代码比起来,VC实现的代码量实在太惊人了,没办法贴上来了,只好打包。

 

最终实现效果:

非递归遍历指定文件夹下的所有文件及其子文件夹_www.fengfly.com

 

非递归遍历指定文件夹下的所有文件及其子文件夹_www.fengfly.com

 

猛击此处下载 源码和demo。

 

免责声明:

源代码和demo在此提供,没有任何限制,你可以自由地拷贝、分发、修改源代码,也可用于各种邪恶(或善良)用途,但你必须自行承担风险,既然是free的,本人自然不对代码提供任何保证和“售后服务”。



本文地址 : http://www.fengfly.com/plus/view-183719-1.html
标签:
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码: