#ifndef __GOODLINKLIST_H__ #define __GOODLINKLIST_H__ #include "stdlithdefs.h" #include "genlist.h" #ifndef ASSERT #define ASSERT #endif #ifndef DWORD // PORT(macOS/LP64): `long` was 32-bit on Win32 but is 64-bit here. // NB the `#ifndef` guard above never fires against a windows.h that // *typedefs* these names -- a typedef is not a macro -- so this // definition wins textually and must itself be the right width. #if defined(__LP64__) || defined(_LP64) #define DWORD unsigned int #else #define DWORD unsigned long #endif #endif class CGLLNode { public: CGLLNode *m_pGPrev, *m_pGNext; }; typedef CGLLNode* GPOS; // This is defined as a separate function because it's called by the virtual // GenFindElement and we don't want to generate a bunch of template code for // every type of object we use in a list. GPOS GLinkedList_FindElementMemcmp( CGLLNode *pHead, const void *pToFind, DWORD elementSize); template class CGLinkedList : public GenList { protected: public: CGLinkedList() { m_nElements = 0; m_pHead = NULL; } ~CGLinkedList() { RemoveAll(); } inline void Term() {RemoveAll();} operator DWORD() {return m_nElements;} operator GPOS() { return m_pHead; } DWORD GetCount() const { return m_nElements; } DWORD GetSize() const { return m_nElements; } int IsEmpty() const { return !m_pHead; } inline T GetHead() const; inline T GetTail() const; inline T RemoveHead(); inline T RemoveTail(); inline void Append(T newTail) { AddTail(newTail); } inline GPOS AddHead( T newHead ); inline GPOS AddTail( T newTail ); inline void RemoveAll(); GPOS GetHeadPosition() const { return m_pHead; } GPOS GetTailPosition() const { return (m_pHead ? m_pHead->m_pGPrev : NULL); } inline T GetNext( GPOS &pos ) const; inline T GetPrev( GPOS &pos ) const; inline T GetAt( GPOS pos ) const; inline void RemoveAt( GPOS pos ); GPOS InsertBefore( GPOS pos, T el ); GPOS InsertAfter( GPOS pos, T el ); // Find and compare with T::operator==. GPOS Find( T searchFor, DWORD *pIndex=NULL ) const; DWORD FindElement( T searchFor, GPOS *pPos=NULL ) const; GPOS FindIndex( DWORD index ) const; // Copy the source list. This also calls _Term_ on theList. void StealList(CGLinkedList &theList); // Yes, we can be a hash bucket. static void CheckSupportHashBucket() {} // GenList implementation. public: virtual GenListPos GenBegin() const { #ifdef _DEBUG return GenListPos(GetHeadPosition(), 0); #else return GenListPos(GetHeadPosition()); #endif } virtual BOOL GenIsValid(const GenListPos &pos) const { return !!pos.m_Pos; } virtual T GenGetNext(GenListPos &pos) const { #ifdef _DEBUG ++pos.m_Index; #endif return GetNext(*((GPOS*)&pos.m_Pos)); } virtual T GenGetAt(GenListPos &pos) const { return GetAt(*((GPOS*)&pos.m_Pos)); } virtual BOOL GenAppend(T &toAppend) { Append(toAppend); return TRUE; } virtual void GenRemoveAt(GenListPos pos) { RemoveAt((GPOS)pos.m_Pos); } virtual void GenRemoveAll() { RemoveAll(); } virtual DWORD GenGetSize() const { return GetSize(); } virtual BOOL GenCopyList(const GenList &other) { RemoveAll(); return GenAppendList(other); } virtual BOOL GenAppendList(const GenList &other) { GenListPos pos; for(pos=other.GenBegin(); other.GenIsValid(pos); ) { Append(other.GenGetNext(pos)); } return TRUE; } virtual BOOL GenFindElement(const T &toFind, GenListPos &thePos) const { thePos.m_Pos = GLinkedList_FindElementMemcmp( m_pHead, &toFind, sizeof(T)); return !!thePos.m_Pos; } protected: DWORD m_nElements; CGLLNode *m_pHead; }; template inline T CGLinkedList::GetHead() const { ASSERT(m_pHead); return (T)m_pHead; } template inline T CGLinkedList::GetTail() const { ASSERT(m_pHead); return (T)m_pHead->m_pGPrev; } template inline T CGLinkedList::GetNext( GPOS &pos ) const { T ret = (T)pos; if( pos->m_pGNext == m_pHead ) pos = NULL; else pos = pos->m_pGNext; return ret; } template inline T CGLinkedList::GetPrev( GPOS &pos ) const { T ret = (T)pos; if( pos->m_pGPrev == m_pHead ) pos = NULL; else pos = pos->m_pGPrev; return ret; } template inline T CGLinkedList::RemoveHead() { T ret; ASSERT( m_pHead ); ret = (T)m_pHead; RemoveAt( m_pHead ); return ret; } template inline T CGLinkedList::RemoveTail() { T ret; ASSERT( m_pHead ); ret = (T)m_pHead->m_pGPrev; RemoveAt( m_pHead->m_pGPrev ); return ret; } template inline GPOS CGLinkedList::AddHead( T newHead ) { if( m_pHead ) { return InsertBefore( m_pHead, newHead ); } else { CGLLNode *pNode = (CGLLNode*)newHead; pNode->m_pGNext = (CGLLNode*)newHead; pNode->m_pGPrev = (CGLLNode*)newHead; m_pHead = (CGLLNode*)newHead; ++m_nElements; return m_pHead; } } template inline GPOS CGLinkedList::AddTail( T newTail ) { if( m_pHead ) return InsertAfter( m_pHead->m_pGPrev, newTail ); else return AddHead( newTail ); } template inline void CGLinkedList::RemoveAll() { m_pHead = NULL; m_nElements = 0; } template inline T CGLinkedList::GetAt( GPOS pos ) const { return (T)pos; } template void CGLinkedList::RemoveAt( GPOS pos ) { ASSERT( m_nElements > 0 ); pos->m_pGPrev->m_pGNext = pos->m_pGNext; pos->m_pGNext->m_pGPrev = pos->m_pGPrev; if( pos == m_pHead ) m_pHead = m_pHead->m_pGNext; --m_nElements; if( m_nElements == 0 ) m_pHead = NULL; } template GPOS CGLinkedList::InsertBefore( GPOS pos, T el ) { pos->m_pGPrev->m_pGNext = (CGLLNode*)el; ((CGLLNode*)el)->m_pGPrev = pos->m_pGPrev; ((CGLLNode*)el)->m_pGNext = pos; pos->m_pGPrev = (CGLLNode*)el; ++m_nElements; if( ((CGLLNode*)el)->m_pGNext == m_pHead ) m_pHead = (CGLLNode*)el; return (CGLLNode*)el; } template GPOS CGLinkedList::InsertAfter( GPOS pos, T el ) { pos->m_pGNext->m_pGPrev = (CGLLNode*)el; ((CGLLNode*)el)->m_pGNext = pos->m_pGNext; ((CGLLNode*)el)->m_pGPrev = pos; pos->m_pGNext = (CGLLNode*)el; ++m_nElements; return (CGLLNode*)el; } template GPOS CGLinkedList::Find( T searchFor, DWORD *pIndex ) const { T pCur; DWORD index = 0; if( m_pHead ) { pCur = (T)m_pHead; do { if( pCur == searchFor ) { if( pIndex ) *pIndex = index; return pCur; } pCur = (T)pCur->m_pGNext; ++index; } while( pCur != (T)m_pHead ); } if( pIndex ) *pIndex = BAD_INDEX; return NULL; } template DWORD CGLinkedList::FindElement( T searchFor, GPOS *pPos ) const { GPOS pos; DWORD index; pos = Find( searchFor, &index ); if( pPos ) *pPos = pos; return index; } template GPOS CGLinkedList::FindIndex( DWORD index ) const { T pCur; if( index >= m_nElements ) return NULL; pCur = (T)m_pHead; do { if( index == 0 ) return pCur; pCur = (T)pCur->m_pGNext; --index; } while( pCur != (T)m_pHead ); ASSERT( FALSE ); // Shouldn't ever get here. return NULL; } template void CGLinkedList::StealList(CGLinkedList &theList) { m_pHead = theList.m_pHead; m_nElements = theList.m_nElements; theList.Term(); } // Useful template function if your linked list is made up of pointers. template void GDeleteAndRemoveElements( CGLinkedList &theList) { GPOS pos; for(pos=theList.GetHeadPosition(); pos != NULL;) delete (T)(theList.GetNext(pos)); theList.RemoveAll(); } // Useful template function if your linked list is made up of pointers. template void GDeleteAndRemoveElementsOB(CGLinkedList &theList, OB &objectBank) { GPOS pos; for(pos=theList.GetHeadPosition(); pos != NULL;) { objectBank.Free((T)(theList.GetNext(pos))); } theList.RemoveAll(); } #endif // __GOODLINKLIST_H__