123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553 |
- //------------------------------------------------------------------------------
- // File: WXList.h
- //
- // Desc: DirectShow base classes - defines a non-MFC generic template list
- // class.
- //
- // Copyright (c) 1992-2001 Microsoft Corporation. All rights reserved.
- //------------------------------------------------------------------------------
- /* A generic list of pointers to objects.
- No storage management or copying is done on the objects pointed to.
- Objectives: avoid using MFC libraries in ndm kernel mode and
- provide a really useful list type.
- The class is thread safe in that separate threads may add and
- delete items in the list concurrently although the application
- must ensure that constructor and destructor access is suitably
- synchronised. An application can cause deadlock with operations
- which use two lists by simultaneously calling
- list1->Operation(list2) and list2->Operation(list1). So don't!
- The names must not conflict with MFC classes as an application
- may use both.
- */
- #ifndef __WXLIST__
- #define __WXLIST__
- /* A POSITION represents (in some fashion that's opaque) a cursor
- on the list that can be set to identify any element. NULL is
- a valid value and several operations regard NULL as the position
- "one step off the end of the list". (In an n element list there
- are n+1 places to insert and NULL is that "n+1-th" value).
- The POSITION of an element in the list is only invalidated if
- that element is deleted. Move operations may mean that what
- was a valid POSITION in one list is now a valid POSITION in
- a different list.
- Some operations which at first sight are illegal are allowed as
- harmless no-ops. For instance RemoveHead is legal on an empty
- list and it returns NULL. This allows an atomic way to test if
- there is an element there, and if so, get it. The two operations
- AddTail and RemoveHead thus implement a MONITOR (See Hoare's paper).
- Single element operations return POSITIONs, non-NULL means it worked.
- whole list operations return a BOOL. TRUE means it all worked.
- This definition is the same as the POSITION type for MFCs, so we must
- avoid defining it twice.
- */
- #ifndef __AFX_H__
- struct __POSITION { int unused; };
- typedef __POSITION* POSITION;
- #endif
- const int DEFAULTCACHE = 10; /* Default node object cache size */
- /* A class representing one node in a list.
- Each node knows a pointer to it's adjacent nodes and also a pointer
- to the object that it looks after.
- All of these pointers can be retrieved or set through member functions.
- */
- class CBaseList
- #ifdef DEBUG
- : public CBaseObject
- #endif
- {
- /* Making these classes inherit from CBaseObject does nothing
- functionally but it allows us to check there are no memory
- leaks in debug builds.
- */
- public:
- #ifdef DEBUG
- class CNode : public CBaseObject {
- #else
- class CNode {
- #endif
- CNode *m_pPrev; /* Previous node in the list */
- CNode *m_pNext; /* Next node in the list */
- void *m_pObject; /* Pointer to the object */
- public:
- /* Constructor - initialise the object's pointers */
- CNode()
- #ifdef DEBUG
- : CBaseObject(NAME("List node"))
- #endif
- {
- };
- /* Return the previous node before this one */
- __out CNode *Prev() const { return m_pPrev; };
- /* Return the next node after this one */
- __out CNode *Next() const { return m_pNext; };
- /* Set the previous node before this one */
- void SetPrev(__in_opt CNode *p) { m_pPrev = p; };
- /* Set the next node after this one */
- void SetNext(__in_opt CNode *p) { m_pNext = p; };
- /* Get the pointer to the object for this node */
- __out void *GetData() const { return m_pObject; };
- /* Set the pointer to the object for this node */
- void SetData(__in void *p) { m_pObject = p; };
- };
- class CNodeCache
- {
- public:
- CNodeCache(INT iCacheSize) : m_iCacheSize(iCacheSize),
- m_pHead(NULL),
- m_iUsed(0)
- {};
- ~CNodeCache() {
- CNode *pNode = m_pHead;
- while (pNode) {
- CNode *pCurrent = pNode;
- pNode = pNode->Next();
- delete pCurrent;
- }
- };
- void AddToCache(__inout CNode *pNode)
- {
- if (m_iUsed < m_iCacheSize) {
- pNode->SetNext(m_pHead);
- m_pHead = pNode;
- m_iUsed++;
- } else {
- delete pNode;
- }
- };
- CNode *RemoveFromCache()
- {
- CNode *pNode = m_pHead;
- if (pNode != NULL) {
- m_pHead = pNode->Next();
- m_iUsed--;
- ASSERT(m_iUsed >= 0);
- } else {
- ASSERT(m_iUsed == 0);
- }
- return pNode;
- };
- private:
- INT m_iCacheSize;
- INT m_iUsed;
- CNode *m_pHead;
- };
- protected:
- CNode* m_pFirst; /* Pointer to first node in the list */
- CNode* m_pLast; /* Pointer to the last node in the list */
- LONG m_Count; /* Number of nodes currently in the list */
- private:
- CNodeCache m_Cache; /* Cache of unused node pointers */
- private:
- /* These override the default copy constructor and assignment
- operator for all list classes. They are in the private class
- declaration section so that anybody trying to pass a list
- object by value will generate a compile time error of
- "cannot access the private member function". If these were
- not here then the compiler will create default constructors
- and assignment operators which when executed first take a
- copy of all member variables and then during destruction
- delete them all. This must not be done for any heap
- allocated data.
- */
- CBaseList(const CBaseList &refList);
- CBaseList &operator=(const CBaseList &refList);
- public:
- CBaseList(__in_opt LPCTSTR pName,
- INT iItems);
- CBaseList(__in_opt LPCTSTR pName);
- #ifdef UNICODE
- CBaseList(__in_opt LPCSTR pName,
- INT iItems);
- CBaseList(__in_opt LPCSTR pName);
- #endif
- ~CBaseList();
- /* Remove all the nodes from *this i.e. make the list empty */
- void RemoveAll();
- /* Return a cursor which identifies the first element of *this */
- __out_opt POSITION GetHeadPositionI() const;
- /* Return a cursor which identifies the last element of *this */
- __out_opt POSITION GetTailPositionI() const;
- /* Return the number of objects in *this */
- int GetCountI() const;
- protected:
- /* Return the pointer to the object at rp,
- Update rp to the next node in *this
- but make it NULL if it was at the end of *this.
- This is a wart retained for backwards compatibility.
- GetPrev is not implemented.
- Use Next, Prev and Get separately.
- */
- __out void *GetNextI(__inout POSITION& rp) const;
- /* Return a pointer to the object at p
- Asking for the object at NULL will return NULL harmlessly.
- */
- __out_opt void *GetI(__in_opt POSITION p) const;
- __out void *GetValidI(__in POSITION p) const;
- public:
- /* return the next / prev position in *this
- return NULL when going past the end/start.
- Next(NULL) is same as GetHeadPosition()
- Prev(NULL) is same as GetTailPosition()
- An n element list therefore behaves like a n+1 element
- cycle with NULL at the start/end.
- !!WARNING!! - This handling of NULL is DIFFERENT from GetNext.
- Some reasons are:
- 1. For a list of n items there are n+1 positions to insert
- These are conveniently encoded as the n POSITIONs and NULL.
- 2. If you are keeping a list sorted (fairly common) and you
- search forward for an element to insert before and don't
- find it you finish up with NULL as the element before which
- to insert. You then want that NULL to be a valid POSITION
- so that you can insert before it and you want that insertion
- point to mean the (n+1)-th one that doesn't have a POSITION.
- (symmetrically if you are working backwards through the list).
- 3. It simplifies the algebra which the methods generate.
- e.g. AddBefore(p,x) is identical to AddAfter(Prev(p),x)
- in ALL cases. All the other arguments probably are reflections
- of the algebraic point.
- */
- __out_opt POSITION Next(__in_opt POSITION pos) const
- {
- if (pos == NULL) {
- return (POSITION) m_pFirst;
- }
- CNode *pn = (CNode *) pos;
- return (POSITION) pn->Next();
- } //Next
- // See Next
- __out_opt POSITION Prev(__in_opt POSITION pos) const
- {
- if (pos == NULL) {
- return (POSITION) m_pLast;
- }
- CNode *pn = (CNode *) pos;
- return (POSITION) pn->Prev();
- } //Prev
- /* Return the first position in *this which holds the given
- pointer. Return NULL if the pointer was not not found.
- */
- protected:
- __out_opt POSITION FindI( __in void * pObj) const;
- // ??? Should there be (or even should there be only)
- // ??? POSITION FindNextAfter(void * pObj, POSITION p)
- // ??? And of course FindPrevBefore too.
- // ??? List.Find(&Obj) then becomes List.FindNextAfter(&Obj, NULL)
- /* Remove the first node in *this (deletes the pointer to its
- object from the list, does not free the object itself).
- Return the pointer to its object.
- If *this was already empty it will harmlessly return NULL.
- */
- __out_opt void *RemoveHeadI();
- /* Remove the last node in *this (deletes the pointer to its
- object from the list, does not free the object itself).
- Return the pointer to its object.
- If *this was already empty it will harmlessly return NULL.
- */
- __out_opt void *RemoveTailI();
- /* Remove the node identified by p from the list (deletes the pointer
- to its object from the list, does not free the object itself).
- Asking to Remove the object at NULL will harmlessly return NULL.
- Return the pointer to the object removed.
- */
- __out_opt void *RemoveI(__in_opt POSITION p);
- /* Add single object *pObj to become a new last element of the list.
- Return the new _tail position, NULL if it fails.
- If you are adding a COM objects, you might want AddRef it first.
- Other existing POSITIONs in *this are still valid
- */
- __out_opt POSITION AddTailI(__in void * pObj);
- public:
- /* Add all the elements in *pList to the _tail of *this.
- This duplicates all the nodes in *pList (i.e. duplicates
- all its pointers to objects). It does not duplicate the objects.
- If you are adding a list of pointers to a COM object into the list
- it's a good idea to AddRef them all it when you AddTail it.
- Return TRUE if it all worked, FALSE if it didn't.
- If it fails some elements may have been added.
- Existing POSITIONs in *this are still valid
- If you actually want to MOVE the elements, use MoveToTail instead.
- */
- BOOL AddTail(__in CBaseList *pList);
- /* Mirror images of AddHead: */
- /* Add single object to become a new first element of the list.
- Return the new _head position, NULL if it fails.
- Existing POSITIONs in *this are still valid
- */
- protected:
- __out_opt POSITION AddHeadI(__in void * pObj);
- public:
- /* Add all the elements in *pList to the _head of *this.
- Same warnings apply as for AddTail.
- Return TRUE if it all worked, FALSE if it didn't.
- If it fails some of the objects may have been added.
- If you actually want to MOVE the elements, use MoveToHead instead.
- */
- BOOL AddHead(__in CBaseList *pList);
- /* Add the object *pObj to *this after position p in *this.
- AddAfter(NULL,x) adds x to the start - equivalent to AddHead
- Return the position of the object added, NULL if it failed.
- Existing POSITIONs in *this are undisturbed, including p.
- */
- protected:
- __out_opt POSITION AddAfterI(__in_opt POSITION p, __in void * pObj);
- public:
- /* Add the list *pList to *this after position p in *this
- AddAfter(NULL,x) adds x to the start - equivalent to AddHead
- Return TRUE if it all worked, FALSE if it didn't.
- If it fails, some of the objects may be added
- Existing POSITIONs in *this are undisturbed, including p.
- */
- BOOL AddAfter(__in_opt POSITION p, __in CBaseList *pList);
- /* Mirror images:
- Add the object *pObj to this-List after position p in *this.
- AddBefore(NULL,x) adds x to the end - equivalent to AddTail
- Return the position of the new object, NULL if it fails
- Existing POSITIONs in *this are undisturbed, including p.
- */
- protected:
- __out_opt POSITION AddBeforeI(__in_opt POSITION p, __in void * pObj);
- public:
- /* Add the list *pList to *this before position p in *this
- AddAfter(NULL,x) adds x to the start - equivalent to AddHead
- Return TRUE if it all worked, FALSE if it didn't.
- If it fails, some of the objects may be added
- Existing POSITIONs in *this are undisturbed, including p.
- */
- BOOL AddBefore(__in_opt POSITION p, __in CBaseList *pList);
- /* Note that AddAfter(p,x) is equivalent to AddBefore(Next(p),x)
- even in cases where p is NULL or Next(p) is NULL.
- Similarly for mirror images etc.
- This may make it easier to argue about programs.
- */
- /* The following operations do not copy any elements.
- They move existing blocks of elements around by switching pointers.
- They are fairly efficient for long lists as for short lists.
- (Alas, the Count slows things down).
- They split the list into two parts.
- One part remains as the original list, the other part
- is appended to the second list. There are eight possible
- variations:
- Split the list {after/before} a given element
- keep the {_head/_tail} portion in the original list
- append the rest to the {_head/_tail} of the new list.
- Since After is strictly equivalent to Before Next
- we are not in serious need of the Before/After variants.
- That leaves only four.
- If you are processing a list left to right and dumping
- the bits that you have processed into another list as
- you go, the Tail/Tail variant gives the most natural result.
- If you are processing in reverse order, Head/Head is best.
- By using NULL positions and empty lists judiciously either
- of the other two can be built up in two operations.
- The definition of NULL (see Next/Prev etc) means that
- degenerate cases include
- "move all elements to new list"
- "Split a list into two lists"
- "Concatenate two lists"
- (and quite a few no-ops)
- !!WARNING!! The type checking won't buy you much if you get list
- positions muddled up - e.g. use a POSITION that's in a different
- list and see what a mess you get!
- */
- /* Split *this after position p in *this
- Retain as *this the _tail portion of the original *this
- Add the _head portion to the _tail end of *pList
- Return TRUE if it all worked, FALSE if it didn't.
- e.g.
- foo->MoveToTail(foo->GetHeadPosition(), bar);
- moves one element from the _head of foo to the _tail of bar
- foo->MoveToTail(NULL, bar);
- is a no-op, returns NULL
- foo->MoveToTail(foo->GetTailPosition, bar);
- concatenates foo onto the end of bar and empties foo.
- A better, except excessively long name might be
- MoveElementsFromHeadThroughPositionToOtherTail
- */
- BOOL MoveToTail(__in_opt POSITION pos, __in CBaseList *pList);
- /* Mirror image:
- Split *this before position p in *this.
- Retain in *this the _head portion of the original *this
- Add the _tail portion to the start (i.e. _head) of *pList
- e.g.
- foo->MoveToHead(foo->GetTailPosition(), bar);
- moves one element from the _tail of foo to the _head of bar
- foo->MoveToHead(NULL, bar);
- is a no-op, returns NULL
- foo->MoveToHead(foo->GetHeadPosition, bar);
- concatenates foo onto the start of bar and empties foo.
- */
- BOOL MoveToHead(__in_opt POSITION pos, __in CBaseList *pList);
- /* Reverse the order of the [pointers to] objects in *this
- */
- void Reverse();
- /* set cursor to the position of each element of list in turn */
- #define TRAVERSELIST(list, cursor) \
- for ( cursor = (list).GetHeadPosition() \
- ; cursor!=NULL \
- ; cursor = (list).Next(cursor) \
- )
- /* set cursor to the position of each element of list in turn
- in reverse order
- */
- #define REVERSETRAVERSELIST(list, cursor) \
- for ( cursor = (list).GetTailPosition() \
- ; cursor!=NULL \
- ; cursor = (list).Prev(cursor) \
- )
- }; // end of class declaration
- template<class OBJECT> class CGenericList : public CBaseList
- {
- public:
- CGenericList(__in_opt LPCTSTR pName,
- INT iItems,
- BOOL bLock = TRUE,
- BOOL bAlert = FALSE) :
- CBaseList(pName, iItems) {
- UNREFERENCED_PARAMETER(bAlert);
- UNREFERENCED_PARAMETER(bLock);
- };
- CGenericList(__in_opt LPCTSTR pName) :
- CBaseList(pName) {
- };
- __out_opt POSITION GetHeadPosition() const { return (POSITION)m_pFirst; }
- __out_opt POSITION GetTailPosition() const { return (POSITION)m_pLast; }
- int GetCount() const { return m_Count; }
- __out OBJECT *GetNext(__inout POSITION& rp) const { return (OBJECT *) GetNextI(rp); }
- __out_opt OBJECT *Get(__in_opt POSITION p) const { return (OBJECT *) GetI(p); }
- __out OBJECT *GetValid(__in POSITION p) const { return (OBJECT *) GetValidI(p); }
- __out_opt OBJECT *GetHead() const { return Get(GetHeadPosition()); }
- __out_opt OBJECT *RemoveHead() { return (OBJECT *) RemoveHeadI(); }
- __out_opt OBJECT *RemoveTail() { return (OBJECT *) RemoveTailI(); }
- __out_opt OBJECT *Remove(__in_opt POSITION p) { return (OBJECT *) RemoveI(p); }
- __out_opt POSITION AddBefore(__in_opt POSITION p, __in OBJECT * pObj) { return AddBeforeI(p, pObj); }
- __out_opt POSITION AddAfter(__in_opt POSITION p, __in OBJECT * pObj) { return AddAfterI(p, pObj); }
- __out_opt POSITION AddHead(__in OBJECT * pObj) { return AddHeadI(pObj); }
- __out_opt POSITION AddTail(__in OBJECT * pObj) { return AddTailI(pObj); }
- BOOL AddTail(__in CGenericList<OBJECT> *pList)
- { return CBaseList::AddTail((CBaseList *) pList); }
- BOOL AddHead(__in CGenericList<OBJECT> *pList)
- { return CBaseList::AddHead((CBaseList *) pList); }
- BOOL AddAfter(__in_opt POSITION p, __in CGenericList<OBJECT> *pList)
- { return CBaseList::AddAfter(p, (CBaseList *) pList); };
- BOOL AddBefore(__in_opt POSITION p, __in CGenericList<OBJECT> *pList)
- { return CBaseList::AddBefore(p, (CBaseList *) pList); };
- __out_opt POSITION Find( __in OBJECT * pObj) const { return FindI(pObj); }
- }; // end of class declaration
- /* These define the standard list types */
- typedef CGenericList<CBaseObject> CBaseObjectList;
- typedef CGenericList<IUnknown> CBaseInterfaceList;
- #endif /* __WXLIST__ */
|