HashArra.h

Go to the documentation of this file.

// BC  11/4/2004  \BobL115\Include\HashArra.h

#ifndef __HASHARRA_H
#define __HASHARRA_H

#ifndef __ALLOCATE_H
#include "Allocate.h"
#endif
#if defined(_MSC_VER) || defined(_OSX)
#include <new.h>
#else
#ifndef __PLACEMENT_NEW_INLINE
#define __PLACEMENT_NEW_INLINE
inline void *__cdecl operator new(size_t, void *_P)
        {return (_P); }
#if     _MSC_VER >= 1200
inline void __cdecl operator delete(void *, void *)
   {return; }
#endif
#endif
#endif

template<class TYPE>
inline void AFXAPI HashConstructElements(TYPE* pElements, int nCount)
{
   ASSERT(nCount == 0 ||
      AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));

   // first do bit-wise zero initialization
   memset((void*)pElements, 0, nCount * sizeof(TYPE));

   // then call the constructor(s)
   for (; nCount--; pElements++)
      ::new((void*)pElements) TYPE;
}

template<class TYPE>
inline void AFXAPI HashDestructElements(TYPE* pElements, int nCount)
{
   ASSERT(nCount == 0 ||
      AfxIsValidAddress(pElements, nCount * sizeof(TYPE)));

   // call the destructor(s)
   for (; nCount--; pElements++)
      pElements->~TYPE();
}

template<class TYPE>
inline void ConstructTheElements(TYPE* pElements, int count)
{
   memset((void*)pElements, 0, count * sizeof(TYPE));

   for (; count--; pElements++)
      ::new((void*)pElements) TYPE;
}

template<class TYPE>
inline void DestructTheElements(TYPE* pElements, int count)
{
   for (; count--; pElements++)
      pElements->~TYPE();
}

template<class TYPE, class ARG_TYPE>
class HashArray 
{
public:
   HashArray();

   int GetSize() const;
   int GetUpperBound() const;
   void SetSize(int newsize, int growby = -1);

   void FreeExtra();
   void RemoveAll();

   TYPE GetAt(int index) const;
   TYPE& ElementAt(int index);
   void SetAt(int index, ARG_TYPE newElement);
   void InsertAt(int nIndex, ARG_TYPE newElement, int nCount=1 );
   void RemoveAt(int index, int count=1);
   
   TYPE  operator [] ( int index ) const { return m_data[index]; }
   TYPE &operator [] (int index) { return m_data[index]; }

   TYPE* GetArray();

   void SetAtGrow(int index, ARG_TYPE newElement);
   int Add(ARG_TYPE newElement);
   void Push(ARG_TYPE newElement);
   TYPE Pop();
   TYPE GetPushed() const;
   void SetGranularity(int granularity) { m_growby = granularity; }

protected:
   TYPE* m_data;
   int m_size;
   int m_maxsize;
   int m_growby;

public:
   ~HashArray();
};

template<class TYPE, class ARG_TYPE>
inline int HashArray<TYPE, ARG_TYPE>::GetSize() const { return m_size; }
   
template<class TYPE, class ARG_TYPE>
inline int HashArray<TYPE, ARG_TYPE>::GetUpperBound() const { return m_size-1; }
   
template<class TYPE, class ARG_TYPE>
inline void HashArray<TYPE, ARG_TYPE>::RemoveAll() { SetSize(0, -1); }
   
template<class TYPE, class ARG_TYPE>
inline TYPE HashArray<TYPE, ARG_TYPE>::GetAt(int index) const { return m_data[index]; }
    
template<class TYPE, class ARG_TYPE>
inline TYPE& HashArray<TYPE, ARG_TYPE>::ElementAt(int index) { return m_data[index]; }
    
template<class TYPE, class ARG_TYPE>
inline void HashArray<TYPE, ARG_TYPE>::SetAt(int index, ARG_TYPE newElement) { m_data[index] = newElement; }
   
template<class TYPE, class ARG_TYPE>
inline TYPE* HashArray<TYPE, ARG_TYPE>::GetArray() { return (TYPE*)m_data; }
   
template<class TYPE, class ARG_TYPE>
inline int HashArray<TYPE, ARG_TYPE>::Add(ARG_TYPE newElement)
{ 
   int index = m_size;
   SetAtGrow(index, newElement);
   return index; 
}

template<class TYPE, class ARG_TYPE>
HashArray<TYPE, ARG_TYPE>::HashArray()
{
   m_data = NULL;
   m_size = m_maxsize = m_growby = 0;
}

template<class TYPE, class ARG_TYPE>
HashArray<TYPE, ARG_TYPE>::~HashArray()
{
   if (m_data != NULL) {
      DestructTheElements(m_data, m_size);
      FreeExt( m_data );
   }
}

template<class TYPE, class ARG_TYPE>
void HashArray<TYPE, ARG_TYPE>::SetSize(int newsize, int growby)
{
   if (growby != -1)
      m_growby = growby;

   if (newsize == 0) {
      if (m_data != NULL) {
         DestructTheElements(m_data, m_size);
         FreeExt( m_data );
         m_data = NULL;
      }
      m_size = m_maxsize = 0;
   }
   else if (m_data == NULL) {
      m_data = (TYPE*) AllocExt( newsize * sizeof(TYPE));
      ConstructTheElements(m_data, newsize);
      m_size = m_maxsize = newsize;
   }
   else if (newsize <= m_maxsize) {
      if (newsize > m_size) {
         ConstructTheElements(&m_data[m_size], newsize-m_size);
      }
      else if (m_size > newsize) {
         DestructTheElements(&m_data[newsize], m_size-newsize);
      }
      m_size = newsize;
   }
   else  {
      int growby = m_growby;
      if (growby == 0) {
         growby = m_size / 8;
         growby = (growby < 4) ? 4 : ((growby > 1024) ? 1024 : growby);
      }
      int newmax;
      if (newsize < m_maxsize + growby)
         newmax = m_maxsize + growby;
      else
         newmax = newsize;

      TYPE* newdata = (TYPE*) AllocExt( newmax * sizeof(TYPE));

      memcpy(newdata, m_data, m_size * sizeof(TYPE));

      ConstructTheElements(&newdata[m_size], newsize-m_size);

      FreeExt( m_data );
      m_data = newdata;
      m_size = newsize;
      m_maxsize = newmax;
   }
}

template<class TYPE, class ARG_TYPE>
void HashArray<TYPE, ARG_TYPE>::FreeExtra()
{
   if (m_size != m_maxsize) {
      TYPE* newdata = NULL;
      if (m_size != 0)  {
         newdata = (TYPE*) AllocExt( m_size * sizeof(TYPE));
         memcpy(newdata, m_data, m_size * sizeof(TYPE));
      }

      FreeExt( m_data );
      m_data = newdata;
      m_maxsize = m_size;
   }
}

template<class TYPE, class ARG_TYPE>
void HashArray<TYPE, ARG_TYPE>::SetAtGrow(int index, ARG_TYPE newElement)
{
   if (index >= m_size)
      SetSize(index+1, -1);
   m_data[index] = newElement;
}

template<class TYPE, class ARG_TYPE>
void HashArray<TYPE, ARG_TYPE>::InsertAt(int nIndex, ARG_TYPE newElement, int nCount /*=1*/)
{
   // YP Comeback: "this" is not a CObject so can not be used with ASSERT_VALID
// ASSERT_VALID(this);
   ASSERT(nIndex >= 0);    // will expand to meet need
   ASSERT(nCount > 0);     // zero or negative size not allowed

   if (nIndex >= m_size)
   {
      // adding after the end of the array
      SetSize(nIndex + nCount, -1);   // grow so nIndex is valid
   }
   else
   {
      // inserting in the middle of the array
      int nOldSize = m_size;
      SetSize(m_size + nCount, -1);  // grow it to new size
      // destroy intial data before copying over it
#if (_MFC_VER > 0x0420)
      HashDestructElements<TYPE>(&m_data[nOldSize], nCount);
#else   
      HashDestructElements(&m_data[nOldSize], nCount);
#endif   
      // shift old data up to fill gap
      memmove(&m_data[nIndex+nCount], &m_data[nIndex],
         (nOldSize-nIndex) * sizeof(TYPE));

      // re-init slots we copied from
#if (_MFC_VER > 0x0420)
      HashConstructElements<TYPE>(&m_data[nIndex], nCount);
#else   
      HashConstructElements(&m_data[nIndex], nCount);
#endif   
   }

   // insert new value in the gap
   ASSERT(nIndex + nCount <= m_size);
   while (nCount--)
      m_data[nIndex++] = newElement;
}

template<class TYPE, class ARG_TYPE>
void HashArray<TYPE, ARG_TYPE>::RemoveAt(int index, int count)
{
   // just remove a range
   int movecount = m_size - (index + count);

#if (_MFC_VER > 0x0420)
   HashDestructElements<TYPE>(&m_data[index], count);
#else   
   HashDestructElements(&m_data[index], count);
#endif   
   
   if (movecount)
      memmove(&m_data[index], &m_data[index + count],
         movecount * sizeof(TYPE));
   m_size -= count;
}

template<class TYPE, class ARG_TYPE>
inline void HashArray<TYPE, ARG_TYPE>::Push(ARG_TYPE newElement)
{ 
   SetAtGrow(m_size, newElement);
}

template<class TYPE, class ARG_TYPE>
TYPE HashArray<TYPE, ARG_TYPE>::Pop()
{
   if (m_size < 1) {
      ASSERT(FALSE);
      return (TYPE)NULL;
   }
   TYPE rvalue = m_data[m_size-1];
#if (_MFC_VER > 0x0420)
   HashDestructElements<TYPE>(&m_data[m_size-1], 1);
#else   
   HashDestructElements(&m_data[m_size-1], 1);
#endif   
  
   --m_size;
   return rvalue;
}

template<class TYPE, class ARG_TYPE>
inline TYPE HashArray<TYPE, ARG_TYPE>::GetPushed() const { return m_data[m_size-1]; }

#endif __HASHARRA_H

---