- Main Page
- Related Pages
- Modules
- Classes
- Files

# Array.h

Go to the documentation of this file.

    00001 #ifndef _ARRAY_H_
    00002 #define _ARRAY_H_
    00003 //
    00004
    00005 //
    00006 // Copyright (C) 2004-2006  Autodesk, Inc.
    00007 //
    00008 // This library is free software; you can redistribute it and/or
    00009 // modify it under the terms of version 2.1 of the GNU Lesser
    00010 // General Public License as published by the Free Software Foundation.
    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 // Lesser General Public License for more details.
    00016 //
    00017 // You should have received a copy of the GNU Lesser General Public
    00018 // License along with this library; if not, write to the Free Software
    00019 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
    00020 //
    00021
    00022 #ifdef _WIN32
    00023 #pragma once
    00024 #endif
    00025
    00026 #include <Common/ArrayHelper.h>
    00027
    00028
    00029 // Template for dynamic array.  It supports:
    00030 //  - shared ownership, via reference counting
    00031 //  - single allocation on heap for entire structure (no internal indirection)
    00032 //  - dynamic growth with infrequent reallocation
    00033 //  - hiding "new" and "delete" from callers that may have redefined these operators
    00034 //
    00035 // This class integrates its own needed member variables within
    00036 // the array itself.  This approach is very space efficient, as
    00037 // it avoids the overhead of a level of indirection; there is no
    00038 // pointer to an internal, owned array.
    00039 //
    00040 // The tradeoffs to get these features are:
    00041 //  - any method call that could cause re-allocation is static,
    00042 //    returning a (possibly new) location for the array object
    00043 //  - one cannot call re-allocating methods if the object is shared
    00044 //  - this class must never contain virtual methods (thus does its own reference counting)
    00045 //  - the allocation mechanism delegates to a helper class
    00046 //  - it is not typesafe for objects that cannot safely be moved around
    00047 //    in memory or which have non-empty destructors (it is safe for basic
    00048 //    types and most structs).
    00049 //
    00050 // Example:
    00051 //      FdoIntArray* ints = FdoIntArray::Create();
    00052 //      ints = FdoIntArray::Append(ints, 7);
    00053 //      FdoInt32 moreInts [] = { 8, 9 };
    00054 //      FdoInt32 numMoreInts = sizeof(moreInts)/sizeof(moreInts[0]);
    00055 //      ints = FdoIntArray::Append(ints, numMoreInts, moreInts);
    00056 //      int element = (*ints)[1];
    00057 //      cout << "The second element is " << element << endl;
    00058 //      FDO_SAFE_RELEASE(ints);
    00059
    00060 /// \brief
    00061 /// Abstract template class for defining dynamic arrays.
    00062 ///
    00063 /// <span class="red_text"><b>WARNING:</b></span> This array uses a single memory allocation to store array elements
    00064 /// and may re-allocate that memory when the array size needs to change.
    00065 /// Therefore, do not keep pointers to array elements and avoid using
    00066 /// for objects which cannot be safely moved around in memory or which have
    00067 /// non-empty destructors.
    00068 template <typename T> class FdoArray
    00069 {
    00070 public:
    00071
    00072     /// \brief
    00073     /// Create an empty array
    00074     ///
    00075     /// \return
    00076     /// Returns a FdoArray pointer
    00077     ///
    00078     static FdoArray<T> * Create();
    00079     /// \brief
    00080     /// Create a dynamic array preallocated to a specific size
    00081     ///
    00082     /// \param initialAlloc
    00083     /// Input initial size of the array
    00084     ///
    00085     /// \return
    00086     /// Returns a FdoArray pointer
    00087     ///
    00088     static FdoArray<T> * Create(FdoInt32 initialAlloc);
    00089     /// \brief
    00090     /// Create a dynamic array from a pointer to a fixed array
    00091     ///
    00092     /// \param elements
    00093     /// Input pointer to array of elements
    00094     /// \param initialNumElements
    00095     /// Input number of elements to be added
    00096     ///
    00097     /// \return
    00098     /// Returns a FdoArray pointer
    00099     ///
    00100     static FdoArray<T> * Create(const T* elements, FdoInt32 initialNumElements);
    00101
    00102     /// \brief
    00103     /// Increase the reference count.
    00104     ///
    00105     /// \return
    00106     /// Returns the new reference count. For debugging use only.
    00107     ///
    00108     inline FdoInt32 AddRef() { return ++((FdoArrayHelper::GenericArray*)this)->m_metadata.refCount; }
    00109     /// \brief
    00110     /// Decrease the reference count.
    00111     ///
    00112     /// \return
    00113     /// Returns the new reference count. For debugging use only.
    00114     ///
    00115     inline FdoInt32 Release()
    00116     {
    00117 #ifdef _DEBUG
    00118         if (((FdoArrayHelper::GenericArray*)this)->m_metadata.refCount <= 0)
    00119             throw FdoException::Create(FdoException::NLSGetMessage(FDO_NLSID(FDO_1_MEMORY_DEALLOCATION_ERROR),
    00120                                                                L"FdoArray::Release",
    00121                                                                L"FDO Array"));
    00122 #endif
    00123         if (0 != --((FdoArrayHelper::GenericArray*)this)->m_metadata.refCount )
    00124             return ((FdoArrayHelper::GenericArray*)this)->m_metadata.refCount;
    00125         Dispose();
    00126         return 0;
    00127     }
    00128
    00129     /// \brief
    00130     /// Retrieves the reference count.
    00131     ///
    00132     /// \return
    00133     /// Returns the existing reference count value.
    00134     ///
    00135     inline FdoInt32 GetRefCount() { return ((FdoArrayHelper::GenericArray*)this)->m_metadata.refCount; }
    00136
    00137     /// \brief
    00138     /// Gets the number of items in the array.
    00139     ///
    00140     /// \return
    00141     /// Returns number of items in the array
    00142     ///
    00143     FdoInt32 GetCount() const { return ((FdoArrayHelper::GenericArray*)this)->m_metadata.size; }
    00144     /// \brief
    00145     /// Get a pointer to the data in the array.
    00146     ///
    00147     /// \return
    00148     /// Returns a pointer to the data
    00149     ///
    00150     T* GetData() { return (T*)(((FdoArrayHelper::GenericArray*)this)->GetData()); }
    00151     /// \brief
    00152     /// Get a pointer to the data in the array.
    00153     ///
    00154     /// \return
    00155     /// Returns a pointer to the data
    00156     ///
    00157     const T* GetData() const {return (const T*)(((FdoArrayHelper::GenericArray*)this)->GetData()); }
    00158
    00159     /// \brief
    00160     ///  Resize the array.
    00161     ///
    00162     /// \return
    00163     /// Returns the new array pointer.
    00164     ///
    00165     static FdoArray<T> * SetSize(FdoArray<T> * array, FdoInt32 numElements);
    00166
    00167     /// \brief
    00168     /// Adds the specified array of items to the end of the array. Returns a new array pointer.
    00169     ///
    00170     /// \param array
    00171     /// Input array pointer
    00172     /// \param numElements
    00173     /// Input number of items to be added
    00174     /// \param elements
    00175     /// Input pointer to array to append
    00176     ///
    00177     /// \return
    00178     /// Returns the new array pointer.
    00179     ///
    00180     static FdoArray<T> * Append(FdoArray<T> * array, FdoInt32 numElements, T * elements);
    00181     /// \brief
    00182     /// Adds the specified item to the end of the array. Returns a new array pointer.
    00183     ///
    00184     /// \param array
    00185     /// Input array pointer
    00186     /// \param element
    00187     /// Input item to be appended to array
    00188     ///
    00189     /// \return
    00190     /// Returns the new array pointer.
    00191     ///
    00192     static FdoArray<T> * Append(FdoArray<T> * array, T element);
    00193     /// \brief
    00194     /// Removes all items from the array.
    00195     ///
    00196     /// \return
    00197     /// Returns nothing
    00198     ///
    00199     void Clear();
    00200
    00201     /// \brief
    00202     /// Provide index operator [] access to array members.
    00203     ///
    00204     /// \param i
    00205     /// Input index to access
    00206     ///
    00207     /// \return
    00208     /// Returns the value of the specified item in the array.
    00209     ///
    00210     const T& operator[](int i) const { return GetValue(i); }
    00211     /// \brief
    00212     /// Provide index operator [] access to array members.
    00213     ///
    00214     /// \param i
    00215     /// Input index to access
    00216     ///
    00217     /// \return
    00218     /// Returns the value of the specified item in the array.
    00219     ///
    00220     T& operator[](int i) { return GetValue(i); }
    00221
    00222 protected:
    00223     /// Constructor
    00224     FdoArray() {}
    00225
    00226     static FdoArray<T> * AllocMore(FdoArray<T> * array, FdoInt32 atLeastThisMuch, bool exactly);
    00227     static FdoArray<T> * SetAlloc(FdoArray<T> * array, FdoInt32 numElements);
    00228
    00229     /// Access elements
    00230     const T& GetValue(FdoInt32 i) const;
    00231     T& GetValue(FdoInt32 i);
    00232     void SetValue(FdoInt32 i, T newElement);
    00233
    00234     /// the rest of FdoIDisposable
    00235     void Dispose();
    00236 };
    00237
    00238 template <class T>
    00239 inline
    00240 FdoArray<T> * FdoArray<T>::Create()
    00241 {
    00242     return AllocMore(0, 0, true);
    00243 }
    00244
    00245 template <class T>
    00246 inline
    00247 FdoArray<T> * FdoArray<T>::Create(FdoInt32 initialAlloc)
    00248 {
    00249     return AllocMore(0, initialAlloc, true);
    00250 }
    00251
    00252 template <class T>
    00253 inline
    00254 FdoArray<T> * FdoArray<T>::Create(const T* elements, FdoInt32 initialNumElements)
    00255 {
    00256     FdoArray<T> * array = AllocMore(0, initialNumElements, true);
    00257     if (array != NULL)
    00258         array = (FdoArray<T> *)FdoArrayHelper::Append((FdoArrayHelper::GenericArray*) array, initialNumElements, (FdoByte*) elements, sizeof(T));
    00259     return array;
    00260 }
    00261
    00262 template <class T>
    00263 inline
    00264 FdoArray<T> * FdoArray<T>::Append(FdoArray<T> * array, FdoInt32 numElements, T * elements)
    00265 {
    00266     array = (FdoArray<T> *)FdoArrayHelper::Append((FdoArrayHelper::GenericArray*) array, numElements, (FdoByte*) elements, sizeof(T));
    00267     return array;
    00268 }
    00269
    00270 template <class T>
    00271 inline
    00272 FdoArray<T> * FdoArray<T>::Append(FdoArray<T> * array, T element)
    00273 {
    00274     if ( ((FdoArrayHelper::GenericArray*)array)->m_metadata.size == ((FdoArrayHelper::GenericArray*)array)->m_metadata.alloc )
    00275     {
    00276         array = (FdoArray<T> *)FdoArrayHelper::AllocMore((FdoArrayHelper::GenericArray*) array, 1, false /*exactly*/, sizeof(T));
    00277     }
    00278     array->GetValue((((FdoArrayHelper::GenericArray*)array)->m_metadata.size)++) = element;
    00279     return array;
    00280 }
    00281
    00282 template <class T>
    00283 inline
    00284 void FdoArray<T>::Clear()
    00285 {
    00286     /// since no memory reallocation we can avoid input/output of array class pointer
    00287     SetSize(this, 0);
    00288 }
    00289
    00290 template <class T>
    00291 inline
    00292 FdoArray<T> * FdoArray<T>::SetSize(FdoArray<T> * array, FdoInt32 numElements)
    00293 {
    00294     array = (FdoArray<T> *)FdoArrayHelper::SetSize((FdoArrayHelper::GenericArray*) array, numElements, sizeof(T));
    00295     return array;
    00296 }
    00297
    00298 template <class T>
    00299 inline
    00300 FdoArray<T> * FdoArray<T>::SetAlloc(FdoArray<T> * array, FdoInt32 numElements)
    00301 {
    00302     array = (FdoArray<T> *)FdoArrayHelper::SetAlloc((FdoArrayHelper::GenericArray*) array, numElements, sizeof(T));
    00303     return array;
    00304 }
    00305
    00306 //
    00307 // Allocate some more memory for the array.
    00308 // If the given array is NULL, a new array of zero size
    00309 // but the requested allocation is returned.
    00310 // The returned array will always have at least one new
    00311 // free element allocated. Thus, passing atLeastThisMuch < 1,
    00312 // while not an error, still results in some new storage.
    00313 //
    00314 template <class T>
    00315 inline
    00316 FdoArray<T> * FdoArray<T>::AllocMore(FdoArray<T> * array, FdoInt32 atLeastThisMuch, bool exactly)
    00317 {
    00318     array = (FdoArray<T> *)FdoArrayHelper::AllocMore((FdoArrayHelper::GenericArray*) array, atLeastThisMuch, exactly, sizeof(T));
    00319     return array;
    00320 }
    00321
    00322 template <class T>
    00323 inline
    00324 void FdoArray<T>::Dispose()
    00325 {
    00326     FdoArrayHelper::DisposeOfArray((FdoArrayHelper::GenericArray*) this, sizeof(T));
    00327 }
    00328
    00329 template <class T>
    00330 inline
    00331 const T& FdoArray<T>::GetValue(FdoInt32 i) const
    00332 {
    00333     if (i >= GetCount() || i < 0)
    00334         throw FdoException::Create(FdoException::NLSGetMessage(FDO_NLSID(FDO_5_INDEXOUTOFBOUNDS)));
    00335
    00336     return *(this->GetData()+i);
    00337 }
    00338
    00339 template <class T>
    00340 inline
    00341 T& FdoArray<T>::GetValue(FdoInt32 i)
    00342 {
    00343     if (i >= GetCount() || i < 0)
    00344         throw FdoException::Create(FdoException::NLSGetMessage(FDO_NLSID(FDO_5_INDEXOUTOFBOUNDS)));
    00345
    00346     return *(this->GetData()+i);
    00347 }
    00348
    00349 template <class T>
    00350 inline
    00351 void FdoArray<T>::SetValue(FdoInt32 i, T newElement)
    00352 {
    00353     if (i >= GetCount() || i < 0)
    00354         throw FdoException::Create(FdoException::NLSGetMessage(FDO_NLSID(FDO_5_INDEXOUTOFBOUNDS)));
    00355
    00356     *(this->GetData()+i) = newElement;
    00357 }
    00358
    00359 /// \ingroup (typedefs)
    00360 /// \brief
    00361 /// Dynamic array of bytes (FdoByte).
    00362 typedef FdoArray<FdoByte>   FdoByteArray;
    00363
    00364 /// \ingroup (typedefs)
    00365 /// \brief
    00366 /// Dynamic array of doubles (FdoDouble).
    00367 typedef FdoArray<FdoDouble> FdoDoubleArray;
    00368
    00369 /// \ingroup (typedefs)
    00370 /// \brief
    00371 /// Dynamic array of integers (FdoInt32).
    00372 typedef FdoArray<FdoInt32>  FdoIntArray;
    00373 //typedef FdoArray<FdoString> FdoStringArray;
    00374 #endif
    00375
    00376

Please send us your comment about this page