LinkedList.c

Go to the documentation of this file.

/*******************************************************************************
 * Copyright (c) 2009, 2020 IBM Corp.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v2.0
 * and Eclipse Distribution License v1.0 which accompany this distribution. 
 *
 * The Eclipse Public License is available at 
 *    https://www.eclipse.org/legal/epl-2.0/
 * and the Eclipse Distribution License is available at 
 *   http://www.eclipse.org/org/documents/edl-v10.php.
 *
 * Contributors:
 *    Ian Craggs - initial API and implementation and/or initial documentation
 *    Ian Craggs - updates for the async client
 *******************************************************************************/

#include "LinkedList.h"

#include <stdlib.h>
#include <string.h>

#include "Heap.h"


static int ListUnlink(List* aList, void* content, int(*callback)(void*, void*), int freeContent);


void ListZero(List* newl)
{
        memset(newl, '\0', sizeof(List));
}


List* ListInitialize(void)
{
        List* newl = malloc(sizeof(List));
        if (newl)
                ListZero(newl);
        return newl;
}


void ListAppendNoMalloc(List* aList, void* content, ListElement* newel, size_t size)
{ /* for heap use */
        newel->content = content;
        newel->next = NULL;
        newel->prev = aList->last;
        if (aList->first == NULL)
                aList->first = newel;
        else
                aList->last->next = newel;
        aList->last = newel;
        ++(aList->count);
        aList->size += size;
}


ListElement* ListAppend(List* aList, void* content, size_t size)
{
        ListElement* newel = malloc(sizeof(ListElement));
        if (newel)
                ListAppendNoMalloc(aList, content, newel, size);
        return newel;
}


ListElement* ListInsert(List* aList, void* content, size_t size, ListElement* index)
{
        ListElement* newel = malloc(sizeof(ListElement));

        if (newel == NULL)
                return newel;
        if ( index == NULL )
                ListAppendNoMalloc(aList, content, newel, size);
        else
        {
                newel->content = content;
                newel->next = index;
                newel->prev = index->prev;

                index->prev = newel;
                if ( newel->prev != NULL )
                        newel->prev->next = newel;
                else
                        aList->first = newel;

                ++(aList->count);
                aList->size += size;
        }
        return newel;
}


ListElement* ListFind(List* aList, void* content)
{
        return ListFindItem(aList, content, NULL);
}


ListElement* ListFindItem(List* aList, void* content, int(*callback)(void*, void*))
{
        ListElement* rc = NULL;

        if (aList->current != NULL && ((callback == NULL && aList->current->content == content) ||
                   (callback != NULL && callback(aList->current->content, content))))
                rc = aList->current;
        else
        {
                ListElement* current = NULL;

                /* find the content */
                while (ListNextElement(aList, &current) != NULL)
                {
                        if (callback == NULL)
                        {
                                if (current->content == content)
                                {
                                        rc = current;
                                        break;
                                }
                        }
                        else
                        {
                                if (callback(current->content, content))
                                {
                                        rc = current;
                                        break;
                                }
                        }
                }
                if (rc != NULL)
                        aList->current = rc;
        }
        return rc;
}


static int ListUnlink(List* aList, void* content, int(*callback)(void*, void*), int freeContent)
{
        ListElement* next = NULL;
        ListElement* saved = aList->current;
        int saveddeleted = 0;

        if (!ListFindItem(aList, content, callback))
                return 0; /* false, did not remove item */

        if (aList->current->prev == NULL)
                /* so this is the first element, and we have to update the "first" pointer */
                aList->first = aList->current->next;
        else
                aList->current->prev->next = aList->current->next;

        if (aList->current->next == NULL)
                aList->last = aList->current->prev;
        else
                aList->current->next->prev = aList->current->prev;

        next = aList->current->next;
        if (freeContent)
    {
                free(aList->current->content);
                aList->current->content = NULL;
    }
        if (saved == aList->current)
                saveddeleted = 1;
        free(aList->current);
        if (saveddeleted)
                aList->current = next;
        else
                aList->current = saved;
        --(aList->count);
        return 1; /* successfully removed item */
}


int ListDetach(List* aList, void* content)
{
        return ListUnlink(aList, content, NULL, 0);
}


int ListRemove(List* aList, void* content)
{
        return ListUnlink(aList, content, NULL, 1);
}


void* ListDetachHead(List* aList)
{
        void *content = NULL;
        if (aList->count > 0)
        {
                ListElement* first = aList->first;
                if (aList->current == first)
                        aList->current = first->next;
                if (aList->last == first) /* i.e. no of items in list == 1 */
                        aList->last = NULL;
                content = first->content;
                aList->first = aList->first->next;
                if (aList->first)
                        aList->first->prev = NULL;
                free(first);
                --(aList->count);
        }
        return content;
}


int ListRemoveHead(List* aList)
{
        free(ListDetachHead(aList));
        return 0;
}


void* ListPopTail(List* aList)
{
        void* content = NULL;
        if (aList->count > 0)
        {
                ListElement* last = aList->last;
                if (aList->current == last)
                        aList->current = last->prev;
                if (aList->first == last) /* i.e. no of items in list == 1 */
                        aList->first = NULL;
                content = last->content;
                aList->last = aList->last->prev;
                if (aList->last)
                        aList->last->next = NULL;
                free(last);
                --(aList->count);
        }
        return content;
}


int ListDetachItem(List* aList, void* content, int(*callback)(void*, void*))
{ /* do not free the content */
        return ListUnlink(aList, content, callback, 0);
}


int ListRemoveItem(List* aList, void* content, int(*callback)(void*, void*))
{ /* remove from list and free the content */
        return ListUnlink(aList, content, callback, 1);
}


void ListEmpty(List* aList)
{
        while (aList->first != NULL)
        {
                ListElement* first = aList->first;
                if (first->content != NULL)
                {
                        free(first->content);
                        first->content = NULL;
                }
                aList->first = first->next;
                free(first);
        }
        aList->count = 0;
        aList->size = 0;
        aList->current = aList->first = aList->last = NULL;
}

void ListFree(List* aList)
{
        ListEmpty(aList);
        free(aList);
}


void ListFreeNoContent(List* aList)
{
        while (aList->first != NULL)
        {
                ListElement* first = aList->first;
                aList->first = first->next;
                free(first);
        }
        free(aList);
}


ListElement* ListNextElement(List* aList, ListElement** pos)
{
        return *pos = (*pos == NULL) ? aList->first : (*pos)->next;
}


ListElement* ListPrevElement(List* aList, ListElement** pos)
{
        return *pos = (*pos == NULL) ? aList->last : (*pos)->prev;
}


int intcompare(void* a, void* b)
{
        return *((int*)a) == *((int*)b);
}


int stringcompare(void* a, void* b)
{
        return strcmp((char*)a, (char*)b) == 0;
}


#if defined(UNIT_TESTS)


int main(int argc, char *argv[])
{
        int i, *ip, *todelete;
        ListElement* current = NULL;
        List* l = ListInitialize();
        printf("List initialized\n");

        for (i = 0; i < 10; i++)
        {
                ip = malloc(sizeof(int));
                *ip = i;
                ListAppend(l, (void*)ip, sizeof(int));
                if (i==5)
                        todelete = ip;
                printf("List element appended %d\n",  *((int*)(l->last->content)));
        }

        printf("List contents:\n");
        current = NULL;
        while (ListNextElement(l, &current) != NULL)
                printf("List element: %d\n", *((int*)(current->content)));

        printf("List contents in reverse order:\n");
        current = NULL;
        while (ListPrevElement(l, &current) != NULL)
                printf("List element: %d\n", *((int*)(current->content)));

        /* if ListFindItem(l, *ip, intcompare)->content */

        printf("List contents having deleted element %d:\n", *todelete);
        ListRemove(l, todelete);
        current = NULL;
        while (ListNextElement(l, &current) != NULL)
                printf("List element: %d\n", *((int*)(current->content)));

        i = 9;
        ListRemoveItem(l, &i, intcompare);
        printf("List contents having deleted another element, %d, size now %d:\n", i, l->size);
        current = NULL;
        while (ListNextElement(l, &current) != NULL)
                printf("List element: %d\n", *((int*)(current->content)));

        ListFree(l);
        printf("List freed\n");
}

#endif