#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <assert.h>
#include <string.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct listnode
{
  struct listnode *next;
  struct listnode *prev;
} listnode_t;

/* Circular linked list with a head */
typedef struct linkedlist
{
  listnode_t *node;
} linkedlist_t;


#define LISTNODE( n )                                                         \
  ( (listnode_t*)(n) )

#define LIST_NEXT( n )                                                        \
  ( (__typeof__(n)) LISTNODE(n)->next )

#define LIST_PREV( n )                                                        \
  ( (__typeof__(n)) LISTNODE(n)->prev )

#define LIST_FIRST(list)                                                      \
  ( LIST_NEXT((list)->node) )

#define LIST_LAST(list)                                                       \
  ( LIST_PREV((list)->node) )

#define LIST_SENTINEL(list)                                                   \
  ( (list)->node )

#define LIST_EMPTY(list)                                                      \
  ( LIST_FIRST(list) == LIST_SENTINEL(list) )

#define for_each_list_element(list, pnode)                                    \
  for ( (pnode) =  (__typeof__(pnode)) LIST_FIRST(list);                      \
        (pnode) != (__typeof__(pnode)) LIST_SENTINEL(list);                   \
        (pnode) =  (__typeof__(pnode)) LIST_NEXT(pnode) )



static inline listnode_t *
__list_add( const linkedlist_t *list, listnode_t *node )
{
  assert( list != NULL );
  assert( list->node != NULL );
  assert( node != NULL );

  listnode_t *first = list->node;
  listnode_t *last = list->node->prev;

  node->next = first;
  first->prev = node;

  node->prev = last;
  last->next = node;

  return node;
}

/**
 * Append value to linked list.
 */
#define list_add( list, type )                                                \
   ({                                                                         \
      type *node = calloc( 1, sizeof(type) );                                 \
      (type *)__list_add( (list), LISTNODE(node) );                           \
    })


static inline listnode_t *
__list_insert_in_order( const linkedlist_t *list, listnode_t *node,
			int (*cmp)( const listnode_t *, const listnode_t *) )
{
  assert( list != NULL );
  assert( list->node != NULL );
  assert( node != NULL );
  assert( cmp != NULL );

  listnode_t *p;

  /* try to anticipate insert of already ordered elements */
  if ( ( LIST_EMPTY( list ) ) || ( cmp( LIST_LAST( list ), node ) < 0 ) )
    {
      return __list_add( list, node );
    }

  for_each_list_element( list, p )
    {
      int ret = cmp( p, node );
      if ( ret >= 0 )
	{
	  node->next = p;
	  node->prev = p->prev;

	  p->prev->next = node;
	  p->prev = node;
	  return node;
	}
    }

  assert( 1 == 0 );
  return NULL;
}

/**
 * Insert node in order in the linked list.
 */
#define list_insert_in_order( list, node, cmp )                               \
   ({                                                                         \
      typeof(node) *_n = calloc( 1, sizeof(node) );                           \
      *_n = (node);                                                           \
      (typeof(node)*)__list_insert_in_order( (list), LISTNODE(_n), (cmp) );   \
    })


/**
 * Removes node from list and free() its memory.
 */
static inline void
__list_del( const linkedlist_t *list, listnode_t *node )
{
  assert( list != NULL );
  assert( list->node != NULL );
  assert( node != NULL );
  assert( list->node != node ); /* avoid removing the head */

  listnode_t *prev = node->prev;
  listnode_t *next = node->next;
  prev->next = next;
  next->prev = prev;
  memset( node, 0, sizeof(listnode_t) );
  free( node );
}
#define list_del( list, node ) __list_del( (list), LISTNODE(node) )


static inline linkedlist_t *
list_new()
{
  linkedlist_t *list = ( linkedlist_t* ) calloc( 1, sizeof(linkedlist_t) );
  listnode_t *node = ( listnode_t * ) calloc( 1, sizeof(listnode_t) );
  node->next = node;
  node->prev = node;

  list->node = node;
  return list;
}

static inline void
list_clear( const linkedlist_t *list )
{
  assert( list != NULL );
  assert( list->node != NULL );

  listnode_t *node, *oldnode=NULL;

  for_each_list_element( list, node ) {
    if ( oldnode != NULL )
      list_del( list, oldnode );
    oldnode = node;
  }

  if ( oldnode != NULL )
    list_del( list, oldnode );

}

static inline void
list_free( linkedlist_t *list )
{
  assert( list != NULL );
  assert( list->node != NULL );

  list_clear( list );
  free( list->node );
  free( list );
}


#endif /* LINKEDLIST_H */