1 /* -*- Mode: C; tab-width: 4 -*- 2 * 3 * Copyright (c) 2003 Apple Computer, Inc. All rights reserved. 4 * 5 * Licensed under the Apache License, Version 2.0 (the "License"); 6 * you may not use this file except in compliance with the License. 7 * You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 17 File: GenLinkedList.c 18 19 Contains: implementation of generic linked lists. 20 21 Version: 1.0 22 Tabs: 4 spaces 23 */ 24 25 #include "GenLinkedList.h" 26 27 28 // Return the link pointer contained within element e at offset o. 29 #define GETLINK( e, o) ( *(void**)((char*) (e) + (o)) ) 30 31 // Assign the link pointer l to element e at offset o. 32 #define ASSIGNLINK( e, l, o) ( *((void**)((char*) (e) + (o))) = (l)) 33 34 35 // GenLinkedList ///////////////////////////////////////////////////////////// 36 37 void InitLinkedList( GenLinkedList *pList, size_t linkOffset) 38 /* Initialize the block of memory pointed to by pList as a linked list. */ 39 { 40 pList->Head = NULL; 41 pList->Tail = NULL; 42 pList->LinkOffset = linkOffset; 43 } 44 45 46 void AddToTail( GenLinkedList *pList, void *elem) 47 /* Add a linked list element to the tail of the list. */ 48 { 49 if ( pList->Tail) { 50 ASSIGNLINK( pList->Tail, elem, pList->LinkOffset); 51 } else 52 pList->Head = elem; 53 ASSIGNLINK( elem, NULL, pList->LinkOffset); 54 55 pList->Tail = elem; 56 } 57 58 59 void AddToHead( GenLinkedList *pList, void *elem) 60 /* Add a linked list element to the head of the list. */ 61 { 62 ASSIGNLINK( elem, pList->Head, pList->LinkOffset); 63 if ( pList->Tail == NULL) 64 pList->Tail = elem; 65 66 pList->Head = elem; 67 } 68 69 70 int RemoveFromList( GenLinkedList *pList, void *elem) 71 /* Remove a linked list element from the list. Return 0 if it was not found. */ 72 /* If the element is removed, its link will be set to NULL. */ 73 { 74 void *iElem, *lastElem; 75 76 for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) { 77 if ( iElem == elem) { 78 if ( lastElem) { // somewhere past the head 79 ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset); 80 } else { // at the head 81 pList->Head = GETLINK( elem, pList->LinkOffset); 82 } 83 if ( pList->Tail == elem) 84 pList->Tail = lastElem ? lastElem : NULL; 85 ASSIGNLINK( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug. 86 return 1; 87 } 88 lastElem = iElem; 89 } 90 91 return 0; 92 } 93 94 95 int ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem) 96 /* Replace an element in the list with a new element, in the same position. */ 97 { 98 void *iElem, *lastElem; 99 100 if ( elemInList == NULL || newElem == NULL) 101 return 0; 102 103 for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) 104 { 105 if ( iElem == elemInList) 106 { 107 ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset); 108 if ( lastElem) // somewhere past the head 109 { 110 ASSIGNLINK( lastElem, newElem, pList->LinkOffset); 111 } 112 else // at the head 113 { 114 pList->Head = newElem; 115 } 116 if ( pList->Tail == elemInList) 117 pList->Tail = newElem; 118 return 1; 119 } 120 lastElem = iElem; 121 } 122 123 return 0; 124 } 125 126 127 // GenDoubleLinkedList ///////////////////////////////////////////////////////// 128 129 void InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset, 130 size_t backLinkOffset) 131 /* Initialize the block of memory pointed to by pList as a double linked list. */ 132 { 133 pList->Head = NULL; 134 pList->Tail = NULL; 135 pList->FwdLinkOffset = fwdLinkOffset; 136 pList->BackLinkOffset = backLinkOffset; 137 } 138 139 140 void DLLAddToHead( GenDoubleLinkedList *pList, void *elem) 141 /* Add a linked list element to the head of the list. */ 142 { 143 void *pNext; 144 145 pNext = pList->Head; 146 147 // fix up the forward links 148 ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset); 149 pList->Head = elem; 150 151 // fix up the backward links 152 if ( pNext) { 153 ASSIGNLINK( pNext, elem, pList->BackLinkOffset); 154 } else 155 pList->Tail = elem; 156 ASSIGNLINK( elem, NULL, pList->BackLinkOffset); 157 } 158 159 160 void DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem) 161 /* Remove a linked list element from the list. */ 162 /* When the element is removed, its link will be set to NULL. */ 163 { 164 void *pNext, *pPrev; 165 166 pNext = GETLINK( elem, pList->FwdLinkOffset); 167 pPrev = GETLINK( elem, pList->BackLinkOffset); 168 169 // fix up the forward links 170 if ( pPrev) 171 ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset); 172 else 173 pList->Head = pNext; 174 175 // fix up the backward links 176 if ( pNext) 177 ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset); 178 else 179 pList->Tail = pPrev; 180 181 ASSIGNLINK( elem, NULL, pList->FwdLinkOffset); 182 ASSIGNLINK( elem, NULL, pList->BackLinkOffset); 183 } 184 185 186 // GenLinkedOffsetList ///////////////////////////////////////////////////// 187 188 // Extract the Next offset from element 189 #define GETOFFSET( e, o) ( *(size_t*)((char*) (e) + (o)) ) 190 191 static void AssignOffsetLink( void *elem, void *link, size_t linkOffset); 192 193 194 static void AssignOffsetLink( void *elem, void *link, size_t linkOffset) 195 // Assign link to elem as an offset from elem. Assign 0 to elem if link is NULL. 196 { 197 GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0; 198 } 199 200 201 void *GetHeadPtr( GenLinkedOffsetList *pList) 202 /* Return a pointer to the head element of a list, or NULL if none. */ 203 { 204 return pList->Head ? ( (char*) (pList) + pList->Head) : NULL; 205 } 206 207 208 void *GetTailPtr( GenLinkedOffsetList *pList) 209 /* Return a pointer to the tail element of a list, or NULL if none. */ 210 { 211 return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL; 212 } 213 214 215 void *GetOffsetLink( GenLinkedOffsetList *pList, void *elem) 216 /* Return the link pointer contained within element e for pList, or NULL if it is 0. */ 217 { 218 size_t nextOffset; 219 220 nextOffset = GETOFFSET( elem, pList->LinkOffset); 221 222 return nextOffset ? (char*) elem + nextOffset : NULL; 223 } 224 225 226 void InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset) 227 /* Initialize the block of memory pointed to by pList as a linked list. */ 228 { 229 pList->Head = 0; 230 pList->Tail = 0; 231 pList->LinkOffset = linkOffset; 232 } 233 234 235 void OffsetAddToTail( GenLinkedOffsetList *pList, void *elem) 236 /* Add a linked list element to the tail of the list. */ 237 { 238 if ( pList->Tail) { 239 AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset); 240 } else 241 pList->Head = (size_t) elem - (size_t) pList; 242 AssignOffsetLink( elem, NULL, pList->LinkOffset); 243 244 pList->Tail = (size_t) elem - (size_t) pList; 245 } 246 247 248 void OffsetAddToHead( GenLinkedOffsetList *pList, void *elem) 249 /* Add a linked list element to the head of the list. */ 250 { 251 AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset); 252 if ( pList->Tail == 0) 253 pList->Tail = (size_t) elem - (size_t) pList; 254 255 pList->Head = (size_t) elem - (size_t) pList; 256 } 257 258 259 int OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem) 260 /* Remove a linked list element from the list. Return 0 if it was not found. */ 261 /* If the element is removed, its link will be set to NULL. */ 262 { 263 void *iElem, *lastElem; 264 265 for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem; 266 iElem = GetOffsetLink( pList, iElem)) 267 { 268 if ( iElem == elem) { 269 if ( lastElem) { // somewhere past the head 270 AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset); 271 } else { // at the head 272 iElem = GetOffsetLink( pList, elem); 273 pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0; 274 } 275 if ( GetTailPtr( pList) == elem) 276 pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0; 277 AssignOffsetLink( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug. 278 return 1; 279 } 280 lastElem = iElem; 281 } 282 283 return 0; 284 } 285 286 287 int OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem) 288 /* Replace an element in the list with a new element, in the same position. */ 289 { 290 void *iElem, *lastElem; 291 292 if ( elemInList == NULL || newElem == NULL) 293 return 0; 294 295 for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem; 296 iElem = GetOffsetLink( pList, iElem)) 297 { 298 if ( iElem == elemInList) 299 { 300 AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset); 301 if ( lastElem) // somewhere past the head 302 { 303 AssignOffsetLink( lastElem, newElem, pList->LinkOffset); 304 } 305 else // at the head 306 { 307 pList->Head = (size_t) newElem - (size_t) pList; 308 } 309 if ( GetTailPtr( pList) == elemInList) 310 pList->Tail = (size_t) newElem - (size_t) pList; 311 return 1; 312 } 313 lastElem = iElem; 314 } 315 316 return 0; 317 } 318 319 320