/*!
 * \file libdotat/slist.h
 *
 * \brief Singly-linked lists.
 *
 * Code that doesn't need all the functionality of doubly-linked lists
 * can gain some space and time performance improvements by using this
 * header as a drop-in replacement for list.h provided they use only
 * the following functions:
 *
 * \li list_types()
 * \li list_typedefs()
 * \li list_functions()
 * \li void NAME_init(t_root *root);
 * \li void NAME_init_link(t_elem *elem);
 * \li t_elem *NAME_first(t_root *root);
 * \li t_elem *NAME_next(t_elem *elem);
 * \li bool NAME_empty(t_root *root);
 * \li bool NAME_istail(t_elem *elem);
 * \li bool NAME_attail(t_elem *elem);
 * \li bool NAME_islast(t_elem *elem);
 * \li void NAME_insert_after(t_elem *elem, t_elem *new);
 * \li void NAME_insert_first(t_root *root, t_elem *new);
 * \li t_elem *NAME_remove_first(t_root *root);
 * \li void NAME_remove_next(t_elem *elem);
 * \li int NAME_length(t_root *root);
 * \li t_root *NAME_create(void);
 * \li void NAME_destroy(t_root *root);
 *
 * \author Tony Finch <dot@dotat.at>
 * \date   2001-2002
 *
 * You may - at your own risk - do whatever you want with this code.
 *
 * $dotat: progetc/libdotat/slist.h,v 1.22 2002/04/13 04:56:19 fanf Exp $
 */

#ifndef SLIST_H
#define SLIST_H

#include <sanity.h>

IDENT(slist_hc, "$Copyright: (C) 2001, 2002 Tony Finch (dot@dotat.at) $");
IDENT(slist_hv, "$dotat: progetc/libdotat/slist.h,v 1.22 2002/04/13 04:56:19 fanf Exp $");

#include <stdbool.h>

#include <dotat/xalloc.h>


/*! \hideinitializer */
#define list_types(root_tag, elem_tag, link_tag)			\
									\
struct link_tag { struct elem_tag *next; };				\
struct root_tag { struct link_tag  head; };				\
									\
struct list__hack


/*! \hideinitializer */
#define list_typedefs(t_root, t_elem, t_link)				\
									\
list_types(t_root, t_elem, t_link);					\
									\
typedef struct t_root t_root;						\
typedef struct t_elem t_elem;						\
typedef struct t_link t_link;						\
									\
struct list__hack


/*! \hideinitializer */
#define list_functions(name, t_root, t_elem, link)			\
									\
/* initializers */							\
static inline void name##_init(t_root *root) {				\
	root->head.next = NULL;						\
}									\
static inline void name##_init_link(t_elem *elem) {			\
	elem->link.next = NULL;						\
}									\
									\
/* accessor functions */						\
static inline t_elem *name##_first(t_root *root) {			\
	return(root->head.next);					\
}									\
static inline t_elem *name##_next(t_elem *elem) {			\
	return(elem->link.next);					\
}									\
									\
/* predicates */							\
static inline bool name##_empty(t_root *root) {				\
	return(root->head.next == NULL);				\
}									\
static inline bool name##_istail(t_elem *elem) {			\
	return(elem == NULL);						\
}									\
static inline bool name##_attail(t_elem *elem) {			\
	return(elem == NULL);						\
}									\
static inline bool name##_islast(t_elem *elem) {			\
	return(name##_attail(name##_next(elem)));			\
}									\
									\
/* single element manipulation */					\
static inline void name##_insert_after(t_elem *elem, t_elem *new) {	\
	new->link.next = elem->link.next;				\
	elem->link.next = new; 						\
}									\
static inline void name##_insert_first(t_root *root, t_elem *new) {	\
	new->link.next = root->head.next;				\
	root->head.next = new; 						\
}									\
static inline t_elem *name##_remove_first(t_root *root) {		\
	t_elem *elem = name##_first(root);				\
	if(name##_attail(elem)) return(NULL);				\
	root->head.next = elem->link.next;				\
	name##_init_link(elem);						\
	return(elem);							\
}									\
static inline void name##_remove_next(t_elem *elem) {			\
	t_elem *next = name##_next(elem);				\
	if(name##_attail(next)) return;					\
	elem->link.next = next->link.next;				\
	name##_init_link(next);						\
}									\
									\
static inline int name##_length(t_root *root) {				\
	t_elem *elem; int i;						\
	for(elem = name##_first(root), i = 0;				\
	    !name##_attail(elem);					\
	    elem = name##_next(elem), i++);				\
	return(i);							\
}									\
									\
/* memory handling */							\
static inline t_root *name##_create(void) {				\
	t_root *root = xalloc(sizeof(*root));				\
	name##_init(root);						\
	return(root);							\
}									\
static inline void name##_destroy(t_root *root) {			\
	t_elem *elem;							\
	if(root == NULL) return;					\
	while(elem = name##_remove_first(root), elem != NULL)		\
		xfree(elem, sizeof(*elem));				\
	xfree(root, sizeof(*root));					\
}									\
									\
struct list__hack

#endif /* ! SLIST_H */