mDNSShared/GenLinkedList.c

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