text: ﻿//------------------------------------------------------------------------------
  // 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__ */
  
  