[BUG] Return statement in data_structures/linked_list/doubly_linked_list.c

[tevjd]

Description

There is a bug in the doubly_linked_list.c because some functions don't have a return statement for every path. The consequence is an undefined behaviour in some context.

Expected behavior

The result of the search function should be 1 if the value exists and 0 if not.

Actual behavior

Undefined behaviour for some configuration.

Possible fix

Add return statement to search, insert and delete functions.

Steps to reproduce

with gcc 13.3.0

gcc -o test_gcc doubly_linked_list.c
./test_gcc

3.000000 0.000000 20.000000 10.000000 5.000000
1
5.000000
0

with clang 18.1.3

clang -o test_clang doubly_linked_list.c
./test_clang

3.000000 0.000000 20.000000 10.000000 5.000000
24027
5.000000
24027

Context

For a personal project I needed to compile some C code with no dependencies. So I chose random programs from this repo.

I noticed a bug with one of the algorithms, especially the doubly_linked_list.c under: data_structures/linked_list
The problem is that some functions in this program don't have a return statement for every path.

For the functions insert and delete this is not crucial for the execution, but it is safer to add a return list; at the end.

For the search function this is more problematic as the behaviour is undefined. For example working on my Ubuntu machine with GCC 13.3.0 and Clang 18.1.3 we have different results with the test present in the main function.

Additional information

You have the warning for the non-return statement for every path with clang. You can enable them for gcc using the option -Wall.

There is only a minor change to make to fix the issue. I can propose the new version if needed with a small pull request.
I didn't check the other algorithm under the linked_lidt/ folder as I was not working with them. But I would be happy to do it if there is a need.

[TikTorchic18]

Would the below work for search?

int search(List *list, double value)
{
    if (list == NULL)
        return 0;
    if (list->value == value)
        return 1;
    return search(list->next, value);
}

As the function is written rn, the search only checks the root (the results for later searches aren't used).
I also wanted to ask why stdbool.h isn't being used?

P.S. If you wanted to be a bit more terse while still being readable (also using stdbool.h), you could write the above as:

bool search(List *list, double value)
{
    if (list == NULL)
        return false;
    return list->value == value || search(list->next, value);
}

[tevjd]

Yes, your first code example is the fix I tried. We need to return the recursive value otherwise, the behaviour would be undefined.

For your second question, yes, this is actually a good rewriting of the function. The only default is that it could be less readable for a beginner programmer, I guess.

Suppose we want to optimise a bit and not overflow the stack for potential very big recursion. We can use this version instead, which is an iterative approach:

bool search(List *list, double value)
{
    List *current = list;

    while(current != NULL) {
        if (current->value == value) {
            return true;
        }
        current = current->next;
    }
    return false;
}

What do you think?

[TikTorchic18]

The recursive approach ties into tree traversal very nicely.

For the iterative approach, a for loop would be super slick:

for (List *node = list; node != NULL; node = node->next) {
    if (node->value == value) {
        return true;
    }
}

I guess slickness comes at the cost of readability but tbf, this design pattern is used similarly for looping through the chars of a string:

for (char *p = str; *p != '\0'; p++) ...