1/* -*- Mode: C; tab-width: 4 -*-
2 *
3 * Copyright (c) 2003-2011 Apple 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
18#include "GenLinkedList.h"
19
20
21// Return the link pointer contained within element e at offset o.
22#define     GETLINK( e, o)          ( *(void**)((char*) (e) + (o)) )
23
24// Assign the link pointer l to element e at offset o.
25#define     ASSIGNLINK( e, l, o)    ( *((void**)((char*) (e) + (o))) = (l))
26
27
28//		GenLinkedList		/////////////////////////////////////////////////////////////
29
30void        InitLinkedList( GenLinkedList *pList, size_t linkOffset)
31/* Initialize the block of memory pointed to by pList as a linked list. */
32{
33    pList->Head = NULL;
34    pList->Tail = NULL;
35    pList->LinkOffset = linkOffset;
36}
37
38
39void        AddToTail( GenLinkedList *pList, void *elem)
40/* Add a linked list element to the tail of the list. */
41{
42    if ( pList->Tail) {
43        ASSIGNLINK( pList->Tail, elem, pList->LinkOffset);
44    } else
45        pList->Head = elem;
46    ASSIGNLINK( elem, NULL, pList->LinkOffset);
47
48    pList->Tail = elem;
49}
50
51
52void        AddToHead( GenLinkedList *pList, void *elem)
53/* Add a linked list element to the head of the list. */
54{
55    ASSIGNLINK( elem, pList->Head, pList->LinkOffset);
56    if ( pList->Tail == NULL)
57        pList->Tail = elem;
58
59    pList->Head = elem;
60}
61
62
63int     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. */
66{
67    void    *iElem, *lastElem;
68
69    for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) {
70        if ( iElem == elem) {
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);
75            }
76            if ( pList->Tail == elem)
77                pList->Tail = lastElem ? lastElem : NULL;
78            ASSIGNLINK( elem, NULL, pList->LinkOffset);         // maybe catch a stale reference bug.
79            return 1;
80        }
81        lastElem = iElem;
82    }
83
84    return 0;
85}
86
87
88int         ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
89/* Replace an element in the list with a new element, in the same position. */
90{
91    void    *iElem, *lastElem;
92
93    if ( elemInList == NULL || newElem == NULL)
94        return 0;
95
96    for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset))
97    {
98        if ( iElem == elemInList)
99        {
100            ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset);
101            if ( lastElem)      // somewhere past the head
102            {
103                ASSIGNLINK( lastElem, newElem, pList->LinkOffset);
104            }
105            else                // at the head
106            {
107                pList->Head = newElem;
108            }
109            if ( pList->Tail == elemInList)
110                pList->Tail = newElem;
111            return 1;
112        }
113        lastElem = iElem;
114    }
115
116    return 0;
117}
118
119
120//		GenDoubleLinkedList		/////////////////////////////////////////////////////////
121
122void        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. */
125{
126    pList->Head = NULL;
127    pList->Tail = NULL;
128    pList->FwdLinkOffset = fwdLinkOffset;
129    pList->BackLinkOffset = backLinkOffset;
130}
131
132
133void            DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
134/* Add a linked list element to the head of the list. */
135{
136    void        *pNext;
137
138    pNext = pList->Head;
139
140    // fix up the forward links
141    ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset);
142    pList->Head = elem;
143
144    // fix up the backward links
145    if ( pNext) {
146        ASSIGNLINK( pNext, elem, pList->BackLinkOffset);
147    } else
148        pList->Tail = elem;
149    ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
150}
151
152
153void            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. */
156{
157    void        *pNext, *pPrev;
158
159    pNext = GETLINK( elem, pList->FwdLinkOffset);
160    pPrev = GETLINK( elem, pList->BackLinkOffset);
161
162    // fix up the forward links
163    if ( pPrev)
164        ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset);
165    else
166        pList->Head = pNext;
167
168    // fix up the backward links
169    if ( pNext)
170        ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset);
171    else
172        pList->Tail = pPrev;
173
174    ASSIGNLINK( elem, NULL, pList->FwdLinkOffset);
175    ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
176}
177
178
179//		GenLinkedOffsetList		/////////////////////////////////////////////////////
180
181// Extract the Next offset from element
182#define     GETOFFSET( e, o)    ( *(size_t*)((char*) (e) + (o)) )
183
184static void     AssignOffsetLink( void *elem, void *link, size_t linkOffset);
185
186
187static 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.
189{
190    GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0;
191}
192
193
194void        *GetHeadPtr( GenLinkedOffsetList *pList)
195/* Return a pointer to the head element of a list, or NULL if none. */
196{
197    return pList->Head ? ( (char*) (pList) + pList->Head) : NULL;
198}
199
200
201void        *GetTailPtr( GenLinkedOffsetList *pList)
202/* Return a pointer to the tail element of a list, or NULL if none. */
203{
204    return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL;
205}
206
207
208void        *GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
209/* Return the link pointer contained within element e for pList, or NULL if it is 0. */
210{
211    size_t nextOffset;
212
213    nextOffset = GETOFFSET( elem, pList->LinkOffset);
214
215    return nextOffset ? (char*) elem + nextOffset : NULL;
216}
217
218
219void        InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset)
220/* Initialize the block of memory pointed to by pList as a linked list. */
221{
222    pList->Head = 0;
223    pList->Tail = 0;
224    pList->LinkOffset = linkOffset;
225}
226
227
228void        OffsetAddToTail( GenLinkedOffsetList *pList, void *elem)
229/* Add a linked list element to the tail of the list. */
230{
231    if ( pList->Tail) {
232        AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset);
233    } else
234        pList->Head = (size_t) elem - (size_t) pList;
235    AssignOffsetLink( elem, NULL, pList->LinkOffset);
236
237    pList->Tail = (size_t) elem - (size_t) pList;
238}
239
240
241void        OffsetAddToHead( GenLinkedOffsetList *pList, void *elem)
242/* Add a linked list element to the head of the list. */
243{
244    AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset);
245    if ( pList->Tail == 0)
246        pList->Tail = (size_t) elem - (size_t) pList;
247
248    pList->Head = (size_t) elem - (size_t) pList;
249}
250
251
252int     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. */
255{
256    void    *iElem, *lastElem;
257
258    for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
259          iElem = GetOffsetLink( pList, iElem))
260    {
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;
267            }
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.
271            return 1;
272        }
273        lastElem = iElem;
274    }
275
276    return 0;
277}
278
279
280int         OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
281/* Replace an element in the list with a new element, in the same position. */
282{
283    void    *iElem, *lastElem;
284
285    if ( elemInList == NULL || newElem == NULL)
286        return 0;
287
288    for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
289          iElem = GetOffsetLink( pList, iElem))
290    {
291        if ( iElem == elemInList)
292        {
293            AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset);
294            if ( lastElem)      // somewhere past the head
295            {
296                AssignOffsetLink( lastElem, newElem, pList->LinkOffset);
297            }
298            else                // at the head
299            {
300                pList->Head = (size_t) newElem - (size_t) pList;
301            }
302            if ( GetTailPtr( pList) == elemInList)
303                pList->Tail = (size_t) newElem - (size_t) pList;
304            return 1;
305        }
306        lastElem = iElem;
307    }
308
309    return 0;
310}
311
312
313