List_ops exercise function void delete_list(list_t *list)

Programming C
1

I get a segmentation fault when I include my delete_list function. All my other functions passed tests in the editor. The comment for the function in file list_ops.h is:

// destroy the entire list
// list will be a dangling pointer after calling this method on it

There appears to be no actual test for the function delete_list. It is only called in the body of the function:

static void call_delete_list(list_t **list)

If I leave out the function delete_list then I get the error undefined reference to delete_list.

How do I fix this? I expected a simple call:

free(list);

would be all that is required.

2

The tests call delete_list, so you have to define it, or you will get a “undefined reference” error.

But I don’t understand how you get a “segmentation fault”. Can you show your code?

free(list) deallocates the list object itself. Depending on how you’ve defined list_t that might not be enough, it might be necessary to deallocate the elements, too.

As for testing: I don’t think it’s possible to test delete_list() without complex and platform-specific code that dives into the implementation of the malloc()/calloc()/realloc()/free() subsystem that performs the actual allocation.

3

My code is:

void delete_list(list_t *list)
{
    free(list);
}

Simple as that. I did not get any errors or warnings compiling on my local machine with gcc.

4

Great! And that will do the work.

5

Except it does not. The output I receive is:

We received the following error when we ran your code:
make: *** [makefile:22: test] Segmentation fault (core dumped)
6

Then the issue is probably somewhere else in your solution.
I just checked, the delete_list() in my solution looks exactly like yours and all tests pass.

Can you show your code?

7

See below:

#include "list_ops.h"

list_t *new_list(size_t length, list_element_t elements[])
{
    list_t *list = malloc(sizeof(list_t));
    list->length = length;
    size_t i;
    for (i = 0; i < length; ++i){
        list->elements[i] = elements[i];
    }
    return list;
}

size_t length_list(list_t *list)
{
    return list->length;
}

list_t *append_list(list_t *list1, list_t *list2)
{
    size_t n1 = list1->length, n2 = list2->length, i;
    if (n1 == 0 && n2 > 0) {
        return list2;
    } else if (n1 > 0 && n2 == 0) {
        return list1;
    }
    list1 = realloc(list1, n1 + n2);
    assert(list1 != NULL);
    for (i = n1; i < n2; ++i)
        list1->elements[i] = list2->elements[i];
    list1->length = n1 + n2;
    return list1;
}

list_t *filter_list(list_t *list, bool (*filter)(list_element_t))
{
    if (list->length == 0) {return list;}
    else {
        size_t n = list->length, i, j;
        list_element_t elements2[n];
        for (i = 0; i < n; ++i)
            elements2[i] = 0;
        list_t *list2 = new_list(n, elements2);
        for (i = 0, j = 0; i < n; ++i) {
            if (filter(list->elements[i])) {
                list2->elements[j] = list->elements[i];
                j++;
            }
        }
        list2->length = j;
        return list2;
    }
}

list_t *map_list(list_t *list, list_element_t (*map)(list_element_t))
{
    if (!list->length) {return list;}
    else {
        size_t n = list->length, i;
        list_element_t elements2[n];
        for (i = 0; i < n; ++i)
            elements2[i] = 0;
        list_t *list2 = new_list(n, elements2);
        for (i = 0; i < n; ++i) {
            list2->elements[i] = map(list->elements[i]);
        }
        list2->length = n;
        return list2;
    }
}

list_element_t foldl_list(list_t *list, list_element_t initial,
                          list_element_t (*foldl)(list_element_t, list_element_t))
{
    if (!list->length) {return initial;}
    else {
        size_t n = list->length, i;
        list_element_t accum = initial;
        for (i = 0; i < n; ++i)
            accum = foldl(list->elements[i], accum);
        return accum;
    }
}

list_element_t foldr_list(list_t *list, list_element_t initial,
                          list_element_t (*foldr)(list_element_t, list_element_t))
{
    if (!list->length) {return initial;}
    else {
        int n = list->length, i;
        list_element_t accum = initial;
        for (i = n - 1; i >= 0; --i) {
            accum = foldr(list->elements[i], accum);
        }
        return accum;
    }
}

list_t *reverse_list(list_t *list)
{
    if (!list->length) {return list;};
    list_t *list2;
    size_t n = list->length, i;
    list_element_t elements2[n];
    for (i = 0; i < n; ++i)
        elements2[i] = 0;
    for (int i = 0, j = n - 1; j >= 0; --j, ++i)
        elements2[i] = list->elements[j];
    list2 = new_list(n, elements2);
    return list2;
}

void delete_list(list_t *list)
{
    free(list);
}
8

At first glance I can see a few issues:

  • The malloc() in new_list allocates enough memory for the list_t itself, but not for its elements.
  • The realloc() in append_list() allocates n1 + n2 bytes. But you need to allocate enough memory for the list_t and the n1 + n2 integers.
  • If you look at the tests you’ll see that tearDown() deletes all three lists (list, list2, and actual). But in this solution some functions return a pointer to one of their arguments, so the tearDown() will try to delete a list twice which invokes undefined behavior. Instead the functions that return a list should return a completely new list. (I think this is where your issue originates.)
1 Like
9

Thanks a lot for the supper quick response and taking the trouble to look through my code. You make some good suggestions which I understand (I think) and will try out soon but not this evening.

I have not got started with Unity for unit testing locally yet. I just wrote tests on my local machine which as far as I can tell closely match those in the editor.

Hopefully after trying out your suggestions I will have cracked it.

Many Thanks

10

I’m glad I could help. Let me know if you need any hints or help. Cheers!

11

A while ago I had a pretty similar session and it was actually because the malloc allocated not enough memory. I still didn’t dive into the “why”, but actually local versions almost always worked. Seems the Alpine / musl environment is really more strict (what is good, but weird when it works locally).

12

Well after resting my brain. I had another go and tackled each of the three points you raised. Locally I created the call_delete_list() function and called it on any of the lists created in the local tests I wrote to mimic the Unity tests. I added gcc option -Wextra in addition to -O -Wall -pedantic -ansi -std=c99 -o. After some work I again got all my local tests passed.

In the editor however, I have error segmentation fault. So clearly I have not implemented your suggestions properly, or have some other error in my code.

If you could help further that would be great. Latest code is below:

#include "list_ops.h"

list_t *new_list(size_t length, list_element_t elements[])
{
    list_t *list = malloc(sizeof(list_t) + sizeof(list_element_t) * length);
    list->length = length;
    size_t i;
    for (i = 0; i < length; ++i){
        list->elements[i] = elements[i];
    }
    return list;
}

size_t length_list(list_t *list)
{
    return list->length;
}

list_t *append_list(list_t *list1, list_t *list2)
{
    size_t n1 = list1->length, n2 = list2->length, i, j;
    if (n1 == 0 && n2 > 0) {
        list_t *out_list;
        list_element_t *elements2 = malloc(sizeof(list_element_t) * n2);
        for (i = 0; i < n2; ++i)
            elements2[i] = list2->elements[i];
        out_list = new_list(n2, elements2);
        return out_list;
    } else if (n1 > 0 && n2 == 0) {
        list_t *out_list;
        list_element_t *elements2 = malloc(sizeof(list_element_t) * n1);
        for (i = 0; i < n1; ++i)
            elements2[i] = list1->elements[i];
        out_list = new_list(n1, elements2);
        return out_list;
    } else if (n1 == 0 && n2 == 0) {
        return new_list(0, NULL);
    } else {
        list1 = realloc(list1, sizeof(list_t) + sizeof(list_element_t) * (n1 + n2));
        assert(list1 != NULL);
        list_element_t *elements2 = malloc(sizeof(list_element_t) * (n1 + n2));
        for (i = 0; i < n1; ++i)
            elements2[i] = list1->elements[i];
        for (i = n1, j = 0; i < n1 + n2; ++i, ++j)
            elements2[i] = list2->elements[j];
        list_t *out_list;
        out_list = new_list(n1 + n2, elements2);
        return out_list;
    }
}

list_t *filter_list(list_t *list, bool (*filter)(list_element_t))
{
    if (list->length == 0) {return new_list(0, NULL);}
    else {
        size_t n = list->length, i, j;
        list_element_t elements2[n];
        for (i = 0; i < n; ++i)
            elements2[i] = 0;
        list_t *list2 = new_list(n, elements2);
        for (i = 0, j = 0; i < n; ++i) {
            if (filter(list->elements[i])) {
                list2->elements[j] = list->elements[i];
                j++;
            }
        }
        list2->length = j;
        return list2;
    }
}

list_t *map_list(list_t *list, list_element_t (*map)(list_element_t))
{
    if (!list->length) {return new_list(0, NULL);}
    else {
        size_t n = list->length, i;
        list_element_t elements2[n];
        for (i = 0; i < n; ++i)
            elements2[i] = 0;
        list_t *list2 = new_list(n, elements2);
        for (i = 0; i < n; ++i) {
            list2->elements[i] = map(list->elements[i]);
        }
        list2->length = n;
        return list2;
    }
}

list_element_t foldl_list(list_t *list, list_element_t initial,
                          list_element_t (*foldl)(list_element_t, list_element_t))
{
    if (!list->length) {return initial;}
    else {
        size_t n = list->length, i;
        list_element_t accum = initial;
        for (i = 0; i < n; ++i)
            accum = foldl(list->elements[i], accum);
        return accum;
    }
}

list_element_t foldr_list(list_t *list, list_element_t initial,
                          list_element_t (*foldr)(list_element_t, list_element_t))
{
    if (!list->length) {return initial;}
    else {
        int n = list->length, i;
        list_element_t accum = initial;
        for (i = n - 1; i >= 0; --i) {
            accum = foldr(list->elements[i], accum);
        }
        return accum;
    }
}

list_t *reverse_list(list_t *list)
{
    if (!list->length) {
        return new_list(0, NULL);
    } else {
        list_t *list2;
        size_t n = list->length;
        int i, j, _n;
        _n = n;
        list_element_t *elements2 = malloc(sizeof(list_element_t) * n);
        for (i = 0; i < _n; ++i)
            elements2[i] = 0;
        for (i = 0, j = _n - 1; j >= 0; --j, ++i)
            elements2[i] = list->elements[j];
        list2 = new_list(n, elements2);
        return list2;
    }
}

void delete_list(list_t *list)
{
    free(list);
}
13

append_list() calls realloc(list1, ...). This function is a little bit tricky: It might resize the allocated chunk of memory that the first parameter points to and return the first parameter. Or it might allocate a new chunk of memory, copy the contents of the old chunk over, delete the old chunk of memory, and return a pointer to the new chunk. (Or it might fail to allocate anything and just return NULL.)
That means this realloc() might modify the parameter list1 so that the first argument of the caller is now dangling, and if they try to access it or deallocate it they invoke undefined behavior.

Luckily you don’t need that realloc() at all, you can just remove the line.

Also, several functions call malloc() to create some temporary space. But that temporary space never gets deallocated. That’s a memory leak.

If you fix those two issues your solution will pass the tests.

14

Sweet after following your advice my updated code passed. Thank you. I am learning.
:smile: