GenLinkedList.c

Go to the documentation of this file.
00001 /*
00002         File:           GenLinkedList.c
00003         
00004         Contains:       Linked List utility routines
00005 
00006         Disclaimer:     IMPORTANT:  This Apple software is supplied to you by Apple Computer, Inc.
00007                                 ("Apple") in consideration of your agreement to the following terms, and your
00008                                 use, installation, modification or redistribution of this Apple software
00009                                 constitutes acceptance of these terms.  If you do not agree with these terms,
00010                                 please do not use, install, modify or redistribute this Apple software.
00011 
00012                                 In consideration of your agreement to abide by the following terms, and subject
00013                                 to these terms, Apple grants you a personal, non-exclusive license, under Apple’s
00014                                 copyrights in this original Apple software (the "Apple Software"), to use,
00015                                 reproduce, modify and redistribute the Apple Software, with or without
00016                                 modifications, in source and/or binary forms; provided that if you redistribute
00017                                 the Apple Software in its entirety and without modifications, you must retain
00018                                 this notice and the following text and disclaimers in all such redistributions of
00019                                 the Apple Software.  Neither the name, trademarks, service marks or logos of
00020                                 Apple Computer, Inc. may be used to endorse or promote products derived from the
00021                                 Apple Software without specific prior written permission from Apple.  Except as
00022                                 expressly stated in this notice, no other rights or licenses, express or implied,
00023                                 are granted by Apple herein, including but not limited to any patent rights that
00024                                 may be infringed by your derivative works or by other works in which the Apple
00025                                 Software may be incorporated.
00026 
00027                                 The Apple Software is provided by Apple on an "AS IS" basis.  APPLE MAKES NO
00028                                 WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
00029                                 WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00030                                 PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND OPERATION ALONE OR IN
00031                                 COMBINATION WITH YOUR PRODUCTS.
00032 
00033                                 IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL OR
00034                                 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
00035                                 GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00036                                 ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION, MODIFICATION AND/OR DISTRIBUTION
00037                                 OF THE APPLE SOFTWARE, HOWEVER CAUSED AND WHETHER UNDER THEORY OF CONTRACT, TORT
00038                                 (INCLUDING NEGLIGENCE), STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN
00039                                 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00040 
00041         Copyright © 2003-2004 Apple Computer, Inc., All Rights Reserved
00042 */
00043 
00044 #include "GenLinkedList.h"
00045 
00046 #pragma mark --- Data Structures ---
00047 
00048         /* This is the internal data structure for the nodes in the linked list.                */
00049         /*                                                                                                                                                              */
00050         /* Note: The memory pointed to by pNext is owned by the list and is disposed of */
00051         /* in DestroyList.  It should not be disposed of in any other way.                              */
00052         /*                                                                                                                                                              */
00053         /* Note: The memory pointed to by pData is owned by the caller of the linked    */
00054         /* list.  The caller is responsible for disposing of this memory.  This can be  */
00055         /* done by simply implementing a DisposeDataProc that will be called on each    */
00056         /* node in the list, giving the caller a chance to dispose of any memory                */
00057         /* created.  The DisposeDataProc is called from DestroyList                                             */ 
00058 struct GenNode
00059 {
00060         struct  GenNode                         *pNext; /* Pointer to the next node in the list         */
00061                         GenDataPtr                       pData; /* The data for this node, owned by caller      */
00062 };
00063 typedef struct GenNode GenNode;
00064 
00065 #pragma mark --- List Implementation ---
00066 
00067         /* Initializes the given GenLinkedList to an empty list.  This MUST be                  */
00068         /* called before any operations are performed on the list, otherwise bad things */
00069         /* will happen.                                                                                                                                 */
00070 void            InitLinkedList( GenLinkedList *pList, DisposeDataProcPtr disposeProcPtr)
00071 {
00072         if( pList == NULL )
00073                 return;
00074 
00075         pList->pHead = pList->pTail = NULL;
00076         pList->NumberOfItems    = 0;
00077         pList->DisposeProcPtr   = disposeProcPtr;
00078 }
00079 
00080         /* returns the current number of items in the given list.                                               */
00081         /* If pList == NULL, it returns 0                                                                                               */
00082 ItemCount       GetNumberOfItems( GenLinkedList *pList )
00083 {
00084         return (pList) ? pList->NumberOfItems : 0;
00085 }
00086         
00087         /* Creates a new node, containing pData, and adds it to the tail of pList.              */
00088         /* Note: if an error occurs, pList is unchanged.                                                                */
00089 OSErr           AddToTail( GenLinkedList *pList, void *pData )
00090 {
00091         OSErr           err                     = paramErr;
00092         GenNode         *tmpNode        = NULL;
00093         
00094         if( pList == NULL || pData == NULL )
00095                 return err;
00096 
00097                 /* create memory for new node, if this fails we _must_ bail     */
00098         err = ( ( tmpNode = (GenNode*) NewPtr( sizeof( GenNode ) ) ) != NULL ) ? noErr : MemError();
00099         if( err == noErr )
00100         {
00101                 tmpNode->pData = pData;                                                                 /* Setup new node                               */
00102                 tmpNode->pNext = NULL;
00103                 
00104                 if( pList->pTail != NULL )                                                              /* more then one item already   */
00105                         ((GenNode*) pList->pTail)->pNext = (void*) tmpNode;     /* so append to tail                    */
00106                 else
00107                         pList->pHead = (void*) tmpNode;                                         /* no items, so adjust head             */
00108                 
00109                 pList->pTail                    = (void*) tmpNode;
00110                 pList->NumberOfItems    += 1;
00111         }       
00112         
00113         return err;
00114 }
00115 
00116         /* Takes pSrcList and inserts it into pDestList at the location pIter points to.                        */
00117         /* The lists must have the same DisposeProcPtr, but the Data can be different.  If pSrcList     */
00118         /* is empty, it does nothing and just returns                                                                                           */
00119         /*                                                                                                                                                                                      */
00120         /* If pIter == NULL, insert pSrcList before the head                                                                            */
00121         /* else If pIter == pTail, append pSrcList to the tail                                                                          */
00122         /* else insert pSrcList in the middle somewhere                                                                                         */
00123         /* On return: pSrcList is cleared and is an empty list.                                                                         */
00124         /*            The data that was owned by pSrcList is now owned by pDestList                                     */
00125 void            InsertList( GenLinkedList *pDestList, GenLinkedList *pSrcList, GenIteratorPtr pIter )
00126 {
00127         if( pDestList           == NULL || pSrcList                     == NULL ||
00128                 pSrcList->pHead == NULL || pSrcList->pTail      == NULL ||
00129                 pDestList->DisposeProcPtr != pSrcList->DisposeProcPtr )
00130                 return;
00131                 
00132         if( pDestList->pHead == NULL && pDestList->pTail == NULL )      /* empty list                                   */
00133         {
00134                 pDestList->pHead = pSrcList->pHead;
00135                 pDestList->pTail = pSrcList->pTail;
00136         }
00137         else if( pIter == NULL )                                                                        /* insert before head                   */
00138         {                               
00139                         /* attach the list      */
00140                 ((GenNode*)pSrcList->pTail)->pNext = pDestList->pHead;
00141                         /* fix up head          */
00142                 pDestList->pHead = pSrcList->pHead;
00143         }
00144         else if( pIter == pDestList->pTail )                                            /* append to tail                               */
00145         {
00146                         /* attach the list      */
00147                 ((GenNode*)pDestList->pTail)->pNext = pSrcList->pHead;
00148                         /* fix up tail          */
00149                 pDestList->pTail = pSrcList->pTail;
00150         }
00151         else                                                                                                            /* insert in middle somewhere   */
00152         {
00153                 GenNode *tmpNode = ((GenNode*)pIter)->pNext;
00154                 ((GenNode*)pIter)->pNext = pSrcList->pHead;
00155                 ((GenNode*)pSrcList->pTail)->pNext = tmpNode;
00156         }
00157 
00158         pDestList->NumberOfItems += pSrcList->NumberOfItems;            /* sync up NumberOfItems                */
00159         
00160         InitLinkedList( pSrcList, NULL);                                                        /* reset the source list                */
00161 }
00162 
00163         /* Goes through the list and disposes of any memory we allocated.  Calls the DisposeProcPtr,*/
00164         /* if it exists, to give the caller a chance to free up their memory                                            */
00165 void            DestroyList( GenLinkedList      *pList )
00166 {
00167         GenIteratorPtr  pIter           = NULL,
00168                                         pNextIter       = NULL;
00169 
00170         if( pList == NULL )
00171                 return;
00172         
00173         for( InitIterator( pList, &pIter ), pNextIter = pIter; pIter != NULL; pIter = pNextIter )
00174         {
00175                 Next( &pNextIter );     /* get the next node before we blow away the link */
00176                 
00177                 if( pList->DisposeProcPtr != NULL )
00178                         CallDisposeDataProc( pList->DisposeProcPtr, GetData( pIter ) );
00179                 DisposePtr( (char*) pIter );
00180         }
00181         
00182         InitLinkedList( pList, NULL);           
00183 }
00184 
00185 /*#############################################*/
00186 /*#############################################*/
00187 /*#############################################*/
00188 
00189 #pragma mark -
00190 #pragma mark --- Iterator Implementation ---
00191 
00192         /* Initializes pIter to point at the head of pList                                                      */
00193         /* This must be called before performing any operations with pIter                      */
00194 void            InitIterator( GenLinkedList *pList, GenIteratorPtr *pIter )
00195 {
00196         if( pList != NULL && pIter != NULL )
00197                 *pIter = pList->pHead;
00198 }
00199 
00200         /* On return, pIter points to the next node in the list.  NULL if its gone      */
00201         /* past the end of the list                                                                                                     */
00202 void            Next( GenIteratorPtr *pIter )
00203 {
00204         if( pIter != NULL )
00205                 *pIter = ((GenNode*)*pIter)->pNext;
00206 }
00207 
00208         /* Returns the data of the current node that pIter points to                            */
00209 GenDataPtr      GetData( GenIteratorPtr pIter )
00210 {
00211         return ( pIter != NULL ) ? ((GenNode*)pIter)->pData : NULL;
00212 }

Generated on Thu Jul 1 06:08:17 2010 for Second Life Viewer by  doxygen 1.4.7