What is the fastest way to get only directory list

Question

I need to build a tree structure recursively of only directories for a given root/parent path. something like "browse for folder" dialog.

Delphi's FindFirst (FindFirstFile API) is not working with faDirectory and FindNext will get all files (it uses faAnyFile regardless of the specified faDirectory) not only directories. which make the process of building the tree very slow.

Is there a fast way to get a directory list (tree) without using FindFirst/FindNext?

Answer 1

the absolute fastest way, use the NtQueryDirectoryFile api. with this we can query not single file but many files at once. also select what information will be returned (smaller info - higher speed). example (with full recursion)

// int nLevel, PSTR prefix for debug only
void ntTraverse(POBJECT_ATTRIBUTES poa, int nLevel, PSTR prefix)
{
    enum { ALLOCSIZE = 0x10000 };//64kb

    if (nLevel > MAXUCHAR)
    {
        DbgPrint("nLevel > MAXUCHAR\n");
        return ;
    }

    NTSTATUS status;
    IO_STATUS_BLOCK iosb;
    UNICODE_STRING ObjectName;
    OBJECT_ATTRIBUTES oa = { sizeof(oa), 0, &ObjectName };

    DbgPrint("%s[<%wZ>]\n", prefix, poa->ObjectName);

    if (0 <= (status = NtOpenFile(&oa.RootDirectory, FILE_GENERIC_READ, poa, &iosb, FILE_SHARE_VALID_FLAGS, 
        FILE_SYNCHRONOUS_IO_NONALERT|FILE_OPEN_REPARSE_POINT|FILE_OPEN_FOR_BACKUP_INTENT)))
    {
        if (PVOID buffer = new UCHAR[ALLOCSIZE])
        {
            union {
                PVOID pv;
                PBYTE pb;
                PFILE_DIRECTORY_INFORMATION DirInfo;
            };

            while (0 <= (status = NtQueryDirectoryFile(oa.RootDirectory, NULL, NULL, NULL, &iosb, 
                pv = buffer, ALLOCSIZE, FileDirectoryInformation, 0, NULL, FALSE)))
            {

                ULONG NextEntryOffset = 0;

                do 
                {
                    pb += NextEntryOffset;

                    ObjectName.Buffer = DirInfo->FileName;

                    switch (ObjectName.Length = (USHORT)DirInfo->FileNameLength)
                    {
                    case 2*sizeof(WCHAR):
                        if (ObjectName.Buffer[1] != '.') break;
                    case sizeof(WCHAR):
                        if (ObjectName.Buffer[0] == '.') continue;
                    }

                    ObjectName.MaximumLength = ObjectName.Length;

                    if (DirInfo->FileAttributes & FILE_ATTRIBUTE_DIRECTORY)
                    {
                        ntTraverse(&oa, nLevel + 1, prefix - 1);
                    }

                } while (NextEntryOffset = DirInfo->NextEntryOffset);    
            }

            delete [] buffer;

            if (status == STATUS_NO_MORE_FILES)
            {
                status = STATUS_SUCCESS;
            }
        }

        NtClose(oa.RootDirectory);
    }

    if (0 > status)
    {
        DbgPrint("---- %x %wZ\n", status, poa->ObjectName);
    }
}
   


void ntTraverse()
{
    BOOLEAN b;
    RtlAdjustPrivilege(SE_BACKUP_PRIVILEGE, TRUE, FALSE, &b);

    char prefix[MAXUCHAR + 1];
    memset(prefix, '\t', MAXUCHAR);
    prefix[MAXUCHAR] = 0;

    STATIC_OBJECT_ATTRIBUTES(oa, "\\systemroot");
    ntTraverse(&oa, 0, prefix + MAXUCHAR);
}

but if you use interactive tree - you not need expand all tree at once, but only top level, handle TVN_ITEMEXPANDING with TVE_EXPAND and TVN_ITEMEXPANDED with TVE_COLLAPSE for expand/ collapse nodes on user click and set cChildren

if use FindFirstFileExW with FIND_FIRST_EX_LARGE_FETCH and FindExInfoBasic this give to as near NtQueryDirectoryFile perfomance, but little smaller:

WIN32_FIND_DATA fd;
HANDLE hFindFile = FindFirstFileExW(L"..\\*", FindExInfoBasic, &fd, FindExSearchLimitToDirectories, 0, FIND_FIRST_EX_LARGE_FETCH);
if (hFindFile != INVALID_HANDLE_VALUE)
{
    do 
    {
        if (fd.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
        {
            if (fd.cFileName[0] == '.')
            {
                switch (fd.cFileName[1])
                {
                case 0:
                    continue;
                case '.':
                    if (fd.cFileName[2] == 0) continue;
                    break;
                }
            }
            DbgPrint("%S\n", fd.cFileName);
        }
    } while (FindNextFile(hFindFile, &fd));

    FindClose(hFindFile);
}

unfortunately FindExSearchLimitToDirectories not implemented currently

Answer 2

Find(First|Next)/File() is a viable solution, especially in Delphi 7. Just filter out the results you don't need, eg:

if FindFirst(Root, faDirectory, sr) = 0 then
try
  repeat
    if (sr.Attr and faDirectory <> 0) and (sr.Name <> '.') and (sr.Name <> '..') then
    begin
      // ... 
    end;
  until FindNext(sr) <> 0;
finally
  FindClose(sr);
end;

If that is not fast enough for you, then other options include:

1. On Win7+, use FindFirstFileEx() with FindExInfoBasic and FIND_FIRST_EX_LARGE_FETCH. That will provide speed improvements over FindFirstFile().

2. access the filesystem metadata directly. On NTFS, you can use DeviceIoControl() to enumerate the Master File Table directly.