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