Recursive function doesn't return correct value

Question

I have a recursive function. It does recursive search of folder which name is given in second argument inside drive or folder which name given in first argument. The folder given in second argument can locate on any path and any nesting level inside drive or folder given in first argument. So function browse all content of drive or folder specified in first argument for finding of folder specified in second argument. Below is function itself:

wstring FolderPathValidator::FindRequiredFolder(const wstring& p_InitialPath, wstring p_RequiredFolderName)
{
      wstring foundFolder = L"";
      wstring folderPath = p_InitialPath + L"\\*";
      WIN32_FIND_DATAW folderInfo;
      HANDLE search_handle = FindFirstFileW(folderPath.c_str(), &folderInfo);
      if (search_handle != INVALID_HANDLE_VALUE)
      {
           vector<wstring> folders;

           do
           {
                if (folderInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
                {
                     if ((!lstrcmpW(folderInfo.cFileName, L".")) || (!lstrcmpW(folderInfo.cFileName, L"..")))
                     continue;
                }

                folderPath = p_InitialPath + L"\\" + wstring(folderInfo.cFileName);

                if (folderInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
                {
                     if (folderInfo.cFileName == p_RequiredFolderName)
                     {
                          foundFolder = folderInfo.cFileName;
                          return foundFolder;
                     }
                     folders.push_back(folderPath);
                }
           } while (FindNextFileW(search_handle, &folderInfo));

           ::FindClose(search_handle);

           for (vector<wstring>::iterator iter = folders.begin(), end = folders.end(); iter != end; ++iter)
               FindRequiredFolder(*iter, p_RequiredFolderName);
      }

      return foundFolder;
}

And in code I call it in the following manner:

wstring FoundFolder = FindRequiredFolder(L"C:", L"TextFiles_to_Test");

But if I direct my function to knowingly right way (where the folder given in second argument exists) it return an empty string. How should I correct the code so the function returns folder found.

I add that I check in debugger step by step and there I see that the function finds required folder but returns an empty string in its call operator.

Answer 1

I was thinking about that caveat I mentioned earlier about returning the first matching folder, so I threw this together:

#define UNICODE
#define _UNICODE
#include <windows.h>
#include <vector>
#include <string>

// Find *all* folders in a directory tree with a given name.
// Params:
//    initialPath      location to start search
//    searchForName    name of folder to search for
//    locations        vector in which to put paths for any matches
//  Returns
//    vector containing all matches (if any).  Same as input parameter,
//    helps with performance on recursion (and also RVO).
std::vector<std::wstring> 
FindRequiredFolderLocations(const std::wstring& initialPath, 
                            const std::wstring& searchForName,
                            std::vector<std::wstring>& locations
                           )
{
    std::wstring searchSpec = initialPath + L"\\*";

    WIN32_FIND_DATA folderInfo;
    HANDLE search_handle = ::FindFirstFile(searchSpec.c_str(), &folderInfo);
    if (search_handle != INVALID_HANDLE_VALUE){
        do{
            if (folderInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY){
                if ((!lstrcmp(folderInfo.cFileName, L".")) || (!lstrcmp(folderInfo.cFileName, L"..")))
                    continue;

                std::wstring fullPath = initialPath + L"\\" + folderInfo.cFileName;
                if (folderInfo.cFileName == searchForName){
                    locations.push_back(fullPath);
                }
                FindRequiredFolderLocations(fullPath, searchForName, locations);
            }
        } while (::FindNextFile(search_handle, &folderInfo));

        ::FindClose(search_handle);
    }
    return locations;
}

// Overload not requiring "locations" vector parameter (see above)
std::vector<std::wstring> 
FindRequiredFolderLocations(const std::wstring& initialPath, 
                            const std::wstring& folderName)
{
    std::vector<std::wstring> result;
    return FindRequiredFolderLocations(initialPath, folderName, result);
}

#ifdef TEST_FRFL
#include <iostream>
void FRFL_Test(const std::wstring& folderName)
{
    std::vector<std::wstring> locations;

    FindRequiredFolderLocations(L"C:",  folderName, locations);
    size_t count = locations.size();
    if (0 == count){
        std::wcout << L"Required folder not found.\n";
    }
    else if (1 == count){
        std::wcout << L"One location found: " << locations[0] << L"\n";
    }
    else{
        std::wcout << L"multiple locations found for required folder name:\n";
        for (auto loc : locations){
            std::wcout << L"\t" << loc.c_str() << L"\n";
        }
        std::wcout << L"Which one do you want?\n";
    }
}

int main()
{
    FRFL_Test(L"!!exists_1_Location");
    FRFL_Test(L"!!exists_several_Locations");
    FRFL_Test(L"!!exists_nowhere");

    return 0;
}

#endif

Build:

C:\tmp>cl /nologo /EHsc /W4 /DTEST_FRFL so-findpathw.cpp

Ran the following commands to create test directories:

C:\tmp>md frfl
C:\tmp>md frfl\a
C:\tmp>md frfl\a\b
C:\tmp>md frfl\a\b\!!exists_1_Location
C:\tmp>md frfl\a\!!exists_several_Locations
C:\tmp>md frfl\a\b\!!exists_several_Locations
C:\tmp>md frfl\!!exists_several_Locations
C:\tmp>md !!exists_several_Locations

Output:

C:\tmp>so-findpathw
One location found: C:\tmp\frfl\a\b\!!exists_1_Location
multiple locations found for required folder name:
      C:\tmp\!!exists_several_Locations
      C:\tmp\frfl\!!exists_several_Locations
      C:\tmp\frfl\a\!!exists_several_Locations
      C:\tmp\frfl\a\b\!!exists_several_Locations
Which one do you want?
Required folder not found.

Don't know if you'll need this, but finding any folder that matches the directory basename you are looking for regardless of where it is actually located in the tree just really bothered me. I'm a bit obsessive like that.

Answer 2

This will return the fully qualified path to the first folder that matches p_RequiredFolderName. If p_RequiredFolderName does not exist, an empty string is returned:

wstring FindRequiredFolder(const wstring& p_InitialPath, const wstring& p_RequiredFolderName)
{
    wstring foundFolder;
    wstring searchSpec = p_InitialPath + L"\\*";
    WIN32_FIND_DATAW folderInfo;
    HANDLE search_handle = ::FindFirstFileW(searchSpec.c_str(), &folderInfo);
    if (search_handle != INVALID_HANDLE_VALUE){
        do{
            if (folderInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY){
                if ((!lstrcmpW(folderInfo.cFileName, L".")) || (!lstrcmpW(folderInfo.cFileName, L"..")))
                    continue;

                wstring fullPath = p_InitialPath + L"\\" + folderInfo.cFileName;
                if (folderInfo.cFileName == p_RequiredFolderName){
                    foundFolder = fullPath;  // we're done.
                }
                else{
                    foundFolder = FindRequiredFolder(fullPath, p_RequiredFolderName);
                }
                if (foundFolder.length()){
                    break;
                }
            }
        } while (::FindNextFileW(search_handle, &folderInfo));

        ::FindClose(search_handle);
    }
    return foundFolder;
}

Answer 3

Your problem is that you are not returning the right thing when you get to the required folder name -

if (folderInfo.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
{
        if (folderInfo.cFileName == p_RequiredFolderName)
        {
            return folderPath;  // <-- return the found (fully qualified) path name
        }
        // else
        folders.push_back(folderPath);
}

You might have a few problems with this approach, though (you may have already considered these): First, this will return the first match, regardless of where it appears in the tree. Consider:

    c:\a\system
    c:\windows\system
    c:\tmp\system

This might be an issue for you.
Also, it takes a fair bit of time. I looked for foo1219, which I just created in c:\tmp and it took a while (recycle bin, documents, program files, etc., are all costly). If you have any user interface for this, you might want to use a dialog box and let the user select a folder. The common dialogs File dialog box could be very helpful.

Answer 4

Try this:

wstring FoundFolder = FindRequiredFolder(L"C:\\", L"TextFiles_to_Test");

You are starting your search in whatever the current working directory for the "C:" drive is - not the root directory of the C: drive.