dist/mDNSShared/GenLinkedList.c

/*
 * Copyright (c) 2003-2019 Apple Inc. All rights reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "GenLinkedList.h"


// Return the link pointer contained within element e at offset o.
#define     GETLINK( e, o)          ( *(void**)((char*) (e) + (o)) )

// Assign the link pointer l to element e at offset o.
#define     ASSIGNLINK( e, l, o)    ( *((void**)((char*) (e) + (o))) = (l))


//		GenLinkedList		/////////////////////////////////////////////////////////////

void        InitLinkedList( GenLinkedList *pList, size_t linkOffset)
/* Initialize the block of memory pointed to by pList as a linked list. */
{
    pList->Head = NULL;
    pList->Tail = NULL;
    pList->LinkOffset = linkOffset;
}


void        AddToTail( GenLinkedList *pList, void *elem)
/* Add a linked list element to the tail of the list. */
{
    if ( pList->Tail) {
        ASSIGNLINK( pList->Tail, elem, pList->LinkOffset);
    } else
        pList->Head = elem;
    ASSIGNLINK( elem, NULL, pList->LinkOffset);

    pList->Tail = elem;
}


void        AddToHead( GenLinkedList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
    ASSIGNLINK( elem, pList->Head, pList->LinkOffset);
    if ( pList->Tail == NULL)
        pList->Tail = elem;

    pList->Head = elem;
}


int     RemoveFromList( GenLinkedList *pList, void *elem)
/* Remove a linked list element from the list. Return 0 if it was not found. */
/* If the element is removed, its link will be set to NULL. */
{
    void    *iElem, *lastElem;

    for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset)) {
        if ( iElem == elem) {
            if ( lastElem) {        // somewhere past the head
                ASSIGNLINK( lastElem, GETLINK( elem, pList->LinkOffset), pList->LinkOffset);
            } else {                // at the head
                pList->Head = GETLINK( elem, pList->LinkOffset);
            }
            if ( pList->Tail == elem)
                pList->Tail = lastElem ? lastElem : NULL;
            ASSIGNLINK( elem, NULL, pList->LinkOffset);         // maybe catch a stale reference bug.
            return 1;
        }
        lastElem = iElem;
    }

    return 0;
}


int         ReplaceElem( GenLinkedList *pList, void *elemInList, void *newElem)
/* Replace an element in the list with a new element, in the same position. */
{
    void    *iElem, *lastElem;

    if ( elemInList == NULL || newElem == NULL)
        return 0;

    for ( iElem = pList->Head, lastElem = NULL; iElem; iElem = GETLINK( iElem, pList->LinkOffset))
    {
        if ( iElem == elemInList)
        {
            ASSIGNLINK( newElem, GETLINK( elemInList, pList->LinkOffset), pList->LinkOffset);
            if ( lastElem)      // somewhere past the head
            {
                ASSIGNLINK( lastElem, newElem, pList->LinkOffset);
            }
            else                // at the head
            {
                pList->Head = newElem;
            }
            if ( pList->Tail == elemInList)
                pList->Tail = newElem;
            return 1;
        }
        lastElem = iElem;
    }

    return 0;
}


//		GenDoubleLinkedList		/////////////////////////////////////////////////////////

void        InitDoubleLinkedList( GenDoubleLinkedList *pList, size_t fwdLinkOffset,
                                  size_t backLinkOffset)
/* Initialize the block of memory pointed to by pList as a double linked list. */
{
    pList->Head = NULL;
    pList->Tail = NULL;
    pList->FwdLinkOffset = fwdLinkOffset;
    pList->BackLinkOffset = backLinkOffset;
}


void            DLLAddToHead( GenDoubleLinkedList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
    void        *pNext;

    pNext = pList->Head;

    // fix up the forward links
    ASSIGNLINK( elem, pList->Head, pList->FwdLinkOffset);
    pList->Head = elem;

    // fix up the backward links
    if ( pNext) {
        ASSIGNLINK( pNext, elem, pList->BackLinkOffset);
    } else
        pList->Tail = elem;
    ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
}


void            DLLRemoveFromList( GenDoubleLinkedList *pList, void *elem)
/* Remove a linked list element from the list. */
/* When the element is removed, its link will be set to NULL. */
{
    void        *pNext, *pPrev;

    pNext = GETLINK( elem, pList->FwdLinkOffset);
    pPrev = GETLINK( elem, pList->BackLinkOffset);

    // fix up the forward links
    if ( pPrev)
        ASSIGNLINK( pPrev, pNext, pList->FwdLinkOffset);
    else
        pList->Head = pNext;

    // fix up the backward links
    if ( pNext)
        ASSIGNLINK( pNext, pPrev, pList->BackLinkOffset);
    else
        pList->Tail = pPrev;

    ASSIGNLINK( elem, NULL, pList->FwdLinkOffset);
    ASSIGNLINK( elem, NULL, pList->BackLinkOffset);
}


//		GenLinkedOffsetList		/////////////////////////////////////////////////////

// Extract the Next offset from element
#define     GETOFFSET( e, o)    ( *(size_t*)((char*) (e) + (o)) )

static void     AssignOffsetLink( void *elem, void *link, size_t linkOffset);


static void AssignOffsetLink( void *elem, void *link, size_t linkOffset)
// Assign link to elem as an offset from elem. Assign 0 to elem if link is NULL.
{
    GETOFFSET( elem, linkOffset) = link ? (size_t) link - (size_t) elem : 0;
}


void        *GetHeadPtr( GenLinkedOffsetList *pList)
/* Return a pointer to the head element of a list, or NULL if none. */
{
    return pList->Head ? ( (char*) (pList) + pList->Head) : NULL;
}


void        *GetTailPtr( GenLinkedOffsetList *pList)
/* Return a pointer to the tail element of a list, or NULL if none. */
{
    return pList->Tail ? ( (char*) (pList) + pList->Tail) : NULL;
}


void        *GetOffsetLink( GenLinkedOffsetList *pList, void *elem)
/* Return the link pointer contained within element e for pList, or NULL if it is 0. */
{
    size_t nextOffset;

    nextOffset = GETOFFSET( elem, pList->LinkOffset);

    return nextOffset ? (char*) elem + nextOffset : NULL;
}


void        InitLinkedOffsetList( GenLinkedOffsetList *pList, size_t linkOffset)
/* Initialize the block of memory pointed to by pList as a linked list. */
{
    pList->Head = 0;
    pList->Tail = 0;
    pList->LinkOffset = linkOffset;
}


void        OffsetAddToTail( GenLinkedOffsetList *pList, void *elem)
/* Add a linked list element to the tail of the list. */
{
    if ( pList->Tail) {
        AssignOffsetLink( GetTailPtr( pList), elem, pList->LinkOffset);
    } else
        pList->Head = (size_t) elem - (size_t) pList;
    AssignOffsetLink( elem, NULL, pList->LinkOffset);

    pList->Tail = (size_t) elem - (size_t) pList;
}


void        OffsetAddToHead( GenLinkedOffsetList *pList, void *elem)
/* Add a linked list element to the head of the list. */
{
    AssignOffsetLink( elem, GetHeadPtr( pList), pList->LinkOffset);
    if ( pList->Tail == 0)
        pList->Tail = (size_t) elem - (size_t) pList;

    pList->Head = (size_t) elem - (size_t) pList;
}


int     OffsetRemoveFromList( GenLinkedOffsetList *pList, void *elem)
/* Remove a linked list element from the list. Return 0 if it was not found. */
/* If the element is removed, its link will be set to NULL. */
{
    void    *iElem, *lastElem;

    if (elem == NULL) {
        return 0;
    }
    for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
          iElem = GetOffsetLink( pList, iElem))
    {
        if ( iElem == elem) {
            if ( lastElem) {        // somewhere past the head
                AssignOffsetLink( lastElem, GetOffsetLink( pList, elem), pList->LinkOffset);
            } else {                // at the head
                iElem = GetOffsetLink( pList, elem);
                pList->Head = iElem ? (size_t) iElem - (size_t) pList : 0;
            }
            if ( GetTailPtr( pList) == elem)
                pList->Tail = lastElem ? (size_t) lastElem - (size_t) pList : 0;
            AssignOffsetLink( elem, NULL, pList->LinkOffset);   // maybe catch a stale reference bug.
            return 1;
        }
        lastElem = iElem;
    }

    return 0;
}


int         OffsetReplaceElem( GenLinkedOffsetList *pList, void *elemInList, void *newElem)
/* Replace an element in the list with a new element, in the same position. */
{
    void    *iElem, *lastElem;

    if ( elemInList == NULL || newElem == NULL)
        return 0;

    for ( iElem = GetHeadPtr( pList), lastElem = NULL; iElem;
          iElem = GetOffsetLink( pList, iElem))
    {
        if ( iElem == elemInList)
        {
            AssignOffsetLink( newElem, GetOffsetLink( pList, elemInList), pList->LinkOffset);
            if ( lastElem)      // somewhere past the head
            {
                AssignOffsetLink( lastElem, newElem, pList->LinkOffset);
            }
            else                // at the head
            {
                pList->Head = (size_t) newElem - (size_t) pList;
            }
            if ( GetTailPtr( pList) == elemInList)
                pList->Tail = (size_t) newElem - (size_t) pList;
            return 1;
        }
        lastElem = iElem;
    }

    return 0;
}