mDNSShared/GenLinkedList.c

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