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