Singly-linked list library

Question

This is sort of a follow-up to a post I created about 10 days ago, but I have completed the implementation: Designing function prototypes for a singly-linked list API in C.

As I began to work on the implementation, I chose to change some of the functions and to move things around a little. This post includes source for the header, followed by the source code for the implementation.

There are 10 API functions.

Here is my number one concern: if I run Valgrind on a test file that does a lot of operations, I don't have any noticeable memory leaks, but Valgrind complains that sllist_destroy() performs an invalid free(). That is, it attempts to free something that is either already freed or not at the beginning of a heap block. This saddens me, as I cannot figure out why this is occurring. So please take careful notice of the sllist_destroy() function.

I'm also interested in opinions on opaque versus non-opaque. I have left the structs visible in the header for now, but I'm open to suggestions.

The third thing I'd like to have some feedback on is return points. I don't know how sane my choices are there, as I know some people advocate single exit points for functions.

Header: Please note that I am using Doxygen for documentation, so if you see something unfamiliar in my comments, it is because it is Doxygen syntax.

sllist.h

#ifndef SLLIST_H
#define SLLIST_H

/**
 * @file sllist.h
 * @brief Stuctures and functions for a singly-linked list API.
 *
 * The user is provided with several different functions to manipulate lists 
 * and associated data.
 */

/**
 * The node structure.
 *
 * The purpose of this structure is to actually hold the data or "payload" to be
 * stored in the list. The nodes are connected sequentially, and thus each node
 * requires a second field to store the address of the next node.
 */
struct lnode {
        void *data;
        struct lnode *next;
};
/**
 * The list structure.
 *
 * Metadata is contained here. A pointer to the first and last nodes in the list
 * allows for several operations to be performed more quickly. There is also
 * another pointer-to-node member variable for storing the location of a
 * "current" or active node that presumably will have operations performed on
 * it. Finally there is a size variable containing the total number of nodes.
 * Note that the first index of the list is considered index zero.
 */
struct sllist {
        struct lnode *head;
        struct lnode *tail;
        struct lnode *current;
        int size;
};
/**
 * Create a new list.
 *
 * Returns a pointer to a new, empty list. If allocation fails, returns NULL.
 */
struct sllist* sllist_create(void);

/**
 * Destroy a list.
 *
 * Frees the memory of the list struct and all associated nodes.
 */
void sllist_destroy(struct sllist *sllist);

/**
 * Prepend a node to the list:
 *
 * Adds a node to the front of the list. If allocation fails, returns -1,
 * otherwise returns 0.
 */
int sllist_push_front(struct sllist *sllist, void *data);

/**
 * Append node to a list.
 *
 * Adds a node to the end of the list. If allocation fails, returns -1,
 * otherwise returns 0.
 */
int sllist_push_back(struct sllist *sllist, void *data);

/**
 * Extract the first node.
 *
 * Remove the first node from the linked list, save a pointer to the data, free
 * the node (but do not free the data itself), and return a pointer to the data
 * so that it can be used. If the list is empty, returns NULL.
 */
void* sllist_pop_front(struct sllist *sllist);

/**
 * Extract the last node.
 *
 * Remove the last node from the linked list, save a pointer to the data, free
 * the node (but do not free the data itself), and return a pointer to the data
 * so that it can be used. If the list is empty, returns NULL.
 */
 void* sllist_pop_back(struct sllist *sllist);

/**
 * Step through a list.
 *
 * Changes the current node to the node after the current node. Returns 1 if
 * the current node is NULL.
 */

int sllist_step(struct sllist *sllist);

/**
 * Access data by index.
 *
 * Returns a pointer to the payload of the node at the location specified by the
 * passed index value. The passed index value is interpreted as an offset from
 * index zero, the first node of the list. Returns NULL if the list is empty or
 * the index is out of range.
 */
void* sllist_read_index(struct sllist *sllist, int index);

/**
 * Insert a node after the node at the specified index.
 *
 * Adds a node after the passed node. If allocation fails, returns -1. If the
 * node doesn't exist in the list, returns 1. Otherwise, returns 0.
 */
int sllist_insert_after(struct sllist *sllist, int index, void *data);

/**
 * Extract a node after the node at the specified index.
 *
 * Remove the specified node from the linked list, save a pointer to the data,
 * free the node (but do not free the data itself), and return a pointer to the
 * data so that it can be used. If the list is empty or the node doesn't exist
 * in the list, returns NULL. Attempting to extract after the tail will also
 * return NULL.
 */
void* sllist_extract_after(struct sllist *sllist, int index);

#endif

Implementation:

sllist.c

#include <stdlib.h>
#include "sllist.h"

struct sllist* sllist_create(void)
{
        struct sllist *sllist;
        sllist = malloc(sizeof(struct sllist));
        if (sllist != NULL) {
                sllist->head = NULL;
                sllist->tail = NULL;
                sllist->current = NULL;
                sllist->size = 0;
        }
        return sllist;
}

void sllist_destroy(struct sllist *sllist)
{
        struct lnode *save_next;
        sllist->current = sllist->head;
        while(sllist->current != NULL) {
                save_next = sllist->current->next;
                free(sllist->current->data);
                free(sllist->current);
                sllist->current = save_next;
        }
        free(sllist);
}

int sllist_push_front(struct sllist *sllist, void *data)
{
        struct lnode *lnode;
        lnode = malloc(sizeof(struct lnode));
        if (lnode == NULL)
                return -1;
        lnode->data = data;
        lnode->next = sllist->head;
        sllist->head = lnode;
        if (sllist->size == 0)
                sllist->tail = lnode;
        sllist->size++;
        return 0;

}

int sllist_push_back(struct sllist *sllist, void *data)
{
        struct lnode *lnode;
        lnode = malloc(sizeof(struct lnode));
        if (lnode ==NULL)
                return -1;
        lnode->data = data;
        lnode->next = NULL;
        if (sllist->size == 0) {
                sllist->head = lnode;
                sllist->tail = lnode;
        } else {
                sllist->tail->next = lnode;
                sllist->tail = lnode;
        }
        sllist->size++;
        return 0;
}

void* sllist_pop_front(struct sllist *sllist)
{
    if (sllist->size == 0)
        return NULL;
        void* data = sllist->head->data;
        struct lnode *save_head = sllist->head;
    if (sllist->size == 1) {
                sllist->head = NULL;
        sllist->tail = NULL;
                //Clear current since it shouldn't be used.
        sllist->current = NULL;
    } else {
        sllist->head = sllist->head->next;
    }
        free(save_head);
    sllist->size--;
    return data;
}

void* sllist_pop_back(struct sllist *sllist)
{
        if (sllist->size == 0)
                return NULL;
        void *data = sllist->tail->data;
        struct lnode *save_tail = sllist->tail;
        if (sllist->size == 1) {
                sllist->head = NULL;
                sllist->tail = NULL;
                //Clear current since it shouldn't be used.
                sllist->current = NULL;
        } else {
                struct lnode *new_tail = sllist->head;
                while(new_tail->next->next != NULL)
                        new_tail = new_tail->next;
                sllist->tail = new_tail;
                sllist->tail->next = NULL;
        }
        free(save_tail);
        sllist->size--;
        return data;
}

int sllist_step(struct sllist *sllist)
{
        if (sllist->current == NULL)
                return 1;
        else {
                sllist->current = sllist->current->next;
                return 0;
        }
}

void* sllist_read_index(struct sllist *sllist, int index)
{
        if ( ((sllist->size - index - 1) < 0 ) || (index < 0) )
                return NULL;
        struct lnode *target;
        target = sllist->head;
        for(int i = 0; i < index; i++)
                target = target->next;
        return (target->data);
}

int sllist_insert_after(struct sllist *sllist, int index, void *data)
{
        if ( ((sllist->size - index - 1) < 0 ) || (index < 0) )
                return 1;
        struct lnode *target;
        target = sllist->head;
        for(int i = 0; i < index; i++)
                target = target->next;
        struct lnode *lnode;
        lnode = malloc(sizeof(struct lnode));
        if (lnode == NULL)
                return -1;
        lnode->data = data;
        lnode->next = target->next;
        target->next = lnode;
        if (index == sllist->size - 1) //if inserting after tail
                sllist->tail = lnode;
        sllist->size++;
        return 0;

}

void* sllist_extract_after(struct sllist *sllist, int index)
{
        if ( ((sllist->size - index - 2) < 0 ) || (index < 0) )
                return NULL;
        struct lnode *target;
        target = sllist->head;
        for(int i = 0; i < index; i++)
                target = target->next;
        if (index == sllist->size - 1) //if extracting tail
                sllist->tail = target;
        void *data = target->next->data;
        struct lnode *save_obsolete = target->next;
        target->next = target->next->next;
        free(save_obsolete);
        sllist->size--;
        return data;
}

If you've made it this far, all I ask is for your most exacting criticism.

As requested, here is the portion of do-nothing code that generates the Valgrind error:

#include <stdlib.h>
#include "sllist.h"

int main(void)
{
        struct sllist *nums;
        nums = sllist_create();
        int *number;
        for(int i = 0; i < 2000; i++) {
                number = malloc(sizeof(int));
                *number = i;
                sllist_push_front(nums, number);
                sllist_push_back(nums, number);
        } 

        number = sllist_pop_front(nums); //testing multiple different things
        free(number);
        number = sllist_pop_back(nums);
        free(number);
        sllist_destroy(nums);
}

Further, if anyone is interested in seeing the glib-2.0 testing API in action, I used it in this project to see how it works. Here is my unit test code:

unit.c

#include <stdlib.h>
#include <glib.h>
#include "sllist.h"

/* Types of lists to test:
 * empty lists
 * lists with 1 element
 * lists with 2 elements
 * lists with multiple elements
 */

//Singly linked list fixture. A wrapper for sllist struct, for testing.
struct sll_fix {
        struct sllist *sllist;
};

//Prepare fixture for testing an empty list.
static void sll_setup(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_f->sllist = sllist_create();
}

static void sll_teardown(struct sll_fix *sll_f, gconstpointer ignored)
{
        sllist_destroy(sll_f->sllist);
}

//Prepare fixture for testing push_front operation.
static void sll_setup_pf(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_f->sllist = sllist_create();
        int *testp;
        testp = malloc(sizeof(int) * 10);
        for(int i = 0; i < 10; i++)
                testp[i] = i * 10;
        sllist_push_front(sll_f->sllist, testp);
}

//Prepare fixture for testing push_back operation.
static void sll_setup_pb(struct sll_fix *sll_f, gconstpointer ignored)
{
    sll_f->sllist = sllist_create();
    int *testp;
    testp = malloc(sizeof(int) * 10);
    for(int i = 0; i < 10; i++)
            testp[i] = i * 10;
    sllist_push_back(sll_f->sllist, testp);
}

//Prepare fixture for testing pop operation.
static void sll_setup_pop(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_f->sllist = sllist_create();
        int *testp_1;
        int *testp_2;
        int *testp_3;
    testp_1 = malloc(sizeof(int) * 10);
    testp_2 = malloc(sizeof(int) * 10);
    testp_3 = malloc(sizeof(int) * 10);
    for(int i = 0; i < 10; i++) {
        testp_1[i] = i * 10;
        testp_2[i] = i * 20;
        testp_3[i] = i * 30;
    }
    sllist_push_back(sll_f->sllist, testp_1);
    sllist_push_back(sll_f->sllist, testp_2);
    sllist_push_back(sll_f->sllist, testp_3);
}

//Prepare fixture for testing step operation.
static void sll_setup_step(struct sll_fix *sll_f, gconstpointer ignored)
{
    sll_f->sllist = sllist_create();
    int *testp_1;
    int *testp_2;
        int *testp_3;
    testp_1 = malloc(sizeof(int) * 10);
    testp_2 = malloc(sizeof(int) * 10);
    testp_3 = malloc(sizeof(int) * 10);
    for(int i = 0; i < 10; i++) {
        testp_1[i] = i * 10;
        testp_2[i] = i * 20;
        testp_3[i] = i * 30;
    }
    sllist_push_back(sll_f->sllist, testp_1);
    sllist_push_back(sll_f->sllist, testp_2);
    sllist_push_back(sll_f->sllist, testp_3);
}

//Prepare fixture for testing a lengthy list (100 elements.)
static void sll_setup_lengthy(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_f->sllist = sllist_create();
        int *testp;
        for(int i = 0; i < 100; i++) {
                testp = malloc(sizeof(int) * 10);
                for(int j = 0; j < 10; j++)
                        testp[j] = j * 10;
                sllist_push_back(sll_f->sllist, testp);

        }
}

//Procedure for testing an empty list
static void check_create(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup(sll_f, ignored);
        g_assert(sll_f->sllist->head == NULL);
        g_assert(sll_f->sllist->tail == NULL);
        g_assert(sll_f->sllist->current == NULL);
        g_assert(sll_f->sllist->size == 0);
}

//Procedure for testing a push_front operation on an empty list.
static void check_pf(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_pf(sll_f, ignored);
        int *int_arr;
    int_arr = sll_f->sllist->head->data;
        g_assert(sll_f->sllist->size == 1);
    for(int i = 0; i < 10; i++)
            g_assert(int_arr[i] == i * 10);
}

//Procedure for testing a push_back operation on an empty list
static void check_pb(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_pb(sll_f, ignored);
        int *int_arr;
        int_arr = sll_f->sllist->head->data;
        g_assert(sll_f->sllist->size == 1);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == i * 10);

}

//Procedure for testing a pop_front operation on a list with 3 elements.
static void check_popf(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_pop(sll_f, ignored);
        int* int_arr;
        int loop_ctr = 1;
        while ((int_arr = sllist_pop_front(sll_f->sllist))) {
                for(int i = 0; i < 10; i++)
                        g_assert(int_arr[i] == 10 * loop_ctr * i);
                loop_ctr++;
        }
}

//Procedure for testing a pop_back operation on a list with 3 elements.
static void check_popb(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_pop(sll_f, ignored);
        int* int_arr;
        int loop_ctr = 3;
        while((int_arr = sllist_pop_back(sll_f->sllist))) {
                for(int i = 0; i < 10; i++)
                        g_assert(int_arr[i] == 10 * loop_ctr * i);
                loop_ctr--;
        }
}

//Procedure for testing a step operation on a list with 3 elements.
static void check_step(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_step(sll_f, ignored);
        int *int_arr_1;
        int *int_arr_2;
        int *int_arr_3;
        int_arr_1 = sll_f->sllist->head->data;
        int_arr_2 = sll_f->sllist->head->next->data;
        int_arr_3 = sll_f->sllist->head->next->next->data;
        g_assert(sll_f->sllist->size == 3);
        for(int i = 0; i < 10; i++) {
                g_assert(int_arr_1[i] == i * 10);
                g_assert(int_arr_2[i] == i * 20);
                g_assert(int_arr_3[i] == i * 30);
        }
        int *int_arr;
        int loop_ctr = 1;
        sll_f->sllist->current = sll_f->sllist->head;
        while(sll_f->sllist->current != NULL) {
                int_arr = sll_f->sllist->current->data;
                for(int i = 0; i < 10; i++)
                        g_assert(int_arr[i] == 10 * loop_ctr * i);
                sllist_step(sll_f->sllist);
                loop_ctr++;
        }

}

//Procedure for testing a read_index operation on a list with 100 elements.
static void check_ri(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_lengthy(sll_f, ignored);
        int *int_arr;
        sll_f->sllist->current = sll_f->sllist->head;
        for(int i = 0; i < sll_f->sllist->size; i++) {
                int_arr = sllist_read_index(sll_f->sllist, i);
                for(int j = 0; j < 10; j++)
                        g_assert(int_arr[j] == j * 10);
                sllist_step(sll_f->sllist);
        }
}

//Procedure for testing an insert_after operation on a list with 100 elements.
static void check_ia(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_lengthy(sll_f, ignored);
        int *int_arr;
        int_arr = malloc(sizeof(int) * 10);
        for(int i = 0; i < 10; i++)
                int_arr[i] = 314159 * i;
        g_assert(!sllist_insert_after(sll_f->sllist, 0, int_arr));
        g_assert(!sllist_insert_after(sll_f->sllist, 1, int_arr));
        g_assert(!sllist_insert_after(sll_f->sllist, 50, int_arr));
        g_assert(!sllist_insert_after(sll_f->sllist, 102, int_arr));
        int_arr = sllist_read_index(sll_f->sllist, 0);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == i * 10);
        int_arr = sllist_read_index(sll_f->sllist, 1);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == 314159 * i);
        int_arr = sllist_read_index(sll_f->sllist, 2);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == 314159 * i);
        int_arr = sllist_read_index(sll_f->sllist, 51);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == 314159 * i);
        int_arr = sllist_read_index(sll_f->sllist, 52);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == i * 10);
        int_arr = sllist_read_index(sll_f->sllist, 103);
        for(int i = 0; i < 10; i++)
                g_assert(int_arr[i] == 314159 * i);

}

//Procedure for testing an extract_after operation on a list with 100 elements.
static void check_ea(struct sll_fix *sll_f, gconstpointer ignored)
{
        sll_setup_lengthy(sll_f, ignored);
        int *int_arr = malloc(sizeof(int) * 10);
        int_arr = sllist_extract_after(sll_f->sllist, 98);
        g_assert(sll_f->sllist->size == 99);
        g_assert(int_arr != NULL);
        int_arr = sllist_extract_after(sll_f->sllist, 98);
        g_assert(int_arr == NULL);
}

//Run tests in the order they appear in this file.
int main(int argc, char *argv[])
{
        g_test_init(&argc, &argv, NULL);
        g_test_add("/test/sll_create test", struct sll_fix, NULL, sll_setup,
                                                        check_create,
                                                        sll_teardown);
        g_test_add("/test/sll_push_front test", struct sll_fix, NULL, 
                                                        sll_setup_pf, check_pf,
                                                        sll_teardown);
        g_test_add("/test/sll_push_back test", struct sll_fix, NULL,
                                                        sll_setup_pb, check_pb,
                                                        sll_teardown);
        g_test_add("/test/sll_pop_front test", struct sll_fix, NULL, 
                                                        sll_setup_pop,
                                                        check_popf,
                                                        sll_teardown);
        g_test_add("/test/sll_pop_back test", struct sll_fix, NULL,
                                                        sll_setup_pop,
                                                        check_popb,
                                                        sll_teardown);
        g_test_add("/test/sll_step test", struct sll_fix, NULL, sll_setup_step,
                                                        check_step,
                                                        sll_teardown);
        g_test_add("/test/sll_read_index test", struct sll_fix, NULL,
                                                        sll_setup_lengthy, 
                                                        check_ri, sll_teardown);
        g_test_add("/test/sll_insert_after test", struct sll_fix, NULL,
                                                        sll_setup_lengthy, 
                                                        check_ia, sll_teardown);
        g_test_add("/test/sll_extract_after test", struct sll_fix, NULL,
                                                        sll_setup_lengthy, 
                                                        check_ea, sll_teardown);
        return g_test_run();
}

Answer 1

This is a clean and well documented API: There is little reason to have to read to the code to know how to use it. The only thing I see missing from the comment is any mention of what happens to the cursor (sllist.current) when the list is modified.

The memory error is because your code is pushing the same node onto the list twice:

sllist_push_front(nums, number);
sllist_push_back(nums, number);

In order for that to work, the second push will need its own malloc.

Multiple return points are only a problem if a function is too large for them to be easy to spot. The solution: Don't write large functions. Your functions are not too large, so it's not a problem.

The only suggestion I have would be not minor surgery, but a complete redesign. I'll mention it here not because it has anything to do with your question, but because you may not have considered it. Below the fold:

---

If you are able to switch to a doubly linked with with a dummy (root) node to serve as the head/tail, then linked list code can be simplified considerably, and most operations--such as insertion before or after an arbitrary node, or removing a node from a list--can be done very efficiently without any linear searches over the list, and with very little conditional logic.

struct Node {
  struct void *data;
  struct Node *prev;
  struct Node *next;
};

A special node is the "dummy" node, which serves as both the head and tail of the list (in this sketch I will ignore dynamic allocation). The root node is initialized like so:

void init_list(Node * node) {
  node->prev = node;
  node->next = next;
  node->data = NULL;     
}

The dummy/root node always has a NULL data pointer. A non-dummy node always has a non-NULL data pointer.

insertion after an arbitrary node is trivial:

void insert_after(Node * pred, Node * node) {
  node->pred = pred;
  node->next = pred->next;
  pred->next->pred = node;
  pred->next = node;
}

insertion before an arbitrary node:

void insert_before(Node * next, Node * node) {
  insert_after(next->pred, node);
}

The node being inserted before or after can be the dummy (root) node--the same logic works. Whether inserting at the head or tail, or before or after an arbitrary node, no list traversal is needed.

Return true if the node is a dummy (root) node. This is used to detect the end of list:

bool dummy_node(Node * node) {
  node->data == NULL;
}

One advantage of this structure is that no separate cursor (current node) is needed. Every node pointer is automatically a cursor.

Node * next_node(Node * node) {return node->next;}
Node * prev_node(Node * node) {return node->prev;}

Node * node = next_node(dummy);
while(!dummy_node(node))
  node = next_node(node);

The big disadvantage of this approach, compared to yours, is that a cursor is not integrated into the list. That means a cursor cannot be automatically invalidated when the list changes, as your code does. In every other way, I believe this approach to be simpler and more efficient to implement. It is, however, necessarily a complete redesign of the API. That's why it is out of scope in answering your original question.

Answer 2

The code looks nice and compiles cleanly. One thing that I guess you have heard before is to use braces on conditions (etc) even when strictly unnecessary.

if (lnode == NULL) {
    return -1;
}

Yes, it is ugly, but it is generally accepted as being safer. I hate doing it too, but sometimes ugly really is better...

---

I prefer to see variables initialised immediately where possible, so for example:

struct sllist *sllist;
sllist = malloc(sizeof(struct sllist));

is written:

struct sllist *sllist = malloc(sizeof(struct sllist));

---

In sllist_pop_back, I'd prefer to see the loop that finds the end of the list extracted into a separate static inline function.

---

Your last three functions all contain an expression that determines whether index exceeds the list size:

if ( ((sllist->size - index - 1) < 0 ) || (index < 0) )

Wouldn't it be easier to say:

if ((index >= sllist->size) || (index < 0))

---

Your last three functions all contain code to find a given entry in the list:

struct lnode *target = sllist->head;
for (int i = 0; i < index; i++) {
    target = target->next;
}

This should really be extracted into a static function.

---

Nits:

• sllist_read_index return statement has brackets. No other function has them.
• I see no purpose in the current field. Nothing really uses it.
• The structures are not opaqe (and hence are open to client manipulation)
• You free all of the data pointers when destroying the list, which assumes that the data was dynamically allocated. Best to state this restriction in the interface.
• How does the client determine which 'index' to use in those functions taking an index?