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 }
1.4.7