linked_list.h File Reference

#include "string.h"
#include <core/mpx_supt.h>

Include dependency graph for linked_list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	s_ll_node
	struct for a node of the linked list More...
struct	s_ll
	struct definition for the linked list More...

Macros
#define	MAX_NUM_OF_LL_NODES   256
#define	VARIABLE_LL_LENGTH(LIST_LENGTH)

Typedefs
typedef struct s_ll	linkedList_t
typedef struct s_ll_node	node_t

Functions
void	initLinkedList (linkedList_t *list)
	initilize list and the optional array that backs the list 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 *	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...
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...
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...
void	setFreeFunction (linkedList_t *list, int(*newFreeFunc)(node_t *))
	sets the function whose job it is to free the node's memory More...
void	setInsertComparisonFunction (linkedList_t *list, int(*newCompFunc)(void *, void *))
	takes in a function pointer and sets the library shared comparison pointer 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	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 *	removeNode (node_t *nodeToRemove)
	will remove the node from the list. the list hierarchy will change to reflect the missing node. 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...
void	printList (linkedList_t *list)
	test function to show list functionality. uses const char* as test data More...
void	listTest ()
	test the linked_list class with const char* data and output to screen the results of the test More...

Variables
struct s_ll_node	__attribute__

Detailed Description

This module provides a generic linked list that can be array backed or use dynamic allocation

Definition in file linked_list.h.

Macro Definition Documentation

#define MAX_NUM_OF_LL_NODES   256

Definition at line 22 of file linked_list.h.

Referenced by initLinkedList(), and makeNewNode().

#define VARIABLE_LL_LENGTH

(

LIST_LENGTH

)

Value:

{ \
    typedef struct s_ll_##LIST_LENGTH##_t linkedList_##LIST_LENGTH##_t \
    struct s_ll_##LIST_LENGTH##_t \
    { \
        node_t head; \
        node_t tail; \
        int (*searchCompFunc)(void*, void*); \
        int (*comparisonFunc)(void*, void*); \
        int (*freeNodeFunc)(node_t *nodeToFree); \
        void (*printList)(void*); \
        size_t length; \
        unsigned int numNodesInUse; \
        node_t backingArray[LIST_LENGTH]; \
    }; \
}

defines a macro that will generate a new type that has a different array backing size, new type has the name linkedList_<list_length>_t

Definition at line 81 of file linked_list.h.

Typedef Documentation

typedef struct s_ll linkedList_t

Definition at line 30 of file linked_list.h.

typedef struct s_ll_node node_t

Definition at line 38 of file linked_list.h.

Function Documentation

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

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

Variable Documentation

struct s_ll_node __attribute__