Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
array.h
Go to the documentation of this file.00001 /* 00002 Crystal Space Generic Array Template 00003 Copyright (C) 2003 by Matze Braun 00004 Copyright (C) 2003 by Jorrit Tyberghein 00005 Copyright (C) 2003,2004 by Eric Sunshine 00006 00007 This library is free software; you can redistribute it and/or 00008 modify it under the terms of the GNU Library General Public 00009 License as published by the Free Software Foundation; either 00010 version 2 of the License, or (at your option) any later version. 00011 00012 This library is distributed in the hope that it will be useful, 00013 but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 Library General Public License for more details. 00016 00017 You should have received a copy of the GNU Library General Public 00018 License along with this library; if not, write to the Free 00019 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 */ 00021 #ifndef __CSUTIL_ARRAY_H__ 00022 #define __CSUTIL_ARRAY_H__ 00023 00028 // Hack: Work around problems caused by #defining 'new'. 00029 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 00030 # undef new 00031 #endif 00032 #include <new> 00033 00034 #if defined(CS_MEMORY_TRACKER) 00035 #include "csutil/memdebug.h" 00036 #include "csutil/snprintf.h" 00037 #include <typeinfo> 00038 #endif 00039 00043 template <class T1, class T2> 00044 class csOrdering 00045 { 00046 public: 00060 static int Compare(T1 const &r1, T2 const &r2) 00061 { 00062 if (r1 < r2) return -1; 00063 else if (r2 < r1) return 1; 00064 else return 0; 00065 } 00066 }; 00067 00068 // Define CSARRAY_INHIBIT_TYPED_KEYS if the compiler is too old or too buggy to 00069 // properly support templated functions within a templated class. When this is 00070 // defined, rather than using a properly typed "key" argument, search methods 00071 // fall back to dealing with opaque void* for the "key" argument. Note, 00072 // however, that this fact is completely hidden from the client; the client 00073 // simply creates csArrayCmp<> functors using correct types for the keys 00074 // regardless of whether the compiler actually supports this feature. (The 00075 // MSVC6 compiler, for example, does support templated functions within a 00076 // template class but crashes and burns horribly when a function pointer or 00077 // functor is thrown into the mix; thus this should be defined for MSVC6.) 00078 #if !defined(CSARRAY_INHIBIT_TYPED_KEYS) 00079 00089 template <class T, class K> 00090 class csArrayCmp 00091 { 00092 public: 00098 typedef int(*CF)(T const&, K const&); 00100 csArrayCmp(K const& k, CF c = DefaultCompare) : key(k), cmp(c) {} 00102 csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {} 00104 csArrayCmp& operator=(csArrayCmp const& o) 00105 { key = o.key; cmp = o.cmp; return *this; } 00114 int operator()(T const& r) const { return cmp(r, key); } 00116 operator CF() const { return cmp; } 00118 operator K const&() const { return key; } 00129 static int DefaultCompare(T const& r, K const& k) 00130 { return csOrdering<T,K>::Compare(r,k); } 00131 private: 00132 K key; 00133 CF cmp; 00134 }; 00135 00136 #define csArrayTemplate(K) template <class K> 00137 #define csArrayCmpDecl(T1,T2) csArrayCmp<T1,T2> 00138 #define csArrayCmpInvoke(C,R) C(R) 00139 00140 #else // CSARRAY_INHIBIT_TYPED_KEYS 00141 00142 class csArrayCmpAbstract 00143 { 00144 public: 00145 typedef int(*CF)(void const*, void const*); 00146 virtual int operator()(void const*) const = 0; 00147 virtual operator CF() const = 0; 00148 }; 00149 00150 template <class T, class K> 00151 class csArrayCmp : public csArrayCmpAbstract 00152 { 00153 public: 00154 typedef int(*CFTyped)(T const&, K const&); 00155 csArrayCmp(K const& k, CFTyped c = DefaultCompare) : key(k), cmp(CF(c)) {} 00156 csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {} 00157 csArrayCmp& operator=(csArrayCmp const& o) 00158 { key = o.key; cmp = o.cmp; return *this; } 00159 virtual int operator()(void const* p) const { return cmp(p, &key); } 00160 virtual operator CF() const { return cmp; } 00161 operator K const&() const { return key; } 00162 static int DefaultCompare(T const& r, K const& k) 00163 { return csOrdering<T,K>::Compare(r,k); } 00164 private: 00165 K key; 00166 CF cmp; 00167 }; 00168 00169 #define csArrayTemplate(K) 00170 #define csArrayCmpDecl(T1,T2) csArrayCmpAbstract const& 00171 #define csArrayCmpInvoke(C,R) C(&(R)) 00172 00173 #endif // CSARRAY_INHIBIT_TYPED_KEYS 00174 00178 template <class T> 00179 class csArrayElementHandler 00180 { 00181 public: 00182 static void Construct (T* address) 00183 { 00184 new (CS_STATIC_CAST(void*,address)) T(); 00185 } 00186 00187 static void Construct (T* address, T const& src) 00188 { 00189 new (CS_STATIC_CAST(void*,address)) T(src); 00190 } 00191 00192 static void Destroy (T* address) 00193 { 00194 address->~T(); 00195 } 00196 00197 static void InitRegion (T* address, size_t count) 00198 { 00199 for (size_t i = 0 ; i < count ; i++) 00200 Construct (address + i); 00201 } 00202 }; 00203 00207 template <class T> 00208 class csArrayMemoryAllocator 00209 { 00210 public: 00211 static T* Alloc (size_t count) 00212 { 00213 return (T*)malloc (count * sizeof(T)); 00214 } 00215 00216 static void Free (T* mem) 00217 { 00218 free (mem); 00219 } 00220 00221 // The 'relevantcount' parameter should be the number of items 00222 // in the old array that are initialized. 00223 static T* Realloc (T* mem, size_t relevantcount, size_t oldcount, 00224 size_t newcount) 00225 { 00226 (void)relevantcount; (void)oldcount; 00227 return (T*)realloc (mem, newcount * sizeof(T)); 00228 } 00229 00230 // Move memory. 00231 static void MemMove (T* mem, size_t dest, size_t src, size_t count) 00232 { 00233 memmove (mem + dest, mem + src, count * sizeof(T)); 00234 } 00235 }; 00236 00245 template <class T, class ElementHandler = csArrayElementHandler<T> > 00246 class csSafeCopyArrayMemoryAllocator 00247 { 00248 public: 00249 static T* Alloc (size_t count) 00250 { 00251 return (T*)malloc (count * sizeof(T)); 00252 } 00253 00254 static void Free (T* mem) 00255 { 00256 free (mem); 00257 } 00258 00259 static T* Realloc (T* mem, size_t relevantcount, size_t oldcount, 00260 size_t newcount) 00261 { 00262 if (newcount <= oldcount) 00263 { 00264 // Realloc is safe. 00265 T* newmem = (T*)realloc (mem, newcount * sizeof (T)); 00266 CS_ASSERT (newmem == mem); 00267 return newmem; 00268 } 00269 00270 T* newmem = Alloc (newcount); 00271 size_t i; 00272 for (i = 0 ; i < relevantcount ; i++) 00273 { 00274 ElementHandler::Construct (newmem + i, mem[i]); 00275 ElementHandler::Destroy (mem + i); 00276 } 00277 Free (mem); 00278 return newmem; 00279 } 00280 00281 static void MemMove (T* mem, size_t dest, size_t src, size_t count) 00282 { 00283 size_t i; 00284 if (dest < src) 00285 { 00286 for (i = 0 ; i < count ; i++) 00287 { 00288 ElementHandler::Construct (mem + dest + i, mem[src + i]); 00289 ElementHandler::Destroy (mem + src + i); 00290 } 00291 } 00292 else 00293 { 00294 i = count; 00295 while (i > 0) 00296 { 00297 i--; 00298 ElementHandler::Construct (mem + dest + i, mem[src + i]); 00299 ElementHandler::Destroy (mem + src + i); 00300 } 00301 } 00302 } 00303 }; 00304 00309 const size_t csArrayItemNotFound = (size_t)-1; 00310 00318 template <class T, 00319 class ElementHandler = csArrayElementHandler<T>, 00320 class MemoryAllocator = csArrayMemoryAllocator<T> > 00321 class csArray 00322 { 00323 private: 00324 size_t count; 00325 size_t capacity; 00326 size_t threshold; 00327 T* root; 00328 # ifdef CS_MEMORY_TRACKER 00329 MemTrackerInfo* mti; 00330 void UpdateMti (int dn, int curcapacity) 00331 { 00332 if (!mti) 00333 { 00334 if (!curcapacity) return; 00335 char buf[1024]; 00336 cs_snprintf (buf, sizeof (buf), "csArray<%s>", typeid (T).name()); 00337 mti = mtiRegisterAlloc (1 * sizeof (T), buf); 00338 if (!mti) return; 00339 curcapacity--; 00340 if (curcapacity) 00341 mtiUpdateAmount (mti, curcapacity, curcapacity * sizeof (T)); 00342 return; 00343 } 00344 mtiUpdateAmount (mti, dn, dn * sizeof (T)); 00345 } 00346 # endif 00347 00348 protected: 00353 void InitRegion (size_t start, size_t count) 00354 { 00355 ElementHandler::InitRegion (root+start, count); 00356 } 00357 00358 private: 00360 void CopyFrom (const csArray& source) 00361 { 00362 if (&source != this) 00363 { 00364 DeleteAll (); 00365 threshold = source.threshold; 00366 SetLengthUnsafe (source.Length ()); 00367 for (size_t i=0 ; i<source.Length() ; i++) 00368 ElementHandler::Construct (root + i, source[i]); 00369 } 00370 } 00371 00373 void InternalSetCapacity (size_t n) 00374 { 00375 if (root == 0) 00376 { 00377 root = MemoryAllocator::Alloc (n); 00378 # ifdef CS_MEMORY_TRACKER 00379 UpdateMti (n, n); 00380 # endif 00381 } 00382 else 00383 { 00384 root = MemoryAllocator::Realloc (root, count, capacity, n); 00385 # ifdef CS_MEMORY_TRACKER 00386 UpdateMti (n-capacity, n); 00387 # endif 00388 } 00389 capacity = n; 00390 } 00391 00396 void AdjustCapacity (size_t n) 00397 { 00398 if (n > capacity || (capacity > threshold && n < capacity - threshold)) 00399 { 00400 InternalSetCapacity (((n + threshold - 1) / threshold ) * threshold); 00401 } 00402 } 00403 00409 void SetLengthUnsafe (size_t n) 00410 { 00411 if (n > capacity) 00412 AdjustCapacity (n); 00413 count = n; 00414 } 00415 00416 public: 00428 static int DefaultCompare(T const& r1, T const& r2) 00429 { 00430 return csOrdering<T,T>::Compare(r1,r2); 00431 } 00432 00437 csArray (size_t icapacity = 0, size_t ithreshold = 0) 00438 { 00439 # ifdef CS_MEMORY_TRACKER 00440 mti = 0; 00441 # endif 00442 count = 0; 00443 capacity = (icapacity > 0 ? icapacity : 0); 00444 threshold = (ithreshold > 0 ? ithreshold : 16); 00445 if (capacity != 0) 00446 { 00447 root = MemoryAllocator::Alloc (capacity); 00448 # ifdef CS_MEMORY_TRACKER 00449 UpdateMti (capacity, capacity); 00450 # endif 00451 } 00452 else 00453 { 00454 root = 0; 00455 } 00456 } 00457 00459 ~csArray () 00460 { 00461 DeleteAll (); 00462 } 00463 00465 csArray (const csArray& source) 00466 { 00467 # ifdef CS_MEMORY_TRACKER 00468 mti = 0; 00469 # endif 00470 root = 0; 00471 capacity = 0; 00472 count = 0; 00473 CopyFrom (source); 00474 } 00475 00477 csArray<T,ElementHandler>& operator= (const csArray& other) 00478 { 00479 CopyFrom (other); 00480 return *this; 00481 } 00482 00484 size_t Length () const 00485 { 00486 return count; 00487 } 00488 00490 size_t Capacity () const 00491 { 00492 return capacity; 00493 } 00494 00501 void TransferTo (csArray& destination) 00502 { 00503 if (&destination != this) 00504 { 00505 destination.DeleteAll (); 00506 destination.root = root; 00507 destination.count = count; 00508 destination.capacity = capacity; 00509 destination.threshold = threshold; 00510 # ifdef CS_MEMORY_TRACKER 00511 destination.mti = mti; 00512 mti = 0; 00513 # endif 00514 root = 0; 00515 capacity = count = 0; 00516 } 00517 } 00518 00526 void SetLength (size_t n, T const& what) 00527 { 00528 if (n <= count) 00529 { 00530 Truncate (n); 00531 } 00532 else 00533 { 00534 size_t old_len = Length (); 00535 SetLengthUnsafe (n); 00536 for (size_t i = old_len ; i < n ; i++) 00537 ElementHandler::Construct (root + i, what); 00538 } 00539 } 00540 00542 void SetLength (size_t n) 00543 { 00544 if (n <= count) 00545 { 00546 Truncate (n); 00547 } 00548 else 00549 { 00550 size_t old_len = Length (); 00551 SetLengthUnsafe (n); 00552 ElementHandler::InitRegion (root + old_len, n-old_len); 00553 } 00554 } 00555 00557 T& Get (size_t n) 00558 { 00559 CS_ASSERT (n < count); 00560 return root[n]; 00561 } 00562 00564 T const& Get (size_t n) const 00565 { 00566 CS_ASSERT (n < count); 00567 return root[n]; 00568 } 00569 00574 T& GetExtend (size_t n) 00575 { 00576 if (n >= count) 00577 SetLength (n+1); 00578 return root[n]; 00579 } 00580 00582 T& operator [] (size_t n) 00583 { 00584 return Get(n); 00585 } 00586 00588 T const& operator [] (size_t n) const 00589 { 00590 return Get(n); 00591 } 00592 00594 void Put (size_t n, T const& what) 00595 { 00596 if (n >= count) 00597 SetLength (n+1); 00598 ElementHandler::Destroy (root + n); 00599 ElementHandler::Construct (root + n, what); 00600 } 00601 00605 csArrayTemplate(K) 00606 size_t FindKey (csArrayCmpDecl(T,K) comparekey) const 00607 { 00608 for (size_t i = 0 ; i < Length () ; i++) 00609 if (csArrayCmpInvoke(comparekey, root[i]) == 0) 00610 return i; 00611 return csArrayItemNotFound; 00612 } 00613 00615 size_t Push (T const& what) 00616 { 00617 if (((&what >= root) && (&what < root + Length())) && 00618 (capacity < count + 1)) 00619 { 00620 /* 00621 Special case: An element from this very array is pushed, and a 00622 reallocation is needed. This could cause the passed ref to the 00623 element to be pushed to be read from deleted memory. Work 00624 around this. 00625 */ 00626 size_t whatIndex = &what - root; 00627 SetLengthUnsafe (count + 1); 00628 ElementHandler::Construct (root + count - 1, root[whatIndex]); 00629 } 00630 else 00631 { 00632 SetLengthUnsafe (count + 1); 00633 ElementHandler::Construct (root + count - 1, what); 00634 } 00635 return count - 1; 00636 } 00637 00642 size_t PushSmart (T const& what) 00643 { 00644 size_t const n = Find (what); 00645 return (n == csArrayItemNotFound) ? Push (what) : n; 00646 } 00647 00649 T Pop () 00650 { 00651 CS_ASSERT (count > 0); 00652 T ret(root [count - 1]); 00653 ElementHandler::Destroy (root + count - 1); 00654 SetLengthUnsafe (count - 1); 00655 return ret; 00656 } 00657 00659 T const& Top () const 00660 { 00661 CS_ASSERT (count > 0); 00662 return root [count - 1]; 00663 } 00664 00666 T& Top () 00667 { 00668 CS_ASSERT (count > 0); 00669 return root [count - 1]; 00670 } 00671 00673 bool Insert (size_t n, T const& item) 00674 { 00675 if (n <= count) 00676 { 00677 SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect. 00678 size_t const nmove = (count - n - 1); 00679 if (nmove > 0) 00680 MemoryAllocator::MemMove (root, n+1, n, nmove); 00681 ElementHandler::Construct (root + n, item); 00682 return true; 00683 } 00684 else 00685 return false; 00686 } 00687 00691 csArray<T> Section (size_t low, size_t high) const 00692 { 00693 CS_ASSERT (low >= 0 && high < count && high >= low); 00694 csArray<T> sect (high - low + 1); 00695 for (size_t i = low; i <= high; i++) sect.Push (root[i]); 00696 return sect; 00697 } 00698 00704 csArrayTemplate(K) 00705 size_t FindSortedKey (csArrayCmpDecl(T,K) comparekey, 00706 size_t* candidate = 0) const 00707 { 00708 size_t m = 0, l = 0, r = Length (); 00709 while (l < r) 00710 { 00711 m = (l + r) / 2; 00712 int cmp = csArrayCmpInvoke(comparekey, root[m]); 00713 if (cmp == 0) 00714 { 00715 if (candidate) *candidate = csArrayItemNotFound; 00716 return m; 00717 } 00718 else if (cmp < 0) 00719 l = m + 1; 00720 else 00721 r = m; 00722 } 00723 if (candidate) *candidate = m; 00724 return csArrayItemNotFound; 00725 } 00726 00731 size_t InsertSorted (const T& item, 00732 int (*compare)(T const&, T const&) = DefaultCompare, 00733 size_t* equal_index = 0) 00734 { 00735 size_t m = 0, l = 0, r = Length (); 00736 while (l < r) 00737 { 00738 m = (l + r) / 2; 00739 int cmp = compare (root [m], item); 00740 00741 if (cmp == 0) 00742 { 00743 if (equal_index) *equal_index = m; 00744 Insert (++m, item); 00745 return m; 00746 } 00747 else if (cmp < 0) 00748 l = m + 1; 00749 else 00750 r = m; 00751 } 00752 //if (m == r) 00753 // m++; 00754 if ((m + 1) == r) 00755 m++; 00756 if (equal_index) *equal_index = csArrayItemNotFound; 00757 Insert (m, item); 00758 return m; 00759 } 00760 00765 size_t Find (T const& which) const 00766 { 00767 for (size_t i = 0 ; i < Length () ; i++) 00768 if (root[i] == which) 00769 return i; 00770 return csArrayItemNotFound; 00771 } 00772 00779 size_t GetIndex (const T* which) const 00780 { 00781 CS_ASSERT (which >= root); 00782 CS_ASSERT (which < (root + count)); 00783 return which-root; 00784 } 00785 00789 void Sort (int (*compare)(T const&, T const&) = DefaultCompare) 00790 { 00791 qsort (root, Length(), sizeof(T), 00792 (int (*)(void const*, void const*))compare); 00793 } 00794 00798 void DeleteAll () 00799 { 00800 if (root) 00801 { 00802 size_t i; 00803 for (i = 0 ; i < count ; i++) 00804 ElementHandler::Destroy (root + i); 00805 MemoryAllocator::Free (root); 00806 # ifdef CS_MEMORY_TRACKER 00807 UpdateMti (-capacity, 0); 00808 # endif 00809 root = 0; 00810 capacity = count = 0; 00811 } 00812 } 00813 00819 void Truncate (size_t n) 00820 { 00821 CS_ASSERT(n <= count); 00822 if (n < count) 00823 { 00824 for (size_t i = n; i < count; i++) 00825 ElementHandler::Destroy (root + i); 00826 SetLengthUnsafe(n); 00827 } 00828 } 00829 00835 void Empty () 00836 { 00837 Truncate (0); 00838 } 00839 00846 void SetCapacity (size_t n) 00847 { 00848 if (n > Length ()) 00849 InternalSetCapacity (n); 00850 } 00851 00857 void ShrinkBestFit () 00858 { 00859 if (count == 0) 00860 { 00861 DeleteAll (); 00862 } 00863 else if (count != capacity) 00864 { 00865 root = MemoryAllocator::Realloc (root, count, capacity, count); 00866 # ifdef CS_MEMORY_TRACKER 00867 UpdateMti (count-capacity, count); 00868 # endif 00869 capacity = count; 00870 } 00871 } 00872 00874 bool DeleteIndex (size_t n) 00875 { 00876 if (n < count) 00877 { 00878 size_t const ncount = count - 1; 00879 size_t const nmove = ncount - n; 00880 ElementHandler::Destroy (root + n); 00881 if (nmove > 0) 00882 MemoryAllocator::MemMove (root, n, n+1, nmove); 00883 SetLengthUnsafe (ncount); 00884 return true; 00885 } 00886 else 00887 return false; 00888 } 00889 00896 bool DeleteIndexFast (size_t n) 00897 { 00898 if (n < count) 00899 { 00900 size_t const ncount = count - 1; 00901 size_t const nmove = ncount - n; 00902 ElementHandler::Destroy (root + n); 00903 if (nmove > 0) 00904 MemoryAllocator::MemMove (root, n, ncount, 1); 00905 SetLengthUnsafe (ncount); 00906 return true; 00907 } 00908 else 00909 return false; 00910 } 00911 00916 void DeleteRange (size_t start, size_t end) 00917 { 00918 if (start >= count) return; 00919 // Treat 'csArrayItemNotFound' as invalid indices, do nothing. 00920 // @@@ Assert that? 00921 if (end == csArrayItemNotFound) return; 00922 if (start == csArrayItemNotFound) return;//start = 0; 00923 if (end >= count) end = count - 1; 00924 size_t i; 00925 for (i = start ; i <= end ; i++) 00926 ElementHandler::Destroy (root + i); 00927 00928 size_t const range_size = end - start + 1; 00929 size_t const ncount = count - range_size; 00930 size_t const nmove = count - end - 1; 00931 if (nmove > 0) 00932 MemoryAllocator::MemMove (root, start, start + range_size, nmove); 00933 SetLengthUnsafe (ncount); 00934 } 00935 00937 bool Delete (T const& item) 00938 { 00939 size_t const n = Find (item); 00940 if (n != csArrayItemNotFound) 00941 return DeleteIndex (n); 00942 return false; 00943 } 00944 00951 bool DeleteFast (T const& item) 00952 { 00953 size_t const n = Find (item); 00954 if (n != csArrayItemNotFound) 00955 return DeleteIndexFast (n); 00956 return false; 00957 } 00958 00960 class Iterator 00961 { 00962 public: 00964 Iterator(Iterator const& r) : 00965 currentelem(r.currentelem), array(r.array) {} 00966 00968 Iterator& operator=(Iterator const& r) 00969 { currentelem = r.currentelem; array = r.array; return *this; } 00970 00972 bool HasNext() 00973 { return currentelem < array.Length(); } 00974 00976 const T& Next() 00977 { return array.Get(currentelem++); } 00978 00980 void Reset() 00981 { currentelem = 0; } 00982 protected: 00983 Iterator(const csArray<T, ElementHandler>& newarray) 00984 : currentelem(0), array(newarray) 00985 { } 00986 friend class csArray<T, ElementHandler>; 00987 00988 private: 00989 size_t currentelem; 00990 const csArray<T, ElementHandler>& array; 00991 }; 00992 00994 Iterator GetIterator() const 00995 { return Iterator(*this); } 00996 }; 00997 01003 template <class T> 01004 class csSafeCopyArray 01005 : public csArray<T, 01006 csArrayElementHandler<T>, 01007 csSafeCopyArrayMemoryAllocator<T> > 01008 { 01009 public: 01014 csSafeCopyArray (size_t ilimit = 0, size_t ithreshold = 0) 01015 : csArray<T, csArrayElementHandler<T>, 01016 csSafeCopyArrayMemoryAllocator<T> > (ilimit, ithreshold) 01017 { 01018 } 01019 }; 01020 01021 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER) 01022 # define new CS_EXTENSIVE_MEMDEBUG_NEW 01023 #endif 01024 01025 #endif
Generated for Crystal Space by doxygen 1.3.9.1