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();
}
valgrind test
instead ofvalgrind ./test
, you will be horribly confused as to why it doesn't seem to have any memory problems. :) \$\endgroup\$ – Wayne Conrad May 30 '13 at 0:53