C 文件管理器的高效链表设计

Question

上下文。

我正在用 C 语言制作一个文件管理器。为了在 ncurses 中显示 CWD 中的文件列表，我选择将文件列表实现为以下结构的单链表：

typedef struct FileNode {
    char name[256]
    struct FileNode* next;
} FileNode;

我确信文件名绝不会超过 255 个字符加上空终止符。这是 ext2、ext3、ext4、BTRFS、XFS、ZFS 和 exFAT 的标准。 （我不熟悉 DOS 文件系统，但我只是针对 UNIX。）

我必须考虑将给定文件重命名为更长名称的情况，在这种情况下，我只会更改该文件节点的名称，而不会重建整个链接列表。但是，如果名称发生更改，则该结构体也可能会更改列表中的位置，因为 列表按 FileNode

 名称的字母顺序

排列。

注意。 稍后我可能会向

FileNode

结构添加成员，以确定用户在 ncurses 界面中选择列表中的哪些文件。

问题。

由于

FileNode

结构体为文件名保留了 256 个字节，对于具有大量文件且名称相对较短的目录，将会浪费大量内存。我的文件管理器是通用的，所以我可以想象发生这种情况的场景。

在这种情况下，高级程序员会做什么？ 在创建大型文件列表或同时重命名许多文件时，文件名的动态分配会导致显着增加的开销。 （这将是我的文件管理器的一个功能。）

我研究过的事情。

在考虑 FAM 一段时间后（请参阅下面的代码片段），我注意到文件重命名的事情变得很复杂，除非我选择在重命名文件时“释放节点并创建一个新节点”。这是一个好的选择吗？成本高昂的部分是首先检查所有文件名的长度，以便生成分别适合这些长度的操作系统结构列表。重复我之前的问题，高级程序员会做什么？

typedef FileNode {
    struct FileNode* next;
    char name[]; // this member should be the last
} FileNode;

Answer 1

从算法角度看的一些想法：

对于始终排序的列表，您可以使用

AVL or Red-Black Trees

等数据结构在根据您的选择创建、删除或重命名文件时维护 FileList 的排序顺序。

要提高大型目录的性能：

受 Linux 内核的启发，使用哈希表进行文件名查找

dcache

将文件名（或文件 ID）映射到红黑树中的

FileNode

指针，以进行 O(1) 查找。

要处理重命名案例，我会：

使用哈希表检索 FileNode 指针。

1. 通过FileNode->name释放占用的内存。从红黑树中删除节点并重新平衡。
2. 重新分配所需的必要内存。
3. 将newName复制到FileNode->name。将节点插入红黑树并再次重新平衡。

进一步改进范围：

RB 树/AVL 树有一个称为宽松平衡的概念。您可以在

本文
• 中探索权衡。 对于更高程度的并发重新平衡：
彩色二叉搜索树
• 和HyperRed-Black树