xref: /illumos-gate/usr/src/contrib/mDNSResponder/mDNSShared/GenLinkedList.c (revision 472cd20d26008f77084ade4c2048159b98c2b705)
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 
InitLinkedList(GenLinkedList * pList,size_t linkOffset)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 
AddToTail(GenLinkedList * pList,void * elem)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 
AddToHead(GenLinkedList * pList,void * elem)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 
RemoveFromList(GenLinkedList * pList,void * elem)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 
ReplaceElem(GenLinkedList * pList,void * elemInList,void * newElem)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 
InitDoubleLinkedList(GenDoubleLinkedList * pList,size_t fwdLinkOffset,size_t backLinkOffset)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 
DLLAddToHead(GenDoubleLinkedList * pList,void * elem)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 
DLLRemoveFromList(GenDoubleLinkedList * pList,void * elem)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 
AssignOffsetLink(void * elem,void * link,size_t linkOffset)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 
GetHeadPtr(GenLinkedOffsetList * pList)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 
GetTailPtr(GenLinkedOffsetList * pList)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 
GetOffsetLink(GenLinkedOffsetList * pList,void * elem)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 
InitLinkedOffsetList(GenLinkedOffsetList * pList,size_t linkOffset)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 
OffsetAddToTail(GenLinkedOffsetList * pList,void * elem)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 
OffsetAddToHead(GenLinkedOffsetList * pList,void * elem)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 
OffsetRemoveFromList(GenLinkedOffsetList * pList,void * elem)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 
OffsetReplaceElem(GenLinkedOffsetList * pList,void * elemInList,void * newElem)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 
315