1 /* 2 ** tarray.h 3 ** Templated, automatically resizing array 4 ** 5 **--------------------------------------------------------------------------- 6 ** Copyright 1998-2007 Randy Heit 7 ** All rights reserved. 8 ** 9 ** Redistribution and use in source and binary forms, with or without 10 ** modification, are permitted provided that the following conditions 11 ** are met: 12 ** 13 ** 1. Redistributions of source code must retain the above copyright 14 ** notice, this list of conditions and the following disclaimer. 15 ** 2. Redistributions in binary form must reproduce the above copyright 16 ** notice, this list of conditions and the following disclaimer in the 17 ** documentation and/or other materials provided with the distribution. 18 ** 3. The name of the author may not be used to endorse or promote products 19 ** derived from this software without specific prior written permission. 20 ** 21 ** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22 ** IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23 ** OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24 ** IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25 ** INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26 ** NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 ** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 ** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 ** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30 ** THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 **--------------------------------------------------------------------------- 32 ** 33 */ 34 35 #ifndef __TARRAY_H__ 36 #define __TARRAY_H__ 37 38 #include <stdlib.h> 39 #include <assert.h> 40 #include <string.h> 41 #include <new> 42 43 #if !defined(_WIN32) 44 #include <inttypes.h> // for intptr_t 45 #elif !defined(_MSC_VER) 46 #include <stdint.h> // for mingw 47 #endif 48 49 #include "m_alloc.h" 50 51 class FArchive; 52 53 // TArray ------------------------------------------------------------------- 54 55 // T is the type stored in the array. 56 // TT is the type returned by operator(). 57 template <class T, class TT=T> 58 class TArray 59 { 60 template<class U, class UU> friend FArchive &operator<< (FArchive &arc, TArray<U,UU> &self); 61 62 public: 63 //////// 64 // This is a dummy constructor that does nothing. The purpose of this 65 // is so you can create a global TArray in the data segment that gets 66 // used by code before startup without worrying about the constructor 67 // resetting it after it's already been used. You MUST NOT use it for 68 // heap- or stack-allocated TArrays. 69 enum ENoInit 70 { 71 NoInit 72 }; TArray(ENoInit dummy)73 TArray (ENoInit dummy) 74 { 75 } 76 //////// TArray()77 TArray () 78 { 79 Most = 0; 80 Count = 0; 81 Array = NULL; 82 } TArray(int max)83 TArray (int max) 84 { 85 Most = max; 86 Count = 0; 87 Array = (T *)M_Malloc (sizeof(T)*max); 88 } TArray(const TArray<T> & other)89 TArray (const TArray<T> &other) 90 { 91 DoCopy (other); 92 } 93 TArray<T> &operator= (const TArray<T> &other) 94 { 95 if (&other != this) 96 { 97 if (Array != NULL) 98 { 99 if (Count > 0) 100 { 101 DoDelete (0, Count-1); 102 } 103 M_Free (Array); 104 } 105 DoCopy (other); 106 } 107 return *this; 108 } ~TArray()109 ~TArray () 110 { 111 if (Array) 112 { 113 if (Count > 0) 114 { 115 DoDelete (0, Count-1); 116 } 117 M_Free (Array); 118 Array = NULL; 119 Count = 0; 120 Most = 0; 121 } 122 } 123 // Return a reference to an element 124 T &operator[] (size_t index) const 125 { 126 return Array[index]; 127 } 128 // Returns the value of an element operator()129 TT operator() (size_t index) const 130 { 131 return Array[index]; 132 } 133 // Returns a reference to the last element Last()134 T &Last() const 135 { 136 return Array[Count-1]; 137 } 138 Find(const T & item)139 unsigned int Find(const T& item) const 140 { 141 unsigned int i; 142 for(i = 0;i < Count;++i) 143 { 144 if(Array[i] == item) 145 break; 146 } 147 return i; 148 } 149 Push(const T & item)150 unsigned int Push (const T &item) 151 { 152 Grow (1); 153 ::new((void*)&Array[Count]) T(item); 154 return Count++; 155 } Pop()156 bool Pop () 157 { 158 if (Count > 0) 159 { 160 Array[--Count].~T(); 161 return true; 162 } 163 return false; 164 } Pop(T & item)165 bool Pop (T &item) 166 { 167 if (Count > 0) 168 { 169 item = Array[--Count]; 170 Array[Count].~T(); 171 return true; 172 } 173 return false; 174 } Delete(unsigned int index)175 void Delete (unsigned int index) 176 { 177 if (index < Count) 178 { 179 Array[index].~T(); 180 if (index < --Count) 181 { 182 memmove (&Array[index], &Array[index+1], sizeof(T)*(Count - index)); 183 } 184 } 185 } 186 Delete(unsigned int index,int deletecount)187 void Delete (unsigned int index, int deletecount) 188 { 189 if (index + deletecount > Count) 190 { 191 deletecount = Count - index; 192 } 193 if (deletecount > 0) 194 { 195 for (int i = 0; i < deletecount; i++) 196 { 197 Array[index + i].~T(); 198 } 199 Count -= deletecount; 200 if (index < Count) 201 { 202 memmove (&Array[index], &Array[index+deletecount], sizeof(T)*(Count - index)); 203 } 204 } 205 } 206 207 // Inserts an item into the array, shifting elements as needed Insert(unsigned int index,const T & item)208 void Insert (unsigned int index, const T &item) 209 { 210 if (index >= Count) 211 { 212 // Inserting somewhere past the end of the array, so we can 213 // just add it without moving things. 214 Resize (index + 1); 215 ::new ((void *)&Array[index]) T(item); 216 } 217 else 218 { 219 // Inserting somewhere in the middle of the array, 220 // so make room for it 221 Resize (Count + 1); 222 223 // Now move items from the index and onward out of the way 224 memmove (&Array[index+1], &Array[index], sizeof(T)*(Count - index - 1)); 225 226 // And put the new element in 227 ::new ((void *)&Array[index]) T(item); 228 } 229 } ShrinkToFit()230 void ShrinkToFit () 231 { 232 if (Most > Count) 233 { 234 Most = Count; 235 if (Most == 0) 236 { 237 if (Array != NULL) 238 { 239 M_Free (Array); 240 Array = NULL; 241 } 242 } 243 else 244 { 245 DoResize (); 246 } 247 } 248 } 249 // Grow Array to be large enough to hold amount more entries without 250 // further growing. Grow(unsigned int amount)251 void Grow (unsigned int amount) 252 { 253 if (Count + amount > Most) 254 { 255 const unsigned int choicea = Count + amount; 256 const unsigned int choiceb = Most = (Most >= 16) ? Most + Most / 2 : 16; 257 Most = (choicea > choiceb ? choicea : choiceb); 258 DoResize (); 259 } 260 } 261 // Resize Array so that it has exactly amount entries in use. Resize(unsigned int amount)262 void Resize (unsigned int amount) 263 { 264 if (Count < amount) 265 { 266 // Adding new entries 267 Grow (amount - Count); 268 for (unsigned int i = Count; i < amount; ++i) 269 { 270 ::new((void *)&Array[i]) T; 271 } 272 } 273 else if (Count != amount) 274 { 275 // Deleting old entries 276 DoDelete (amount, Count - 1); 277 } 278 Count = amount; 279 } 280 // Reserves amount entries at the end of the array, but does nothing 281 // with them. Reserve(unsigned int amount)282 unsigned int Reserve (unsigned int amount) 283 { 284 Grow (amount); 285 unsigned int place = Count; 286 Count += amount; 287 for (unsigned int i = place; i < Count; ++i) 288 { 289 ::new((void *)&Array[i]) T; 290 } 291 return place; 292 } Size()293 unsigned int Size () const 294 { 295 return Count; 296 } Max()297 unsigned int Max () const 298 { 299 return Most; 300 } Clear()301 void Clear () 302 { 303 if (Count > 0) 304 { 305 DoDelete (0, Count-1); 306 Count = 0; 307 } 308 } 309 private: 310 T *Array; 311 unsigned int Most; 312 unsigned int Count; 313 DoCopy(const TArray<T> & other)314 void DoCopy (const TArray<T> &other) 315 { 316 Most = Count = other.Count; 317 if (Count != 0) 318 { 319 Array = (T *)M_Malloc (sizeof(T)*Most); 320 for (unsigned int i = 0; i < Count; ++i) 321 { 322 ::new(&Array[i]) T(other.Array[i]); 323 } 324 } 325 else 326 { 327 Array = NULL; 328 } 329 } 330 DoResize()331 void DoResize () 332 { 333 size_t allocsize = sizeof(T)*Most; 334 Array = (T *)M_Realloc (Array, allocsize); 335 } 336 DoDelete(unsigned int first,unsigned int last)337 void DoDelete (unsigned int first, unsigned int last) 338 { 339 assert (last != ~0u); 340 for (unsigned int i = first; i <= last; ++i) 341 { 342 Array[i].~T(); 343 } 344 } 345 }; 346 347 // TDeletingArray ----------------------------------------------------------- 348 // An array that deletes its elements when it gets deleted. 349 template<class T, class TT=T> 350 class TDeletingArray : public TArray<T, TT> 351 { 352 public: 353 ~TDeletingArray<T, TT> () 354 { 355 for (unsigned int i = 0; i < TArray<T,TT>::Size(); ++i) 356 { 357 if ((*this)[i] != NULL) 358 delete (*this)[i]; 359 } 360 } 361 }; 362 363 // TAutoGrowArray ----------------------------------------------------------- 364 // An array with accessors that automatically grow the array as needed. 365 // It can still be used as a normal TArray if needed. ACS uses this for 366 // world and global arrays. 367 368 template <class T, class TT=T> 369 class TAutoGrowArray : public TArray<T, TT> 370 { 371 public: GetVal(unsigned int index)372 T GetVal (unsigned int index) 373 { 374 if (index >= this->Size()) 375 { 376 return 0; 377 } 378 return (*this)[index]; 379 } SetVal(unsigned int index,T val)380 void SetVal (unsigned int index, T val) 381 { 382 if ((int)index < 0) return; // These always result in an out of memory condition. 383 384 if (index >= this->Size()) 385 { 386 this->Resize (index + 1); 387 } 388 (*this)[index] = val; 389 } 390 }; 391 392 // TMap --------------------------------------------------------------------- 393 // An associative array, similar in concept to the STL extension 394 // class hash_map. It is implemented using Lua's table algorithm: 395 /* 396 ** Hash uses a mix of chained scatter table with Brent's variation. 397 ** A main invariant of these tables is that, if an element is not 398 ** in its main position (i.e. the `original' position that its hash gives 399 ** to it), then the colliding element is in its own main position. 400 ** Hence even when the load factor reaches 100%, performance remains good. 401 */ 402 /****************************************************************************** 403 * Copyright (C) 1994-2006 Lua.org, PUC-Rio. All rights reserved. 404 * 405 * Permission is hereby granted, free of charge, to any person obtaining 406 * a copy of this software and associated documentation files (the 407 * "Software"), to deal in the Software without restriction, including 408 * without limitation the rights to use, copy, modify, merge, publish, 409 * distribute, sublicense, and/or sell copies of the Software, and to 410 * permit persons to whom the Software is furnished to do so, subject to 411 * the following conditions: 412 * 413 * The above copyright notice and this permission notice shall be 414 * included in all copies or substantial portions of the Software. 415 * 416 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 417 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 418 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 419 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 420 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 421 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 422 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 423 ******************************************************************************/ 424 425 typedef unsigned int hash_t; 426 427 template<class KT> struct THashTraits 428 { 429 // Returns the hash value for a key. HashTHashTraits430 hash_t Hash(const KT key) { return (hash_t)(intptr_t)key; } 431 432 // Compares two keys, returning zero if they are the same. CompareTHashTraits433 int Compare(const KT left, const KT right) { return left != right; } 434 }; 435 436 template<class VT> struct TValueTraits 437 { 438 // Initializes a value for TMap. If a regular constructor isn't 439 // good enough, you can override it. InitTValueTraits440 void Init(VT &value) 441 { 442 ::new(&value) VT; 443 } 444 }; 445 446 template<class KT, class VT, class MapType> class TMapIterator; 447 template<class KT, class VT, class MapType> class TMapConstIterator; 448 449 template<class KT, class VT, class HashTraits=THashTraits<KT>, class ValueTraits=TValueTraits<VT> > 450 class TMap 451 { 452 template<class KTa, class VTa, class MTa> friend class TMapIterator; 453 template<class KTb, class VTb, class MTb> friend class TMapConstIterator; 454 455 public: 456 typedef class TMap<KT, VT, HashTraits, ValueTraits> MyType; 457 typedef class TMapIterator<KT, VT, MyType> Iterator; 458 typedef class TMapConstIterator<KT, VT, MyType> ConstIterator; 459 typedef struct { const KT Key; VT Value; } Pair; 460 typedef const Pair ConstPair; 461 TMap()462 TMap() { NumUsed = 0; SetNodeVector(1); } TMap(hash_t size)463 TMap(hash_t size) { NumUsed = 0; SetNodeVector(size); } ~TMap()464 ~TMap() { ClearNodeVector(); } 465 TMap(const TMap & o)466 TMap(const TMap &o) 467 { 468 NumUsed = 0; 469 SetNodeVector(o.CountUsed()); 470 CopyNodes(o.Nodes, o.Size); 471 } 472 473 TMap &operator= (const TMap &o) 474 { 475 NumUsed = 0; 476 ClearNodeVector(); 477 SetNodeVector(o.CountUsed()); 478 CopyNodes(o.Nodes, o.Size); 479 return *this; 480 } 481 482 //======================================================================= 483 // 484 // TransferFrom 485 // 486 // Moves the contents from one TMap to another, leaving the TMap moved 487 // from empty. 488 // 489 //======================================================================= 490 TransferFrom(TMap & o)491 void TransferFrom(TMap &o) 492 { 493 // Clear all our nodes. 494 NumUsed = 0; 495 ClearNodeVector(); 496 497 // Copy all of o's nodes. 498 Nodes = o.Nodes; 499 LastFree = o.LastFree; 500 Size = o.Size; 501 NumUsed = o.NumUsed; 502 503 // Tell o it doesn't have any nodes. 504 o.Nodes = NULL; 505 o.Size = 0; 506 o.LastFree = NULL; 507 o.NumUsed = 0; 508 509 // Leave o functional with one empty node. 510 o.SetNodeVector(1); 511 } 512 513 //======================================================================= 514 // 515 // Clear 516 // 517 // Empties out the table and resizes it with room for count entries. 518 // 519 //======================================================================= 520 521 void Clear(hash_t count=1) 522 { 523 ClearNodeVector(); 524 SetNodeVector(count); 525 } 526 527 //======================================================================= 528 // 529 // CountUsed 530 // 531 // Returns the number of entries in use in the table. 532 // 533 //======================================================================= 534 CountUsed()535 hash_t CountUsed() const 536 { 537 #ifdef _DEBUG 538 hash_t used = 0; 539 hash_t ct = Size; 540 for (Node *n = Nodes; ct-- > 0; ++n) 541 { 542 if (!n->IsNil()) 543 { 544 ++used; 545 } 546 } 547 assert (used == NumUsed); 548 #endif 549 return NumUsed; 550 } 551 552 //======================================================================= 553 // 554 // operator[] 555 // 556 // Returns a reference to the value associated with a particular key, 557 // creating the pair if the key isn't already in the table. 558 // 559 //======================================================================= 560 561 VT &operator[] (const KT key) 562 { 563 return GetNode(key)->Pair.Value; 564 } 565 566 const VT &operator[] (const KT key) const 567 { 568 return GetNode(key)->Pair.Value; 569 } 570 571 //======================================================================= 572 // 573 // CheckKey 574 // 575 // Returns a pointer to the value associated with a particular key, or 576 // NULL if the key isn't in the table. 577 // 578 //======================================================================= 579 CheckKey(const KT key)580 VT *CheckKey (const KT key) 581 { 582 Node *n = FindKey(key); 583 return n != NULL ? &n->Pair.Value : NULL; 584 } 585 CheckKey(const KT key)586 const VT *CheckKey (const KT key) const 587 { 588 const Node *n = FindKey(key); 589 return n != NULL ? &n->Pair.Value : NULL; 590 } 591 592 //======================================================================= 593 // 594 // Insert 595 // 596 // Adds a key/value pair to the table if key isn't in the table, or 597 // replaces the value for the existing pair if the key is in the table. 598 // 599 // This is functionally equivalent to (*this)[key] = value; but can be 600 // slightly faster if the pair needs to be created because it doesn't run 601 // the constructor on the value part twice. 602 // 603 //======================================================================= 604 Insert(const KT key,const VT & value)605 VT &Insert(const KT key, const VT &value) 606 { 607 Node *n = FindKey(key); 608 if (n != NULL) 609 { 610 n->Pair.Value = value; 611 } 612 else 613 { 614 n = NewKey(key); 615 ::new(&n->Pair.Value) VT(value); 616 } 617 return n->Pair.Value; 618 } 619 620 //======================================================================= 621 // 622 // Remove 623 // 624 // Removes the key/value pair for a particular key if it is in the table. 625 // 626 //======================================================================= 627 Remove(const KT key)628 void Remove(const KT key) 629 { 630 DelKey(key); 631 } 632 633 protected: 634 struct IPair // This must be the same as Pair above, but with a 635 { // non-const Key. 636 KT Key; 637 VT Value; 638 }; 639 struct Node 640 { 641 Node *Next; 642 IPair Pair; SetNilNode643 void SetNil() 644 { 645 Next = (Node *)1; 646 } IsNilNode647 bool IsNil() const 648 { 649 return Next == (Node *)1; 650 } 651 }; 652 653 /* This is used instead of memcpy, because Node is likely to be small, 654 * such that the time spent calling a function would eclipse the time 655 * spent copying. */ 656 struct NodeSizedStruct { unsigned char Pads[sizeof(Node)]; }; 657 658 Node *Nodes; 659 Node *LastFree; /* any free position is before this position */ 660 hash_t Size; /* must be a power of 2 */ 661 hash_t NumUsed; 662 MainPosition(const KT k)663 const Node *MainPosition(const KT k) const 664 { 665 HashTraits Traits; 666 return &Nodes[Traits.Hash(k) & (Size - 1)]; 667 } 668 MainPosition(const KT k)669 Node *MainPosition(const KT k) 670 { 671 HashTraits Traits; 672 return &Nodes[Traits.Hash(k) & (Size - 1)]; 673 } 674 SetNodeVector(hash_t size)675 void SetNodeVector(hash_t size) 676 { 677 // Round size up to nearest power of 2 678 for (Size = 1; Size < size; Size <<= 1) 679 { } 680 Nodes = (Node *)M_Malloc(Size * sizeof(Node)); 681 LastFree = &Nodes[Size]; /* all positions are free */ 682 for (hash_t i = 0; i < Size; ++i) 683 { 684 Nodes[i].SetNil(); 685 } 686 } 687 ClearNodeVector()688 void ClearNodeVector() 689 { 690 for (hash_t i = 0; i < Size; ++i) 691 { 692 if (!Nodes[i].IsNil()) 693 { 694 Nodes[i].~Node(); 695 } 696 } 697 M_Free(Nodes); 698 Nodes = NULL; 699 Size = 0; 700 LastFree = NULL; 701 NumUsed = 0; 702 } 703 Resize(hash_t nhsize)704 void Resize(hash_t nhsize) 705 { 706 hash_t i, oldhsize = Size; 707 Node *nold = Nodes; 708 /* create new hash part with appropriate size */ 709 SetNodeVector(nhsize); 710 /* re-insert elements from hash part */ 711 NumUsed = 0; 712 for (i = 0; i < oldhsize; ++i) 713 { 714 if (!nold[i].IsNil()) 715 { 716 Node *n = NewKey(nold[i].Pair.Key); 717 ::new(&n->Pair.Value) VT(nold[i].Pair.Value); 718 nold[i].~Node(); 719 } 720 } 721 M_Free(nold); 722 } 723 Rehash()724 void Rehash() 725 { 726 Resize (Size << 1); 727 } 728 GetFreePos()729 Node *GetFreePos() 730 { 731 while (LastFree-- > Nodes) 732 { 733 if (LastFree->IsNil()) 734 { 735 return LastFree; 736 } 737 } 738 return NULL; /* could not find a free place */ 739 } 740 741 /* 742 ** Inserts a new key into a hash table; first, check whether key's main 743 ** position is free. If not, check whether colliding node is in its main 744 ** position or not: if it is not, move colliding node to an empty place and 745 ** put new key in its main position; otherwise (colliding node is in its main 746 ** position), new key goes to an empty position. 747 ** 748 ** The Value field is left unconstructed. 749 */ NewKey(const KT key)750 Node *NewKey(const KT key) 751 { 752 Node *mp = MainPosition(key); 753 if (!mp->IsNil()) 754 { 755 Node *othern; 756 Node *n = GetFreePos(); /* get a free place */ 757 if (n == NULL) /* cannot find a free place? */ 758 { 759 Rehash(); /* grow table */ 760 return NewKey(key); /* re-insert key into grown table */ 761 } 762 othern = MainPosition(mp->Pair.Key); 763 if (othern != mp) /* is colliding node out of its main position? */ 764 { /* yes; move colliding node into free position */ 765 while (othern->Next != mp) /* find previous */ 766 { 767 othern = othern->Next; 768 } 769 othern->Next = n; /* redo the chain with 'n' in place of 'mp' */ 770 CopyNode(n, mp); /* copy colliding node into free pos. (mp->Next also goes) */ 771 mp->Next = NULL; /* now 'mp' is free */ 772 } 773 else /* colliding node is in its own main position */ 774 { /* new node will go into free position */ 775 n->Next = mp->Next; /* chain new position */ 776 mp->Next = n; 777 mp = n; 778 } 779 } 780 else 781 { 782 mp->Next = NULL; 783 } 784 ++NumUsed; 785 ::new(&mp->Pair.Key) KT(key); 786 return mp; 787 } 788 DelKey(const KT key)789 void DelKey(const KT key) 790 { 791 Node *mp = MainPosition(key), **mpp; 792 HashTraits Traits; 793 794 if (mp->IsNil()) 795 { 796 /* the key is definitely not present, because there is nothing at its main position */ 797 } 798 else if (!Traits.Compare(mp->Pair.Key, key)) /* the key is in its main position */ 799 { 800 if (mp->Next != NULL) /* move next node to its main position */ 801 { 802 Node *n = mp->Next; 803 mp->~Node(); /* deconstruct old node */ 804 CopyNode(mp, n); /* copy next node */ 805 n->SetNil(); /* next node is now nil */ 806 } 807 else 808 { 809 mp->~Node(); 810 mp->SetNil(); /* there is no chain, so main position is nil */ 811 } 812 --NumUsed; 813 } 814 else /* the key is either not present or not in its main position */ 815 { 816 for (mpp = &mp->Next, mp = *mpp; mp != NULL && Traits.Compare(mp->Pair.Key, key); mpp = &mp->Next, mp = *mpp) 817 { } /* look for the key */ 818 if (mp != NULL) /* found it */ 819 { 820 *mpp = mp->Next; /* rechain so this node is skipped */ 821 mp->~Node(); 822 mp->SetNil(); /* because this node is now nil */ 823 --NumUsed; 824 } 825 } 826 } 827 FindKey(const KT key)828 Node *FindKey(const KT key) 829 { 830 HashTraits Traits; 831 Node *n = MainPosition(key); 832 while (n != NULL && !n->IsNil() && Traits.Compare(n->Pair.Key, key)) 833 { 834 n = n->Next; 835 } 836 return n == NULL || n->IsNil() ? NULL : n; 837 } 838 FindKey(const KT key)839 const Node *FindKey(const KT key) const 840 { 841 HashTraits Traits; 842 const Node *n = MainPosition(key); 843 while (n != NULL && !n->IsNil() && Traits.Compare(n->Pair.Key, key)) 844 { 845 n = n->Next; 846 } 847 return n == NULL || n->IsNil() ? NULL : n; 848 } 849 GetNode(const KT key)850 Node *GetNode(const KT key) 851 { 852 Node *n = FindKey(key); 853 if (n != NULL) 854 { 855 return n; 856 } 857 n = NewKey(key); 858 ValueTraits traits; 859 traits.Init(n->Pair.Value); 860 return n; 861 } 862 863 /* Perform a bit-wise copy of the node. Used when relocating a node in the table. */ CopyNode(Node * dst,const Node * src)864 void CopyNode(Node *dst, const Node *src) 865 { 866 *(NodeSizedStruct *)dst = *(const NodeSizedStruct *)src; 867 } 868 869 /* Copy all nodes in the node vector to this table. */ CopyNodes(const Node * nodes,hash_t numnodes)870 void CopyNodes(const Node *nodes, hash_t numnodes) 871 { 872 for (; numnodes-- > 0; ++nodes) 873 { 874 if (!nodes->IsNil()) 875 { 876 Node *n = NewKey(nodes->Pair.Key); 877 ::new(&n->Pair.Value) VT(nodes->Pair.Value); 878 } 879 } 880 } 881 }; 882 883 // TMapIterator ------------------------------------------------------------- 884 // A class to iterate over all the pairs in a TMap. 885 886 template<class KT, class VT, class MapType=TMap<KT,VT> > 887 class TMapIterator 888 { 889 public: TMapIterator(MapType & map)890 TMapIterator(MapType &map) 891 : Map(map), Position(0) 892 { 893 } 894 895 //======================================================================= 896 // 897 // NextPair 898 // 899 // Returns false if there are no more entries in the table. Otherwise, it 900 // returns true, and pair is filled with a pointer to the pair in the 901 // table. 902 // 903 //======================================================================= 904 NextPair(typename MapType::Pair * & pair)905 bool NextPair(typename MapType::Pair *&pair) 906 { 907 if (Position >= Map.Size) 908 { 909 return false; 910 } 911 do 912 { 913 if (!Map.Nodes[Position].IsNil()) 914 { 915 pair = reinterpret_cast<typename MapType::Pair *>(&Map.Nodes[Position].Pair); 916 Position += 1; 917 return true; 918 } 919 } while (++Position < Map.Size); 920 return false; 921 } 922 923 //======================================================================= 924 // 925 // Reset 926 // 927 // Restarts the iteration so you can do it all over again. 928 // 929 //======================================================================= 930 Reset()931 void Reset() 932 { 933 Position = 0; 934 } 935 936 protected: 937 MapType ⤅ 938 hash_t Position; 939 }; 940 941 // TMapConstIterator -------------------------------------------------------- 942 // Exactly the same as TMapIterator, but it works with a const TMap. 943 944 template<class KT, class VT, class MapType=TMap<KT,VT> > 945 class TMapConstIterator 946 { 947 public: TMapConstIterator(const MapType & map)948 TMapConstIterator(const MapType &map) 949 : Map(map), Position(0) 950 { 951 } 952 NextPair(typename MapType::ConstPair * & pair)953 bool NextPair(typename MapType::ConstPair *&pair) 954 { 955 if (Position >= Map.Size) 956 { 957 return false; 958 } 959 do 960 { 961 if (!Map.Nodes[Position].IsNil()) 962 { 963 pair = reinterpret_cast<typename MapType::Pair *>(&Map.Nodes[Position].Pair); 964 Position += 1; 965 return true; 966 } 967 } while (++Position < Map.Size); 968 return false; 969 } 970 971 protected: 972 const MapType ⤅ 973 hash_t Position; 974 }; 975 976 #endif //__TARRAY_H__ 977