1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2017-2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #pragma once
10 
11 #include "Object.h"
12 #include "Threading.h"
13 #include "MemCopy.h"
14 
15 
16 #if defined _DEBUG
17 #   if defined( ISTDLIB_UMD ) && !defined( NO_RTTI )
18 #       include <typeinfo>
19 #       define TYPEID_NAME( type )   (typeid(type).name())
20 #   else // ISTDLIB_UMD
21 #       define TYPEID_NAME( type )   (#type)
22 #   endif // ISTDLIB_UMD
23 #else // _DEBUG
24 #   define TYPEID_NAME( type )
25 #endif // _DEBUG
26 
27 namespace iSTD
28 {
29 
30 /*****************************************************************************\
31 Struct: IsLinkedListTypeSupported
32 \*****************************************************************************/
33 template<typename T>
34 struct IsLinkedListTypeSupported                    { enum { value = false }; };
35 
36 template<>
37 struct IsLinkedListTypeSupported<bool>              { enum { value = true }; };
38 
39 template<>
40 struct IsLinkedListTypeSupported<char>              { enum { value = true }; };
41 
42 template<>
43 struct IsLinkedListTypeSupported<unsigned char>     { enum { value = true }; };
44 
45 template<>
46 struct IsLinkedListTypeSupported<int>               { enum { value = true }; };
47 
48 template<>
49 struct IsLinkedListTypeSupported<unsigned int>      { enum { value = true }; };
50 
51 #ifndef __LP64__ // u/long on linux64 platform is 64-bit type and collides with U/INT64
52 template<>
53 struct IsLinkedListTypeSupported<long>              { enum { value = true }; };
54 
55 template<>
56 struct IsLinkedListTypeSupported<unsigned long>     { enum { value = true }; };
57 #endif
58 
59 template<>
60 struct IsLinkedListTypeSupported<float>             { enum { value = true }; };
61 
62 template<>
63 struct IsLinkedListTypeSupported<INT64>             { enum { value = true }; };
64 
65 template<>
66 struct IsLinkedListTypeSupported<UINT64>            { enum { value = true }; };
67 
68 template<typename T>
69 struct IsLinkedListTypeSupported<T*>                { enum { value = true }; };
70 
71 /*****************************************************************************\
72 Struct: AreLinkedListDuplicatesSupported
73 \*****************************************************************************/
74 template<typename T>
75 struct AreLinkedListDuplicatesSupported         { enum { value = true }; };
76 
77 template<typename T>
78 struct AreLinkedListDuplicatesSupported<T*>     { enum { value = false }; };
79 
80 template<typename T>
81 struct AreLinkedListDuplicatesSupported<T&>     { enum { value = false }; };
82 
83 /*****************************************************************************\
84 Template Parameters
85 \*****************************************************************************/
86 #define LinkedListTemplateList  class Type, class CAllocatorType
87 #define CLinkedListType         CLinkedList<Type,CAllocatorType>
88 
89 /*****************************************************************************\
90 
91 Class:
92     CLinkedList
93 
94 Description:
95     Implements a pointer-based linked-list
96 
97 \*****************************************************************************/
98 template<LinkedListTemplateList>
99 class CLinkedList : public CObject<CAllocatorType>
100 {
101 protected:
102 
103     class CNode : public CObject<CAllocatorType>
104     {
105     public:
106 
107         CNode( void );
108         CNode( const Type &element );
109         virtual ~CNode( void );
110 
111         void    Insert( CNode* pNext );
112         void    Remove( void );
113 
114         void        SetElement( const Type &element );
115         Type&       GetElement( void );
116         const Type& GetElement( void ) const;
117 
118         void    SetPrevious( CNode* pNode );
119         void    SetNext( CNode* pNode );
120 
121         CNode*  GetPrevious( void ) const;
122         CNode*  GetNext( void ) const;
123 
124     protected:
125 
126         Type    m_Element;
127         CNode*  m_Next;
128         CNode*  m_Previous;
129     };
130 
131 public:
132 
133     CLinkedList( void );
134     virtual ~CLinkedList( void );
135 
136     class CIterator
137     {
138     public:
139 
140         CIterator( void );
141         CIterator( CNode* ptr );
142         CIterator( const CIterator &iterator );
143 
144         CIterator&  operator--( void );
145         CIterator&  operator++( void );
146 
147         bool operator==( const CIterator &iterator ) const;
148         bool operator!=( const CIterator &iterator ) const;
149 
150         CIterator &operator=( const CIterator &iterator );
151         Type&   operator*( void );
152 
153         bool    IsNull( void ) const;
154         void    SetNull( void );
155 
156         friend class CLinkedList;
157         friend class CConstIterator;
158 
159     protected:
160 
161         CNode*  m_Ptr;
162     };
163 
164     class CConstIterator
165     {
166     public:
167 
168         CConstIterator( void );
169         CConstIterator( const CIterator &iterator );
170         CConstIterator( const CNode* ptr );
171 
172         CConstIterator& operator--( void );
173         CConstIterator& operator++( void );
174 
175         bool operator==( const CConstIterator &iterator ) const;
176         bool operator!=( const CConstIterator &iterator ) const;
177 
178         const Type& operator*( void );
179 
180         bool    IsNull( void ) const;
181         void    SetNull( void );
182 
183         friend class CLinkedList;
184 
185     protected:
186 
187         const CNode*    m_Ptr;
188     };
189 
190     bool    IsEmpty( void ) const;
191     DWORD   GetCount( void ) const;
192 
193     CLinkedListType& operator= ( const CLinkedListType &llist );
194 
195     CIterator   Begin( void );
196     CIterator   Get( const DWORD index );
197     CIterator   End( void );
198 
199     CConstIterator  Begin( void ) const;
200     CConstIterator  Get( const DWORD index ) const;
201     CConstIterator  End( void ) const;
202 
203     CIterator Find( const Type &element );
204     CConstIterator Find( const Type &element ) const;
205 
206     bool    Add( const Type &element );
207     bool    Remove( const Type &element );
208 
209     bool    Add( const CIterator &location, const Type &element );
210     bool    Remove( const CIterator &location );
211 
212     void    Clear( void );
213 
214     void    Splice(
215                 const CIterator &dstLocation,
216                 const CIterator &srcLocation,
217                 CLinkedListType &srcList );
218 
219     void    SpliceListPartAtTheEnd(
220                 CLinkedListType &srcList,
221                 const CIterator &srcStartLocation,
222                 const CIterator &srcEndLocation );
223 
224     void    Set( const CIterator &location, const Type &element );
225 
226     void    DeleteFreePool( void );
227 
228     void    DebugPrint( void ) const;
229 
230     C_ASSERT( IsLinkedListTypeSupported<Type>::value == true );
231 
232 protected:
233 
234     bool    Remove( CNode* &pNode );
235 
236     CNode*  CreateNode( const Type &element );
237     void    DeleteNode( CNode* &pNode );
238 
239     CNode   m_DummyTail;
240     DWORD   m_Count;
241 
242     CNode   m_FreePoolDummyTail;
243     DWORD   m_FreePoolCount;
244 
245     DECL_DEBUG_MUTEX( m_InstanceNotThreadSafe )
246 };
247 
248 /*****************************************************************************\
249 
250 Function:
251     CNode Constructor
252 
253 Description:
254     Initializes internal data
255 
256 Input:
257     none
258 
259 Output:
260     none
261 
262 \*****************************************************************************/
263 template<LinkedListTemplateList>
264 CLinkedListType::CNode::CNode( void )
265     : CObject<CAllocatorType>()
266 {
267     SafeMemSet( &m_Element, 0, sizeof(Type) );
268 
269     m_Next = this;
270     m_Previous = this;
271 }
272 
273 /*****************************************************************************\
274 
275 Function:
276     CNode Constructor
277 
278 Description:
279     Initializes internal data
280 
281 Input:
282     none
283 
284 Output:
285     none
286 
287 \*****************************************************************************/
288 template<LinkedListTemplateList>
289 CLinkedListType::CNode::CNode( const Type &element )
290     : CObject<CAllocatorType>()
291 {
292     m_Element = element;
293     m_Next = this;
294     m_Previous = this;
295 }
296 
297 /*****************************************************************************\
298 
299 Function:
300     CNode Destructor
301 
302 Description:
303     Deletes internal data
304 
305 Input:
306     none
307 
308 Output:
309     none
310 
311 \*****************************************************************************/
312 template<LinkedListTemplateList>
313 CLinkedListType::CNode::~CNode( void )
314 {
315     ASSERT( m_Next == this );
316     ASSERT( m_Previous == this );
317 }
318 
319 /*****************************************************************************\
320 
321 Function:
322     CNode::Insert
323 
324 Description:
325     Inserts the node before the given node
326 
327 Input:
328     const CNode* pNext
329 
330 Output:
331     none
332 
333 \*****************************************************************************/
334 template<LinkedListTemplateList>
335 void CLinkedListType::CNode::Insert( CNode* pNext )
336 {
337     m_Next = pNext;
338     m_Previous = m_Next->m_Previous;
339 
340     m_Previous->m_Next = this;
341     m_Next->m_Previous = this;
342 }
343 
344 /*****************************************************************************\
345 
346 Function:
347     CNode::Remove
348 
349 Description:
350     Removes the node from the linked list
351 
352 Input:
353     none
354 
355 Output:
356     none
357 
358 \*****************************************************************************/
359 template<LinkedListTemplateList>
360 void CLinkedListType::CNode::Remove( void )
361 {
362     m_Previous->m_Next = m_Next;
363     m_Next->m_Previous = m_Previous;
364 
365     m_Previous = this;
366     m_Next = this;
367 
368     SafeMemSet( &m_Element, 0, sizeof(Type) );
369 }
370 
371 /*****************************************************************************\
372 
373 Function:
374     CNode::SetElement
375 
376 Description:
377     Sets the element of the node from the linked list
378 
379 Input:
380     const Type &element
381 
382 Output:
383     none
384 
385 \*****************************************************************************/
386 template<LinkedListTemplateList>
387 void CLinkedListType::CNode::SetElement( const Type &element )
388 {
389     m_Element = element;
390 }
391 
392 /*****************************************************************************\
393 
394 Function:
395     CNode::GetElement
396 
397 Description:
398     Gets the element of the node from the linked list
399 
400 Input:
401     none
402 
403 Output:
404     Type&
405 
406 \*****************************************************************************/
407 template<LinkedListTemplateList>
408 Type& CLinkedListType::CNode::GetElement( void )
409 {
410     return m_Element;
411 }
412 
413 /*****************************************************************************\
414 
415 Function:
416     CNode::GetElement
417 
418 Description:
419     Gets the element of the node from the linked list
420 
421 Input:
422     none
423 
424 Output:
425     const Type&
426 
427 \*****************************************************************************/
428 template<LinkedListTemplateList>
429 const Type& CLinkedListType::CNode::GetElement( void ) const
430 {
431     return m_Element;
432 }
433 
434 /*****************************************************************************\
435 
436 Function:
437     CNode::SetPrevious
438 
439 Description:
440     Sets the previous pointer of the node from the linked list
441 
442 Input:
443     CNode* pNode
444 
445 Output:
446     none
447 
448 \*****************************************************************************/
449 template<LinkedListTemplateList>
450 void CLinkedListType::CNode::SetPrevious( CNode* pNode )
451 {
452     m_Previous = pNode;
453 }
454 
455 /*****************************************************************************\
456 
457 Function:
458     CNode::SetNext
459 
460 Description:
461     Sets the next pointer of the node from the linked list
462 
463 Input:
464     CNode* pNode
465 
466 Output:
467     none
468 
469 \*****************************************************************************/
470 template<LinkedListTemplateList>
471 void CLinkedListType::CNode::SetNext( CNode* pNode )
472 {
473     m_Next = pNode;
474 }
475 
476 /*****************************************************************************\
477 
478 Function:
479     CNode::GetPrevious
480 
481 Description:
482     Gets the previous pointer of the node from the linked list
483 
484 Input:
485     none
486 
487 Output:
488     CNode*
489 
490 \*****************************************************************************/
491 template<LinkedListTemplateList>
492 typename CLinkedListType::CNode* CLinkedListType::CNode::GetPrevious( void ) const
493 {
494     return m_Previous;
495 }
496 
497 /*****************************************************************************\
498 
499 Function:
500     CNode::GetNext
501 
502 Description:
503     Gets the next pointer of the node from the linked list
504 
505 Input:
506     none
507 
508 Output:
509     CNode*
510 
511 \*****************************************************************************/
512 template<LinkedListTemplateList>
513 typename CLinkedListType::CNode* CLinkedListType::CNode::GetNext( void ) const
514 {
515     return m_Next;
516 }
517 
518 /*****************************************************************************\
519 
520 Function:
521     CLinkedList Constructor
522 
523 Description:
524     Initializes internal data
525 
526 Input:
527     none
528 
529 Output:
530     none
531 
532 \*****************************************************************************/
533 template<LinkedListTemplateList>
534 CLinkedListType::CLinkedList( void )
535     : CObject<CAllocatorType>()
536 {
537     m_Count = 0;
538     m_FreePoolCount = 0;
539     m_DummyTail.SetNext( &m_DummyTail );
540     m_DummyTail.SetPrevious( &m_DummyTail );
541 
542     INIT_DEBUG_MUTEX( m_InstanceNotThreadSafe );
543 }
544 
545 /*****************************************************************************\
546 
547 Function:
548     CLinkedList Destructor
549 
550 Description:
551     Deletes internal data
552 
553 Input:
554     none
555 
556 Output:
557     none
558 
559 \*****************************************************************************/
560 template<LinkedListTemplateList>
561 CLinkedListType::~CLinkedList( void )
562 {
563     ASSERT( IsEmpty() );
564 
565     // Delete all objects on the linked-list
566     Clear();
567 
568     DeleteFreePool();
569 
570     DELETE_DEBUG_MUTEX( m_InstanceNotThreadSafe );
571 }
572 
573 /*****************************************************************************\
574 
575 Function:
576     Default CLinkedList::CIterator Constructor
577 
578 Description:
579     Creates a NULL CIterator.
580 
581 Input:
582     none
583 
584 Output:
585     none
586 
587 \*****************************************************************************/
588 template<LinkedListTemplateList>
589 CLinkedListType::CIterator::CIterator( void )
590 {
591     m_Ptr = NULL;
592 }
593 
594 /*****************************************************************************\
595 
596 Function:
597     CLinkedList::CIterator Constructor
598 
599 Description:
600     Constructs a CIterator to the specified linked list node pointer.
601 
602 Input:
603     CNode* - pointer to create an iterator to.
604 
605 Output:
606     none
607 
608 \*****************************************************************************/
609 template<LinkedListTemplateList>
610 CLinkedListType::CIterator::CIterator( CNode* ptr )
611 {
612     ASSERT( ptr );
613     m_Ptr = ptr;
614 }
615 
616 /*****************************************************************************\
617 
618 Function:
619     CLinkedList::CIterator Copying Constructor
620 
621 Description:
622     Constructs a CIterator being copy of other iterator.
623 
624 Input:
625     const CIterator & - reference to iterator to copy from.
626 
627 Output:
628     none
629 
630 \*****************************************************************************/
631 template<LinkedListTemplateList>
632 CLinkedListType::CIterator::CIterator( const CIterator &iterator )
633 {
634     m_Ptr = iterator.m_Ptr;
635 }
636 
637 
638 /*****************************************************************************\
639 
640 Function:
641     CLinkedList::CIterator::operator--
642 
643 Description:
644     Iterates backwards through the linked list via predecrement.
645 
646 Input:
647     none
648 
649 Output:
650     CLinkedList CIterator& - iterator to the previous node in the list.
651 
652 \*****************************************************************************/
653 template<LinkedListTemplateList>
654 typename CLinkedListType::CIterator&
655 CLinkedListType::CIterator::operator--( void )
656 {
657     m_Ptr = m_Ptr->GetPrevious();
658     ASSERT( m_Ptr );
659     return *this;
660 }
661 
662 /*****************************************************************************\
663 
664 Function:
665     CLinkedList::CIterator::operator++
666 
667 Description:
668     Iterates forwards through the linked list via preincrement.
669 
670 Input:
671     none
672 
673 Output:
674     CLinkedList CIterator& - iterator to the next node in the list.
675 
676 \*****************************************************************************/
677 template<LinkedListTemplateList>
678 typename CLinkedListType::CIterator&
679 CLinkedListType::CIterator::operator++( void )
680 {
681     m_Ptr = m_Ptr->GetNext();
682     ASSERT( m_Ptr );
683     return *this;
684 }
685 
686 /*****************************************************************************\
687 
688 Function:
689     CLinkedList::CIterator::operator==
690 
691 Description:
692 
693 Input:
694     const CIterator& - pointer to the iterator to compare to.
695 
696 Output:
697     bool - true if this iterator and the passed-in iterator point to the same
698            linked list node.
699 
700 \*****************************************************************************/
701 template<LinkedListTemplateList>
702 bool CLinkedListType::CIterator::operator==(
703     const CIterator& iterator ) const
704 {
705     return m_Ptr == iterator.m_Ptr;
706 }
707 
708 /*****************************************************************************\
709 
710 Function:
711     CLinkedList::CIterator::operator!=
712 
713 Description:
714 
715 Input:
716     const CIterator& - pointer to the iterator to compare to.
717 
718 Output:
719     bool - true if this iterator and the passed-in iterator point to different
720            linked list nodes.
721 
722 \*****************************************************************************/
723 template<LinkedListTemplateList>
724 bool CLinkedListType::CIterator::operator!=(
725     const CIterator& iterator ) const
726 {
727     return m_Ptr != iterator.m_Ptr;
728 }
729 
730 /*****************************************************************************\
731 
732 Function:
733     CLinkedList::CIterator::operator=
734 
735 Description:
736 
737 Input:
738     const CIterator& - reference to the iterator to copy from.
739 
740 Output:
741     const CIterator & - reference to self
742 
743 \*****************************************************************************/
744 template<LinkedListTemplateList>
745 typename CLinkedListType::CIterator &CLinkedListType::CIterator::operator=(
746     const CIterator &iterator )
747 {
748     m_Ptr = iterator.m_Ptr;
749     return *this;
750 }
751 /*****************************************************************************\
752 
753 Function:
754     CLinkedList::CIterator::operator*
755 
756 Description:
757     Returns a reference to the item that this iterator points to.
758 
759 Input:
760     none
761 
762 Output:
763     Type& - reference to the item that this iterator points to.
764 
765 \*****************************************************************************/
766 template<LinkedListTemplateList>
767 Type& CLinkedListType::CIterator::operator*( void )
768 {
769     return m_Ptr->GetElement();
770 }
771 
772 /*****************************************************************************\
773 
774 Function:
775     CLinkedList::CIterator::IsNull
776 
777 Description:
778     Determines if the iterator has been assigned
779 
780 Input:
781     none
782 
783 Output:
784     bool
785 
786 \*****************************************************************************/
787 template<LinkedListTemplateList>
788 bool CLinkedListType::CIterator::IsNull( void ) const
789 {
790     return ( m_Ptr == NULL );
791 }
792 
793 /*****************************************************************************\
794 
795 Function:
796     CLinkedList::CIterator::SetNull
797 
798 Description:
799     Sets the iterator pointer to null
800 
801 Input:
802     none
803 
804 Output:
805     none
806 
807 \*****************************************************************************/
808 template<LinkedListTemplateList>
809 void CLinkedListType::CIterator::SetNull( void )
810 {
811     m_Ptr = NULL;
812 }
813 
814 /*****************************************************************************\
815 
816 Function:
817     Default CLinkedList::CConstIterator Constructor
818 
819 Description:
820     Creates a NULL CConstIterator.
821 
822 Input:
823     none
824 
825 Output:
826     none
827 
828 \*****************************************************************************/
829 template<LinkedListTemplateList>
830 CLinkedListType::CConstIterator::CConstIterator( void )
831 {
832     m_Ptr = NULL;
833 }
834 
835 /*****************************************************************************\
836 
837 Function:
838     CLinkedList::CConstIterator Constructor
839 
840 Description:
841     Constructs a CConstIterator to the specified const linked list node pointer.
842 
843 Input:
844     const CNode* - pointer to create an iterator to.
845 
846 Output:
847     none
848 
849 \*****************************************************************************/
850 template<LinkedListTemplateList>
851 CLinkedListType::CConstIterator::CConstIterator( const CNode* ptr )
852 {
853     ASSERT( ptr );
854     m_Ptr = ptr;
855 }
856 
857 /*****************************************************************************\
858 
859 Function:
860     CLinkedList::CConstIterator Constructor
861 
862 Description:
863     Constructs a CConstIterator from a CIterator.
864 
865 Input:
866     const CIterator& - CIterator to convert to a CConstIterator.
867 
868 Output:
869     none
870 
871 \*****************************************************************************/
872 template<LinkedListTemplateList>
873 CLinkedListType::CConstIterator::CConstIterator( const CIterator& iterator )
874 {
875     ASSERT( iterator.m_Ptr );
876     m_Ptr = iterator.m_Ptr;
877 }
878 
879 /*****************************************************************************\
880 
881 Function:
882     CLinkedList::CConstIterator::operator--
883 
884 Description:
885     Iterates backwards through the linked list via predecrement.
886 
887 Input:
888     none
889 
890 Output:
891     CLinkedList CConstIterator& - iterator to the previous node in the list.
892 
893 \*****************************************************************************/
894 template<LinkedListTemplateList>
895 typename CLinkedListType::CConstIterator&
896 CLinkedListType::CConstIterator::operator--( void )
897 {
898     m_Ptr = m_Ptr->GetPrevious();
899     ASSERT( m_Ptr );
900     return *this;
901 }
902 
903 /*****************************************************************************\
904 
905 Function:
906     CLinkedList::CConstIterator::operator++
907 
908 Description:
909     Iterates forwards through the linked list via preincrement.
910 
911 Input:
912     none
913 
914 Output:
915     CLinkedList CConstIterator& - iterator to the next node in the list.
916 
917 \*****************************************************************************/
918 template<LinkedListTemplateList>
919 typename CLinkedListType::CConstIterator&
920 CLinkedListType::CConstIterator::operator++( void )
921 {
922     m_Ptr = m_Ptr->GetNext();
923     ASSERT( m_Ptr );
924     return *this;
925 }
926 
927 /*****************************************************************************\
928 
929 Function:
930     CLinkedList::CConstIterator::operator==
931 
932 Description:
933 
934 Input:
935     const CConstIterator& - pointer to the iterator to compare to.
936 
937 Output:
938     bool - true if this iterator and the passed-in iterator point to the same
939            linked list node.
940 
941 \*****************************************************************************/
942 template<LinkedListTemplateList>
943 bool CLinkedListType::CConstIterator::operator==(
944     const CConstIterator& iterator ) const
945 {
946     return m_Ptr == iterator.m_Ptr;
947 }
948 
949 /*****************************************************************************\
950 
951 Function:
952     CLinkedList::CConstIterator::operator!=
953 
954 Description:
955 
956 Input:
957     const CConstIterator& - pointer to the iterator to compare to.
958 
959 Output:
960     bool - true if this iterator and the passed-in iterator point to different
961            linked list nodes.
962 
963 \*****************************************************************************/
964 template<LinkedListTemplateList>
965 bool CLinkedListType::CConstIterator::operator!=(
966     const CConstIterator& o ) const
967 {
968     return m_Ptr != o.m_Ptr;
969 }
970 
971 /*****************************************************************************\
972 
973 Function:
974     CLinkedList::CConstIterator::operator*
975 
976 Description:
977     Returns a const reference to the item that this iterator points to.
978 
979 Input:
980     none
981 
982 Output:
983     const Type& - reference to the item that this iterator points to.
984 
985 \*****************************************************************************/
986 template<LinkedListTemplateList>
987 const Type& CLinkedListType::CConstIterator::operator*( void )
988 {
989     return m_Ptr->GetElement();
990 }
991 
992 /*****************************************************************************\
993 
994 Function:
995     CLinkedList::CConstIterator::IsNull
996 
997 Description:
998     Determines if the iterator has been assigned
999 
1000 Input:
1001     none
1002 
1003 Output:
1004     bool
1005 
1006 \*****************************************************************************/
1007 template<LinkedListTemplateList>
1008 bool CLinkedListType::CConstIterator::IsNull( void ) const
1009 {
1010     return ( m_Ptr == NULL );
1011 }
1012 
1013 /*****************************************************************************\
1014 
1015 Function:
1016     CLinkedList::CConstIterator::SetNull
1017 
1018 Description:
1019     Sets the iterator pointer to null
1020 
1021 Input:
1022     none
1023 
1024 Output:
1025     none
1026 
1027 \*****************************************************************************/
1028 template<LinkedListTemplateList>
1029 void CLinkedListType::CConstIterator::SetNull( void )
1030 {
1031     m_Ptr = NULL;
1032 }
1033 
1034 /*****************************************************************************\
1035 
1036 Function:
1037     CLinkedList::IsEmpty
1038 
1039 Description:
1040     Returns if the linked-list is empty
1041 
1042 Input:
1043     none
1044 
1045 Output:
1046     bool - true or false
1047 
1048 \*****************************************************************************/
1049 template<LinkedListTemplateList>
1050 bool CLinkedListType::IsEmpty( void ) const
1051 {
1052     return ( m_DummyTail.GetNext() == &m_DummyTail );
1053 }
1054 
1055 /*****************************************************************************\
1056 
1057 Function:
1058     CLinkedList::GetCount
1059 
1060 Description:
1061     Returns the number of elements in the linked-list
1062 
1063 Input:
1064     none
1065 
1066 Output:
1067     DWORD - number of elements
1068 
1069 \*****************************************************************************/
1070 template<LinkedListTemplateList>
1071 DWORD CLinkedListType::GetCount( void ) const
1072 {
1073     return m_Count;
1074 }
1075 
1076 /*****************************************************************************\
1077 
1078 Function:
1079     CLinkedList::operator=
1080 
1081 Description:
1082     Copies a linked-list to this linked-list
1083 
1084 Input:
1085     CLinkedListType &llist - linked-list to copy
1086 
1087 Output:
1088     CLinkedListType& - *this
1089 
1090 \*****************************************************************************/
1091 template<LinkedListTemplateList>
1092 CLinkedListType& CLinkedListType::operator= ( const CLinkedListType &llist )
1093 {
1094     // Copy from back-to-front so we wind up with the same order of elements
1095     const CNode* pDummyTail = &llist.m_DummyTail;
1096     const CNode* pNode = pDummyTail->GetPrevious();
1097 
1098     while( pNode != pDummyTail )
1099     {
1100         Add( pNode->GetElement() );
1101         pNode = pNode->GetPrevious();
1102     }
1103 
1104     return *this;
1105 }
1106 
1107 /*****************************************************************************\
1108 
1109 Function:
1110     CLinkedList::Begin
1111 
1112 Description:
1113     Returns an iterator to the first node in the linked list.
1114 
1115 Input:
1116     none
1117 
1118 Output:
1119     CLinkedListType::CIterator
1120 
1121 \*****************************************************************************/
1122 template<LinkedListTemplateList>
1123 typename CLinkedListType::CIterator
1124 CLinkedListType::Begin( void )
1125 {
1126     return CIterator( m_DummyTail.GetNext() );
1127 }
1128 
1129 /*****************************************************************************\
1130 
1131 Function:
1132     CLinkedList::Get
1133 
1134 Description:
1135     Returns an iterator to the nth node in the linked list.
1136 
1137 Input:
1138     const DWORD index - index of node requesting
1139 
1140 Output:
1141     CLinkedListType::CIterator
1142 
1143 \*****************************************************************************/
1144 template<LinkedListTemplateList>
1145 typename CLinkedListType::CIterator
1146 CLinkedListType::Get( const DWORD index )
1147 {
1148     ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1149 
1150     CIterator iterator;
1151 
1152     if( index <= ( m_Count - 1 ) )
1153     {
1154         if( index <= ( m_Count / 2 ) )
1155         {
1156             iterator = Begin();
1157 
1158             for( DWORD i = 0; i < index; i++ )
1159             {
1160                 ++iterator;
1161             }
1162         }
1163         else
1164         {
1165             iterator = End();
1166 
1167             for( DWORD i = m_Count; i > index; i-- )
1168             {
1169                 --iterator;
1170             }
1171         }
1172     }
1173     else
1174     {
1175         iterator = End();
1176     }
1177 
1178     RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1179     return iterator;
1180 }
1181 
1182 /*****************************************************************************\
1183 
1184 Function:
1185     CLinkedList::End
1186 
1187 Description:
1188     Returns an iterator to the last (dummy) node in the linked list.
1189 
1190 Input:
1191     none
1192 
1193 Output:
1194     CLinkedListType::CIterator
1195 
1196 \*****************************************************************************/
1197 template<LinkedListTemplateList>
1198 typename CLinkedListType::CIterator
1199 CLinkedListType::End( void )
1200 {
1201     return CIterator( &m_DummyTail );
1202 }
1203 
1204 /*****************************************************************************\
1205 
1206 Function:
1207     CLinkedList::Begin
1208 
1209 Description:
1210     Returns a const iterator to the first node in the linked list.
1211 
1212 Input:
1213     none
1214 
1215 Output:
1216     CLinkedListType::CConstIterator
1217 
1218 \*****************************************************************************/
1219 template<LinkedListTemplateList>
1220 typename CLinkedListType::CConstIterator
1221 CLinkedListType::Begin( void ) const
1222 {
1223     return CConstIterator( m_DummyTail.GetNext() );
1224 }
1225 
1226 /*****************************************************************************\
1227 
1228 Function:
1229     CLinkedList::Get
1230 
1231 Description:
1232     Returns a const iterator to the nth node in the linked list.
1233 
1234 Input:
1235     const DWORD index - index of node requesting
1236 
1237 Output:
1238     CLinkedListType::CConstIterator
1239 
1240 \*****************************************************************************/
1241 template<LinkedListTemplateList>
1242 typename CLinkedListType::CConstIterator
1243 CLinkedListType::Get( const DWORD index ) const
1244 {
1245     ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1246 
1247     CConstIterator iterator;
1248 
1249     if( index <= ( m_Count - 1 ) )
1250     {
1251         if( index <= ( m_Count / 2 ) )
1252         {
1253             iterator = Begin();
1254 
1255             for( DWORD i = 0; i < index; i++ )
1256             {
1257                 ++iterator;
1258             }
1259         }
1260         else
1261         {
1262             iterator = End();
1263 
1264             for( DWORD i = m_Count; i > index; i-- )
1265             {
1266                 --iterator;
1267             }
1268         }
1269     }
1270     else
1271     {
1272         iterator = End();
1273     }
1274 
1275     RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1276     return iterator;
1277 }
1278 
1279 /*****************************************************************************\
1280 
1281 Function:
1282     CLinkedList::End
1283 
1284 Description:
1285     Returns a const iterator to the last (dummy) node in the linked list.
1286 
1287 Input:
1288     none
1289 
1290 Output:
1291     CLinkedListType::CConstIterator
1292 
1293 \*****************************************************************************/
1294 template<LinkedListTemplateList>
1295 typename CLinkedListType::CConstIterator
1296 CLinkedListType::End( void ) const
1297 {
1298     return CConstIterator( &m_DummyTail );
1299 }
1300 
1301 /*****************************************************************************\
1302 
1303 Function:
1304     CLinkedList::Find
1305 
1306 Description:
1307     Finds the first instance of the specified element in the linked-list
1308 
1309 Input:
1310     Type element - element to find
1311 
1312 Output:
1313     CIterator - iterator to the node containing the element
1314 
1315 \*****************************************************************************/
1316 template<LinkedListTemplateList>
1317 typename CLinkedListType::CIterator
1318 CLinkedListType::Find( const Type &element )
1319 {
1320     ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1321 
1322     CNode* pDummyTail = &m_DummyTail;
1323     CNode* pNode = m_DummyTail.GetNext();
1324 
1325     while( pNode != pDummyTail )
1326     {
1327         // If this node contains the element, then
1328         // return an iterator to this node
1329         if( pNode->GetElement() == element )
1330         {
1331             RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1332             return CIterator( pNode );
1333         }
1334 
1335         // Get the next node
1336         pNode = pNode->GetNext();
1337     }
1338 
1339     // Node not found
1340     RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1341     return End();
1342 }
1343 
1344 /*****************************************************************************\
1345 
1346 Function:
1347     CLinkedList::Find
1348 
1349 Description:
1350     Finds the first instance of the specified element in the linked-list
1351 
1352 Input:
1353     Type element - element to find
1354 
1355 Output:
1356     CConstIterator - iterator to the node containing the element
1357 
1358 \*****************************************************************************/
1359 template<LinkedListTemplateList>
1360 typename CLinkedListType::CConstIterator
1361 CLinkedListType::Find( const Type &element ) const
1362 {
1363     ACQUIRE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1364 
1365     const CNode* pDummyTail = &m_DummyTail;
1366     const CNode* pNode = m_DummyTail.GetNext();
1367 
1368     while( pNode != pDummyTail )
1369     {
1370         // If this node contains the element, then
1371         // return an iterator to this node
1372         if( pNode->GetElement() == element )
1373         {
1374             RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1375             return CConstIterator( pNode );
1376         }
1377 
1378         // Get the next node
1379         pNode = pNode->GetNext();
1380     }
1381 
1382     // Node not found
1383     RELEASE_DEBUG_MUTEX_READ( m_InstanceNotThreadSafe );
1384     return End();
1385 }
1386 
1387 /*****************************************************************************\
1388 
1389 Function:
1390     CLinkedList::Add
1391 
1392 Description:
1393     Adds the specified element to the beginning of the linked-list
1394 
1395 Input:
1396     const Type& element - element to add to the linked-list
1397 
1398 Output:
1399     bool - SUCCESS or FAIL
1400 
1401 \*****************************************************************************/
1402 template<LinkedListTemplateList>
1403 bool CLinkedListType::Add( const Type &element )
1404 {
1405     const bool success = Add( Begin(), element );
1406     return success;
1407 }
1408 
1409 /*****************************************************************************\
1410 
1411 Function:
1412     CLinkedList::Remove
1413 
1414 Description:
1415     Removes the first instance of the specified element from the linked-list
1416 
1417 Input:
1418     Type element - element to remove
1419 
1420 Output:
1421     bool - SUCCESS or FAIL
1422 
1423 \*****************************************************************************/
1424 template<LinkedListTemplateList>
1425 bool CLinkedListType::Remove( const Type &element )
1426 {
1427     // Find the specified element in the list
1428     CIterator iterator = Find( element );
1429     const bool success = Remove( iterator );
1430     return success;
1431 }
1432 
1433 /*****************************************************************************\
1434 
1435 Function:
1436     CLinkedList::Add
1437 
1438 Description:
1439     Adds the specified element to the linked-list at the location specified by
1440     the passed-in iterator.  The item is added before the passed-in iterator.
1441 
1442 Input:
1443     const CIterator& location - place in the list to add the element
1444     const Type& element - element to add to the linked-list
1445 
1446 Output:
1447     bool - SUCCESS or FAIL
1448 
1449 \*****************************************************************************/
1450 template<LinkedListTemplateList>
1451 bool CLinkedListType::Add(
1452     const CIterator &location,
1453     const Type &element )
1454 {
1455     // If necessary, make sure we do not add an element twice
1456     ASSERT( ( AreLinkedListDuplicatesSupported<Type>::value == true ) ||
1457             ( Find( element ) == End() ) );
1458 
1459     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1460 
1461     bool success = false;
1462 
1463     // Create a new object for the element
1464     CNode* pNode = CreateNode( element );
1465 
1466     if( pNode )
1467     {
1468         pNode->Insert( location.m_Ptr );
1469 
1470         m_Count++;
1471 
1472         // Element successfully added
1473         success = true;
1474     }
1475     else
1476     {
1477         ASSERT( 0 );
1478 
1479         // Element not added
1480         success = false;
1481     }
1482 
1483     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1484     return success;
1485 }
1486 
1487 /*****************************************************************************\
1488 
1489 Function:
1490     CLinkedList::Remove
1491 
1492 Description:
1493     Removes the node specified by the passed-in iterator.
1494 
1495 Input:
1496     const CIterator& - location to remove
1497 
1498 Output:
1499     bool - SUCCESS or FAIL
1500 
1501 \*****************************************************************************/
1502 template<LinkedListTemplateList>
1503 bool CLinkedListType::Remove(
1504     const CIterator &location )
1505 {
1506     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1507 
1508     bool success = false;
1509 
1510     if( location == End() )
1511     {
1512         // Element not removed
1513         success = false;
1514     }
1515     else
1516     {
1517         CNode* pNode = location.m_Ptr;
1518 
1519         success = Remove( pNode );
1520     }
1521 
1522     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1523     return success;
1524 }
1525 
1526 /*****************************************************************************\
1527 
1528 Function:
1529     CLinkedList::Clear
1530 
1531 Description:
1532     clears the list
1533 
1534 Input:
1535     none
1536 
1537 Output:
1538     none
1539 
1540 \*****************************************************************************/
1541 template<LinkedListTemplateList>
1542 void CLinkedListType::Clear( void )
1543 {
1544     // Delete all objects on the linked-list
1545     while( !IsEmpty() )
1546     {
1547         Remove( Begin() );
1548     }
1549 }
1550 
1551 /*****************************************************************************\
1552 
1553 Function:
1554     CLinkedList::Splice
1555 
1556 Description:
1557     Splices some or all of a source list into this list.  Upon return the
1558     source list will be smaller than it was before (assuming the source
1559     iterator is not the list end).
1560 
1561     This would be a constant time operation, but we need to maintain the
1562     list of counts in each list.  As such, it is a linear time operation,
1563     albeit a fast linear operation.
1564 
1565 Input:
1566     const CIterator& dstLocation - location to put the source list's nodes;
1567                                    the source lists's nodes will be spliced
1568                                    before this node
1569     const CIterator& srcLocation - the first node in the source list that will
1570                                    be spliced into this list
1571     CLinkedListType& srcList - source list to splice into this list
1572 
1573 Output:
1574     none
1575 
1576 \*****************************************************************************/
1577 template<LinkedListTemplateList>
1578 void CLinkedListType::Splice(
1579     const CIterator &dstLocation,
1580     const CIterator &srcLocation,
1581     CLinkedListType &srcList )
1582 {
1583     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1584 
1585     if( this != &srcList )
1586     {
1587         if( !srcList.IsEmpty() )
1588         {
1589             // Figure out how many nodes we're going to splice.
1590             CIterator countIterator = srcLocation;
1591             DWORD   count = 0;
1592             while( countIterator != srcList.End() )
1593             {
1594                 count++;
1595                 ++countIterator;
1596             }
1597 
1598             // Update the counts.
1599 
1600             m_Count += count;
1601             srcList.m_Count -= count;
1602 
1603             // Actually do the splicing.
1604 
1605             CNode* pDstNode = dstLocation.m_Ptr;
1606 
1607             CNode* pSrcStartNode = srcLocation.m_Ptr;
1608             CNode* pSrcEndNode = srcList.m_DummyTail.GetPrevious();
1609 
1610             pSrcStartNode->GetPrevious()->SetNext( &srcList.m_DummyTail );
1611             srcList.m_DummyTail.SetPrevious( pSrcStartNode->GetPrevious() );
1612 
1613             pDstNode->GetPrevious()->SetNext( pSrcStartNode );
1614             pSrcStartNode->SetPrevious( pDstNode->GetPrevious() );
1615 
1616             pSrcEndNode->SetNext( pDstNode );
1617             pDstNode->SetPrevious( pSrcEndNode );
1618         }
1619     }
1620 
1621     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1622 }
1623 
1624 /*****************************************************************************\
1625 
1626 Function:
1627     CLinkedList::SpliceListPartAtTheEnd
1628 
1629 Description:
1630     Splices some or all (interval) of a source list at the end of
1631     this list.
1632 
1633     Upon return the source list will be smaller than it was before
1634     (assuming the source iterator is not the list end).
1635 
1636     This would be a constant time operation, but we need to maintain the
1637     list of counts in each list.  As such, it is a linear time operation,
1638     albeit a fast linear operation.
1639 
1640 Input:
1641     CLinkedListType& srcList - source list to splice into this list.
1642 
1643     const CIterator &srcStartLocation - the first node in the source list that will
1644         be spliced into this list.
1645 
1646     const CIterator &srcEndLocation - the first node AFTER the last
1647         in the source list that will be spliced into this list
1648         (this element will not be moved).
1649 
1650 
1651 Output:
1652     none
1653 
1654 \*****************************************************************************/
1655 template<LinkedListTemplateList>
1656 void CLinkedListType::SpliceListPartAtTheEnd(
1657     CLinkedListType &srcList,
1658     const CIterator &srcStartLocation,
1659     const CIterator &srcEndLocation )
1660 {
1661     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1662 
1663     if( this != &srcList )
1664     {
1665         if( !srcList.IsEmpty() &&
1666             ( srcStartLocation.m_Ptr != srcEndLocation.m_Ptr ) )
1667         {
1668             // Figure out how many nodes we're going to splice.
1669             CIterator countIterator = srcStartLocation;
1670             DWORD   count = 0;
1671             while( countIterator != srcEndLocation )
1672             {
1673                 count++;
1674                 ++countIterator;
1675             }
1676 
1677             // Update the counts.
1678 
1679             m_Count += count;
1680             srcList.m_Count -= count;
1681 
1682             // Actually do the splicing.
1683 
1684             // last before End.
1685             CNode* pDstNode = m_DummyTail.GetPrevious();
1686 
1687             CNode* pSrcStartNode = srcStartLocation.m_Ptr;
1688             CNode* pSrcEndNode = srcEndLocation.m_Ptr->GetPrevious();
1689 
1690             // Seal the gap after removed part
1691             pSrcStartNode->GetPrevious()->SetNext( srcEndLocation.m_Ptr );
1692             srcEndLocation.m_Ptr->SetPrevious( pSrcStartNode->GetPrevious() );
1693 
1694             // splice in.
1695             pDstNode->SetNext( pSrcStartNode );
1696             pSrcStartNode->SetPrevious( pDstNode );
1697 
1698             pSrcEndNode->SetNext( &m_DummyTail );
1699             m_DummyTail.SetPrevious( pSrcEndNode );
1700         }
1701     }
1702 
1703     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1704 }
1705 
1706 
1707 /*****************************************************************************\
1708 
1709 Function:
1710     CLinkedList::Set
1711 
1712 Description:
1713     Sets the contents of the node pointed to by location with element
1714     provided
1715 
1716 Input:
1717     const CIterator &location - location to set the element
1718     const Type &element - the element to set
1719 
1720 Output:
1721     bool
1722 
1723 \*****************************************************************************/
1724 template<LinkedListTemplateList>
1725 void CLinkedListType::Set(
1726     const CIterator &location,
1727     const Type &element )
1728 {
1729     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1730 
1731     if( location.m_Ptr )
1732     {
1733         location.m_Ptr->SetElement( element );
1734     }
1735 
1736     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1737 }
1738 
1739 /*****************************************************************************\
1740 
1741 Function:
1742     CLinkedList::DeleteFreePool
1743 
1744 Description:
1745     Deletes all memory on the free pool
1746 
1747 Input:
1748     none
1749 
1750 Output:
1751     none
1752 
1753 \*****************************************************************************/
1754 template<LinkedListTemplateList>
1755 void CLinkedListType::DeleteFreePool( void )
1756 {
1757     ACQUIRE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1758 
1759     // Delete all objects on the free pool list
1760     while( m_FreePoolDummyTail.GetNext() != &m_FreePoolDummyTail )
1761     {
1762         CNode* pNode = m_FreePoolDummyTail.GetNext();
1763         pNode->Remove();
1764         SafeDelete( pNode );
1765     }
1766 
1767     m_FreePoolCount = 0;
1768 
1769     RELEASE_DEBUG_MUTEX_WRITE( m_InstanceNotThreadSafe );
1770 }
1771 
1772 /*****************************************************************************\
1773 
1774 Function:
1775     CLinkedList::DebugPrint
1776 
1777 Description:
1778     Prints the linked-list to std output for debug only
1779 
1780 Input:
1781     none
1782 
1783 Output:
1784     none
1785 
1786 \*****************************************************************************/
1787 template<LinkedListTemplateList>
1788 void CLinkedListType::DebugPrint( void ) const
1789 {
1790 #ifdef _DEBUG
1791     DPF( GFXDBG_STDLIB, "%s\n", __FUNCTION__ );
1792     DPF( GFXDBG_STDLIB, "\tAddress = %p\n", this );
1793     DPF( GFXDBG_STDLIB, "\tType = %s\n", TYPEID_NAME(Type) );
1794 
1795     const CNode* pDummyTail = &m_DummyTail;
1796     CNode* pNode = m_DummyTail.GetNext();
1797 
1798     while( pNode != pDummyTail )
1799     {
1800         DWORD index = 0;
1801         DPF( GFXDBG_STDLIB, "\t\tLinkedListNode[%u] = 0x%08x\n",
1802             index,
1803             *(DWORD*)&pNode->GetElement() );
1804         index++;
1805 
1806         // Get the next node
1807         pNode = pNode->GetNext();
1808     }
1809 #endif
1810 }
1811 
1812 /*****************************************************************************\
1813 
1814 Function:
1815     CLinkedList::Remove
1816 
1817 Description:
1818     Removes the specified node from the linked-list
1819 
1820 Input:
1821     CNode* pNode - object to remove
1822 
1823 Output:
1824     none
1825 
1826 \*****************************************************************************/
1827 template<LinkedListTemplateList>
1828 bool CLinkedListType::Remove( CNode* &pNode )
1829 {
1830     bool success = false;
1831 
1832     if( pNode )
1833     {
1834         // Remove the node from the linked-list
1835         pNode->Remove();
1836 
1837         // Delete the node
1838         DeleteNode( pNode );
1839         m_Count--;
1840 
1841         success = true;
1842     }
1843 
1844     return success;
1845 }
1846 
1847 /*****************************************************************************\
1848 
1849 Function:
1850     CLinkedList::CreateNode
1851 
1852 Description:
1853     Creates a node
1854 
1855 Input:
1856     const Type &element
1857 
1858 Output:
1859     CNode*
1860 
1861 \*****************************************************************************/
1862 template<LinkedListTemplateList>
1863 typename CLinkedListType::CNode* CLinkedListType::CreateNode( const Type &element )
1864 {
1865     CNode* pNode = NULL;
1866 
1867     if( m_FreePoolDummyTail.GetNext() != &m_FreePoolDummyTail )
1868     {
1869         pNode = m_FreePoolDummyTail.GetNext();
1870         pNode->Remove();
1871         --m_FreePoolCount;
1872 
1873         pNode->SetElement( element );
1874     }
1875     else
1876     {
1877         pNode = new CNode( element );
1878     }
1879 
1880     return pNode;
1881 }
1882 
1883 /*****************************************************************************\
1884 
1885 Function:
1886     CLinkedList::DeleteNode
1887 
1888 Description:
1889     Deletes a node
1890 
1891 Input:
1892     CNode* pNode
1893 
1894 Output:
1895     none
1896 
1897 \*****************************************************************************/
1898 template<LinkedListTemplateList>
1899 void CLinkedListType::DeleteNode( CNode* &pNode )
1900 {
1901     const DWORD cMaxFreePoolCount = 32;
1902     if( m_FreePoolCount <= cMaxFreePoolCount )
1903     {
1904         pNode->Insert( m_FreePoolDummyTail.GetNext() );
1905         ++m_FreePoolCount;
1906     }
1907     else
1908     {
1909         SafeDelete( pNode );
1910     }
1911 }
1912 
1913 } // iSTD
1914