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