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