c - 如何在文件系统中实现类似碎片整理的方法

Question

我用 C 语言构建了自己的虚拟文件系统。

现在我想实现某种碎片整理方法，它会查找间隙并关闭它们。

因此，如果文件 1 的大小为 10，位置为 X，文件 2 的大小为 20，位置为 Z，我希望它移动到位置 Y。

我现在的想法是获取文件 2 的大小，从文件 1 的大小中减去它，然后使用结果将文件 2 向左移动到与结果一样高的位置。

我有一个伪代码，因为我无法提出可行的解决方案:

for (int i = 0; i < files; i++) 
     //look for inconsistencies/gaps. 

if (found gaps)
    file 2 - file 1 = x;
    shiftfiletotheleft x bytes;

感谢提前提供的想法和答案。

Answer 1

天真的碎片相当简单，假设 disk[n] 引用第 n 个 block ，并且 files 是所有文件的集合(或更准确地说，它们占用的 block )，包括所有剩余 block 的伪文件:

i = 0
for file in files:
  for blocknum in file:
    // Swap content
    buf = disk[i]
    disk[i] = disk[blocknum]
    disk[blocknum] = buf

    // Swap metadata
    swap_block(file, blocknum, i)
    file += i
    changed_file = find_file_by_block(blocknum)
    swap_block(changed_file, i, blocknum)

    i += 1

请注意，可以进行多种优化，并且对于良好的用户体验来说这是必要的。例如，由于您无论如何都需要按 block 号查找文件，因此您可以通过始终选择当前检查的(第 i 个) block 所属的文件来防止已进行碎片整理的文件系统被重新排序到。此外，如果要交换的文件为空，您当然可以通过不实际复制内容来简化交换，并且如果 blocknum 和 i 则完全跳过交换操作是相同的。

伪代码如何转换为 C 代码完全取决于您的实现。