TARRAY.H
//+-----------------------------------------------------------------------
//
// Template Array Implementation
// Copyright (C) Microsoft Corporation, 1996, 1997
//
// File: tarray.h
//
// Contents: Template for resizeable arrays. Allows for the creation
// and manipulation of arrays of any type. Arrays can
// be dynamically reallocated, and thus can "grow and shrink".
// Constructors and destructors of array elements is
// automatically handles, even when the size of the array is
// changed.
// Templates: TSTDArray
//
//------------------------------------------------------------------------
#ifndef _TARRAY_H_
#define _TARRAY_H_
//+-----------------------------------------------------------------------
//
// Class: TSTDArray
//
// Synopsis: Contains an array of "type". Allows array to grow
// dynamically. During debug, can check bounds on indices.
// Array is indexed 0 to _cArraySize-1. _cArraySize holds
// number of elements.
//
// Methods: Init allocate memory for array
// Passivate
// [] allows indexing of array
// GetSize returns size of array
// InsertElems insert elements anywhere in array
// DeleteElems delete elements anywhere in array
//
//------------------------------------------------------------------------
template <class TYPE>
class TSTDArray
{
public:
TSTDArray();
#if DBG == 1
~TSTDArray();
#endif
HRESULT Init(const size_t cSize); // initialize data structures
void Passivate();
TYPE& operator[](const size_t iElement);
const TYPE& operator[](const size_t iElement) const; // constant reference
size_t GetSize() const { return _cArraySize; }
HRESULT InsertElems(const size_t iElem, const size_t cElems);
void DeleteElems(const size_t iElem, const size_t cElems);
private:
#if DBG == 1
void IsValidObject() const;
#else
void IsValidObject() const
{ }
#endif
// All elements are packaged inside a class CElem. This allows us to
// overload the new operator so that we can manually invoke the
// constructors.
class CElem
{
friend TSTDArray;
private:
// Now we overload the new operator to allow placement argument
void *operator new(size_t uSize, void *pv) { return pv; }
// Internal data:
TYPE _Element; // actual element
};
// Internal data:
CElem *_paArray; // pointer to actual data
size_t _cArraySize;
size_t _cAllocSize; // the size of allocated object
#if DBG == 1
// Ensure we call constructors and destructors right number of times.
// Used only as a check.
size_t _cNumElems;
#endif
};
//+---------------------------------------------------------------------------
//
// Member: IsValidObject
//
// Synopsis: Validation method. Checks that array structure is valid.
// It is usefull to call this member function at the beginning
// of each member function that uses the internal array to
// ensure that the array is not corrupt before attempting to
// modify it.
//
#if DBG == 1
template <class TYPE>
void
TSTDArray<TYPE>::IsValidObject() const
{
_ASSERT("Must have valid this pointer" &&
this );
_ASSERT("Array has no memory" &&
_paArray );
_ASSERT("destructors called wrong number of times" &&
(_cNumElems == _cArraySize) );
}
#endif
//+-----------------------------------------------------------------------
//
// Constructor for TSTDArray
//
// Synopsis: Doesn't do anything. Must call member function init to
// actually initialize. Only call init once.
//
// Arguments: None.
//
// Returns: Nothing.
//
template <class TYPE>
TSTDArray<TYPE>::TSTDArray()
{
// We null the internal data, so that they are not actually used
// until the init member function is called.
_paArray = 0;
_cArraySize = 0;
_cAllocSize = 0;
#if DBG == 1
_cNumElems = 0;
#endif
}
//+-----------------------------------------------------------------------
//
// Destructor for TSTDArray
//
// Synopsis: Must call member function passivate
// to actually de-initialize.
//
// Arguments: None.
//
// Returns: Nothing.
//
#if DBG == 1
template <class TYPE>
TSTDArray<TYPE>::~TSTDArray()
{
_ASSERT("Passivate must be called first" &&
!_paArray );
_ASSERT("Destructors called wrong number of times" &&
(_cNumElems == 0) );
}
#endif
//+-----------------------------------------------------------------------
//
// Member: Init
//
// Synopsis: Initializes the array abstract data type. Allocates
// memory for the array. Also sets the cArraySize to
// the number of elements.
//
// Arguments: cSize initial size of array (# of elements)
//
// Returns: Success if memory can be allocated for table.
// Returns E_OUTOFMEMORY if can't get memory.
//
template <class TYPE>
HRESULT
TSTDArray<TYPE>::Init(const size_t cSize)
{
HRESULT hr;
_ASSERT(this);
_ASSERT("Only call init once" &&
!_paArray );
// Get memory:
// 0 element array is made into 1 element array so that it functions
// normally.
{
//;begin_internal
// BUGBUG:
// MSVC 2.0 has a bug in it. Evaluating the expression sizeof(CElem)
// seems to confuse it. CElem is a class containing a variable
// whose size can only be calculated when the template containing it
// is instantiated. In addition to this, CElem is a member of that
// template. Placing the sizeof(CElem) expression within a more
// complicated expression is not possible.
//;end_internal
size_t uCElemSize;
uCElemSize = sizeof(CElem);
uCElemSize *= (cSize == 0 ? 1 : cSize);
_paArray = (CElem *) CoTaskMemAlloc(uCElemSize);
}
if (!_paArray)
{
hr = E_OUTOFMEMORY;
}
else
{
CElem *pTemp; // index used to call constructors
// We need to call the constructors manually for each element:
for (pTemp = _paArray; pTemp < _paArray + cSize; pTemp++)
{
new (pTemp) CElem;
#if DBG == 1
_cNumElems++;
#endif
}
_cArraySize = cSize;
_cAllocSize = (cSize == 0 ? 1 : cSize);
hr = S_OK;
}
return hr;
}
//+-----------------------------------------------------------------------
//
// Member: Passivate
//
// Synopsis: Releases memory held in array. Should be called before
// the object is destroyed. Should only be called once on an
// object.
//
// Arguments: None.
//
// Returns: Nothing.
//
//------------------------------------------------------------------------
template <class TYPE>
void
TSTDArray<TYPE>::Passivate()
{
IsValidObject();
_ASSERT("Only call Passivate once" &&
_paArray );
// We need to call the destructors manually for each element:
{
CElem *pTemp; // index used to call destructors
for (pTemp = _paArray; pTemp < _paArray + _cArraySize; pTemp++)
{
pTemp->CElem::~CElem();
#if DBG == 1
_cNumElems--;
#endif
}
}
CoTaskMemFree(_paArray);
_paArray = 0; // make sure we don't call Passivate again
_cArraySize = 0;
_cAllocSize = 0;
}
//+-----------------------------------------------------------------------
//
// Member: operator[]
//
// Synopsis: Allows indexing of array's elements. Use this to either
// store an element in the array or read an element from
// the array. It is the user's responsibility to ensure
// that the index is within the proper range, 0.._cArraySize-1.
// During debugging, the index range is checked.
//
// Arguments: iElement Element index
//
// Returns: Reference to element.
//
template <class TYPE>
inline
TYPE&
TSTDArray<TYPE>::operator[](const size_t iElement)
{
IsValidObject();
_ASSERT("Index is out of range" &&
(iElement < _cArraySize) );
return _paArray[iElement]._Element;
}
//+-----------------------------------------------------------------------
//
// Member: operator[] const
//
// Synopsis: Same as previous [] operator, but returns a constant
// reference so that it can't be used as an l-value.
//
// Arguments: iElement Element index
//
// Returns: Constant reference to element.
//
template <class TYPE>
inline
const TYPE&
TSTDArray<TYPE>::operator[](const size_t iElement) const
{
IsValidObject(this);
_ASSERT("Index is out of range" &&
(iElement < _cArraySize) );
return _paArray[iElement]._Element;
}
//+-----------------------------------------------------------------------
//
// Member: InsertElems
//
// Synopsis: Changes the size of the array by using MemRealloc().
// Inserts a number of elements cElems into the array at
// iElem. This can be used to add new elements to the end of
// the array by specifying iElem equal to _cArraySize. It is
// the responsibility of the user to make sure that iElem is
// within the proper bounds of the array, although this will
// be checked during debug mode.
//
// Arguments: iElem place to insert first element
// cElems number of new elements
//
// Returns: Returns success if elements can be added.
// Returns E_OUTOFMEMORY if request cannot be met.
// Array retains its old size if the request cannot be met.
//
template<class TYPE>
HRESULT
TSTDArray<TYPE>::InsertElems(const size_t iElem, const size_t cElems)
{
HRESULT hr = S_OK;
IsValidObject();
// Note that you can insert past the END of an array (appending to it):
_ASSERT("iElem is too large" &&
(iElem <= _cArraySize) );
if (_cArraySize + cElems > _cAllocSize)
{
// Resize the current array we have:
ULONG cAllocSize = _cAllocSize ? _cAllocSize : 8;
CElem * paArray; // new array
// Double alloc size until it's big enough. This will, I suppose, loop
// forever if someone asks to allocate more than 2^31 elements.
_ASSERT(_cArraySize + cElems < MAXLONG);
while (_cArraySize + cElems > cAllocSize) cAllocSize <<= 1;
paArray = (CElem *)CoTaskMemRealloc(_paArray, sizeof(CElem) * cAllocSize);
if (!paArray)
{
hr = E_OUTOFMEMORY;
goto Error;
}
_paArray = paArray;
_cAllocSize = cAllocSize;
}
// Now we have to shift elements to allow space for the new elements:
memmove(_paArray + iElem + cElems, // dest
_paArray + iElem,
(_cArraySize - iElem) * sizeof(CElem));
// Call constructors on all new elements:
{
CElem *pTemp; // index used to call constructors
for (pTemp = _paArray + iElem;
pTemp < _paArray + iElem + cElems;
pTemp++)
{
new (pTemp) CElem;
#if DBG == 1
_cNumElems++;
#endif
}
}
_cArraySize += cElems;
Error:
return hr;
}
//+-----------------------------------------------------------------------
//
// Member: DeleteElems
//
// Synopsis: Deletes a number of elements cElems from the array at
// iElem. It is the responsibility of the user to make sure
// that the region to be deleted is within the proper bounds
// of the array, although this will be checked during
// debug mode.
//
// Arguments: iElem place to delete first element
// cElems number of elements to delete
//
// Returns: Returns success.
//
template<class TYPE>
void
TSTDArray<TYPE>::DeleteElems(const size_t iElem, const size_t cElems)
{
IsValidObject();
_ASSERT("Region to delete is too large" &&
(iElem+cElems-1 < _cArraySize) );
// First we need to call destructors on elements:
{
CElem *pTemp; // index used to call destructors
for (pTemp = _paArray + iElem;
pTemp < _paArray + iElem + cElems;
pTemp++)
{
pTemp->CElem::~CElem();
#if DBG == 1
_cNumElems--;
#endif
}
}
// Now we need to shift the remaining elements in:
memmove(_paArray + iElem, // dest
_paArray + iElem + cElems,
(_cArraySize - (iElem + cElems)) * sizeof(CElem));
_cArraySize -= cElems;
}
#endif // _TARRAY_H_