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
37void		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
46void		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
59void		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
70int		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{
74void	*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
95int			ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
96/* Replace an element in the list with a new element, in the same position. */
97{
98void	*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
129void		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
140void			DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
141/* Add a linked list element to the head of the list. */
142{
143void		*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
160void			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{
164void		*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
191static void		AssignOffsetLink( void *elem, void *link, size_t linkOffset);
192
193
194static 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
201void		*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
208void		*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
215void		*GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
216/* Return the link pointer contained within element e for pList, or NULL if it is 0. */
217{
218size_t		nextOffset;
219
220	nextOffset = GETOFFSET( elem, pList->LinkOffset);
221
222	return nextOffset ? (char*) elem + nextOffset : NULL;
223}
224
225
226void		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
235void		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
248void		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
259int		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{
263void	*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
287int			OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
288/* Replace an element in the list with a new element, in the same position. */
289{
290void	*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