home *** CD-ROM | disk | FTP | other *** search
/ Windows Game Programming for Dummies (2nd Edition) / WinGamProgFD.iso / pc / DirectX SDK / DXSDK / samples / Multimedia / DirectShow / BaseClasses / wxlist.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-10-08  |  24.0 KB  |  886 lines
  1. //------------------------------------------------------------------------------
  2. // File: WXList.cpp
  3. //
  4. // Desc: DirectShow base classes - implements a non-MFC based generic list
  5. //       template class.
  6. //
  7. // Copyright (c) 1992-2001 Microsoft Corporation.  All rights reserved.
  8. //------------------------------------------------------------------------------
  9.  
  10.  
  11. /* A generic list of pointers to objects.
  12.    Objectives: avoid using MFC libraries in ndm kernel mode and
  13.    provide a really useful list type.
  14.  
  15.    The class is thread safe in that separate threads may add and
  16.    delete items in the list concurrently although the application
  17.    must ensure that constructor and destructor access is suitably
  18.    synchronised.
  19.  
  20.    The list name must not conflict with MFC classes as an
  21.    application may use both
  22.  
  23.    The nodes form a doubly linked, NULL terminated chain with an anchor
  24.    block (the list object per se) holding pointers to the first and last
  25.    nodes and a count of the nodes.
  26.    There is a node cache to reduce the allocation and freeing overhead.
  27.    It optionally (determined at construction time) has an Event which is
  28.    set whenever the list becomes non-empty and reset whenever it becomes
  29.    empty.
  30.    It optionally (determined at construction time) has a Critical Section
  31.    which is entered during the important part of each operation.  (About
  32.    all you can do outside it is some parameter checking).
  33.  
  34.    The node cache is a repository of nodes that are NOT in the list to speed
  35.    up storage allocation.  Each list has its own cache to reduce locking and
  36.    serialising.  The list accesses are serialised anyway for a given list - a
  37.    common cache would mean that we would have to separately serialise access
  38.    of all lists within the cache.  Because the cache only stores nodes that are
  39.    not in the list, releasing the cache does not release any list nodes.  This
  40.    means that list nodes can be copied or rechained from one list to another
  41.    without danger of creating a dangling reference if the original cache goes
  42.    away.
  43.  
  44.    Questionable design decisions:
  45.    1. Retaining the warts for compatibility
  46.    2. Keeping an element count -i.e. counting whenever we do anything
  47.       instead of only when we want the count.
  48.    3. Making the chain pointers NULL terminated.  If the list object
  49.       itself looks just like a node and the list is kept as a ring then
  50.       it reduces the number of special cases.  All inserts look the same.
  51. */
  52.  
  53.  
  54. #include <streams.h>
  55.  
  56. /* set cursor to the position of each element of list in turn  */
  57. #define INTERNALTRAVERSELIST(list, cursor)               \
  58. for ( cursor = (list).GetHeadPositionI()           \
  59.     ; cursor!=NULL                               \
  60.     ; cursor = (list).Next(cursor)                \
  61.     )
  62.  
  63.  
  64. /* set cursor to the position of each element of list in turn
  65.    in reverse order
  66. */
  67. #define INTERNALREVERSETRAVERSELIST(list, cursor)        \
  68. for ( cursor = (list).GetTailPositionI()           \
  69.     ; cursor!=NULL                               \
  70.     ; cursor = (list).Prev(cursor)                \
  71.     )
  72.  
  73. /* Constructor calls a separate initialisation function that
  74.    creates a node cache, optionally creates a lock object
  75.    and optionally creates a signaling object.
  76.  
  77.    By default we create a locking object, a DEFAULTCACHE sized
  78.    cache but no event object so the list cannot be used in calls
  79.    to WaitForSingleObject
  80. */
  81. CBaseList::CBaseList(TCHAR *pName,    // Descriptive list name
  82.                      INT iItems) :    // Node cache size
  83. #ifdef DEBUG
  84.     CBaseObject(pName),
  85. #endif
  86.     m_pFirst(NULL),
  87.     m_pLast(NULL),
  88.     m_Count(0),
  89.     m_Cache(iItems)
  90. {
  91. } // constructor
  92.  
  93. CBaseList::CBaseList(TCHAR *pName) :  // Descriptive list name
  94. #ifdef DEBUG
  95.     CBaseObject(pName),
  96. #endif
  97.     m_pFirst(NULL),
  98.     m_pLast(NULL),
  99.     m_Count(0),
  100.     m_Cache(DEFAULTCACHE)
  101. {
  102. } // constructor
  103.  
  104. #ifdef UNICODE
  105. CBaseList::CBaseList(CHAR *pName,    // Descriptive list name
  106.                      INT iItems) :    // Node cache size
  107. #ifdef DEBUG
  108.     CBaseObject(pName),
  109. #endif
  110.     m_pFirst(NULL),
  111.     m_pLast(NULL),
  112.     m_Count(0),
  113.     m_Cache(iItems)
  114. {
  115. } // constructor
  116.  
  117. CBaseList::CBaseList(CHAR *pName) :  // Descriptive list name
  118. #ifdef DEBUG
  119.     CBaseObject(pName),
  120. #endif
  121.     m_pFirst(NULL),
  122.     m_pLast(NULL),
  123.     m_Count(0),
  124.     m_Cache(DEFAULTCACHE)
  125. {
  126. } // constructor
  127.  
  128. #endif
  129.  
  130. /* The destructor enumerates all the node objects in the list and
  131.    in the cache deleting each in turn. We do not do any processing
  132.    on the objects that the list holds (i.e. points to) so if they
  133.    represent interfaces for example the creator of the list should
  134.    ensure that each of them is released before deleting us
  135. */
  136. CBaseList::~CBaseList()
  137. {
  138.     /* Delete all our list nodes */
  139.  
  140.     RemoveAll();
  141.  
  142. } // destructor
  143.  
  144. /* Remove all the nodes from the list but don't do anything
  145.    with the objects that each node looks after (this is the
  146.    responsibility of the creator).
  147.    Aa a last act we reset the signalling event
  148.    (if available) to indicate to clients that the list
  149.    does not have any entries in it.
  150. */
  151. void CBaseList::RemoveAll()
  152. {
  153.     /* Free up all the CNode objects NOTE we don't bother putting the
  154.        deleted nodes into the cache as this method is only really called
  155.        in serious times of change such as when we are being deleted at
  156.        which point the cache will be deleted anway */
  157.  
  158.     CNode *pn = m_pFirst;
  159.     while (pn) {
  160.         CNode *op = pn;
  161.         pn = pn->Next();
  162.         delete op;
  163.     }
  164.  
  165.     /* Reset the object count and the list pointers */
  166.  
  167.     m_Count = 0;
  168.     m_pFirst = m_pLast = NULL;
  169.  
  170. } // RemoveAll
  171.  
  172.  
  173.  
  174. /* Return a position enumerator for the entire list.
  175.    A position enumerator is a pointer to a node object cast to a
  176.    transparent type so all we do is return the head/tail node
  177.    pointer in the list.
  178.    WARNING because the position is a pointer to a node there is
  179.    an implicit assumption for users a the list class that after
  180.    deleting an object from the list that any other position
  181.    enumerators that you have may be invalid (since the node
  182.    may be gone).
  183. */
  184. POSITION CBaseList::GetHeadPositionI() const
  185. {
  186.     return (POSITION) m_pFirst;
  187. } // GetHeadPosition
  188.  
  189.  
  190.  
  191. POSITION CBaseList::GetTailPositionI() const
  192. {
  193.     return (POSITION) m_pLast;
  194. } // GetTailPosition
  195.  
  196.  
  197.  
  198. /* Get the number of objects in the list,
  199.    Get the lock before accessing the count.
  200.    Locking may not be entirely necessary but it has the side effect
  201.    of making sure that all operations are complete before we get it.
  202.    So for example if a list is being added to this list then that
  203.    will have completed in full before we continue rather than seeing
  204.    an intermediate albeit valid state
  205. */
  206. int CBaseList::GetCountI() const
  207. {
  208.     return m_Count;
  209. } // GetCount
  210.  
  211.  
  212.  
  213. /* Return the object at rp, update rp to the next object from
  214.    the list or NULL if you have moved over the last object.
  215.    You may still call this function once we return NULL but
  216.    we will continue to return a NULL position value
  217. */
  218. void *CBaseList::GetNextI(POSITION& rp) const
  219. {
  220.     /* have we reached the end of the list */
  221.  
  222.     if (rp == NULL) {
  223.         return NULL;
  224.     }
  225.  
  226.     /* Lock the object before continuing */
  227.  
  228.     void *pObject;
  229.  
  230.     /* Copy the original position then step on */
  231.  
  232.     CNode *pn = (CNode *) rp;
  233.     ASSERT(pn != NULL);
  234.     rp = (POSITION) pn->Next();
  235.  
  236.     /* Get the object at the original position from the list */
  237.  
  238.     pObject = pn->GetData();
  239.     // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
  240.     return pObject;
  241. } //GetNext
  242.  
  243.  
  244.  
  245. /* Return the object at p.
  246.    Asking for the object at NULL ASSERTs then returns NULL
  247.    The object is NOT locked.  The list is not being changed
  248.    in any way.  If another thread is busy deleting the object
  249.    then locking would only result in a change from one bad
  250.    behaviour to another.
  251. */
  252. void *CBaseList::GetI(POSITION p) const
  253. {
  254.     if (p == NULL) {
  255.         return NULL;
  256.     }
  257.  
  258.     CNode * pn = (CNode *) p;
  259.     void *pObject = pn->GetData();
  260.     // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
  261.     return pObject;
  262. } //Get
  263.  
  264.  
  265.  
  266. /* Return the first position in the list which holds the given pointer.
  267.    Return NULL if it's not found.
  268. */
  269. POSITION CBaseList::FindI( void * pObj) const
  270. {
  271.     POSITION pn;
  272.     INTERNALTRAVERSELIST(*this, pn){
  273.         if (GetI(pn)==pObj) {
  274.             return pn;
  275.         }
  276.     }
  277.     return NULL;
  278. } // Find
  279.  
  280.  
  281.  
  282. /* Remove the first node in the list (deletes the pointer to its object
  283.    from the list, does not free the object itself).
  284.    Return the pointer to its object or NULL if empty
  285. */
  286. void *CBaseList::RemoveHeadI()
  287. {
  288.     /* All we do is get the head position and ask for that to be deleted.
  289.        We could special case this since some of the code path checking
  290.        in Remove() is redundant as we know there is no previous
  291.        node for example but it seems to gain little over the
  292.        added complexity
  293.     */
  294.  
  295.     return RemoveI((POSITION)m_pFirst);
  296. } // RemoveHead
  297.  
  298.  
  299.  
  300. /* Remove the last node in the list (deletes the pointer to its object
  301.    from the list, does not free the object itself).
  302.    Return the pointer to its object or NULL if empty
  303. */
  304. void *CBaseList::RemoveTailI()
  305. {
  306.     /* All we do is get the tail position and ask for that to be deleted.
  307.        We could special case this since some of the code path checking
  308.        in Remove() is redundant as we know there is no previous
  309.        node for example but it seems to gain little over the
  310.        added complexity
  311.     */
  312.  
  313.     return RemoveI((POSITION)m_pLast);
  314. } // RemoveTail
  315.  
  316.  
  317.  
  318. /* Remove the pointer to the object in this position from the list.
  319.    Deal with all the chain pointers
  320.    Return a pointer to the object removed from the list.
  321.    The node object that is freed as a result
  322.    of this operation is added to the node cache where
  323.    it can be used again.
  324.    Remove(NULL) is a harmless no-op - but probably is a wart.
  325. */
  326. void *CBaseList::RemoveI(POSITION pos)
  327. {
  328.     /* Lock the critical section before continuing */
  329.  
  330.     // ASSERT (pos!=NULL);     // Removing NULL is to be harmless!
  331.     if (pos==NULL) return NULL;
  332.  
  333.  
  334.     CNode *pCurrent = (CNode *) pos;
  335.     ASSERT(pCurrent != NULL);
  336.  
  337.     /* Update the previous node */
  338.  
  339.     CNode *pNode = pCurrent->Prev();
  340.     if (pNode == NULL) {
  341.         m_pFirst = pCurrent->Next();
  342.     } else {
  343.         pNode->SetNext(pCurrent->Next());
  344.     }
  345.  
  346.     /* Update the following node */
  347.  
  348.     pNode = pCurrent->Next();
  349.     if (pNode == NULL) {
  350.         m_pLast = pCurrent->Prev();
  351.     } else {
  352.         pNode->SetPrev(pCurrent->Prev());
  353.     }
  354.  
  355.     /* Get the object this node was looking after */
  356.  
  357.     void *pObject = pCurrent->GetData();
  358.  
  359.     // ASSERT(pObject != NULL);    // NULL pointers in the list are allowed.
  360.  
  361.     /* Try and add the node object to the cache -
  362.        a NULL return code from the cache means we ran out of room.
  363.        The cache size is fixed by a constructor argument when the
  364.        list is created and defaults to DEFAULTCACHE.
  365.        This means that the cache will have room for this many
  366.        node objects. So if you have a list of media samples
  367.        and you know there will never be more than five active at
  368.        any given time of them for example then override the default
  369.        constructor
  370.     */
  371.  
  372.     m_Cache.AddToCache(pCurrent);
  373.  
  374.     /* If the list is empty then reset the list event */
  375.  
  376.     --m_Count;
  377.     ASSERT(m_Count >= 0);
  378.     return pObject;
  379. } // Remove
  380.  
  381.  
  382.  
  383. /* Add this object to the tail end of our list
  384.    Return the new tail position.
  385. */
  386.  
  387. POSITION CBaseList::AddTailI(void *pObject)
  388. {
  389.     /* Lock the critical section before continuing */
  390.  
  391.     CNode *pNode;
  392.     // ASSERT(pObject);   // NULL pointers in the list are allowed.
  393.  
  394.     /* If there is a node objects in the cache then use
  395.        that otherwise we will have to create a new one */
  396.  
  397.     pNode = (CNode *) m_Cache.RemoveFromCache();
  398.     if (pNode == NULL) {
  399.         pNode = new CNode;
  400.     }
  401.  
  402.     /* Check we have a valid object */
  403.  
  404.     if (pNode == NULL) {
  405.         return NULL;
  406.     }
  407.  
  408.     /* Initialise all the CNode object
  409.        just in case it came from the cache
  410.     */
  411.  
  412.     pNode->SetData(pObject);
  413.     pNode->SetNext(NULL);
  414.     pNode->SetPrev(m_pLast);
  415.  
  416.     if (m_pLast == NULL) {
  417.         m_pFirst = pNode;
  418.     } else {
  419.         m_pLast->SetNext(pNode);
  420.     }
  421.  
  422.     /* Set the new last node pointer and also increment the number
  423.        of list entries, the critical section is unlocked when we
  424.        exit the function
  425.     */
  426.  
  427.     m_pLast = pNode;
  428.     ++m_Count;
  429.  
  430.     return (POSITION) pNode;
  431. } // AddTail(object)
  432.  
  433.  
  434.  
  435. /* Add this object to the head end of our list
  436.    Return the new head position.
  437. */
  438. POSITION CBaseList::AddHeadI(void *pObject)
  439. {
  440.     CNode *pNode;
  441.     // ASSERT(pObject);  // NULL pointers in the list are allowed.
  442.  
  443.     /* If there is a node objects in the cache then use
  444.        that otherwise we will have to create a new one */
  445.  
  446.     pNode = (CNode *) m_Cache.RemoveFromCache();
  447.     if (pNode == NULL) {
  448.         pNode = new CNode;
  449.     }
  450.  
  451.     /* Check we have a valid object */
  452.  
  453.     if (pNode == NULL) {
  454.         return NULL;
  455.     }
  456.  
  457.     /* Initialise all the CNode object
  458.        just in case it came from the cache
  459.     */
  460.  
  461.     pNode->SetData(pObject);
  462.  
  463.     /* chain it in (set four pointers) */
  464.     pNode->SetPrev(NULL);
  465.     pNode->SetNext(m_pFirst);
  466.  
  467.     if (m_pFirst == NULL) {
  468.         m_pLast = pNode;
  469.     } else {
  470.         m_pFirst->SetPrev(pNode);
  471.     }
  472.     m_pFirst = pNode;
  473.  
  474.     ++m_Count;
  475.  
  476.     return (POSITION) pNode;
  477. } // AddHead(object)
  478.  
  479.  
  480.  
  481. /* Add all the elements in *pList to the tail of this list.
  482.    Return TRUE if it all worked, FALSE if it didn't.
  483.    If it fails some elements may have been added.
  484. */
  485. BOOL CBaseList::AddTail(CBaseList *pList)
  486. {
  487.     /* lock the object before starting then enumerate
  488.        each entry in the source list and add them one by one to
  489.        our list (while still holding the object lock)
  490.        Lock the other list too.
  491.     */
  492.     POSITION pos = pList->GetHeadPositionI();
  493.  
  494.     while (pos) {
  495.        if (NULL == AddTailI(pList->GetNextI(pos))) {
  496.            return FALSE;
  497.        }
  498.     }
  499.     return TRUE;
  500. } // AddTail(list)
  501.  
  502.  
  503.  
  504. /* Add all the elements in *pList to the head of this list.
  505.    Return TRUE if it all worked, FALSE if it didn't.
  506.    If it fails some elements may have been added.
  507. */
  508. BOOL CBaseList::AddHead(CBaseList *pList)
  509. {
  510.     /* lock the object before starting then enumerate
  511.        each entry in the source list and add them one by one to
  512.        our list (while still holding the object lock)
  513.        Lock the other list too.
  514.  
  515.        To avoid reversing the list, traverse it backwards.
  516.     */
  517.  
  518.     POSITION pos;
  519.  
  520.     INTERNALREVERSETRAVERSELIST(*pList, pos) {
  521.         if (NULL== AddHeadI(pList->GetI(pos))){
  522.             return FALSE;
  523.         }
  524.     }
  525.     return TRUE;
  526. } // AddHead(list)
  527.  
  528.  
  529.  
  530. /* Add the object after position p
  531.    p is still valid after the operation.
  532.    AddAfter(NULL,x) adds x to the start - same as AddHead
  533.    Return the position of the new object, NULL if it failed
  534. */
  535. POSITION  CBaseList::AddAfterI(POSITION pos, void * pObj)
  536. {
  537.     if (pos==NULL)
  538.         return AddHeadI(pObj);
  539.  
  540.     /* As someone else might be furkling with the list -
  541.        Lock the critical section before continuing
  542.     */
  543.     CNode *pAfter = (CNode *) pos;
  544.     ASSERT(pAfter != NULL);
  545.     if (pAfter==m_pLast)
  546.         return AddTailI(pObj);
  547.  
  548.     /* set pnode to point to a new node, preferably from the cache */
  549.  
  550.     CNode *pNode = (CNode *) m_Cache.RemoveFromCache();
  551.     if (pNode == NULL) {
  552.         pNode = new CNode;
  553.     }
  554.  
  555.     /* Check we have a valid object */
  556.  
  557.     if (pNode == NULL) {
  558.         return NULL;
  559.     }
  560.  
  561.     /* Initialise all the CNode object
  562.        just in case it came from the cache
  563.     */
  564.  
  565.     pNode->SetData(pObj);
  566.  
  567.     /* It is to be added to the middle of the list - there is a before
  568.        and after node.  Chain it after pAfter, before pBefore.
  569.     */
  570.     CNode * pBefore = pAfter->Next();
  571.     ASSERT(pBefore != NULL);
  572.  
  573.     /* chain it in (set four pointers) */
  574.     pNode->SetPrev(pAfter);
  575.     pNode->SetNext(pBefore);
  576.     pBefore->SetPrev(pNode);
  577.     pAfter->SetNext(pNode);
  578.  
  579.     ++m_Count;
  580.  
  581.     return (POSITION) pNode;
  582.  
  583. } // AddAfter(object)
  584.  
  585.  
  586.  
  587. BOOL CBaseList::AddAfter(POSITION p, CBaseList *pList)
  588. {
  589.     POSITION pos;
  590.     INTERNALTRAVERSELIST(*pList, pos) {
  591.         /* p follows along the elements being added */
  592.         p = AddAfterI(p, pList->GetI(pos));
  593.         if (p==NULL) return FALSE;
  594.     }
  595.     return TRUE;
  596. } // AddAfter(list)
  597.  
  598.  
  599.  
  600. /* Mirror images:
  601.    Add the element or list after position p.
  602.    p is still valid after the operation.
  603.    AddBefore(NULL,x) adds x to the end - same as AddTail
  604. */
  605. POSITION CBaseList::AddBeforeI(POSITION pos, void * pObj)
  606. {
  607.     if (pos==NULL)
  608.         return AddTailI(pObj);
  609.  
  610.     /* set pnode to point to a new node, preferably from the cache */
  611.  
  612.     CNode *pBefore = (CNode *) pos;
  613.     ASSERT(pBefore != NULL);
  614.     if (pBefore==m_pFirst)
  615.         return AddHeadI(pObj);
  616.  
  617.     CNode * pNode = (CNode *) m_Cache.RemoveFromCache();
  618.     if (pNode == NULL) {
  619.         pNode = new CNode;
  620.     }
  621.  
  622.     /* Check we have a valid object */
  623.  
  624.     if (pNode == NULL) {
  625.         return NULL;
  626.     }
  627.  
  628.     /* Initialise all the CNode object
  629.        just in case it came from the cache
  630.     */
  631.  
  632.     pNode->SetData(pObj);
  633.  
  634.     /* It is to be added to the middle of the list - there is a before
  635.        and after node.  Chain it after pAfter, before pBefore.
  636.     */
  637.  
  638.     CNode * pAfter = pBefore->Prev();
  639.     ASSERT(pAfter != NULL);
  640.  
  641.     /* chain it in (set four pointers) */
  642.     pNode->SetPrev(pAfter);
  643.     pNode->SetNext(pBefore);
  644.     pBefore->SetPrev(pNode);
  645.     pAfter->SetNext(pNode);
  646.  
  647.     ++m_Count;
  648.  
  649.     return (POSITION) pNode;
  650.  
  651. } // Addbefore(object)
  652.  
  653.  
  654.  
  655. BOOL CBaseList::AddBefore(POSITION p, CBaseList *pList)
  656. {
  657.     POSITION pos;
  658.     INTERNALREVERSETRAVERSELIST(*pList, pos) {
  659.         /* p follows along the elements being added */
  660.         p = AddBeforeI(p, pList->GetI(pos));
  661.         if (p==NULL) return FALSE;
  662.     }
  663.     return TRUE;
  664. } // AddBefore(list)
  665.  
  666.  
  667.  
  668. /* Split *this after position p in *this
  669.    Retain as *this the tail portion of the original *this
  670.    Add the head portion to the tail end of *pList
  671.    Return TRUE if it all worked, FALSE if it didn't.
  672.  
  673.    e.g.
  674.       foo->MoveToTail(foo->GetHeadPosition(), bar);
  675.           moves one element from the head of foo to the tail of bar
  676.       foo->MoveToTail(NULL, bar);
  677.           is a no-op
  678.       foo->MoveToTail(foo->GetTailPosition, bar);
  679.           concatenates foo onto the end of bar and empties foo.
  680.  
  681.    A better, except excessively long name might be
  682.        MoveElementsFromHeadThroughPositionToOtherTail
  683. */
  684. BOOL CBaseList::MoveToTail
  685.         (POSITION pos, CBaseList *pList)
  686. {
  687.     /* Algorithm:
  688.        Note that the elements (including their order) in the concatenation
  689.        of *pList to the head of *this is invariant.
  690.        1. Count elements to be moved
  691.        2. Join *pList onto the head of this to make one long chain
  692.        3. Set first/Last pointers in *this and *pList
  693.        4. Break the chain at the new place
  694.        5. Adjust counts
  695.        6. Set/Reset any events
  696.     */
  697.  
  698.     if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.
  699.  
  700.  
  701.     /* Make cMove the number of nodes to move */
  702.     CNode * p = (CNode *)pos;
  703.     int cMove = 0;            // number of nodes to move
  704.     while(p!=NULL) {
  705.        p = p->Prev();
  706.        ++cMove;
  707.     }
  708.  
  709.  
  710.     /* Join the two chains together */
  711.     if (pList->m_pLast!=NULL)
  712.         pList->m_pLast->SetNext(m_pFirst);
  713.     if (m_pFirst!=NULL)
  714.         m_pFirst->SetPrev(pList->m_pLast);
  715.  
  716.  
  717.     /* set first and last pointers */
  718.     p = (CNode *)pos;
  719.  
  720.     if (pList->m_pFirst==NULL)
  721.         pList->m_pFirst = m_pFirst;
  722.     m_pFirst = p->Next();
  723.     if (m_pFirst==NULL)
  724.         m_pLast = NULL;
  725.     pList->m_pLast = p;
  726.  
  727.  
  728.     /* Break the chain after p to create the new pieces */
  729.     if (m_pFirst!=NULL)
  730.         m_pFirst->SetPrev(NULL);
  731.     p->SetNext(NULL);
  732.  
  733.  
  734.     /* Adjust the counts */
  735.     m_Count -= cMove;
  736.     pList->m_Count += cMove;
  737.  
  738.     return TRUE;
  739.  
  740. } // MoveToTail
  741.  
  742.  
  743.  
  744. /* Mirror image of MoveToTail:
  745.    Split *this before position p in *this.
  746.    Retain in *this the head portion of the original *this
  747.    Add the tail portion to the start (i.e. head) of *pList
  748.    Return TRUE if it all worked, FALSE if it didn't.
  749.  
  750.    e.g.
  751.       foo->MoveToHead(foo->GetTailPosition(), bar);
  752.           moves one element from the tail of foo to the head of bar
  753.       foo->MoveToHead(NULL, bar);
  754.           is a no-op
  755.       foo->MoveToHead(foo->GetHeadPosition, bar);
  756.           concatenates foo onto the start of bar and empties foo.
  757. */
  758. BOOL CBaseList::MoveToHead
  759.         (POSITION pos, CBaseList *pList)
  760. {
  761.  
  762.     /* See the comments on the algorithm in MoveToTail */
  763.  
  764.     if (pos==NULL) return TRUE;  // no-op.  Eliminates special cases later.
  765.  
  766.     /* Make cMove the number of nodes to move */
  767.     CNode * p = (CNode *)pos;
  768.     int cMove = 0;            // number of nodes to move
  769.     while(p!=NULL) {
  770.        p = p->Next();
  771.        ++cMove;
  772.     }
  773.  
  774.  
  775.     /* Join the two chains together */
  776.     if (pList->m_pFirst!=NULL)
  777.         pList->m_pFirst->SetPrev(m_pLast);
  778.     if (m_pLast!=NULL)
  779.         m_pLast->SetNext(pList->m_pFirst);
  780.  
  781.  
  782.     /* set first and last pointers */
  783.     p = (CNode *)pos;
  784.  
  785.  
  786.     if (pList->m_pLast==NULL)
  787.         pList->m_pLast = m_pLast;
  788.  
  789.     m_pLast = p->Prev();
  790.     if (m_pLast==NULL)
  791.         m_pFirst = NULL;
  792.     pList->m_pFirst = p;
  793.  
  794.  
  795.     /* Break the chain after p to create the new pieces */
  796.     if (m_pLast!=NULL)
  797.         m_pLast->SetNext(NULL);
  798.     p->SetPrev(NULL);
  799.  
  800.  
  801.     /* Adjust the counts */
  802.     m_Count -= cMove;
  803.     pList->m_Count += cMove;
  804.  
  805.     return TRUE;
  806.  
  807. } // MoveToHead
  808.  
  809.  
  810.  
  811. /* Reverse the order of the [pointers to] objects in *this
  812. */
  813. void CBaseList::Reverse()
  814. {
  815.     /* algorithm:
  816.        The obvious booby trap is that you flip pointers around and lose
  817.        addressability to the node that you are going to process next.
  818.        The easy way to avoid this is do do one chain at a time.
  819.  
  820.        Run along the forward chain,
  821.        For each node, set the reverse pointer to the one ahead of us.
  822.        The reverse chain is now a copy of the old forward chain, including
  823.        the NULL termination.
  824.  
  825.        Run along the reverse chain (i.e. old forward chain again)
  826.        For each node set the forward pointer of the node ahead to point back
  827.        to the one we're standing on.
  828.        The first node needs special treatment,
  829.        it's new forward pointer is NULL.
  830.        Finally set the First/Last pointers
  831.  
  832.     */
  833.     CNode * p;
  834.  
  835.     // Yes we COULD use a traverse, but it would look funny!
  836.     p = m_pFirst;
  837.     while (p!=NULL) {
  838.         CNode * q;
  839.         q = p->Next();
  840.         p->SetNext(p->Prev());
  841.         p->SetPrev(q);
  842.         p = q;
  843.     }
  844.  
  845.     p = m_pFirst;
  846.     m_pFirst = m_pLast;
  847.     m_pLast = p;
  848.  
  849.  
  850. #if 0     // old version
  851.  
  852.     if (m_pFirst==NULL) return;          // empty list
  853.     if (m_pFirst->Next()==NULL) return;  // single node list
  854.  
  855.  
  856.     /* run along forward chain */
  857.     for ( p = m_pFirst
  858.         ; p!=NULL
  859.         ; p = p->Next()
  860.         ){
  861.         p->SetPrev(p->Next());
  862.     }
  863.  
  864.  
  865.     /* special case first element */
  866.     m_pFirst->SetNext(NULL);     // fix the old first element
  867.  
  868.  
  869.     /* run along new reverse chain i.e. old forward chain again */
  870.     for ( p = m_pFirst           // start at the old first element
  871.         ; p->Prev()!=NULL        // while there's a node still to be set
  872.         ; p = p->Prev()          // work in the same direction as before
  873.         ){
  874.         p->Prev()->SetNext(p);
  875.     }
  876.  
  877.  
  878.     /* fix forward and reverse pointers
  879.        - the triple XOR swap would work but all the casts look hideous */
  880.     p = m_pFirst;
  881.     m_pFirst = m_pLast;
  882.     m_pLast = p;
  883. #endif
  884.  
  885. } // Reverse
  886.