//------------------------------------------------------------------------------
// File: WXList.cpp
//
// Desc: DirectShow base classes - implements a non-MFC based generic list
//       template class.
//
// Copyright (c) 1992-2002 Microsoft Corporation.  All rights reserved.
//------------------------------------------------------------------------------


/* A generic list of pointers to objects.
   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.

   The list name must not conflict with MFC classes as an
   application may use both

   The nodes form a doubly linked, NULL terminated chain with an anchor
   block (the list object per se) holding pointers to the first and last
   nodes and a count of the nodes.
   There is a node cache to reduce the allocation and freeing overhead.
   It optionally (determined at construction time) has an Event which is
   set whenever the list becomes non-empty and reset whenever it becomes
   empty.
   It optionally (determined at construction time) has a Critical Section
   which is entered during the important part of each operation.  (About
   all you can do outside it is some parameter checking).

   The node cache is a repository of nodes that are NOT in the list to speed
   up storage allocation.  Each list has its own cache to reduce locking and
   serialising.  The list accesses are serialised anyway for a given list - a
   common cache would mean that we would have to separately serialise access
   of all lists within the cache.  Because the cache only stores nodes that are
   not in the list, releasing the cache does not release any list nodes.  This
   means that list nodes can be copied or rechained from one list to another
   without danger of creating a dangling reference if the original cache goes
   away.

   Questionable design decisions:
   1. Retaining the warts for compatibility
   2. Keeping an element count -i.e. counting whenever we do anything
      instead of only when we want the count.
   3. Making the chain pointers NULL terminated.  If the list object
      itself looks just like a node and the list is kept as a ring then
      it reduces the number of special cases.  All inserts look the same.
*/


#include <streams.h>

/* set cursor to the position of each element of list in turn  */
#define INTERNALTRAVERSELIST(list, cursor)               \
for ( cursor = (list).GetHeadPositionI()           \
    ; cursor!=NULL                               \
    ; cursor = (list).Next(cursor)                \
    )


/* set cursor to the position of each element of list in turn
   in reverse order
*/
#define INTERNALREVERSETRAVERSELIST(list, cursor)        \
for ( cursor = (list).GetTailPositionI()           \
    ; cursor!=NULL                               \
    ; cursor = (list).Prev(cursor)                \
    )

/* Constructor calls a separate initialisation function that
   creates a node cache, optionally creates a lock object
   and optionally creates a signaling object.

   By default we create a locking object, a DEFAULTCACHE sized
   cache but no event object so the list cannot be used in calls
   to WaitForSingleObject
*/
CBaseList::CBaseList(TCHAR *pName,    // Descriptive list name
                     INT iItems) :    // Node cache size
#ifdef DEBUG
    CBaseObject(pName),
#endif
    m_pFirst(NULL),
    m_pLast(NULL),
    m_Count(0),
    m_Cache(iItems)
{
} // constructor

CBaseList::CBaseList(TCHAR *pName) :  // Descriptive list name
#ifdef DEBUG
    CBaseObject(pName),
#endif
    m_pFirst(NULL),
    m_pLast(NULL),
    m_Count(0),
    m_Cache(DEFAULTCACHE)
{
} // constructor

#ifdef UNICODE
CBaseList::CBaseList(CHAR *pName,    // Descriptive list name
                     INT iItems) :    // Node cache size
#ifdef DEBUG
    CBaseObject(pName),
#endif
    m_pFirst(NULL),
    m_pLast(NULL),
    m_Count(0),
    m_Cache(iItems)
{
} // constructor

CBaseList::CBaseList(CHAR *pName) :  // Descriptive list name
#ifdef DEBUG
    CBaseObject(pName),
#endif
    m_pFirst(NULL),
    m_pLast(NULL),
    m_Count(0),
    m_Cache(DEFAULTCACHE)
{
} // constructor

#endif

/* The destructor enumerates all the node objects in the list and
   in the cache deleting each in turn. We do not do any processing
   on the objects that the list holds (i.e. points to) so if they
   represent interfaces for example the creator of the list should
   ensure that each of them is released before deleting us
*/
CBaseList::~CBaseList()
{
    /* Delete all our list nodes */

    RemoveAll();

} // destructor

/* Remove all the nodes from the list but don't do anything
   with the objects that each node looks after (this is the
   responsibility of the creator).
   Aa a last act we reset the signalling event
   (if available) to indicate to clients that the list
   does not have any entries in it.
*/
void CBaseList::RemoveAll()
{
    /* Free up all the CNode objects NOTE we don't bother putting the
       deleted nodes into the cache as this method is only really called
       in serious times of change such as when we are being deleted at
       which point the cache will be deleted anway */

    CNode *pn = m_pFirst;
    while (pn) {
        CNode *op = pn;
        pn = pn->Next();
        delete op;
    }

    /* Reset the object count and the list pointers */

    m_Count = 0;
    m_pFirst = m_pLast = NULL;

} // RemoveAll



/* Return a position enumerator for the entire list.
   A position enumerator is a pointer to a node object cast to a
   transparent type so all we do is return the head/tail node
   pointer in the list.
   WARNING because the position is a pointer to a node there is
   an implicit assumption for users a the list class that after
   deleting an object from the list that any other position
   enumerators that you have may be invalid (since the node
   may be gone).
*/
POSITION CBaseList::GetHeadPositionI() const
{
    return (POSITION) m_pFirst;
} // GetHeadPosition



POSITION CBaseList::GetTailPositionI() const
{
    return (POSITION) m_pLast;
} // GetTailPosition



/* Get the number of objects in the list,
   Get the lock before accessing the count.
   Locking may not be entirely necessary but it has the side effect
   of making sure that all operations are complete before we get it.
   So for example if a list is being added to this list then that
   will have completed in full before we continue rather than seeing
   an intermediate albeit valid state
*/
int CBaseList::GetCountI() const
{
    return m_Count;
} // GetCount



/* Return the object at rp, update rp to the next object from
   the list or NULL if you have moved over the last object.
   You may still call this function once we return NULL but
   we will continue to return a NULL position value
*/
void *CBaseList::GetNextI(POSITION& rp) const
{
    /* have we reached the end of the list */

    if (rp == NULL) {
        return NULL;
    }

    /* Lock the object before continuing */

    void *pObject;

    /* Copy the original position then step on */

    CNode *pn = (CNode *) rp;
    ASSERT(pn != NULL);
    rp = (POSITION) pn->Next();

    /* Get the object at the original position from the list */

    pObject = pn->GetData();
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
    return pObject;
} //GetNext



/* Return the object at p.
   Asking for the object at NULL ASSERTs then returns NULL
   The object is NOT locked.  The list is not being changed
   in any way.  If another thread is busy deleting the object
   then locking would only result in a change from one bad
   behaviour to another.
*/
void *CBaseList::GetI(POSITION p) const
{
    if (p == NULL) {
        return NULL;
    }

    CNode * pn = (CNode *) p;
    void *pObject = pn->GetData();
    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
    return pObject;
} //Get



/* Return the first position in the list which holds the given pointer.
   Return NULL if it's not found.
*/
POSITION CBaseList::FindI( void * pObj) const
{
    POSITION pn;
    INTERNALTRAVERSELIST(*this, pn){
        if (GetI(pn)==pObj) {
            return pn;
        }
    }
    return NULL;
} // Find



/* Remove the first node in the list (deletes the pointer to its object
   from the list, does not free the object itself).
   Return the pointer to its object or NULL if empty
*/
void *CBaseList::RemoveHeadI()
{
    /* All we do is get the head position and ask for that to be deleted.
       We could special case this since some of the code path checking
       in Remove() is redundant as we know there is no previous
       node for example but it seems to gain little over the
       added complexity
    */

    return RemoveI((POSITION)m_pFirst);
} // RemoveHead



/* Remove the last node in the list (deletes the pointer to its object
   from the list, does not free the object itself).
   Return the pointer to its object or NULL if empty
*/
void *CBaseList::RemoveTailI()
{
    /* All we do is get the tail position and ask for that to be deleted.
       We could special case this since some of the code path checking
       in Remove() is redundant as we know there is no previous
       node for example but it seems to gain little over the
       added complexity
    */

    return RemoveI((POSITION)m_pLast);
} // RemoveTail



/* Remove the pointer to the object in this position from the list.
   Deal with all the chain pointers
   Return a pointer to the object removed from the list.
   The node object that is freed as a result
   of this operation is added to the node cache where
   it can be used again.
   Remove(NULL) is a harmless no-op - but probably is a wart.
*/
void *CBaseList::RemoveI(POSITION pos)
{
    /* Lock the critical section before continuing */

    // ASSERT (pos!=NULL);     // Removing NULL is to be harmless!
    if (pos==NULL) return NULL;


    CNode *pCurrent = (CNode *) pos;
    ASSERT(pCurrent != NULL);

    /* Update the previous node */

    CNode *pNode = pCurrent->Prev();
    if (pNode == NULL) {
        m_pFirst = pCurrent->Next();
    } else {
        pNode->SetNext(pCurrent->Next());
    }

    /* Update the following node */

    pNode = pCurrent->Next();
    if (pNode == NULL) {
        m_pLast = pCurrent->Prev();
    } else {
        pNode->SetPrev(pCurrent->Prev());
    }

    /* Get the object this node was looking after */

    void *pObject = pCurrent->GetData();

    // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.

    /* Try and add the node object to the cache -
       a NULL return code from the cache means we ran out of room.
       The cache size is fixed by a constructor argument when the
       list is created and defaults to DEFAULTCACHE.
       This means that the cache will have room for this many
       node objects. So if you have a list of media samples
       and you know there will never be more than five active at
       any given time of them for example then override the default
       constructor
    */

    m_Cache.AddToCache(pCurrent);

    /* If the list is empty then reset the list event */

    --m_Count;
    ASSERT(m_Count >= 0);
    return pObject;
} // Remove



/* Add this object to the tail end of our list
   Return the new tail position.
*/

POSITION CBaseList::AddTailI(void *pObject)
{
    /* Lock the critical section before continuing */

    CNode *pNode;
    // ASSERT(pObject);   // NULL pointers in the list are allowed.

    /* If there is a node objects in the cache then use
       that otherwise we will have to create a new one */

    pNode = (CNode *) m_Cache.RemoveFromCache();
    if (pNode == NULL) {
        pNode = new CNode;
    }

    /* Check we have a valid object */

    if (pNode == NULL) {
        return NULL;
    }

    /* Initialise all the CNode object
       just in case it came from the cache
    */

    pNode->SetData(pObject);
    pNode->SetNext(NULL);
    pNode->SetPrev(m_pLast);

    if (m_pLast == NULL) {
        m_pFirst = pNode;
    } else {
        m_pLast->SetNext(pNode);
    }

    /* Set the new last node pointer and also increment the number
       of list entries, the critical section is unlocked when we
       exit the function
    */

    m_pLast = pNode;
    ++m_Count;

    return (POSITION) pNode;
} // AddTail(object)



/* Add this object to the head end of our list
   Return the new head position.
*/
POSITION CBaseList::AddHeadI(void *pObject)
{
    CNode *pNode;
    // ASSERT(pObject);  // NULL pointers in the list are allowed.

    /* If there is a node objects in the cache then use