A better approach using sentinel nodes (less special conditions):
Code:
// Sedgewick method.
#include <stdio.h>
// A "base" node.
struct node { struct node *next; };
// A list (with sentinel nodes).
struct list { struct node head, tail; };
// list initializer
#define LIST_INIT(list__) (struct list){ .head.next = &(list__).tail, .tail.next = &(list__).tail }
_Bool slist_empty( struct list *list )
{ return list->head.next == &list->tail; }
// WARNING: 'node' never can be the tail sentinel node!
// it can be any other node (including sentinel 'head').
void slist_insertAfter( struct node *node, struct node *new )
{
new->next = node->next;
node->next = new;
}
// ANY node, including both sentinels, can be used as 'node'.
// return NULL if list is empty or the "deleted" node ptr.
struct node *slist_deleteAfter( struct node *node )
{
struct node *next;
next = node->next;
if ( next == next->next )
return NULL;
node->next = next->next;
return next;
}
void slist_clear( struct list *list, void (*dtor)( void * ) )
{
while ( 1 )
{
struct node *node;
node = slist_deleteAfter( &list->head );
if ( ! node )
break;
if ( dtor )
dtor( node );
}
}
// macro for simple list iteration.
#define for_each(iter__,listptr__) \
for ( (iter__) = (listptr__)->head.next; (iter__) != (iter__)->next; (iter__) = (iter__)->next )
// macro for list iteration where we can change the list.
// using an auxiliar 'iterator'.
#define for_each_safe(iter__,tmp__,listptr__) \
for ( (iter__) = (listptr__)->head.next, (tmp__) = (iter__)->next; \
(iter__) != (iter__)->next; \
(iter__) = (tmp__) )
//--- test ---
int main( void )
{
struct list list = LIST_INIT(list);
struct node *p;
// Our internal nodes are polymorphic this way.
struct mynode {
struct node *next; // MUST BE the first member.
int value;
};
static struct mynode node[] = { { .value = 0 }, { .value = 1 }, { .value = 2 } };
// Of course we could do:
//
// struct mynode *q, *r;
// q = malloc( siseof *q ); q->value = 2; slist_insertAfter( &list.head, (struct node *)q );
// r = malloc( siseof *r ); r->value = 1; slist_insertAfter( (struct node *)q, (struct node *)r ); q = r;
// r = malloc( siseof *r ); r->value = 0; slist_insertAfter( (struct node *)q, (struct node *)r );
//
// Notice that memory allocation have nothing to do with the list internals.
slist_insertAfter( &list.head, (struct node *)&node[2] );
slist_insertAfter( (struct node *)&node[2], (struct node *)&node[1] );
slist_insertAfter( (struct node *)&node[1], (struct node *)&node[0] );
for_each( p, &list )
{
struct mynode *q = (struct mynode *)p;
printf( "%d ", q->value );
}
putchar( '\n' );
// if we had allocated the nodes we could do
// slist_clear( &list, free );
slist_clear( &list, NULL );
}