4
\$\begingroup\$

After watching Stroustrup's presentation on performance comparison between vectors and linked lists (https://youtu.be/YQs6IC-vgmo?si=9r5wXqnwkmN29xqn), I've decided it would be a good problem to get a hang of C. To that end, I've profiled how long gthe removal of all elements from the lists by sampling random indices takes. It's a toy problem, and I did not want to go for a doubly linked list immediately, just PoC implementation using fixed data types in nodes and a single linked list. I'm aware the implementations can be optimized, but first I wanted to make sure I'm not doing any terrible practices.

What I'm looking for is mostly design review, specifically:

  1. Is this a proper way to design multiple implementations of a single interface?
  2. removed
  3. If there are obvious bugs or "it works, but please don't do it that way" things, please point them out.

Thank you to anyone who takes the time to check this out. A side note, the tester.c and tester.h were taken from https://codeahoy.com/learn/cprogramming/ch46/ so I will not be including them for review (but a big thanks to the authors, it's a really cool tool!).

profile_list.c

#include "lists/list.h"

#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdio.h>

#define N_ELEMS 100000
#define TO_REMOVE 100000

void test_list(List list)
{
    clock_t start = clock();
    for (int i = 0; i < TO_REMOVE; i++)
    {
        usize next_index = rand() % List_length(list);
        List_success res = List_remove_index(list, next_index);
        assert(res != List_ERROR);
    }
    clock_t end = clock();
    printf("Remove time: %ld\n", end - start);
}

int main(int argc, char const *argv[])
{
    srand(time(NULL));
    List list = List_init();
    for (int i = 0; i < N_ELEMS; i++)
    {
        List_append(list, i);
    }
    test_list(list);
    return 0;
}

lists/list.h

#ifndef C4E61219_04C6_41E9_87A7_649125E1083C
#define C4E61219_04C6_41E9_87A7_649125E1083C
#include <stddef.h>
#include <stdint.h>

typedef int32_t i32;
typedef size_t usize;

typedef struct List *List;

typedef enum
{
    List_ERROR,
    List_OK
} List_success;

typedef struct List_result
{
    List_success success;
    i32 data;
} List_result;

List List_init(void);
void List_delete(List *list);
void List_append(List list, i32 data);
List_success List_insert(List list, i32 data, usize position);
List_success List_remove_val(List list, i32 val);
List_success List_remove_index(List list, usize position);
List_result List_get(List list, usize position);
void List_print(List list);
usize List_length(List list);

#endif /* C4E61219_04C6_41E9_87A7_649125E1083C */

lists/linked_list.c

#include "list.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef struct Node *Node;
Node make_node(i32 data, Node next);
void delete_node(Node *node);

struct List
{
    Node head;
    usize size;
};

struct Node
{
    i32 data;
    Node next;
};

Node make_node(i32 data, Node next)
{
    Node node = malloc(sizeof(Node));
    if (node == NULL)
    {
        fprintf(stderr, "Failed to allocate memory for node!\n");
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->next = next;
    return node;
}

void delete_node(Node *node)
{
    free(*node);
    *node = NULL;
}

List List_init(void)
{
    List list = malloc(sizeof(List));
    if (list == NULL)
    {
        fprintf(stderr, "Failed to allocate memory for list!\n");
        exit(EXIT_FAILURE);
    }
    list->head = NULL;
    list->size = 0;
    return list;
}

void List_delete(List *list_pointer)
{
    List list = *list_pointer;

    while (list->head != NULL)
    {
        Node current_node = list->head;
        list->head = current_node->next;
        delete_node(&current_node);
    }
    free(list);
    *list_pointer = NULL;
}

void List_append(List list, i32 data)
{
    Node node = make_node(data, NULL);
    list->size += 1;
    if (list->head == NULL)
    {
        list->head = node;
        return;
    }
    Node current_node = list->head;
    while (current_node->next != NULL)
    {
        current_node = current_node->next;
    }
    current_node->next = node;
}

List_success List_insert(List list, i32 data, usize index)
{
    if (index >= list->size || index < 0)
    {
        return List_ERROR;
    }

    list->size += 1;
    Node node = make_node(data, NULL);
    Node current_node = list->head;

    if (index == 0)
    {
        node->next = current_node;
        list->head = node;
        return List_OK;
    }

    while (index > 1) /*Stop at the element just before the position!*/
    {
        current_node = current_node->next;
        index -= 1;
    }
    node->next = current_node->next;
    current_node->next = node;
    return List_OK;
}

List_success List_remove_val(List list, i32 val)
{
    if (val == list->head->data)
    {
        Node to_delete = list->head;
        list->head = list->head->next;
        delete_node(&to_delete);
        list->size -= 1;
        return List_OK;
    }
    for (Node curr = list->head; curr->next != NULL; curr = curr->next)
    {
        if (curr->next->data == val)
        {
            Node to_delete = curr->next;
            curr->next = curr->next->next;
            delete_node(&to_delete);
            list->size -= 1;
            return List_OK;
        }
    }
    return List_ERROR;
}

List_success List_remove_index(List list, usize index)
{
    if (index >= list->size || index < 0)
    {
        return List_ERROR;
    }

    list->size -= 1;
    if (index == 0)
    {
        Node to_delete = list->head;
        list->head = list->head->next;
        delete_node(&to_delete);
        return List_OK;
    }

    Node current_node = list->head;
    while (index > 1)
    {
        index -= 1;
        current_node = current_node->next;
    }

    Node to_delete = current_node->next;
    current_node->next = to_delete->next;
    delete_node(&to_delete);
    return List_OK;
}

List_result List_get(List list, usize index)
{
    List_result res;
    if (index >= list->size || index < 0)
    {
        res.success = List_ERROR;
    }
    else
    {
        res.success = List_OK;
        Node current_node = list->head;
        while (index > 0)
        {
            index -= 1;
            current_node = current_node->next;
        }
        res.data = current_node->data;
    }

    return res;
}

void List_print(List list)
{
    printf("[");
    Node curr_node = list->head;
    while (curr_node != NULL)
    {
        printf("%d, ", curr_node->data);
        curr_node = curr_node->next;
    }
    printf("]\n");
}

usize List_length(List list)
{
    return list->size;
}

lists/array_list.c

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct List
{
    i32 *elements;
    usize size;
    usize capacity;
};

List List_init(void)
{
    List list = malloc(sizeof(List));
    if (list == NULL)
    {
        fprintf(stderr, "Failed to allocate memory for list!\n");
        exit(EXIT_FAILURE);
    }
    list->elements = NULL;
    list->size = 0;
    list->capacity = 0;
    return list;
}

void List_delete(List *list)
{
    free((*list)->elements);
    (*list)->elements = NULL;

    free(*list);
    *list = NULL;
}

static inline usize _closest_power_of_2(usize val)
{
    usize p = 1;
    while (p < val)
    {
        p = p << 1;
    }
    return p;
}

void _resize_if_needed(List list, usize newsize)
{
    if (newsize == 0)
    {
        free(list->elements);
        list->elements = NULL;
        list->capacity = 0;
        return;
    }

    usize blocksize = _closest_power_of_2(newsize);
    usize new_capacity = blocksize * sizeof(i32);

    if (new_capacity == list->capacity)
    {
        return;
    }

    if (list->elements == NULL)
    {
        list->elements = malloc(new_capacity);
        if (list->elements == NULL)
        {
            fprintf(stderr, "Failed to allocate memory for list elements of %zu!\n", new_capacity);
            exit(EXIT_FAILURE);
        }
        list->capacity = new_capacity;
    }
    else
    {
        void *tmp = realloc(list->elements, new_capacity);
        if (tmp != NULL)
        {
            list->elements = tmp;
        }
        else
        {
            fprintf(stderr, "Failed to allocate memory for list elements of %zu!\n", new_capacity);
            exit(EXIT_FAILURE);
        }
    }
}

void List_append(List list, i32 data)
{
    _resize_if_needed(list, list->size + 1);
    list->elements[list->size] = data;
    list->size += 1;
}

List_success List_insert(List list, i32 data, usize position)
{
    if (position < 0 || position >= list->size)
    {
        return List_ERROR;
    }

    _resize_if_needed(list, list->size + 1);
    for (usize i = list->size; i > position; i--)
    {
        list->elements[i] = list->elements[i - 1];
    }
    list->elements[position] = data;
    list->size += 1;
    return List_OK;
}

List_success List_remove_val(List list, i32 val)
{
    for (usize i = 0; i < list->size; i++)
    {
        if (list->elements[i] == val)
        {
            List_remove_index(list, i);
            return List_OK;
        }
    }
    return List_ERROR;
}

List_success List_remove_index(List list, usize position)
{
    if (position < 0 || position >= list->size)
    {
        return List_ERROR;
    }

    for (usize i = position; i < list->size - 1; i++)
    {
        list->elements[i] = list->elements[i + 1];
    }

    _resize_if_needed(list, list->size - 1);
    list->size -= 1;
    return List_OK;
}

List_result List_get(List list, usize position)
{
    List_result res = {0};
    if (position < 0 || position >= list->size)
    {
        res.success = List_ERROR;
    }
    else
    {
        res.data = list->elements[position];
        res.success = List_OK;
    }
    return res;
}

void List_print(List list)
{
    printf("[");
    for (int i = 0; i < list->size; i++)
    {
        printf("%d, ", list->elements[i]);
    }

    printf("]\n");
}

usize List_length(List list)
{
    return list->size;
}

test/test_list.c

/*
Includes required for tester.h to work.
*/
#include <stdio.h>
#include <setjmp.h>
#include <signal.h>
#include <unistd.h>

#include "../lists/list.h"
#include "tester.h"


int main(int argc, char const *argv[])
{
    List list = List_init();
    List_success res;
    usize currsize;

    /* Test initialize empty list */
    TEST_ASSERT(List_length(list) == 0);

    List_append(list, 5);
    List_append(list, 15);
    List_append(list, 200);

    /* Test List_append increased List_length  */
    TEST_ASSERT(List_length(list) == 3);

    /* Test List_get zeroth index */
    TEST_ASSERT(List_get(list, 0).data == 5);

    /* Test List_get non-zero index */
    TEST_ASSERT(List_get(list, 1).data == 15);

    /* Test List_get non-existent index */
    TEST_ASSERT(List_get(list, 15).success == List_ERROR);

    /* Test List_insert on the zeroth position */
    res = List_insert(list, -1, 0);
    TEST_ASSERT(res == List_OK && List_get(list, 0).data == -1);

    /* Test List_insert on non-zero position */
    res = List_insert(list, -256, 2);
    TEST_ASSERT(res == List_OK && List_get(list, 2).data == -256);

    /* Test List_insert on non-existing position */
    res = List_insert(list, 800, 19);
    TEST_ASSERT(res == List_ERROR);

    /* Test remove value at zeroth position */
    currsize = List_length(list);
    res = List_remove_val(list, -1);
    TEST_ASSERT(res == List_OK && List_length(list) == currsize - 1);

    /* Test remove value at non-zeroth position */
    currsize = List_length(list);
    res = List_remove_val(list, 15);
    TEST_ASSERT(res == List_OK && List_length(list) == currsize - 1);

    /* Test remove trying to remove non-existent value */
    currsize = List_length(list);
    res = List_remove_val(list, 15);
    TEST_ASSERT(res == List_ERROR && List_length(list) == currsize);

    /* Test remove some index */
    currsize = List_length(list);
    res = List_remove_index(list, 1);
    TEST_ASSERT(res == List_OK && List_length(list) == currsize - 1);

    /* Test remove zeroth index */
    currsize = List_length(list);
    res = List_remove_index(list, 0);
    TEST_ASSERT(res == List_OK && List_length(list) == currsize - 1);

    /* Test remove non-existent index */
    currsize = List_length(list);
    res = List_remove_index(list, 19);
    TEST_ASSERT(res == List_ERROR && List_length(list) == currsize);
    
    /* Test delete list */
    List_delete(&list);
    TEST_ASSERT(list == NULL);

    return 0;
}

Makefile

CC=gcc
CFLAGS=-g3 -Wall

all:

test: test_linked_list.out test_array_list.out
    ./test_linked_list.out
    ./test_array_list.out
    @echo OK!

test_linked_list.out: test/test_list.o test/tester.o lists/linked_list.o
    $(CC) $(CFLAGS) -o $@ $^

test_array_list.out: test/test_list.o test/tester.o lists/array_list.o
    $(CC) $(CFLAGS) -o $@ $^

test/test_list.o: test/tester.h lists/list.h

perftest: profile_array_list profile_linked_list
    @echo LinkedList:
    ./profile_linked_list
    @echo ArrayList:
    ./profile_array_list

profile_array_list.out: profile_list.o lists/array_list.o
    $(CC) $(CFLAGS) -o $@ $^

profile_linked_list.out: profile_list.o lists/linked_list.o
    $(CC) $(CFLAGS) -o $@ $^

tester.o: test/tester.h

linked_list.o: lists/list.h

array_list.o: lists/list.h

clean:
    rm -f *.o test/*.o lists/*.o *.out

Edits:

  1. Removed question 2) since it is not suited for this community
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Note that removal of a random element from the middle of a linked list is something that actually is efficient, if you have a pointer to the preceding node already. Taking an integer index and pointer to the head is of course terrible since it takes O(n) time just to seek to the indexed element. \$\endgroup\$ Oct 26, 2023 at 16:03

2 Answers 2

7
\$\begingroup\$

Most of the code looks good, apart from the misleading typedef that harold's answer addresses. In this review, I'll be assuming that we fix that problem.

I just have a handful of minor observations; no very serious problems.

The main program

It might be worth adding assert(TO_REMOVE <= N_ELEMS) at the start of the function to fail early rather than hitting a divide-by-zero if we give it bad input.

We could convert clock_t values to human units (e.g. by dividing by (double)CLOCKS_PER_SEC for seconds). But that's not important for this case, where we're more interested in the ratio of the two implementations.

rand() % List_length(list) doesn't give a perfectly uniform probability distribution. That's not important here, but thought I should mention it.

srand(time(NULL)); will give us a different random sequence depending on when we run the program. Usually, that's a good thing, but when we're comparing two implementations, it's arguably fairer if we give both implementations exactly the same workload. So I'd seed with a fixed value (or just omit this, which has the effect of srand(1)).

We don't use any command-line arguments, so could use the simpler signature int main(void).

The main() function is magical in that we're allowed to reach the end of it without returning a value, and that's treated as success. So we can remove the return statement. If we choose to keep it regardless, we could make it clearer by using the macro EXIT_SUCCESS instead of plain 0.


Common definitions

I'm really not a fan of the typedefs of standard library types. Code would be clearer if it directly used the names we all know.

What would be valuable would be a name such as list_value_t to identify the type contained by the list, so that could be easily changed without affecting anything else. (Warning: identifiers ending in _t are reserved by POSIX, so this naming might not be appropriate in a program that uses any POSIX headers).


The linked list

When allocating memory, it's generally a good practice to use the size of the target rather than its type - like this:

    Node *node = malloc(sizeof *node);

Though it makes little difference here, it can make reading code easier when the assignment is a long way from the declaration, because we don't need to go back and find the declaration of node to check that the allocation is the correct size. And we can change the type more easily, with the allocation remaining correct.

It's good to see that the return value is tested before use. Normally, I'd say that exiting the program from a function like this is too drastic - we should instead inform the caller (who might need to take other actions, or may be able to mitigate the memory shortage). But for this simple use, it's probably acceptable.

When checking pointers for nullness, it's a matter of taste whether we explicitly compare against NULL or use the conversion of pointer to boolean that does that for us. I find the implicit version cleaner, but some do believe that the explicit conversion reinforces the type involved. I do appreciate consistency, and you're absolutely fine there!

We have ++ operator for adding 1 to a value. Although += 1 isn't wrong, it's more idiomatic to write ++list->size rather than list->size += 1. Similarly, I'd write --list->size when we remove a value.

In a real library implementation, where failed memory allocation doesn't immediately abort the program, we'd need to be a bit more careful about exactly when we modify the size - only when the action definitely happens, and not in the error path.

There's a few places where we need to special-case the "head" element for different behaviour. It's possible to avoid this by embedding a Node within the List structure. This "dummy head" node doesn't represent a value, but it can allow us uniform access regardless of position. You should be able to find reading material online to support this design.

List_remove_val() doesn't have any documentation. I had to read the implementation to discover that it removes only the first matching value, or returns error if no value matches. This is something that you should communicate clearly to users (which may well include Future You!). Other functions are generally obvious from their names and signatures.

As an alternative to List_result for List_get, consider passing a pointer to a location to copy the value to:

List_success List_get(const List *list, usize index, i32 *value)

(notice the use of const to declare that this function doesn't modify the list)

Consider adding a FILE* argument to List_print so that we can print to any stream (e.g. for writing to files or to stderr).


The array

When deleting the array, this assignment is pointless:

    (*list)->elements = NULL;

Since the very next thing we do is to free(*list), that's effectively a dead write: no valid code can access that value subsequently.

Some of the functions have names that are reserved identifiers: in particular, all the names beginning with underscore are reserved for use by the implementation and should not be defined in user programs.

The _closest_power_of_2() function isn't guaranteed to terminate for half the possible arguments. If val is greater than SIZE_MAX/2, then we'll never reach a power of two that's greater than val (p becomes zero when unsigned << overflows). We could change it so that it returns one less than a power of two, by adding 1 at each step (though the name becomes a misnomer then, and should be changed). Or we could count how many times we can shift val rightwards before it becomes zero.

We don't need separate code branches in _resize_if_needed() - realloc(NULL, n) is specified to be equivalent to malloc(n). This function should be declared static, as it's not needed outside of its translation unit.

Instead of this loop:

    for (usize i = list->size; i > position; i--)
    {
        list->elements[i] = list->elements[i - 1];
    }

we can use the standard library function:

    // untested - may contain off-by-one errors!
    memmove(list->elements + i + 1, list->elements + i,
            (list->size - position) * sizeof *list->elements);

We should use memmove() when removing elements too. This may well be faster than the explicit loop (but a good compiler will be able to convert that to memmove() when optimising).

test_list

No review of this, because most of it depends on TEST_ASSERT() which is not present.

Makefile

We need to be compiling with optimisations enabled, if our benchmarks are to be meaningful. I'd recommend some additional warnings, too:

CFLAGS += -O3
CFLAGS += -Wextra
CFLAGS += -Wwrite-strings
CFLAGS += -Warray-bounds
CFLAGS +=  -Wmissing-braces
CFLAGS += -Wconversion 
CFLAGS += -Wstrict-prototypes
CFLAGS += -fanalyzer

Consider adding a target to run the tests under Valgrind, to help identify memory leaks, use-after-free and similar issues.

The clean target could use $(RM) rather than writing out rm -f - and that may help it work on non-POSIX platforms, too.

Add the standard pseudo-targets:

.DELETE_ON_ERROR:
.PHONY: clean all test perftest
\$\endgroup\$
3
  • \$\begingroup\$ IMO all of list->size += 1, list->size++, ++(list->size) are better than ++list->size, which can too easily be confused with (++list)->size \$\endgroup\$
    – Ben Voigt
    Oct 26, 2023 at 16:11
  • \$\begingroup\$ Your proposed rewrite with memmove is missing a sizeof *(list->elements) \$\endgroup\$
    – Ben Voigt
    Oct 26, 2023 at 16:14
  • \$\begingroup\$ Thanks @Ben - slipped out of my brain when writing. I knew I had a reason for that comment! \$\endgroup\$ Oct 26, 2023 at 16:28
9
\$\begingroup\$
typedef struct Node *Node;

I strongly recommend against this. Whether something is a pointer or not (or in general, the number of indirections) is an extremely important difference that shouldn't be hidden. Call it a NodePtr or PNode if you must, although many people do not like that style of naming either..

That typedef has consequences all over the code, for example this:

void delete_node(Node *node)
{
    free(*node);
    *node = NULL;
}

Just looks nonsensical.. it's not wrong, but it looks like it is, and that's a problem by itself.

\$\endgroup\$
5
  • \$\begingroup\$ On way in which it's harmful, particularly for the public types, is that we can't easily make a pointer to constant list, for example. That's a strong motivation to keep * out of our typedefs. \$\endgroup\$ Oct 25, 2023 at 16:44
  • \$\begingroup\$ Originally, it was implemented as you suggest, but I changed it after being introduced to opaque pointers. So I just wanted to clarify: is the concept of opaque pointers a problem by itself (and am I doing it right) or is the problem using typedef'd opaque pointers in the implementation files? \$\endgroup\$ Oct 25, 2023 at 17:04
  • 1
    \$\begingroup\$ @low-altitude the way I see it (Toby may disagree), the main issue here is that this pointer type looks like a struct. If it had a name that was more suggestive of being an (opaque) pointer or "handle", then I'm fine with that. \$\endgroup\$
    – user555045
    Oct 25, 2023 at 17:30
  • \$\begingroup\$ I agree that it's clearer with "pointer" in the name, but in general I would always prefer to have a non-pointer typedef so that we can form pointers to const or volatile objects where needed. (IOW, the improved name is better but not best, in my opinion.) I would have simply typedef struct Node Node; (if anything, as this is internal) and typedef struct List List; \$\endgroup\$ Oct 26, 2023 at 6:38
  • 2
    \$\begingroup\$ @low-altitude, the key thing is that struct List is declared but not defined in the public header. That's exactly what we want, so that the client code can store a pointer to a list object, but can't see into its implementation. The typedef is just syntactic sugar to shorten the type name, and doesn't itself hide or expose anything. \$\endgroup\$ Oct 26, 2023 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.