2
\$\begingroup\$

I want to use it when some function needs to return a list of something. Is it working as I think it should or is there undefined behavior somewhere? What I really tried to achieve is something like a templated <list> from C++ - for any type. I'm not sure if there is a standard solution/include/library for this.

list.h

#pragma once

#include <stddef.h>

struct list_handler
{
    struct list_node *head;
    struct list_node *tail;
    size_t count;
};

struct list_node
{
    void *data;
    struct list_node *next;
};

void list_init(struct list_handler *list);
void list_add(struct list_handler *list, void *data);
void list_free(struct list_handler *list);
void list_foreach(struct list_handler *list, void (*foreach_function)(void *));

list.c

#include "list.h"

#include <stdlib.h>

void list_init(struct list_handler *list)
{
    list->head = NULL;
    list->tail = NULL;
    list->count = 0;
}

void list_add(struct list_handler *list, void *data)
{
    struct list_node *new_node = malloc(sizeof(struct list_node));

    new_node->data = data;
    new_node->next = NULL;

    if (list->count > 0)
    {
        list->tail->next = new_node;
    }
    else
    {
        list->head = new_node;
    }

    list->tail = new_node;

    ++list->count;
}

void list_free(struct list_handler *list)
{
    struct list_node *current = list->head;
    struct list_node *previous;

    while (current != NULL)
    {
        previous = current;
        current = current->next;

        free(current);

        list->head = current;
        --list->count;
    }

    list->tail = NULL;
}

void list_foreach(struct list_handler *list, void (*foreach_function)(void *))
{
    struct list_node *current = list->head;

    while (current != NULL)
    {
        (*foreach_function)(current->data);
        current = current->next;
    }
}

Usage:

void list_print(void *data)
{
    int *temp = (int*) data;
    printf("%d\n", *temp);
}

void list_free_data(void *data)
{
    int *temp = (int*) data;
    free(temp);
    data = NULL;
}

int main(int argc, char *argv[])
{
    struct list_handler list;
    list_init(&list);

    for (size_t i = 0; i < 3; ++i)
    {
        int *data = malloc(sizeof(int));
        *data = i;
        list_add(&list, data);
    }

    list_foreach(&list, list_print);
    list_foreach(&list, list_free_data);

    list_free(&list);

    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ The only direct question is "Is it working as I think it should or is there undefined behavior somewhere?". Posts here should include "working" code, so please state another review goal than that. \$\endgroup\$ Commented Feb 19, 2018 at 17:08
  • \$\begingroup\$ Is the "quick" in the title referring to runtime speed, or ease of development, or something else? \$\endgroup\$ Commented Feb 19, 2018 at 17:41

2 Answers 2

Reset to default
2
\$\begingroup\$

  1. "What I really tried to achieve is something like a templated <list> from C++ - for any type." Approach has limited applicability in that it only well handles pointers to object types, not any type. Still, this limited use is sufficient for many applications.

  2. size_t count member is unnecessary with current function interface as only its zero-ness is tested and that may be determined by other simple code.

  3. Advanced: With current function interface, keeping track of both head and tail is not needed. A tail pointer is sufficient. Let the tail point to the head of the list rather than NULL. Now struct list_handler can be a simple pointer instead. list_init(); could be replaced with struct list_handler *list = NULL;

  4. Definition of struct list_node is not needed in list.h. Move to list.c to simplify user's view of this list_... code.

  5. Like mentioned by @Joop Eggen, list_foreach should have a state variable. Also having a return value that stops the loop when non-zero is very useful. Maybe an int or a pointer to data. Consider using this to perform a search.

    int list_foreach(struct list_handler *list, 
    int (*foreach_function)(void *state, void *data), void *state) {
  struct list_node *current = list->head;
  while (current != NULL) {
    int i = (*foreach_function)(state, current->data);
    if (i) {
      return i;
    } 
    current = current->next;
  }
  return 0;
}

  6. Like free() accepts free(NULL), list_free() should also tolerate list_free(NULL).

\$\endgroup\$
2
\$\begingroup\$

The list_free has a small error. Whether the function should free the list is up to the API design. Maybe you did not want dangling pointers. Then the name should be better list_clear.

void list_free(struct list_handler *list)
{
    struct list_node *current = list->head;
    struct list_node *previous;

    while (current != NULL)
    {
        previous = current;
        current = current->next;

        //- free(current);
        free(previous); //+

        list->head = current;
        --list->count;
    }

    list->tail = NULL;
    free(list); //+
}

Freeing the data is a non-list issue, misleading, especially with a void*.

void list_free_data(void *data)
{
    //int *temp = (int*) data;
    //free(temp);
    //data = NULL;
    free(data);
}

Assigning NULL to data has no effect.

However if you want to free the list with freeing the data:

list_foreach(list, free);
list_free(list);
free(list);

The list_foreach is limited as it must work with side-effects, storing results or other context in global variables. Better provide a for-each with an additional parameter. So bad coding style is not inevitable.

For the remainder: I like APIs to provide a full set of operations, that is with a remove too.

\$\endgroup\$
2
  • \$\begingroup\$ First of all, thanks for the bug fix with free(current) to free(previous) - totally overlooked this. I have several questions about list_free_data fixes: 1) Is it safe to free a void* pointer in list_free_data? As far as I know, free has no way of knowing the size of the underlying object if a pointer is a void*. This is why I created list_free_data instead of passing free from stdlib.h directly - to handle the type. 2) About assigning NULL - that way I signal to a higher level that the memory has been freed. \$\endgroup\$ Commented Feb 19, 2018 at 10:30
  • 1
    \$\begingroup\$ Memory allocation has its own administration of sizes. Hence void* is fine, and NULL does not need to be assigned, other than prevent the usage of freed pointers ("dangling pointers"). Note: free of char* would not free one char, but could be done on an array. For concepts C is not that pedagogical, as opposed to Pascal/Modula-2. \$\endgroup\$ Commented Feb 19, 2018 at 10:59

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.