linked_list.c File Reference

#include "linked_list.h"

Include dependency graph for linked_list.c:

Go to the source code of this file.

Functions
void	initLinkedList (linkedList_t *list)
	initilize list and the optional array that backs the list More...
node_t *	makeNewNode (linkedList_t *list, void *data)
	get new node, allocate a new node or find an unused node from the list's pool More...
void	setInsertComparisonFunction (linkedList_t *list, int(*newCompFunc)(void *, void *))
	takes in a function pointer and sets the library shared comparison pointer More...
void	setFreeFunction (linkedList_t *list, int(*newFreeFunc)(node_t *))
	sets the function whose job it is to free the node's memory More...
void	setSearchComparisonFunction (linkedList_t *list, int(*newSearchFunc)(void *, void *))
	sets the function whose job it is to compare the input data with the data in the list. the first void parameter will always be the data contained in the list, the second will be the data passed to the search function. More...
node_t *	insertAfterNode (node_t *preceedingNode, node_t *newNode)
	insert a node into the parent list of the preceedingNode after preceedingNode More...
node_t *	insertBeforeNode (node_t *nodeToFollow, node_t *newNode)
	insert a node into the parent list of the nodeToFollow before nodeToFollow More...
node_t *	removeNode (node_t *nodeToRemove)
	will remove the node from the list. the list hierarchy will change to reflect the missing node. More...
node_t *	moveNodeToNewList (node_t *nodeToMove, linkedList_t *newList)
	If a node needs to move lists and lists are array backed, instead of just moving preceeding and suceeding pointers of the node, the node actaully needs to move backing arrays so one list's nodes are not the only ones being consumed. The equivalent process will be to execute the parent list's removeNode funcion, execute the makeNewNode function on the newList, copy all structure members to the new node, and return the new node. The list of nodeToMove freeNodeFunc will be called with nodeToMov as the argument. If the lists are not array backed, the function simply removes the node from its containing list and calls insertNode on the new list. More...
node_t *	searchList (linkedList_t *listToSearch, void *data)
	goes through the list using the list's comparison function to find the node which matches the data. if the search function is undefined for this list, the function returns null immedietly. More...
node_t *	insertNode (linkedList_t *list, node_t *newNode)
	Will insert the node into the list. This function will attempt to call the list's insert comparison function if defined. The function will insert the new node into the list after this function returns > 0. If the insert comparison function is not defined for this list, the inserting function will placed the new node at the end of the list before the tail. More...
void	setPrintFunction (linkedList_t *list, void(*newPrintFunc)(void *))
	sets the function whose job it is to print the list to the screen. More...
void	printList (linkedList_t *list)
	test function to show list functionality. uses const char* as test data More...
int	compFunction (void *nodeData1, void *nodeData2)
int	searchcompFunction (void *nodeData1, void *nodeData2)
void	testPrintFunc (void *nodeData)
void	listTest ()
	test the linked_list class with const char* data and output to screen the results of the test More...

Function Documentation

int compFunction	(	void *	nodeData1,
		void *	nodeData2
	)

Definition at line 231 of file linked_list.c.

Referenced by listTest().

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

void initLinkedList

(

linkedList_t *

list

)

initilize list and the optional array that backs the list

Parameters

list	pointer to list

Definition at line 3 of file linked_list.c.

References MAX_NUM_OF_LL_NODES.

Referenced by initHeap(), initPCBQueues(), and listTest().

{
#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* insertAfterNode	(	node_t *	preceedingNode,
		node_t *	newNode
	)

insert a node into the parent list of the preceedingNode after preceedingNode

Parameters

preceedingNode	node to insert the new node afterwards
newNode	the new node to insert. if the list is array backed, the newNode will be copied to the list's node pool if it currently does not reside there

Returns

pointer to node inserted in the parent list of preceedingNode, null if insertion failed

Definition at line 78 of file linked_list.c.

References moveNodeToNewList().

{
#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
	)

insert a node into the parent list of the nodeToFollow before nodeToFollow

Parameters

nodeToFollow	node to insert the newNode before
newNode	the new node to insert. if the list is array backed, the newNode will be copied to the list's node pool if it currently does not reside there

Returns

pointer to node inserted in the parent list of nodeToFollow, null if insertion failed

Definition at line 99 of file linked_list.c.

References moveNodeToNewList().

Referenced by insertNode().

{
#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* insertNode	(	linkedList_t *	list,
		node_t *	newNode
	)

Will insert the node into the list. This function will attempt to call the list's insert comparison function if defined. The function will insert the new node into the list after this function returns > 0. If the insert comparison function is not defined for this list, the inserting function will placed the new node at the end of the list before the tail.

Parameters

list	list to place the node
newNode	the new node to insert. if the list is array backed, the newNode will be copied to the list's node pool if it currently does not reside there

Returns

pointer to the node in the new list, or null if inserting failed.

Definition at line 173 of file linked_list.c.

References insertBeforeNode(), and moveNodeToNewList().

Referenced by insertMCBIntoList(), insertPCB(), listTest(), and moveNodeToNewList().

{
    //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 listTest

(

)

test the linked_list class with const char* data and output to screen the results of the test

Definition at line 250 of file linked_list.c.

References compFunction(), initLinkedList(), insertNode(), makeNewNode(), printf, printList(), searchcompFunction(), searchList(), setInsertComparisonFunction(), setPrintFunction(), setSearchComparisonFunction(), and testPrintFunc().

{
    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);
}

node_t* makeNewNode	(	linkedList_t *	list,
		void *	data
	)

get new node, allocate a new node or find an unused node from the list's pool

Parameters

list	to find an unused node from. This argument is ignored if the list is dynamically allocated
data	pointer to the data the new node should contain, the pointer must be valid obviously

Returns

pointer to new node, null if no new node could be found or created

Definition at line 37 of file linked_list.c.

References MAX_NUM_OF_LL_NODES, and sys_alloc_mem().

Referenced by allocatePCB(), listTest(), and moveNodeToNewList().

{
#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
}

node_t* moveNodeToNewList	(	node_t *	nodeToMove,
		linkedList_t *	newList
	)

If a node needs to move lists and lists are array backed, instead of just moving preceeding and suceeding pointers of the node, the node actaully needs to move backing arrays so one list's nodes are not the only ones being consumed. The equivalent process will be to execute the parent list's removeNode funcion, execute the makeNewNode function on the newList, copy all structure members to the new node, and return the new node. The list of nodeToMove freeNodeFunc will be called with nodeToMov as the argument. If the lists are not array backed, the function simply removes the node from its containing list and calls insertNode on the new list.

Parameters

nodeToMove	the node to move, this pointer is no longer guarenteed to be valid. Stop using this pointer,
newList	the list to move the node to, this will be the node's new parent list

Returns

the pointer of param nodeToMove will no longer be valid, the pointer to the node in the new list will be returned on sucess. Null on failure and nodeToMove will remain valid

Definition at line 132 of file linked_list.c.

References insertNode(), makeNewNode(), and removeNode().

Referenced by insertAfterNode(), insertBeforeNode(), and insertNode().

{
#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
}

void printList

(

linkedList_t *

list

)

test function to show list functionality. uses const char* as test data

Parameters

list	list to print the nodes of

Definition at line 212 of file linked_list.c.

References printf.

Referenced by heapTest(), listTest(), mcbFunc(), pcbTest(), printAlloc(), printFree(), showAllProcesses(), showBlockedProcesses(), and showReadyProcesses().

{
    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"," ");
    }
}

node_t* removeNode

(

node_t *

nodeToRemove

)

will remove the node from the list. the list hierarchy will change to reflect the missing node.

Parameters

nodeToRemove

pointer to the node to remove

Returns

pointer to the removed node

Definition at line 120 of file linked_list.c.

Referenced by allocateMemFromHeap(), freeHeapMem(), moveNodeToNewList(), reclaimFreeMem(), and removePCB().

{
    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;
}

int searchcompFunction	(	void *	nodeData1,
		void *	nodeData2
	)

Definition at line 238 of file linked_list.c.

References strcmp().

Referenced by listTest().

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

node_t* searchList	(	linkedList_t *	listToSearch,
		void *	data
	)

goes through the list using the list's comparison function to find the node which matches the data. if the search function is undefined for this list, the function returns null immedietly.

Parameters

listToSearch	the list to search
data	valid pointer to data that can be dereferenced. this pointer will be the second argument to the list's search comparison function

Returns

null if not found, else pointer to the node that matches.

Definition at line 154 of file linked_list.c.

Referenced by findPCB(), freeHeapMem(), and listTest().

{
    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;
}

void setFreeFunction	(	linkedList_t *	list,
		int(*)(node_t *)	newFreeFunc
	)

sets the function whose job it is to free the node's memory

Parameters

list	the list to set the function pointer for
newFreeFunc	the job of this function should be to free the memory with the node once it the list no longer needs it. This can be literally through free() or by other means.

Definition at line 68 of file linked_list.c.

{
    list->freeNodeFunc = newFreeFunc;
}

void setInsertComparisonFunction	(	linkedList_t *	list,
		int(*)(void *, void *)	newCompFunc
	)

takes in a function pointer and sets the library shared comparison pointer

Parameters

list

the list to set the function pointer for

newCompFunc

pointer to function whose job is to define the comparison of the data stored in the node this function should return 0 if the comparison succeeds. The function should return < 0 if the data to compare comes after the data in the node. The function should return > 0 if the data to compare comes before the data in the node. The first void argument is guarenteed to be the data from the list to compare against. The second void argument is the data in the node passed to the insertNode function

Definition at line 63 of file linked_list.c.

Referenced by initHeap(), and listTest().

{
    list->insertCompFunc = newCompFunc;
}

void setSearchComparisonFunction	(	linkedList_t *	list,
		int(*)(void *, void *)	newSearchFunc
	)

sets the function whose job it is to compare the input data with the data in the list. the first void parameter will always be the data contained in the list, the second will be the data passed to the search function.

Parameters

list

to set the search function for

newSeachFunc

pointer to function whose job is to define the comparison of the data stored in the node this function should return 0 if the comparison succeeds. The function should return < 0 if the data to compare comes after the data in the node. The function should return > 0 if the data to compare comes before the data in the node. The first void argument is guarenteed to be the data from the list to compare against. The second void argument is the data passed to the searchList function

Definition at line 73 of file linked_list.c.

Referenced by initHeap(), initPCBQueues(), and listTest().

{
    list->searchCompFunc = newSearchFunc;
}

void testPrintFunc

(

void *

nodeData

)

Definition at line 245 of file linked_list.c.

References printf.

Referenced by listTest().

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