mDNSShared/GenLinkedList.c

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