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