1 |
torben |
2671 |
// Upgraded to Delphi 2009: Sebastian Zierer
|
2 |
|
|
|
3 |
|
|
(* ***** BEGIN LICENSE BLOCK *****
|
4 |
|
|
* Version: MPL 1.1
|
5 |
|
|
*
|
6 |
|
|
* The contents of this file are subject to the Mozilla Public License Version
|
7 |
|
|
* 1.1 (the "License"); you may not use this file except in compliance with
|
8 |
|
|
* the License. You may obtain a copy of the License at
|
9 |
|
|
* http://www.mozilla.org/MPL/
|
10 |
|
|
*
|
11 |
|
|
* Software distributed under the License is distributed on an "AS IS" basis,
|
12 |
|
|
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
|
13 |
|
|
* for the specific language governing rights and limitations under the
|
14 |
|
|
* License.
|
15 |
|
|
*
|
16 |
|
|
* The Original Code is TurboPower SysTools
|
17 |
|
|
*
|
18 |
|
|
* The Initial Developer of the Original Code is
|
19 |
|
|
* TurboPower Software
|
20 |
|
|
*
|
21 |
|
|
* Portions created by the Initial Developer are Copyright (C) 1996-2002
|
22 |
|
|
* the Initial Developer. All Rights Reserved.
|
23 |
|
|
*
|
24 |
|
|
* Contributor(s):
|
25 |
|
|
*
|
26 |
|
|
* ***** END LICENSE BLOCK ***** *)
|
27 |
|
|
|
28 |
|
|
{*********************************************************}
|
29 |
|
|
{* SysTools: StSort.pas 4.04 *}
|
30 |
|
|
{*********************************************************}
|
31 |
|
|
{* SysTools: General purpose sorting class using *}
|
32 |
|
|
{* merge sort algorithm *}
|
33 |
|
|
{*********************************************************}
|
34 |
|
|
|
35 |
|
|
{$I StDefine.inc}
|
36 |
|
|
|
37 |
|
|
{Notes:
|
38 |
|
|
The sequence to sort data is this:
|
39 |
|
|
|
40 |
|
|
Sorter := TStSorter.Create(MaxHeap, RecLen);
|
41 |
|
|
Sorter.Compare := ACompareFunction;
|
42 |
|
|
repeat
|
43 |
|
|
... obtain ADataRecord from somewhere ...
|
44 |
|
|
Sorter.Put(ADataRecord);
|
45 |
|
|
until NoMoreData;
|
46 |
|
|
while Sorter.Get(ADataRecord) do
|
47 |
|
|
... do something with ADataRecord ...
|
48 |
|
|
Sorter.Free;
|
49 |
|
|
|
50 |
|
|
While Put is called, the sorter buffers as many records as it can fit in
|
51 |
|
|
MaxHeap. When that space is filled, it sorts the buffer and stores that
|
52 |
|
|
buffer to a temporary merge file. When Get is called, the sorter sorts the
|
53 |
|
|
last remaining buffer and starts either returning the records from the
|
54 |
|
|
buffer (if all records fit into memory) or merging the files and returning
|
55 |
|
|
the records from there.
|
56 |
|
|
|
57 |
|
|
The Compare function can be used as a place to display status and to abort
|
58 |
|
|
the sort. It is not possible to accurately predict the total number of
|
59 |
|
|
times Compare will be called, but it is called very frequently throughout
|
60 |
|
|
the sort. To abort a sort from the Compare function, just raise an
|
61 |
|
|
exception there.
|
62 |
|
|
|
63 |
|
|
The Reset method can be called to sort another set of data of the same
|
64 |
|
|
record length. Once Get has been called, Put cannot be called again unless
|
65 |
|
|
Reset is called first.
|
66 |
|
|
|
67 |
|
|
There is no default Compare function. One must be assigned after creating
|
68 |
|
|
a TStSorter and before calling Put. Otherwise an exception is raised the
|
69 |
|
|
first time a Compare function is needed.
|
70 |
|
|
|
71 |
|
|
If Create cannot allocate MaxHeap bytes for a work buffer, it
|
72 |
|
|
repeatedly divides MaxHeap by two until it can successfully allocate that
|
73 |
|
|
much space. After finding a block it can allocate, it does not attempt to
|
74 |
|
|
allocate larger blocks that might still fit.
|
75 |
|
|
|
76 |
|
|
Unlike MSORTP, STSORT always swaps full records. It does not use pointer
|
77 |
|
|
swapping for large records. If this is desirable, the application should
|
78 |
|
|
pass pointers to previously allocated records into the TStSorter class.
|
79 |
|
|
|
80 |
|
|
The OptimumHeapToUse, MinimumHeapToUse, and MergeInfo functions can be used
|
81 |
|
|
to optimize the buffer size before starting a sort.
|
82 |
|
|
|
83 |
|
|
By default, temporary merge files are saved in the current directory with
|
84 |
|
|
names of the form SORnnnnn.TMP, where nnnnn is a sequential file number.
|
85 |
|
|
You can supply a different merge name function via the MergeName property
|
86 |
|
|
to put the files in a different location or use a different form for the
|
87 |
|
|
names.
|
88 |
|
|
|
89 |
|
|
The sorter is thread-aware and uses critical sections to protect the Put,
|
90 |
|
|
Get, and Reset methods. Be sure that one thread does not call Put after
|
91 |
|
|
another thread has already called Get.
|
92 |
|
|
}
|
93 |
|
|
|
94 |
|
|
unit StSort;
|
95 |
|
|
|
96 |
|
|
interface
|
97 |
|
|
|
98 |
|
|
uses
|
99 |
|
|
Windows,
|
100 |
|
|
SysUtils, STConst, STBase;
|
101 |
|
|
|
102 |
|
|
const
|
103 |
|
|
{.Z+}
|
104 |
|
|
MinRecsPerRun = 4; {Minimum number of records in run buffer}
|
105 |
|
|
MergeOrder = 5; {Input files used at a time during merge, >=2, <=10}
|
106 |
|
|
MedianThreshold = 16; {Threshold for using median-of-three quicksort}
|
107 |
|
|
{.Z-}
|
108 |
|
|
|
109 |
|
|
type
|
110 |
|
|
TMergeNameFunc = function (MergeNum : Integer) : string;
|
111 |
|
|
|
112 |
|
|
TMergeInfo = record {Record returned by MergeInfo}
|
113 |
|
|
SortStatus : Integer; {Predicted status of sort, assuming disk ok}
|
114 |
|
|
MergeFiles : Integer; {Total number of merge files created}
|
115 |
|
|
MergeHandles : Integer; {Maximum file handles used}
|
116 |
|
|
MergePhases : Integer; {Number of merge phases}
|
117 |
|
|
MaxDiskSpace : LongInt; {Maximum peak disk space used}
|
118 |
|
|
HeapUsed : LongInt; {Heap space actually used}
|
119 |
|
|
end;
|
120 |
|
|
|
121 |
|
|
{.Z+}
|
122 |
|
|
TMergeIntArray = array[1..MergeOrder] of Integer;
|
123 |
|
|
TMergeLongArray = array[1..MergeOrder] of LongInt;
|
124 |
|
|
TMergePtrArray = array[1..MergeOrder] of Pointer;
|
125 |
|
|
{.Z-}
|
126 |
|
|
|
127 |
|
|
TStSorter = class(TObject)
|
128 |
|
|
{.Z+}
|
129 |
|
|
protected
|
130 |
|
|
{property instance variables}
|
131 |
|
|
FCount : LongInt; {Number of records put to sort}
|
132 |
|
|
FRecLen : Cardinal; {Size of each record}
|
133 |
|
|
FCompare : TUntypedCompareFunc; {Compare function}
|
134 |
|
|
FMergeName : TMergeNameFunc; {Merge file naming function}
|
135 |
|
|
|
136 |
|
|
{private instance variables}
|
137 |
|
|
sorRunCapacity : LongInt; {Capacity (in records) of run buffer}
|
138 |
|
|
sorRunCount : LongInt; {Current number of records in run buffer}
|
139 |
|
|
sorGetIndex : LongInt; {Last run element passed back to user}
|
140 |
|
|
sorPivotPtr : Pointer; {Pointer to pivot record}
|
141 |
|
|
sorSwapPtr : Pointer; {Pointer to swap record}
|
142 |
|
|
sorState : Integer; {0 = empty, 1 = adding, 2 = getting}
|
143 |
|
|
sorMergeFileCount : Integer; {Number of merge files created}
|
144 |
|
|
sorMergeFileMerged : Integer; {Index of last merge file merged}
|
145 |
|
|
sorMergeOpenCount : Integer; {Count of open merge files}
|
146 |
|
|
sorMergeBufSize : LongInt; {Usable bytes in merge buffer}
|
147 |
|
|
sorMergeFileNumber : TMergeIntArray; {File number of each open merge file}
|
148 |
|
|
sorMergeFiles : TMergeIntArray; {File handles for merge files}
|
149 |
|
|
sorMergeBytesLoaded: TMergeLongArray;{Count of bytes in each merge buffer}
|
150 |
|
|
sorMergeBytesUsed : TMergeLongArray; {Bytes used in each merge buffer}
|
151 |
|
|
sorMergeBases : TMergePtrArray; {Base index for each merge buffer}
|
152 |
|
|
sorMergePtrs : TMergePtrArray; {Current head elements in each merge buffer}
|
153 |
|
|
sorOutFile : Integer; {Output file handle}
|
154 |
|
|
sorOutPtr : Pointer; {Pointer for output buffer}
|
155 |
|
|
sorOutBytesUsed : LongInt; {Number of bytes in output buffer}
|
156 |
|
|
{$IFDEF ThreadSafe}
|
157 |
|
|
sorThreadSafe : TRTLCriticalSection;{Windows critical section record}
|
158 |
|
|
{$ENDIF}
|
159 |
|
|
sorBuffer : Pointer; {Pointer to global buffer}
|
160 |
|
|
|
161 |
|
|
{protected undocumented methods}
|
162 |
|
|
procedure sorAllocBuffer(MaxHeap : LongInt);
|
163 |
|
|
procedure sorCreateNewMergeFile(var Handle : Integer);
|
164 |
|
|
procedure sorDeleteMergeFiles;
|
165 |
|
|
function sorElementPtr(Index : LongInt) : Pointer;
|
166 |
|
|
procedure sorFlushOutBuffer;
|
167 |
|
|
procedure sorFreeBuffer;
|
168 |
|
|
procedure sorGetMergeElementPtr(M : Integer);
|
169 |
|
|
function sorGetNextElementIndex : Integer;
|
170 |
|
|
procedure sorMergeFileGroup;
|
171 |
|
|
procedure sorMoveElement(Src, Dest : Pointer);
|
172 |
|
|
procedure sorOpenMergeFiles;
|
173 |
|
|
procedure sorPrimaryMerge;
|
174 |
|
|
procedure sorRunSort(L, R : LongInt);
|
175 |
|
|
procedure sorStoreElement(Src : Pointer);
|
176 |
|
|
procedure sorStoreNewMergeFile;
|
177 |
|
|
procedure sorSwapElements(L, R : LongInt);
|
178 |
|
|
procedure sorSetCompare(Comp : TUntypedCompareFunc);
|
179 |
|
|
|
180 |
|
|
{protected documented methods}
|
181 |
|
|
procedure EnterCS;
|
182 |
|
|
{-Enter critical section for this instance}
|
183 |
|
|
procedure LeaveCS;
|
184 |
|
|
{-Leave critical section}
|
185 |
|
|
{.Z-}
|
186 |
|
|
|
187 |
|
|
public
|
188 |
|
|
constructor Create(MaxHeap : LongInt; RecLen : Cardinal); virtual;
|
189 |
|
|
{-Initialize a sorter}
|
190 |
|
|
destructor Destroy; override;
|
191 |
|
|
{-Destroy a sorter}
|
192 |
|
|
|
193 |
|
|
procedure Put(const X);
|
194 |
|
|
{-Add an element to the sort system}
|
195 |
|
|
function Get(var X) : Boolean;
|
196 |
|
|
{-Return next sorted element from the sort system}
|
197 |
|
|
|
198 |
|
|
procedure Reset;
|
199 |
|
|
{-Reset sorter before starting another sort}
|
200 |
|
|
|
201 |
|
|
property Count : LongInt
|
202 |
|
|
{-Return the number of elements in the sorter}
|
203 |
|
|
read FCount;
|
204 |
|
|
|
205 |
|
|
property Compare : TUntypedCompareFunc
|
206 |
|
|
{-Set or read the element comparison function}
|
207 |
|
|
read FCompare
|
208 |
|
|
write sorSetCompare;
|
209 |
|
|
|
210 |
|
|
property MergeName : TMergeNameFunc
|
211 |
|
|
{-Set or read the merge filename function}
|
212 |
|
|
read FMergeName
|
213 |
|
|
write FMergeName;
|
214 |
|
|
|
215 |
|
|
property RecLen : Cardinal
|
216 |
|
|
{-Return the size of each record}
|
217 |
|
|
read FRecLen;
|
218 |
|
|
end;
|
219 |
|
|
|
220 |
|
|
function OptimumHeapToUse(RecLen : Cardinal; NumRecs : LongInt) : LongInt;
|
221 |
|
|
{-Returns the optimum amount of heap space to sort NumRecs records
|
222 |
|
|
of RecLen bytes each. Less heap space causes merging; more heap
|
223 |
|
|
space is partially unused.}
|
224 |
|
|
|
225 |
|
|
function MinimumHeapToUse(RecLen : Cardinal) : LongInt;
|
226 |
|
|
{-Returns the absolute minimum heap that allows MergeSort to succeed}
|
227 |
|
|
|
228 |
|
|
function MergeInfo(MaxHeap : LongInt; RecLen : Cardinal;
|
229 |
|
|
NumRecs : LongInt) : TMergeInfo;
|
230 |
|
|
{-Predicts status and resource usage of a merge sort}
|
231 |
|
|
|
232 |
|
|
function DefaultMergeName(MergeNum : Integer) : string;
|
233 |
|
|
{-Default function used for returning merge file names}
|
234 |
|
|
|
235 |
|
|
procedure ArraySort(var A; RecLen, NumRecs : Cardinal;
|
236 |
|
|
Compare : TUntypedCompareFunc);
|
237 |
|
|
{-Sort a normal Delphi array (A) in place}
|
238 |
|
|
|
239 |
|
|
{======================================================================}
|
240 |
|
|
|
241 |
|
|
implementation
|
242 |
|
|
|
243 |
|
|
const
|
244 |
|
|
ecOutOfMemory = 8;
|
245 |
|
|
|
246 |
|
|
procedure RaiseError(Code : longint);
|
247 |
|
|
var
|
248 |
|
|
E : ESTSortError;
|
249 |
|
|
begin
|
250 |
|
|
if Code = ecOutOfMemory then
|
251 |
|
|
OutOfMemoryError
|
252 |
|
|
else begin
|
253 |
|
|
E := ESTSortError.CreateResTP(Code, 0);
|
254 |
|
|
E.ErrorCode := Code;
|
255 |
|
|
raise E;
|
256 |
|
|
end;
|
257 |
|
|
end;
|
258 |
|
|
|
259 |
|
|
function DefaultMergeName(MergeNum : Integer) : string;
|
260 |
|
|
begin
|
261 |
|
|
Result := 'SOR'+IntToStr(MergeNum)+'.TMP';
|
262 |
|
|
end;
|
263 |
|
|
|
264 |
|
|
function MergeInfo(MaxHeap : LongInt; RecLen : Cardinal;
|
265 |
|
|
NumRecs : LongInt) : TMergeInfo;
|
266 |
|
|
type
|
267 |
|
|
MergeFileSizeArray = array[1..(StMaxBlockSize div SizeOf(LongInt))] of LongInt;
|
268 |
|
|
var
|
269 |
|
|
MFileMerged, MOpenCount, MFileCount : Integer;
|
270 |
|
|
SizeBufSize, DiskSpace, OutputSpace, PeakDiskSpace : LongInt;
|
271 |
|
|
AllocRecs, RunCapacity, RecordsLeft, RecordsInFile : LongInt;
|
272 |
|
|
MFileSizeP : ^MergeFileSizeArray;
|
273 |
|
|
begin
|
274 |
|
|
{Set defaults for the result}
|
275 |
|
|
FillChar(Result, SizeOf(TMergeInfo), 0);
|
276 |
|
|
|
277 |
|
|
{Validate input parameters}
|
278 |
|
|
if (RecLen = 0) or (MaxHeap <= 0) or (NumRecs <= 0) then begin
|
279 |
|
|
Result.SortStatus := stscBadSize;
|
280 |
|
|
Exit;
|
281 |
|
|
end;
|
282 |
|
|
|
283 |
|
|
AllocRecs := MaxHeap div LongInt(RecLen);
|
284 |
|
|
if AllocRecs < MergeOrder+1 then begin
|
285 |
|
|
Result.SortStatus := stscBadSize;
|
286 |
|
|
Exit;
|
287 |
|
|
end;
|
288 |
|
|
|
289 |
|
|
RunCapacity := AllocRecs-2;
|
290 |
|
|
if RunCapacity < MinRecsPerRun then begin
|
291 |
|
|
Result.SortStatus := stscBadSize;
|
292 |
|
|
Exit;
|
293 |
|
|
end;
|
294 |
|
|
|
295 |
|
|
{Compute amount of memory used}
|
296 |
|
|
Result.HeapUsed := AllocRecs*LongInt(RecLen);
|
297 |
|
|
|
298 |
|
|
if RunCapacity >= NumRecs then
|
299 |
|
|
{All the records fit into memory}
|
300 |
|
|
Exit;
|
301 |
|
|
|
302 |
|
|
{Compute initial number of merge files and disk space}
|
303 |
|
|
MFileCount := NumRecs div (AllocRecs-2);
|
304 |
|
|
if NumRecs mod (AllocRecs-2) <> 0 then
|
305 |
|
|
inc(MFileCount);
|
306 |
|
|
{if MFileCount > MaxInt then begin }
|
307 |
|
|
{ Result.SortStatus := stscTooManyFiles;}
|
308 |
|
|
{ Exit; }
|
309 |
|
|
{end; }
|
310 |
|
|
DiskSpace := NumRecs*LongInt(RecLen);
|
311 |
|
|
|
312 |
|
|
{At least one merge phase required}
|
313 |
|
|
Result.MergePhases := 1;
|
314 |
|
|
|
315 |
|
|
if MFileCount <= MergeOrder then begin
|
316 |
|
|
{Only one merge phase, direct to user}
|
317 |
|
|
Result.MergeFiles := MFileCount;
|
318 |
|
|
Result.MergeHandles := MFileCount;
|
319 |
|
|
Result.MaxDiskSpace := DiskSpace;
|
320 |
|
|
Exit;
|
321 |
|
|
end;
|
322 |
|
|
|
323 |
|
|
{Compute total number of merge files and merge phases}
|
324 |
|
|
MFileMerged := 0;
|
325 |
|
|
while MFileCount-MFileMerged > MergeOrder do begin
|
326 |
|
|
inc(Result.MergePhases);
|
327 |
|
|
MOpenCount := 0;
|
328 |
|
|
while (MOpenCount < MergeOrder) and (MFileMerged < MFileCount) do begin
|
329 |
|
|
inc(MOpenCount);
|
330 |
|
|
inc(MFileMerged);
|
331 |
|
|
end;
|
332 |
|
|
inc(MFileCount);
|
333 |
|
|
end;
|
334 |
|
|
|
335 |
|
|
{Store the information we already know}
|
336 |
|
|
Result.MergeFiles := MFileCount;
|
337 |
|
|
Result.MergeHandles := MergeOrder+1; {MergeOrder input files, 1 output file}
|
338 |
|
|
|
339 |
|
|
{Determine whether the disk space analysis can proceed}
|
340 |
|
|
Result.MaxDiskSpace := -1;
|
341 |
|
|
if MFileCount > (StMaxBlockSize div SizeOf(LongInt)) then
|
342 |
|
|
Exit;
|
343 |
|
|
SizeBufSize := MFileCount*SizeOf(LongInt);
|
344 |
|
|
try
|
345 |
|
|
GetMem(MFileSizeP, SizeBufSize);
|
346 |
|
|
except
|
347 |
|
|
Exit;
|
348 |
|
|
end;
|
349 |
|
|
|
350 |
|
|
{Compute size of initial merge files}
|
351 |
|
|
RecordsLeft := NumRecs;
|
352 |
|
|
MFileCount := 0;
|
353 |
|
|
while RecordsLeft > 0 do begin
|
354 |
|
|
inc(MFileCount);
|
355 |
|
|
if RecordsLeft >= RunCapacity then
|
356 |
|
|
RecordsInFile := RunCapacity
|
357 |
|
|
else
|
358 |
|
|
RecordsInFile := RecordsLeft;
|
359 |
|
|
MFileSizeP^[MFileCount] := RecordsInFile*LongInt(RecLen);
|
360 |
|
|
dec(RecordsLeft, RecordsInFile);
|
361 |
|
|
end;
|
362 |
|
|
|
363 |
|
|
{Carry sizes forward to get disk space used}
|
364 |
|
|
PeakDiskSpace := DiskSpace;
|
365 |
|
|
MFileMerged := 0;
|
366 |
|
|
while MFileCount-MFileMerged > MergeOrder do begin
|
367 |
|
|
MOpenCount := 0;
|
368 |
|
|
OutputSpace := 0;
|
369 |
|
|
while (MOpenCount < MergeOrder) and (MFileMerged < MFileCount) do begin
|
370 |
|
|
inc(MOpenCount);
|
371 |
|
|
inc(MFileMerged);
|
372 |
|
|
inc(OutputSpace, MFileSizeP^[MFileMerged]);
|
373 |
|
|
end;
|
374 |
|
|
inc(MFileCount);
|
375 |
|
|
{Save size of output file}
|
376 |
|
|
MFileSizeP^[MFileCount] := OutputSpace;
|
377 |
|
|
{Output file and input files coexist temporarily}
|
378 |
|
|
inc(DiskSpace, OutputSpace);
|
379 |
|
|
{Store new peak disk space}
|
380 |
|
|
if DiskSpace > PeakDiskSpace then
|
381 |
|
|
PeakDiskSpace := DiskSpace;
|
382 |
|
|
{Account for deleting input files}
|
383 |
|
|
dec(DiskSpace, OutputSpace);
|
384 |
|
|
end;
|
385 |
|
|
Result.MaxDiskSpace := PeakDiskSpace;
|
386 |
|
|
|
387 |
|
|
FreeMem(MFileSizeP, SizeBufSize);
|
388 |
|
|
end;
|
389 |
|
|
|
390 |
|
|
function MinimumHeapToUse(RecLen : Cardinal) : LongInt;
|
391 |
|
|
var
|
392 |
|
|
HeapToUse : LongInt;
|
393 |
|
|
begin
|
394 |
|
|
HeapToUse := (MergeOrder+1)*RecLen;
|
395 |
|
|
Result := (MinRecsPerRun+2)*RecLen;
|
396 |
|
|
if Result < HeapToUse then
|
397 |
|
|
Result := HeapToUse;
|
398 |
|
|
end;
|
399 |
|
|
|
400 |
|
|
function OptimumHeapToUse(RecLen : Cardinal; NumRecs : LongInt) : LongInt;
|
401 |
|
|
begin
|
402 |
|
|
if (NumRecs < MergeOrder+1) then
|
403 |
|
|
NumRecs := MergeOrder+1;
|
404 |
|
|
Result := LongInt(RecLen)*(NumRecs+2);
|
405 |
|
|
end;
|
406 |
|
|
|
407 |
|
|
{----------------------------------------------------------------------}
|
408 |
|
|
|
409 |
|
|
constructor TStSorter.Create(MaxHeap : LongInt; RecLen : Cardinal);
|
410 |
|
|
begin
|
411 |
|
|
if (RecLen = 0) or (MaxHeap <= 0) then
|
412 |
|
|
RaiseError(stscBadSize);
|
413 |
|
|
|
414 |
|
|
FMergeName := DefaultMergeName;
|
415 |
|
|
FRecLen := RecLen;
|
416 |
|
|
|
417 |
|
|
{Allocate a sort work buffer using at most MaxHeap bytes}
|
418 |
|
|
sorAllocBuffer(MaxHeap);
|
419 |
|
|
|
420 |
|
|
{$IFDEF ThreadSafe}
|
421 |
|
|
Windows.InitializeCriticalSection(sorThreadSafe);
|
422 |
|
|
{$ENDIF}
|
423 |
|
|
end;
|
424 |
|
|
|
425 |
|
|
destructor TStSorter.Destroy;
|
426 |
|
|
begin
|
427 |
|
|
{$IFDEF ThreadSafe}
|
428 |
|
|
Windows.DeleteCriticalSection(sorThreadSafe);
|
429 |
|
|
{$ENDIF}
|
430 |
|
|
sorDeleteMergeFiles;
|
431 |
|
|
sorFreeBuffer;
|
432 |
|
|
end;
|
433 |
|
|
|
434 |
|
|
procedure TStSorter.EnterCS;
|
435 |
|
|
begin
|
436 |
|
|
{$IFDEF ThreadSafe}
|
437 |
|
|
EnterCriticalSection(sorThreadSafe);
|
438 |
|
|
{$ENDIF}
|
439 |
|
|
end;
|
440 |
|
|
|
441 |
|
|
function TStSorter.Get(var X) : Boolean;
|
442 |
|
|
var
|
443 |
|
|
NextIndex : Integer;
|
444 |
|
|
begin
|
445 |
|
|
{$IFDEF ThreadSafe}
|
446 |
|
|
EnterCS;
|
447 |
|
|
try
|
448 |
|
|
{$ENDIF}
|
449 |
|
|
Result := False;
|
450 |
|
|
|
451 |
|
|
if sorState <> 2 then begin
|
452 |
|
|
{First call to Get}
|
453 |
|
|
if sorRunCount > 0 then begin
|
454 |
|
|
{Still have elements to sort}
|
455 |
|
|
sorRunSort(0, sorRunCount-1);
|
456 |
|
|
if sorMergeFileCount > 0 then begin
|
457 |
|
|
{Already have other merge files}
|
458 |
|
|
sorStoreNewMergeFile;
|
459 |
|
|
sorPrimaryMerge;
|
460 |
|
|
sorOpenMergeFiles;
|
461 |
|
|
end else
|
462 |
|
|
{No merging necessary}
|
463 |
|
|
sorGetIndex := 0;
|
464 |
|
|
end else if FCount = 0 then
|
465 |
|
|
{No elements were sorted}
|
466 |
|
|
Exit;
|
467 |
|
|
|
468 |
|
|
sorState := 2;
|
469 |
|
|
end;
|
470 |
|
|
|
471 |
|
|
if sorMergeFileCount > 0 then begin
|
472 |
|
|
{Get next record from merge files}
|
473 |
|
|
NextIndex := sorGetNextElementIndex;
|
474 |
|
|
if NextIndex <> 0 then begin
|
475 |
|
|
{Return the element}
|
476 |
|
|
sorMoveElement(sorMergePtrs[NextIndex], @X);
|
477 |
|
|
{Get pointer to next element in the stream just used}
|
478 |
|
|
sorGetMergeElementPtr(NextIndex);
|
479 |
|
|
Result := True;
|
480 |
|
|
end;
|
481 |
|
|
end else if sorGetIndex < sorRunCount then begin
|
482 |
|
|
{Get next record from run buffer}
|
483 |
|
|
sorMoveElement(sorElementPtr(sorGetIndex), @X);
|
484 |
|
|
inc(sorGetIndex);
|
485 |
|
|
Result := True;
|
486 |
|
|
end;
|
487 |
|
|
{$IFDEF ThreadSafe}
|
488 |
|
|
finally
|
489 |
|
|
LeaveCS;
|
490 |
|
|
end;
|
491 |
|
|
{$ENDIF}
|
492 |
|
|
end;
|
493 |
|
|
|
494 |
|
|
procedure TStSorter.LeaveCS;
|
495 |
|
|
begin
|
496 |
|
|
{$IFDEF ThreadSafe}
|
497 |
|
|
LeaveCriticalSection(sorThreadSafe);
|
498 |
|
|
{$ENDIF}
|
499 |
|
|
end;
|
500 |
|
|
|
501 |
|
|
procedure TStSorter.Reset;
|
502 |
|
|
begin
|
503 |
|
|
{$IFDEF ThreadSafe}
|
504 |
|
|
EnterCS;
|
505 |
|
|
try
|
506 |
|
|
{$ENDIF}
|
507 |
|
|
sorDeleteMergeFiles;
|
508 |
|
|
FCount := 0;
|
509 |
|
|
sorState := 0;
|
510 |
|
|
sorRunCount := 0;
|
511 |
|
|
sorMergeFileCount := 0;
|
512 |
|
|
sorMergeFileMerged := 0;
|
513 |
|
|
sorMergeOpenCount := 0;
|
514 |
|
|
{$IFDEF ThreadSafe}
|
515 |
|
|
finally
|
516 |
|
|
LeaveCS;
|
517 |
|
|
end;
|
518 |
|
|
{$ENDIF}
|
519 |
|
|
end;
|
520 |
|
|
|
521 |
|
|
procedure TStSorter.Put(const X);
|
522 |
|
|
begin
|
523 |
|
|
{$IFDEF ThreadSafe}
|
524 |
|
|
EnterCS;
|
525 |
|
|
try
|
526 |
|
|
{$ENDIF}
|
527 |
|
|
if sorState = 2 then
|
528 |
|
|
{Can't Put after calling Get}
|
529 |
|
|
RaiseError(stscBadState);
|
530 |
|
|
|
531 |
|
|
sorState := 1;
|
532 |
|
|
|
533 |
|
|
if sorRunCount >= sorRunCapacity then begin
|
534 |
|
|
{Run buffer full; sort buffer and store to disk}
|
535 |
|
|
sorRunSort(0, sorRunCount-1);
|
536 |
|
|
sorStoreNewMergeFile;
|
537 |
|
|
sorRunCount := 0;
|
538 |
|
|
end;
|
539 |
|
|
|
540 |
|
|
{Store new element into run buffer}
|
541 |
|
|
sorMoveElement(@X, sorElementPtr(sorRunCount));
|
542 |
|
|
inc(sorRunCount);
|
543 |
|
|
inc(FCount);
|
544 |
|
|
{$IFDEF ThreadSafe}
|
545 |
|
|
finally
|
546 |
|
|
LeaveCS;
|
547 |
|
|
end;
|
548 |
|
|
{$ENDIF}
|
549 |
|
|
end;
|
550 |
|
|
|
551 |
|
|
procedure TStSorter.sorAllocBuffer(MaxHeap : LongInt);
|
552 |
|
|
{-Allocate a work buffer of records in at most MaxHeap bytes}
|
553 |
|
|
var
|
554 |
|
|
Status : Integer;
|
555 |
|
|
AllocRecs : LongInt;
|
556 |
|
|
begin
|
557 |
|
|
Status := stscBadSize;
|
558 |
|
|
repeat
|
559 |
|
|
AllocRecs := MaxHeap div LongInt(FRecLen);
|
560 |
|
|
if AllocRecs < MergeOrder+1 then
|
561 |
|
|
RaiseError(Status);
|
562 |
|
|
{$IFDEF Version6} {$WARN SYMBOL_PLATFORM OFF} {$ENDIF}
|
563 |
|
|
sorBuffer := GlobalAllocPtr(HeapAllocFlags, AllocRecs*LongInt(FRecLen));
|
564 |
|
|
{$IFDEF Version6} {$WARN SYMBOL_PLATFORM ON} {$ENDIF}
|
565 |
|
|
if sorBuffer = nil then begin
|
566 |
|
|
Status := ecOutOfMemory;
|
567 |
|
|
MaxHeap := MaxHeap div 2;
|
568 |
|
|
end else
|
569 |
|
|
break;
|
570 |
|
|
until False;
|
571 |
|
|
|
572 |
|
|
sorMergeBufSize := LongInt(FRecLen)*(AllocRecs div (MergeOrder+1));
|
573 |
|
|
|
574 |
|
|
sorRunCapacity := AllocRecs-2;
|
575 |
|
|
if sorRunCapacity < MinRecsPerRun then
|
576 |
|
|
RaiseError(Status);
|
577 |
|
|
|
578 |
|
|
sorPivotPtr := sorElementPtr(AllocRecs-1);
|
579 |
|
|
sorSwapPtr := sorElementPtr(AllocRecs-2);
|
580 |
|
|
end;
|
581 |
|
|
|
582 |
|
|
procedure TStSorter.sorCreateNewMergeFile(var Handle : Integer);
|
583 |
|
|
{-Create another merge file and return its handle}
|
584 |
|
|
begin
|
585 |
|
|
if sorMergeFileCount = MaxInt then
|
586 |
|
|
{Too many merge files}
|
587 |
|
|
RaiseError(stscTooManyFiles);
|
588 |
|
|
|
589 |
|
|
{Create new merge file}
|
590 |
|
|
inc(sorMergeFileCount);
|
591 |
|
|
Handle := FileCreate(FMergeName(sorMergeFileCount));
|
592 |
|
|
if Handle < 0 then begin
|
593 |
|
|
dec(sorMergeFileCount);
|
594 |
|
|
RaiseError(stscFileCreate);
|
595 |
|
|
end;
|
596 |
|
|
end;
|
597 |
|
|
|
598 |
|
|
procedure TStSorter.sorDeleteMergeFiles;
|
599 |
|
|
{-Delete open and already-closed merge files}
|
600 |
|
|
var
|
601 |
|
|
I : Integer;
|
602 |
|
|
begin
|
603 |
|
|
for I := 1 to sorMergeOpenCount do begin
|
604 |
|
|
FileClose(sorMergeFiles[I]);
|
605 |
|
|
SysUtils.DeleteFile(FMergeName(sorMergeFileNumber[I]));
|
606 |
|
|
end;
|
607 |
|
|
|
608 |
|
|
for I := sorMergeFileMerged+1 to sorMergeFileCount do
|
609 |
|
|
SysUtils.DeleteFile(FMergeName(I));
|
610 |
|
|
end;
|
611 |
|
|
|
612 |
|
|
function TStSorter.sorElementPtr(Index : LongInt) : Pointer;
|
613 |
|
|
{-Return a pointer to the given element in the sort buffer}
|
614 |
|
|
begin
|
615 |
|
|
Result := PAnsiChar(sorBuffer)+Index*LongInt(FRecLen);
|
616 |
|
|
end;
|
617 |
|
|
|
618 |
|
|
procedure TStSorter.sorFlushOutBuffer;
|
619 |
|
|
{-Write the merge output buffer to disk}
|
620 |
|
|
var
|
621 |
|
|
BytesWritten : LongInt;
|
622 |
|
|
begin
|
623 |
|
|
if sorOutBytesUsed <> 0 then begin
|
624 |
|
|
BytesWritten := FileWrite(sorOutFile, sorOutPtr^, sorOutBytesUsed);
|
625 |
|
|
if BytesWritten <> sorOutBytesUsed then
|
626 |
|
|
RaiseError(stscFileWrite);
|
627 |
|
|
end;
|
628 |
|
|
end;
|
629 |
|
|
|
630 |
|
|
procedure TStSorter.sorFreeBuffer;
|
631 |
|
|
begin
|
632 |
|
|
GlobalFreePtr(sorBuffer);
|
633 |
|
|
end;
|
634 |
|
|
|
635 |
|
|
procedure TStSorter.sorGetMergeElementPtr(M : Integer);
|
636 |
|
|
{-Update head pointer in input buffer of specified open merge file}
|
637 |
|
|
var
|
638 |
|
|
BytesRead : LongInt;
|
639 |
|
|
begin
|
640 |
|
|
if sorMergeBytesUsed[M] >= sorMergeBytesLoaded[M] then begin
|
641 |
|
|
{Try to load new data into buffer}
|
642 |
|
|
BytesRead := FileRead(sorMergeFiles[M], sorMergeBases[M]^, sorMergeBufSize);
|
643 |
|
|
if BytesRead < 0 then
|
644 |
|
|
{Error reading file}
|
645 |
|
|
RaiseError(stscFileRead);
|
646 |
|
|
if BytesRead < LongInt(FRecLen) then begin
|
647 |
|
|
{End of file. Close and delete it}
|
648 |
|
|
FileClose(sorMergeFiles[M]);
|
649 |
|
|
SysUtils.DeleteFile(FMergeName(sorMergeFileNumber[M]));
|
650 |
|
|
{Remove file from merge list}
|
651 |
|
|
if M <> sorMergeOpenCount then begin
|
652 |
|
|
sorMergeFileNumber[M] := sorMergeFileNumber[sorMergeOpenCount];
|
653 |
|
|
sorMergeFiles[M] := sorMergeFiles[sorMergeOpenCount];
|
654 |
|
|
sorMergePtrs[M] := sorMergePtrs[sorMergeOpenCount];
|
655 |
|
|
sorMergeBytesLoaded[M] := sorMergeBytesLoaded[sorMergeOpenCount];
|
656 |
|
|
sorMergeBytesUsed[M] := sorMergeBytesUsed[sorMergeOpenCount];
|
657 |
|
|
sorMergeBases[M] := sorMergeBases[sorMergeOpenCount];
|
658 |
|
|
end;
|
659 |
|
|
dec(sorMergeOpenCount);
|
660 |
|
|
Exit;
|
661 |
|
|
end;
|
662 |
|
|
sorMergeBytesLoaded[M] := BytesRead;
|
663 |
|
|
sorMergeBytesUsed[M] := 0;
|
664 |
|
|
end;
|
665 |
|
|
|
666 |
|
|
sorMergePtrs[M] := PAnsiChar(sorMergeBases[M])+sorMergeBytesUsed[M];
|
667 |
|
|
inc(sorMergeBytesUsed[M], FRecLen);
|
668 |
|
|
end;
|
669 |
|
|
|
670 |
|
|
function TStSorter.sorGetNextElementIndex : Integer;
|
671 |
|
|
{-Return index into open merge file of next smallest element}
|
672 |
|
|
var
|
673 |
|
|
M : Integer;
|
674 |
|
|
MinElPtr : Pointer;
|
675 |
|
|
begin
|
676 |
|
|
if sorMergeOpenCount = 0 then begin
|
677 |
|
|
{All merge streams are empty}
|
678 |
|
|
Result := 0;
|
679 |
|
|
Exit;
|
680 |
|
|
end;
|
681 |
|
|
|
682 |
|
|
{Assume first element is the least}
|
683 |
|
|
MinElPtr := sorMergePtrs[1];
|
684 |
|
|
Result := 1;
|
685 |
|
|
|
686 |
|
|
{Scan the other elements}
|
687 |
|
|
for M := 2 to sorMergeOpenCount do
|
688 |
|
|
if FCompare(sorMergePtrs[M]^, MinElPtr^) < 0 then begin
|
689 |
|
|
Result := M;
|
690 |
|
|
MinElPtr := sorMergePtrs[M];
|
691 |
|
|
end;
|
692 |
|
|
end;
|
693 |
|
|
|
694 |
|
|
procedure TStSorter.sorMergeFileGroup;
|
695 |
|
|
{-Merge a group of input files into one output file}
|
696 |
|
|
var
|
697 |
|
|
NextIndex : Integer;
|
698 |
|
|
begin
|
699 |
|
|
sorOutBytesUsed := 0;
|
700 |
|
|
repeat
|
701 |
|
|
{Find index of minimum element}
|
702 |
|
|
NextIndex := sorGetNextElementIndex;
|
703 |
|
|
if NextIndex = 0 then
|
704 |
|
|
break
|
705 |
|
|
else begin
|
706 |
|
|
{Copy element to output}
|
707 |
|
|
sorStoreElement(sorMergePtrs[NextIndex]);
|
708 |
|
|
{Get the next element from its merge stream}
|
709 |
|
|
sorGetMergeElementPtr(NextIndex);
|
710 |
|
|
end;
|
711 |
|
|
until False;
|
712 |
|
|
|
713 |
|
|
{Flush and close the output file}
|
714 |
|
|
sorFlushOutBuffer;
|
715 |
|
|
FileClose(sorOutFile);
|
716 |
|
|
end;
|
717 |
|
|
|
718 |
|
|
procedure TStSorter.sorMoveElement(Src, Dest : Pointer); assembler;
|
719 |
|
|
{-Copy one record to another location, non-overlapping}
|
720 |
|
|
register;
|
721 |
|
|
asm
|
722 |
|
|
{eax = Self, edx = Src, ecx = Dest}
|
723 |
|
|
push esi
|
724 |
|
|
mov esi,Src
|
725 |
|
|
mov edx,edi
|
726 |
|
|
mov edi,Dest
|
727 |
|
|
mov ecx,TStSorter([eax]).FRecLen
|
728 |
|
|
mov eax,ecx
|
729 |
|
|
shr ecx,2
|
730 |
|
|
rep movsd
|
731 |
|
|
mov ecx,eax
|
732 |
|
|
and ecx,3
|
733 |
|
|
rep movsb
|
734 |
|
|
mov edi,edx
|
735 |
|
|
pop esi
|
736 |
|
|
end;
|
737 |
|
|
|
738 |
|
|
procedure TStSorter.sorOpenMergeFiles;
|
739 |
|
|
{-Open a group of up to MergeOrder input files}
|
740 |
|
|
begin
|
741 |
|
|
sorMergeOpenCount := 0;
|
742 |
|
|
while (sorMergeOpenCount < MergeOrder) and
|
743 |
|
|
(sorMergeFileMerged < sorMergeFileCount) do begin
|
744 |
|
|
inc(sorMergeOpenCount);
|
745 |
|
|
{Open associated merge file}
|
746 |
|
|
inc(sorMergeFileMerged);
|
747 |
|
|
sorMergeFiles[sorMergeOpenCount] :=
|
748 |
|
|
FileOpen(FMergeName(sorMergeFileMerged), fmOpenRead);
|
749 |
|
|
if sorMergeFiles[sorMergeOpenCount] < 0 then begin
|
750 |
|
|
dec(sorMergeFileMerged);
|
751 |
|
|
dec(sorMergeOpenCount);
|
752 |
|
|
RaiseError(stscFileOpen);
|
753 |
|
|
end;
|
754 |
|
|
{File number of merge file}
|
755 |
|
|
sorMergeFileNumber[sorMergeOpenCount] := sorMergeFileMerged;
|
756 |
|
|
{Selector for merge file}
|
757 |
|
|
sorMergePtrs[sorMergeOpenCount] := PAnsiChar(sorBuffer)+
|
758 |
|
|
(sorMergeOpenCount-1)*sorMergeBufSize;
|
759 |
|
|
{Number of bytes currently in merge buffer}
|
760 |
|
|
sorMergeBytesLoaded[sorMergeOpenCount] := 0;
|
761 |
|
|
{Number of bytes used in merge buffer}
|
762 |
|
|
sorMergeBytesUsed[sorMergeOpenCount] := 0;
|
763 |
|
|
{Save the merge pointer}
|
764 |
|
|
sorMergeBases[sorMergeOpenCount] := sorMergePtrs[sorMergeOpenCount];
|
765 |
|
|
{Get the first element}
|
766 |
|
|
sorGetMergeElementPtr(sorMergeOpenCount);
|
767 |
|
|
end;
|
768 |
|
|
end;
|
769 |
|
|
|
770 |
|
|
procedure TStSorter.sorPrimaryMerge;
|
771 |
|
|
{-Merge until there are no more than MergeOrder merge files left}
|
772 |
|
|
begin
|
773 |
|
|
sorOutPtr := PAnsiChar(sorBuffer)+MergeOrder*sorMergeBufSize;
|
774 |
|
|
while sorMergeFileCount-sorMergeFileMerged > MergeOrder do begin
|
775 |
|
|
{Open next group of MergeOrder files}
|
776 |
|
|
sorOpenMergeFiles;
|
777 |
|
|
{Create new output file}
|
778 |
|
|
sorCreateNewMergeFile(sorOutFile);
|
779 |
|
|
{Merge these files into the output}
|
780 |
|
|
sorMergeFileGroup;
|
781 |
|
|
end;
|
782 |
|
|
end;
|
783 |
|
|
|
784 |
|
|
procedure TStSorter.sorRunSort(L, R : LongInt);
|
785 |
|
|
{-Sort one run buffer full of records in memory using non-recursive QuickSort}
|
786 |
|
|
const
|
787 |
|
|
StackSize = 32;
|
788 |
|
|
type
|
789 |
|
|
Stack = array[0..StackSize-1] of LongInt;
|
790 |
|
|
var
|
791 |
|
|
Pl : LongInt; {Left edge within partition}
|
792 |
|
|
Pr : LongInt; {Right edge within partition}
|
793 |
|
|
Pm : LongInt; {Mid-point of partition}
|
794 |
|
|
PartitionLen : LongInt; {Size of current partition}
|
795 |
|
|
StackP : Integer; {Stack pointer}
|
796 |
|
|
Lstack : Stack; {Pending partitions, left edge}
|
797 |
|
|
Rstack : Stack; {Pending partitions, right edge}
|
798 |
|
|
begin
|
799 |
|
|
{Make sure there's a compare function}
|
800 |
|
|
if @FCompare = nil then
|
801 |
|
|
RaiseError(stscNoCompare);
|
802 |
|
|
|
803 |
|
|
{Initialize the stack}
|
804 |
|
|
StackP := 0;
|
805 |
|
|
Lstack[0] := L;
|
806 |
|
|
Rstack[0] := R;
|
807 |
|
|
|
808 |
|
|
{Repeatedly take top partition from stack}
|
809 |
|
|
repeat
|
810 |
|
|
|
811 |
|
|
{Pop the stack}
|
812 |
|
|
L := Lstack[StackP];
|
813 |
|
|
R := Rstack[StackP];
|
814 |
|
|
Dec(StackP);
|
815 |
|
|
|
816 |
|
|
{Sort current partition}
|
817 |
|
|
repeat
|
818 |
|
|
Pl := L;
|
819 |
|
|
Pr := R;
|
820 |
|
|
PartitionLen := Pr-Pl+1;
|
821 |
|
|
|
822 |
|
|
{$IFDEF MidPoint}
|
823 |
|
|
Pm := Pl+(PartitionLen shr 1);
|
824 |
|
|
{$ENDIF}
|
825 |
|
|
|
826 |
|
|
{$IFDEF Random}
|
827 |
|
|
Pm := Pl+Random(PartitionLen);
|
828 |
|
|
{$ENDIF}
|
829 |
|
|
|
830 |
|
|
{$IFDEF Median}
|
831 |
|
|
Pm := Pl+(PartitionLen shr 1);
|
832 |
|
|
if PartitionLen >= MedianThreshold then begin
|
833 |
|
|
{Sort elements Pl, Pm, Pr}
|
834 |
|
|
if FCompare(sorElementPtr(Pm)^, sorElementPtr(Pl)^) < 0 then
|
835 |
|
|
sorSwapElements(Pm, Pl);
|
836 |
|
|
if FCompare(sorElementPtr(Pr)^, sorElementPtr(Pl)^) < 0 then
|
837 |
|
|
sorSwapElements(Pr, Pl);
|
838 |
|
|
if FCompare(sorElementPtr(Pr)^, sorElementPtr(Pm)^) < 0 then
|
839 |
|
|
sorSwapElements(Pr, Pm);
|
840 |
|
|
|
841 |
|
|
{Exchange Pm with Pr-1 but use Pm's value as the pivot}
|
842 |
|
|
sorSwapElements(Pm, Pr-1);
|
843 |
|
|
Pm := Pr-1;
|
844 |
|
|
|
845 |
|
|
{Reduce range of swapping}
|
846 |
|
|
inc(Pl);
|
847 |
|
|
dec(Pr, 2);
|
848 |
|
|
end;
|
849 |
|
|
{$ENDIF}
|
850 |
|
|
|
851 |
|
|
{Save the pivot element}
|
852 |
|
|
sorMoveElement(sorElementPtr(Pm), sorPivotPtr);
|
853 |
|
|
|
854 |
|
|
{Swap items in sort order around the pivot}
|
855 |
|
|
repeat
|
856 |
|
|
while FCompare(sorElementPtr(Pl)^, sorPivotPtr^) < 0 do
|
857 |
|
|
Inc(Pl);
|
858 |
|
|
while FCompare(sorPivotPtr^, sorElementPtr(Pr)^) < 0 do
|
859 |
|
|
Dec(Pr);
|
860 |
|
|
|
861 |
|
|
if Pl = Pr then begin
|
862 |
|
|
{Reached the pivot}
|
863 |
|
|
Inc(Pl);
|
864 |
|
|
Dec(Pr);
|
865 |
|
|
end else if Pl < Pr then begin
|
866 |
|
|
{Swap elements around the pivot}
|
867 |
|
|
sorSwapElements(Pl, Pr);
|
868 |
|
|
Inc(Pl);
|
869 |
|
|
Dec(Pr);
|
870 |
|
|
end;
|
871 |
|
|
until Pl > Pr;
|
872 |
|
|
|
873 |
|
|
{Decide which partition to sort next}
|
874 |
|
|
if (Pr-L) < (R-Pl) then begin
|
875 |
|
|
{Left partition is bigger}
|
876 |
|
|
if Pl < R then begin
|
877 |
|
|
{Stack the request for sorting right partition}
|
878 |
|
|
Inc(StackP);
|
879 |
|
|
Lstack[StackP] := Pl;
|
880 |
|
|
Rstack[StackP] := R;
|
881 |
|
|
end;
|
882 |
|
|
{Continue sorting left partition}
|
883 |
|
|
R := Pr;
|
884 |
|
|
end else begin
|
885 |
|
|
{Right partition is bigger}
|
886 |
|
|
if L < Pr then begin
|
887 |
|
|
{Stack the request for sorting left partition}
|
888 |
|
|
Inc(StackP);
|
889 |
|
|
Lstack[StackP] := L;
|
890 |
|
|
Rstack[StackP] := Pr;
|
891 |
|
|
end;
|
892 |
|
|
{Continue sorting right partition}
|
893 |
|
|
L := Pl;
|
894 |
|
|
end;
|
895 |
|
|
until L >= R;
|
896 |
|
|
until StackP < 0;
|
897 |
|
|
end;
|
898 |
|
|
|
899 |
|
|
procedure TStSorter.sorSetCompare(Comp : TUntypedCompareFunc);
|
900 |
|
|
{-Set the compare function, with error checking}
|
901 |
|
|
begin
|
902 |
|
|
if ((FCount <> 0) or (@Comp = nil)) and (@Comp <> @FCompare) then
|
903 |
|
|
RaiseError(stscBadCompare);
|
904 |
|
|
FCompare := Comp;
|
905 |
|
|
end;
|
906 |
|
|
|
907 |
|
|
procedure TStSorter.sorStoreElement(Src : Pointer);
|
908 |
|
|
{-Store element in the merge output buffer}
|
909 |
|
|
begin
|
910 |
|
|
if sorOutBytesUsed >= sorMergeBufSize then begin
|
911 |
|
|
sorFlushOutBuffer;
|
912 |
|
|
sorOutBytesUsed := 0;
|
913 |
|
|
end;
|
914 |
|
|
sorMoveElement(Src, PAnsiChar(sorOutPtr)+sorOutBytesUsed);
|
915 |
|
|
inc(sorOutBytesUsed, FRecLen);
|
916 |
|
|
end;
|
917 |
|
|
|
918 |
|
|
procedure TStSorter.sorStoreNewMergeFile;
|
919 |
|
|
{-Create new merge file, write run buffer to it, close file}
|
920 |
|
|
var
|
921 |
|
|
BytesToWrite, BytesWritten : Integer;
|
922 |
|
|
begin
|
923 |
|
|
sorCreateNewMergeFile(sorOutFile);
|
924 |
|
|
try
|
925 |
|
|
BytesToWrite := sorRunCount*LongInt(FRecLen);
|
926 |
|
|
BytesWritten := FileWrite(sorOutFile, sorBuffer^, BytesToWrite);
|
927 |
|
|
if BytesWritten <> BytesToWrite then
|
928 |
|
|
RaiseError(stscFileWrite);
|
929 |
|
|
finally
|
930 |
|
|
{Close merge file}
|
931 |
|
|
FileClose(sorOutFile);
|
932 |
|
|
end;
|
933 |
|
|
end;
|
934 |
|
|
|
935 |
|
|
procedure TStSorter.sorSwapElements(L, R : LongInt);
|
936 |
|
|
{-Swap elements with indexes L and R}
|
937 |
|
|
var
|
938 |
|
|
LPtr : Pointer;
|
939 |
|
|
RPtr : Pointer;
|
940 |
|
|
begin
|
941 |
|
|
LPtr := sorElementPtr(L);
|
942 |
|
|
RPtr := sorElementPtr(R);
|
943 |
|
|
sorMoveElement(LPtr, sorSwapPtr);
|
944 |
|
|
sorMoveElement(RPtr, LPtr);
|
945 |
|
|
sorMoveElement(sorSwapPtr, RPtr);
|
946 |
|
|
end;
|
947 |
|
|
|
948 |
|
|
procedure ArraySort(var A; RecLen, NumRecs : Cardinal;
|
949 |
|
|
Compare : TUntypedCompareFunc);
|
950 |
|
|
const
|
951 |
|
|
StackSize = 32;
|
952 |
|
|
type
|
953 |
|
|
Stack = array[0..StackSize-1] of LongInt;
|
954 |
|
|
var
|
955 |
|
|
Pl, Pr, Pm, L, R : LongInt;
|
956 |
|
|
ArraySize, PartitionLen : LongInt;
|
957 |
|
|
PivotPtr : Pointer;
|
958 |
|
|
SwapPtr : Pointer;
|
959 |
|
|
StackP : Integer;
|
960 |
|
|
Lstack, Rstack : Stack;
|
961 |
|
|
|
962 |
|
|
function ElementPtr(Index : Cardinal) : Pointer;
|
963 |
|
|
begin
|
964 |
|
|
Result := PAnsiChar(@A)+Index*RecLen;
|
965 |
|
|
end;
|
966 |
|
|
|
967 |
|
|
procedure SwapElements(L, R : LongInt);
|
968 |
|
|
var
|
969 |
|
|
LPtr : Pointer;
|
970 |
|
|
RPtr : Pointer;
|
971 |
|
|
begin
|
972 |
|
|
LPtr := ElementPtr(L);
|
973 |
|
|
RPtr := ElementPtr(R);
|
974 |
|
|
Move(LPtr^, SwapPtr^, RecLen);
|
975 |
|
|
Move(RPtr^, LPtr^, RecLen);
|
976 |
|
|
Move(SwapPtr^, RPtr^, RecLen);
|
977 |
|
|
end;
|
978 |
|
|
|
979 |
|
|
begin
|
980 |
|
|
{Make sure there's a compare function}
|
981 |
|
|
if @Compare = nil then
|
982 |
|
|
RaiseError(stscNoCompare);
|
983 |
|
|
|
984 |
|
|
{Make sure the array size is reasonable}
|
985 |
|
|
ArraySize := LongInt(RecLen)*LongInt(NumRecs);
|
986 |
|
|
if (ArraySize = 0) {or (ArraySize > MaxBlockSize)} then
|
987 |
|
|
RaiseError(stscBadSize);
|
988 |
|
|
|
989 |
|
|
{Get pivot and swap elements}
|
990 |
|
|
GetMem(PivotPtr, RecLen);
|
991 |
|
|
try
|
992 |
|
|
GetMem(SwapPtr, RecLen);
|
993 |
|
|
try
|
994 |
|
|
{Initialize the stack}
|
995 |
|
|
StackP := 0;
|
996 |
|
|
Lstack[0] := 0;
|
997 |
|
|
Rstack[0] := NumRecs-1;
|
998 |
|
|
|
999 |
|
|
{Repeatedly take top partition from stack}
|
1000 |
|
|
repeat
|
1001 |
|
|
|
1002 |
|
|
{Pop the stack}
|
1003 |
|
|
L := Lstack[StackP];
|
1004 |
|
|
R := Rstack[StackP];
|
1005 |
|
|
Dec(StackP);
|
1006 |
|
|
|
1007 |
|
|
{Sort current partition}
|
1008 |
|
|
repeat
|
1009 |
|
|
Pl := L;
|
1010 |
|
|
Pr := R;
|
1011 |
|
|
PartitionLen := Pr-Pl+1;
|
1012 |
|
|
|
1013 |
|
|
{$IFDEF MidPoint}
|
1014 |
|
|
Pm := Pl+(PartitionLen shr 1);
|
1015 |
|
|
{$ENDIF}
|
1016 |
|
|
|
1017 |
|
|
{$IFDEF Random}
|
1018 |
|
|
Pm := Pl+Random(PartitionLen);
|
1019 |
|
|
{$ENDIF}
|
1020 |
|
|
|
1021 |
|
|
{$IFDEF Median}
|
1022 |
|
|
Pm := Pl+(PartitionLen shr 1);
|
1023 |
|
|
if PartitionLen >= MedianThreshold then begin
|
1024 |
|
|
{Sort elements Pl, Pm, Pr}
|
1025 |
|
|
if Compare(ElementPtr(Pm)^, ElementPtr(Pl)^) < 0 then
|
1026 |
|
|
SwapElements(Pm, Pl);
|
1027 |
|
|
if Compare(ElementPtr(Pr)^, ElementPtr(Pl)^) < 0 then
|
1028 |
|
|
SwapElements(Pr, Pl);
|
1029 |
|
|
if Compare(ElementPtr(Pr)^, ElementPtr(Pm)^) < 0 then
|
1030 |
|
|
SwapElements(Pr, Pm);
|
1031 |
|
|
|
1032 |
|
|
{Exchange Pm with Pr-1 but use Pm's value as the pivot}
|
1033 |
|
|
SwapElements(Pm, Pr-1);
|
1034 |
|
|
Pm := Pr-1;
|
1035 |
|
|
|
1036 |
|
|
{Reduce range of swapping}
|
1037 |
|
|
inc(Pl);
|
1038 |
|
|
dec(Pr, 2);
|
1039 |
|
|
end;
|
1040 |
|
|
{$ENDIF}
|
1041 |
|
|
|
1042 |
|
|
{Save the pivot element}
|
1043 |
|
|
Move(ElementPtr(Pm)^, PivotPtr^, RecLen);
|
1044 |
|
|
|
1045 |
|
|
{Swap items in sort order around the pivot}
|
1046 |
|
|
repeat
|
1047 |
|
|
while Compare(ElementPtr(Pl)^, PivotPtr^) < 0 do
|
1048 |
|
|
Inc(Pl);
|
1049 |
|
|
while Compare(PivotPtr^, ElementPtr(Pr)^) < 0 do
|
1050 |
|
|
Dec(Pr);
|
1051 |
|
|
|
1052 |
|
|
if Pl = Pr then begin
|
1053 |
|
|
{Reached the pivot}
|
1054 |
|
|
Inc(Pl);
|
1055 |
|
|
Dec(Pr);
|
1056 |
|
|
end else if Pl < Pr then begin
|
1057 |
|
|
{Swap elements around the pivot}
|
1058 |
|
|
SwapElements(Pl, Pr);
|
1059 |
|
|
Inc(Pl);
|
1060 |
|
|
Dec(Pr);
|
1061 |
|
|
end;
|
1062 |
|
|
until Pl > Pr;
|
1063 |
|
|
|
1064 |
|
|
{Decide which partition to sort next}
|
1065 |
|
|
if (Pr-L) < (R-Pl) then begin
|
1066 |
|
|
{Left partition is bigger}
|
1067 |
|
|
if Pl < R then begin
|
1068 |
|
|
{Stack the request for sorting right partition}
|
1069 |
|
|
Inc(StackP);
|
1070 |
|
|
Lstack[StackP] := Pl;
|
1071 |
|
|
Rstack[StackP] := R;
|
1072 |
|
|
end;
|
1073 |
|
|
{Continue sorting left partition}
|
1074 |
|
|
R := Pr;
|
1075 |
|
|
end else begin
|
1076 |
|
|
{Right partition is bigger}
|
1077 |
|
|
if L < Pr then begin
|
1078 |
|
|
{Stack the request for sorting left partition}
|
1079 |
|
|
Inc(StackP);
|
1080 |
|
|
Lstack[StackP] := L;
|
1081 |
|
|
Rstack[StackP] := Pr;
|
1082 |
|
|
end;
|
1083 |
|
|
{Continue sorting right partition}
|
1084 |
|
|
L := Pl;
|
1085 |
|
|
end;
|
1086 |
|
|
until L >= R;
|
1087 |
|
|
until StackP < 0;
|
1088 |
|
|
|
1089 |
|
|
finally
|
1090 |
|
|
FreeMem(SwapPtr, RecLen);
|
1091 |
|
|
end;
|
1092 |
|
|
finally
|
1093 |
|
|
FreeMem(PivotPtr, RecLen);
|
1094 |
|
|
end;
|
1095 |
|
|
end;
|
1096 |
|
|
|
1097 |
|
|
|
1098 |
|
|
end.
|