Thread: List

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 );
}