//------------------------------------------------------------------------------
// File: WXList.h
//
// Desc: DirectShow base classes - defines a non-MFC generic template list
//       class.
//
// Copyright (c) 1992-2002 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 */
        CNode *Prev() const { return m_pPrev; };


        /* Return the next node after this one */
        CNode *Next() const { return m_pNext; };


        /* Set the previous node before this one */
        void SetPrev(CNode *p) { m_pPrev = p; };


        /* Set the next node after this one */
        void SetNext(CNode *p) { m_pNext = p; };


        /* Get the pointer to the object for this node */
        void *GetData() const { return m_pObject; };


        /* Set the pointer to the object for this node */
        void SetData(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(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(TCHAR *pName,
              INT iItems);

    CBaseList(TCHAR *pName);
#ifdef UNICODE
    CBaseList(CHAR *pName,
              INT iItems);

    CBaseList(CHAR *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 */
    POSITION GetHeadPositionI() const;


    /* Return a cursor which identifies the last element of *this */
    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.
    */
    void *GetNextI(POSITION& rp) const;


    /* Return a pointer to the object at p
       Asking for the object at NULL will return NULL harmlessly.
    */
    void *GetI(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.
    */
    POSITION Next(POSITION pos) const
    {
        if (pos == NULL) {
            return (POSITION) m_pFirst;
        }
        CNode *pn = (CNode *) pos;
        return (POSITION) pn->Next();
    } //Next

    // See Next
    POSITION Prev(POSITION pos) const
    {
        if (pos == NULL) {
            return (POSITION) m_pLast;