Week 09 Tutorial Sample Answers

Your tutor has asked a lab pair to present their week 8 work.
Discuss the good, the bad and the ugly aspects of their code.
Please be gentle in any criticism - we are all learning!
How are you progressing with the assignment?
Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?
What does malloc() do?
What are its inputs and output and what do they mean?
Describe a function that will allocate memory for a struct and assign a pointer to the result.
If we answer this with a diagram, we can show that the memory allocated using malloc is outside the memory for any function, so it lasts beyond the functions themselves.
Malloc() will always return a pointer that will give us the address of this memory. This means we will have a pointer to a variable that won't be cleaned up automatically and we can pass that around between functions etc.
The input to malloc() will be the number of bytes needed to store the variable. We will nearly always use sizeof() to find out this value.
The code below can be useful, but there's not much there. It's more useful to think about what "allocating memory" means. It's basically the idea that we're creating a new variable, except it's only accessible by a pointer and it lasts after the function that created it has returned.
```
// a generic linked list node (we could use any struct we want here)
struct node {
    int data;
    struct node * next;
};

struct node *makeNode(int inputData) {
    struct node *n;
    n = malloc(sizeof (struct node));
    return n;
}
```
What does free() do?
What is the input to free and how does it help it do what it needs to do?
Free will return allocated memory to the computer. This means it will follow the pointer (which it is given as input) to a memory location and free as much memory as the pointer has allocated to it. free knows how much memory to free based on the information stored when malloc is called as these two functions are from the same library.
What is a use after free error? Give an example.
Discuss why these are extremely dangerous, one of the worst causes of bugs in C programs and a major source of security vulnerabilities.
A use after free error occurs when memory which has deallocated with free is subsequently used. Here is a very simple example:
```
free(p);
printf("%d\n", p->data);
```
Students often incorrectly believe that it is must be safe to access p->data because nothing can have changed.
Commonly free will change the contents of the memory it is given (back) to record its internal housekeeping information.
More generally in a threaded program a malloc could be called in another thread between the free and the printf.
In more complex programs its common mistake for programmers to free some memory, for example holding a struct, but forget that it is still being used elsewhere in their code (probably via different pointer).
As their code keeps executing if malloc is called again to store another struct it is likely to be allocated the recently freed memory.
This means what are meant to be two structs containing different values are now occupying the one piece of memory.
This has disastrous results as assignments to one struct change the other.
Not only is this is very difficult to debug, but malicious users exploit these error (in extremely convoluted ways) to bypass security.
So essentially:
1. you malloc some memory
2. you free that memory
3. you forget you've freed it, and try to use it again e.g. dereference fields in a struct
4. somewhere between steps 2 and 3, I malloced memory which ended up in the same memory as yours was
5. I put whatever I want in that memory; when you try to use it, you get whatever I've put there
(this might not sound so bad in the scope of COMP1511 code, but it's very dangerous when it comes to things like function pointers, wherein UAF means you can have arbitrary code execution. yay security.)
What is a memory leak?
What does dcc --leak-check do?

A memory leak is when a program doesn't free memory allocated with malloc.
This is (generally) not important in the programs we write in COMP1511 because they run only for short periods of time and allocate small amounts of memory.
But if, for example, a web browser allocates memory (calls malloc) every time a user visits a page but doesn't free the memory (call free) when they leave the page, the web browser's memory use will steadily grow, eventually causing performance problems and then if it exhausts available memory, termination.
So we want you to practice free-ing memory in lab exercises.
dcc --leak-check warns you when you haven't freed your memory. It uses an underlying tool named valgrind. It translates valgrind output into something hopefully a COMP1511 student can understand.
Note, the operating system reclaims all memory when a program exits.

Implement a function list_append which appends its second argument to its first. Treat both inputs as if they are lists and may have more than one node. It should have this prototype:

struct node *list_append(struct node *list1, struct node *list2);

As usual, struct node has this definition:

struct node {
    int          data;
    struct node *next;
};

It should not create (malloc) any new list elements.

It should just change the appropriate next field in the first list.

struct node *list_append(struct node *list1, struct node *list2) {
    struct node *n;
    if (list1 == NULL) {
        return list2;
    }
    n = list1;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = list2;
    return list1;
}

This and following questions use this datatype from lectures:
```
struct node {
    int data;
    struct node *next;
};
```
See list_empty.c and list.h for this weeks linked list tute questions, and test_list.c for autotests. Alternatively download all three files as tut_list_files.zip.

See tut10_list.c for a version with the functions implemented.

Implement a function copy which returns a copy of a linked list. It should have this prototype.

struct node *copy(struct node *head);

It should call malloc to create a new linked list of the same length and which contains the same data.

struct node *copy(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *new_head = malloc(sizeof (struct node));
    assert(new_head);
    new_head->data = head->data;

    struct node *last_new_node = new_head;
    struct node *p = head->next;

    while (p != NULL) {
        last_new_node->next = malloc(sizeof (struct node));
        last_new_node = last_new_node->next;
        assert(last_new_node != NULL);
        last_new_node->data = p->data;
        p = p->next;
    }
    last_new_node->next = NULL;

    return new_head;
}

Implement a function identical that returns 1 if the contents of the two linked lists are identical (same length, same values in data fields) and otherwise returns 0. It should have this prototype:

int identical(struct node *head1, struct node *head2);

int identical(struct node *head1, struct node *head2) {
    struct node *p1 = head1;
    struct node *p2 = head2;

    while (p1 != NULL && p2 != NULL) {
        if (p1->data != p2->data) {
            return 0;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    return p1 == p2;
}

Implement a function set_intersection which given two linked lists in strictly increasing order returns a new linked list containing a copy of the elements found in both lists.

The new linked list should also be in strictly increasing order. It should include only elements found in both lists.

set_intersection should call malloc to create the nodes of the new linked list.

set_intersection should have this prototype:

struct node *set_intersection(struct node *set1, struct node *set2);

// given two lists in strictly increasing order,
// return a new linked list (in strictly increasing order) of the elements
// in both set1 and set2
struct node *set_intersection(struct node *set1, struct node *set2) {
    struct node *head = NULL;
    struct node *tail = NULL;

    // Loop through both lists at the same time.
    // We're not going to be at exactly the same place
    // in both lists, we might move asymetrically
    // based on which numbers are higher in which list.
    struct node *curr1 = set1;
    struct node *curr2 = set2;    
    while (curr1 != NULL && curr2 != NULL) {
        if (curr1->data < curr2->data) {
            // set1 is lower, so needs to catch up
            curr1 = curr1->next;
        } else if (curr1->data > curr2-> data) {
            // set2 is lower, so needs to catch up
            curr2 = curr2->next;
        } else { // curr1->data == curr2->data
            // numbers are the same, add a node to the new list
            if (head == NULL) { // start new list
                head = create_node(curr1->data);
                tail = head;
            } else { // add to end of list
                tail->next = create_node(curr1->data);
                tail = tail->next;
            }
            curr1 = curr1->next;
            curr2 = curr2->next;         
        }
    }
    return head;
}