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
InitLinkedList(GenLinkedList * pList,size_t linkOffset)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
AddToTail(GenLinkedList * pList,void * elem)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
AddToHead(GenLinkedList * pList,void * elem)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
RemoveFromList(GenLinkedList * pList,void * elem)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
ReplaceElem(GenLinkedList * pList,void * elemInList,void * newElem)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
InitDoubleLinkedList(GenDoubleLinkedList * pList,size_t fwdLinkOffset,size_t backLinkOffset)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
DLLAddToHead(GenDoubleLinkedList * pList,void * elem)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
DLLRemoveFromList(GenDoubleLinkedList * pList,void * elem)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
AssignOffsetLink(void * elem,void * link,size_t linkOffset)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
GetHeadPtr(GenLinkedOffsetList * pList)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
GetTailPtr(GenLinkedOffsetList * pList)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
GetOffsetLink(GenLinkedOffsetList * pList,void * elem)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
InitLinkedOffsetList(GenLinkedOffsetList * pList,size_t linkOffset)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
OffsetAddToTail(GenLinkedOffsetList * pList,void * elem)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
OffsetAddToHead(GenLinkedOffsetList * pList,void * elem)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
OffsetRemoveFromList(GenLinkedOffsetList * pList,void * elem)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
OffsetReplaceElem(GenLinkedOffsetList * pList,void * elemInList,void * newElem)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
320