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 30void 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 39void 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 52void 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 63int 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 88int 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 122void 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 133void 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 153void 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 184static void AssignOffsetLink( void *elem, void *link, size_t linkOffset); 185 186 187static 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 194void *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 201void *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 208void *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 219void 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 228void 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 241void 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 252int 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 280int 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