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 *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->tail = NULL;
sllist->current = NULL;
sllist->size = 0;
}
return sllist;
}

void sllist_destroy(struct sllist *sllist)
{
struct lnode *save_next;
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;
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->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;
if (sllist->size == 1) {
sllist->tail = NULL;
//Clear current since it shouldn't be used.
sllist->current = NULL;
} else {
}
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->tail = NULL;
//Clear current since it shouldn't be used.
sllist->current = NULL;
} else {
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;
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;
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;
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;
}


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->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;
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;
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;
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;
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;
for(int i = 0; i < sll_f->sllist->size; 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));
for(int i = 0; i < 10; i++)
g_assert(int_arr[i] == i * 10);
for(int i = 0; i < 10; i++)
g_assert(int_arr[i] == 314159 * i);
for(int i = 0; i < 10; i++)
g_assert(int_arr[i] == 314159 * i);
for(int i = 0; i < 10; i++)
g_assert(int_arr[i] == 314159 * i);
for(int i = 0; i < 10; i++)
g_assert(int_arr[i] == i * 10);
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);
sll_setup_pf, check_pf,
sll_teardown);
sll_setup_pb, check_pb,
sll_teardown);
sll_setup_pop,
check_popf,
sll_teardown);
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);
sll_setup_lengthy,
check_ri, sll_teardown);
sll_setup_lengthy,
check_ia, sll_teardown);
sll_setup_lengthy,
check_ea, sll_teardown);
return g_test_run();
}

• I don't see a problem with sllist_destroy. Do you have a minimal program that uses your library to elicit the Valgrind complaint? If you do, could you please attach it? – Wayne Conrad May 29 '13 at 16:59
• Hi Wayne, I've added the code that causes the invalid free() error. Thanks for your time. – oddlogic May 29 '13 at 20:27
• OK, I see the memory error. I'll amend my answer. By the way, I can tell you from personal experience that if you run valgrind with valgrind test instead of valgrind ./test, you will be horribly confused as to why it doesn't seem to have any memory problems. :) – Wayne Conrad May 30 '13 at 0:53

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.

• Thank you for you well-reasoned reply. I am glad that you pointed out that the documentation makes no mention of what happens to the current node. I will add this to the documentation. You have also brought to my attention that in the function sllist_extract_after() I forget to check whether I need to invalidate current, since my intention was to assign a NULL pointer to any invalid node references to make errors more obvious. Regarding your redesign, I have definitely given it much thought, and I actually intended from the beginning to do a full API suite involving dllists, hashes, etc. – oddlogic May 29 '13 at 17:43
• About the memory error: Wow, now I feel silly. I don't know why I didn't realize that. I just wrote the test very quickly and thought, hm, I'll just reuse this same data. Yeah, thanks for keeping me sane. – oddlogic May 30 '13 at 2:49
• @oddlogic, I'll bet you didn't feel as silly as I felt when I realized I had been running Valgrind on a Unix utility instead of your code. :) I'm just glad we got it sorted out. By the way, your code caused gcc to emit no warnings even on the strict settings I prefer. Nice job! – Wayne Conrad May 30 '13 at 4:14
• Thanks for the kind words. I usually compile with -Wall as well. Also, I didn't even know there was a utility called 'test', but I typed 'man test', and there it was! – oddlogic May 30 '13 at 7:31

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?
• All solid advice. I'll start with the "nits": I believe my rationale for 'index' is that the user conceivably have their own reasons for accessing a particular index. For example, if the list is created with some kind of order, say a list of prime numbers or something, index 6 would contain the 7th prime number. I think I am going to add some accessor functions and move the structs into the implementation. This would make current more sensible because it would provide an opaque way to move through the list, via sllist_step. – oddlogic Jun 1 '13 at 18:18
• The condition if (abs(index) >= sllist->size) treats negative values greater than or equal to -index as acceptable, but if I change it to if ((abs(index) >= sllist->size) || (index < 0) then I believe we've created a statement that more clearly expresses my intent than if ( ((sllist->size - index - 1) < 0 ) || (index < 0) ) On the other hand, I then have to include cmath.h. I don't believe this is much of a problem, however. What are your thoughts? Everything else you've said I more or less totally agree with. – oddlogic Jun 1 '13 at 18:28
• oops! Yes, abs is clearly wrong. You could use (unsigned) index >= sllist->size but that will provoke a conversion warning. I will change the answer... – William Morris Jun 1 '13 at 23:40