1 |
// 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.
|