Sun
15
Feb 2009

SceNtriC na swoim blogu często pisze długie notki, w których opisuje swoje algorytmy, więc ja nie będę gorszy i dzisiaj też tak zrobię :) Problem, który rozwiązywałem niedawno, wyglądał tak: Mamy duży plik - tak duży, że nie chcemy wczytywać go całego do pamięci. W pliku są bloki z danymi, a między nimi dziury (na rysunku zakreskowane). Zadaniem jest tak "zsunąć" te dane, żeby dziur nie było.

Dziury można opisać tablicą takich struktur, z których każda pamięta numer pierwszego bajtu i liczbę bajtów:

struct BLOCK
{
  unsigned Start, Size;
  
  BLOCK() { }
  BLOCK(unsigned4 Start, unsigned4 Size) : Start(Start), Size(Size) { }
  bool operator < (const BLOCK &b) const { return Start < b.Start; }
};

std::vector<BLOCK> BlockToDelete;

Te puste bloki warto najpierw posortować rosnąco według ich początku. Oczywiście zakładamy, że nie nachodzą na siebie.

std::sort(BlocksToDelete.begin(), BlocksToDelete.end());

Warto je po tym przetworzyć w taki sposób, żeby sąsiadujące ze sobą puste bloki (jak dwa pierwsze na rysunku) połączyć w jeden.

void MergeBlocksToDelete()
{
  if (BlocksToDelete.size() < 2) return;
  unsigned i = BlocksToDelete.size()-1;
  while (i > 0)
  {
    // Próbuje połączyć blok z poprzednim.
    if (BlocksToDelete[i].Start == BlocksToDelete[i-1].Start + BlocksToDelete[i-1].Size)
    {
      BlocksToDelete[i-1].Size += BlocksToDelete[i].Size;
      BlocksToDelete.erase(BlocksToDelete.begin() + i);
    }
    i--;
  }
}

Czas na właściwą defragmentację pliku. Nie chcemy wczytywać całego pliku do pamięci, więc będziemy dane przepisywać przez pewien bufor, tak jak pokazują strzałki na rysunku. Całe przepisywanie odbywa się w miejscu, bez użycia dodatkowego miejsca na dysku czy dodatkowego pliku. Przepisywanie zaczynamy od miejsca, gdzie kończy się pierwszy pusty blok. Pamiętamy zawsze aktualne miejsca z którego przepisujemy i aktualne miejsce, do którego przepisujemy. Jeden przebieg pętli głównej przepisuje dane pomiędzy dwoma pustymi blokami lub za ostatnim takim blokiem.

int ApplyBlocksToDeleteToFileContents()
{
  if (BlocksToDelete.empty()) return 0;

  const unsigned BUF_SIZE = 1024 * 1024; // 1 MB
  std::vector<char> Buf(BUF_SIZE);

  unsigned DstOffset = BlocksToDelete[0].Start;
  for (unsigned Block_i = 0; Block_i < BlocksToDelete.size(); Block_i++)
  {
    unsigned SrcOffset = BlocksToDelete[Block_i].Start + BlocksToDelete[Block_i].Size;
    unsigned SizeToMove;
    if (Block_i == BlocksToDelete.size()-1)
      SizeToMove = FileSize - SrcOffset;
    else
      SizeToMove = BlocksToDelete[Block_i+1].Start - SrcOffset;

    MoveFileData(
      DstOffset, SrcOffset, SizeToMove, &Buf[0], BUF_SIZE);
    DstOffset += SizeToMove;
  }

  for (unsigned Block_i = 0; Block_i < BlocksToDelete.size(); Block_i++)
    FileSize -= BlocksToDelete[Block_i].Size;
}

Funkcja pomocnicza przepisuje dane w pliku z jednego miejsca w drugie przez podany bufor. Jej dokładna postać zależy od tego, jakich funkcji używamy do obsługi plików.

int MoveFileData(
  unsigned DstOffset, unsigned SrcOffset, unsigned Size,
  char *Buf, unsigned BufSize)
{
  unsigned CurrSize;
  DWORD CurrTime;
  while (Size > 0)
  {
    CurrSize = Size;
    if (CurrSize > BufSize) CurrSize = BufSize;
    
    File->SetPos(SrcOffset);
    File->Read(Buf, CurrSize);

    File->SetPos(DstOffset);
    File->Write(Buf, CurrSize);

    DstOffset += CurrSize;
    SrcOffset += CurrSize;
    Size -= CurrSize;
  }

  return 0;
}

Zostaje jeszcze przyciąć plik do nowej długości. Może nie wszyscy wiedzą, ale w bibliotekach do obsługi plików zawsze istnieje taka funkcja, która przycina plik do miejsca w którym jest aktualnie kursor, a tym samym ustawia nowy rozmiar pliku i porzuca dane, które zostały dalej. Np. w WinAPI to będzie tak:

SetFilePointer(FileHandle, (LONG)FileSize, NULL, FILE_BEGIN);
SetEndOfFile(FileHandle);

Ponieważ dane w pliku mają jakieś znaczenie i pewnie gdzieś zapamiętane są offsety do nich, trzeba też uaktualnić te offsety, żeby pokazywały na nowe pozycje danych.

void UpdateDataOffsets()
{
  for (unsigned Record_i = 0; Record_i < RecordCount; Record_i++)
  {
    uint OffsetDiff = 0;
    for (uint i = 0; i < BlockCount; i++)
    {
      if (BlocksToDelete[i].Start < Records[Record_i].ContentOffset)
        OffsetDiff += BlocksToDelete[i].Size;
      else
        break;
    }
    Records[Record_i].ContentOffset -= OffsetDiff;
  }
}

Comments | #algorithms Share

Comments