Subversion Repositories Kolibri OS

/** \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 

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 

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 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(from_obj)); }

  inline void destruct(void * obj) const

  { /*obj;*/ static_cast(obj)->~T(); }

  //inline int size() const { return sizeof(T); }

};

template 

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(to_obj) = *static_cast(from_obj); }

  inline void destruct(void * obj) const {}

  //inline int size() const { return sizeof(T); }

};

template 

class ArrOpsCustomPtr : public ArrOps

{

  typedef T* TY;

public:

  ArrOpsCustomPtr() {}

  inline void construct(void * buffer) const

  { *static_cast(buffer) = 0; }

  inline void construct(void * to_obj, const void * from_obj) const

  { *static_cast(to_obj) = *static_cast(from_obj); }

  inline void destruct(void * obj) const {}

  //inline int size() const { return sizeof(TY); }

  inline int granularity() const { return 8; }

};

template 

class ArrOpsDeletingObj {};

template 

class ArrOpsDeletingPtr : public ArrOpsCustomPtr

{

  typedef T* TY;

public:

  inline void destruct(void * obj) const

  { delete *static_cast(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 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& 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& operator=(const CArrayGrower& 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

    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 

    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 CDeletingArrayGrower : public CArrayGrower

{

public:

  CDeletingArrayGrower() {}

};

#endif