home *** CD-ROM | disk | FTP | other *** search
/ The Net: Ultimate Internet Guide / WWLCD1.ISO / mac / SiteBldr / AMOVIE / SDK / _SETUP / COMMON.Z / wxlist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1996-06-15  |  19.0 KB  |  531 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 template list class, December 1994
  13.  
  14. /* A generic list of pointers to objects.
  15.    No storage management or copying is done on the objects pointed to.
  16.    Objectives: avoid using MFC libraries in ndm kernel mode and
  17.    provide a really useful list type.
  18.  
  19.    The class is thread safe in that separate threads may add and
  20.    delete items in the list concurrently although the application
  21.    must ensure that constructor and destructor access is suitably
  22.    synchronised. An application can cause deadlock with operations
  23.    which use two lists by simultaneously calling
  24.    list1->Operation(list2) and list2->Operation(list1).  So don't!
  25.  
  26.    The names must not conflict with MFC classes as an application
  27.    may use both.
  28.    */
  29.  
  30. #ifndef __WXLIST__
  31. #define __WXLIST__
  32.  
  33.    /* A POSITION represents (in some fashion that's opaque) a cursor
  34.       on the list that can be set to identify any element.  NULL is
  35.       a valid value and several operations regard NULL as the position
  36.       "one step off the end of the list".  (In an n element list there
  37.       are n+1 places to insert and NULL is that "n+1-th" value).
  38.       The POSITION of an element in the list is only invalidated if
  39.       that element is deleted.  Move operations may mean that what
  40.       was a valid POSITION in one list is now a valid POSITION in
  41.       a different list.
  42.  
  43.       Some operations which at first sight are illegal are allowed as
  44.       harmless no-ops.  For instance RemoveHead is legal on an empty
  45.       list and it returns NULL.  This allows an atomic way to test if
  46.       there is an element there, and if so, get it.  The two operations
  47.       AddTail and RemoveHead thus implement a MONITOR (See Hoare's paper).
  48.  
  49.       Single element operations return POSITIONs, non-NULL means it worked.
  50.       whole list operations return a BOOL.  TRUE means it all worked.
  51.  
  52.       This definition is the same as the POSITION type for MFCs, so we must
  53.       avoid defining it twice.
  54.    */
  55. #ifndef __AFX_H__
  56. struct __POSITION { int unused; };
  57. typedef __POSITION* POSITION;
  58. #endif
  59.  
  60. const int DEFAULTCACHE = 10;    /* Default node object cache size */
  61.  
  62. /* A class representing one node in a list.
  63.    Each node knows a pointer to it's adjacent nodes and also a pointer
  64.    to the object that it looks after.
  65.    All of these pointers can be retrieved or set through member functions.
  66. */
  67. class CBaseList : public CBaseObject
  68. {
  69.     /* Making these classes inherit from CBaseObject does nothing
  70.        functionally but it allows us to check there are no memory
  71.        leaks in debug builds. In retail builds the CBaseObject class
  72.        simply keeps a count of active objects in the system so that
  73.        it can tell OLE if it is safe to unload the DLL yet
  74.     */
  75.  
  76. public:
  77.  
  78.     class CNode : public CBaseObject {
  79.  
  80.         CNode *m_pPrev;         /* Previous node in the list */
  81.         CNode *m_pNext;         /* Next node in the list */
  82.         void *m_pObject;      /* Pointer to the object */
  83.  
  84.     public:
  85.  
  86.         /* Constructor - initialise the object's pointers */
  87.         CNode() : CBaseObject(NAME("List node")) {
  88.             m_pNext = NULL;
  89.             m_pPrev = NULL;
  90.             m_pObject = NULL;
  91.         };
  92.  
  93.  
  94.         /* Return the previous node before this one */
  95.         CNode *Prev() { return m_pPrev; };
  96.  
  97.  
  98.         /* Return the next node after this one */
  99.         CNode *Next() { return m_pNext; };
  100.  
  101.  
  102.         /* Set the previous node before this one */
  103.         void SetPrev(CNode *p) { m_pPrev = p; };
  104.  
  105.  
  106.         /* Set the next node after this one */
  107.         void SetNext(CNode *p) { m_pNext = p; };
  108.  
  109.  
  110.         /* Get the pointer to the object for this node */
  111.         void *GetData() { return m_pObject; };
  112.  
  113.  
  114.         /* Set the pointer to the object for this node */
  115.         void SetData(void *p) { m_pObject = p; };
  116.     };
  117.  
  118.     class CNodeCache
  119.     {
  120.     public:
  121.         CNodeCache(INT iCacheSize) : m_iCacheSize(iCacheSize),
  122.                                      m_pHead(NULL),
  123.                                      m_iUsed(0)
  124.                                      {};
  125.         ~CNodeCache() {
  126.             CNode *pNode = m_pHead;
  127.             while (pNode) {
  128.                 CNode *pCurrent = pNode;
  129.                 pNode = pNode->Next();
  130.                 delete pCurrent;
  131.             }
  132.         };
  133.         void AddToCache(CNode *pNode)
  134.         {
  135.             if (m_iUsed < m_iCacheSize) {
  136.                 pNode->SetNext(m_pHead);
  137.                 m_pHead = pNode;
  138.                 m_iUsed++;
  139.             } else {
  140.                 delete pNode;
  141.             }
  142.         };
  143.         CNode *RemoveFromCache()
  144.         {
  145.             CNode *pNode = m_pHead;
  146.             if (pNode != NULL) {
  147.                 m_pHead = pNode->Next();
  148.                 m_iUsed--;
  149.                 ASSERT(m_iUsed >= 0);
  150.             } else {
  151.                 ASSERT(m_iUsed == 0);
  152.             }
  153.             return pNode;
  154.         };
  155.     private:
  156.         INT m_iCacheSize;
  157.         INT m_iUsed;
  158.         CNode *m_pHead;
  159.     };
  160.  
  161. private:
  162.  
  163.     CNodeCache m_Cache; /* Cache of unused node pointers */
  164.     CNode* m_pFirst;    /* Pointer to first node in the list */
  165.     CNode* m_pLast;     /* Pointer to the last node in the list */
  166.     LONG m_Count;       /* Number of nodes currently in the list */
  167.  
  168. private:
  169.  
  170.     /* These override the default copy constructor and assignment
  171.        operator for all list classes. They are in the private class
  172.        declaration section so that anybody trying to pass a list
  173.        object by value will generate a compile time error of
  174.        "cannot access the private member function". If these were
  175.        not here then the compiler will create default constructors
  176.        and assignment operators which when executed first take a
  177.        copy of all member variables and then during destruction
  178.        delete them all. This must not be done for any heap
  179.        allocated data.
  180.     */
  181.     CBaseList(const CBaseList &refList);
  182.     CBaseList &operator=(const CBaseList &refList);
  183.  
  184. public:
  185.  
  186.     CBaseList(TCHAR *pName,
  187.               INT iItems = DEFAULTCACHE);
  188.  
  189.     ~CBaseList();
  190.  
  191.     /* Remove all the nodes from *this i.e. make the list empty */
  192.     void RemoveAll();
  193.  
  194.  
  195.     /* Return a cursor which identifies the first element of *this */
  196.     POSITION GetHeadPosition();
  197.  
  198.  
  199.     /* Return a cursor which identifies the last element of *this */
  200.     POSITION GetTailPosition();
  201.  
  202.  
  203.     /* Return the number of objects in *this */
  204.     int GetCount();
  205.  
  206. protected:
  207.     /* Return the pointer to the object at rp,
  208.        Update rp to the next node in *this
  209.        but make it NULL if it was at the end of *this.
  210.        This is a wart retained for backwards compatibility.
  211.        GetPrev is not implemented.
  212.        Use Next, Prev and Get separately.
  213.     */
  214.     void *GetNextI(POSITION& rp);
  215.  
  216.  
  217.     /* Return a pointer to the object at p
  218.        Asking for the object at NULL will return NULL harmlessly.
  219.     */
  220.     void *GetI(POSITION p);
  221.  
  222. public:
  223.     /* return the next / prev position in *this
  224.        return NULL when going past the end/start.
  225.        Next(NULL) is same as GetHeadPosition()
  226.        Prev(NULL) is same as GetTailPosition()
  227.        An n element list therefore behaves like a n+1 element
  228.        cycle with NULL at the start/end.
  229.  
  230.        !!WARNING!! - This handling of NULL is DIFFERENT from GetNext.
  231.  
  232.        Some reasons are:
  233.        1. For a list of n items there are n+1 positions to insert
  234.           These are conveniently encoded as the n POSITIONs and NULL.
  235.        2. If you are keeping a list sorted (fairly common) and you
  236.           search forward for an element to insert before and don't
  237.           find it you finish up with NULL as the element before which
  238.           to insert.  You then want that NULL to be a valid POSITION
  239.           so that you can insert before it and you want that insertion
  240.           point to mean the (n+1)-th one that doesn't have a POSITION.
  241.           (symmetrically if you are working backwards through the list).
  242.        3. It simplifies the algebra which the methods generate.
  243.           e.g. AddBefore(p,x) is identical to AddAfter(Prev(p),x)
  244.           in ALL cases.  All the other arguments probably are reflections
  245.           of the algebraic point.
  246.     */
  247.     POSITION Next(POSITION pos)
  248.     {
  249.         if (pos == NULL) {
  250.             return (POSITION) m_pFirst;
  251.         }
  252.         CNode *pn = (CNode *) pos;
  253.         return (POSITION) pn->Next();
  254.     } //Next
  255.  
  256.     // See Next
  257.     POSITION Prev(POSITION pos)
  258.     {
  259.         if (pos == NULL) {
  260.             return (POSITION) m_pLast;
  261.         }
  262.         CNode *pn = (CNode *) pos;
  263.         return (POSITION) pn->Prev();
  264.     } //Prev
  265.  
  266.  
  267.     /* Return the first position in *this which holds the given
  268.        pointer.  Return NULL if the pointer was not not found.
  269.     */
  270. protected:
  271.     POSITION FindI( void * pObj);
  272.  
  273.     // ??? Should there be (or even should there be only)
  274.     // ??? POSITION FindNextAfter(void * pObj, POSITION p)
  275.     // ??? And of course FindPrevBefore too.
  276.     // ??? List.Find(&Obj) then becomes List.FindNextAfter(&Obj, NULL)
  277.  
  278.  
  279.     /* Remove the first node in *this (deletes the pointer to its
  280.        object from the list, does not free the object itself).
  281.        Return the pointer to its object.
  282.        If *this was already empty it will harmlessly return NULL.
  283.     */
  284.     void *RemoveHeadI();
  285.  
  286.  
  287.     /* Remove the last node in *this (deletes the pointer to its
  288.        object from the list, does not free the object itself).
  289.        Return the pointer to its object.
  290.        If *this was already empty it will harmlessly return NULL.
  291.     */
  292.     void *RemoveTailI();
  293.  
  294.  
  295.     /* Remove the node identified by p from the list (deletes the pointer
  296.        to its object from the list, does not free the object itself).
  297.        Asking to Remove the object at NULL will harmlessly return NULL.
  298.        Return the pointer to the object removed.
  299.     */
  300.     void *RemoveI(POSITION p);
  301.  
  302.     /* Add single object *pObj to become a new last element of the list.
  303.        Return the new tail position, NULL if it fails.
  304.        If you are adding a COM objects, you might want AddRef it first.
  305.        Other existing POSITIONs in *this are still valid
  306.     */
  307.     POSITION AddTailI(void * pObj);
  308. public:
  309.  
  310.  
  311.     /* Add all the elements in *pList to the tail of *this.
  312.        This duplicates all the nodes in *pList (i.e. duplicates
  313.        all its pointers to objects).  It does not duplicate the objects.
  314.        If you are adding a list of pointers to a COM object into the list
  315.        it's a good idea to AddRef them all  it when you AddTail it.
  316.        Return TRUE if it all worked, FALSE if it didn't.
  317.        If it fails some elements may have been added.
  318.        Existing POSITIONs in *this are still valid
  319.  
  320.        If you actually want to MOVE the elements, use MoveToTail instead.
  321.     */
  322.     BOOL AddTail(CBaseList *pList);
  323.  
  324.  
  325.     /* Mirror images of AddHead: */
  326.  
  327.     /* Add single object to become a new first element of the list.
  328.        Return the new head position, NULL if it fails.
  329.        Existing POSITIONs in *this are still valid
  330.     */
  331. protected:
  332.     POSITION AddHeadI(void * pObj);
  333. public:
  334.  
  335.     /* Add all the elements in *pList to the head of *this.
  336.        Same warnings apply as for AddTail.
  337.        Return TRUE if it all worked, FALSE if it didn't.
  338.        If it fails some of the objects may have been added.
  339.  
  340.        If you actually want to MOVE the elements, use MoveToHead instead.
  341.     */
  342.     BOOL AddHead(CBaseList *pList);
  343.  
  344.  
  345.     /* Add the object *pObj to *this after position p in *this.
  346.        AddAfter(NULL,x) adds x to the start - equivalent to AddHead
  347.        Return the position of the object added, NULL if it failed.
  348.        Existing POSITIONs in *this are undisturbed, including p.
  349.     */
  350. protected:
  351.     POSITION AddAfterI(POSITION p, void * pObj);
  352. public:
  353.  
  354.     /* Add the list *pList to *this after position p in *this
  355.        AddAfter(NULL,x) adds x to the start - equivalent to AddHead
  356.        Return TRUE if it all worked, FALSE if it didn't.
  357.        If it fails, some of the objects may be added
  358.        Existing POSITIONs in *this are undisturbed, including p.
  359.     */
  360.     BOOL AddAfter(POSITION p, CBaseList *pList);
  361.  
  362.  
  363.     /* Mirror images:
  364.        Add the object *pObj to this-List after position p in *this.
  365.        AddBefore(NULL,x) adds x to the end - equivalent to AddTail
  366.        Return the position of the new object, NULL if it fails
  367.        Existing POSITIONs in *this are undisturbed, including p.
  368.     */
  369.     protected:
  370.     POSITION AddBeforeI(POSITION p, void * pObj);
  371.     public:
  372.  
  373.     /* Add the list *pList to *this before position p in *this
  374.        AddAfter(NULL,x) adds x to the start - equivalent to AddHead
  375.        Return TRUE if it all worked, FALSE if it didn't.
  376.        If it fails, some of the objects may be added
  377.        Existing POSITIONs in *this are undisturbed, including p.
  378.     */
  379.     BOOL AddBefore(POSITION p, CBaseList *pList);
  380.  
  381.  
  382.     /* Note that AddAfter(p,x) is equivalent to AddBefore(Next(p),x)
  383.        even in cases where p is NULL or Next(p) is NULL.
  384.        Similarly for mirror images etc.
  385.        This may make it easier to argue about programs.
  386.     */
  387.  
  388.  
  389.  
  390.     /* The following operations do not copy any elements.
  391.        They move existing blocks of elements around by switching pointers.
  392.        They are fairly efficient for long lists as for short lists.
  393.        (Alas, the Count slows things down).
  394.  
  395.        They split the list into two parts.
  396.        One part remains as the original list, the other part
  397.        is appended to the second list.  There are eight possible
  398.        variations:
  399.        Split the list {after/before} a given element
  400.        keep the {head/tail} portion in the original list
  401.        append the rest to the {head/tail} of the new list.
  402.  
  403.        Since After is strictly equivalent to Before Next
  404.        we are not in serious need of the Before/After variants.
  405.        That leaves only four.
  406.  
  407.        If you are processing a list left to right and dumping
  408.        the bits that you have processed into another list as
  409.        you go, the Tail/Tail variant gives the most natural result.
  410.        If you are processing in reverse order, Head/Head is best.
  411.  
  412.        By using NULL positions and empty lists judiciously either
  413.        of the other two can be built up in two operations.
  414.  
  415.        The definition of NULL (see Next/Prev etc) means that
  416.        degenerate cases include
  417.           "move all elements to new list"
  418.           "Split a list into two lists"
  419.           "Concatenate two lists"
  420.           (and quite a few no-ops)
  421.  
  422.        !!WARNING!! The type checking won't buy you much if you get list
  423.        positions muddled up - e.g. use a POSITION that's in a different
  424.        list and see what a mess you get!
  425.     */
  426.  
  427.     /* Split *this after position p in *this
  428.        Retain as *this the tail portion of the original *this
  429.        Add the head portion to the tail end of *pList
  430.        Return TRUE if it all worked, FALSE if it didn't.
  431.  
  432.        e.g.
  433.           foo->MoveToTail(foo->GetHeadPosition(), bar);
  434.               moves one element from the head of foo to the tail of bar
  435.           foo->MoveToTail(NULL, bar);
  436.               is a no-op, returns NULL
  437.           foo->MoveToTail(foo->GetTailPosition, bar);
  438.               concatenates foo onto the end of bar and empties foo.
  439.  
  440.        A better, except excessively long name might be
  441.            MoveElementsFromHeadThroughPositionToOtherTail
  442.     */
  443.     BOOL MoveToTail(POSITION pos, CBaseList *pList);
  444.  
  445.  
  446.     /* Mirror image:
  447.        Split *this before position p in *this.
  448.        Retain in *this the head portion of the original *this
  449.        Add the tail portion to the start (i.e. head) of *pList
  450.  
  451.        e.g.
  452.           foo->MoveToHead(foo->GetTailPosition(), bar);
  453.               moves one element from the tail of foo to the head of bar
  454.           foo->MoveToHead(NULL, bar);
  455.               is a no-op, returns NULL
  456.           foo->MoveToHead(foo->GetHeadPosition, bar);
  457.               concatenates foo onto the start of bar and empties foo.
  458.     */
  459.     BOOL MoveToHead(POSITION pos, CBaseList *pList);
  460.  
  461.  
  462.     /* Reverse the order of the [pointers to] objects in *this
  463.     */
  464.     void Reverse();
  465.  
  466.  
  467.     /* set cursor to the position of each element of list in turn  */
  468.     #define TRAVERSELIST(list, cursor)               \
  469.     for ( cursor = (list).GetHeadPosition()           \
  470.         ; cursor!=NULL                               \
  471.         ; cursor = (list).Next(cursor)                \
  472.         )
  473.  
  474.  
  475.     /* set cursor to the position of each element of list in turn
  476.        in reverse order
  477.     */
  478.     #define REVERSETRAVERSELIST(list, cursor)        \
  479.     for ( cursor = (list).GetTailPosition()           \
  480.         ; cursor!=NULL                               \
  481.         ; cursor = (list).Prev(cursor)                \
  482.         )
  483.  
  484. }; // end of class declaration
  485.  
  486. template<class OBJECT> class CGenericList : public CBaseList
  487. {
  488. public:
  489.     CGenericList(TCHAR *pName,
  490.                  INT iItems = DEFAULTCACHE,
  491.                  BOOL bLock = TRUE,
  492.                  BOOL bAlert = FALSE) :
  493.                      CBaseList(pName, iItems) {
  494.         UNREFERENCED_PARAMETER(bAlert);
  495.         UNREFERENCED_PARAMETER(bLock);
  496.     };
  497.  
  498.     OBJECT *GetNext(POSITION& rp) { return (OBJECT *) GetNextI(rp); }
  499.  
  500.     OBJECT *Get(POSITION p) { return (OBJECT *) GetI(p); }
  501.  
  502.     OBJECT *RemoveHead() { return (OBJECT *) RemoveHeadI(); }
  503.  
  504.     OBJECT *RemoveTail() { return (OBJECT *) RemoveTailI(); }
  505.  
  506.     OBJECT *Remove(POSITION p) { return (OBJECT *) RemoveI(p); }
  507.     POSITION AddBefore(POSITION p, OBJECT * pObj) { return AddBeforeI(p, pObj); }
  508.     POSITION AddAfter(POSITION p, OBJECT * pObj)  { return AddAfterI(p, pObj); }
  509.     POSITION AddHead(OBJECT * pObj) { return AddHeadI(pObj); }
  510.     POSITION AddTail(OBJECT * pObj)  { return AddTailI(pObj); }
  511.     BOOL AddTail(CGenericList<OBJECT> *pList)
  512.         { return CBaseList::AddTail((CBaseList *) pList); }
  513.     BOOL AddHead(CGenericList<OBJECT> *pList)
  514.         { return CBaseList::AddHead((CBaseList *) pList); }
  515.     BOOL AddAfter(POSITION p, CGenericList<OBJECT> *pList)
  516.             { return CBaseList::AddAfter(p, (CBaseList *) pList); };
  517.     BOOL AddBefore(POSITION p, CGenericList<OBJECT> *pList)
  518.             { return CBaseList::AddBefore(p, (CBaseList *) pList); };
  519.     POSITION Find( OBJECT * pObj) { return FindI(pObj); }
  520. }; // end of class declaration
  521.  
  522.  
  523.  
  524. /* These define the standard list types */
  525.  
  526. typedef CGenericList<CBaseObject> CBaseObjectList;
  527. typedef CGenericList<IUnknown> CBaseInterfaceList;
  528.  
  529. #endif /* __WXLIST__ */
  530.  
  531.