/*
 * Copyright (c) 2007, 2008 University of Tsukuba
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. Neither the name of the University of Tsukuba nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * Copyright (c) 2010-2013 Yuichi Watanabe
 */

#ifndef _LIST_H_
#define _LIST_H_

/*
 * Simple list implementation
 */
struct list { void *next; };
#define LIST_DEFINE(listname) struct list listname
#define LIST_DEFINE_HEAD(listname) struct list listname##_head = { NULL }
#define LIST_EXTERN_HEAD(listname) extern struct list listname##_head

#define LIST_INSERT(listname, new)			\
{							\
	new.listname.next = listname##_head.next;	\
	listname##_head.next = new;			\
}

#define LIST_APPEND(listname, new)			\
{							\
	typeof(new) p = listname##_head.next;		\
	if (p != NULL) {				\
		while (p->listname.next != NULL)	\
			p = p->listname.next;		\
		p->listname.next = new;			\
	} else						\
		listname##_head.next = new;		\
	new->listname.next = NULL;			\
}

#define LIST_FOREACH(listname, p) for (p = listname##_head.next; p != NULL; p = p->listname.next)
#define LIST_NEXT(listname, cur) \
	((cur) ? (cur)->listname.next : listname##_head.next)
#define LIST_HEAD(listname) listname##_head.next

/*
 * 1st list implementation
 *
 * usage:
 * struct foo {
 *   LIST1_DEFINE (struct foo);
 *   int bar;
 * };
 * LIST1_DEFINE_HEAD (struct foo, list1_foo);
 * func () {
 *   struct foo f[3], *p;
 *   LIST1_HEAD_INIT (list1_foo);
 *   LIST1_PUSH (list1_foo, &f[0]);
 *   LIST1_PUSH (list1_foo, &f[1]);
 *   p = LIST1_POP (list1_foo);
 *   LIST1_DEL (list1_foo, &f[0]);
 * }
 */

#define LIST1_NAME list
#define LIST1_DEFINE(type)		LIST2_DEFINE(type, LIST1_NAME)
#define LIST1_DEFINE_HEAD(type, name)	LIST2_DEFINE_HEAD(type, name)
#define LIST1_DEFINE_HEAD_INIT(type, name) \
	LIST2_DEFINE_HEAD_INIT(type, name)
#define LIST1_HEAD_INIT(head)		LIST2_HEAD_INIT(head)
#define LIST1_ADD(head, data)		LIST2_ADD(head, LIST1_NAME, data)
#define LIST1_INSERT(head, nextd, data)	LIST2_INSERT(head, LIST1_NAME, nextd, data)
#define LIST1_PUSH(head, data)		LIST2_PUSH(head, LIST1_NAME, data)
#define LIST1_DEL(head, data)		LIST2_DEL(head, LIST1_NAME, data)
#define LIST1_POP(head)			LIST2_POP(head, LIST1_NAME)
#define LIST1_FOREACH(head, var)	LIST2_FOREACH(head, LIST1_NAME, var)
#define LIST1_FOREACH_DELETABLE(head, var, varn) \
	LIST2_FOREACH_DELETABLE(head, LIST1_NAME, var, varn)
#define LIST1_NEXT(head, cur)		LIST2_NEXT(head, LIST1_NAME, cur)
#define LIST1_PREV(head, cur)		LIST2_PREV(head, LIST1_NAME, cur)

/*
 * 2nd list implementation
 *
 * usage:
 * struct foo {
 *   LIST2_DEFINE (struct foo, mona);
 *   LIST2_DEFINE (struct foo, giko);
 *   int bar;
 * };
 * LIST2_DEFINE_HEAD (struct foo, list_foo_mona);
 * LIST2_DEFINE_HEAD (struct foo, list_foo_giko);
 * func () {
 *   struct foo f[3], *p;
 *   LIST2_HEAD_INIT (list_foo_mona);
 *   LIST2_HEAD_INIT (list_foo_giko);
 *   LIST2_PUSH (list_foo_mona, mona, &f[0]);
 *   LIST2_PUSH (list_foo_mona, mona, &f[1]);
 *   LIST2_PUSH (list_foo_giko, giko, &f[0]);
 *   p = LIST2_POP (list_foo_mona, mona);
 *   LIST2_DEL (list_foo_giko, giko, &f[0]);
 * }
 */

#define LIST2_DEFINE(type, name) \
	struct {type *next, *prev; } name

#define LIST2_DEFINE_HEAD(type, headname) \
	struct {type *top, *tail; } headname

#define LIST2_DEFINE_HEAD_INIT(type, name) \
	struct {type *top, *tail; } name = {NULL, NULL}

#define LIST2_HEAD_INIT(head) \
	(head).top = (head).tail = NULL

#define LIST2_ADD(head, name, data)				\
	do {							\
		(data)->name.next = NULL;			\
		(data)->name.prev = (head).tail;		\
		if ((head).tail != NULL) {			\
			(head).tail->name.next = (data);	\
		}						\
		(head).tail = (data);				\
		if ((head).top == NULL) {			\
			(head).top = (data);			\
		}						\
	} while (0)

#define LIST2_INSERT(head, name, nextd, data)		\
	do {						\
		(data)->name.next = (nextd);		\
		(data)->name.prev = (nextd)->name.prev;	\
		if ((nextd)->name.prev == NULL) {	\
			(head).top = (data);		\
		} else {				\
			(nextd)->name.prev->name.next	\
				= (data);		\
		}					\
		(nextd)->name.prev = (data);		\
	} while (0)

#define LIST2_PUSH(head, name, data)			\
	do {						\
		(data)->name.next = (head).top;		\
		(data)->name.prev = NULL;		\
		if ((head).top != NULL)	{		\
			(head).top->name.prev = (data);	\
		}					\
		(head).top = (data);			\
		if ((head).tail == NULL) {		\
			(head).tail = (data);		\
		}					\
	} while (0)

#define LIST2_DEL(head, name, data) ({ \
	void *RET = (data); \
	( (data)->name.prev ? (data)->name.next ? ( /* prev && next */ \
		(((data)->name.prev)->name.next = (data)->name.next), \
		(((data)->name.next)->name.prev = (data)->name.prev), \
		RET \
	) : ( /* prev && !next */	   \
		((head).tail = (data)->name.prev), \
		((head).tail->name.next = NULL),  \
		RET \
	) : (data)->name.next ? ( /* !prev && next */	\
		((head).top = ((data)->name.next)),	\
		((head).top->name.prev = NULL), \
		RET \
	) : ( /* !prev && !next */ \
		((head).top = (head).tail = NULL),\
		RET \
		)); \
})

#define LIST2_POP(head, name)						\
	(head.top ?							\
	 LIST2_DEL(head, name, head.top) : NULL)

#define LIST2_FOREACH(head, name, var)					\
	for (var = (head).top; var; var = var->name.next)

#define LIST2_FOREACH_DELETABLE(head, name, var, varn)			\
	for (var = (head).top; var && ((varn = var->name.next), 1);	\
	     var = varn)

#define LIST2_NEXT(head, name, cur)					\
	((cur) ? (cur)->name.next : (head).top)

#define LIST2_PREV(head, name, cur)					\
	((cur) ? (cur)->name.prev : (head).tail)

/* list for continuous array
   every element of a list is in one array
   usage:
   struct foo {
     LIST3_DEFINE (struct foo, mona, signed char);
     LIST3_DEFINE_BIT (struct foo, giko, signed int, 4);
     int bar;
   };
   LIST3_DEFINE_HEAD (list_foo_mona, struct foo, mona);
   LIST3_DEFINE_HEAD (list_foo_giko, struct foo, giko);
   func () {
     struct foo f[3], *p;
     LIST3_HEAD_INIT (list_foo_mona, mona);
     LIST3_HEAD_INIT (list_foo_giko, giko);
     LIST3_PUSH (list_foo_mona, mona, &f[0]);
     LIST3_PUSH (list_foo_mona, mona, &f[1]);
     LIST3_PUSH (list_foo_giko, giko, &f[0]);
     p = LIST3_POP (list_foo_mona, mona);
     LIST3_DEL (list_foo_giko, giko, &f[0]);
   }
*/
#define LIST3_DEFINE(type, sx, inttype) \
	inttype sx##prev, sx##next
#define LIST3_DEFINE_BIT(type, sx, inttype, nbits) \
	inttype sx##prev : nbits, sx##next : nbits
#define LIST3_DEFINE_HEAD(name, type, sx) \
	struct { type *prev, *next; } name
#define LIST3_DEFINE_HEAD_INIT(name, type, sx) \
	struct { type *prev, *next; } name = { NULL, NULL }
#define LIST3_HEAD_INIT(name, sx) name.prev = name.next = NULL
#define LIST3_ADD(head, sx, data) ( \
	((data)->sx##next = 0), \
	(/* if */ (head).prev ? ( \
		((data)->sx##prev = (head).prev - (data)), \
		((head).prev->sx##next = -(data)->sx##prev), \
		((head).prev = (data)) \
	) : (/* else */ \
		((data)->sx##prev = 0), \
		((head).prev = (head).next = (data)) \
	)))
#define LIST3_INSERT(head, sx, nextd, data) \
	(/* if */ (nextd) ? ( \
		((data)->sx##next = (nextd) - (data)), \
		(/* if */ (nextd)->sx##prev ? ( \
			((data)->sx##prev = \
				(data)->sx##next + (nextd)->sx##prev), \
			((nextd)->sx##prev = -(data)->sx##next), \
			(((data) + (data)->sx##prev)->sx##next = \
				-(data)->sx##prev), \
			(data) \
		) : (/* else */ \
			((data)->sx##prev = 0), \
			((nextd)->sx##prev = -(data)->sx##next), \
			((head).next = (data)) \
		)) \
	) : (/* else */ \
		LIST3_ADD (head, sx, (data)) \
	))
#define LIST3_PUSH(head, sx, data) \
	LIST3_INSERT (head, sx, (head).next, (data))
#define LIST3_DEL(head, sx, data) ({ \
	void *RET = (data); \
	((data)->sx##prev ? (data)->sx##next ? ( /* prev && next */ \
		(((data) + (data)->sx##prev)->sx##next += (data)->sx##next), \
		(((data) + (data)->sx##next)->sx##prev += (data)->sx##prev), \
		RET \
	) : ( /* prev && !next */ \
		((head).prev = ((data) + (data)->sx##prev)), \
		((head).prev->sx##next = 0), \
		RET \
	) : (data)->sx##next ? ( /* !prev && next */ \
		((head).next = ((data) + (data)->sx##next)), \
		((head).next->sx##prev = 0), \
		RET \
	) : ( /* !prev && !next */ \
		((head).prev = (head).next = NULL), \
		RET \
	)); \
})
#define LIST3_POP(head, sx) \
	((head).next ? LIST3_DEL (head, sx, (head).next) : NULL)
#define LIST3_FOREACH(head, sx, var) \
	for (var = (head).next; var; var = var->sx##next ? \
	     var + var->sx##next : NULL)
#define LIST3_FOREACH_DELETABLE(head, sx, var, varn) \
	for (var = (head).next; var && ((varn = var->sx##next ? \
					 (var + var->sx##next) : NULL), 1); \
	     var = varn)

/* #define LIST1_DEFINE(type) type **pnext, *next */
/* #define LIST1_DEFINE_HEAD(type, name) struct { type **pnext, *next; } name */
/* #define LIST1_DEFINE_HEAD_INIT(type, name) \ */
/* 	struct { type **pnext, *next; } name = { &name.next, NULL } */
/* #define LIST1_HEAD_INIT(name) *(name.pnext = &name.next) = NULL */
/* #define _LIST1_NEXTPNEXT(head, data) \ */
/* 	((data)->next ? &(data)->next->pnext : &(head).pnext) */
/* #define LIST1_ADD(head, data) \ */
/* 	list1_insert ((head).pnext, (data), &(data)->pnext, &(data)->next, \ */
/* 		      NULL, &(head).pnext) */
/* #define LIST1_PUSH(head, data) \ */
/* 	list1_insert (&(head).next, (data), &(data)->pnext, &(data)->next, \ */
/* 		      (head).next, _LIST1_NEXTPNEXT (head, &head)) */
/* #define LIST1_DEL(head, data) \ */
/* 	list1_delete ((data)->pnext, (data)->next, \ */
/* 		      _LIST1_NEXTPNEXT (head, data), (data)) */
/* #define LIST1_POP(head) \ */
/* 	((head).next ? LIST1_DEL (head, (head).next) : NULL) */
/* #define LIST1_FOREACH(head, var) \ */
/* 	for (var = (head).next; var; var = var->next) */
/* #define LIST1_INSERT(head, nextd, data) \ */
/* 	((nextd) ? list1_insert ((nextd)->pnext, (data), &(data)->pnext, \ */
/* 				 &(data)->next, (nextd), &(nextd)->pnext) \ */
/* 		 : LIST1_ADD ((head), (data))) */
/* #define LIST1_NEXT(head, cur) \ */
/* 	((cur) ? (cur)->next : (head).next) */

/* #define LIST2_DEFINE(type, sx) type **sx##pnext, *sx##next */
/* #define LIST2_DEFINE_HEAD(name, type) \ */
/* 	struct { type **pnext, *next; } name */
/* #define LIST2_DEFINE_HEAD_INIT(name, type) \ */
/* 	struct { type **pnext, *next; } name = { &name.next, NULL } */
/* #define LIST2_HEAD_INIT(name) *(name.pnext = &name.next) = NULL */
/* #define _LIST2_NEXTPNEXT(head, sx, data) \ */
/* 	((data)->sx##next ? &(data)->sx##next->sx##pnext : &(head).pnext) */
/* #define _LIST2_NEXTPNEXT2(head, sx) \ */
/* 	((head).next ? &(head).next->sx##pnext : &(head).pnext) */
/* #define LIST2_ADD(head, sx, data) \ */
/* 	list1_insert ((head).pnext, (data), &(data)->sx##pnext, \ */
/* 		      &(data)->sx##next, NULL, &(head).pnext) */
/* #define LIST2_PUSH(head, sx, data) \ */
/* 	list1_insert (&(head).next, (data), &(data)->sx##pnext, \ */
/* 		      &(data)->sx##next, (head).next, \ */
/* 		      _LIST2_NEXTPNEXT2 (head, sx)) */
/* #define LIST2_DEL(head, sx, data) \ */
/* 	list1_delete ((data)->sx##pnext, (data)->sx##next, \ */
/* 		      _LIST2_NEXTPNEXT (head, sx, data), (data)) */
/* #define LIST2_POP(head, sx) \ */
/* 	((head).next ? LIST2_DEL (head, sx, (head).next) : NULL) */
/* #define LIST2_FOREACH(head, sx, var) \ */
/* 	for (var = (head).next; var; var = var->sx##next) */
/* #define LIST2_FOREACH_DELETABLE(head, sx, var, varn) \ */
/* 	for (var = (head).next; var && ((varn = var->sx##next), 1); \ */
/* 	     var = varn) */
/* #define LIST2_INSERT(head, sx, nextd, data) \ */
/* 	((nextd) ? list1_insert ((nextd)->sx##pnext, (data), \ */
/* 				 &(data)->sx##pnext, &(data)->sx##next, \ */
/* 				 (nextd), &(nextd)->sx##pnext) \ */
/* 		 : LIST2_ADD (head, sx, (data))) */
/* #define LIST2_NEXT(head, sx, cur) \ */
/* 	((cur) ? (cur)->sx##next : (head).next) */

/* /\* p{p_pn,p_n} -> n{n_pn,n_n} *\/ */
/* /\* p{p_pn,p_n} -> d{d_pn,d_n} -> n{n_pn,n_n} *\/ */
/* static inline void */
/* list1_insert (void *p_n, void *d, void *d_pn, void *d_n, void *n, */
/* 	      void *n_pn) */
/* { */
/* 	*(unsigned long *)p_n = (unsigned long)d; */
/* 	*(unsigned long *)d_pn = (unsigned long)p_n; */
/* 	*(unsigned long *)d_n = (unsigned long)n; */
/* 	*(unsigned long *)n_pn = (unsigned long)d_n; */
/* } */

/* /\* p{p_pn,p_n=*d_pn} -> d{d_pn,d_n} -> n=d_n{n_pn=&d_n,n_n} *\/ */
/* /\* p{p_pn,p_n=n} -> n{n_pn=&p_n,n_n} *\/ */
/* static inline void * */
/* list1_delete (void *p_n, void *n, void *n_pn, void *d) */
/* { */
/* 	*(unsigned long *)p_n = (unsigned long)n; */
/* 	*(unsigned long *)n_pn = (unsigned long)p_n; */
/* 	return d; */
/* } */

#endif
