CrystalSpace

Public API Reference

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