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