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