generalised linked list routines - opinion appreciated

[Steve Lambert]

Hi,

I've knocked up a number of small routines to create and manipulate a linked
list of any structure. If anyone could take a look at this code and give me
their opinion and details of any potential pitfalls I'd be extremely
grateful.

Cheers

Steve

ll.h
/*
USAGE NOTES FOR CALLING MODULES

-- include the linked list module header file
#include "ll.h"

-- declare any structure that is going to make up the linked list
eg.
struct PERSONAL_DETAILS
{
char forename[20];
char surname[20];
short house_number;
char street[20];
char town[20];
char county[20];
char phone[12];
};

-- declare a variable of this type
eg.
PERSONAL_DETAILS person;

-- declare a pointer to the linked list
eg
LINKED_LIST_TYPE *people = NULL;

-- create the actual linked list
eg
ll_create( &people ); NB The ADDRESS of the pointer is passed

-- populate your structure with appropriate details
eg
strcpy(person.forename, "steve");
strcpy(person.surname, "lambert");
etc ...

-- add the structure to the end of the linked list
eg
ll_append( people, &person, sizeof(PERSONAL_DETAILS) );

-- to loop through the linked list elements
-- reset internal linked list variables to point to the start of the
linked list
eg
ll_start( people );

-- loop through all the elements
eg
while ( ll_next(people) )
{
-- get the data
eg
people = (PERSONAL_DETAILS *)ll_data(people);
}

-- finally, deallocate all allocated memory
eg
ll_destroy( &people ); NB The ADDRESS of the pointer is passed

*/

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

struct LINKED_LIST_TYPE
{
NODE_TYPE *header;
NODE_TYPE *current_node;
NODE_TYPE *last_node;
long number_of_nodes;
long node_number;
};


void ll_create( LINKED_LIST_TYPE **ptr );

void ll_destroy( LINKED_LIST_TYPE **linked_list );

void ll_append( LINKED_LIST_TYPE *linked_list,
void *data,
size_t data_size );

short ll_start ( LINKED_LIST_TYPE *linked_list );

void *ll_data ( LINKED_LIST_TYPE *linked_list );

short ll_next ( LINKED_LIST_TYPE *linked_list );

ll.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ll.h"
#include "debug_refdec.h"

void ll_create( LINKED_LIST_TYPE **linked_list_ptr )
{
LINKED_LIST_TYPE *linked_list;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_create - start\n");
}
/* ****************************** */

/* allocate space for the linked list structure */
linked_list = (LINKED_LIST_TYPE *) malloc( sizeof(LINKED_LIST_TYPE) );
if ( !linked_list )
{
exit( EXIT_FAILURE );
}
//printf("Allocating linked list : %p\n",linked_list);

/* initialise the linked list elements */
linked_list->header = NULL;
linked_list->current_node = NULL;
linked_list->last_node = NULL;
linked_list->number_of_nodes = 0;
linked_list->node_number = 0;

*linked_list_ptr = linked_list;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_create - end\n");
}
/* ****************************** */
}

void ll_destroy( LINKED_LIST_TYPE **linked_list )
{
NODE_TYPE *current_node = NULL;
NODE_TYPE *next_node = NULL;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_destroy - start\n");
}
/* ****************************** */

/* check that the linked list has been initialised */
if ( !*linked_list )
{
//printf("ERROR : linked list not initialised\n");
exit( EXIT_FAILURE );
}

current_node = (*linked_list)->header;

while ( current_node )
{
next_node = current_node->next;

//printf("Freeing node data : %p\n", current_node->data);
free( current_node->data );
//printf("Freeing node : %p\n", current_node);
free( current_node );

current_node = next_node;
}
//printf("freeing linked list : %p\n", *linked_list);
free( *linked_list );


*linked_list = NULL;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_destroy - end\n");
}
/* ****************************** */

}

void ll_append( LINKED_LIST_TYPE *linked_list,
void *data,
size_t data_size )
{
NODE_TYPE *new_node = NULL;
void *node_data = NULL;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_append - start\n");
}
/* ****************************** */

/* check that the linked list has been initialised */
if ( !linked_list )
{
//printf("ERROR : linked list not initialised\n");
exit( EXIT_FAILURE );
}

/* allocate space for the new node */
new_node = (NODE_TYPE *) malloc( sizeof(NODE_TYPE) );
if ( !new_node )
{
//printf("ERROR : failed to allocate space for new node\n");
exit( EXIT_FAILURE );
}
//printf("Allocating node : %p\n", new_node);

/* allocate space for the node data */
new_node->data = malloc( data_size );
if ( !new_node->data )
{
//printf("ERROR : failed to allocate space for new node data\n");
exit( EXIT_FAILURE );
}
//printf("allocating node data : %p\n", new_node->data);
/* copy the data to the node */
memcpy( new_node->data, data, data_size );

/* note that this is the last node in the linked list */
new_node->next = NULL;

/* append the node to the linked list */
if ( linked_list->number_of_nodes == 0 )
{
/* this is the first node in the linked list */
linked_list->header = new_node;
linked_list->last_node = new_node;
linked_list->number_of_nodes = 1;
}
else
{
/* add the node to the end of the linked list */
linked_list->last_node->next = new_node;
linked_list->last_node = new_node;
linked_list->number_of_nodes++;
}

/* ****************************** */
if (debug_level == 1)
{
printf("ll_append - end\n");
}
/* ****************************** */
}

short ll_start ( LINKED_LIST_TYPE *linked_list )
{
short status;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_start - start\n");
}
/* ****************************** */

if ( !linked_list )
{
/* linked list has not been initialised */
status = 0;
}
else if ( linked_list->number_of_nodes == 0 )
{
/* linked list has no entries */
status = 0;
}
else
{
/* point to the start of the linked list */
linked_list->current_node = NULL;
linked_list->node_number = 0;
status = 1;
}

/* ****************************** */
if (debug_level == 1)
{
printf("ll_start - end\n");
}
/* ****************************** */

return ( status );
}

void *ll_data ( LINKED_LIST_TYPE *linked_list )
{
/* ****************************** */
if (debug_level == 1)
{
printf("ll_data - start\n");
}
/* ****************************** */

/* check that the linked list has been initialised */
if ( !linked_list )
{
//printf("ERROR : linked list not initialised\n");
exit( EXIT_FAILURE );
}

/* check that the linked list has entries */
if ( linked_list->number_of_nodes == 0 )
{
//printf("ERROR : linked list has no data\n");
exit( EXIT_FAILURE );
}

/* ****************************** */
if (debug_level == 1)
{
printf("ll_data - end\n");
}
/* ****************************** */

return( linked_list->current_node->data );
}

short ll_next ( LINKED_LIST_TYPE *linked_list )
{
short status;

/* ****************************** */
if (debug_level == 1)
{
printf("ll_next - start\n");
}
/* ****************************** */

/* check that the linked list has been initialised */
if ( !linked_list )
{
//printf("ERROR : linked list not initialised\n");
exit( EXIT_FAILURE );
}

/* check that the linked list has entries */
if ( linked_list->number_of_nodes == 0 )
{
//printf("ERROR : linked list has no data\n");
exit( EXIT_FAILURE );
}

if ( !linked_list->current_node )
{
/* at the start of the list */
linked_list->current_node = linked_list->header;
linked_list->node_number++;
status = 1;
}
else if ( linked_list->current_node != linked_list->last_node )
{
/* part way through the list */
linked_list->current_node = linked_list->current_node->next;
linked_list->node_number++;
status = 1;
}
else
{
/* at end of list */
status = 0;
}

/* ****************************** */
if (debug_level == 1)
{
printf("ll_next - end : status = %d\n", status);
}
/* ****************************** */

return ( status );
}

 

[CBFalconer]

I've knocked up a number of small routines to create and
manipulate a linked list of any structure. If anyone could take
a look at this code and give me their opinion and details of any
potential pitfalls I'd be extremely grateful.

.... snip monstrous code ...

Much too complex. Deal with the essence of a list first. Since
you don't know what the data it carries is, use a void* to point
to that.

typedef struct node {
struct node *next;
void *datum;
} node, *nodeptr;

Now you can write code to create nodes and nodeptrs. Their size
is known and they can be passed back and forth. Only a code
module that actually has to deal with datum need know what it
consists of. The list processing proper shouldn't care at all.

When you create a node initialize its contents to NULLs. Go on
from there.

For testing your basic mechanisms, you can change datum to an int
and not worry about the actual usage.

 

[Steve Lambert]

Thanks very much for the comments. I'd just like to expand a little though :

The intention is to create a pseudo abstract data type giving other modules
/ users access to a set of linked list manipulation routines without them
having to mess about building the linked list themselves.

The publicly available routines ll_create, ll_append etc allow a user to
create linked list structures using a set of robustly tested routines
without having to think of building the linked list structure themselves or
knowing the details of the implementation. The given routines have been
generalised to handle any structures that a user might define. I just
wondered if there were any pitfalls, specifically with casting void* to the
user defined structures.

Many thanks

Steve

 

[Alberto =?iso-8859-1?Q?Gim=E9nez?=]

El Fri, 03 Sep 2004 12:11:31 GMT, Steve Lambert escribió:

Hi,

I've knocked up a number of small routines to create and manipulate a linked
list of any structure. If anyone could take a look at this code and give me
their opinion and details of any potential pitfalls I'd be extremely
grateful.

Hello! I implemented some months ago a module very near to yours. If you
want I can send it to your personal email address.

The main differences are that I request functions to duplicate and free
objects at list creation time and that I use an opaque object
definition in the header, so the module's user don't know how is it
implemented (and therefore can't change any internal variable).

 

[CBFalconer]

The intention is to create a pseudo abstract data type giving
other modules / users access to a set of linked list manipulation
routines without them having to mess about building the linked
list themselves.

The publicly available routines ll_create, ll_append etc allow a
user to create linked list structures using a set of robustly
tested routines without having to think of building the linked
list structure themselves or knowing the details of the
implementation. The given routines have been generalised to
handle any structures that a user might define. I just wondered
if there were any pitfalls, specifically with casting void* to
the user defined structures.

Don't toppost. Do snip. Your reply belongs after, or intermixed
with, the quoted material after removing anything that is not
germane. Failure to do this will get you ignored.

This is C. There is no need to ever cast a void* pointer. You
pass it onwards to a routine that knows what to do with it. For
example, you might make a function such as:

void *ll_createnode(void *gubris)
{
ll_nodeptr node;

if (!(node = malloc(sizeof *node))) {
/* out of memory error */
}
else {
node->next = NULL;
node->datum = makecopy(gubris);
}
return node;
}

where makecopy is a routine that you setup for your own particular
data set. It may well be a function pointer that was passed in to
the code that initialized the linked list. Now lets see what
makecopy should do, remembering that it is NOT part of the linked
list manipulation package, but code written by the user of that
package. That user knows that the gubris he passed to ll_create
is really a char *, because he just wants to store a string.

void *makecopy(void *item)
{
char *theitem = item; /* because this knows about it */
char *newcopy;

if ((newcopy = malloc(strlen(item) + 1))) {
strcpy(newcopy, item);
}
return newcopy;
}

without a cast in sight. It will return NULL if out of memory.
The ll package knows about ll_nodes, the user code doesn't. The
user code knows about gubris, the ll package doesn't. The use of
void* pointers allows this isolation.

After this you can write something like:

void ll_append(void *newnode, void* *listbase)
{
ll_node *new = newnode;
ll_node *base = *listbase;
ll_node *last;

if (!base) /* empty list */
*listbase = new;
else {
while (base) { /* find tail */
last = base;
base = base->next;
}
last->next = new;
}
}

All totally untested code. I probably would do it differently
anyhow. The first thing to write is the .h file that specifies
the interconnection.

If you want to see a package that does this sort of thing
extensively (and incidentally some of the example uses use linked
lists), see:

<http://cbfalconer.home.att.net/download/hashlib.zip>

and IMNSHO, does an excellent job of it <blowing on fingernails>.

 

[Paul Hsieh]

I've knocked up a number of small routines to create and manipulate a linked
list of any structure. If anyone could take a look at this code and give me
their opinion and details of any potential pitfalls I'd be extremely
grateful.

Its a well motivated idea. But it has a few weakness that you should
consider seriously.

----

1) By putting the iterator state in the linked list header, you make
the process of iteration non-reentrant. I.e., you can have only one
thread of execution iterating through the linked list at once.
Suppose you had a nested loop in which the outer loop was iterating
over that linked list, and the inner loop was as well. Because you
have only one iterator per linked list you can't do it.

2) For generic data you cannot assume that node data is "shallow".
I.e., in your destroy function you are just straight freeing the
entries -- but this may be an incorrect mechanism for deallocating the
object in general. This has the further problem of disallowing node
data aliases (which *you* may not like, but its not something you
should impose on a truly generic solution.) Since (unlike C++) C
doesn't have a concept of type associated destructors the programmer
ends up having to manage data deallocation in a programmer defined way
anyways. I.e., you should not try to decide how their raw data is
managed.

The programmer can always iterate through the linked list themselves,
destroy each data entry as they see fit, then call your routines just
to do container destruction. You can't do better in C on a generic
container type.

3) Your interface is not type safe. What I mean is if you a pair of
lists on two different types, and you mix them up you will be in
undefined behavior land before you know it. You are exposing the
genericness of your construction to the programmer who will be forced
to do correct casting everywhere, which kind of makes the whole
concept of a "type safe language" kind of useless.

----

I have developed a kind of generic linked list myself for
demonstration purposes (from a more general technique) which solves
all of the above problems which you might like to take a look at. The
general idea is to create a generic linked list module, but then wraps
it totally with type-safe wrapper functions (generated inline by
macros.) I also split out the iterator as a seperate entity so that
you can have several simultaneously running iterators. Its a bit much
to post all here, so I'll just give a link to it on my website:

http://www.azillionmonkeys.com/qed/ll.zip

 

[Paul Hsieh]

Could you possibly explain this for me in more detail [...]

Ok, the first thing to understand in the code are just the generic linked
list routines: utilGenLinkedList<function>. Hopefully these are fairly
straightforward as they correspond roughly to the code you wrote. Except
for explicit new and destroy functions, they provide everything you need
to deal with linked lists. You could use these functions directly for
managing linked lists if you wanted to. But they suffer the problem that
they treat all incoming data as void *'s. That means you could
inadvertently mix in non-homogeneous data into a list without any hint
from the compiler about the type mismatch.

Ok, so the point of the macros is to create wrapper functions of the form:

llo_<ptypeName>_<function>

Look up the "##" concatenation preprocessor mechanism if you are
unfamilliar with it. Its the key to being able to build these functions
on the fly with just a macro call (that's how the llo__glue*() macros
work). Ok, so as an example this is one of the core functions:

int utilGenLinkedListAppend (struct genLinkedList * gl, void * e);

After invoking the macro llTemplateImpl(pbio) one of the functions we get
implemented for us is:

int llo_pbio_append (llOf_pbio g, pbio e);

Which is basically functionally equivalent to the generic function above,
except that its parameters are declared with specific types which
correspond to the type "pbio". The type pbio is just something I created
in test.c meaning "pointer to biography information" -- the point is that
the name has been typedef'ed and its a pointer to a data type where the
real information is (in this case a struct biography.) This allows the
llTemplateImpl macro to do its magic and build up legally generated C
wrapper function names for the functions and the specific linked list
types. So you can't mismatch the types through this interface -- its
typesafety will be enforced by the compiler.

The point is that all the type safety concerns get taken care of with
these wrapper functions, and risk from the danger of using a generic type
unsafe void * underlying mechanism is hidden in the one time
implementation of the llTemplateImpl macro where all the casting has been
done.

or point me in the direction of some appropriate reading material.

There is nowhere for me to point you to other than myself. The closest
this kind of thing comes to in programming is, in fact, C++'s templates
which, of course, its borrowing farily heavily from. People in the C
community tend not to program this way (to their peril, IMHO.)