Как реализовать defragmantation подобный метод в файловой системе

Question

Я строю свой собственный виртуальный файловой системы в С.

Теперь я хочу, чтобы реализовать какой-то метод defragmantation, где он ищет пробелы и закрывает их.

Так что, если файл 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] относится к п -го блока и files это набор всех файлов (или более точно, блоки, которые они занимают), в том числе псевдо-файл для всех остальных блоков:

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 

Обратите внимание, что возможны различные оптимизации и необходимы для хорошего пользовательского опыта. Например, так как вам все равно нужно искать файлы по номеру блока, вы можете предотвратить переупорядочение уже дефрагментированной файловой системы, всегда выбирая файл, к которому относится текущий, проверенный (i-й) блок. Кроме того, вы можете, конечно, упростить свопинг, не копируя на самом деле содержимое, если файл, который вы меняете, пуст, и полностью пропускаете действие подкачки, если blocknum и i идентичны.

Как этот псевдокод переводит на C-код, полностью зависит от вашей реализации.