//---------------------------------------------------------- // // MODULE : FASTLIST.H // // PUROSE : CFastList definition file // // CREATED : 10 / 27 / 1996 // //---------------------------------------------------------- #ifndef __FASTLIST_H_ #define __FASTLIST_H_ // Includes.... template struct CFastListNode { public: // Constructor CFastListNode() { m_pPrev = NULL; m_pNext = NULL; } // Accessors CFastListNode* GetPrev() { return m_pPrev; } CFastListNode* GetNext() { return m_pNext; } T GetData() { return m_Data; } CFastListNode *m_pPrev; CFastListNode *m_pNext; T m_Data; }; template class CFastList { public: // Constructor CFastList(); CFastList(int nTotalElem); // Destructor ~CFastList() { Term(); } // Member Functions void Term(BOOL bDeAlloc = TRUE); BOOL AddHead(T data); BOOL AddTail(T data); BOOL InsertAfter(CFastListNode *pNode, T data); BOOL InsertBefore(CFastListNode *pNode, T data); T RemoveHead(); T RemoveTail(); void Remove(CFastListNode *pNode); void Remove(T data); void RemoveAll() { Term(); } CFastListNode* Find(T data); T Get(DWORD dwIndex); int GetIndex(T data); // Accessors CFastListNode* GetBlock() { return m_pBlock; } CFastListNode* GetHead() { return m_pHead; } CFastListNode* GetTail() { return m_pTail; } DWORD GetSize() { return m_nSize; } private: // Member Functions void AllocMem(int nTotalElem); // Member Variables CFastListNode *m_pBlock; CFastListNode *m_pFreeList; CFastListNode *m_pHead; CFastListNode *m_pTail; DWORD m_nSize; DWORD m_nTotalElem; BOOL m_bAllocated; }; //---------------------------------------------------------- // // FUNCTION : CFastList() // // PURPOSE : Standard constructor // //---------------------------------------------------------- template inline CFastList::CFastList() { m_pBlock = NULL; m_pHead = NULL; m_pTail = NULL; m_nSize = 0; // Allocate the memory AllocMem(100); } //---------------------------------------------------------- // // FUNCTION : CFastList() // // PURPOSE : Standard constructor // //---------------------------------------------------------- template inline CFastList::CFastList(int nTotalElem) { m_pBlock = NULL; m_pHead = NULL; m_pTail = NULL; m_nSize = 0; // Allocate the memory AllocMem(nTotalElem); } //---------------------------------------------------------- // // FUNCTION : CFastList::Term() // // PURPOSE : Terminates a CFastList // //---------------------------------------------------------- template inline void CFastList::Term(BOOL bDeAlloc) { if (m_pBlock) debug_deletea(m_pBlock); m_pBlock = NULL; m_pHead = NULL; m_pTail = NULL; m_pFreeList = NULL; m_nSize = 0; if (!bDeAlloc) AllocMem(m_nTotalElem); } //---------------------------------------------------------- // // FUNCTION : CFastList::AddHead() // // PURPOSE : Adds an element to the head of the array // //---------------------------------------------------------- template inline BOOL CFastList::AddHead(T data) { if (!m_pHead) { m_pHead = debug_new(CFastListNode); if (!m_pRoot) return FALSE; m_pHead->m_Data = data; if (!m_pTail) m_pTail = m_pHead; } else { CFastListNode *pNewNode = debug_new(CFastListNode); if (!pNewNode) return FALSE; m_pHead->m_pPrev = pNewNode; pNewNode->m_pNext = m_pHead; pNewNode->m_Data = data; m_pHead = pNewNode; } m_nSize ++; // Success !! return TRUE; } //---------------------------------------------------------- // // FUNCTION : CFastList::AddTail() // // PURPOSE : Adds an element to the tail of the array // //---------------------------------------------------------- template inline BOOL CFastList::AddTail(T data) { if (!m_pTail) { m_pTail = m_pFreeList; if (!m_pTail) return FALSE; m_pFreeList = m_pFreeList->m_pNext; m_pFreeList->m_pPrev = NULL; m_pTail->m_pPrev = NULL; m_pTail->m_pNext = NULL; m_pTail->m_Data = data; if (!m_pHead) m_pHead = m_pTail; } else { CFastListNode *pNewNode = m_pFreeList; if (!pNewNode) return FALSE; m_pFreeList = m_pFreeList->m_pNext; m_pFreeList->m_pPrev = NULL; pNewNode->m_pPrev = NULL; pNewNode->m_pNext = NULL; m_pTail->m_pNext = pNewNode; pNewNode->m_pPrev = m_pTail; pNewNode->m_Data = data; m_pTail = pNewNode; } m_nSize ++; // Success !! return TRUE; } //---------------------------------------------------------- // // FUNCTION : CFastList::InsertAfter() // // PURPOSE : Inserts an element into the list // //---------------------------------------------------------- template inline BOOL CFastList::InsertAfter(CFastListNode *pNode, T data) { CFastListNode *pNewNode = m_pFreeList; if (!pNewNode) return FALSE; m_pFreeList = m_pFreeList->m_pNext; m_pFreeList->m_pPrev = NULL; pNewNode->m_pNext = NULL; pNewNode->m_pPrev = NULL; // Copy in data pNewNode->m_Data = data; pNewNode->m_pPrev = pNode; if (pNode->m_pNext) { pNewNode->m_pNext = pNode->m_pNext; pNode->m_pNext->m_pPrev = pNewNode; } else { m_pTail = pNewNode; } pNode->m_pNext = pNewNode; m_nSize ++; // Success !! return TRUE; } //---------------------------------------------------------- // // FUNCTION : CFastList::InsertBefore() // // PURPOSE : Inserts an element into the list // //---------------------------------------------------------- template inline BOOL CFastList::InsertBefore(CFastListNode *pNode, T data) { CFastListNode *pNewNode = m_pFreeList; if (!pNewNode) return FALSE; m_pFreeList = m_pFreeList->m_pNext; m_pFreeList->m_pPrev = NULL; pNewNode->m_pNext = pNode; if (pNode->m_pPrev) { pNewNode->m_pPrev = pNode->m_pPrev; } else { m_pHead = pNewNode; } pNode->m_pPrev = pNewNode; m_nSize ++; // Success !! return TRUE; } //---------------------------------------------------------- // // FUNCTION : CFastList::RemoveHead() // // PURPOSE : Removes head element // //---------------------------------------------------------- template inline T CFastList::RemoveHead() { CFastListNode *pNode; T Data; if (m_pHead) { pNode = m_pHead; Data = m_pHead->m_Data; m_pHead = m_pHead->m_pNext; if (!m_pHead) { // List is empty.. m_pTail = NULL; } else { if (m_pHead->m_pNext) { // Correct link m_pHead->m_pNext->m_pPrev = m_pHead; } } pNode->m_pNext = m_pFreeList->m_pNext; pNode->m_pPrev = m_pFreeList; m_pFreeList->m_pNext = pNode; m_nSize --; } return Data; } //---------------------------------------------------------- // // FUNCTION : CFastList::RemoveTail() // // PURPOSE : Removes head element // //---------------------------------------------------------- template inline T CFastList::RemoveTail() { CFastListNode *pNode; T Data; if (m_pTail) { pNode = m_pTail; Data = m_pTail->m_Data; if (m_pTail->m_pPrev) { m_pTail = m_pTail->m_pPrev; } else { // List is empty.. m_pHead = NULL; m_pTail = NULL; } m_nSize --; pNode->m_pNext = m_pFreeList->m_pNext; pNode->m_pPrev = m_pFreeList; m_pFreeList->m_pNext = pNode; } return Data; } //---------------------------------------------------------- // // FUNCTION : CFastList::Remove() // // PURPOSE : Removes an element from the list // //---------------------------------------------------------- template inline void CFastList::Remove(CFastListNode *pNode) { CFastListNode *pPrev = pNode->m_pPrev; CFastListNode *pNext = pNode->m_pNext; if ((pPrev) && (pNext)) { pPrev->m_pNext = pNext; pNext->m_pPrev = pPrev; } if ((!pPrev) && (pNext)) { pNext->m_pPrev = NULL; m_pHead = pNext; } if ((pPrev) && (!pNext)) { pPrev->m_pNext = NULL; m_pTail = pPrev; } if ((!pPrev) && (!pNext)) { m_pTail = NULL; m_pHead = NULL; } // Delete link pNode->m_pNext = m_pFreeList->m_pNext; pNode->m_pPrev = m_pFreeList; m_pFreeList->m_pNext = pNode; m_nSize --; } //---------------------------------------------------------- // // FUNCTION : CFastList::Remove() // // PURPOSE : Removes an element from the list (SLOW) // //---------------------------------------------------------- template inline void CFastList::Remove(T data) { CFastListNode *pNode = m_pHead; if (!pNode) return; while (pNode) { if (pNode->m_Data == data) { Remove(pNode); return; } pNode = pNode->m_pNext; } } //---------------------------------------------------------- // // FUNCTION : CFastList::Find() // // PURPOSE : Finds a data element in the list // //---------------------------------------------------------- template inline CFastListNode* CFastList::Find(T data) { CFastListNode *pNode = m_pHead; if (!pNode) return NULL; while (pNode) { if (pNode->m_Data == data) { return pNode; } pNode = pNode->m_pNext; } return NULL; } //---------------------------------------------------------- // // FUNCTION : CFastList::Get() // // PURPOSE : Returns data for a given index // //---------------------------------------------------------- template inline T CFastList::Get(DWORD dwIndex) { CFastListNode *pNode = m_pHead; if (!pNode) return NULL; for (DWORD i = 0; i < dwIndex; i ++) { pNode = pNode->GetNext(); } return pNode->GetData(); } //---------------------------------------------------------- // // FUNCTION : CFastList::GetIndex() // // PURPOSE : Returns an index for a given pointer // //---------------------------------------------------------- template inline int CFastList::GetIndex(T data) { int i = 0; CFastListNode *pNode = m_pHead; if (!pNode) return NULL; while (pNode) { if (pNode->m_Data == data) { return i; } pNode = pNode->m_pNext; i ++; } return -1; } //------------------------------------------------------------------ // // FUNCTION : Alloc() // // PURPOSE : Allocates memory block for list and links it // //------------------------------------------------------------------ template inline void CFastList::AllocMem(int nTotalElem) { if (m_pBlock) debug_deletea(m_pBlock); m_pBlock = debug_newa(CFastListNode, nTotalElem); m_nTotalElem = nTotalElem; m_pFreeList = m_pBlock; // Link up all the nodes CFastListNode *pStart = m_pBlock; pStart->m_pPrev = NULL; pStart->m_pNext = pStart + 1; pStart ++; for (int i = 1; i < nTotalElem - 1; i ++) { pStart->m_pNext = pStart + 1; pStart->m_pPrev = pStart - 1; pStart ++; } pStart->m_pPrev = pStart - 1; pStart->m_pNext = NULL; } #endif