1 /************************************************************************* 2 * * 3 * Tokamak Physics Engine, Copyright (C) 2002-2007 David Lam. * 4 * All rights reserved. Email: david@tokamakphysics.com * 5 * Web: www.tokamakphysics.com * 6 * * 7 * This library is distributed in the hope that it will be useful, * 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the files * 10 * LICENSE.TXT for more details. * 11 * * 12 *************************************************************************/ 13 14 #ifndef CONTAINERS_H 15 #define CONTAINERS_H 16 17 #define _CRT_SECURE_DEPRECATE_MEMORY 18 #include <memory.h> 19 20 #define PLACEMENT_MAGIC \ 21 public:\ 22 NEINLINE void * operator new(size_t s,void * addr)\ 23 {\ 24 return addr;\ 25 }\ 26 NEINLINE void * operator new[] (size_t s,void * addr)\ 27 {\ 28 return addr;\ 29 }\ 30 NEINLINE void operator delete(void *)\ 31 {\ 32 }\ 33 NEINLINE void operator delete[](void *)\ 34 {\ 35 }\ 36 NEINLINE void operator delete(void *, void *)\ 37 {\ 38 }\ 39 NEINLINE void operator delete[](void *, void *)\ 40 {\ 41 } 42 43 template <class T, int initFixedSize = 1> class neSimpleArray 44 { 45 public: 46 PLACEMENT_MAGIC 47 IsFixedSize()48 NEINLINE bool IsFixedSize() 49 { 50 return (initFixedSize != 1); 51 } 52 neSimpleArray()53 NEINLINE neSimpleArray() 54 { 55 if (IsFixedSize()) 56 { 57 data = initArray; 58 nextFree = data; 59 size = initFixedSize; 60 alloc = NULL; 61 growBy = 0; 62 usedSize = 0; 63 } 64 else 65 { 66 data = NULL; 67 nextFree = NULL; 68 size = 0; 69 alloc = &allocDef; 70 growBy = 0; 71 usedSize = 0; 72 } 73 } ~neSimpleArray()74 NEINLINE ~neSimpleArray() 75 { 76 Free(); 77 } 78 NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL, s32 _growBy = 0) 79 { 80 if (IsFixedSize()) 81 { 82 ASSERT(0); 83 return false; 84 } 85 Free(); 86 87 if (al) 88 alloc = al; 89 else 90 alloc = & allocDef; 91 92 growBy = _growBy; 93 94 neByte * mem = alloc->Alloc(sizeof(T) * n); 95 96 data = (T*) mem; 97 98 if (data) 99 { 100 nextFree = data; 101 size = n; 102 return true; 103 } 104 return false; 105 }; 106 107 NEINLINE T * Alloc(s32 dummy = 0) 108 { 109 if (nextFree >= (data + size)) 110 { 111 if (growBy == 0) 112 return NULL; 113 114 T * oldData = data; 115 116 if (growBy == -1) 117 data = (T*)alloc->Alloc((size * 2) * sizeof(T)); 118 else 119 data = (T*)alloc->Alloc((size + growBy) * sizeof(T)); 120 121 if (!data) 122 { 123 data = oldData; 124 125 return NULL; 126 } 127 128 memcpy(data, oldData, size * sizeof(T)); 129 130 if (oldData) 131 alloc->Free((neByte*)oldData); 132 133 nextFree = data + size; 134 135 if (growBy == -1) 136 size *= 2; 137 else 138 size += growBy; 139 140 usedSize++; 141 return nextFree++; 142 } 143 else 144 { 145 usedSize++; 146 return nextFree++; 147 } 148 } GetIndex(T * c)149 NEINLINE s32 GetIndex(T * c) 150 { 151 ASSERT(c >= data); 152 ASSERT(c < nextFree); 153 154 return (s32)(c - data); 155 } GetUsedCount()156 NEINLINE s32 GetUsedCount(){ 157 return (nextFree - data); 158 } GetTotalSize()159 NEINLINE s32 GetTotalSize(){ 160 return size; 161 } Free()162 NEINLINE void Free() 163 { 164 if (IsFixedSize()) 165 { 166 return; 167 } 168 if (data) 169 { 170 alloc->Free((neByte*)data); 171 } 172 data = NULL; 173 nextFree = NULL; 174 size = 0; 175 usedSize = 0; 176 } Clear()177 NEINLINE void Clear() 178 { 179 nextFree = data; 180 usedSize = 0; 181 } 182 NEINLINE T & operator [] (s32 index) { 183 ASSERT(index >= 0); 184 ASSERT(index < size); 185 return data[index]; 186 } MakeFromPointer(T * pdata,s32 makeSize)187 NEINLINE void MakeFromPointer(T * pdata, s32 makeSize) 188 { 189 data = pdata; 190 size = makeSize; 191 usedSize = size; 192 nextFree = pdata + makeSize; 193 alloc = NULL; 194 growBy = 0; 195 } 196 protected: 197 T * data; 198 T * nextFree; 199 s32 size; 200 s32 usedSize; 201 neAllocatorAbstract * alloc; 202 neAllocatorDefault allocDef; 203 s32 growBy; 204 T initArray[initFixedSize]; 205 }; 206 207 template <class T, int initFixedSize = 1> class neArray 208 { 209 PLACEMENT_MAGIC 210 public: IsFixedSize()211 NEINLINE bool IsFixedSize() 212 { 213 return (initFixedSize != 1); 214 } neArray()215 NEINLINE neArray(){ 216 if (IsFixedSize()) 217 { 218 data = initArray; 219 nextFree = data; 220 size = initFixedSize; 221 alloc = NULL; 222 growBy = 0; 223 } 224 else 225 { 226 data = NULL; 227 nextFree = NULL; 228 size = 0; 229 alloc = &allocDef; 230 growBy = 0; 231 } 232 } ~neArray()233 NEINLINE ~neArray() 234 { 235 Free(); 236 } 237 NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL, s32 _growBy = 0) 238 { 239 if (IsFixedSize()) 240 { 241 ASSERT(0); 242 return false; 243 } 244 Free(); 245 246 if (al) 247 alloc = al; 248 else 249 alloc = & allocDef; 250 251 growBy = _growBy; 252 253 neByte * mem = alloc->Alloc(sizeof(T) * n); 254 255 data = (T*) mem; 256 257 if (data) 258 { 259 nextFree = data; 260 size = n; 261 return true; 262 } 263 return false; 264 }; 265 Alloc()266 NEINLINE T * Alloc() 267 { 268 if (nextFree >= (data + size)) 269 { 270 if (growBy == 0) 271 return NULL; 272 273 T * oldData = data; 274 275 if (growBy == -1) 276 data = (T*)alloc->Alloc(sizeof(T) * (size * 2)); 277 else 278 data = (T*)alloc->Alloc(sizeof(T) * (size + growBy)); 279 280 if (!data) 281 { 282 data = oldData; 283 284 return NULL; 285 } 286 287 memcpy(data, oldData, size * sizeof(T)); 288 289 if (oldData) 290 alloc->Free((neByte*)oldData); 291 292 nextFree = data + size; 293 294 if (growBy == -1) 295 size *= 2; 296 else 297 size += growBy; 298 299 } 300 T * ret = new ((void*)(nextFree++)) T; 301 302 return ret; 303 } GetIndex(T * c)304 NEINLINE s32 GetIndex(T * c) 305 { 306 ASSERT(c >= data); 307 ASSERT(c < nextFree); 308 309 return (s32)(c - data); 310 } GetUsedCount()311 NEINLINE s32 GetUsedCount(){ 312 return (nextFree - data); 313 } GetTotalSize()314 NEINLINE s32 GetTotalSize(){ 315 return size; 316 } Free()317 NEINLINE void Free() 318 { 319 if (IsFixedSize()) 320 { 321 return; 322 } 323 if (data) 324 { 325 //delete [] (data, (void*)data); 326 327 alloc->Free((neByte*)data); 328 } 329 data = NULL; 330 nextFree = NULL; 331 size = 0; 332 } Clear()333 NEINLINE void Clear() 334 { 335 nextFree = data; 336 } 337 NEINLINE T & operator [] (s32 index) { 338 ASSERT(index >= 0); 339 ASSERT(index < size); 340 return data[index]; 341 } MakeFromPointer(T * pdata,s32 makeSize)342 NEINLINE void MakeFromPointer(T * pdata, s32 makeSize) 343 { 344 data = pdata; 345 size = makeSize; 346 nextFree = pdata + makeSize; 347 alloc = NULL; 348 growBy = 0; 349 } 350 protected: 351 T * data; 352 T * nextFree; 353 s32 size; 354 neAllocatorAbstract * alloc; 355 neAllocatorDefault allocDef; 356 s32 growBy; 357 358 T initArray[initFixedSize]; 359 }; 360 361 ///////////////////////////////////////////////////////////// 362 363 template <class T> class neFreeListItem 364 { 365 PLACEMENT_MAGIC 366 public: 367 /* 368 NEINLINE void * operator new (size_t s,void * addr) 369 { 370 return addr; 371 } 372 NEINLINE void * operator new[] (size_t s,void * addr) 373 { 374 return addr; 375 } 376 NEINLINE void operator delete(void *, void *) 377 { 378 } 379 NEINLINE void operator delete[](void *, void *) 380 { 381 } 382 */ T thing; 383 neFreeListItem * next; 384 neFreeListItem * prev; 385 bool state; 386 neFreeListItem()387 NEINLINE neFreeListItem() 388 { 389 prev = NULL; 390 next = NULL; 391 state = false; 392 } 393 Remove()394 NEINLINE void Remove() 395 { 396 if (next != NULL) 397 { 398 next->prev = prev; 399 } 400 if (prev != NULL) 401 { 402 prev->next = next; 403 } 404 Solo(); 405 } Insert(neFreeListItem * newItem)406 NEINLINE void Insert(neFreeListItem * newItem) 407 { 408 newItem->next = this; 409 newItem->prev = prev; 410 if (prev) 411 { 412 prev->next = newItem; 413 } 414 prev = newItem; 415 } Append(neFreeListItem * newItem)416 NEINLINE void Append(neFreeListItem * newItem) 417 { 418 newItem->next = next; 419 newItem->prev = this; 420 if (next) 421 { 422 next->prev = newItem; 423 } 424 next = newItem; 425 } Concat(neFreeListItem * newItem)426 NEINLINE void Concat(neFreeListItem * newItem) 427 { 428 ASSERT(next == NULL); 429 430 next = newItem; 431 432 newItem->prev = this; 433 } Solo()434 NEINLINE void Solo() 435 { 436 prev = NULL; 437 next = NULL; 438 } 439 }; 440 441 ///////////////////////////////////////////////////////////// 442 443 template <class T, int initFixedSize = 1> class neDLinkList 444 { 445 public: 446 typedef neFreeListItem<T> listItem; 447 IsFixedSize()448 NEINLINE bool IsFixedSize() 449 { 450 return (initFixedSize != 1); 451 } CheckBelongAndInUse(T * t)452 NEINLINE neBool CheckBelongAndInUse(T * t) 453 { 454 listItem * item = (listItem *)t; 455 456 if (item < data) 457 return false; 458 459 if (item >= (data + size)) 460 return false; 461 462 return item->state; //1 = in use 463 } Init()464 NEINLINE void Init() 465 { 466 if (!IsFixedSize()) 467 { 468 data = NULL; 469 unused = NULL; 470 used = NULL; 471 unusedTail = NULL; 472 usedTail = NULL; 473 size = 0; 474 usedCount = 0; 475 unusedCount = 0; 476 } 477 else 478 { 479 data = initArray; 480 size = initFixedSize; 481 for (int i = 0; i < size; i++) 482 { 483 data[i].next = &(data[i+1]); 484 data[i].prev = &(data[i-1]); 485 data[i].state = false; 486 } 487 data[0].prev = NULL; 488 data[size-1].next = NULL; 489 490 unused = data; 491 unusedTail = data + size; 492 unusedCount = size; 493 494 used = NULL; 495 usedTail = NULL; 496 usedCount = 0; 497 } 498 } neDLinkList()499 NEINLINE neDLinkList() 500 { 501 alloc = &allocDef; 502 503 Init(); 504 } Free()505 NEINLINE void Free() 506 { 507 if (IsFixedSize()) 508 return; 509 510 //delete [] (data, (void*) data); 511 512 if (data) 513 alloc->Free((neByte*)data-mallocNewDiff); 514 515 Init(); 516 } Size()517 NEINLINE s32 Size() 518 { 519 return size; 520 } ~neDLinkList()521 NEINLINE ~neDLinkList() 522 { 523 Free(); 524 } 525 NEINLINE T * Alloc(s32 flag = 0) 526 { 527 if (!unused) 528 return NULL; 529 530 T * ret = &(unused->thing); 531 532 ASSERT(unused->state == false); 533 534 unused->state = true; 535 536 listItem * newUnusedHead; 537 538 newUnusedHead = unused->next; 539 540 unused->Remove(); 541 542 if (flag == 0) 543 { 544 if (usedTail) 545 { 546 usedTail->Append(unused); 547 usedTail = unused; 548 } 549 else 550 { 551 used = unused; 552 used->Solo(); 553 usedTail = used; 554 } 555 } 556 else 557 { 558 unused->Solo(); 559 } 560 561 if (unused == unusedTail) 562 { 563 unusedTail = NULL; 564 unused = NULL;; 565 ASSERT(newUnusedHead == NULL); 566 } 567 else 568 unused = newUnusedHead; 569 570 unusedCount--; 571 usedCount++; 572 return ret; 573 } 574 NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL) 575 { 576 if (IsFixedSize()) 577 { 578 ASSERT(0); 579 return false; 580 } 581 Free(); 582 583 if (n == 0) 584 return true; 585 586 if (al) 587 alloc = al; 588 589 neByte * mem = alloc->Alloc(sizeof(listItem) * n + 4); 590 591 data = new (mem) listItem[n]; 592 593 mallocNewDiff = (neByte*)data - mem; 594 595 size = n; 596 597 for (int i = 0; i < n; i++) 598 { 599 data[i].next = &(data[i+1]); 600 data[i].prev = &(data[i-1]); 601 data[i].state = false; 602 } 603 data[0].prev = NULL; 604 data[n-1].next = NULL; 605 606 unused = data; 607 unusedTail = data + size; 608 unusedCount = n; 609 610 used = NULL; 611 usedTail = NULL; 612 usedCount = 0; 613 614 return true; 615 } 616 NEINLINE void Dealloc(T * thing, s32 flag = 0) 617 { 618 if (!flag && !used) 619 { 620 ASSERT(0); 621 return; 622 } 623 624 s32 n = GetID(thing); 625 626 ASSERT(n >= 0); 627 ASSERT(n < size); 628 629 listItem * newUnused = &(data[n]); 630 631 ASSERT(newUnused->state == true); 632 633 newUnused->state = false; 634 635 if (flag == 0) 636 { 637 if (newUnused == used) // dealloc head of used 638 { 639 used = newUnused->next; 640 } 641 if (newUnused == usedTail) // dealloc tail of used 642 { 643 usedTail = newUnused->prev; 644 } 645 } 646 647 newUnused->Remove(); 648 649 if (unused) 650 { 651 unused->Insert(newUnused); 652 } 653 else 654 { 655 newUnused->Solo(); 656 unusedTail = newUnused; 657 } 658 unused = newUnused; 659 660 unusedCount++; 661 usedCount--; 662 } GetID(T * t)663 NEINLINE s32 GetID(T * t) 664 { 665 return ((listItem*)t - data); 666 } GetUsedCount()667 NEINLINE s32 GetUsedCount() 668 { 669 return usedCount; 670 } 671 class iterator; 672 Clear()673 NEINLINE void Clear() 674 { 675 iterator iter; 676 677 for (iter = BeginUsed(); iter.Valid();) 678 { 679 iterator next = BeginNext(iter); 680 681 Dealloc(*iter); 682 683 iter = next; 684 } 685 } BeginUsed()686 NEINLINE iterator BeginUsed() 687 { 688 iterator iter; 689 690 iter.cur = used; 691 692 return iter; 693 } BeginUnused()694 NEINLINE iterator BeginUnused() 695 { 696 iterator iter; 697 698 iter.cur = unused; 699 700 return iter; 701 } BeginNext(const iterator & it)702 NEINLINE iterator BeginNext(const iterator & it) 703 { 704 iterator next; 705 706 next.cur = it.cur->next; 707 708 return next; 709 } 710 class iterator 711 { 712 public: 713 NEINLINE T * operator * () const 714 { 715 if (cur) 716 return &(cur->thing); 717 return NULL; 718 } 719 NEINLINE bool operator ++ (int) 720 { 721 if (cur) 722 { 723 cur = cur->next; 724 return true; 725 } 726 return false; 727 } 728 NEINLINE bool operator -- () 729 { 730 if (cur) 731 { 732 cur = cur->prev; 733 return true; 734 } 735 return false; 736 } Valid()737 NEINLINE bool Valid() 738 { 739 return (cur != NULL); 740 } 741 public: 742 listItem * cur; 743 }; 744 745 public: 746 listItem * data; 747 listItem * unused; 748 listItem * used; 749 listItem * unusedTail; 750 listItem * usedTail; 751 s32 size; 752 s32 unusedCount; 753 s32 usedCount; 754 neAllocatorAbstract * alloc; 755 neAllocatorDefault allocDef; 756 s32 mallocNewDiff; 757 listItem initArray[initFixedSize]; 758 }; 759 /* 760 template <class T, int initFixedSize = 1> class neHeap 761 { 762 public: 763 typedef neDLinkList<T*, initFixedSize> FreeList; 764 765 NEINLINE IsFixedSize() 766 { 767 return (initFixedSize != 1); 768 } 769 NEINLINE neHeap() 770 { 771 Init(); 772 } 773 NEINLINE void Init() 774 { 775 freeList.Init(); 776 777 if (IsFixedSize()) 778 { 779 buffer = initArray; 780 alloc = NULL; 781 } 782 else 783 { 784 buffer = NULL; 785 alloc = &allocDef; 786 } 787 } 788 NEINLINE ~neHeap() 789 { 790 Free(); 791 } 792 NEINLINE bool Reserve(s32 n, neAllocatorAbstract * al = NULL) 793 { 794 if (IsFixedSize()) 795 { 796 ASSERT(0); 797 return false; 798 } 799 Free(); 800 801 if (!freeList.Reserve(n, al)) 802 return false; 803 804 if (al) 805 alloc = al; 806 807 neByte * mem = alloc->Alloc(sizeof(T) * n + 4); 808 809 buffer = new(mem) T[n]; 810 811 mallocNewDiff = (neByte*)buffer - mem; 812 813 if (!buffer) 814 { 815 Free(); 816 return false; 817 } 818 FreeList::iterator it; 819 820 int i = 0; 821 for (it = freeList.BeginUnused(); it.Valid(); it++) 822 { 823 (**it) = &(buffer[i]); 824 i++; 825 } 826 return true; 827 } 828 NEINLINE T * Alloc(s32 flag = 0) 829 { 830 T ** pt = freeList.Alloc(flag); 831 832 new (*pt) T; 833 834 if (!pt) 835 return NULL; 836 else 837 return *pt; 838 } 839 NEINLINE void Dealloc(T * t, s32 flag = 0) 840 { 841 s32 offset = GetID(t); 842 843 FreeList::listItem * li = freeList.data + offset; 844 845 freeList.Dealloc((T**)li, flag); 846 } 847 NEINLINE s32 GetID(T * t) 848 { 849 return (t - buffer); 850 } 851 NEINLINE neBool IsInUse(T * t) 852 { 853 s32 i = GetID(t); 854 855 ASSERT(i >= 0 && i <freeList.size); 856 857 return freeList.data[i].state; 858 } 859 NEINLINE void Free() 860 { 861 if (IsFixedSize()) 862 return; 863 864 //delete [] (buffer, (void*)buffer); 865 866 if (buffer) 867 alloc->Free((neByte*)buffer-mallocNewDiff); 868 869 freeList.Free(); 870 871 Init(); 872 } 873 NEINLINE s32 GetUsedCount() 874 { 875 return freeList.usedCount; 876 } 877 NEINLINE s32 GetUnusedCount() 878 { 879 return freeList.unusedCount; 880 } 881 NEINLINE s32 Size() 882 { 883 return freeList.size; 884 } 885 class iterator; 886 887 NEINLINE iterator BeginUsed() 888 { 889 iterator cur; 890 891 cur.iter = freeList.BeginUsed(); 892 893 return cur; 894 } 895 NEINLINE iterator BeginUnused() 896 { 897 iterator cur; 898 899 cur.iter = freeList.BeginUnused(); 900 901 return cur; 902 } 903 NEINLINE iterator BeginNext(const iterator & it) 904 { 905 iterator next; 906 907 next.iter = freeList.BeginNext(it.iter); 908 909 return next; 910 } 911 class iterator 912 { 913 public: 914 FreeList::iterator iter; 915 916 NEINLINE T * operator * () const 917 { 918 return (**iter); 919 } 920 NEINLINE bool operator ++ (int) 921 { 922 return (iter++); 923 } 924 NEINLINE bool operator -- () 925 { 926 return (iter--) 927 } 928 NEINLINE bool Valid() 929 { 930 return (iter.Valid()); 931 } 932 }; 933 934 protected: 935 T * buffer; 936 FreeList freeList; 937 neAllocatorAbstract * alloc; 938 neAllocatorDefault allocDef; 939 s32 mallocNewDiff; 940 941 T initArray[initFixedSize]; 942 }; 943 */ 944 template <class T> class neCollection 945 { 946 public: 947 typedef neFreeListItem<T*> itemType; 948 neCollection()949 neCollection() 950 { 951 Reset(); 952 } Reset()953 void Reset() 954 { 955 headItem = NULL; 956 tailItem = NULL; 957 count = 0; 958 } Add(itemType * add)959 void Add(itemType * add) 960 { 961 ASSERT(add); 962 963 if (headItem) 964 { 965 tailItem->Append(add); 966 967 tailItem = add; 968 } 969 else 970 { 971 headItem = add; 972 tailItem = add; 973 } 974 count++; 975 } Remove(itemType * rem)976 void Remove(itemType * rem) 977 { 978 ASSERT(count > 0); 979 980 ASSERT(rem); 981 982 if (rem == headItem) 983 { 984 headItem = rem->next; 985 } 986 if (rem == tailItem) 987 { 988 tailItem = rem->prev; 989 } 990 rem->Remove(); 991 992 count --; 993 } GetHead()994 itemType * GetHead() 995 { 996 return headItem; 997 } GetNext(itemType * cur)998 itemType * GetNext(itemType * cur) 999 { 1000 return cur->next; 1001 } GetPrev(itemType * cur)1002 itemType * GetPrev(itemType * cur) 1003 { 1004 return cur->prev; 1005 } 1006 1007 public: 1008 neFreeListItem<T*> * headItem; 1009 neFreeListItem<T*> * tailItem; 1010 s32 count; 1011 }; 1012 1013 template <class T> class neList 1014 { 1015 public: 1016 typedef neFreeListItem<T> itemType; 1017 neList()1018 neList() 1019 { 1020 Reset(); 1021 } Reset()1022 void Reset() 1023 { 1024 headItem = NULL; 1025 tailItem = NULL; 1026 count = 0; 1027 } Add(T * add)1028 void Add(T * add) 1029 { 1030 ASSERT(add); 1031 1032 itemType * addItem = (itemType *)add; 1033 1034 if (headItem) 1035 { 1036 tailItem->Append(addItem); 1037 1038 tailItem = addItem; 1039 } 1040 else 1041 { 1042 headItem = addItem; 1043 tailItem = addItem; 1044 } 1045 count++; 1046 } AddOrder(T * add)1047 void AddOrder(T * add) 1048 { 1049 ASSERT(add); 1050 1051 itemType * addItem = (itemType *)add; 1052 1053 if (!headItem) 1054 { 1055 headItem = addItem; 1056 1057 tailItem = addItem; 1058 1059 count = 1; 1060 1061 return; 1062 } 1063 1064 itemType * curItem = tailItem; 1065 1066 neBool done = false; 1067 1068 while (curItem) 1069 { 1070 T * curT = (T *)curItem; 1071 1072 if (add->Value() <= curT->Value()) 1073 { 1074 done = true; 1075 1076 curItem->Append(addItem); 1077 1078 if (curItem == tailItem) 1079 { 1080 tailItem = addItem; 1081 } 1082 break; 1083 } 1084 curItem = curItem->prev; 1085 } 1086 if (!done) 1087 { 1088 headItem->Insert(addItem); 1089 1090 headItem = addItem; 1091 } 1092 count++; 1093 } UpdateOrder(T * u)1094 void UpdateOrder(T * u) 1095 { 1096 if (count == 1) 1097 return; 1098 1099 itemType * uItem = (itemType *) u; 1100 1101 itemType * cItem; 1102 1103 neBool done = false; 1104 1105 if (uItem == tailItem) // move up 1106 { 1107 cItem = uItem->prev; 1108 1109 Remove(u); 1110 1111 while (cItem) 1112 { 1113 if (((T*)cItem)->Value() >= u->Value()) 1114 { 1115 cItem->Append(uItem); 1116 1117 if (cItem == tailItem) 1118 { 1119 tailItem = uItem; 1120 } 1121 done = true; 1122 1123 break; 1124 } 1125 cItem = cItem->prev; 1126 } 1127 if (!done) 1128 { 1129 headItem->Insert(uItem); 1130 1131 headItem = uItem; 1132 } 1133 count++; // because Remove dec count; 1134 } 1135 else if (uItem == headItem) // move down 1136 { 1137 cItem = uItem->next; 1138 1139 Remove(u); 1140 1141 while (cItem) 1142 { 1143 if (((T*)cItem)->Value() <= u->Value()) 1144 { 1145 cItem->Insert(uItem); 1146 1147 if (cItem == headItem) 1148 { 1149 headItem = uItem; 1150 } 1151 done = true; 1152 1153 break; 1154 } 1155 cItem = cItem->next; 1156 } 1157 if (!done) 1158 { 1159 tailItem->Append(uItem); 1160 1161 tailItem = uItem; 1162 } 1163 count ++; 1164 } 1165 else 1166 { 1167 itemType * nextItem = uItem->next; 1168 1169 T * nextT = (T*) nextItem; 1170 1171 if (u->Value() < nextT->Value()) 1172 { 1173 //move down 1174 cItem = nextItem; 1175 1176 Remove(u); 1177 1178 while (cItem) 1179 { 1180 if (((T*)cItem)->Value() <= u->Value()) 1181 { 1182 cItem->Insert(uItem); 1183 1184 done = true; 1185 1186 break; 1187 } 1188 cItem = cItem->next; 1189 } 1190 if (!done) 1191 { 1192 tailItem->Append(uItem); 1193 1194 tailItem = uItem; 1195 } 1196 count ++; 1197 } 1198 else 1199 { 1200 //move up 1201 cItem = uItem->prev; 1202 1203 Remove(u); 1204 1205 while (cItem) 1206 { 1207 if (((T*)cItem)->Value() >= u->Value()) 1208 { 1209 cItem->Append(uItem); 1210 1211 if (cItem == tailItem) 1212 { 1213 tailItem = uItem; 1214 } 1215 done = true; 1216 1217 break; 1218 } 1219 cItem = cItem->prev; 1220 } 1221 if (!done) 1222 { 1223 headItem->Insert(uItem); 1224 1225 headItem = uItem; 1226 } 1227 count++; // because Remove dec count; 1228 } 1229 } 1230 } Remove(T * rem)1231 void Remove(T * rem) 1232 { 1233 ASSERT(count > 0); 1234 1235 ASSERT(rem); 1236 1237 itemType * remItem = (itemType *)rem; 1238 1239 if (remItem == headItem) 1240 { 1241 headItem = remItem->next; 1242 } 1243 if (remItem == tailItem) 1244 { 1245 tailItem = remItem->prev; 1246 } 1247 remItem->Remove(); 1248 1249 count --; 1250 } GetHead()1251 T * GetHead() 1252 { 1253 return(T*)headItem; 1254 } GetNext(T * cur)1255 T * GetNext(T * cur) 1256 { 1257 return (T*)((itemType*)cur)->next; 1258 } GetPrev(T * cur)1259 T * GetPrev(T * cur) 1260 { 1261 return (T*)((itemType*)cur)->prev; 1262 } 1263 1264 public: 1265 itemType * headItem; 1266 itemType * tailItem; 1267 s32 count; 1268 }; 1269 1270 #endif //CONTAINERS_H