UnitBlockSorter.pas

unit UnitBlockSorter;

interface
uses
  SysUtils, Classes,
  Common, UnitThreadManager, UnitBufferedFileStream;

type
  TBlockSorterThread = class(TProtoThread)
  private
  type
    TIndexArray = array[0..0] of integer; 
    PIndexArray = ^TIndexArray;

  var
    FData: PAnsiChar;
    FDataSize: integer;
    FIndexes: PIndexArray; // ìàññèâ ñìåùåíèé ñòðîê îò íà÷àëà áóôåðà. õðàíèì íå â âèäå óêàçàòåëåé, à â âèäå ñìåùåíèé, ò.ê. ïðè íåîáõîäèìîñòè 
                           // ñêîìïèëèðîâàòü ïîä x64 ìàññèâ ñ óêàçàòåëÿìè áóäåò çàíèìàòü â äâà ðàçà áîëüøå ïàìÿòè, êîòîðàÿ ó íàñ îãðàíè÷åíà

    procedure QuickSort(L, R: Integer);
  public
    constructor Create(const Data: PAnsiChar; const DataSize: integer; const BlockIndex: integer);

    procedure Execute; override;
  end;

implementation

procedure TBlockSorterThread.QuickSort(L, R: Integer);
var
  I, J, P, Save: Integer;
begin
  repeat
    I := L;
    J := R;
    P := (L + R) shr 1;
    repeat
      while CompareStrings(FData + FIndexes[I], FData + FIndexes[P]) < 0 do
        Inc(I);
      while CompareStrings(FData + FIndexes[J], FData + FIndexes[P]) > 0 do
        Dec(J);
      if I <= J then
      begin
        Save := FIndexes[I];
        FIndexes[I] := FIndexes[J];
        FIndexes[J] := Save;
        if P = I then
          P := J
        else
        if P = J then
          P := I;
        Inc(I);
        Dec(J);
      end;
    until I > J;
    if L < J then QuickSort(L, J);
    L := I;
  until I >= R;
end;

{ TStreamSorter }

constructor TBlockSorterThread.Create(const Data: PAnsiChar; const DataSize: integer; const BlockIndex: integer);
begin
  inherited Create(BlockIndex);

  FData := Data;
  FDataSize := DataSize;
end;

procedure TBlockSorterThread.Execute;
var
  LineStart, Ptr, DataEnd: PAnsiChar;
  LineCount: integer;
  IndexesSize: integer; // òåêóùèé ðàçìåð ìàññèâà ñìåùåíèé ñòðîê
  FS: TStream;
  i: integer;
  IndexBlockSize: integer;
  LastCRLFAdded: boolean;
begin
  IndexesSize := 0;
  IndexBlockSize := MergeBufferSize div (MAX_LINE_LENGTH div 2) * SizeOf(Integer);  // ïðèðàùåíèå ðàçìåðà ìàññèâà èíäåêñîâ âûáåðåì êàê ñðåäíåå êîëè÷åñòâî ñòðîê, ïîìåùàþùååñÿ â áóôåð
  LastCRLFAdded := false;

  FIndexes := nil;
  try
    try
      // ïîäãîòîâèì ìàññèâ FIndexes ñî ñìåùåíèÿìè êàæäîé ñòðîêè îò íà÷àëà áóôåðà
      // Ïîñêîëüêó êîëè÷åñòâî ñòðîê çàðàíåå íå èçâåñòíî, òî ïàìÿòü ïîä ìàññèâ âûäåëÿåì ïîðöèÿìè ïî INDEX_BLOCK_SIZE áàéò
      DataEnd := FData + FDataSize;
      Ptr := FData;
      LineCount := 0;
      while Ptr < DataEnd do
      begin
        LineStart := Ptr;
        while (Ptr < DataEnd) and (PWord(Ptr)^ <> CRLF) do
          Inc(Ptr);

        if Ptr = DataEnd then
        begin
          // äîøëè äî êîíöà áóôåðà è òàì íå áûëî CRLF - äîáàâèì åãî è çàïîìíèì ýòîò ôàêò, ÷òîáû ïîòîì óäàëèòü
          // Äîáàâëÿòü ìîæíî, ò.ê. â UnitSplitter ìû âûäåëÿëè ïîä áóôôåð äâà ëèøíèõ áàéòà
          PWord(DataEnd)^ := CRLF;
          Inc(DataEnd, 2);
          LastCRLFAdded := true;
        end;
        // ñäâèíåì óêàçàòåëü íà äâà ñèìâîëà CR è ÄÀ
        Inc(Ptr, 2);

        // óâåëè÷èì ðàçìåð ìàññèâîâ èíäåêñîâ è äëèí ñòðîê åñëè íàäî
        if LineCount * SizeOf(integer) >= IndexesSize then
        begin
          Inc(IndexesSize, IndexBlockSize);
          ReallocMem(FIndexes, IndexesSize);
        end;
        FIndexes[LineCount] := LineStart - FData;
        Inc(LineCount);
      end;

      // Ñîðòèðóåì ñòðîêè îáû÷íûì QuickSort-îì. Ðåàëüíî ñîðòèðóþòñÿ ñìåùåíèÿ â ìàññèâå
      QuickSort(0, LineCount - 1);

      FS := nil;  // ÷òîá êîìïèëÿòîð íå ðóãàëñÿ íà íåèíèöèàëèçèðîâàííóþ ïåðåìåííóþ
      try
        FS := TWriteCachedFileStream.Create(ResultFileName, FDataSize, 0, false);
      except
        writeln('Cannot create file ', ResultFileName);

        Halt;
      end;

      // ñîõðàíÿåì îòñîðòèðîâàííûå ñòðîêè â ôàéë
      try
        for i := 0 to LineCount - 1 do
        begin
          Ptr := FData + FIndexes[i];
          LineStart := Ptr;
          while (Ptr < DataEnd) and (PWord(Ptr)^ <> CRLF) do
            Inc(Ptr);
          // Åñëè ýòî áûëà ïîñëåäíÿÿ ñòðîêà è áûë äîáàâëåí CRLF - åãî ïèñàòü íå íàäî
          if (i < LineCount - 1) or not LastCRLFAdded then
            Inc(Ptr, 2);  // CRLF

          FS.WriteBuffer(LineStart^, Ptr - LineStart);
        end;
      finally
        FS.Free;
      end;
    finally
      FreeMem(FData);
    end;
  finally
    FreeMem(FIndexes);
  end;

  inherited;
end;

end.