/*!
 * \file libdotat/list.h
 *
 * \brief Doubly-linked split-ring lists.
 *
 * This header defines a data structure that I call a doubly-linked
 * split-ring list.
 *
 * For a given list there are three types: the element structure,
 * which is defined by the user and contains an instance of the link
 * structure; the link structure, which contains pointers to the
 * previous and next element structures; and the list root structure,
 * which contains two link structures, one for the head end of the
 * list and one for the tail end. The prev pointer of the head and the
 * next pointer of the tail are initialized to NULL so that a program
 * can know when it has reached either end of a list, without knowing
 * the address of the list root beforehand (as is required for unsplit
 * rings).
 *
 * \note Unlike normal linked list terminology, the head isn't the
 * first element of the list, it is a dummy entry before the first
 * element; similarly the tail is a dummy entry after the last element
 * of the list.
 *
 * The following diagram illustrates the structure. Note that the head
 * and tail of the list are stored adjacent to each other in the list
 * root and unlike the elements they do not have other data attached;
 * also, the pointers in the link structure point to the start of the
 * element structure, not to the links inside the element.
 *
 * \code
 *
 *      root
 *     (head)      first       second            last    X-|prev  |
 *    +------+    +------+    +------+         +------+    + -  - +
 *    |  next|--->|  next|--->|  next|-- ... ->|  next|--->|  next|-X
 *  X-|prev  |<---|prev  |<---|prev  |<- ... --|prev  |<---|prev  |
 *    + -  - +    | data |    | data |         | data |    +------+
 *    |  next|-X  +------+    +------+         +------+     (tail)
 *                                                           root
 * \endcode
 *
 * The links in an element don't have to be at the start of the
 * element structure (e.g. to allow a structure to be an element of
 * more than one list), so we play evil games with the first element's
 * prev pointer and the last element's next pointer so that we can
 * treat the links in the list root as if they were part of a normal
 * list element, i.e. we guarantee that first->prev->next == first and
 * last->next->prev == last. However, first->prev != root (and anyway
 * the types are incompatible) so instead you must use NAME_getroot().
 *
 * Each list that uses this structure must be instantiated by invoking
 * one of the list_types() or list_typedefs() macros, followed by the
 * list_functions() macro. The former define the list link and root
 * structures and types respectively, and the latter defines a number
 * of static inline functions that implement the various list
 * operations. Functions with a double underscore in the name are
 * internal to the implementation and shouldn't be called by the user.
 *
 * \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/list.h,v 1.47 2002/09/26 13:42:27 fanf2 Exp $
 */

#ifndef LIST_H
#define LIST_H

#include <sanity.h>

IDENT(list_hv, "$dotat: progetc/libdotat/list.h,v 1.47 2002/09/26 13:42:27 fanf2 Exp $");

#include <stdbool.h>

#include <dotat/xalloc.h>

/*!
 * \brief Pointer magic helper macro for internal use.
 *
 * \invariant
 * \code
 *	dst = list__magic(src, t_src, src_field, t_dst, dst_field);
 *	assert(&src->src_field == &dst->dst_field);
 * \endcode
 *
 * \hideinitializer
 */
#define list__magic(ptr, t_src, src_field, t_dst, dst_field)		\
	((t_dst *)(	(char *)(ptr)					\
			+ offsetof(t_src, src_field)			\
			- offsetof(t_dst, dst_field)	))

/*!
 * \brief Define a list's root and link structures.
 *
 * \param root_tag The \c struct tag of the list's root.
 * \param elem_tag The \c struct tag of the list's elements.
 * \param link_tag The \c struct tag of the list's links.
 *
 * \hideinitializer
 */
#define list_types(root_tag, elem_tag, link_tag)			\
									\
struct link_tag { struct elem_tag *next, *prev; };			\
struct root_tag { struct link_tag  head,  tail; };			\
									\
struct list__hack

/*!
 * \brief Define a list's root, element, and link types.
 *
 * This macro invokes list_types() to define the list structures then
 * defines some types with the same names as the structure tags.
 *
 * \param t_root The name of the type of the list's root.
 * \param t_elem The name of the type of the list's elements.
 * \param t_link The name of the type of the list's links.
 *
 * \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

/*!
 * \brief Define a list's operations.
 *
 * \param name   The name of the list
 *               (written NAME in the function documentation).
 * \param t_root The name of the type of the list's root.
 * \param t_elem The name of the type of the list's elements.
 * \param link   The name of the link structure in each element.
 *
 * \hideinitializer
 */
#define list_functions(name, t_root, t_elem, link)			\
									\
/* internal pointer magic utilities */					\
static inline t_elem *name##__head2elem(t_root *root) {			\
	return(list__magic(root, t_root, head, t_elem, link));		\
}									\
static inline t_elem *name##__tail2elem(t_root *root) {			\
	return(list__magic(root, t_root, tail, t_elem, link));		\
}									\
static inline t_root *name##__elem2head(t_elem *elem) {			\
	return(list__magic(elem, t_elem, link, t_root, head));		\
}									\
static inline t_root *name##__elem2tail(t_elem *elem) {			\
	return(list__magic(elem, t_elem, link, t_root, tail));		\
}									\
									\
/* initializers */							\
static inline void name##_init(t_root *root) {				\
	root->head.next = name##__tail2elem(root);			\
	root->head.prev = root->tail.next = NULL;			\
	root->tail.prev = name##__head2elem(root);			\
}									\
static inline void name##_init_link(t_elem *elem) {			\
	elem->link.next = elem->link.prev = NULL;			\
}									\
									\
/* accessor functions */						\
static inline t_elem *name##_first(t_root *root) {			\
	return(root->head.next);					\
}									\
static inline t_elem *name##_last(t_root *root) {			\
	return(root->tail.prev);					\
}									\
static inline t_elem *name##_next(t_elem *elem) {			\
	return(elem->link.next);					\
}									\
static inline t_elem *name##_prev(t_elem *elem) {			\
	return(elem->link.prev);					\
}									\
									\
/* predicates */							\
static inline bool name##_empty(t_root *root) {				\
	return(root->head.next->link.next == NULL);			\
}									\
static inline bool name##_iselem(t_elem *elem) {			\
	return(elem->link.next != NULL && elem->link.prev != NULL);	\
}									\
static inline bool name##_ishead(t_elem *elem) {			\
	return(elem->link.next != NULL && elem->link.prev == NULL);	\
}									\
static inline bool name##_istail(t_elem *elem) {			\
	return(elem->link.next == NULL && elem->link.prev != NULL);	\
}									\
static inline bool name##_isunlinked(t_elem *elem) {			\
	return(elem->link.next == NULL && elem->link.prev == NULL);	\
}									\
/* faster but less safe predicates for looping */			\
static inline bool name##_athead(t_elem *elem) {			\
	return(elem->link.prev == NULL);				\
}									\
static inline bool name##_attail(t_elem *elem) {			\
	return(elem->link.next == NULL);				\
}									\
/* slightly more complicated predicates */				\
static inline bool name##_isfirst(t_elem *elem) {			\
	return(name##_athead(name##_prev(elem)));			\
}									\
static inline bool name##_islast(t_elem *elem) {			\
	return(name##_attail(name##_next(elem)));			\
}									\
									\
/* internal list manipulation */					\
static inline void name##__splice_before				\
		(t_elem *elem, t_elem *new0, t_elem *newN) {		\
	new0->link.prev = elem->link.prev;				\
	newN->link.next = elem;						\
	elem->link.prev->link.next = new0;				\
	elem->link.prev = newN;						\
}									\
static inline void name##__splice_after					\
		(t_elem *elem, t_elem *new0, t_elem *newN) {		\
	newN->link.next = elem->link.next;				\
	new0->link.prev = elem;						\
	elem->link.next->link.prev = newN;				\
	elem->link.next = new0;						\
}									\
static inline void name##__unsplice(t_elem *old0, t_elem *oldN) {	\
	old0->link.prev->link.next = oldN->link.next;			\
	oldN->link.next->link.prev = old0->link.prev;			\
}									\
									\
/* single element manipulation */					\
static inline void name##_insert_before(t_elem *elem, t_elem *new) {	\
	name##__splice_before(elem, new, new);				\
}									\
static inline void name##_insert_after(t_elem *elem, t_elem *new) {	\
	name##__splice_after(elem, new, new);				\
}									\
static inline void name##_insert_first(t_root *root, t_elem *new) {	\
	name##_insert_before(root->head.next, new);			\
	/* or name##_insert_after(name##__head2elem(root), new); */	\
}									\
static inline void name##_insert_last(t_root *root, t_elem *new) {	\
	name##_insert_after(root->tail.prev, new);			\
	/* or name##_insert_before(name##__tail2elem(root), new); */	\
}									\
static inline void name##_remove(t_elem *elem) {			\
	name##__unsplice(elem, elem);					\
	name##_init_link(elem);						\
}									\
static inline t_elem *name##_remove_first(t_root *root) {		\
	t_elem *elem = name##_first(root);				\
	if(name##_attail(elem)) return(NULL);				\
	name##_remove(elem);						\
	return(elem);							\
}									\
static inline t_elem *name##_remove_last(t_root *root) {		\
	t_elem *elem = name##_last(root);				\
	if(name##_athead(elem)) return(NULL);				\
	name##_remove(elem);						\
	return(elem);							\
}									\
static inline void name##_remove_next(t_elem *elem) {			\
	elem = name##_next(elem);					\
	if(!name##_attail(elem)) name##_remove(elem);			\
}									\
static inline void name##_remove_prev(t_elem *elem) {			\
	elem = name##_prev(elem);					\
	if(!name##_athead(elem)) name##_remove(elem);			\
}									\
									\
/* concatenation etc. */						\
static inline void name##_concat(t_root *dst, t_root *src) {		\
	t_elem *elem0 = name##_first(src);				\
	t_elem *elemN = name##_last(src);				\
	if(name##_attail(elem0)) return;				\
	name##__unsplice(elem0, elemN);					\
	name##__splice_after(dst->tail.prev, elem0, elemN);		\
}									\
									\
/* safe magic for the user */						\
static inline t_root *name##_getroot(t_elem *elem) {			\
	if(name##_ishead(elem))	return(name##__elem2head(elem));	\
	if(name##_istail(elem))	return(name##__elem2tail(elem));	\
	return(NULL);							\
}									\
									\
/* looping operations */						\
static inline t_root *name##_findroot_fwd(t_elem *elem) {		\
	while(!name##_attail(elem))					\
		elem = name##_next(elem);				\
	return(name##__elem2tail(elem));				\
}									\
static inline t_root *name##_findroot_rev(t_elem *elem) {		\
	while(!name##_athead(elem))					\
		elem = name##_prev(elem);				\
	return(name##__elem2head(elem));				\
}									\
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);							\
}									\
static void name##_qsort_r(t_root *root, void *arg,			\
		int (*cmp)(void *, t_elem *, t_elem *)) {		\
	t_elem *pivot, *elem;						\
	t_root one, two, three;						\
	int c;								\
									\
	name##_init(&one);						\
	name##_init(&two);						\
	name##_init(&three);						\
									\
	pivot = name##_remove_first(root);				\
	if(pivot == NULL) return;					\
	name##_insert_last(&two, pivot);				\
									\
	while(elem = name##_remove_first(root), elem != NULL) {		\
		c = cmp(arg, pivot, elem);				\
		if(c > 0)						\
			name##_insert_last(&one, elem);			\
		else							\
		if(c < 0)						\
			name##_insert_last(&three, elem);		\
		else							\
			name##_insert_last(&two, elem);			\
	}								\
	name##_qsort_r(&one, arg, cmp);					\
	name##_qsort_r(&three, arg, cmp);				\
	name##_concat(root, &one);					\
	name##_concat(root, &two);					\
	name##_concat(root, &three);					\
}									\
static int name##_qsort_cmp(void *a, t_elem *e1, t_elem *e2) {		\
	/* function pointers can't be portably cast to void pointers */	\
	int (**arg)(t_elem *, t_elem *) = a;				\
	int (*cmp)(t_elem *, t_elem *) = *arg;				\
	return(cmp(e1,e2));						\
}									\
static inline void name##_qsort						\
		(t_root *root, int (*cmp)(t_elem *, t_elem *)) {	\
	name##_qsort_r(root, &cmp, name##_qsort_cmp);			\
}									\
									\
/* 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

#ifdef FOR_DOCUMENTATION_ONLY

void NAME_init(t_root *root);
/*!<
 * \brief Initialize a list's root.
 * \param root Pointer to the list's root.
 */

void NAME_init_link(t_elem *elem);
/*!<
 * \brief Initialize an element's links.
 * \param elem Pointer to the element.
 */

t_elem *NAME_first(t_root *root);
/*!<
 * \brief Get the first element of a list.
 * \param root Pointer to the list's root.
 * \return A pointer to the first element.
 */

t_elem *NAME_last(t_root *root);
/*!<
 * \brief Get the last element of a list.
 * \param root Pointer to the list's root.
 * \return A pointer to the last element.
 */

t_elem *NAME_next(t_elem *elem);
/*!<
 * \brief Get the next element of a list.
 * \pre not NAME_istail(elem)
 * \param elem Pointer to an element.
 * \return A pointer to the next element.
 */

t_elem *NAME_prev(t_elem *elem);
/*!<
 * \brief Get the previous element of a list.
 * \pre not NAME_ishead(elem)
 * \param elem Pointer to an element.
 * \return A pointer to the previous element.
 */

bool NAME_empty(t_root *root);
/*!<
 * \brief Find out if a list is empty.
 * \param root Pointer to the list's root.
 * \return Non-zero if true; zero if false.
 */

bool NAME_iselem(t_elem *elem);
/*!<
 * \brief Find out if an element is part of a list.
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_ishead(t_elem *elem);
/*!<
 * \brief Find out if an element is the head of a list.
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_istail(t_elem *elem);
/*!<
 * \brief Find out if an element is the tail of a list.
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_isunlinked(t_elem *elem);
/*!<
 * \brief Find out if an element is not part of a list.
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_athead(t_elem *elem);
/*!<
 * \brief Find out if an element is the head of a list.
 * Fast version for use in loops.
 * \pre not NAME_isunlinked(elem)
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_attail(t_elem *elem);
/*!<
 * \brief Find out if an element is the tail of a list.
 * Fast version for use in loops.
 * \pre not NAME_isunlinked(elem)
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_isfirst(t_elem *elem);
/*!<
 * \brief Find out if an element is the first in a list.
 * \pre not NAME_ishead(elem)
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

bool NAME_islast(t_elem *elem);
/*!<
 * \brief Find out if an element is the last in a list.
 * \pre not NAME_istail(elem)
 * \param elem Pointer to an element.
 * \return Non-zero if true; zero if false.
 */

void NAME_insert_before(t_elem *elem, t_elem *new);
/*!<
 * \brief Insert an element before another.
 * \pre not NAME_ishead(elem)
 * \pre NAME_isunlinked(new)
 * \param elem Pointer to an element in a list.
 * \param new  Pointer to the element to add.
 */

void NAME_insert_after(t_elem *elem, t_elem *new);
/*!<
 * \brief Insert an element after another.
 * \pre not NAME_istail(elem)
 * \pre NAME_isunlinked(new)
 * \param elem Pointer to an element in a list.
 * \param new  Pointer to the element to add.
 */

void NAME_insert_first(t_root *root, t_elem *new);
/*!<
 * \brief Insert an element at the start of a list.
 * \pre NAME_isunlinked(new)
 * \param root Pointer to the list's root.
 * \param new  Pointer to the element to add.
 */

void NAME_insert_last(t_root *root, t_elem *new);
/*!<
 * \brief Insert an element at the end of a list.
 * \pre NAME_isunlinked(new)
 * \param root Pointer to the list's root.
 * \param new  Pointer to the element to add.
 */

void NAME_remove(t_elem *elem);
/*!<
 * \brief Remove an element from a list.
 * \pre NAME_iselem(elem)
 * \param elem Pointer to the element.
 */

t_elem *NAME_remove_first(t_root *root);
/*!<
 * \brief Remove the first element from a list.
 * \param root Pointer to the list's root.
 * \return The element that was removed, or NULL if the list was empty.
 */

t_elem *NAME_remove_last(t_root *root);
/*!<
 * \brief Remove the last element from a list.
 * \param root Pointer to the list's root.
 * \return The element that was removed.
 * \return The element that was removed, or NULL if the list was empty.
 */

void NAME_remove_next(t_elem *elem);
/*!<
 * \brief Remove the next element from a list.
 * \pre not NAME_istail(elem)
 * \param elem Pointer to the element.
 */

void NAME_remove_prev(t_elem *elem);
/*!<
 * \brief Remove the previous element from a list.
 * \pre not NAME_ishead(elem)
 * \param elem Pointer to the element.
 */

void NAME_concat(t_root *dst, t_root *src);
/*!<
 * \brief Insert all the elements of one list at the end of another.
 * \post The source list is left empty.
 * \param dst Pointer to the destination list's root.
 * \param src Pointer to the source list's root.
 */

t_root *NAME_getroot(t_elem *elem);
/*!<
 * \brief Turn an element pointer into a root pointer.
 * \param elem Pointer to the element.
 * \return A pointer to the root if the element is
 *         the head or the tail of the list, otherwise NULL.
 */

t_root *NAME_findroot_fwd(t_elem *elem);
/*!<
 * \brief Search for a list's root.
 * \param elem Pointer to an element.
 * \return A pointer to the list's root.
 */

t_root *NAME_findroot_rev(t_elem *elem);
/*!<
 * \brief Search for a list's root.
 * \param elem Pointer to an element.
 * \return A pointer to the list's root.
 */

int NAME_length(t_root *root);
/*!<
 * \brief Count the number of elements in a list.
 * \param root Pointer to the list's root.
 * \return The number of elements.
 */

void NAME_qsort_r(t_root *root, void *arg, int (*cmp)(void *, t_elem *, t_elem *));
/*!<
 * \brief Sort a list in place (extended version).
 * This is a stable sort.
 * \param root Pointer to the list's root.
 * \param arg  Extra data passed down to comparison function.
 * \param cmp  Element comparison function similar to ANSI C qsort() and bsearch().
 */

void NAME_qsort(t_root *root, int (*cmp)(t_elem *, t_elem *));
/*!<
 * \brief Sort a list in place.
 * \param root Pointer to the list's root.
 * \param cmp  Element comparison function same as ANSI C qsort() and bsearch().
 */

t_root *NAME_create(void);
/*!<
 * \brief Allocate an empty list.
 * \return A pointer to the list's root.
 */

void NAME_destroy(t_root *root);
/*!<
 * \brief Free a list and all of its elements.
 * \param root Pointer to the list's root.
 */

#endif /* FOR_DOCUMENTATION_ONLY */

#endif /* ! LIST_H */