Debian Codegraph @

sys/directshow/strmbase/baseclasses/wxlist.cpp

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