mDNSShared/GenLinkedList.c

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