774 lines
20 KiB
C++
774 lines
20 KiB
C++
|
#ifndef Array_hxx
|
||
|
|
#define Array_hxx
|
||
|
|
|
||
|
|
// File: Array.hxx
|
||
|
|
// Description: Template Class definitions for dynamic array class.
|
||
|
|
// Notes: Array class has the following features:
|
||
|
|
// 1. The array can grow dynamically
|
||
|
|
// 2. The class T must have = operator. When the = operator
|
||
|
|
// of class T is invoked, it is guaranteed that the memory
|
||
|
|
// pointed to by the lvalue of the assignment statement is
|
||
|
|
// cleared to 0. Further, << operator is required for printing
|
||
|
|
// the list and == operator is required locating or removing
|
||
|
|
// the objects of class T.
|
||
|
|
// History: Gopal (08/26/95) -- Creation.
|
||
|
|
|
||
|
|
#include <string.h>
|
||
|
|
#include <iostream.h>
|
||
|
|
|
||
|
|
#define AFLAG_OUTOFMEMORY 1
|
||
|
|
#define AFLAG_ISDIRTY 2
|
||
|
|
|
||
|
|
#define ALLOCATED 0
|
||
|
|
#define RESERVED -1
|
||
|
|
#define NOFREEITEM -2
|
||
|
|
|
||
|
|
typedef int BOOL;
|
||
|
|
#define TRUE 1
|
||
|
|
#define FALSE 0
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
class CArray
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
// Static constructor
|
||
|
|
static CArray* CreateArray(const unsigned long ulStep=5,
|
||
|
|
const unsigned long ulSlots=0) {
|
||
|
|
return(new CArray(ulStep, ulSlots));
|
||
|
|
}
|
||
|
|
|
||
|
|
// Copy constructor
|
||
|
|
CArray(const CArray& a);
|
||
|
|
|
||
|
|
// Reference counting functions
|
||
|
|
unsigned long AddRef() {
|
||
|
|
return(++m_refs);
|
||
|
|
}
|
||
|
|
unsigned long Release();
|
||
|
|
|
||
|
|
// New and Delete operators
|
||
|
|
void* operator new(size_t size) {
|
||
|
|
return PrivMemAlloc(size);
|
||
|
|
};
|
||
|
|
void operator delete(void *pv){
|
||
|
|
PrivMemFree(pv);
|
||
|
|
return;
|
||
|
|
};
|
||
|
|
|
||
|
|
// Functionality functions
|
||
|
|
unsigned long Length() {
|
||
|
|
return(m_ulLength);
|
||
|
|
}
|
||
|
|
void SetStepSize(unsigned long ulStep) {
|
||
|
|
m_ulStepSize = ulStep;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
unsigned long Reserve(const unsigned long ulSlots) {
|
||
|
|
if(m_ulCurSize)
|
||
|
|
return(0);
|
||
|
|
m_ulResSlots = ulSlots;
|
||
|
|
return(ulSlots);
|
||
|
|
}
|
||
|
|
unsigned long Locate(const T& givenitem);
|
||
|
|
BOOL AddReservedItem(const T& item, const unsigned long ulSlot);
|
||
|
|
unsigned long AddItem(const T& item);
|
||
|
|
T* GetItem(const unsigned long index);
|
||
|
|
BOOL DeleteItem(const unsigned long index);
|
||
|
|
void DeleteAllItems(void);
|
||
|
|
BOOL ShiftToEnd(unsigned long ulNode);
|
||
|
|
void Reset(unsigned long& index, BOOL fEnumResSlots=TRUE) {
|
||
|
|
if(fEnumResSlots)
|
||
|
|
index = 0;
|
||
|
|
else
|
||
|
|
index = m_ulResSlots;
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
T* GetNext(unsigned long& ulIndex);
|
||
|
|
T* GetPrev(unsigned long& ulIndex);
|
||
|
|
BOOL IsOutOfMemory() {
|
||
|
|
return(m_ulFlags | AFLAG_OUTOFMEMORY);
|
||
|
|
}
|
||
|
|
BOOL IsDirty() {
|
||
|
|
return(m_ulFlags | AFLAG_ISDIRTY);
|
||
|
|
}
|
||
|
|
CArray& operator=(const CArray& a);
|
||
|
|
friend ostream& operator<<(ostream& os, CArray<T>& l);
|
||
|
|
void Dump();
|
||
|
|
private:
|
||
|
|
// Private data type
|
||
|
|
struct ArrayNode {
|
||
|
|
// Member variables
|
||
|
|
T item;
|
||
|
|
unsigned long next;
|
||
|
|
unsigned long prev;
|
||
|
|
};
|
||
|
|
|
||
|
|
// Private constructor
|
||
|
|
CArray(const unsigned long ulStep, const unsigned long ulSlots);
|
||
|
|
|
||
|
|
// Private destructor
|
||
|
|
~CArray();
|
||
|
|
|
||
|
|
// Private member variables
|
||
|
|
unsigned long m_refs;
|
||
|
|
unsigned long m_ulFlags;
|
||
|
|
unsigned long m_ulStepSize;
|
||
|
|
unsigned long m_ulCurSize;
|
||
|
|
unsigned long m_ulLength;
|
||
|
|
unsigned long m_ulResSlots;
|
||
|
|
unsigned long m_ulHeadNode;
|
||
|
|
unsigned long m_ulTailNode;
|
||
|
|
int m_iFree;
|
||
|
|
int* m_piAllocList;
|
||
|
|
ArrayNode* m_pBuffer;
|
||
|
|
|
||
|
|
void MakeCopy(const CArray& a);
|
||
|
|
};
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
CArray<T>::CArray(const unsigned long ulStep, const unsigned long ulSlots)
|
||
|
|
{
|
||
|
|
m_refs = 1;
|
||
|
|
m_ulFlags = 0;
|
||
|
|
m_ulStepSize = ulStep;
|
||
|
|
if(m_ulStepSize<1)
|
||
|
|
m_ulStepSize = 1;
|
||
|
|
m_ulCurSize = 0;
|
||
|
|
m_ulLength = 0;
|
||
|
|
m_ulResSlots = ulSlots;
|
||
|
|
m_ulHeadNode = 0;
|
||
|
|
m_ulTailNode = 0;
|
||
|
|
m_iFree = NOFREEITEM;
|
||
|
|
m_piAllocList = 0;
|
||
|
|
m_pBuffer = 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
void CArray<T>::MakeCopy(const CArray<T>& a)
|
||
|
|
{
|
||
|
|
// Copy the StepSize
|
||
|
|
m_ulStepSize = a.m_ulStepSize;
|
||
|
|
m_ulResSlots = a.m_ulResSlots;
|
||
|
|
|
||
|
|
// Allocate the memory for buffer and Allocation list
|
||
|
|
if(a.m_ulLength>0) {
|
||
|
|
m_pBuffer = (struct ArrayNode *) PrivMemAlloc(sizeof(ArrayNode)*a.m_ulCurSize);
|
||
|
|
if(m_pBuffer) {
|
||
|
|
m_piAllocList = (int *) PrivMemAlloc(sizeof(int)*a.m_ulCurSize);
|
||
|
|
if(m_piAllocList) {
|
||
|
|
// Memory allocation succeded.
|
||
|
|
m_ulFlags = a.m_ulFlags;
|
||
|
|
m_ulFlags &= ~AFLAG_OUTOFMEMORY;
|
||
|
|
m_ulCurSize = a.m_ulCurSize;
|
||
|
|
m_ulLength = 0;
|
||
|
|
m_ulHeadNode = a.m_ulHeadNode;
|
||
|
|
m_ulTailNode = a.m_ulTailNode;
|
||
|
|
m_iFree = a.m_iFree;
|
||
|
|
memset(m_pBuffer, 0, sizeof(ArrayNode)*m_ulCurSize);
|
||
|
|
|
||
|
|
// Now copy the allocation list and the buffer
|
||
|
|
for(int i=0; i<m_ulCurSize;i++) {
|
||
|
|
m_piAllocList[i] = a.p_iAllocList[i];
|
||
|
|
if(m_piAllocList[i]==ALLOCATED) {
|
||
|
|
// Allocated buffer item. So, copy it
|
||
|
|
m_pBuffer[i].item = a.m_pBuffer[i].item;
|
||
|
|
m_pBuffer[i].next = a.m_pBuffer[i].next;
|
||
|
|
m_pBuffer[i].prev = a.m_pBuffer[i].prev;
|
||
|
|
m_ulLength++;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
Win4Assert(m_ulLength==a.m_ulLength);
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Memory allocation failure
|
||
|
|
// Free the buffer allocated earlier
|
||
|
|
PrivMemFree(m_pBuffer);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Set m_Flags to indicate memory allocation failure
|
||
|
|
// so that we will not try another allocation in future
|
||
|
|
m_ulFlags = AFLAG_OUTOFMEMORY;
|
||
|
|
}
|
||
|
|
|
||
|
|
m_refs = 1;
|
||
|
|
m_ulCurSize = 0;
|
||
|
|
m_ulLength = 0;
|
||
|
|
m_ulHeadNode = 0;
|
||
|
|
m_ulTailNode = 0;
|
||
|
|
m_iFree = NOFREEITEM;
|
||
|
|
m_piAllocList = 0;
|
||
|
|
m_pBuffer = 0;
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
CArray<T>::CArray(const CArray<T>& a)
|
||
|
|
{
|
||
|
|
// Make a copy
|
||
|
|
MakeCopy(a);
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
CArray<T>::~CArray()
|
||
|
|
{
|
||
|
|
// Call the destructor for valid objects in the buffer
|
||
|
|
if(m_pBuffer) {
|
||
|
|
for(unsigned long i=0;i<m_ulCurSize;i++)
|
||
|
|
if(m_piAllocList[i]==ALLOCATED)
|
||
|
|
m_pBuffer[i].item.~T();
|
||
|
|
|
||
|
|
// Free the allocated memory
|
||
|
|
PrivMemFree(m_pBuffer);
|
||
|
|
PrivMemFree(m_piAllocList);
|
||
|
|
}
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
unsigned long CArray<T>::Release()
|
||
|
|
{
|
||
|
|
if(--m_refs==0) {
|
||
|
|
delete this;
|
||
|
|
return(0);
|
||
|
|
}
|
||
|
|
|
||
|
|
return(m_refs);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
unsigned long CArray<T>::Locate(const T& GivenItem)
|
||
|
|
{
|
||
|
|
unsigned long i;
|
||
|
|
|
||
|
|
if (m_pBuffer == NULL)
|
||
|
|
return 0;
|
||
|
|
|
||
|
|
// Search all the reserved and allocated items in the buffer
|
||
|
|
for(i=0;i<m_ulResSlots;i++)
|
||
|
|
if(m_piAllocList[i]==ALLOCATED && m_pBuffer[i].item==GivenItem)
|
||
|
|
return(i+1);
|
||
|
|
|
||
|
|
// Search rest of the nodes
|
||
|
|
if(m_ulHeadNode) {
|
||
|
|
i = m_ulHeadNode;
|
||
|
|
while(i) {
|
||
|
|
Win4Assert(m_piAllocList[i-1]==ALLOCATED);
|
||
|
|
if(m_pBuffer[i-1].item==GivenItem)
|
||
|
|
return(i);
|
||
|
|
else
|
||
|
|
i = m_pBuffer[i-1].next;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return(0);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
BOOL CArray<T>::AddReservedItem(const T& item, const unsigned long ulSlot)
|
||
|
|
{
|
||
|
|
// Sanity check
|
||
|
|
if(ulSlot<1 || ulSlot>m_ulResSlots)
|
||
|
|
return(FALSE);
|
||
|
|
|
||
|
|
// Check if buffer has been allocated
|
||
|
|
if(!m_pBuffer && !(m_ulFlags & AFLAG_OUTOFMEMORY)) {
|
||
|
|
unsigned long i, ulNewSize;
|
||
|
|
ArrayNode* pNewBuffer;
|
||
|
|
int* piNewAllocList;
|
||
|
|
|
||
|
|
// Compute the new size
|
||
|
|
ulNewSize = m_ulResSlots + m_ulStepSize;
|
||
|
|
|
||
|
|
// Expand the buffer
|
||
|
|
pNewBuffer = (ArrayNode *) PrivMemAlloc(sizeof(ArrayNode)*(ulNewSize));
|
||
|
|
if(pNewBuffer) {
|
||
|
|
piNewAllocList = (int *) PrivMemAlloc(sizeof(int)*(ulNewSize));
|
||
|
|
if(piNewAllocList) {
|
||
|
|
// Make the m_pBuffer and m_piAllocList point to the new
|
||
|
|
// buffer and allocation list
|
||
|
|
m_pBuffer = pNewBuffer;
|
||
|
|
m_piAllocList = piNewAllocList;
|
||
|
|
|
||
|
|
// Clear the memory in the buffer that is allocated now
|
||
|
|
memset(&m_pBuffer[0], 0, sizeof(ArrayNode)*ulNewSize);
|
||
|
|
|
||
|
|
// Reserve the desiresd number of slots
|
||
|
|
for(i=0;i<m_ulResSlots;i++)
|
||
|
|
m_piAllocList[i] = RESERVED;
|
||
|
|
|
||
|
|
// Generate the free list
|
||
|
|
for(i=m_ulResSlots;i<ulNewSize-1;i++)
|
||
|
|
m_piAllocList[i] = i+2;
|
||
|
|
m_piAllocList[ulNewSize-1] = NOFREEITEM;
|
||
|
|
|
||
|
|
// Make m_iFree point to the first free item in the new buffer
|
||
|
|
m_iFree = m_ulResSlots+1;
|
||
|
|
|
||
|
|
// Update m_ulCurSize
|
||
|
|
m_ulCurSize = ulNewSize;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
PrivMemFree(pNewBuffer);
|
||
|
|
m_ulFlags |= AFLAG_OUTOFMEMORY;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else
|
||
|
|
m_ulFlags |= AFLAG_OUTOFMEMORY;
|
||
|
|
|
||
|
|
// If we could not expand the buffer, return FALSE
|
||
|
|
if((m_ulFlags & AFLAG_OUTOFMEMORY))
|
||
|
|
return(FALSE);
|
||
|
|
}
|
||
|
|
|
||
|
|
// If the reserved slot is occupied, delete the object
|
||
|
|
if(m_piAllocList[ulSlot-1]==ALLOCATED) {
|
||
|
|
m_pBuffer[ulSlot-1].item.~T();
|
||
|
|
memset(&m_pBuffer[ulSlot-1], 0, sizeof(ArrayNode));
|
||
|
|
}
|
||
|
|
|
||
|
|
// Copy the item at the reserved
|
||
|
|
m_pBuffer[ulSlot-1].item = item;
|
||
|
|
|
||
|
|
// Update the allocation list and length
|
||
|
|
if(m_piAllocList[ulSlot-1]==RESERVED) {
|
||
|
|
m_piAllocList[ulSlot-1] = ALLOCATED;
|
||
|
|
++m_ulLength;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Set the dirty Flag
|
||
|
|
m_ulFlags |= AFLAG_ISDIRTY;
|
||
|
|
|
||
|
|
return(TRUE);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
unsigned long CArray<T>::AddItem(const T& item)
|
||
|
|
{
|
||
|
|
unsigned long i;
|
||
|
|
|
||
|
|
// Check if we have free item in the buffer
|
||
|
|
if(m_iFree==NOFREEITEM && !(m_ulFlags & AFLAG_OUTOFMEMORY)) {
|
||
|
|
// No free item in the buffer
|
||
|
|
unsigned long ulNewSize;
|
||
|
|
ArrayNode* pNewBuffer;
|
||
|
|
int* piNewAllocList;
|
||
|
|
|
||
|
|
// Compute the new size
|
||
|
|
if(m_pBuffer)
|
||
|
|
ulNewSize = m_ulCurSize + m_ulStepSize;
|
||
|
|
else
|
||
|
|
ulNewSize = m_ulResSlots + m_ulStepSize;
|
||
|
|
|
||
|
|
// Expand the buffer
|
||
|
|
pNewBuffer = (ArrayNode *) PrivMemAlloc(sizeof(ArrayNode)*(ulNewSize));
|
||
|
|
if(pNewBuffer) {
|
||
|
|
piNewAllocList = (int *) PrivMemAlloc(sizeof(int)*(ulNewSize));
|
||
|
|
if(piNewAllocList) {
|
||
|
|
if(m_pBuffer) {
|
||
|
|
// Copy the existing buffer and allocation list
|
||
|
|
memcpy(pNewBuffer, m_pBuffer, sizeof(ArrayNode)*m_ulCurSize);
|
||
|
|
memcpy(piNewAllocList, m_piAllocList, sizeof(int)*m_ulCurSize);
|
||
|
|
PrivMemFree(m_pBuffer);
|
||
|
|
PrivMemFree(m_piAllocList);
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
// Reserve the desiresd number of slots
|
||
|
|
for(i=0;i<m_ulResSlots;i++)
|
||
|
|
piNewAllocList[i] = RESERVED;
|
||
|
|
|
||
|
|
// Clear the memory in the reserved slots of the buffer
|
||
|
|
memset(&pNewBuffer[0], 0, sizeof(ArrayNode)*m_ulResSlots);
|
||
|
|
|
||
|
|
// Set current size to the number of reserved slots
|
||
|
|
m_ulCurSize = m_ulResSlots;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Make the m_pBuffer and m_piAllocList point to the new
|
||
|
|
// buffer and allocation list
|
||
|
|
m_pBuffer = pNewBuffer;
|
||
|
|
m_piAllocList = piNewAllocList;
|
||
|
|
|
||
|
|
// Clear the memory in the buffer that is allocated now
|
||
|
|
memset(&m_pBuffer[m_ulCurSize], 0, sizeof(ArrayNode)*m_ulStepSize);
|
||
|
|
|
||
|
|
// Generate the free list
|
||
|
|
for(i=m_ulCurSize;i<ulNewSize-1;i++)
|
||
|
|
m_piAllocList[i] = i+2;
|
||
|
|
m_piAllocList[ulNewSize-1] = NOFREEITEM;
|
||
|
|
|
||
|
|
// Make m_iFree point to the first free item in the new buffer
|
||
|
|
m_iFree = m_ulCurSize+1;
|
||
|
|
|
||
|
|
// Update m_ulCurSize
|
||
|
|
m_ulCurSize = ulNewSize;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
PrivMemFree(pNewBuffer);
|
||
|
|
m_ulFlags |= AFLAG_OUTOFMEMORY;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
else
|
||
|
|
m_ulFlags |= AFLAG_OUTOFMEMORY;
|
||
|
|
}
|
||
|
|
|
||
|
|
// If we could not expand the buffer, return 0
|
||
|
|
if(m_iFree==NOFREEITEM)
|
||
|
|
return 0;
|
||
|
|
|
||
|
|
// Copy the item at the place pointed to by m_iFree
|
||
|
|
m_pBuffer[m_iFree-1].item = item;
|
||
|
|
m_pBuffer[m_iFree-1].next = 0;
|
||
|
|
m_pBuffer[m_iFree-1].prev = m_ulTailNode;
|
||
|
|
if(m_ulTailNode)
|
||
|
|
m_pBuffer[m_ulTailNode-1].next = m_iFree;
|
||
|
|
++m_ulLength;
|
||
|
|
|
||
|
|
// Update the m_ulHeadNode, m_ulTailNode, m_iFree and the allocation list
|
||
|
|
if(!m_ulHeadNode)
|
||
|
|
m_ulHeadNode = m_iFree;
|
||
|
|
m_ulTailNode = m_iFree;
|
||
|
|
i = m_iFree;
|
||
|
|
m_iFree = m_piAllocList[i-1];
|
||
|
|
m_piAllocList[i-1] = ALLOCATED;
|
||
|
|
|
||
|
|
// Set the dirty Flag
|
||
|
|
m_ulFlags |= AFLAG_ISDIRTY;
|
||
|
|
|
||
|
|
return(i);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
T* CArray<T>::GetItem(const unsigned long index)
|
||
|
|
{
|
||
|
|
// Sanity checks
|
||
|
|
if(index>m_ulCurSize || index<1)
|
||
|
|
return(0);
|
||
|
|
if(m_piAllocList[index-1]!=ALLOCATED)
|
||
|
|
return(0);
|
||
|
|
|
||
|
|
return(&m_pBuffer[index-1].item);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
BOOL CArray<T>::DeleteItem(const unsigned long index)
|
||
|
|
{
|
||
|
|
// Sanity checks
|
||
|
|
if(index>m_ulCurSize || index<1)
|
||
|
|
return(FALSE);
|
||
|
|
if(m_piAllocList[index-1]!=ALLOCATED)
|
||
|
|
return(FALSE);
|
||
|
|
|
||
|
|
// Delete the object in the buffer
|
||
|
|
m_pBuffer[index-1].item.~T();
|
||
|
|
|
||
|
|
// Relink if index points to a normal item
|
||
|
|
if(index>m_ulResSlots) {
|
||
|
|
if(m_pBuffer[index-1].prev)
|
||
|
|
m_pBuffer[m_pBuffer[index-1].prev-1].next = m_pBuffer[index-1].next;
|
||
|
|
else {
|
||
|
|
Win4Assert(m_ulHeadNode==index);
|
||
|
|
m_ulHeadNode = m_pBuffer[index-1].next;
|
||
|
|
}
|
||
|
|
if(m_pBuffer[index-1].next)
|
||
|
|
m_pBuffer[m_pBuffer[index-1].next-1].prev = m_pBuffer[index-1].prev;
|
||
|
|
else {
|
||
|
|
Win4Assert(m_ulTailNode==index);
|
||
|
|
m_ulTailNode = m_pBuffer[index-1].prev;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Clear memory
|
||
|
|
memset(&m_pBuffer[index-1], 0, sizeof(ArrayNode));
|
||
|
|
--m_ulLength;
|
||
|
|
|
||
|
|
if(index>m_ulResSlots) {
|
||
|
|
// Update the free list
|
||
|
|
m_piAllocList[index-1] = m_iFree;
|
||
|
|
m_iFree = index;
|
||
|
|
}
|
||
|
|
else {
|
||
|
|
// Revert slot to reserved
|
||
|
|
m_piAllocList[index-1] = RESERVED;
|
||
|
|
}
|
||
|
|
|
||
|
|
return(TRUE);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
void CArray<T>::DeleteAllItems(void)
|
||
|
|
{
|
||
|
|
unsigned long i;
|
||
|
|
|
||
|
|
// If we haven't even allocated a buffer yet,
|
||
|
|
// just return.
|
||
|
|
if (NULL == m_pBuffer)
|
||
|
|
return;
|
||
|
|
|
||
|
|
// Delete all objects in the buffer
|
||
|
|
for(i=0;i<m_ulCurSize;i++)
|
||
|
|
if(m_piAllocList[i]==ALLOCATED)
|
||
|
|
m_pBuffer[i].item.~T();
|
||
|
|
|
||
|
|
// Clear the memory in the buffer
|
||
|
|
memset(&m_pBuffer[0], 0, sizeof(ArrayNode)*m_ulCurSize);
|
||
|
|
|
||
|
|
// Update allocation list
|
||
|
|
for(i=0;i<m_ulResSlots;i++)
|
||
|
|
m_piAllocList[i] = RESERVED;
|
||
|
|
|
||
|
|
// Update free list
|
||
|
|
for(i=m_ulResSlots;i<m_ulCurSize-1;i++)
|
||
|
|
m_piAllocList[i] = i+2;
|
||
|
|
m_piAllocList[m_ulCurSize-1] = NOFREEITEM;
|
||
|
|
m_iFree = m_ulResSlots+1;
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
BOOL CArray<T>::ShiftToEnd(unsigned long ulNode)
|
||
|
|
{
|
||
|
|
// Sanity check
|
||
|
|
if(ulNode<=m_ulResSlots || m_piAllocList[ulNode-1]!=ALLOCATED)
|
||
|
|
return(FALSE);
|
||
|
|
|
||
|
|
// Degenerate case
|
||
|
|
if(!m_pBuffer[ulNode-1].next) {
|
||
|
|
Win4Assert(ulNode==m_ulTailNode);
|
||
|
|
return(TRUE);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Fix link info
|
||
|
|
m_pBuffer[m_ulTailNode-1].next = m_ulHeadNode;
|
||
|
|
m_pBuffer[m_ulHeadNode-1].prev = m_ulTailNode;
|
||
|
|
m_ulHeadNode = m_pBuffer[ulNode-1].next;
|
||
|
|
m_pBuffer[m_ulHeadNode-1].prev = 0;
|
||
|
|
m_ulTailNode = ulNode;
|
||
|
|
m_pBuffer[m_ulTailNode-1].next = 0;
|
||
|
|
|
||
|
|
return(TRUE);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
T* CArray<T>::GetNext(unsigned long& index)
|
||
|
|
{
|
||
|
|
// Sanity check
|
||
|
|
if(index>m_ulCurSize)
|
||
|
|
return(0);
|
||
|
|
|
||
|
|
// Search for the next valid item in the buffer
|
||
|
|
unsigned long i=index;
|
||
|
|
|
||
|
|
// Search the reserved slots
|
||
|
|
while(i<m_ulResSlots) {
|
||
|
|
++i;
|
||
|
|
if(m_piAllocList[i-1]==ALLOCATED) {
|
||
|
|
index = i;
|
||
|
|
return(&m_pBuffer[i-1].item);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Skip to the next normal node
|
||
|
|
if(i==m_ulResSlots)
|
||
|
|
i = m_ulHeadNode;
|
||
|
|
else {
|
||
|
|
Win4Assert(m_piAllocList[i-1]==ALLOCATED);
|
||
|
|
i = m_pBuffer[i-1].next;
|
||
|
|
}
|
||
|
|
|
||
|
|
if(i) {
|
||
|
|
Win4Assert(m_piAllocList[i-1]==ALLOCATED);
|
||
|
|
index = i;
|
||
|
|
return(&m_pBuffer[i-1].item);
|
||
|
|
}
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
T* CArray<T>::GetPrev(unsigned long& index)
|
||
|
|
{
|
||
|
|
// Sanity check
|
||
|
|
if(index<1)
|
||
|
|
return 0;
|
||
|
|
|
||
|
|
// Search for the previous valid item in the buffer
|
||
|
|
unsigned long i=index;
|
||
|
|
|
||
|
|
// Skip to the previous normal node
|
||
|
|
if(i>m_ulResSlots) {
|
||
|
|
Win4Assert(m_piAllocList[i-1]==ALLOCATED);
|
||
|
|
i = m_pBuffer[i-1].prev;
|
||
|
|
if(i) {
|
||
|
|
Win4Assert(m_piAllocList[i-1]==ALLOCATED);
|
||
|
|
index = i;
|
||
|
|
return(&m_pBuffer[i-1].item);
|
||
|
|
}
|
||
|
|
else
|
||
|
|
i = m_ulResSlots+1;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Search the reserved slots
|
||
|
|
while(i>1) {
|
||
|
|
--i;
|
||
|
|
if(m_piAllocList[i-1]==ALLOCATED) {
|
||
|
|
index = i;
|
||
|
|
return(&m_pBuffer[i-1].item);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
CArray<T>& CArray<T>::operator=(const CArray<T>& a)
|
||
|
|
{
|
||
|
|
// Check to see, if this a=a case
|
||
|
|
if(this==&a)
|
||
|
|
return(*this);
|
||
|
|
|
||
|
|
// Self destroy
|
||
|
|
CArray<T>::~CArray();
|
||
|
|
|
||
|
|
// Now, make a copy
|
||
|
|
MakeCopy(a);
|
||
|
|
|
||
|
|
return(*this);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
ostream& operator<<(ostream& os, CArray<T>& a)
|
||
|
|
{
|
||
|
|
unsigned long i, index;
|
||
|
|
|
||
|
|
a.Reset(index);
|
||
|
|
os << "Length = " << a.m_ulLength <<
|
||
|
|
" Current Size = " << a.m_ulCurSize << endl;
|
||
|
|
|
||
|
|
if(a.m_ulLength) {
|
||
|
|
os << '[';
|
||
|
|
for(i=0;i<a.m_ulLength-1;i++)
|
||
|
|
os << *(a.GetNext(index)) << ',';
|
||
|
|
os << *(a.GetNext(index)) << ']' << endl;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
os << "[]" << endl;
|
||
|
|
|
||
|
|
return(os);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
void CArray<T>::Dump()
|
||
|
|
{
|
||
|
|
unsigned long i;
|
||
|
|
|
||
|
|
cerr << "Current Size = " << m_ulCurSize << endl;
|
||
|
|
cerr << "HeadNode = " << m_ulHeadNode << endl;
|
||
|
|
cerr << "TailNode = " << m_ulTailNode << endl;
|
||
|
|
cerr << "FreeNode = " << m_iFree << endl;
|
||
|
|
|
||
|
|
if(m_ulCurSize) {
|
||
|
|
cerr << '[';
|
||
|
|
for(i=0;i<m_ulCurSize-1;i++) {
|
||
|
|
if(m_piAllocList[i]==ALLOCATED)
|
||
|
|
cerr << '(' << m_pBuffer[i].item << ',' << m_pBuffer[i].prev << ','
|
||
|
|
<< m_pBuffer[i].next << "),";
|
||
|
|
else
|
||
|
|
cerr << '(' << "NULL," << m_pBuffer[i].prev << ','
|
||
|
|
<< m_pBuffer[i].next << "),";
|
||
|
|
}
|
||
|
|
if(m_piAllocList[m_ulCurSize-1]==ALLOCATED)
|
||
|
|
cerr << '(' << m_pBuffer[m_ulCurSize-1].item << ','
|
||
|
|
<< m_pBuffer[m_ulCurSize-1].prev << ','
|
||
|
|
<< m_pBuffer[m_ulCurSize-1].next << ")]" << endl;
|
||
|
|
else
|
||
|
|
cerr << '(' << "NULL,"
|
||
|
|
<< m_pBuffer[m_ulCurSize-1].prev << ','
|
||
|
|
<< m_pBuffer[m_ulCurSize-1].next << ")]" << endl;
|
||
|
|
|
||
|
|
cerr << '[';
|
||
|
|
for(i=0;i<m_ulCurSize-1;i++)
|
||
|
|
cerr << m_piAllocList[i] << ',';
|
||
|
|
cerr << m_piAllocList[m_ulCurSize-1] << ']' << endl;
|
||
|
|
}
|
||
|
|
else
|
||
|
|
cerr << "[]" << endl;
|
||
|
|
|
||
|
|
return;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <class T>
|
||
|
|
class CInterfacePtr
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
// Default Constructor
|
||
|
|
CInterfacePtr(T* a=NULL) {
|
||
|
|
m_ptr = a;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Copy constructor
|
||
|
|
CInterfacePtr(const CInterfacePtr& a) {
|
||
|
|
m_ptr = a.m_ptr;
|
||
|
|
if(m_ptr)
|
||
|
|
m_ptr->AddRef();
|
||
|
|
}
|
||
|
|
|
||
|
|
// Destructor
|
||
|
|
~CInterfacePtr() {
|
||
|
|
if(m_ptr)
|
||
|
|
m_ptr->Release();
|
||
|
|
}
|
||
|
|
|
||
|
|
// New and Delete operators
|
||
|
|
void* operator new(size_t size) {
|
||
|
|
return PrivMemAlloc(size);
|
||
|
|
};
|
||
|
|
void operator delete(void *pv){
|
||
|
|
PrivMemFree(pv);
|
||
|
|
return;
|
||
|
|
};
|
||
|
|
|
||
|
|
// Operators
|
||
|
|
operator T*() {
|
||
|
|
return(m_ptr);
|
||
|
|
}
|
||
|
|
T* operator->() {
|
||
|
|
return(m_ptr);
|
||
|
|
}
|
||
|
|
T& operator*() {
|
||
|
|
return(*m_ptr);
|
||
|
|
}
|
||
|
|
T& operator[](int i) {
|
||
|
|
return(m_ptr[i]);
|
||
|
|
}
|
||
|
|
T** operator&() {
|
||
|
|
return(&m_ptr);
|
||
|
|
}
|
||
|
|
const CInterfacePtr& operator=(T* a) {
|
||
|
|
// Check for a=a case
|
||
|
|
if(this->m_ptr==a)
|
||
|
|
return(*this);
|
||
|
|
|
||
|
|
// Self destroy
|
||
|
|
CInterfacePtr<T>::~CInterfacePtr();
|
||
|
|
|
||
|
|
m_ptr = a;
|
||
|
|
if(m_ptr)
|
||
|
|
m_ptr->AddRef();
|
||
|
|
|
||
|
|
return(*this);
|
||
|
|
}
|
||
|
|
|
||
|
|
private:
|
||
|
|
T* m_ptr;
|
||
|
|
};
|
||
|
|
|
||
|
|
#endif // Array_hxx
|