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