1 /* -*- Mode: C; tab-width: 4 -*-
3 * Copyright (c) 2003-2011 Apple Inc. All rights reserved.
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
9 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "GenLinkedList.h"
21 // Return the link pointer contained within element e at offset o.
22 #define GETLINK( e, o) ( *(void**)((char*) (e) + (o)) )
24 // Assign the link pointer l to element e at offset o.
25 #define ASSIGNLINK( e, l, o) ( *((void**)((char*) (e) + (o))) = (l))
28 // GenLinkedList /////////////////////////////////////////////////////////////
30 void InitLinkedList( GenLinkedList
*pList
, size_t linkOffset
)
31 /* Initialize the block of memory pointed to by pList as a linked list. */
35 pList
->LinkOffset
= linkOffset
;
39 void AddToTail( GenLinkedList
*pList
, void *elem
)
40 /* Add a linked list element to the tail of the list. */
43 ASSIGNLINK( pList
->Tail
, elem
, pList
->LinkOffset
);
46 ASSIGNLINK( elem
, NULL
, pList
->LinkOffset
);
52 void AddToHead( GenLinkedList
*pList
, void *elem
)
53 /* Add a linked list element to the head of the list. */
55 ASSIGNLINK( elem
, pList
->Head
, pList
->LinkOffset
);
56 if ( pList
->Tail
== NULL
)
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. */
67 void *iElem
, *lastElem
;
69 for ( iElem
= pList
->Head
, lastElem
= NULL
; iElem
; iElem
= GETLINK( iElem
, pList
->LinkOffset
)) {
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
);
76 if ( pList
->Tail
== elem
)
77 pList
->Tail
= lastElem
? lastElem
: NULL
;
78 ASSIGNLINK( elem
, NULL
, pList
->LinkOffset
); // maybe catch a stale reference bug.
88 int ReplaceElem( GenLinkedList
*pList
, void *elemInList
, void *newElem
)
89 /* Replace an element in the list with a new element, in the same position. */
91 void *iElem
, *lastElem
;
93 if ( elemInList
== NULL
|| newElem
== NULL
)
96 for ( iElem
= pList
->Head
, lastElem
= NULL
; iElem
; iElem
= GETLINK( iElem
, pList
->LinkOffset
))
98 if ( iElem
== elemInList
)
100 ASSIGNLINK( newElem
, GETLINK( elemInList
, pList
->LinkOffset
), pList
->LinkOffset
);
101 if ( lastElem
) // somewhere past the head
103 ASSIGNLINK( lastElem
, newElem
, pList
->LinkOffset
);
107 pList
->Head
= newElem
;
109 if ( pList
->Tail
== elemInList
)
110 pList
->Tail
= newElem
;
120 // GenDoubleLinkedList /////////////////////////////////////////////////////////
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. */
128 pList
->FwdLinkOffset
= fwdLinkOffset
;
129 pList
->BackLinkOffset
= backLinkOffset
;
133 void DLLAddToHead( GenDoubleLinkedList
*pList
, void *elem
)
134 /* Add a linked list element to the head of the list. */
140 // fix up the forward links
141 ASSIGNLINK( elem
, pList
->Head
, pList
->FwdLinkOffset
);
144 // fix up the backward links
146 ASSIGNLINK( pNext
, elem
, pList
->BackLinkOffset
);
149 ASSIGNLINK( elem
, NULL
, pList
->BackLinkOffset
);
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. */
159 pNext
= GETLINK( elem
, pList
->FwdLinkOffset
);
160 pPrev
= GETLINK( elem
, pList
->BackLinkOffset
);
162 // fix up the forward links
164 ASSIGNLINK( pPrev
, pNext
, pList
->FwdLinkOffset
);
168 // fix up the backward links
170 ASSIGNLINK( pNext
, pPrev
, pList
->BackLinkOffset
);
174 ASSIGNLINK( elem
, NULL
, pList
->FwdLinkOffset
);
175 ASSIGNLINK( elem
, NULL
, pList
->BackLinkOffset
);
179 // GenLinkedOffsetList /////////////////////////////////////////////////////
181 // Extract the Next offset from element
182 #define GETOFFSET( e, o) ( *(size_t*)((char*) (e) + (o)) )
184 static void AssignOffsetLink( void *elem
, void *link
, size_t linkOffset
);
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.
190 GETOFFSET( elem
, linkOffset
) = link
? (size_t) link
- (size_t) elem
: 0;
194 void *GetHeadPtr( GenLinkedOffsetList
*pList
)
195 /* Return a pointer to the head element of a list, or NULL if none. */
197 return pList
->Head
? ( (char*) (pList
) + pList
->Head
) : NULL
;
201 void *GetTailPtr( GenLinkedOffsetList
*pList
)
202 /* Return a pointer to the tail element of a list, or NULL if none. */
204 return pList
->Tail
? ( (char*) (pList
) + pList
->Tail
) : NULL
;
208 void *GetOffsetLink( GenLinkedOffsetList
*pList
, void *elem
)
209 /* Return the link pointer contained within element e for pList, or NULL if it is 0. */
213 nextOffset
= GETOFFSET( elem
, pList
->LinkOffset
);
215 return nextOffset
? (char*) elem
+ nextOffset
: NULL
;
219 void InitLinkedOffsetList( GenLinkedOffsetList
*pList
, size_t linkOffset
)
220 /* Initialize the block of memory pointed to by pList as a linked list. */
224 pList
->LinkOffset
= linkOffset
;
228 void OffsetAddToTail( GenLinkedOffsetList
*pList
, void *elem
)
229 /* Add a linked list element to the tail of the list. */
232 AssignOffsetLink( GetTailPtr( pList
), elem
, pList
->LinkOffset
);
234 pList
->Head
= (size_t) elem
- (size_t) pList
;
235 AssignOffsetLink( elem
, NULL
, pList
->LinkOffset
);
237 pList
->Tail
= (size_t) elem
- (size_t) pList
;
241 void OffsetAddToHead( GenLinkedOffsetList
*pList
, void *elem
)
242 /* Add a linked list element to the head of the list. */
244 AssignOffsetLink( elem
, GetHeadPtr( pList
), pList
->LinkOffset
);
245 if ( pList
->Tail
== 0)
246 pList
->Tail
= (size_t) elem
- (size_t) pList
;
248 pList
->Head
= (size_t) elem
- (size_t) pList
;
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. */
256 void *iElem
, *lastElem
;
258 for ( iElem
= GetHeadPtr( pList
), lastElem
= NULL
; iElem
;
259 iElem
= GetOffsetLink( pList
, iElem
))
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;
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.
280 int OffsetReplaceElem( GenLinkedOffsetList
*pList
, void *elemInList
, void *newElem
)
281 /* Replace an element in the list with a new element, in the same position. */
283 void *iElem
, *lastElem
;
285 if ( elemInList
== NULL
|| newElem
== NULL
)
288 for ( iElem
= GetHeadPtr( pList
), lastElem
= NULL
; iElem
;
289 iElem
= GetOffsetLink( pList
, iElem
))
291 if ( iElem
== elemInList
)
293 AssignOffsetLink( newElem
, GetOffsetLink( pList
, elemInList
), pList
->LinkOffset
);
294 if ( lastElem
) // somewhere past the head
296 AssignOffsetLink( lastElem
, newElem
, pList
->LinkOffset
);
300 pList
->Head
= (size_t) newElem
- (size_t) pList
;
302 if ( GetTailPtr( pList
) == elemInList
)
303 pList
->Tail
= (size_t) newElem
- (size_t) pList
;