mDNSShared/GenLinkedList.c

   1 /*
   2  * Copyright (c) 2003-2019 Apple Inc. All rights reserved.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "GenLinkedList.h"
  18
  19
  20 // Return the link pointer contained within element e at offset o.
  21 #define     GETLINK( e, o)          ( *(void**)((char*) (e) + (o)) )
  22
  23 // Assign the link pointer l to element e at offset o.
  24 #define     ASSIGNLINK( e, l, o)    ( *((void**)((char*) (e) + (o))) = (l))
  25
  26
  27 //              GenLinkedList           /////////////////////////////////////////////////////////////
  28
  29 void        InitLinkedList( GenLinkedList *pList, size_t linkOffset)
  30 /* Initialize the block of memory pointed to by pList as a linked list. */
  31 {
  32     pList->Head = NULL;
  33     pList->Tail = NULL;
  34     pList->LinkOffset = linkOffset;
  35 }
  36
  37
  38 void        AddToTail( GenLinkedList *pList, void *elem)
  39 /* Add a linked list element to the tail of the list. */
  40 {
  41     if ( pList->Tail) {
  42         ASSIGNLINK( pList->Tail, elem, pList->LinkOffset);
  43     } else
  44         pList->Head = elem;
  45     ASSIGNLINK( elem, NULL, pList->LinkOffset);
  46
  47     pList->Tail = elem;
  48 }
  49
  50
  51 void        AddToHead( GenLinkedList *pList, void *elem)
  52 /* Add a linked list element to the head of the list. */
  53 {
  54     ASSIGNLINK( elem, pList->Head, pList->LinkOffset);
  55     if ( pList->Tail == NULL)
  56         pList->Tail = elem;
  57
  58     pList->Head = elem;
  59 }
  60
  61
  62 int     RemoveFromList( GenLinkedList *pList, void *elem)
  63 /* Remove a linked list element from the list. Return 0 if it was not found. */
  64 /* If the element is removed, its link will be set to NULL. */
  65 {
  66     void    *iElem, *lastElem;
  67
  68     for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) {
  69         if ( iElem == elem) {
  70             if ( lastElem) {        // somewhere past the head
  71                 ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset);
  72             } else {                // at the head
  73                 pList->Head = GETLINK( elem, pList->LinkOffset);
  74             }
  75             if ( pList->Tail == elem)
  76                 pList->Tail = lastElem ? lastElem : NULL;
  77             ASSIGNLINK( elem, NULL, pList->LinkOffset);         // maybe catch a stale reference bug.
  78             return 1;
  79         }
  80         lastElem = iElem;
  81     }
  82
  83     return 0;
  84 }
  85
  86
  87 int         ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
  88 /* Replace an element in the list with a new element, in the same position. */
  89 {
  90     void    *iElem, *lastElem;
  91
  92     if ( elemInList == NULL || newElem == NULL)
  93         return 0;
  94
  95     for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset))
  96     {
  97         if ( iElem == elemInList)
  98         {
  99             ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset);
 100             if ( lastElem)      // somewhere past the head
 101             {
 102                 ASSIGNLINK( lastElem, newElem, pList->LinkOffset);
 103             }
 104             else                // at the head
 105             {
 106                 pList->Head = newElem;
 107             }
 108             if ( pList->Tail == elemInList)
 109                 pList->Tail = newElem;
 110             return 1;
 111         }
 112         lastElem = iElem;
 113     }
 114
 115     return 0;
 116 }
 117
 118
 119 //              GenDoubleLinkedList             /////////////////////////////////////////////////////////
 120
 121 void        InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset,
 122                                   size_t backLinkOffset)
 123 /* Initialize the block of memory pointed to by pList as a double linked list. */
 124 {
 125     pList->Head = NULL;
 126     pList->Tail = NULL;
 127     pList->FwdLinkOffset = fwdLinkOffset;
 128     pList->BackLinkOffset = backLinkOffset;
 129 }
 130
 131
 132 void            DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
 133 /* Add a linked list element to the head of the list. */
 134 {
 135     void        *pNext;
 136
 137     pNext = pList->Head;
 138
 139     // fix up the forward links
 140     ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset);
 141     pList->Head = elem;
 142
 143     // fix up the backward links
 144     if ( pNext) {
 145         ASSIGNLINK( pNext, elem, pList->BackLinkOffset);
 146     } else
 147         pList->Tail = elem;
 148     ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
 149 }
 150
 151
 152 void            DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem)
 153 /* Remove a linked list element from the list. */
 154 /* When the element is removed, its link will be set to NULL. */
 155 {
 156     void        *pNext, *pPrev;
 157
 158     pNext = GETLINK( elem, pList->FwdLinkOffset);
 159     pPrev = GETLINK( elem, pList->BackLinkOffset);
 160
 161     // fix up the forward links
 162     if ( pPrev)
 163         ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset);
 164     else
 165         pList->Head = pNext;
 166
 167     // fix up the backward links
 168     if ( pNext)
 169         ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset);
 170     else
 171         pList->Tail = pPrev;
 172
 173     ASSIGNLINK( elem, NULL, pList->FwdLinkOffset);
 174     ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
 175 }
 176
 177
 178 //              GenLinkedOffsetList             /////////////////////////////////////////////////////
 179
 180 // Extract the Next offset from element
 181 #define     GETOFFSET( e, o)    ( *(size_t*)((char*) (e) + (o)) )
 182
 183 static void     AssignOffsetLink( void *elem, void *link, size_t linkOffset);
 184
 185
 186 static void AssignOffsetLink( void *elem, void *link, size_t linkOffset)
 187 // Assign link to elem as an offset from elem. Assign 0 to elem if link is NULL.
 188 {
 189     GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0;
 190 }
 191
 192
 193 void        *GetHeadPtr( GenLinkedOffsetList *pList)
 194 /* Return a pointer to the head element of a list, or NULL if none. */
 195 {
 196     return pList->Head ? ( (char*) (pList) + pList->Head) : NULL;
 197 }
 198
 199
 200 void        *GetTailPtr( GenLinkedOffsetList *pList)
 201 /* Return a pointer to the tail element of a list, or NULL if none. */
 202 {
 203     return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL;
 204 }
 205
 206
 207 void        *GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
 208 /* Return the link pointer contained within element e for pList, or NULL if it is 0. */
 209 {
 210     size_t nextOffset;
 211
 212     nextOffset = GETOFFSET( elem, pList->LinkOffset);
 213
 214     return nextOffset ? (char*) elem + nextOffset : NULL;
 215 }
 216
 217
 218 void        InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset)
 219 /* Initialize the block of memory pointed to by pList as a linked list. */
 220 {
 221     pList->Head = 0;
 222     pList->Tail = 0;
 223     pList->LinkOffset = linkOffset;
 224 }
 225
 226
 227 void        OffsetAddToTail( GenLinkedOffsetList *pList, void *elem)
 228 /* Add a linked list element to the tail of the list. */
 229 {
 230     if ( pList->Tail) {
 231         AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset);
 232     } else
 233         pList->Head = (size_t) elem - (size_t) pList;
 234     AssignOffsetLink( elem, NULL, pList->LinkOffset);
 235
 236     pList->Tail = (size_t) elem - (size_t) pList;
 237 }
 238
 239
 240 void        OffsetAddToHead( GenLinkedOffsetList *pList, void *elem)
 241 /* Add a linked list element to the head of the list. */
 242 {
 243     AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset);
 244     if ( pList->Tail == 0)
 245         pList->Tail = (size_t) elem - (size_t) pList;
 246
 247     pList->Head = (size_t) elem - (size_t) pList;
 248 }
 249
 250
 251 int     OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem)
 252 /* Remove a linked list element from the list. Return 0 if it was not found. */
 253 /* If the element is removed, its link will be set to NULL. */
 254 {
 255     void    *iElem, *lastElem;
 256
 257     if (elem == NULL) {
 258         return 0;
 259     }
 260     for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
 261           iElem = GetOffsetLink( pList, iElem))
 262     {
 263         if ( iElem == elem) {
 264             if ( lastElem) {        // somewhere past the head
 265                 AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset);
 266             } else {                // at the head
 267                 iElem = GetOffsetLink( pList, elem);
 268                 pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0;
 269             }
 270             if ( GetTailPtr( pList) == elem)
 271                 pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0;
 272             AssignOffsetLink( elem, NULL, pList->LinkOffset);   // maybe catch a stale reference bug.
 273             return 1;
 274         }
 275         lastElem = iElem;
 276     }
 277
 278     return 0;
 279 }
 280
 281
 282 int         OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
 283 /* Replace an element in the list with a new element, in the same position. */
 284 {
 285     void    *iElem, *lastElem;
 286
 287     if ( elemInList == NULL || newElem == NULL)
 288         return 0;
 289
 290     for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
 291           iElem = GetOffsetLink( pList, iElem))
 292     {
 293         if ( iElem == elemInList)
 294         {
 295             AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset);
 296             if ( lastElem)      // somewhere past the head
 297             {
 298                 AssignOffsetLink( lastElem, newElem, pList->LinkOffset);
 299             }
 300             else                // at the head
 301             {
 302                 pList->Head = (size_t) newElem - (size_t) pList;
 303             }
 304             if ( GetTailPtr( pList) == elemInList)
 305                 pList->Tail = (size_t) newElem - (size_t) pList;
 306             return 1;
 307         }
 308         lastElem = iElem;
 309     }
 310
 311     return 0;
 312 }
 313
 314