/*
 *  Copyright (C) 2019 - Vito Caputo - <vcaputo@pengaru.com>
 *
 *  This program is free software: you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License version 3 as published
 *  by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/* (circular) Doubly-Linked List header */

/* I've been using the Linux kernel's list.h for ages, so it definitely
 * takes some inspiration from that API.
 */

#ifndef _DLL_H
#define _DLL_H


#include <stddef.h>	/* offsetof() */


typedef struct dll_t dll_t;

struct dll_t {
	dll_t	*next, *previous;
};


/* This is analagous to container_of */
#define DLL_ENTRY(_ptr, _type, _member) \
	(_type *)((char *)(_ptr) - offsetof(_type, _member))


/* Declare and initialize an empty list named _name */
#define DLL_INIT(_name) \
	dll_t	_name = { .next = &_name, .previous = &_name }


/* Iterate list */
#define DLL_FOR_EACH(_head, _node)		\
	for (	(_node) = (_head)->next;	\
		(_node) != (_head);		\
		(_node) = (_node)->next		\
	)


/* Iterate list in a removal-safe fashion */
#define DLL_FOR_EACH_SAFE(_head, _node, _next)				\
	for (	(_node) = (_head)->next, (_next) = (_node)->next;	\
		(_node) != (_head);					\
		(_node) = (_next), (_next) = (_next->next)		\
	)


/* Iterate list as containers */
#define DLL_FOR_EACH_ENTRY(_head, _entry, _type, _member)			\
	for (	(_entry) = DLL_ENTRY((_head)->next, _type, _member);		\
		&(_entry)->_member != (_head);					\
		(_entry) = DLL_ENTRY((_entry)->_member.next, _type, _member)	\
	)


/* Iterate list as containers in a removal-safe fashion */
#define DLL_FOR_EACH_ENTRY_SAFE(_head, _entry, _next, _type, _member)		\
	for (	(_entry) = DLL_ENTRY((_head)->next, _type, _member),		\
		(_next) = DLL_ENTRY((_entry)->_member.next, _type, _member);	\
		&(_entry)->_member != (_head);					\
		(_entry) = (_next),						\
		(_next) = DLL_ENTRY((_next)->_member.next, _type, _member)	\
	)


/* Initialize node to an empty list state,
 * node is returned for convenience.
 */
static inline dll_t * dll_init(dll_t *node)
{
	return node->next = node->previous = node;
}


/* Delete node from the list it belongs to,
 * node is returned for convenience.
 */
static inline dll_t * dll_del(dll_t *node)
{
	node->next->previous = node->previous;
	node->previous->next = node->next;

	return dll_init(node);
}


/* Insert node immediately before where,
 * node is returned for convenience.
 */
static inline dll_t * dll_pre(dll_t *where, dll_t *node)
{
	node->next = where;
	node->previous = where->previous;
	where->previous->next = node;
	where->previous = node;

	return node;
}


/* Append node immediately after where,
 * node is returned for convenience.
 */
static inline dll_t * dll_post(dll_t *where, dll_t *node)
{
	node->next = where->next;
	node->previous = where;
	where->next->previous = node;
	where->next = node;

	return node;
}


static inline int dll_empty(dll_t *dll)
{
	return (dll->next == dll && dll->next == dll->previous);
}


#endif