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: StList.pas 4.04 *}
|
30 |
|
|
{*********************************************************}
|
31 |
|
|
{* SysTools: Linked list class *}
|
32 |
|
|
{*********************************************************}
|
33 |
|
|
|
34 |
|
|
{$I StDefine.inc}
|
35 |
|
|
|
36 |
|
|
{Notes:
|
37 |
|
|
Nodes stored in the list can be of type TStListNode or of a derived type.
|
38 |
|
|
Pass the node class to the list constructor.
|
39 |
|
|
|
40 |
|
|
TStList is a doubly-linked list that can be scanned backward just as
|
41 |
|
|
efficiently as forward.
|
42 |
|
|
|
43 |
|
|
The list retains the index and node of the last node found by Nth (or by
|
44 |
|
|
the indexed array property). This makes For loops that scan a list much
|
45 |
|
|
faster and speeds up random calls to Nth by about a factor of two.
|
46 |
|
|
}
|
47 |
|
|
|
48 |
|
|
unit StList;
|
49 |
|
|
|
50 |
|
|
interface
|
51 |
|
|
|
52 |
|
|
uses
|
53 |
|
|
Windows, SysUtils, Classes,
|
54 |
|
|
StConst, StBase;
|
55 |
|
|
|
56 |
|
|
type
|
57 |
|
|
TStListNode = class(TStNode)
|
58 |
|
|
{.Z+}
|
59 |
|
|
protected
|
60 |
|
|
FNext : TStListNode; {Next node}
|
61 |
|
|
FPrev : TStListNode; {Previous node}
|
62 |
|
|
|
63 |
|
|
{.Z-}
|
64 |
|
|
public
|
65 |
|
|
constructor Create(AData : Pointer); override;
|
66 |
|
|
{-Initialize node}
|
67 |
|
|
end;
|
68 |
|
|
|
69 |
|
|
TStList = class(TStContainer)
|
70 |
|
|
{.Z+}
|
71 |
|
|
protected
|
72 |
|
|
{property instance variables}
|
73 |
|
|
FHead : TStListNode; {Start of list}
|
74 |
|
|
FTail : TStListNode; {End of list}
|
75 |
|
|
|
76 |
|
|
{private instance variables}
|
77 |
|
|
lsLastI : LongInt; {Last index requested from Nth}
|
78 |
|
|
lsLastP : TStListNode; {Last node returned by Nth}
|
79 |
|
|
|
80 |
|
|
{protected undocumented methods}
|
81 |
|
|
procedure ForEachPointer(Action : TIteratePointerFunc;
|
82 |
|
|
OtherData : pointer);
|
83 |
|
|
override;
|
84 |
|
|
function StoresPointers : boolean;
|
85 |
|
|
override;
|
86 |
|
|
{.Z-}
|
87 |
|
|
public
|
88 |
|
|
constructor Create(NodeClass : TStNodeClass); virtual;
|
89 |
|
|
{-Initialize an empty list}
|
90 |
|
|
|
91 |
|
|
procedure LoadFromStream(S : TStream); override;
|
92 |
|
|
{-Create a list and its data from a stream}
|
93 |
|
|
procedure StoreToStream(S : TStream); override;
|
94 |
|
|
{-Write a list and its data to a stream}
|
95 |
|
|
|
96 |
|
|
procedure Clear; override;
|
97 |
|
|
{-Remove all nodes from container but leave it instantiated}
|
98 |
|
|
|
99 |
|
|
function Append(Data : Pointer) : TStListNode;
|
100 |
|
|
{-Add a new node to the end of a list}
|
101 |
|
|
function Insert(Data : Pointer) : TStListNode;
|
102 |
|
|
{-Insert a new node at the start of a list}
|
103 |
|
|
function Place(Data : Pointer; P : TStListNode) : TStListNode;
|
104 |
|
|
{-Place a new node into a list after an existing node P}
|
105 |
|
|
function PlaceBefore(Data : Pointer; P : TStListNode) : TStListNode;
|
106 |
|
|
{-Place a new node into a list before an existing node P}
|
107 |
|
|
function InsertSorted(Data : Pointer) : TStListNode;
|
108 |
|
|
{-Insert a new node in sorted order}
|
109 |
|
|
procedure MoveToHead(P : TStListNode);
|
110 |
|
|
{-Move P to the head of the list}
|
111 |
|
|
|
112 |
|
|
procedure Assign(Source: TPersistent); override;
|
113 |
|
|
{-Assign another container's contents to this one}
|
114 |
|
|
procedure Join(P : TStListNode; L : TStList);
|
115 |
|
|
{-Join list L after P in the current list. L is freed}
|
116 |
|
|
function Split(P : TStListNode) : TStList;
|
117 |
|
|
{-Split list, creating a new list that starts with P}
|
118 |
|
|
|
119 |
|
|
procedure Sort;
|
120 |
|
|
{-Put the list into sorted order}
|
121 |
|
|
|
122 |
|
|
procedure Delete(P : TStListNode);
|
123 |
|
|
{-Remove an element and dispose of its contents}
|
124 |
|
|
|
125 |
|
|
function Next(P : TStListNode) : TStListNode;
|
126 |
|
|
{-Return the node after P, nil if none}
|
127 |
|
|
function Prev(P : TStListNode) : TStListNode;
|
128 |
|
|
{-Return the node before P, nil if none}
|
129 |
|
|
function Nth(Index : LongInt) : TStListNode;
|
130 |
|
|
{-Return the Index'th node in the list, Index >= 0 (cached)}
|
131 |
|
|
function NthFrom(P : TStListNode; Index : LongInt) : TStListNode;
|
132 |
|
|
{-Return the Index'th node from P, either direction}
|
133 |
|
|
function Posn(P : TStListNode) : LongInt;
|
134 |
|
|
{-Return the ordinal position of an element in the list}
|
135 |
|
|
function Distance(P1, P2 : TStListNode) : LongInt;
|
136 |
|
|
{-Return the number of nodes separating P1 and P2 (signed)}
|
137 |
|
|
function Find(Data : Pointer) : TStListNode;
|
138 |
|
|
{-Return the first node whose data equals Data}
|
139 |
|
|
function Iterate(Action : TIterateFunc; Up : Boolean;
|
140 |
|
|
OtherData : Pointer) : TStListNode;
|
141 |
|
|
{-Call Action for all the nodes, returning the last node visited}
|
142 |
|
|
|
143 |
|
|
property Head : TStListNode
|
144 |
|
|
{-Return the head node}
|
145 |
|
|
read FHead;
|
146 |
|
|
property Tail : TStListNode
|
147 |
|
|
{-Return the tail node}
|
148 |
|
|
read FTail;
|
149 |
|
|
property Items[Index : LongInt] : TStListNode
|
150 |
|
|
{-Return the Index'th node, 0-based}
|
151 |
|
|
read Nth;
|
152 |
|
|
default;
|
153 |
|
|
end;
|
154 |
|
|
|
155 |
|
|
{.Z+}
|
156 |
|
|
TStListClass = class of TStList;
|
157 |
|
|
{.Z-}
|
158 |
|
|
|
159 |
|
|
{======================================================================}
|
160 |
|
|
|
161 |
|
|
implementation
|
162 |
|
|
|
163 |
|
|
{$IFDEF ThreadSafe}
|
164 |
|
|
var
|
165 |
|
|
ClassCritSect : TRTLCriticalSection;
|
166 |
|
|
{$ENDIF}
|
167 |
|
|
|
168 |
|
|
procedure EnterClassCS;
|
169 |
|
|
begin
|
170 |
|
|
{$IFDEF ThreadSafe}
|
171 |
|
|
EnterCriticalSection(ClassCritSect);
|
172 |
|
|
{$ENDIF}
|
173 |
|
|
end;
|
174 |
|
|
|
175 |
|
|
procedure LeaveClassCS;
|
176 |
|
|
begin
|
177 |
|
|
{$IFDEF ThreadSafe}
|
178 |
|
|
LeaveCriticalSection(ClassCritSect);
|
179 |
|
|
{$ENDIF}
|
180 |
|
|
end;
|
181 |
|
|
|
182 |
|
|
constructor TStListNode.Create(AData : Pointer);
|
183 |
|
|
begin
|
184 |
|
|
inherited Create(AData);
|
185 |
|
|
end;
|
186 |
|
|
|
187 |
|
|
{----------------------------------------------------------------------}
|
188 |
|
|
|
189 |
|
|
function FindNode(Container : TStContainer;
|
190 |
|
|
Node : TStNode;
|
191 |
|
|
OtherData : Pointer) : Boolean; far;
|
192 |
|
|
begin
|
193 |
|
|
Result := (Node.Data <> OtherData);
|
194 |
|
|
end;
|
195 |
|
|
|
196 |
|
|
function AssignData(Container : TStContainer;
|
197 |
|
|
Data, OtherData : Pointer) : Boolean; far;
|
198 |
|
|
var
|
199 |
|
|
OurList : TStList absolute OtherData;
|
200 |
|
|
begin
|
201 |
|
|
OurList.Append(Data);
|
202 |
|
|
Result := true;
|
203 |
|
|
end;
|
204 |
|
|
|
205 |
|
|
{----------------------------------------------------------------------}
|
206 |
|
|
|
207 |
|
|
function TStList.Append(Data : Pointer) : TStListNode;
|
208 |
|
|
var
|
209 |
|
|
N : TStListNode;
|
210 |
|
|
begin
|
211 |
|
|
{$IFDEF ThreadSafe}
|
212 |
|
|
EnterCS;
|
213 |
|
|
try
|
214 |
|
|
{$ENDIF}
|
215 |
|
|
N := TStListNode(conNodeClass.Create(Data));
|
216 |
|
|
N.FPrev := FTail;
|
217 |
|
|
if not Assigned(FHead) then begin
|
218 |
|
|
{Special case for first node}
|
219 |
|
|
FHead := N;
|
220 |
|
|
FTail := N;
|
221 |
|
|
end else begin
|
222 |
|
|
{Add at end of existing list}
|
223 |
|
|
FTail.FNext := N;
|
224 |
|
|
FTail := N;
|
225 |
|
|
end;
|
226 |
|
|
Inc(FCount);
|
227 |
|
|
Result := N;
|
228 |
|
|
{$IFDEF ThreadSafe}
|
229 |
|
|
finally
|
230 |
|
|
LeaveCS;
|
231 |
|
|
end;
|
232 |
|
|
{$ENDIF}
|
233 |
|
|
end;
|
234 |
|
|
|
235 |
|
|
procedure TStList.Assign(Source: TPersistent);
|
236 |
|
|
begin
|
237 |
|
|
{$IFDEF ThreadSafe}
|
238 |
|
|
EnterCS;
|
239 |
|
|
try
|
240 |
|
|
{$ENDIF}
|
241 |
|
|
{The only containers that we allow to be assigned to a linked list are
|
242 |
|
|
- another SysTools linked list (TStList)
|
243 |
|
|
- a SysTools binary search tree (TStTree)
|
244 |
|
|
- a SysTools collection (TStCollection, TStSortedCollection)}
|
245 |
|
|
if not AssignPointers(Source, AssignData) then
|
246 |
|
|
inherited Assign(Source);
|
247 |
|
|
{$IFDEF ThreadSafe}
|
248 |
|
|
finally
|
249 |
|
|
LeaveCS;
|
250 |
|
|
end;{try..finally}
|
251 |
|
|
{$ENDIF}
|
252 |
|
|
end;
|
253 |
|
|
|
254 |
|
|
procedure TStList.Clear;
|
255 |
|
|
begin
|
256 |
|
|
{$IFDEF ThreadSafe}
|
257 |
|
|
EnterCS;
|
258 |
|
|
try
|
259 |
|
|
{$ENDIF}
|
260 |
|
|
if Count > 0 then begin
|
261 |
|
|
Iterate(DestroyNode, True, nil);
|
262 |
|
|
FCount := 0;
|
263 |
|
|
end;
|
264 |
|
|
FHead := nil;
|
265 |
|
|
FTail := nil;
|
266 |
|
|
lsLastI := -1;
|
267 |
|
|
lsLastP := nil;
|
268 |
|
|
{$IFDEF ThreadSafe}
|
269 |
|
|
finally
|
270 |
|
|
LeaveCS;
|
271 |
|
|
end;
|
272 |
|
|
{$ENDIF}
|
273 |
|
|
end;
|
274 |
|
|
|
275 |
|
|
constructor TStList.Create(NodeClass : TStNodeClass);
|
276 |
|
|
begin
|
277 |
|
|
CreateContainer(NodeClass, 0);
|
278 |
|
|
Clear;
|
279 |
|
|
end;
|
280 |
|
|
|
281 |
|
|
procedure TStList.Delete(P : TStListNode);
|
282 |
|
|
begin
|
283 |
|
|
{$IFDEF ThreadSafe}
|
284 |
|
|
EnterCS;
|
285 |
|
|
try
|
286 |
|
|
{$ENDIF}
|
287 |
|
|
if (not Assigned(P)) or (Count <= 0) then
|
288 |
|
|
Exit;
|
289 |
|
|
if not (P is conNodeClass) then
|
290 |
|
|
RaiseContainerError(stscBadType);
|
291 |
|
|
|
292 |
|
|
with P do begin
|
293 |
|
|
{Fix pointers of surrounding nodes}
|
294 |
|
|
if Assigned(FNext) then
|
295 |
|
|
FNext.FPrev := FPrev;
|
296 |
|
|
if Assigned(FPrev) then
|
297 |
|
|
FPrev.FNext := FNext;
|
298 |
|
|
end;
|
299 |
|
|
|
300 |
|
|
{Fix head and tail of list}
|
301 |
|
|
if FTail = P then
|
302 |
|
|
FTail := FTail.FPrev;
|
303 |
|
|
if FHead = P then
|
304 |
|
|
FHead := FHead.FNext;
|
305 |
|
|
|
306 |
|
|
{Dispose of the node}
|
307 |
|
|
DisposeNodeData(P);
|
308 |
|
|
P.Free;
|
309 |
|
|
Dec(FCount);
|
310 |
|
|
lsLastI := -1;
|
311 |
|
|
{$IFDEF ThreadSafe}
|
312 |
|
|
finally
|
313 |
|
|
LeaveCS;
|
314 |
|
|
end;
|
315 |
|
|
{$ENDIF}
|
316 |
|
|
end;
|
317 |
|
|
|
318 |
|
|
function TStList.Distance(P1, P2 : TStListNode) : LongInt;
|
319 |
|
|
var
|
320 |
|
|
I : LongInt;
|
321 |
|
|
N : TStListNode;
|
322 |
|
|
begin
|
323 |
|
|
{$IFDEF ThreadSafe}
|
324 |
|
|
EnterCS;
|
325 |
|
|
try
|
326 |
|
|
{$ENDIF}
|
327 |
|
|
{Count forward}
|
328 |
|
|
I := 0;
|
329 |
|
|
N := P1;
|
330 |
|
|
while Assigned(N) and (N <> P2) do begin
|
331 |
|
|
Inc(I);
|
332 |
|
|
N := N.FNext;
|
333 |
|
|
end;
|
334 |
|
|
if N = P2 then begin
|
335 |
|
|
Result := I;
|
336 |
|
|
Exit;
|
337 |
|
|
end;
|
338 |
|
|
|
339 |
|
|
{Count backward}
|
340 |
|
|
I := 0;
|
341 |
|
|
N := P1;
|
342 |
|
|
while Assigned(N) and (N <> P2) do begin
|
343 |
|
|
Dec(I);
|
344 |
|
|
N := N.FPrev;
|
345 |
|
|
end;
|
346 |
|
|
if N = P2 then begin
|
347 |
|
|
Result := I;
|
348 |
|
|
Exit;
|
349 |
|
|
end;
|
350 |
|
|
|
351 |
|
|
{Not on same list}
|
352 |
|
|
Result := MaxLongInt;
|
353 |
|
|
{$IFDEF ThreadSafe}
|
354 |
|
|
finally
|
355 |
|
|
LeaveCS;
|
356 |
|
|
end;
|
357 |
|
|
{$ENDIF}
|
358 |
|
|
end;
|
359 |
|
|
|
360 |
|
|
function TStList.Find(Data : Pointer) : TStListNode;
|
361 |
|
|
begin
|
362 |
|
|
{$IFDEF ThreadSafe}
|
363 |
|
|
EnterCS;
|
364 |
|
|
try
|
365 |
|
|
{$ENDIF}
|
366 |
|
|
Result := Iterate(FindNode, True, Data);
|
367 |
|
|
{$IFDEF ThreadSafe}
|
368 |
|
|
finally
|
369 |
|
|
LeaveCS;
|
370 |
|
|
end;
|
371 |
|
|
{$ENDIF}
|
372 |
|
|
end;
|
373 |
|
|
|
374 |
|
|
procedure TStList.ForEachPointer(Action : TIteratePointerFunc;
|
375 |
|
|
OtherData : pointer);
|
376 |
|
|
var
|
377 |
|
|
N : TStListNode;
|
378 |
|
|
P : TStListNode;
|
379 |
|
|
begin
|
380 |
|
|
{$IFDEF ThreadSafe}
|
381 |
|
|
EnterCS;
|
382 |
|
|
try
|
383 |
|
|
{$ENDIF}
|
384 |
|
|
N := FHead;
|
385 |
|
|
while Assigned(N) do begin
|
386 |
|
|
P := N.FNext;
|
387 |
|
|
if Action(Self, N.Data, OtherData) then
|
388 |
|
|
N := P
|
389 |
|
|
else
|
390 |
|
|
Exit;
|
391 |
|
|
end;
|
392 |
|
|
{$IFDEF ThreadSafe}
|
393 |
|
|
finally
|
394 |
|
|
LeaveCS;
|
395 |
|
|
end;
|
396 |
|
|
{$ENDIF}
|
397 |
|
|
end;
|
398 |
|
|
|
399 |
|
|
function TStList.Insert(Data : Pointer) : TStListNode;
|
400 |
|
|
var
|
401 |
|
|
N : TStListNode;
|
402 |
|
|
begin
|
403 |
|
|
{$IFDEF ThreadSafe}
|
404 |
|
|
EnterCS;
|
405 |
|
|
try
|
406 |
|
|
{$ENDIF}
|
407 |
|
|
N := TStListNode(conNodeClass.Create(Data));
|
408 |
|
|
{N.FPrev := nil;}
|
409 |
|
|
N.FNext := FHead;
|
410 |
|
|
if not Assigned(FHead) then
|
411 |
|
|
{Special case for first node}
|
412 |
|
|
FTail := N
|
413 |
|
|
else
|
414 |
|
|
{Add at start of existing list}
|
415 |
|
|
FHead.FPrev := N;
|
416 |
|
|
FHead := N;
|
417 |
|
|
Inc(FCount);
|
418 |
|
|
lsLastI := -1;
|
419 |
|
|
Result := N;
|
420 |
|
|
{$IFDEF ThreadSafe}
|
421 |
|
|
finally
|
422 |
|
|
LeaveCS;
|
423 |
|
|
end;
|
424 |
|
|
{$ENDIF}
|
425 |
|
|
end;
|
426 |
|
|
|
427 |
|
|
function TStList.InsertSorted(Data : Pointer) : TStListNode;
|
428 |
|
|
var
|
429 |
|
|
N : TStListNode;
|
430 |
|
|
P : TStListNode;
|
431 |
|
|
begin
|
432 |
|
|
{$IFDEF ThreadSafe}
|
433 |
|
|
EnterCS;
|
434 |
|
|
try
|
435 |
|
|
{$ENDIF}
|
436 |
|
|
N := TStListNode(conNodeClass.Create(Data));
|
437 |
|
|
Result := N;
|
438 |
|
|
Inc(FCount);
|
439 |
|
|
lsLastI := -1;
|
440 |
|
|
|
441 |
|
|
if not Assigned(FHead) then begin
|
442 |
|
|
{First element added to list}
|
443 |
|
|
FHead := N;
|
444 |
|
|
FTail := N;
|
445 |
|
|
end else begin
|
446 |
|
|
P := FHead;
|
447 |
|
|
while Assigned(P) do begin
|
448 |
|
|
if DoCompare(N.Data, P.Data) < 0 then begin
|
449 |
|
|
if not Assigned(P.FPrev) then begin
|
450 |
|
|
{New head}
|
451 |
|
|
FHead := N;
|
452 |
|
|
end else begin
|
453 |
|
|
P.FPrev.FNext := N;
|
454 |
|
|
N.FPrev := P.FPrev;
|
455 |
|
|
end;
|
456 |
|
|
P.FPrev := N;
|
457 |
|
|
N.FNext := P;
|
458 |
|
|
Exit;
|
459 |
|
|
end;
|
460 |
|
|
P := P.FNext;
|
461 |
|
|
end;
|
462 |
|
|
{New tail}
|
463 |
|
|
FTail.FNext := N;
|
464 |
|
|
N.FPrev := FTail;
|
465 |
|
|
FTail := N;
|
466 |
|
|
end;
|
467 |
|
|
{$IFDEF ThreadSafe}
|
468 |
|
|
finally
|
469 |
|
|
LeaveCS;
|
470 |
|
|
end;
|
471 |
|
|
{$ENDIF}
|
472 |
|
|
end;
|
473 |
|
|
|
474 |
|
|
function TStList.Iterate(Action : TIterateFunc; Up : Boolean;
|
475 |
|
|
OtherData : Pointer) : TStListNode;
|
476 |
|
|
var
|
477 |
|
|
N : TStListNode;
|
478 |
|
|
P : TStListNode;
|
479 |
|
|
begin
|
480 |
|
|
{$IFDEF ThreadSafe}
|
481 |
|
|
EnterCS;
|
482 |
|
|
try
|
483 |
|
|
{$ENDIF}
|
484 |
|
|
if Up then begin
|
485 |
|
|
N := FHead;
|
486 |
|
|
while Assigned(N) do begin
|
487 |
|
|
P := N.FNext;
|
488 |
|
|
if Action(Self, N, OtherData) then
|
489 |
|
|
N := P
|
490 |
|
|
else begin
|
491 |
|
|
Result := N;
|
492 |
|
|
Exit;
|
493 |
|
|
end;
|
494 |
|
|
end;
|
495 |
|
|
end else begin
|
496 |
|
|
N := FTail;
|
497 |
|
|
while Assigned(N) do begin
|
498 |
|
|
P := N.FPrev;
|
499 |
|
|
if Action(Self, N, OtherData) then
|
500 |
|
|
N := P
|
501 |
|
|
else begin
|
502 |
|
|
Result := N;
|
503 |
|
|
Exit;
|
504 |
|
|
end;
|
505 |
|
|
end;
|
506 |
|
|
end;
|
507 |
|
|
Result := nil;
|
508 |
|
|
{$IFDEF ThreadSafe}
|
509 |
|
|
finally
|
510 |
|
|
LeaveCS;
|
511 |
|
|
end;
|
512 |
|
|
{$ENDIF}
|
513 |
|
|
end;
|
514 |
|
|
|
515 |
|
|
procedure TStList.Join(P : TStListNode; L : TStList);
|
516 |
|
|
var
|
517 |
|
|
N : TStListNode;
|
518 |
|
|
Q : TStListNode;
|
519 |
|
|
begin
|
520 |
|
|
{$IFDEF ThreadSafe}
|
521 |
|
|
EnterClassCS;
|
522 |
|
|
EnterCS;
|
523 |
|
|
L.EnterCS;
|
524 |
|
|
try
|
525 |
|
|
{$ENDIF}
|
526 |
|
|
if Assigned(L) then begin
|
527 |
|
|
if Assigned(P) and (L.Count > 0) then begin
|
528 |
|
|
{Patch the list into the current one}
|
529 |
|
|
N := L.Head;
|
530 |
|
|
Q := P.FNext;
|
531 |
|
|
|
532 |
|
|
P.FNext := N;
|
533 |
|
|
N.FPrev := P;
|
534 |
|
|
|
535 |
|
|
if Assigned(Q) then begin
|
536 |
|
|
N := L.Tail;
|
537 |
|
|
N.FNext := Q;
|
538 |
|
|
Q.FPrev := N;
|
539 |
|
|
end;
|
540 |
|
|
|
541 |
|
|
Inc(FCount, L.Count);
|
542 |
|
|
lsLastI := -1;
|
543 |
|
|
end;
|
544 |
|
|
|
545 |
|
|
{Free L (but not its nodes)}
|
546 |
|
|
L.IncNodeProtection;
|
547 |
|
|
L.Free;
|
548 |
|
|
end;
|
549 |
|
|
{$IFDEF ThreadSafe}
|
550 |
|
|
finally
|
551 |
|
|
L.LeaveCS;
|
552 |
|
|
LeaveCS;
|
553 |
|
|
LeaveClassCS;
|
554 |
|
|
end;
|
555 |
|
|
{$ENDIF}
|
556 |
|
|
end;
|
557 |
|
|
|
558 |
|
|
procedure TStList.LoadFromStream(S : TStream);
|
559 |
|
|
var
|
560 |
|
|
Data : pointer;
|
561 |
|
|
Reader : TReader;
|
562 |
|
|
StreamedClass : TPersistentClass;
|
563 |
|
|
StreamedNodeClass : TPersistentClass;
|
564 |
|
|
StreamedClassName : string;
|
565 |
|
|
StreamedNodeClassName : string;
|
566 |
|
|
begin
|
567 |
|
|
{$IFDEF ThreadSafe}
|
568 |
|
|
EnterCS;
|
569 |
|
|
try
|
570 |
|
|
{$ENDIF}
|
571 |
|
|
Clear;
|
572 |
|
|
Reader := TReader.Create(S, 1024);
|
573 |
|
|
try
|
574 |
|
|
with Reader do
|
575 |
|
|
begin
|
576 |
|
|
StreamedClassName := ReadString;
|
577 |
|
|
StreamedClass := GetClass(StreamedClassName);
|
578 |
|
|
if (StreamedClass = nil) then
|
579 |
|
|
RaiseContainerErrorFmt(stscUnknownClass, [StreamedClassName]);
|
580 |
|
|
if (not IsOrInheritsFrom(StreamedClass, Self.ClassType)) or
|
581 |
|
|
(not IsOrInheritsFrom(TStList, StreamedClass)) then
|
582 |
|
|
RaiseContainerError(stscWrongClass);
|
583 |
|
|
StreamedNodeClassName := ReadString;
|
584 |
|
|
StreamedNodeClass := GetClass(StreamedNodeClassName);
|
585 |
|
|
if (StreamedNodeClass = nil) then
|
586 |
|
|
RaiseContainerErrorFmt(stscUnknownNodeClass, [StreamedNodeClassName]);
|
587 |
|
|
if (not IsOrInheritsFrom(StreamedNodeClass, conNodeClass)) or
|
588 |
|
|
(not IsOrInheritsFrom(TStListNode, StreamedNodeClass)) then
|
589 |
|
|
RaiseContainerError(stscWrongNodeClass);
|
590 |
|
|
ReadListBegin;
|
591 |
|
|
while not EndOfList do
|
592 |
|
|
begin
|
593 |
|
|
Data := DoLoadData(Reader);
|
594 |
|
|
Append(Data);
|
595 |
|
|
end;
|
596 |
|
|
ReadListEnd;
|
597 |
|
|
end;
|
598 |
|
|
finally
|
599 |
|
|
Reader.Free;
|
600 |
|
|
end;
|
601 |
|
|
{$IFDEF ThreadSafe}
|
602 |
|
|
finally
|
603 |
|
|
LeaveCS;
|
604 |
|
|
end;
|
605 |
|
|
{$ENDIF}
|
606 |
|
|
end;
|
607 |
|
|
|
608 |
|
|
procedure TStList.MoveToHead(P : TStListNode);
|
609 |
|
|
begin
|
610 |
|
|
{$IFDEF ThreadSafe}
|
611 |
|
|
EnterCS;
|
612 |
|
|
try
|
613 |
|
|
{$ENDIF}
|
614 |
|
|
if Assigned(P) then
|
615 |
|
|
if P <> Head then begin
|
616 |
|
|
with P do begin
|
617 |
|
|
{Fix pointers of surrounding nodes}
|
618 |
|
|
if FTail = P then
|
619 |
|
|
FTail := FTail.FPrev
|
620 |
|
|
else
|
621 |
|
|
FNext.FPrev := FPrev;
|
622 |
|
|
FPrev.FNext := FNext;
|
623 |
|
|
|
624 |
|
|
FNext := FHead;
|
625 |
|
|
FPrev := nil;
|
626 |
|
|
end;
|
627 |
|
|
FHead.FPrev := P;
|
628 |
|
|
FHead := P;
|
629 |
|
|
end;
|
630 |
|
|
{$IFDEF ThreadSafe}
|
631 |
|
|
finally
|
632 |
|
|
LeaveCS;
|
633 |
|
|
end;
|
634 |
|
|
{$ENDIF}
|
635 |
|
|
end;
|
636 |
|
|
|
637 |
|
|
function TStList.Next(P : TStListNode) : TStListNode;
|
638 |
|
|
begin
|
639 |
|
|
{$IFDEF ThreadSafe}
|
640 |
|
|
EnterCS;
|
641 |
|
|
try
|
642 |
|
|
{$ENDIF}
|
643 |
|
|
Result := P.FNext;
|
644 |
|
|
{$IFDEF ThreadSafe}
|
645 |
|
|
finally
|
646 |
|
|
LeaveCS;
|
647 |
|
|
end;
|
648 |
|
|
{$ENDIF}
|
649 |
|
|
end;
|
650 |
|
|
|
651 |
|
|
function TStList.Nth(Index : LongInt) : TStListNode;
|
652 |
|
|
var
|
653 |
|
|
MinI : LongInt;
|
654 |
|
|
MinP : TStListNode;
|
655 |
|
|
begin
|
656 |
|
|
{$IFDEF ThreadSafe}
|
657 |
|
|
EnterCS;
|
658 |
|
|
try
|
659 |
|
|
{$ENDIF}
|
660 |
|
|
if (Index < 0) or (Index >= FCount) then
|
661 |
|
|
Result := nil
|
662 |
|
|
else begin
|
663 |
|
|
MinI := Index;
|
664 |
|
|
MinP := FHead;
|
665 |
|
|
if lsLastI >= 0 then
|
666 |
|
|
{scan the fewest possible nodes}
|
667 |
|
|
if Index <= lsLastI then begin
|
668 |
|
|
if lsLastI-Index < Index then begin
|
669 |
|
|
MinI := Index-lsLastI;
|
670 |
|
|
MinP := lsLastP;
|
671 |
|
|
end;
|
672 |
|
|
end else if Index-lsLastI < FCount-1-Index then begin
|
673 |
|
|
MinI := Index-lsLastI;
|
674 |
|
|
MinP := lsLastP;
|
675 |
|
|
end else begin
|
676 |
|
|
MinI := Index-(FCount-1);
|
677 |
|
|
MinP := FTail;
|
678 |
|
|
end;
|
679 |
|
|
|
680 |
|
|
Result := NthFrom(MinP, MinI);
|
681 |
|
|
lsLastI := Index;
|
682 |
|
|
lsLastP := Result;
|
683 |
|
|
end;
|
684 |
|
|
{$IFDEF ThreadSafe}
|
685 |
|
|
finally
|
686 |
|
|
LeaveCS;
|
687 |
|
|
end;
|
688 |
|
|
{$ENDIF}
|
689 |
|
|
end;
|
690 |
|
|
|
691 |
|
|
function TStList.NthFrom(P : TStListNode; Index : LongInt) : TStListNode;
|
692 |
|
|
var
|
693 |
|
|
I : LongInt;
|
694 |
|
|
begin
|
695 |
|
|
{$IFDEF ThreadSafe}
|
696 |
|
|
EnterCS;
|
697 |
|
|
try
|
698 |
|
|
{$ENDIF}
|
699 |
|
|
if Assigned(P) then begin
|
700 |
|
|
if not (P is conNodeClass) then
|
701 |
|
|
RaiseContainerError(stscBadType);
|
702 |
|
|
if Index > 0 then begin
|
703 |
|
|
for I := 1 to Index do begin
|
704 |
|
|
P := P.FNext;
|
705 |
|
|
if not Assigned(P) then
|
706 |
|
|
break;
|
707 |
|
|
end;
|
708 |
|
|
end else begin
|
709 |
|
|
for I := 1 to -Index do begin
|
710 |
|
|
P := P.FPrev;
|
711 |
|
|
if not Assigned(P) then
|
712 |
|
|
break;
|
713 |
|
|
end;
|
714 |
|
|
end;
|
715 |
|
|
end;
|
716 |
|
|
Result := P;
|
717 |
|
|
{$IFDEF ThreadSafe}
|
718 |
|
|
finally
|
719 |
|
|
LeaveCS;
|
720 |
|
|
end;
|
721 |
|
|
{$ENDIF}
|
722 |
|
|
end;
|
723 |
|
|
|
724 |
|
|
function TStList.Place(Data : Pointer; P : TStListNode) : TStListNode;
|
725 |
|
|
var
|
726 |
|
|
N : TStListNode;
|
727 |
|
|
begin
|
728 |
|
|
{$IFDEF ThreadSafe}
|
729 |
|
|
EnterCS;
|
730 |
|
|
try
|
731 |
|
|
{$ENDIF}
|
732 |
|
|
if not Assigned(P) then
|
733 |
|
|
Result := Insert(Data)
|
734 |
|
|
else if P = FTail then
|
735 |
|
|
Result := Append(Data)
|
736 |
|
|
else begin
|
737 |
|
|
N := TStListNode(conNodeClass.Create(Data));
|
738 |
|
|
N.FPrev := P;
|
739 |
|
|
N.FNext := P.FNext;
|
740 |
|
|
P.FNext.FPrev := N;
|
741 |
|
|
P.FNext := N;
|
742 |
|
|
Inc(FCount);
|
743 |
|
|
lsLastI := -1;
|
744 |
|
|
Result := N;
|
745 |
|
|
end;
|
746 |
|
|
{$IFDEF ThreadSafe}
|
747 |
|
|
finally
|
748 |
|
|
LeaveCS;
|
749 |
|
|
end;
|
750 |
|
|
{$ENDIF}
|
751 |
|
|
end;
|
752 |
|
|
|
753 |
|
|
function TStList.PlaceBefore(Data : Pointer; P : TStListNode) : TStListNode;
|
754 |
|
|
var
|
755 |
|
|
N : TStListNode;
|
756 |
|
|
begin
|
757 |
|
|
{$IFDEF ThreadSafe}
|
758 |
|
|
EnterCS;
|
759 |
|
|
try
|
760 |
|
|
{$ENDIF}
|
761 |
|
|
if (not Assigned(P)) or (P = Head) then
|
762 |
|
|
{Place the new element at the start of the list}
|
763 |
|
|
Result := Insert(Data)
|
764 |
|
|
else begin
|
765 |
|
|
{Patch in the new element}
|
766 |
|
|
N := TStListNode(conNodeClass.Create(Data));
|
767 |
|
|
N.FNext := P;
|
768 |
|
|
N.FPrev := P.FPrev;
|
769 |
|
|
P.FPrev.FNext := N;
|
770 |
|
|
P.FPrev := N;
|
771 |
|
|
lsLastI := -1;
|
772 |
|
|
Inc(FCount);
|
773 |
|
|
Result := N;
|
774 |
|
|
end;
|
775 |
|
|
{$IFDEF ThreadSafe}
|
776 |
|
|
finally
|
777 |
|
|
LeaveCS;
|
778 |
|
|
end;
|
779 |
|
|
{$ENDIF}
|
780 |
|
|
end;
|
781 |
|
|
|
782 |
|
|
function TStList.Posn(P : TStListNode) : LongInt;
|
783 |
|
|
var
|
784 |
|
|
I : LongInt;
|
785 |
|
|
N : TStListNode;
|
786 |
|
|
begin
|
787 |
|
|
{$IFDEF ThreadSafe}
|
788 |
|
|
EnterCS;
|
789 |
|
|
try
|
790 |
|
|
{$ENDIF}
|
791 |
|
|
if not Assigned(P) then
|
792 |
|
|
Result := -1
|
793 |
|
|
else begin
|
794 |
|
|
if not (P is conNodeClass) then
|
795 |
|
|
RaiseContainerError(stscBadType);
|
796 |
|
|
I := 0;
|
797 |
|
|
N := FHead;
|
798 |
|
|
while Assigned(N) do begin
|
799 |
|
|
if P = N then begin
|
800 |
|
|
Result := I;
|
801 |
|
|
exit;
|
802 |
|
|
end;
|
803 |
|
|
Inc(I);
|
804 |
|
|
N := N.FNext;
|
805 |
|
|
end;
|
806 |
|
|
Result := -1;
|
807 |
|
|
end;
|
808 |
|
|
{$IFDEF ThreadSafe}
|
809 |
|
|
finally
|
810 |
|
|
LeaveCS;
|
811 |
|
|
end;
|
812 |
|
|
{$ENDIF}
|
813 |
|
|
end;
|
814 |
|
|
|
815 |
|
|
function TStList.Prev(P : TStListNode) : TStListNode;
|
816 |
|
|
begin
|
817 |
|
|
{$IFDEF ThreadSafe}
|
818 |
|
|
EnterCS;
|
819 |
|
|
try
|
820 |
|
|
{$ENDIF}
|
821 |
|
|
Result := P.FPrev;
|
822 |
|
|
{$IFDEF ThreadSafe}
|
823 |
|
|
finally
|
824 |
|
|
LeaveCS;
|
825 |
|
|
end;
|
826 |
|
|
{$ENDIF}
|
827 |
|
|
end;
|
828 |
|
|
|
829 |
|
|
procedure TStList.Sort;
|
830 |
|
|
const
|
831 |
|
|
StackSize = 32;
|
832 |
|
|
type
|
833 |
|
|
Stack = array[0..StackSize-1] of TStListNode;
|
834 |
|
|
var
|
835 |
|
|
L : TStListNode;
|
836 |
|
|
R : TStListNode;
|
837 |
|
|
PL : TStListNode;
|
838 |
|
|
PR : TStListNode;
|
839 |
|
|
PivotData : Pointer;
|
840 |
|
|
TmpData : Pointer;
|
841 |
|
|
Dist : LongInt;
|
842 |
|
|
DistL : LongInt;
|
843 |
|
|
DistR : LongInt;
|
844 |
|
|
StackP : Integer;
|
845 |
|
|
LStack : Stack;
|
846 |
|
|
RStack : Stack;
|
847 |
|
|
DStack : array[0..StackSize-1] of LongInt;
|
848 |
|
|
begin
|
849 |
|
|
{$IFDEF ThreadSafe}
|
850 |
|
|
EnterCS;
|
851 |
|
|
try
|
852 |
|
|
{$ENDIF}
|
853 |
|
|
{Need at least 2 elements to sort}
|
854 |
|
|
if Count <= 1 then
|
855 |
|
|
Exit;
|
856 |
|
|
lsLastI := -1;
|
857 |
|
|
|
858 |
|
|
{Initialize the stacks}
|
859 |
|
|
StackP := 0;
|
860 |
|
|
LStack[0] := FHead;
|
861 |
|
|
RStack[0] := FTail;
|
862 |
|
|
DStack[0] := Count-1;
|
863 |
|
|
|
864 |
|
|
{Repeatedly take top partition from stack}
|
865 |
|
|
repeat
|
866 |
|
|
|
867 |
|
|
{Pop the stack}
|
868 |
|
|
L := LStack[StackP];
|
869 |
|
|
R := RStack[StackP];
|
870 |
|
|
Dist := DStack[StackP];
|
871 |
|
|
Dec(StackP);
|
872 |
|
|
|
873 |
|
|
if L <> R then
|
874 |
|
|
{Sort current partition}
|
875 |
|
|
repeat
|
876 |
|
|
|
877 |
|
|
{Load the pivot element}
|
878 |
|
|
PivotData := NthFrom(L, Dist div 2).Data;
|
879 |
|
|
PL := L;
|
880 |
|
|
PR := R;
|
881 |
|
|
DistL := Dist;
|
882 |
|
|
DistR := Dist;
|
883 |
|
|
|
884 |
|
|
{Swap items in sort order around the pivot index}
|
885 |
|
|
repeat
|
886 |
|
|
while DoCompare(PL.Data, PivotData) < 0 do begin
|
887 |
|
|
PL := PL.FNext;
|
888 |
|
|
Dec(Dist);
|
889 |
|
|
Dec(DistR);
|
890 |
|
|
end;
|
891 |
|
|
while DoCompare(PivotData, PR.Data) < 0 do begin
|
892 |
|
|
PR := PR.FPrev;
|
893 |
|
|
Dec(Dist);
|
894 |
|
|
Dec(DistL);
|
895 |
|
|
end;
|
896 |
|
|
if Dist >= 0 then begin
|
897 |
|
|
if PL <> PR then begin
|
898 |
|
|
{Swap the two elements}
|
899 |
|
|
TmpData := PL.Data;
|
900 |
|
|
PL.Data := PR.Data;
|
901 |
|
|
PR.Data := TmpData;
|
902 |
|
|
end;
|
903 |
|
|
if Assigned(PL.FNext) then begin
|
904 |
|
|
PL := PL.FNext;
|
905 |
|
|
Dec(Dist);
|
906 |
|
|
Dec(DistR);
|
907 |
|
|
end;
|
908 |
|
|
if Assigned(PR.FPrev) then begin
|
909 |
|
|
PR := PR.FPrev;
|
910 |
|
|
Dec(Dist);
|
911 |
|
|
Dec(DistL);
|
912 |
|
|
end;
|
913 |
|
|
end;
|
914 |
|
|
until Dist < 0;
|
915 |
|
|
|
916 |
|
|
{Decide which partition to sort next}
|
917 |
|
|
if DistL < DistR then begin
|
918 |
|
|
{Right partition is bigger}
|
919 |
|
|
if DistR > 0 then begin
|
920 |
|
|
{Stack the request for sorting right partition}
|
921 |
|
|
Inc(StackP);
|
922 |
|
|
LStack[StackP] := PL;
|
923 |
|
|
RStack[StackP] := R;
|
924 |
|
|
DStack[StackP] := DistR;
|
925 |
|
|
end;
|
926 |
|
|
{Continue sorting left partition}
|
927 |
|
|
R := PR;
|
928 |
|
|
Dist := DistL;
|
929 |
|
|
end else begin
|
930 |
|
|
{Left partition is bigger}
|
931 |
|
|
if DistL > 0 then begin
|
932 |
|
|
{Stack the request for sorting left partition}
|
933 |
|
|
Inc(StackP);
|
934 |
|
|
LStack[StackP] := L;
|
935 |
|
|
RStack[StackP] := PR;
|
936 |
|
|
DStack[StackP] := DistL;
|
937 |
|
|
end;
|
938 |
|
|
{Continue sorting right partition}
|
939 |
|
|
L := PL;
|
940 |
|
|
Dist := DistR;
|
941 |
|
|
end;
|
942 |
|
|
|
943 |
|
|
until Dist <= 0;
|
944 |
|
|
until StackP < 0;
|
945 |
|
|
{$IFDEF ThreadSafe}
|
946 |
|
|
finally
|
947 |
|
|
LeaveCS;
|
948 |
|
|
end;
|
949 |
|
|
{$ENDIF}
|
950 |
|
|
end;
|
951 |
|
|
|
952 |
|
|
function TStList.Split(P : TStListNode) : TStList;
|
953 |
|
|
var
|
954 |
|
|
I : LongInt;
|
955 |
|
|
begin
|
956 |
|
|
{$IFDEF ThreadSafe}
|
957 |
|
|
EnterCS;
|
958 |
|
|
try
|
959 |
|
|
{$ENDIF}
|
960 |
|
|
I := Posn(P);
|
961 |
|
|
if I < 0 then begin
|
962 |
|
|
Result := nil;
|
963 |
|
|
Exit;
|
964 |
|
|
end;
|
965 |
|
|
|
966 |
|
|
{Create and initialize the new list}
|
967 |
|
|
Result := TStListClass(ClassType).Create(conNodeClass);
|
968 |
|
|
Result.Compare := Compare;
|
969 |
|
|
Result.OnCompare := OnCompare;
|
970 |
|
|
Result.DisposeData := DisposeData;
|
971 |
|
|
Result.OnDisposeData := OnDisposeData;
|
972 |
|
|
Result.LoadData := LoadData;
|
973 |
|
|
Result.OnLoadData := OnLoadData;
|
974 |
|
|
Result.StoreData := StoreData;
|
975 |
|
|
Result.OnStoreData := OnStoreData;
|
976 |
|
|
Result.FHead := P;
|
977 |
|
|
Result.FTail := FTail;
|
978 |
|
|
Result.FCount := Count-I;
|
979 |
|
|
Result.lsLastI := -1;
|
980 |
|
|
|
981 |
|
|
{Truncate the old list}
|
982 |
|
|
if Assigned(P.FPrev) then begin
|
983 |
|
|
P.FPrev.FNext := nil;
|
984 |
|
|
FTail := P.FPrev;
|
985 |
|
|
P.FPrev := nil;
|
986 |
|
|
end;
|
987 |
|
|
if P = FHead then
|
988 |
|
|
FHead := nil;
|
989 |
|
|
FCount := I;
|
990 |
|
|
lsLastI := -1;
|
991 |
|
|
{$IFDEF ThreadSafe}
|
992 |
|
|
finally
|
993 |
|
|
LeaveCS;
|
994 |
|
|
end;
|
995 |
|
|
{$ENDIF}
|
996 |
|
|
end;
|
997 |
|
|
|
998 |
|
|
function TStList.StoresPointers : Boolean;
|
999 |
|
|
begin
|
1000 |
|
|
Result := true;
|
1001 |
|
|
end;
|
1002 |
|
|
|
1003 |
|
|
procedure TStList.StoreToStream(S : TStream);
|
1004 |
|
|
var
|
1005 |
|
|
Writer : TWriter;
|
1006 |
|
|
Walker : TStListNode;
|
1007 |
|
|
begin
|
1008 |
|
|
{$IFDEF ThreadSafe}
|
1009 |
|
|
EnterCS;
|
1010 |
|
|
try
|
1011 |
|
|
{$ENDIF}
|
1012 |
|
|
Writer := TWriter.Create(S, 1024);
|
1013 |
|
|
try
|
1014 |
|
|
with Writer do
|
1015 |
|
|
begin
|
1016 |
|
|
WriteString(Self.ClassName);
|
1017 |
|
|
WriteString(conNodeClass.ClassName);
|
1018 |
|
|
WriteListBegin;
|
1019 |
|
|
Walker := Head;
|
1020 |
|
|
while Walker <> nil do
|
1021 |
|
|
begin
|
1022 |
|
|
DoStoreData(Writer, Walker.Data);
|
1023 |
|
|
Walker := Next(Walker);
|
1024 |
|
|
end;
|
1025 |
|
|
WriteListEnd;
|
1026 |
|
|
end;
|
1027 |
|
|
finally
|
1028 |
|
|
Writer.Free;
|
1029 |
|
|
end;
|
1030 |
|
|
{$IFDEF ThreadSafe}
|
1031 |
|
|
finally
|
1032 |
|
|
LeaveCS;
|
1033 |
|
|
end;
|
1034 |
|
|
{$ENDIF}
|
1035 |
|
|
end;
|
1036 |
|
|
|
1037 |
|
|
{$IFDEF ThreadSafe}
|
1038 |
|
|
initialization
|
1039 |
|
|
Windows.InitializeCriticalSection(ClassCritSect);
|
1040 |
|
|
finalization
|
1041 |
|
|
Windows.DeleteCriticalSection(ClassCritSect);
|
1042 |
|
|
{$ENDIF}
|
1043 |
|
|
end.
|