CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

csutil/array.h

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 
00024 // Hack: Work around problems caused by #defining 'new'.
00025 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00026 # undef new
00027 #endif
00028 #include <new>
00029 
00030 #if defined(CS_MEMORY_TRACKER)
00031 #include "csutil/memdebug.h"
00032 #include <typeinfo>
00033 #endif
00034 
00038 template <class T1, class T2>
00039 class csOrdering
00040 {
00041 public:
00055   static int Compare(T1 const &r1, T2 const &r2)
00056   {
00057     if (r1 < r2) return -1;
00058     else if (r2 < r1) return 1;
00059     else return 0;
00060   }
00061 };
00062 
00063 // Define CSARRAY_INHIBIT_TYPED_KEYS if the compiler is too old or too buggy to
00064 // properly support templated functions within a templated class.  When this is
00065 // defined, rather than using a properly typed "key" argument, search methods
00066 // fall back to dealing with opaque void* for the "key" argument.  Note,
00067 // however, that this fact is completely hidden from the client; the client
00068 // simply creates csArrayCmp<> functors using correct types for the keys
00069 // regardless of whether the compiler actually supports this feature.  (The
00070 // MSVC6 compiler, for example, does support templated functions within a
00071 // template class but crashes and burns horribly when a function pointer or
00072 // functor is thrown into the mix; thus this should be defined for MSVC6.)
00073 #if !defined(CSARRAY_INHIBIT_TYPED_KEYS)
00074 
00084 template <class T, class K>
00085 class csArrayCmp
00086 {
00087 public:
00093   typedef int(*CF)(T const&, K const&);
00095   csArrayCmp(K const& k, CF c = DefaultCompare) : key(k), cmp(c) {}
00097   csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {}
00099   csArrayCmp& operator=(csArrayCmp const& o)
00100     { key = o.key; cmp = o.cmp; return *this; }
00109   int operator()(T const& r) const { return cmp(r, key); }
00111   operator CF() const { return cmp; }
00113   operator K const&() const { return key; }
00124   static int DefaultCompare(T const& r, K const& k)
00125     { return csOrdering<T,K>::Compare(r,k); }
00126 private:
00127   K key;
00128   CF cmp;
00129 };
00130 
00131 #define csArrayTemplate(K) template <class K>
00132 #define csArrayCmpDecl(T1,T2) csArrayCmp<T1,T2>
00133 #define csArrayCmpInvoke(C,R) C(R)
00134 
00135 #else // CSARRAY_INHIBIT_TYPED_KEYS
00136 
00137 class csArrayCmpAbstract
00138 {
00139 public:
00140   typedef int(*CF)(void const*, void const*);
00141   virtual int operator()(void const*) const = 0;
00142   virtual operator CF() const = 0;
00143 };
00144 
00145 template <class T, class K>
00146 class csArrayCmp : public csArrayCmpAbstract
00147 {
00148 public:
00149   typedef int(*CFTyped)(T const&, K const&);
00150   csArrayCmp(K const& k, CFTyped c = DefaultCompare) : key(k), cmp(CF(c)) {}
00151   csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {}
00152   csArrayCmp& operator=(csArrayCmp const& o)
00153     { key = o.key; cmp = o.cmp; return *this; }
00154   virtual int operator()(void const* p) const { return cmp(p, &key); }
00155   virtual operator CF() const { return cmp; }
00156   operator K const&() const { return key; }
00157   static int DefaultCompare(T const& r, K const& k)
00158     { return csOrdering<T,K>::Compare(r,k); }
00159 private:
00160   K key;
00161   CF cmp;
00162 };
00163 
00164 #define csArrayTemplate(K)
00165 #define csArrayCmpDecl(T1,T2) csArrayCmpAbstract const&
00166 #define csArrayCmpInvoke(C,R) C(&(R))
00167 
00168 #endif // CSARRAY_INHIBIT_TYPED_KEYS
00169 
00173 template <class T>
00174 class csArrayElementHandler
00175 {
00176 public:
00177   static void Construct (T* address, T const& src)
00178   {
00179     new (CS_STATIC_CAST(void*,address)) T(src);
00180   }
00181 
00182   static void Destroy (T* address)
00183   {
00184     address->~T();
00185   }
00186 
00187   static void InitRegion (T* address, int count)
00188   {
00189     for (int i = 0 ; i < count ; i++)
00190       Construct (address + i, T ());
00191   }
00192 };
00193 
00197 template <class T>
00198 class csArrayMemoryAllocator
00199 {
00200 public:
00201   static T* Alloc (int count)
00202   {
00203     return (T*)malloc (count * sizeof(T));
00204   }
00205 
00206   static void Free (T* mem)
00207   {
00208     free (mem);
00209   }
00210 
00211   // The 'relevantcount' parameter should be the number of items
00212   // in the old array that are initialized.
00213   static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
00214   {
00215     (void)relevantcount; (void)oldcount;
00216     return (T*)realloc (mem, newcount * sizeof(T));
00217   }
00218 };
00219 
00228 template <class T, class ElementHandler = csArrayElementHandler<T> >
00229 class csSafeCopyArrayMemoryAllocator
00230 {
00231 public:
00232   static T* Alloc (int count)
00233   {
00234     return (T*)malloc (count * sizeof(T));
00235   }
00236 
00237   static void Free (T* mem)
00238   {
00239     free (mem);
00240   }
00241 
00242   static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
00243   {
00244     if (newcount <= oldcount)
00245     {
00246       // Realloc is safe.
00247       T* newmem = (T*)realloc (mem, newcount * sizeof (T));
00248       CS_ASSERT (newmem == mem);
00249       return newmem;
00250     }
00251 
00252     T* newmem = Alloc (newcount);
00253     int i;
00254     for (i = 0 ; i < relevantcount ; i++)
00255     {
00256       ElementHandler::Construct (newmem + i, mem[i]);
00257       ElementHandler::Destroy (mem + i);
00258     }
00259     Free (mem);
00260     return newmem;
00261   }
00262 };
00263 
00264 
00272 template <class T,
00273         class ElementHandler = csArrayElementHandler<T>,
00274         class MemoryAllocator = csArrayMemoryAllocator<T> >
00275 class csArray
00276 {
00277 private:
00278   int count;
00279   int capacity;
00280   int threshold;
00281   T* root;
00282 # ifdef CS_MEMORY_TRACKER
00283   MemTrackerInfo* mti;
00284   void UpdateMti (int dn, int curcapacity)
00285   {
00286     if (!mti)
00287     {
00288       if (!curcapacity) return;
00289       char buf[255];
00290       sprintf (buf, "csArray<%s>", typeid (T).name());
00291       mti = mtiRegisterAlloc (1 * sizeof (T), buf);
00292       if (!mti) return;
00293       curcapacity--;
00294       if (curcapacity)
00295         mtiUpdateAmount (mti, curcapacity, curcapacity * sizeof (T));
00296       return;
00297     }
00298     mtiUpdateAmount (mti, dn, dn * sizeof (T));
00299   }
00300 # endif
00301 
00302 protected:
00307   void InitRegion (int start, int count)
00308   {
00309     ElementHandler::InitRegion (root+start, count);
00310   }
00311 
00312 private:
00314   void CopyFrom (const csArray& source)
00315   {
00316     if (&source != this)
00317     {
00318       DeleteAll ();
00319       threshold = source.threshold;
00320       SetLengthUnsafe (source.Length ());
00321       for (int i=0 ; i<source.Length() ; i++)
00322         ElementHandler::Construct (root + i, source[i]);
00323     }
00324   }
00325 
00326   // Adjust internal capacity of this array.
00327   void AdjustCapacity (int n)
00328   {
00329     if (n > capacity || (capacity > threshold && n < capacity - threshold))
00330     {
00331       n = ((n + threshold - 1) / threshold ) * threshold;
00332       if (root == 0)
00333       {
00334         root = MemoryAllocator::Alloc (n);
00335 #       ifdef CS_MEMORY_TRACKER
00336         UpdateMti (n, n);
00337 #       endif
00338       }
00339       else
00340       {
00341         root = MemoryAllocator::Realloc (root, count, capacity, n);
00342 #       ifdef CS_MEMORY_TRACKER
00343         UpdateMti (n-capacity, n);
00344 #       endif
00345       }
00346       capacity = n;
00347     }
00348   }
00349 
00350   // Set array length.  NOTE: Do not make this public since it does not
00351   // properly construct/destroy elements.  To safely truncate the array, use
00352   // Truncate().  To safely set the capacity, use SetCapacity().
00353   void SetLengthUnsafe (int n)
00354   {
00355     if (n > capacity)
00356       AdjustCapacity (n);
00357     count = n;
00358   }
00359 
00360 public:
00372   static int DefaultCompare(T const& r1, T const& r2)
00373   {
00374     return csOrdering<T,T>::Compare(r1,r2);
00375   }
00376 
00381   csArray (int icapacity = 0, int ithreshold = 0)
00382   {
00383 #   ifdef CS_MEMORY_TRACKER
00384     mti = 0;
00385 #   endif
00386     count = 0;
00387     capacity = (icapacity > 0 ? icapacity : 0);
00388     threshold = (ithreshold > 0 ? ithreshold : 16);
00389     if (capacity != 0)
00390     {
00391       root = MemoryAllocator::Alloc (capacity);
00392 #     ifdef CS_MEMORY_TRACKER
00393       UpdateMti (capacity, capacity);
00394 #     endif
00395     }
00396     else
00397     {
00398       root = 0;
00399     }
00400   }
00401 
00402   ~csArray ()
00403   {
00404     DeleteAll ();
00405   }
00406 
00408   csArray (const csArray& source)
00409   {
00410 #   ifdef CS_MEMORY_TRACKER
00411     mti = 0;
00412 #   endif
00413     root = 0;
00414     capacity = 0;
00415     count = 0;
00416     CopyFrom (source);
00417   }
00418   
00420   csArray<T,ElementHandler>& operator= (const csArray& other)
00421   {
00422     CopyFrom (other);
00423     return *this;
00424   }
00425 
00427   int Length () const
00428   {
00429     return count;
00430   }
00431 
00433   int Capacity () const
00434   {
00435     return capacity;
00436   }
00437 
00444   void TransferTo (csArray& destination)
00445   {
00446     if (&destination != this)
00447     {
00448       destination.DeleteAll ();
00449       destination.root = root;
00450       destination.count = count;
00451       destination.capacity = capacity;
00452       destination.threshold = threshold;
00453 #     ifdef CS_MEMORY_TRACKER
00454       destination.mti = mti;
00455       mti = 0;
00456 #     endif
00457       root = 0;
00458       capacity = count = 0;
00459     }
00460   }
00461 
00469   void SetLength (int n, T const& what)
00470   {
00471     if (n <= count)
00472     {
00473       Truncate (n);
00474     }
00475     else
00476     {
00477       int old_len = Length ();
00478       SetLengthUnsafe (n);
00479       for (int i = old_len ; i < n ; i++)
00480         ElementHandler::Construct (root + i, what);
00481     }
00482   }
00483 
00485   void SetLength (int n)
00486   {
00487     if (n <= count)
00488     {
00489       Truncate (n);
00490     }
00491     else
00492     {
00493       int old_len = Length ();
00494       SetLengthUnsafe (n);
00495       ElementHandler::InitRegion (root + old_len, n-old_len);
00496     }
00497   }
00498 
00500   T& Get (int n)
00501   {
00502     CS_ASSERT (n >= 0 && n < count);
00503     return root[n];
00504   }
00505 
00507   T const& Get (int n) const
00508   {
00509     CS_ASSERT (n >= 0 && n < count);
00510     return root[n];
00511   }
00512 
00517   T& GetExtend (int n)
00518   {
00519     CS_ASSERT (n >= 0);
00520     if (n >= count)
00521       SetLength (n+1);
00522     return root[n];
00523   }
00524 
00526   T& operator [] (int n)
00527   {
00528     return Get(n);
00529   }
00530 
00532   T const& operator [] (int n) const
00533   {
00534     return Get(n);
00535   }
00536 
00538   void Put (int n, T const& what)
00539   {
00540     CS_ASSERT (n >= 0);
00541     if (n >= count)
00542       SetLength (n+1);
00543     ElementHandler::Destroy (root + n);
00544     ElementHandler::Construct (root + n, what);
00545   }
00546 
00550   csArrayTemplate(K)
00551   int FindKey (csArrayCmpDecl(T,K) comparekey) const
00552   {
00553     for (int i = 0 ; i < Length () ; i++)
00554       if (csArrayCmpInvoke(comparekey, root[i]) == 0)
00555         return i;
00556     return -1;
00557   }
00558 
00560   int Push (T const& what)
00561   {
00562     if (((&what >= root) && (&what < root + Length())) && 
00563       (capacity < count + 1))
00564     {
00565       /*
00566         Special case: An element from this very array is pushed, and a 
00567         reallocation is needed. This could cause the passed ref to the
00568         element to be pushed to be read from deleted memory. Work
00569         around this.
00570        */
00571       int whatIndex = &what - root;
00572       SetLengthUnsafe (count + 1);
00573       ElementHandler::Construct (root + count - 1, root[whatIndex]);
00574     }
00575     else
00576     {
00577       SetLengthUnsafe (count + 1);
00578       ElementHandler::Construct (root + count - 1, what);
00579     }
00580     return count - 1;
00581   }
00582 
00583   /*
00584    * Push a element onto the tail end of the array if not already present.
00585    * Returns index of newly pushed element or index of already present element.
00586    */
00587   int PushSmart (T const& what)
00588   {
00589     int const n = Find (what);
00590     return (n < 0) ? Push (what) : n;
00591   }
00592 
00594   T Pop ()
00595   {
00596     CS_ASSERT (count > 0);
00597     T ret(root [count - 1]);
00598     ElementHandler::Destroy (root + count - 1);
00599     SetLengthUnsafe (count - 1);
00600     return ret;
00601   }
00602 
00604   T const& Top () const
00605   {
00606     CS_ASSERT (count > 0);
00607     return root [count - 1];
00608   }
00609 
00611   T& Top ()
00612   {
00613     CS_ASSERT (count > 0);
00614     return root [count - 1];
00615   }
00616 
00618   bool Insert (int n, T const& item)
00619   {
00620     if (n <= count)
00621     {
00622       SetLengthUnsafe (count + 1); // Increments 'count' as a side-effect.
00623       int const nmove = (count - n - 1);
00624       if (nmove > 0)
00625         memmove (root + n + 1, root + n, nmove * sizeof(T));
00626       ElementHandler::Construct (root + n, item);
00627       return true;
00628     }
00629     else
00630       return false;
00631   }
00632 
00636   csArray<T> Section (int low, int high) const
00637   {
00638     CS_ASSERT (low >= 0 && high < count && high >= low);
00639     csArray<T> sect (high - low + 1);
00640     for (int i = low; i <= high; i++) sect.Push (root[i]);
00641     return sect;
00642   }
00643 
00648   csArrayTemplate(K)
00649   int FindSortedKey (csArrayCmpDecl(T,K) comparekey, int* candidate = 0) const
00650   {
00651     int m = 0, l = 0, r = Length () - 1;
00652     while (l <= r)
00653     {
00654       m = (l + r) / 2;
00655       int cmp = csArrayCmpInvoke(comparekey, root[m]);
00656       if (cmp == 0)
00657       {
00658         if (candidate) *candidate = -1;
00659         return m;
00660       }
00661       else if (cmp < 0)
00662         l = m + 1;
00663       else
00664         r = m - 1;
00665     }
00666     if (candidate) *candidate = m;
00667     return -1;
00668   }
00669 
00674   int InsertSorted (const T& item,
00675     int (*compare)(T const&, T const&) = DefaultCompare,
00676     int* equal_index = 0)
00677   {
00678     int m = 0, l = 0, r = Length () - 1;
00679     while (l <= r)
00680     {
00681       m = (l + r) / 2;
00682       int cmp = compare (root [m], item);
00683 
00684       if (cmp == 0)
00685       {
00686         if (equal_index) *equal_index = m;
00687         Insert (++m, item);
00688         return m;
00689       }
00690       else if (cmp < 0)
00691         l = m + 1;
00692       else
00693         r = m - 1;
00694     }
00695     if (r == m)
00696       m++;
00697     if (equal_index) *equal_index = -1;
00698     Insert (m, item);
00699     return m;
00700   }
00701 
00703   int Find (T const& which) const
00704   {
00705     for (int i = 0 ; i < Length () ; i++)
00706       if (root[i] == which)
00707         return i;
00708     return -1;
00709   }
00710 
00717   int GetIndex (const T* which) const
00718   {
00719     return which-root;
00720   }
00721 
00725   void Sort (int (*compare)(T const&, T const&) = DefaultCompare)
00726   {
00727     qsort (root, Length(), sizeof(T),
00728       (int (*)(void const*, void const*))compare);
00729   }
00730 
00734   void DeleteAll ()
00735   {
00736     if (root)
00737     {
00738       int i;
00739       for (i = 0 ; i < count ; i++)
00740         ElementHandler::Destroy (root + i);
00741       MemoryAllocator::Free (root);
00742 #     ifdef CS_MEMORY_TRACKER
00743       UpdateMti (-capacity, 0);
00744 #     endif
00745       root = 0;
00746       capacity = count = 0;
00747     }
00748   }
00749 
00755   void Truncate (int n)
00756   {
00757     CS_ASSERT(n >= 0);
00758     CS_ASSERT(n <= count);
00759     if (n < count)
00760     {
00761       for (int i = n; i < count; i++)
00762         ElementHandler::Destroy (root + i);
00763       SetLengthUnsafe(n);
00764     }
00765   }
00766 
00772   void Empty ()
00773   {
00774     Truncate (0);
00775   }
00776 
00783   void SetCapacity (int n)
00784   {
00785     if (n > Length ())
00786       AdjustCapacity (n);
00787   }
00788 
00794   void ShrinkBestFit ()
00795   {
00796     if (count == 0)
00797     {
00798       DeleteAll ();
00799     }
00800     else if (count != capacity)
00801     {
00802       root = MemoryAllocator::Realloc (root, count, capacity, count);
00803 #     ifdef CS_MEMORY_TRACKER
00804       UpdateMti (count-capacity, count);
00805 #     endif
00806       capacity = count;
00807     }
00808   }
00809 
00811   bool DeleteIndex (int n)
00812   {
00813     if (n >= 0 && n < count)
00814     {
00815       int const ncount = count - 1;
00816       int const nmove = ncount - n;
00817       ElementHandler::Destroy (root + n);
00818       if (nmove > 0)
00819         memmove (root + n, root + n + 1, nmove * sizeof(T));
00820       SetLengthUnsafe (ncount);
00821       return true;
00822     }
00823     else
00824       return false;
00825   }
00826 
00831   void DeleteRange (int start, int end)
00832   {
00833     if (start >= count) return;
00834     if (end < 0) return;
00835     if (start < 0) start = 0;
00836     if (end >= count) end = count-1;
00837     int i;
00838     for (i = start ; i < end ; i++)
00839       ElementHandler::Destroy (root + i);
00840 
00841     int const range_size = end-start+1;
00842     int const ncount = count - range_size;
00843     int const nmove = count - end - 1;
00844     if (nmove > 0)
00845       memmove (root + start, root + start + range_size, nmove * sizeof(T));
00846     SetLengthUnsafe (ncount);
00847   }
00848 
00850   bool Delete (T const& item)
00851   {
00852     int const n = Find (item);
00853     if (n >= 0)
00854       return DeleteIndex (n);
00855     return false;
00856   }
00857 
00859   class Iterator
00860   {
00861   public:
00863     Iterator(Iterator const& r) :
00864       currentelem(r.currentelem), array(r.array) {}
00865 
00867     Iterator& operator=(Iterator const& r)
00868     { currentelem = r.currentelem; array = r.array; return *this; }
00869 
00871     bool HasNext()
00872     { return currentelem < array.Length(); }
00873 
00875     const T& Next()
00876     { return array.Get(currentelem++); }
00877 
00879     void Reset()
00880     { currentelem = 0; }
00881   protected:
00882     Iterator(const csArray<T, ElementHandler>& newarray)
00883         : currentelem(0), array(newarray)
00884     { }
00885     friend class csArray<T, ElementHandler>;
00886     
00887   private:
00888     int currentelem;
00889     const csArray<T, ElementHandler>& array;
00890   };
00891 
00893   Iterator GetIterator() const
00894   { return Iterator(*this); }
00895 };
00896 
00902 template <class T>
00903 class csSafeCopyArray
00904         : public csArray<T,
00905                 csArrayElementHandler<T>,
00906                 csSafeCopyArrayMemoryAllocator<T> >
00907 {
00908 public:
00913   csSafeCopyArray (int ilimit = 0, int ithreshold = 0)
00914         : csArray<T, csArrayElementHandler<T>,
00915                      csSafeCopyArrayMemoryAllocator<T> > (ilimit, ithreshold)
00916   {
00917   }
00918 };
00919 
00920 #if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
00921 # define new CS_EXTENSIVE_MEMDEBUG_NEW
00922 #endif
00923 
00924 #endif

Generated for Crystal Space by doxygen 1.2.18