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