linked_list.c

Go to the documentation of this file.

#include "linked_list.h"

void initLinkedList(linkedList_t *list)
{
#ifdef LL_IS_ARRAY_BACKED
    int i;
    for(i=0; i < MAX_NUM_OF_LL_NODES; i++)
    {
        list->backingArray[i].data=0;
        list->backingArray[i].inUse=0;
        list->backingArray[i].next=0;
        list->backingArray[i].prev=0;
        list->backingArray[i].parentList = list;
    }

    list->head.parentList = list;
    list->head.inUse=1;

    list->tail.parentList = list;
    list->tail.inUse=1;
#endif

    list->head.data=0;
    list->head.next =
        list->head.prev = &list->tail;

    list->tail.data=0;
    list->tail.next =
        list->tail.prev = &list->head;

    list->length = 0;
    list->insertCompFunc = 0;
    list->freeNodeFunc = 0;
    list->searchCompFunc = 0;
}

node_t * makeNewNode(linkedList_t *list, void *data)
{
#ifdef LL_IS_ARRAY_BACKED
    int i;
    for(i=0; i < MAX_NUM_OF_LL_NODES; i++)
    {
        if(!list->backingArray[i].inUse)
        {
            list->backingArray[i].inUse = 1;
            list->numNodesInUse++;
            list->backingArray[i].data = data;
            return &(list->backingArray[i]);
        }
    }
    return 0;
#else
    (void)list;
    node_t * newNode = sys_alloc_mem(sizeof(node_t));
    newNode->data = data;
    newNode->next=0;
    newNode->prev=0;
    return newNode;

#endif
}

void setInsertComparisonFunction(linkedList_t* list, int (*newCompFunc)(void *, void *))
{
    list->insertCompFunc = newCompFunc;
}

void setFreeFunction(linkedList_t *list, int (*newFreeFunc)(node_t *))
{
    list->freeNodeFunc = newFreeFunc;
}

void setSearchComparisonFunction(linkedList_t *list, int (*newSearchFunc)(void*, void*))
{
    list->searchCompFunc = newSearchFunc;
}

node_t *insertAfterNode(node_t * preceedingNode, node_t *newNode)
{
#ifdef LL_IS_ARRAY_BACKED
    if(preceedingNode->parentList != newNode->parentList)
    {
        //if the node to insert is not apart of the list to insert after, the function moveNodeToNewList makes a
            //new node in the parent list of the preceedingNode and recursively calls this function with the newly moved node
        return insertAfterNode(preceedingNode,
                            moveNodeToNewList(newNode, preceedingNode->parentList));
    }
#endif

    newNode->next = preceedingNode->next;
    newNode->prev = preceedingNode;

    newNode->next->prev = newNode;
    newNode->prev->next = newNode;

    return newNode;
}

node_t *insertBeforeNode(node_t *nodeToFollow, node_t *  newNode)
{
#ifdef LL_IS_ARRAY_BACKED
    if(nodeToFollow->parentList != newNode->parentList)
    {
        //if the node to insert is not apart of the list to insert after, the function moveNodeToNewList makes a
            //new node in the parent list of the preceedingNode and recursively calls this function with the newly moved node
        return insertBeforeNode(nodeToFollow,
                            moveNodeToNewList(newNode, nodeToFollow->parentList));
    }
#endif

    newNode->next = nodeToFollow;
    newNode->prev = nodeToFollow->prev;

    newNode->next->prev = newNode;
    newNode->prev->next = newNode;

    return newNode;
}

node_t *removeNode(node_t * nodeToRemove)
{
    if(nodeToRemove)
    {
        if(nodeToRemove->prev){nodeToRemove->prev->next = nodeToRemove->next;}
        if(nodeToRemove->next){nodeToRemove->next->prev = nodeToRemove->prev;}
        nodeToRemove->next = 0;
        nodeToRemove->prev = 0;
    }
    return nodeToRemove;
}

node_t *moveNodeToNewList(node_t *  nodeToMove, linkedList_t *newList)
{
#ifdef LL_IS_ARRAY_BACKED
    node_t *  newNodeInList = makeNewNode(newList, nodeToMove->data);
    if(!newNodeInList)
    {
        return 0;
    }

    removeNode(nodeToMove);

    if(nodeToMove->parentList->freeNodeFunc)
    {
        (*(nodeToMove->parentList->freeNodeFunc))(nodeToMove);
    }
    return newNodeInList;
#else
    node_t* removedNode = removeNode(nodeToMove);
    return insertNode(newList, removedNode);
#endif
}

node_t *  searchList(linkedList_t *listToSearch, void *data)
{
    int (*compFunctCpy)(void*,void*)  = (listToSearch->searchCompFunc) ?
                                            listToSearch->searchCompFunc :
                                                listToSearch->insertCompFunc;
    if(compFunctCpy)
    {
        node_t * itNode = listToSearch->head.next;
        for(; itNode != &(listToSearch->tail); itNode = itNode->next)
        {
            if(!(*(compFunctCpy))(itNode->data, data))
            {
                return itNode;
            }
        }
    }
    return 0;
}

node_t *insertNode(linkedList_t *list, node_t *newNode)
{
    //if newNode is not valid, do not insert any node
    if(!newNode)
    {
        return 0;
    }

#ifdef LL_IS_ARRAY_BACKED
    if(newNode->parentList != list)
    {
        //if the node to insert is not apart of the list to insert after, the function moveNodeToNewList makes a
            //new node in the parent list of the preceedingNode and recursively calls this function with the newly moved node
        return insertNode(list, moveNodeToNewList(newNode, list));
    }
#endif

    if(list->insertCompFunc)
    {
        node_t * itNode = list->head.next;
        for(; itNode != &(list->tail); itNode = itNode->next)
        {
            int result = ((*(list->insertCompFunc))(itNode->data, newNode->data));
            if(result > 0)
            {
                list->length++;
                return insertBeforeNode(itNode, newNode);
            }
        }
    }
    list->length++;
    return insertBeforeNode(&(list->tail), newNode);
}

void setPrintFunction(linkedList_t *list, void (*newPrintFunc)(void *))
{
    list->printNodeFunc = newPrintFunc;
}

void printList(linkedList_t *list)
{
    if(list->printNodeFunc)
    {
        node_t * itNode = list->head.next;
        if(itNode == &(list->tail))
        {
            printf("%s","<List is Empty>\r\n");
        }
        for(; itNode != &(list->tail); itNode = itNode->next)
        {
            list->printNodeFunc(itNode->data);
        }
    }else
    {
        printf("No Search Function provided for List!%s\r\n"," ");
    }
}

int compFunction(void *nodeData1, void* nodeData2)
{
    //return strcmp((const char*)(nodeData1), (const char*)(nodeData2));
    (void)nodeData1; (void)nodeData2;
    return -1;
}

int searchcompFunction(void *nodeData1, void* nodeData2)
{
    return strcmp((const char*)(nodeData1), (const char*)(nodeData2));
    //(void)nodeData1; (void)nodeData2;
    //return -1;
}

void testPrintFunc(void* nodeData)
{
    printf("List Test Print: data is string: %s\r\n", (const char*)nodeData);
}

void listTest()
{
    linkedList_t list1;
    linkedList_t list2;

    initLinkedList(&list1);
    initLinkedList(&list2);

    setInsertComparisonFunction(&list1, &compFunction);
    setSearchComparisonFunction(&list1, &searchcompFunction);
    setPrintFunction(&list1, &testPrintFunc);

    insertNode(&list1, makeNewNode(&list2, (void*)"test3"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test1"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test5"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test2"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test7"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test4"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test8"));
    insertNode(&list1, makeNewNode(&list2, (void*)"test3"));


   // node_t * nodeFound = searchList(&list1, (void*)"test3");

    node_t * nodeFound = searchList(&list1, (void*)"test5");
    printf("looking for node whose data is: %s\r\nsearch return: %d\r\n", "test5", (int)nodeFound);

    if(nodeFound)
    {
        printf("found node:: data string = %s\r\n", (const char*)nodeFound->data);
    }

    printList(&list1);
}