Please read this assignment carefully and follow the instructions EXACTLY. Program must be in C 

Submission:

 If a part asks for a program, you must provide a Makefile. Please refer to lab1 for the requirements for Makefiles. The TAs will make no attempt to compile your program other than typing "make". 

 Please include a README.txt in the top level directory. Checking memory errors with valgrind 

 You will be heavily penalized if your program contains memory errors. Memory errors include (among other things) failure to call free() on the memory you obtained through malloc(), accessing past array bounds, dereferencing uninitialized pointers, etc. 

 You can use a debugging tool called "valgrind" to check your program: 

 valgrind --leak-check=yes ./your_executable 

 It will tell you if your program has any memory error. See "The Valgrind Quick Start Guide" at http://valgrind.org/docs/manual/quick-start.html for more info. 

 You must include the output of the valgrind run for EACH PART in your README.txt. In addition, TAs will run valgrind on your program when grading. 

Part 1: Implement a singly linked list -------------------------------------- 

(a)

Your job is to implement a generic singly linked list that can hold any data type. The interface has been specified and provided to you in a header file called mylist.h. So your job is to write mylist.c that implements each function whose prototype is included in mylist.h. Specifically, you are asked to write the following functions: 

 struct Node *addFront(struct List *list, void *data) void traverseList(struct List *list, void (*f)(void *)) void flipSignDouble(void *data) int compareDouble(const void *data1, const void *data2) 

 struct Node *findNode(struct List *list, const void *dataSought, int (*compar)(const void *, const void *)) 

 void *popFront(struct List *list) 

 void removeAllNodes(struct List *list) 

 struct Node *addAfter(struct List *list, struct Node *prevNode, void *data) 

 void reverseList(struct List *list) 

The header file contains detailed comments specifying the behavior of the functions. Your implementation should follow the specified behavior. 

In addition, I provide you with a test driver program, mylist-test.c, which produces the following output for a correctly implemented linked list: 

 testing addFront(): 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 testing flipSignDouble(): -9.0 -8.0 -7.0 -6.0 -5.0 -4.0 -3.0 -2.0 -1.0 testing flipSignDouble() again: 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 testing findNode(): OK popped 9.0, the rest is: [ 8.0 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 8.0, the rest is: [ 7.0 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 7.0, the rest is: [ 6.0 5.0 4.0 3.0 2.0 1.0 ] popped 6.0, the rest is: [ 5.0 4.0 3.0 2.0 1.0 ] popped 5.0, the rest is: [ 4.0 3.0 2.0 1.0 ] popped 4.0, the rest is: [ 3.0 2.0 1.0 ] popped 3.0, the rest is: [ 2.0 1.0 ] popped 2.0, the rest is: [ 1.0 ] popped 1.0, the rest is: [ ] testing addAfter(): 1.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0 popped 1.0, and reversed the rest: [ 9.0 8.0 7.0 6.0 5.0 4.0 3.0 2.0 ] popped 9.0, and reversed the rest: [ 2.0 3.0 4.0 5.0 6.0 7.0 8.0 ] popped 2.0, and reversed the rest: [ 8.0 7.0 6.0 5.0 4.0 3.0 ] popped 8.0, and reversed the rest: [ 3.0 4.0 5.0 6.0 7.0 ] popped 3.0, and reversed the rest: [ 7.0 6.0 5.0 4.0 ] popped 7.0, and reversed the rest: [ 4.0 5.0 6.0 ] popped 4.0, and reversed the rest: [ 6.0 5.0 ] popped 6.0, and reversed the rest: [ 5.0 ] popped 5.0, and reversed the rest: [ ] 

This model output is also provided to you in mylist-test-output.txt. 

I recommend you implement the functions in the order listed, and test each function as you go. You can start by commenting out the code in main() of mylist-test.c and uncomment the code one block at a time to test each list function you implemented, comparing your output with that of mylist-test-output.txt. The diff UNIX command may come in handy. 

Note that mylist-test.c may not test every single function. You are still responsible for correct implementations of all functions. 

Dont forget to run valgrind at each step to make sure you dont have a memory bug, and dont forget to include the valgrind output in your README.txt when youre done. 

(b)

Modify your Makefile to produce a static library named libmylist.a that contains your linked list object files. Your test program, mylist-test, must link with the library file, not the mylist.o file. 

You can learn how to make a library file here: http://randu.org/tutorials/c/libraries.php 

Note that we are making a static library, not a shared library. 

Part 2: Using the linked list library for strings ------------------------------------------------- 

In this part, you will use the linked list library that you implemented in part1 to write a program called revecho that simply prints out the command line arguments in reverse order. In addition, it will look for the word "dude" (case-sensitive) among the command line arguments you passed, and report whether its there or not. 

For example,

 ./revecho hello world dude dude world hello 

 dude found Another example: 

 ./revecho hello world friend friend world hello 

 dude not found 

Here are the program requirements and hints: 

- Your program should simply put all the argument strings into a list WITHOUT duplicating them. There should be no malloc in your code. Just call addFront() for all strings. 

- To print out the strings, you can either use traverseList() or you can traverse the list by yourself by following the next pointers, printing out each string. 

- Dont forget to initialize the list and remove all nodes at the end to prevent memory errors or leaks. Make sure you include valgrind output in your README.txt. 

- To find dude, you can either traverse the list yourself, or use findNode(). Either way, strcmp() function will come in handy. If you want to pass strcmp to findNode(), you will have to cast it to 

 the correct function pointer type because the signature of strcmp() is slightly different from the signature of compar argument of findNode(). K&R2 section 5.11 has an example of casting a function pointer. 

- You must use libmylist.a that you built in part1 from the part1 directory. Do not copy any files from part1 directory to part2 directory. The part2 directory should contain only 2 files: Makefile and revecho.c. (You will have intermediate files while youre testing obviously.) Your Makefile must reference "../part1" as the directory to look for mylist.h and libmylist.a. "-I" option and "-L" option do the trick, respectively. (The gcc man page tells you about the options.) If you modeled your Makefile after the lab1 solution as I recommended, you can put the options into INCLUDES and LDFLAGS, respectively. 

 The directory that contains mylist.h and libmylist.a should be expressed in a relative path from the directory containing the part2 Makefile. The path should NOT include "~" anywhere. The path should NOT begin with "/". If you do not follow this instruction, your code will fail to build when the graders try to build your code in their home directories. These requirements apply to all future labs that uses the mylist library. 

 Note that all you need to use the linked list is the header file and the library file (that are residing somewhere else). This is in fact what it means to use a 3rd party library in your code. 

#ifndef _MYLIST_H_

#define _MYLIST_H_

/*

* A node in a linked list.

*/

struct Node {

void *data;

struct Node *next;

};

/*

* A linked list.

* 'head' points to the first node in the list.

*/

struct List {

struct Node *head;

};

/*

* Initialize an empty list.

*/

static inline void initList(struct List *list)

{

list->head = 0;

}

/*

* In all functions below, the 'list' parameter is assumed to point to

* a valid List structure.

*/

/*

* Create a node that holds the given data pointer,

* and add the node to the front of the list.

*

* Note that this function does not manage the lifetime of the object

* pointed to by 'data'.

*

* It returns the newly created node on success and NULL on failure.

*/

struct Node *addFront(struct List *list, void *data);

/*

* Traverse the list, calling f() with each data item.

*/

void traverseList(struct List *list, void (*f)(void *));

/*

* Traverse the list, comparing each data item with 'dataSought' using

* 'compar' function. ('compar' returns 0 if the data pointed to by

* the two parameters are equal, non-zero value otherwise.)

*

* Returns the first node containing the matching data,

* NULL if not found.

*/

struct Node *findNode(struct List *list, const void *dataSought,

int (*compar)(const void *, const void *));

/*

* Flip the sign of the double value pointed to by 'data' by

* multiplying -1 to it and putting the result back into the memory

* location.

*/

void flipSignDouble(void *data);

/*

* Compare two double values pointed to by the two pointers.

* Return 0 if they are the same value, 1 otherwise.

*/

int compareDouble(const void *data1, const void *data2);

/*

* Returns 1 if the list is empty, 0 otherwise.

*/

static inline int isEmptyList(struct List *list)

{

return (list->head == 0);

}

/*

* Remove the first node from the list, deallocate the memory for the

* ndoe, and return the 'data' pointer that was stored in the node.

* Returns NULL is the list is empty.

*/

void *popFront(struct List *list);

/*

* Remove all nodes from the list, deallocating the memory for the

* nodes. You can implement this function using popFront().

*/

void removeAllNodes(struct List *list);

/*

* Create a node that holds the given data pointer,

* and add the node right after the node passed in as the 'prevNode'

* parameter. If 'prevNode' is NULL, this function is equivalent to

* addFront().

*

* Note that prevNode, if not NULL, is assumed to be one of the nodes

* in the given list. The behavior of this function is undefined if

* prevNode does not belong in the given list.

*

* Note that this function does not manage the lifetime of the object

* pointed to by 'data'.

*

* It returns the newly created node on success and NULL on failure.

*/

struct Node *addAfter(struct List *list,

struct Node *prevNode, void *data);

/*

* Reverse the list.

*

* Note that this function reverses the list purely by manipulating

* pointers. It does NOT call malloc directly or indirectly (which

* means that it does not call addFront() or addAfter()).

*

* Implementation hint: keep track of 3 consecutive nodes (previous,

* current, next) and move them along in a while loop. Your function

* should start like this:

struct Node *prv = NULL;

struct Node *cur = list->head;

struct Node *nxt;

while (cur) {

......

* And at the end, prv will end up pointing to the first element of

* the reversed list. Don't forget to assign it to list->head.

*/

void reverseList(struct List *list);

#endif /* #ifndef _MYLIST_H_ */

#include

#include

#include

#include "mylist.h"

static void printDouble(void *p)

{

printf("%.1f ", *(double *)p);

}

static void die(const char *message)

{

perror(message);

exit(1);

}

int main()

{

double a[] = { 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0 };

int n = sizeof(a) / sizeof(a[0]);

int i;

double x;

void *data;

struct Node *node;

// initialize list

struct List list;

initList(&list);

// test addFront()

printf("testing addFront(): ");

for (i = 0; i < n; i++) {

if (addFront(&list, a+i) == NULL)

die("addFront() failed");

}

traverseList(&list, &printDouble);

printf(" ");

// test flipSignDouble()

printf("testing flipSignDouble(): ");

traverseList(&list, &flipSignDouble);

traverseList(&list, &printDouble);

printf(" ");

printf("testing flipSignDouble() again: ");

traverseList(&list, &flipSignDouble);

traverseList(&list, &printDouble);

printf(" ");

// test findNode()

printf("testing findNode(): ");

x = 3.5;

node = findNode(&list, &x, &compareDouble);

assert(node == NULL);

x = 1.0;

node = findNode(&list, &x, &compareDouble);

assert(node != NULL && *(double *)node->data == x);

printf("OK ");

// test popFront()

while ((data = popFront(&list)) != NULL) {

printf("popped %.1f, the rest is: [ ", *(double *)data);

traverseList(&list, &printDouble);

printf("] ");

}

// test addAfter()

printf("testing addAfter(): ");

node = NULL;

for (i = 0; i < n; i++) {

// We keep adding after the previously added node,

// so we are in effect 'appending' to the list.

node = addAfter(&list, node, a+i);

if (node == NULL)

die("addAfter() failed");

}

traverseList(&list, &printDouble);

printf(" ");

// test reverseList()

while ((data = popFront(&list)) != NULL) {

printf("popped %.1f, and reversed the rest: [ ", *(double *)data);

reverseList(&list);

traverseList(&list, &printDouble);

printf("] ");

}

return 0;

}