123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279 |
- //
- // File: list.h
- //
- // Description:
- // This file contains codes for a linked list template that
- // can be used as a stack or a queue.
- //
- // History:
- // Mar 5, 1997 jfink Created file.
- // Jan 7, 1998 jfink Added Empty method.
- //
- #ifndef _LIST_H_
- #define _LIST_H_
- #include "base.h"
- template <class TElement> class FListIterator
- {
- public:
- virtual void OnIterate(TElement* pElement, DWORD dw, void* pv) = 0;
- } ;
- template <class TElement> class FList : public CBase
- {
- protected:
- TElement *mpHead, *mpTail;
- DWORD mcElements;
- public:
- FList();
- virtual ~FList();
- DWORD Length();
- VOID Enqueue(TElement *pElement);
- TElement *Dequeue();
- VOID Push(TElement *pElement);
- TElement *Pop();
- TElement *Find(const TElement &Element);
- TElement *Find(TElement *pStart, const TElement &Element);
- TElement *Remove(const TElement &Element);
- TElement *Remove(TElement *pELement);
- void Iterate(FListIterator<TElement>* pIterator, DWORD dw, void* pv);
- VOID Empty();
- } ;
- template <class TElement>
- FList<TElement>::FList() : CBase()
- {
- mpHead = mpTail = NULL;
- mcElements = 0;
- }
- template <class TElement>
- FList<TElement>::~FList()
- {
- this->Empty();
- }
- template <class TElement>
- DWORD FList<TElement>::Length()
- {
- return(mcElements);
- }
- template <class TElement>
- VOID FList<TElement>::Enqueue(TElement *pElement)
- {
- this->Lock();
- if (NULL == mpHead)
- mpHead = pElement;
- else
- mpTail->mpNext = pElement;
- mpTail = pElement;
- pElement->mpNext = NULL;
- mcElements++;
- this->Unlock();
- }
- template <class TElement>
- TElement *FList<TElement>::Dequeue()
- {
- TElement *pTemp;
- this->Lock();
- pTemp = mpHead;
- if (NULL != mpHead)
- {
- mpHead = mpHead->mpNext;
- pTemp->mpNext = NULL;
- mcElements--;
- } else
- mpTail = NULL;
- this->Unlock();
- return(pTemp);
- }
- template <class TElement>
- VOID FList<TElement>::Iterate(FListIterator<TElement>* pIterator, DWORD dw, void* pv)
- {
- if (!pIterator)
- return;
- this->Lock();
- for (TElement* pTemp = mpHead; NULL != pTemp; pTemp = pTemp->mpNext)
- {
- pIterator->OnIterate(pTemp, dw, pv);
- }
- this->Unlock();
- }
- template <class TElement>
- VOID FList<TElement>::Push(TElement *pElement)
- {
- if (pElement)
- {
- this->Lock();
- if (NULL == mpHead)
- mpTail = pElement;
- pElement->mpNext = mpHead;
- mpHead = pElement;
- mcElements++;
- this->Unlock();
- }
- }
- template <class TElement>
- TElement *FList<TElement>::Pop()
- {
- return(this->Dequeue());
- }
- //
- // Find the element in the list, starting a pStart, whose contents
- // match Element.
- //
- template <class TElement>
- TElement *FList<TElement>::Find(TElement *pStart, const TElement &Element)
- {
- TElement *pLoop;
-
- this->Lock();
- for(pLoop = pStart; NULL != pLoop; pLoop = pLoop->mpNext)
- {
- if (pLoop->Find(Element))
- break;
- }
- this->Unlock();
- return(pLoop);
- }
- //
- // Find the element in the list, starting at the head, whose contents
- // match Element.
- //
- template <class TElement>
- TElement *FList<TElement>::Find(const TElement &Element)
- {
- return(this->Find(mpHead, Element));
- }
- //
- // Remove the element from the list whose contents match
- // Element.
- //
- template <class TElement>
- TElement *FList<TElement>::Remove(const TElement &Element)
- {
- TElement *pLoop, *pPrev;
-
- this->Lock();
- for(pPrev = NULL, pLoop = mpHead;
- NULL != pLoop;
- pPrev = pLoop, pLoop = pLoop->mpNext)
- {
- if (*pLoop == Element)
- {
- //
- // Remove the node from the list.
- //
- if (pLoop == mpHead)
- mpHead = pLoop->mpNext;
- else
- pPrev->mpNext = pLoop->mpNext;
- if (pLoop == mpTail)
- mpTail = pPrev;
- pLoop->mpNext = NULL;
- mcElements--;
- break;
- }
- }
- this->Unlock();
- return(pLoop);
- }
- //
- // Remove the element from the list whose pointer matches
- // pElement.
- //
- template <class TElement>
- TElement *FList<TElement>::Remove(TElement * pElement)
- {
- TElement *pLoop, *pPrev;
-
- this->Lock();
- for(pPrev = NULL, pLoop = mpHead;
- NULL != pLoop;
- pPrev = pLoop, pLoop = pLoop->mpNext)
- {
- if (pLoop == pElement)
- {
- //
- // Remove the node from the list.
- //
- if (pLoop == mpHead)
- mpHead = pLoop->mpNext;
- else
- pPrev->mpNext = pLoop->mpNext;
- if (pLoop == mpTail)
- mpTail = pPrev;
- pLoop->mpNext = NULL;
- mcElements--;
- break;
- }
- }
- this->Unlock();
- return(pLoop);
- }
- template <class TElement>
- VOID FList<TElement>::Empty()
- {
- TElement *pElement;
- this->Lock();
- while(pElement = this->Pop())
- {
- delete pElement;
- }
- this->Unlock();
- }
- #endif
|