Structuring/organizing 文件系统文件夹的链接列表

Question

TLDR:

I need to know how I can represent a filesystem using a linked-list struct, when the node traversal is in a weirdly reversed depth-first, alphabetical order, knowing only two things at a time:

The full file (or folder) path, and:

Is this node a file, or a folder?

详情：

UE4 通过 IPlatformFile.
支持 built-in、cross-platform 文件系统操作对于文件系统遍历，他们包括以下方法：

我的目标是填写以下结构：

struct FFolderNode
{
public:
    FFolderNode() : FFolderNode(nullptr, TEXT(""), TEXT("")) {};
    FFolderNode(const FString& Path, const FString& Name) : FFolderNode(nullptr, Path, Name) {};
    FFolderNode(FFolderNode *ParentNode, const FString& Path, const FString& Name) : ParentNode(ParentNode), Path(Path), Name(Name)
    {
        ID = FGuid::NewGuid();
    };

    // Makes it easier to identify, map & find this node
    FGuid ID;
    // The name of this directory
    FString Name;
    // The path of this directory
    FString Path;
    // The filenames this directory contains
    TArray<FString> FileNames;
    // The upwards directory (equivalent to the path "..")
    FFolderNode *ParentNode;
    // The subfolders (if any) contained within this directory
    TArray<FFolderNode*> ChildNodes;
};

我遇到的问题...
我将项目的 Contents 文件夹路径传递给 IPlatformFile::IterateDirectory，它会执行以下操作：

看起来像字母顺序？所以我不确定从哪里开始。
似乎我需要能够在创建和分配它们的 parents 之前创建节点，并且在没有任何真正的所有权先验知识的情况下，除了当前访问的节点是文件或文件夹之外，它的完整路径作为字符串.

IPlatformFile::FDirectoryVisitor::Visit is the recursive function called by IterateDirectory... The engine source seems to make an inline class which subclasses FDirectoryVisitor 并重写此方法，这就是我在代码中所做的：

FFolderNode UDSAssetManager::GetContentTree()
{
    static auto ContentPath = FPaths::ConvertRelativePathToFull(FPaths::GameContentDir());

    class FFolderVisitor : public IPlatformFile::FDirectoryVisitor
    {
    public:
        IPlatformFile& PlatformFile;

        FFolderVisitor(IPlatformFile& InPlatformFile) :
            PlatformFile(InPlatformFile), RootNode(nullptr), PreviousNode(nullptr),
            FolderDepth(-1), PreviousDepth(-1) {};

        FFolderNode *CreateRootNode(const FString& Path, const FString& Name)
        {
            VisitedNodes.Empty();
            if (RootNode != nullptr)
                delete RootNode; // TODO: Traverse entire tree, releasing memory for all child nodes

            TArray<FString> SubPath;
            Path.ParseIntoArray(SubPath, TEXT("/"));
            if (SubPath.Num() > 0 && SubPath[SubPath.Num() - 1] == Name)
                SubPath.RemoveAt(SubPath.Num() - 1);

            return RootNode = new FFolderNode(FString::Join(SubPath, TEXT("/")), Name);
        };

        virtual bool Visit(const TCHAR* FilenameOrDirectory, bool bIsDirectory) override
        {
            auto Path = FString(FilenameOrDirectory);
            auto Result = PlatformFile.IterateDirectory(FilenameOrDirectory, *this);

            if (RootNode == nullptr)
                return false;

            FFolderNode *ThisNode = nullptr;
            if (VisitedNodes.Num() < 1)
                ThisNode = RootNode;
            else
                ThisNode = new FFolderNode();

            auto TempPath = Path.Replace(*ContentPath, TEXT(""));
            TArray<FString> PathArray;
            TempPath.ParseIntoArray(PathArray, TEXT("/"));
            FolderDepth = PathArray.Num();

            //
            // DO SOMETHING here, even though RootNode is NOT guaranteed
            // to be the actual root of the tree... ?
            //

            PreviousNode = ThisNode;
            PreviousDepth = FolderDepth;
            VisitedNodes.Add(ThisNode);

            return true;
        };

        FORCEINLINE FFolderNode GetRootNode() const {
            if (RootNode == nullptr)
                return FFolderNode();
            return *RootNode;
        };

    private:
        FFolderNode *RootNode;
        FFolderNode *PreviousNode;
        int32 FolderDepth;
        int32 PreviousDepth;
        TArray<FFolderNode*> VisitedNodes;
    };

    FFolderVisitor FolderList(FPlatformFileManager::Get().GetPlatformFile());
    auto RootNode = FolderList.CreateRootNode(ContentPath, TEXT("Content"));
    FolderList.PlatformFile.IterateDirectory(*ContentPath, FolderList);

    return *RootNode;
}

如何使用引擎遍历文件结构的方式正确构建链表？

Answer 1

从 FFolderVisitor::Visit 内部调用 IterateDirectory 似乎实际上导致了奇怪的遍历顺序。在创建一个单独的方法来处理根节点的初始化并从那里调用 IterateDirectory 之后，遍历以正确的 DFS 顺序进行。

Structuring/organizing 文件系统文件夹的链接列表

Structuring/organizing a linked list of filesystem folders

c++

directory

tree

graph-traversal

unreal-engine4