I've written a double-linked list library for another program I'm working on. I want to be particular about this library because I will be using it in another library, which will be used the program I'm currently working on.
I'm including the header file, source file, and a test main
file (and its output). As far as I can tell, everything works fine. But I can run additional testing, if there's a reason to do so.
Any sort of feedback would be great. I don't mind criticism.
The source file is large-ish, so I can remove the main
and test results if nobody thinks that it's necessary.
#ifndef LIST_H
#define LIST_H
/*
* list.h
*
* A simple library for using double linked lists
*
* Written by Taylor Holberton
* During June 2013
*/
typedef enum {
list_null,
list_single,
list_front,
list_back,
list_middle
} list_nodetype;
struct list_node {
void * data,
* next,
* last;
};
/* Notes:
*
* 'after' and 'before' {
*
* The words after and before indicate which way
* the list is shifting after list size modification
*
* ie: (1) - (2) - (3)
*
* putafter(2) = (1) - (2) - (n) - (3)
*
* putbefore (2) = (1) - (n) - (2) - (3)
* }
*
* 'backwards' and 'forwards' {
*
* The words 'backwards' and 'forwards' refer
* to the order of traversal the function will take.
* 'Backwards' doesn't include the current node in the
* traversal and 'forwards' does.
* }
*/
struct list_node * list_createnode (unsigned int size);
void list_setnode (struct list_node *, void * data, unsigned int size);
struct list_node * list_get (struct list_node *, int offset);
struct list_node * list_getfront (struct list_node *);
struct list_node * list_getback (struct list_node *);
struct list_node * list_putbefore (struct list_node *, unsigned int size);
struct list_node * list_putafter (struct list_node *, unsigned int size);
struct list_node * list_splitbefore (struct list_node *);
struct list_node * list_splitafter (struct list_node *);
struct list_node * list_freeforwards (struct list_node *);
void list_freebackwards (struct list_node *);
void list_free (struct list_node *);
void list_remove (struct list_node *);
unsigned int list_size (struct list_node *);
unsigned int list_countbackwards (struct list_node *);
unsigned int list_countforwards (struct list_node *);
// returns the node at which the traversal stopped (may be null)
struct list_node * list_traverse (struct list_node *, int (*callback)(void *));
struct list_node * list_traversebackwards (struct list_node *, int (*callback)(void *));
struct list_node * list_traverseforwards (struct list_node *, int (*callback)(void *));
struct list_node * list_pop (struct list_node *);
struct list_node * list_popback (struct list_node *);
struct list_node * list_popfront (struct list_node *);
struct list_node * list_pushback (struct list_node *, unsigned int size);
struct list_node * list_pushfront (struct list_node *, unsigned int size);
list_nodetype list_getnodetype (struct list_node * node);
#endif
Source file:
#include <stdlib.h>
#include <string.h>
#include "list.h"
struct list_node * list_createnode (unsigned int size){
size += sizeof (struct list_node);
struct list_node * newnode = calloc (1, size);
if (size) newnode->data = newnode + sizeof (struct list_node);
return newnode;
}
void list_setnode (struct list_node * node, void * data, unsigned int size){
if (node && node->data)
memcpy (node->data, data, size);
}
struct list_node * list_get (struct list_node * node, int offset){
switch (list_getnodetype (node)){
case list_null:
return 0;
case list_back:
if (offset > 0) return 0;
break;
case list_front:
if (offset < 0) return 0;
break;
}
if (offset > 0)
while (node && offset){
node = node->next;
offset--;
}
if (offset < 0)
while (node && offset){
node = node->last;
offset++;
}
return node;
}
struct list_node * list_getfront (struct list_node * node){
if (node) while (node->last) node = node->last;
return node;
}
struct list_node * list_getback (struct list_node * node){
if (node) while (node->next) node = node->next;
return node;
}
struct list_node * list_putbefore (struct list_node * node, unsigned int size){
struct list_node * newnode = 0,
* last = 0;
switch (list_getnodetype (node)){
case list_null:
break;
default:
if (newnode = list_createnode (size)){
last = node->last;
newnode->next = node;
newnode->last = node->last;
node->last = newnode;
if (last) last->next = newnode;
}
break;
}
return newnode;
}
struct list_node * list_putafter (struct list_node * node, unsigned int size){
struct list_node * newnode = 0,
* next = 0;
switch (list_getnodetype (node)){
case list_null:
break;
default:
if (newnode = list_createnode (size)){
next = node->next;
newnode->last = node;
newnode->next = next;
if (next) next->last = newnode;
node->next = newnode;
}
break;
}
return newnode;
}
struct list_node * list_splitbefore (struct list_node * node){
struct list_node * last = 0;
switch (list_getnodetype (node)){
case list_middle:
case list_back:
last = node->last;
last->next = 0;
node->last = 0;
last = list_getfront (last);
break;
}
return last;
}
struct list_node * list_splitafter (struct list_node * node){
struct list_node * next = 0;
switch (list_getnodetype (node)){
case list_middle:
case list_front:
next = node->next;
next->last = 0;
node->next = 0;
}
return next;
}
struct list_node * list_freeforwards (struct list_node * node){
struct list_node * temp = 0,
* last = 0;
switch (list_getnodetype (node)){
case list_middle:
case list_back:
last = node->last;
}
while (node){
temp = node->next;
free (node);
node = temp;
}
return last;
}
void list_freebackwards (struct list_node * node){
struct list_node * temp = 0;
switch (list_getnodetype (node)){
case list_middle:
case list_back:
node = node->last;
while (node){
temp = node->last;
free (node);
node = temp;
}
break;
}
}
void list_free (struct list_node * node){
switch (list_getnodetype (node)){
case list_null:
return;
case list_front:
list_freeforwards (node);
break;
case list_middle:
list_freebackwards (node); // the order of this
list_freeforwards (node); // is important
break;
case list_back:
list_freebackwards (node);
free (node);
break;
case list_single:
free (node);
break;
}
}
void list_remove (struct list_node * node){
node = list_pop (node);
if (node) free (node);
}
unsigned int list_size (struct list_node * node){
unsigned int count = 0;
switch (list_getnodetype (node)){
case list_null:
return 0;
case list_single:
return 1;
default:
count = list_countforwards (node)
+ list_countbackwards (node);
break;
}
return count;
}
unsigned int list_countbackwards (struct list_node * node){
unsigned int count = 0;
switch (list_getnodetype (node)){
case list_null:
case list_front:
break;
case list_single:
return 1;
default:
while (node = node->last)
count++;
break;
}
return count;
}
unsigned int list_countforwards (struct list_node * node){
unsigned int count = 0;
switch (list_getnodetype (node)){
case list_null:
case list_back:
break;
case list_single:
return 1;
default:
while (node){
count++;
node = node->next;
}
break;
}
return count;
}
struct list_node * list_traverse (struct list_node * node, int (*callback)(void * data)){
if (!callback || !node) return node;
node = list_getfront (node);
while (node){
if (callback (node->data)) break;
node = node->next;
}
return node;
}
struct list_node * list_traverseforwards (struct list_node * node, int (*callback)(void * data)){
if (!callback) return node;
switch (list_getnodetype (node)){
case list_null:
break;
default:
while (node){
if (callback (node->data)) break;
node = node->next;
}
}
return node;
}
struct list_node * list_traversebackwards (struct list_node * node, int (*callback)(void * data)){
if (!callback) return node;
switch (list_getnodetype (node)){
case list_null:
break;
default:
node = node->last;
while (node){
if (callback (node->data)) break;
node = node->last;
}
break;
}
return node;
}
struct list_node * list_pop (struct list_node * node){
struct list_node * next = 0,
* last = 0;
if (!node) return;
next = node->next;
last = node->last;
if (next) next->last = last;
if (last) last->next = next;
node->next = 0;
node->last = 0;
return node;
}
struct list_node * list_popback (struct list_node * node){
return list_pop (list_getback (node));
}
struct list_node * list_popfront (struct list_node * node){
return list_pop (list_getfront (node));
}
struct list_node * list_pushback (struct list_node * node, unsigned int size){
return list_putafter (list_getback (node), size); // already error-checked
}
struct list_node * list_pushfront (struct list_node * node, unsigned int size){
return list_putbefore (list_getfront (node), size);
}
list_nodetype list_getnodetype (struct list_node * node){
list_nodetype type;
if (!node) type = list_null;
else if ( node->next && !node->last) type = list_front;
else if ( node->last && !node->next) type = list_back;
else if (!node->last && !node->next) type = list_single;
else type = list_middle;
return type;
}
Example implementation:
#include <stdio.h>
#include <string.h>
#include "list.h"
#define strpsize(value) value, sizeof (value)
#define nodesize 5
int callback (void * data){
if (data) printf ("found data\n");
else printf ("found empty node\n");
return 0;
}
int callback2 (void * data){
if (data) printf ("found data traversing backwards!\n");
else printf ("found empty data traversing backwards!\n");
return 0;
}
int callback3 (void * data){
if (data) printf ("found data traversing forwards\n");
else printf ("found empty data traversing forwards!\n");
return 0;
}
int callback4 (void * data){
if (!data){
printf ("found empty slot. stopping loop now.\n");
return -1;
}
return 0;
}
int callback5 (void * data){
char * str = data;
if (data && str[0]){
printf ("found: %s\n", str);
return -1;
} else printf ("null\n");
return 0;
}
int main (){
struct list_node * head = list_createnode (nodesize),
* middle = 0,
* tail = 0,
* error = 0;
list_pushback (head, nodesize);
list_pushback (head, 0);
if (!head){
printf ("head is null\n");
list_free (head);
return -1;
}
middle = list_get (head, 1);
if (!middle){
printf ("middle node is null\n");
list_free (head);
return -1;
}
middle = list_putafter (middle, nodesize);
list_putbefore (middle, nodesize);
list_pushfront (middle, nodesize);
head = list_getfront (middle);
printf ("size of list is %d\n", list_size (head));
printf ("size after head is %d\n", list_countforwards (head));
tail = list_getback (middle);
printf ("size before tail is %d\n", list_countbackwards (tail));
printf ("size after middle is %d\n", list_countforwards (middle));
printf ("size before middle is %d\n", list_countbackwards (middle));
list_traverse (head, callback);
list_traversebackwards (head, callback2);
list_traverseforwards (head, callback3);
list_traverse (head, callback4);
middle = list_putafter (middle, sizeof ("node message"));
list_setnode (middle, strpsize ("node message"));
error = list_traverse (head, callback5);
printf ("removing text node..\n");
list_remove (error);
printf ("checking again..\n");
list_traverse (head, callback5);
printf ("freeing memory\n");
list_free (head);
printf ("exiting\n");
return 0;
}
Results:
size of list is 6
size after head is 6
size before tail is 5
size after middle is 2
size before middle is 4
found data
found data
found data
found data
found data
found data
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
found data traversing forwards
null
null
null
null
null
found: node message
removing text node..
checking again..
null
null
null
null
null
null
freeing memory
exiting
Running this with valgrind
the output is a little different and I get a lot of invalid reads (still working on that), but no memory leaks. I'm not asking anyone to figure that out, though - just a general review.
Additional notes:
The library was written so that any node within the list can be used for operations. This is advantageous when it comes to successive calls to similar areas within the list.
For example:
Instead of calling list_pushback (head, size)
multiple times, like this:
list_pushback (head, size);
list_pushback (head, size);
list_pushback (head, size);
The calls could be made like this:
tail = list_pushback (head, size);
tail = list_pushback (tail, size);
tail = list_pushback (tail, size);
Which completely eliminates the need for traversal within the function - which greatly improves the speed in loops. This might help review the code, just so you know what I was "going for".