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