1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
|
//------------------------------------------------------------------------------
// File: WXList.cpp
//
// Desc: DirectShow base classes - implements a non-MFC based generic list
// template class.
// Copyright (c) 1992-2001 Microsoft Corporation. All rights reserved.
//------------------------------------------------------------------------------
/* A generic list of pointers to objects.
Objectives: avoid using MFC libraries in ndm kernel mode and
provide a really useful list type.
The class is thread safe in that separate threads may add and
delete items in the list concurrently although the application
must ensure that constructor and destructor access is suitably
synchronised.
The list name must not conflict with MFC classes as an
application may use both
The nodes form a doubly linked, NULL terminated chain with an anchor
block (the list object per se) holding pointers to the first and last
nodes and a count of the nodes.
There is a node cache to reduce the allocation and freeing overhead.
It optionally (determined at construction time) has an Event which is
set whenever the list becomes non-empty and reset whenever it becomes
empty.
It optionally (determined at construction time) has a Critical Section
which is entered during the important part of each operation. (About
all you can do outside it is some parameter checking).
The node cache is a repository of nodes that are NOT in the list to speed
up storage allocation. Each list has its own cache to reduce locking and
serialising. The list accesses are serialised anyway for a given list - a
common cache would mean that we would have to separately serialise access
of all lists within the cache. Because the cache only stores nodes that are
not in the list, releasing the cache does not release any list nodes. This
means that list nodes can be copied or rechained from one list to another
without danger of creating a dangling reference if the original cache goes
away.
Questionable design decisions:
1. Retaining the warts for compatibility
2. Keeping an element count -i.e. counting whenever we do anything
instead of only when we want the count.
3. Making the chain pointers NULL terminated. If the list object
itself looks just like a node and the list is kept as a ring then
it reduces the number of special cases. All inserts look the same.
*/
#include "streams.h"
/* set cursor to the position of each element of list in turn */
#define INTERNALTRAVERSELIST(list, cursor) \
for ( cursor = (list).GetHeadPositionI() \
; cursor!=NULL \
; cursor = (list).Next(cursor) \
)
/* set cursor to the position of each element of list in turn
in reverse order
*/
#define INTERNALREVERSETRAVERSELIST(list, cursor) \
for ( cursor = (list).GetTailPositionI() \
; cursor!=NULL \
; cursor = (list).Prev(cursor) \
)
/* Constructor calls a separate initialisation function that
creates a node cache, optionally creates a lock object
and optionally creates a signaling object.
By default we create a locking object, a DEFAULTCACHE sized
cache but no event object so the list cannot be used in calls
to WaitForSingleObject
*/
CBaseList::CBaseList(__in_opt LPCTSTR pName, // Descriptive list name
INT iItems) : // Node cache size
#ifdef _DEBUG
CBaseObject(pName),
#endif
m_pFirst(NULL),
m_pLast(NULL),
m_Count(0),
m_Cache(iItems)
{
} // constructor
CBaseList::CBaseList(__in_opt LPCTSTR pName) : // Descriptive list name
#ifdef _DEBUG
CBaseObject(pName),
#endif
m_pFirst(NULL),
m_pLast(NULL),
m_Count(0),
m_Cache(DEFAULTCACHE)
{
} // constructor
#ifdef UNICODE
CBaseList::CBaseList(__in_opt LPCSTR pName, // Descriptive list name
INT iItems) : // Node cache size
#ifdef _DEBUG
CBaseObject(pName),
#endif
m_pFirst(NULL),
m_pLast(NULL),
m_Count(0),
m_Cache(iItems)
{
} // constructor
CBaseList::CBaseList(__in_opt LPCSTR pName) : // Descriptive list name
#ifdef _DEBUG
CBaseObject(pName),
#endif
m_pFirst(NULL),
m_pLast(NULL),
m_Count(0),
m_Cache(DEFAULTCACHE)
{
} // constructor
#endif
/* The destructor enumerates all the node objects in the list and
in the cache deleting each in turn. We do not do any processing
on the objects that the list holds (i.e. points to) so if they
represent interfaces for example the creator of the list should
ensure that each of them is released before deleting us
*/
CBaseList::~CBaseList()
{
/* Delete all our list nodes */
RemoveAll();
} // destructor
/* Remove all the nodes from the list but don't do anything
with the objects that each node looks after (this is the
responsibility of the creator).
Aa a last act we reset the signalling event
(if available) to indicate to clients that the list
does not have any entries in it.
*/
void CBaseList::RemoveAll()
{
/* Free up all the CNode objects NOTE we don't bother putting the
deleted nodes into the cache as this method is only really called
in serious times of change such as when we are being deleted at
which point the cache will be deleted anway */
CNode *pn = m_pFirst;
while (pn) {
CNode *op = pn;
pn = pn->Next();
delete op;
}
/* Reset the object count and the list pointers */
m_Count = 0;
m_pFirst = m_pLast = NULL;
} // RemoveAll
/* Return a position enumerator for the entire list.
A position enumerator is a pointer to a node object cast to a
transparent type so all we do is return the head/tail node
pointer in the list.
WARNING because the position is a pointer to a node there is
an implicit assumption for users a the list class that after
deleting an object from the list that any other position
enumerators that you have may be invalid (since the node
may be gone).
*/
__out_opt POSITION CBaseList::GetHeadPositionI() const
{
return (POSITION) m_pFirst;
} // GetHeadPosition
__out_opt POSITION CBaseList::GetTailPositionI() const
{
return (POSITION) m_pLast;
} // GetTailPosition
/* Get the number of objects in the list,
Get the lock before accessing the count.
Locking may not be entirely necessary but it has the side effect
of making sure that all operations are complete before we get it.
So for example if a list is being added to this list then that
will have completed in full before we continue rather than seeing
an intermediate albeit valid state
*/
int CBaseList::GetCountI() const
{
return m_Count;
} // GetCount
/* Return the object at rp, update rp to the next object from
the list or NULL if you have moved over the last object.
You may still call this function once we return NULL but
we will continue to return a NULL position value
*/
__out void *CBaseList::GetNextI(__inout POSITION& rp) const
{
/* have we reached the end of the list */
if (rp == NULL) {
return NULL;
}
/* Lock the object before continuing */
void *pObject;
/* Copy the original position then step on */
CNode *pn = (CNode *) rp;
ASSERT(pn != NULL);
rp = (POSITION) pn->Next();
/* Get the object at the original position from the list */
pObject = pn->GetData();
// ASSERT(pObject != NULL); // NULL pointers in the list are allowed.
return pObject;
} //GetNext
/* Return the object at p.
Asking for the object at NULL ASSERTs then returns NULL
The object is NOT locked. The list is not being changed
in any way. If another thread is busy deleting the object
then locking would only result in a change from one bad
behaviour to another.
*/
__out_opt void *CBaseList::GetI(__in_opt POSITION p) const
{
if (p == NULL) {
return NULL;
}
CNode * pn = (CNode *) p;
void *pObject = pn->GetData();
// ASSERT(pObject != NULL); // NULL pointers in the list are allowed.
return pObject;
} //Get
__out void *CBaseList::GetValidI(__in POSITION p) const
{
CNode * pn = (CNode *) p;
void *pObject = pn->GetData();
// ASSERT(pObject != NULL); // NULL pointers in the list are allowed.
return pObject;
} //Get
/* Return the first position in the list which holds the given pointer.
Return NULL if it's not found.
*/
__out_opt POSITION CBaseList::FindI( __in void * pObj) const
{
POSITION pn;
INTERNALTRAVERSELIST(*this, pn){
if (GetI(pn)==pObj) {
return pn;
}
}
return NULL;
} // Find
/* Remove the first node in the list (deletes the pointer to its object
from the list, does not free the object itself).
Return the pointer to its object or NULL if empty
*/
__out_opt void *CBaseList::RemoveHeadI()
{
/* All we do is get the head position and ask for that to be deleted.
We could special case this since some of the code path checking
in Remove() is redundant as we know there is no previous
node for example but it seems to gain little over the
added complexity
*/
return RemoveI((POSITION)m_pFirst);
} // RemoveHead
/* Remove the last node in the list (deletes the pointer to its object
from the list, does not free the object itself).
Return the pointer to its object or NULL if empty
*/
__out_opt void *CBaseList::RemoveTailI()
{
/* All we do is get the tail position and ask for that to be deleted.
We could special case this since some of the code path checking
in Remove() is redundant as we know there is no previous
node for example but it seems to gain little over the
added complexity
*/
return RemoveI((POSITION)m_pLast);
} // RemoveTail
/* Remove the pointer to the object in this position from the list.
Deal with all the chain pointers
Return a pointer to the object removed from the list.
The node object that is freed as a result
of this operation is added to the node cache where
it can be used again.
Remove(NULL) is a harmless no-op - but probably is a wart.
*/
__out_opt void *CBaseList::RemoveI(__in_opt POSITION pos)
{
/* Lock the critical section before continuing */
// ASSERT (pos!=NULL); // Removing NULL is to be harmless!
if (pos==NULL) return NULL;
CNode *pCurrent = (CNode *) pos;
ASSERT(pCurrent != NULL);
/* Update the previous node */
CNode *pNode = pCurrent->Prev();
if (pNode == NULL) {
m_pFirst = pCurrent->Next();
} else {
pNode->SetNext(pCurrent->Next());
}
/* Update the following node */
pNode = pCurrent->Next();
if (pNode == NULL) {
m_pLast = pCurrent->Prev();
} else {
pNode->SetPrev(pCurrent->Prev());
}
/* Get the object this node was looking after */
void *pObject = pCurrent->GetData();
// ASSERT(pObject != NULL); // NULL pointers in the list are allowed.
/* Try and add the node object to the cache -
a NULL return code from the cache means we ran out of room.
The cache size is fixed by a constructor argument when the
list is created and defaults to DEFAULTCACHE.
This means that the cache will have room for this many
node objects. So if you have a list of media samples
and you know there will never be more than five active at
any given time of them for example then override the default
constructor
*/
m_Cache.AddToCache(pCurrent);
/* If the list is empty then reset the list event */
--m_Count;
ASSERT(m_Count >= 0);
return pObject;
} // Remove
/* Add this object to the tail end of our list
Return the new tail position.
*/
__out_opt POSITION CBaseList::AddTailI(__in void *pObject)
{
/* Lock the critical section before continuing */
CNode *pNode;
// ASSERT(pObject); // NULL pointers in the list are allowed.
/* If there is a node objects in the cache then use
that otherwise we will have to create a new one */
pNode = (CNode *) m_Cache.RemoveFromCache();
if (pNode == NULL) {
pNode = new CNode;
}
/* Check we have a valid object */
if (pNode == NULL) {
return NULL;
}
/* Initialise all the CNode object
just in case it came from the cache
*/
pNode->SetData(pObject);
pNode->SetNext(NULL);
pNode->SetPrev(m_pLast);
if (m_pLast == NULL) {
m_pFirst = pNode;
} else {
m_pLast->SetNext(pNode);
}
/* Set the new last node pointer and also increment the number
of list entries, the critical section is unlocked when we
exit the function
*/
m_pLast = pNode;
++m_Count;
return (POSITION) pNode;
} // AddTail(object)
/* Add this object to the head end of our list
Return the new head position.
*/
__out_opt POSITION CBaseList::AddHeadI(__in void *pObject)
{
CNode *pNode;
// ASSERT(pObject); // NULL pointers in the list are allowed.
/* If there is a node objects in the cache then use
that otherwise we will have to create a new one */
pNode = (CNode *) m_Cache.RemoveFromCache();
if (pNode == NULL) {
pNode = new CNode;
}
/* Check we have a valid object */
if (pNode == NULL) {
return NULL;
}
/* Initialise all the CNode object
just in case it came from the cache
*/
pNode->SetData(pObject);
/* chain it in (set four pointers) */
pNode->SetPrev(NULL);
pNode->SetNext(m_pFirst);
if (m_pFirst == NULL) {
m_pLast = pNode;
} else {
m_pFirst->SetPrev(pNode);
}
m_pFirst = pNode;
++m_Count;
return (POSITION) pNode;
} // AddHead(object)
/* Add all the elements in *pList to the tail of this list.
Return TRUE if it all worked, FALSE if it didn't.
If it fails some elements may have been added.
*/
BOOL CBaseList::AddTail(__in CBaseList *pList)
{
/* lock the object before starting then enumerate
each entry in the source list and add them one by one to
our list (while still holding the object lock)
Lock the other list too.
*/
POSITION pos = pList->GetHeadPositionI();
while (pos) {
if (NULL == AddTailI(pList->GetNextI(pos))) {
return FALSE;
}
}
return TRUE;
} // AddTail(list)
/* Add all the elements in *pList to the head of this list.
Return TRUE if it all worked, FALSE if it didn't.
If it fails some elements may have been added.
*/
BOOL CBaseList::AddHead(__in CBaseList *pList)
{
/* lock the object before starting then enumerate
each entry in the source list and add them one by one to
our list (while still holding the object lock)
Lock the other list too.
To avoid reversing the list, traverse it backwards.
*/
POSITION pos;
INTERNALREVERSETRAVERSELIST(*pList, pos) {
if (NULL== AddHeadI(pList->GetValidI(pos))){
return FALSE;
}
}
return TRUE;
} // AddHead(list)
/* Add the object after position p
p is still valid after the operation.
AddAfter(NULL,x) adds x to the start - same as AddHead
Return the position of the new object, NULL if it failed
*/
__out_opt POSITION CBaseList::AddAfterI(__in_opt POSITION pos, __in void * pObj)
{
if (pos==NULL)
return AddHeadI(pObj);
/* As someone else might be furkling with the list -
Lock the critical section before continuing
*/
CNode *pAfter = (CNode *) pos;
ASSERT(pAfter != NULL);
if (pAfter==m_pLast)
return AddTailI(pObj);
/* set pnode to point to a new node, preferably from the cache */
CNode *pNode = (CNode *) m_Cache.RemoveFromCache();
if (pNode == NULL) {
pNode = new CNode;
}
/* Check we have a valid object */
if (pNode == NULL) {
return NULL;
}
/* Initialise all the CNode object
just in case it came from the cache
*/
pNode->SetData(pObj);
/* It is to be added to the middle of the list - there is a before
and after node. Chain it after pAfter, before pBefore.
*/
CNode * pBefore = pAfter->Next();
ASSERT(pBefore != NULL);
/* chain it in (set four pointers) */
pNode->SetPrev(pAfter);
pNode->SetNext(pBefore);
pBefore->SetPrev(pNode);
pAfter->SetNext(pNode);
++m_Count;
return (POSITION) pNode;
} // AddAfter(object)
BOOL CBaseList::AddAfter(__in_opt POSITION p, __in CBaseList *pList)
{
POSITION pos;
INTERNALTRAVERSELIST(*pList, pos) {
/* p follows along the elements being added */
p = AddAfterI(p, pList->GetValidI(pos));
if (p==NULL) return FALSE;
}
return TRUE;
} // AddAfter(list)
/* Mirror images:
Add the element or list after position p.
p is still valid after the operation.
AddBefore(NULL,x) adds x to the end - same as AddTail
*/
__out_opt POSITION CBaseList::AddBeforeI(__in_opt POSITION pos, __in void * pObj)
{
if (pos==NULL)
return AddTailI(pObj);
/* set pnode to point to a new node, preferably from the cache */
CNode *pBefore = (CNode *) pos;
ASSERT(pBefore != NULL);
if (pBefore==m_pFirst)
return AddHeadI(pObj);
CNode * pNode = (CNode *) m_Cache.RemoveFromCache();
if (pNode == NULL) {
pNode = new CNode;
}
/* Check we have a valid object */
if (pNode == NULL) {
return NULL;
}
/* Initialise all the CNode object
just in case it came from the cache
*/
pNode->SetData(pObj);
/* It is to be added to the middle of the list - there is a before
and after node. Chain it after pAfter, before pBefore.
*/
CNode * pAfter = pBefore->Prev();
ASSERT(pAfter != NULL);
/* chain it in (set four pointers) */
pNode->SetPrev(pAfter);
pNode->SetNext(pBefore);
pBefore->SetPrev(pNode);
pAfter->SetNext(pNode);
++m_Count;
return (POSITION) pNode;
} // Addbefore(object)
BOOL CBaseList::AddBefore(__in_opt POSITION p, __in CBaseList *pList)
{
POSITION pos;
INTERNALREVERSETRAVERSELIST(*pList, pos) {
/* p follows along the elements being added */
p = AddBeforeI(p, pList->GetValidI(pos));
if (p==NULL) return FALSE;
}
return TRUE;
} // AddBefore(list)
/* Split *this after position p in *this
Retain as *this the tail portion of the original *this
Add the head portion to the tail end of *pList
Return TRUE if it all worked, FALSE if it didn't.
e.g.
foo->MoveToTail(foo->GetHeadPosition(), bar);
moves one element from the head of foo to the tail of bar
foo->MoveToTail(NULL, bar);
is a no-op
foo->MoveToTail(foo->GetTailPosition, bar);
concatenates foo onto the end of bar and empties foo.
A better, except excessively long name might be
MoveElementsFromHeadThroughPositionToOtherTail
*/
BOOL CBaseList::MoveToTail
(__in_opt POSITION pos, __in CBaseList *pList)
{
/* Algorithm:
Note that the elements (including their order) in the concatenation
of *pList to the head of *this is invariant.
1. Count elements to be moved
2. Join *pList onto the head of this to make one long chain
3. Set first/Last pointers in *this and *pList
4. Break the chain at the new place
5. Adjust counts
6. Set/Reset any events
*/
if (pos==NULL) return TRUE; // no-op. Eliminates special cases later.
/* Make cMove the number of nodes to move */
CNode * p = (CNode *)pos;
int cMove = 0; // number of nodes to move
while(p!=NULL) {
p = p->Prev();
++cMove;
}
/* Join the two chains together */
if (pList->m_pLast!=NULL)
pList->m_pLast->SetNext(m_pFirst);
if (m_pFirst!=NULL)
m_pFirst->SetPrev(pList->m_pLast);
/* set first and last pointers */
p = (CNode *)pos;
if (pList->m_pFirst==NULL)
pList->m_pFirst = m_pFirst;
m_pFirst = p->Next();
if (m_pFirst==NULL)
m_pLast = NULL;
pList->m_pLast = p;
/* Break the chain after p to create the new pieces */
if (m_pFirst!=NULL)
m_pFirst->SetPrev(NULL);
p->SetNext(NULL);
/* Adjust the counts */
m_Count -= cMove;
pList->m_Count += cMove;
return TRUE;
} // MoveToTail
/* Mirror image of MoveToTail:
Split *this before position p in *this.
Retain in *this the head portion of the original *this
Add the tail portion to the start (i.e. head) of *pList
Return TRUE if it all worked, FALSE if it didn't.
e.g.
foo->MoveToHead(foo->GetTailPosition(), bar);
moves one element from the tail of foo to the head of bar
foo->MoveToHead(NULL, bar);
is a no-op
foo->MoveToHead(foo->GetHeadPosition, bar);
concatenates foo onto the start of bar and empties foo.
*/
BOOL CBaseList::MoveToHead
(__in_opt POSITION pos, __in CBaseList *pList)
{
/* See the comments on the algorithm in MoveToTail */
if (pos==NULL) return TRUE; // no-op. Eliminates special cases later.
/* Make cMove the number of nodes to move */
CNode * p = (CNode *)pos;
int cMove = 0; // number of nodes to move
while(p!=NULL) {
p = p->Next();
++cMove;
}
/* Join the two chains together */
if (pList->m_pFirst!=NULL)
pList->m_pFirst->SetPrev(m_pLast);
if (m_pLast!=NULL)
m_pLast->SetNext(pList->m_pFirst);
/* set first and last pointers */
p = (CNode *)pos;
if (pList->m_pLast==NULL)
pList->m_pLast = m_pLast;
m_pLast = p->Prev();
if (m_pLast==NULL)
m_pFirst = NULL;
pList->m_pFirst = p;
/* Break the chain after p to create the new pieces */
if (m_pLast!=NULL)
m_pLast->SetNext(NULL);
p->SetPrev(NULL);
/* Adjust the counts */
m_Count -= cMove;
pList->m_Count += cMove;
return TRUE;
} // MoveToHead
/* Reverse the order of the [pointers to] objects in *this
*/
void CBaseList::Reverse()
{
/* algorithm:
The obvious booby trap is that you flip pointers around and lose
addressability to the node that you are going to process next.
The easy way to avoid this is do do one chain at a time.
Run along the forward chain,
For each node, set the reverse pointer to the one ahead of us.
The reverse chain is now a copy of the old forward chain, including
the NULL termination.
Run along the reverse chain (i.e. old forward chain again)
For each node set the forward pointer of the node ahead to point back
to the one we're standing on.
The first node needs special treatment,
it's new forward pointer is NULL.
Finally set the First/Last pointers
*/
CNode * p;
// Yes we COULD use a traverse, but it would look funny!
p = m_pFirst;
while (p!=NULL) {
CNode * q;
q = p->Next();
p->SetNext(p->Prev());
p->SetPrev(q);
p = q;
}
p = m_pFirst;
m_pFirst = m_pLast;
m_pLast = p;
#if 0 // old version
if (m_pFirst==NULL) return; // empty list
if (m_pFirst->Next()==NULL) return; // single node list
/* run along forward chain */
for ( p = m_pFirst
; p!=NULL
; p = p->Next()
){
p->SetPrev(p->Next());
}
/* special case first element */
m_pFirst->SetNext(NULL); // fix the old first element
/* run along new reverse chain i.e. old forward chain again */
for ( p = m_pFirst // start at the old first element
; p->Prev()!=NULL // while there's a node still to be set
; p = p->Prev() // work in the same direction as before
){
p->Prev()->SetNext(p);
}
/* fix forward and reverse pointers
- the triple XOR swap would work but all the casts look hideous */
p = m_pFirst;
m_pFirst = m_pLast;
m_pLast = p;
#endif
} // Reverse
|