147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* -*- Mode: C; tab-width: 4 -*- 247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * 347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * Copyright (c) 2003 Apple Computer, Inc. All rights reserved. 447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * 547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * Licensed under the Apache License, Version 2.0 (the "License"); 647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * you may not use this file except in compliance with the License. 747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * You may obtain a copy of the License at 847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * 947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * http://www.apache.org/licenses/LICENSE-2.0 1047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * 1147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * Unless required by applicable law or agreed to in writing, software 1247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * distributed under the License is distributed on an "AS IS" BASIS, 1347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * See the License for the specific language governing permissions and 1547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt * limitations under the License. 1647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 1747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt File: GenLinkedList.c 1847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 1947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt Contains: implementation of generic linked lists. 2047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 2147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt Version: 1.0 2247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt Tabs: 4 spaces 2347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt */ 2447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 2547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt#include "GenLinkedList.h" 2647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 2747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 2847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// Return the link pointer contained within element e at offset o. 2947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt#define GETLINK( e, o) ( *(void**)((char*) (e) + (o)) ) 3047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 3147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// Assign the link pointer l to element e at offset o. 3247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt#define ASSIGNLINK( e, l, o) ( *((void**)((char*) (e) + (o))) = (l)) 3347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 3447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 3547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// GenLinkedList ///////////////////////////////////////////////////////////// 3647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 3747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid InitLinkedList( GenLinkedList *pList, size_t linkOffset) 3847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Initialize the block of memory pointed to by pList as a linked list. */ 3947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 4047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = NULL; 4147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = NULL; 4247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->LinkOffset = linkOffset; 4347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 4447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 4547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 4647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid AddToTail( GenLinkedList *pList, void *elem) 4747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Add a linked list element to the tail of the list. */ 4847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 4947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail) { 5047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( pList->Tail, elem, pList->LinkOffset); 5147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } else 5247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = elem; 5347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, NULL, pList->LinkOffset); 5447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 5547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = elem; 5647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 5747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 5847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 5947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid AddToHead( GenLinkedList *pList, void *elem) 6047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Add a linked list element to the head of the list. */ 6147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 6247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, pList->Head, pList->LinkOffset); 6347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail == NULL) 6447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = elem; 6547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 6647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = elem; 6747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 6847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 6947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 7047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltint RemoveFromList( GenLinkedList *pList, void *elem) 7147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Remove a linked list element from the list. Return 0 if it was not found. */ 7247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* If the element is removed, its link will be set to NULL. */ 7347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 7447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *iElem, *lastElem; 7547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 7647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) { 7747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( iElem == elem) { 7847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( lastElem) { // somewhere past the head 7947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset); 8047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } else { // at the head 8147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = GETLINK( elem, pList->LinkOffset); 8247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 8347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail == elem) 8447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = lastElem ? lastElem : NULL; 8547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug. 8647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 1; 8747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 8847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt lastElem = iElem; 8947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 9047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 9147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 9247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 9347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 9447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 9547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltint ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem) 9647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Replace an element in the list with a new element, in the same position. */ 9747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 9847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *iElem, *lastElem; 9947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 10047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( elemInList == NULL || newElem == NULL) 10147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 10247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 10347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) 10447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 10547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( iElem == elemInList) 10647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 10747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset); 10847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( lastElem) // somewhere past the head 10947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 11047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( lastElem, newElem, pList->LinkOffset); 11147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 11247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt else // at the head 11347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 11447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = newElem; 11547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 11647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail == elemInList) 11747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = newElem; 11847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 1; 11947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 12047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt lastElem = iElem; 12147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 12247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 12347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 12447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 12547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 12647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 12747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// GenDoubleLinkedList ///////////////////////////////////////////////////////// 12847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 12947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset, 13047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt size_t backLinkOffset) 13147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Initialize the block of memory pointed to by pList as a double linked list. */ 13247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 13347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = NULL; 13447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = NULL; 13547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->FwdLinkOffset = fwdLinkOffset; 13647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->BackLinkOffset = backLinkOffset; 13747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 13847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 13947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 14047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid DLLAddToHead( GenDoubleLinkedList *pList, void *elem) 14147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Add a linked list element to the head of the list. */ 14247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 14347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *pNext; 14447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 14547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pNext = pList->Head; 14647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 14747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt // fix up the forward links 14847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset); 14947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = elem; 15047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 15147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt // fix up the backward links 15247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pNext) { 15347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( pNext, elem, pList->BackLinkOffset); 15447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } else 15547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = elem; 15647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, NULL, pList->BackLinkOffset); 15747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 15847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 15947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 16047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem) 16147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Remove a linked list element from the list. */ 16247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* When the element is removed, its link will be set to NULL. */ 16347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 16447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *pNext, *pPrev; 16547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 16647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pNext = GETLINK( elem, pList->FwdLinkOffset); 16747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pPrev = GETLINK( elem, pList->BackLinkOffset); 16847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 16947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt // fix up the forward links 17047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pPrev) 17147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset); 17247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt else 17347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = pNext; 17447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 17547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt // fix up the backward links 17647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pNext) 17747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset); 17847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt else 17947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = pPrev; 18047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 18147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, NULL, pList->FwdLinkOffset); 18247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt ASSIGNLINK( elem, NULL, pList->BackLinkOffset); 18347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 18447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 18547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 18647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// GenLinkedOffsetList ///////////////////////////////////////////////////// 18747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 18847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// Extract the Next offset from element 18947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt#define GETOFFSET( e, o) ( *(size_t*)((char*) (e) + (o)) ) 19047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 19147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltstatic void AssignOffsetLink( void *elem, void *link, size_t linkOffset); 19247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 19347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 19447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltstatic void AssignOffsetLink( void *elem, void *link, size_t linkOffset) 19547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt// Assign link to elem as an offset from elem. Assign 0 to elem if link is NULL. 19647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 19747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0; 19847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 19947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 20047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 20147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *GetHeadPtr( GenLinkedOffsetList *pList) 20247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Return a pointer to the head element of a list, or NULL if none. */ 20347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 20447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return pList->Head ? ( (char*) (pList) + pList->Head) : NULL; 20547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 20647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 20747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 20847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *GetTailPtr( GenLinkedOffsetList *pList) 20947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Return a pointer to the tail element of a list, or NULL if none. */ 21047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 21147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL; 21247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 21347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 21447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 21547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *GetOffsetLink( GenLinkedOffsetList *pList, void *elem) 21647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Return the link pointer contained within element e for pList, or NULL if it is 0. */ 21747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 21847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltsize_t nextOffset; 21947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 22047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt nextOffset = GETOFFSET( elem, pList->LinkOffset); 22147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 22247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return nextOffset ? (char*) elem + nextOffset : NULL; 22347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 22447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 22547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 22647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset) 22747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Initialize the block of memory pointed to by pList as a linked list. */ 22847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 22947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = 0; 23047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = 0; 23147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->LinkOffset = linkOffset; 23247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 23347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 23447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 23547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid OffsetAddToTail( GenLinkedOffsetList *pList, void *elem) 23647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Add a linked list element to the tail of the list. */ 23747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 23847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail) { 23947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset); 24047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } else 24147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = (size_t) elem - (size_t) pList; 24247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( elem, NULL, pList->LinkOffset); 24347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 24447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = (size_t) elem - (size_t) pList; 24547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 24647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 24747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 24847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid OffsetAddToHead( GenLinkedOffsetList *pList, void *elem) 24947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Add a linked list element to the head of the list. */ 25047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 25147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset); 25247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( pList->Tail == 0) 25347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = (size_t) elem - (size_t) pList; 25447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 25547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = (size_t) elem - (size_t) pList; 25647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 25747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 25847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 25947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltint OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem) 26047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Remove a linked list element from the list. Return 0 if it was not found. */ 26147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* If the element is removed, its link will be set to NULL. */ 26247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 26347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *iElem, *lastElem; 26447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 26547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem; 26647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt iElem = GetOffsetLink( pList, iElem)) 26747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 26847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( iElem == elem) { 26947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( lastElem) { // somewhere past the head 27047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset); 27147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } else { // at the head 27247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt iElem = GetOffsetLink( pList, elem); 27347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0; 27447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 27547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( GetTailPtr( pList) == elem) 27647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0; 27747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( elem, NULL, pList->LinkOffset); // maybe catch a stale reference bug. 27847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 1; 27947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 28047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt lastElem = iElem; 28147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 28247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 28347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 28447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 28547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 28647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 28747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltint OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem) 28847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt/* Replace an element in the list with a new element, in the same position. */ 28947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt{ 29047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwaltvoid *iElem, *lastElem; 29147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 29247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( elemInList == NULL || newElem == NULL) 29347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 29447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 29547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem; 29647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt iElem = GetOffsetLink( pList, iElem)) 29747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 29847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( iElem == elemInList) 29947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 30047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset); 30147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( lastElem) // somewhere past the head 30247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 30347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt AssignOffsetLink( lastElem, newElem, pList->LinkOffset); 30447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 30547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt else // at the head 30647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt { 30747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Head = (size_t) newElem - (size_t) pList; 30847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 30947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt if ( GetTailPtr( pList) == elemInList) 31047e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt pList->Tail = (size_t) newElem - (size_t) pList; 31147e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 1; 31247e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 31347e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt lastElem = iElem; 31447e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt } 31547e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 31647e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt return 0; 31747e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt} 31847e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 31947e4cebad7397422144bb03a21f3f7682c062c4aRobert Greenwalt 320