0,0 → 1,295 |
/** \file grower.h Template class that implements dynamic growing arrays. |
* Yacas implements its own growing array class to ensure correct behaviour |
* on all platforms (stl was still in development and not supported on all |
* platforms when development started). |
* |
* grower started 1998 ayal Pinkus |
* |
*/ |
|
#ifndef _GROWER_H_ |
#define _GROWER_H_ |
|
#include "yacasbase.h" |
#include "lispassert.h" |
|
|
|
// Default placement versions of operator new and delete, placed here because I do not want to include <new> |
inline void* operator new(size_t, void* __p) throw() { return __p; } |
inline void* operator new[](size_t, void* __p) throw() { return __p; } |
inline void operator delete (void*, void*) throw() { } |
inline void operator delete[](void*, void*) throw() { } |
|
|
template <class T> |
inline void constructAt(void * to_obj, const T * from_obj) |
{ |
new (to_obj) T(*from_obj); |
} |
|
class ArrOps |
{ |
public: |
virtual bool isPOD() const { return false; } |
virtual void construct(void * buffer) const = 0; |
virtual void construct(void * to_obj, const void * from_obj) const = 0; |
virtual void destruct(void * obj) const = 0; |
virtual int granularity() const { return 8; } |
static void resize(char** pArray, const ArrOps& opers, int& iSize, int& iCapacity, int aSize, int aItemSize, int ext); |
static void remove(char** pArray, const ArrOps& opers, int& iSize, int aIndex, int aCount, int aItemSize); |
static void reserve(char** pArray, int& iCapacity, int aSize, int aItemSize); |
//static void* insert(char** pArray, const ArrOps& opers, int& iSize, void* aData, int aIndex, int aCount, int aSize, int aExtSize); |
}; |
|
template <class T> |
class ArrOpsCustomObj : public ArrOps |
{ |
public: |
ArrOpsCustomObj() {} |
inline void construct(void * buffer) const |
{ new (buffer) T; } |
inline void construct(void * to_obj, const void * from_obj) const |
{ constructAt(to_obj, static_cast<const T*>(from_obj)); } |
inline void destruct(void * obj) const |
{ /*obj;*/ static_cast<T*>(obj)->~T(); } |
//inline int size() const { return sizeof(T); } |
}; |
|
template <class T> |
class ArrOpsPOD : public ArrOps |
{ |
public: |
ArrOpsPOD() {} |
inline bool isPOD() const { return true; } |
inline void construct(void * buffer) const {} |
inline void construct(void * to_obj, const void * from_obj) const |
{ *static_cast<T*>(to_obj) = *static_cast<const T*>(from_obj); } |
inline void destruct(void * obj) const {} |
//inline int size() const { return sizeof(T); } |
}; |
|
template <class T> |
class ArrOpsCustomPtr : public ArrOps |
{ |
typedef T* TY; |
public: |
ArrOpsCustomPtr() {} |
inline void construct(void * buffer) const |
{ *static_cast<TY*>(buffer) = 0; } |
inline void construct(void * to_obj, const void * from_obj) const |
{ *static_cast<TY*>(to_obj) = *static_cast<const TY*>(from_obj); } |
inline void destruct(void * obj) const {} |
//inline int size() const { return sizeof(TY); } |
inline int granularity() const { return 8; } |
}; |
|
template <class T> |
class ArrOpsDeletingObj {}; |
|
template <class T> |
class ArrOpsDeletingPtr : public ArrOpsCustomPtr<T> |
{ |
typedef T* TY; |
public: |
inline void destruct(void * obj) const |
{ delete *static_cast<const TY*>(obj); } |
}; |
|
/** template class useful for implementing a dynamic growing array |
* for any arbitrary type of object. If using the array to maintain |
* objects, please use pointers to the objects, and use the |
* CDeletingArrayGrower to automatically delete the objects at destruction. |
*/ |
template <class T, class TOps > |
class CArrayGrower : public YacasBase |
{ |
public: |
/** ElementType can be used outside this class as the type of the |
* object in the array. This is useful in templated functions that |
* work on a CArrayGrower without being part of CArrayGrower |
*/ |
typedef LispInt SizeType; |
typedef T ElementType; |
|
CArrayGrower() |
: iArray(0) |
, iSize(0) |
, iCapacity(0) |
, iArrayOwnedExternally(LispFalse) |
{ |
} |
virtual ~CArrayGrower() |
{ |
Clear(); |
} |
inline void Clear() // oddly, only *one* use outside destructor!? |
{ |
if (iSize) |
{ |
const TOps opers; |
if(!opers.isPOD()) |
{ |
while (iSize) |
opers.destruct(iArray + --iSize); |
} |
} |
if (!iArrayOwnedExternally) |
{ |
PlatFree(iArray); |
} |
iArray = 0; |
iCapacity = iSize = 0; |
iArrayOwnedExternally = LispFalse; |
} |
inline SizeType Size() const { return iSize; } |
|
inline CArrayGrower(const CArrayGrower<T,TOps>& aOther) |
: iArray(0) |
, iSize(0) |
, iCapacity(0) |
, iArrayOwnedExternally(LispFalse) |
{ |
// Make sure we're not accidentally copying a huge array. We want this system to stay efficient... |
LISPASSERT(aOther.iSize == 0); |
LISPASSERT(aOther.iArrayOwnedExternally == LispFalse); |
} |
|
inline const CArrayGrower<T,TOps>& operator=(const CArrayGrower<T,TOps>& aOther) |
{ |
// Make sure we're not accidentally copying a huge array. We want this system to stay efficient... |
LISPASSERT(iArray == 0); |
LISPASSERT(iSize == 0); |
LISPASSERT(iCapacity == 0); |
LISPASSERT(iArrayOwnedExternally == LispFalse); |
|
LISPASSERT(aOther.iSize == 0); |
LISPASSERT(aOther.iArrayOwnedExternally == LispFalse); |
return *this; |
} |
|
private: |
|
void moreCapacity(SizeType aSize, int g) // almost independent of T |
{ |
LISPASSERT(!iArrayOwnedExternally); |
LISPASSERT(iCapacity >= 0); |
// Compute a new iCapacity >= aSize, with iCapacity % g == 0. |
// We assume g is a power of 2. (fwiw, in two's-complement, ~(g-1) == -g. |
iCapacity = (aSize + g) & ~(g-1); |
if (!iArray) |
{ |
iArray = (ElementType*)PlatAlloc(iCapacity*sizeof(ElementType)); |
} |
else |
{ |
// we assume 'memcpy' suffices for moving the existing items. |
iArray = (ElementType*)PlatReAlloc(iArray,iCapacity*sizeof(ElementType)); |
} |
} |
public: |
inline void ResizeTo(SizeType aSize) |
{ |
LISPASSERT(!iArrayOwnedExternally); |
TOps opers; |
if (aSize > iCapacity) |
{ |
moreCapacity(aSize, opers.granularity()); |
} |
if (!opers.isPOD()) |
{ |
if (iSize < aSize) |
{ |
for (int ii = iSize; ii < aSize; ii++) |
opers.construct(iArray + ii); |
} |
else |
{ |
for (int ii = aSize; ii < iSize; ii++) |
opers.destruct(iArray + ii); |
} |
} |
iSize = aSize; |
} |
void Delete(SizeType aIndex, SizeType aCount=1) |
{ |
LISPASSERT(aIndex>=0 && aIndex<iSize); |
ArrOps::remove((char**)&iArray, TOps(), iSize, aIndex, aCount, sizeof(ElementType)); |
} |
inline LispBoolean ArrayOwnedExternally() |
{ |
return iArrayOwnedExternally; |
} |
public: |
/// Access to an element in the array |
inline ElementType& operator[](const SizeType aIndex) const |
{ |
return iArray[aIndex]; |
} |
|
/// Append an element to an array |
template <class Type> |
inline void Append(const Type& aVal) |
{ |
if (iSize >= iCapacity) moreCapacity(iSize+1, TOps().granularity()); |
new ((void *)(iArray+iSize)) ElementType(aVal); |
++iSize; |
} |
|
/// Insert object aObj at aIndex, aCount times. |
inline void Insert(SizeType aIndex, const ElementType& aObj, SizeType aCount=1) |
{ |
const SizeType oldItems = iSize; |
LISPASSERT(aIndex <= oldItems && aCount >= 0); |
ResizeTo(iSize+aCount); |
ElementType * pOld = iArray+oldItems; |
ElementType * pEnd = iArray+iSize; |
int i = iSize - aIndex; // = (oldItems - aIndex) + aCount |
for ( ; i > aCount; i--) |
*--pEnd = *--pOld; |
while (i-- > 0) |
*--pEnd = aObj; |
} |
|
/** Set the array to an external array. This means the array will |
* not be freed at destruction time |
*/ |
inline void SetExternalArray(ElementType* aArray, SizeType aSize) |
{ |
LISPASSERT(!iArray || iArrayOwnedExternally == LispTrue); |
iArray = aArray; |
iSize = aSize; |
iArrayOwnedExternally = LispTrue; |
iCapacity = -10000; // Setting iCapacity should not strictly be necessary, setting it to hugely negative number will hopefully force a fail. |
} |
|
/// Copy the array to another array |
inline void CopyToExternalArray(ElementType * aArray) |
{ |
PlatMemCopy(aArray,iArray,iSize*sizeof(ElementType)); |
} |
|
protected: |
inline ElementType * elements() const { return iArray; } |
private: |
ElementType * iArray; |
SizeType iSize; |
SizeType iCapacity; |
LispBoolean iArrayOwnedExternally; |
}; |
|
/** \class CDeletingArrayGrower calls delete on each element in the |
* array at destruction time. This is useful if the array is a list |
* of pointers to objects. |
*/ |
|
template <class T, class TOps > |
class CDeletingArrayGrower : public CArrayGrower<T, TOps > |
{ |
public: |
CDeletingArrayGrower() {} |
}; |
|
#endif |
|
|