/*
 * Copyright (c) 2011 Jiri Svoboda
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - 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.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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.
 */

/** @file Doubly linked list.
 *
 * Circular, with a head. Nodes structures are allocated separately from data.
 * Data is stored as 'void *'. We implement several sanity checks to prevent
 * common usage errors.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "mytypes.h"

#include "list.h"

static list_node_t *list_node_new(void *data);
static void list_node_delete(list_node_t *node);
static void list_node_insert_between(list_node_t *n, list_node_t *a, list_node_t *b);
static void list_node_unlink(list_node_t *n);
static bool_t list_node_present(list_t *list, list_node_t *node);

/** Initialize list.
 *
 * @param list	List to initialize.
 */
void list_init(list_t *list)
{
	list->head.prev = &list->head;
	list->head.next = &list->head;
}

/** Deinitialize list.
 *
 * @param list	List to deinitialize.
 */
void list_fini(list_t *list)
{
	assert(list_is_empty(list));

	list->head.prev = NULL;
	list->head.next = NULL;
}

/** Append data to list.
 *
 * Create a new list node and append it at the end of the list.
 *
 * @param list	Linked list.
 * @param data	Data for the new node.
 */
void list_append(list_t *list, void *data)
{
	list_node_t *node;

	node = list_node_new(data);
	list_node_insert_between(node, list->head.prev, &list->head);
}

/** Prepend data to list.
 *
 * Create a new list node and prepend it at the beginning of the list.
 *
 * @param list	Linked list.
 * @param data	Data for the new node.
 */
void list_prepend(list_t *list, void *data)
{
	list_node_t *node;

	node = list_node_new(data);
	list_node_insert_between(node, list->head.prev, &list->head);
}

/** Remove data from list.
 *
 * Removes the given node from a list and destroys it. Any data the node might
 * have is ignored. If asserts are on, we check wheter node is really present
 * in the list the caller is requesting us to remove it from.
 *
 * @param list	Linked list.
 * @param node	List node to remove.
 */
void list_remove(list_t *list, list_node_t *node)
{
	/* Check whether node is in the list as claimed. */
	assert(list_node_present(list, node));
	list_node_unlink(node);
	node->data = NULL;
	list_node_delete(node);
}

/** Return first list node or NULL if list is empty.
 *
 * @param list	Linked list.
 * @return	First node of the list or @c NULL if the list is empty.
 */
list_node_t *list_first(list_t *list)
{
	list_node_t *node;

	assert(list != NULL);
	node = list->head.next;

	return (node != &list->head) ? node : NULL;
}

/** Return last list node or NULL if list is empty.
 *
 * @param list	Linked list.
 * @return	Last node of the list or @c NULL if the list is empty.
 */
list_node_t *list_last(list_t *list)
{
	list_node_t *node;

	assert(list != NULL);
	node = list->head.prev;

	return (node != &list->head) ? node : NULL;
}

/** Return next list node or NULL if this was the last one.
 *
 * @param list	Linked list.
 * @param node	Node whose successor we are interested in.
 * @return	Following list node or @c NULL if @a node is last.
 */
list_node_t *list_next(list_t *list, list_node_t *node)
{
	(void) list;
	assert(list != NULL);
	assert(node != NULL);

	return (node->next != &list->head) ? node->next : NULL;
}

/** Return previous list node or NULL if this was the last one.
 *
 * @param list	Linked list.
 * @param node	Node whose predecessor we are interested in.
 * @return	Preceding list node or @c NULL if @a node is last.
 */
list_node_t *list_prev(list_t *list, list_node_t *node)
{
	(void) list;
	assert(list != NULL);
	assert(node != NULL);

	return (node->prev != &list->head) ? node->prev : NULL;
}

/** Return b_true if list is empty.
 *
 * @param list	Linked list.
 * @return	@c b_true if list is empty, @c b_false otherwise.
 */
bool_t list_is_empty(list_t *list)
{
	return (list_first(list) == NULL);
}

/** Change node data.
 *
 * Change the data associated with a node.
 *
 * @param node	List node.
 * @param data	New data for node.
 */
void list_node_setdata(list_node_t *node, void *data)
{
	node->data = data;
}

/** Create new node.
 *
 * @param data	Initial data for node.
 * @return	New list node.
 */
static list_node_t *list_node_new(void *data)
{
	list_node_t *node;

	node = malloc(sizeof(list_node_t));
	if (node == NULL) {
		printf("Memory allocation failed.\n");
		exit(1);
	}

	node->prev = NULL;
	node->next = NULL;
	node->data = data;

	return node;
}

/** Delete node.
 *
 * @param node	List node. Must not take part in any list.
 */
static void list_node_delete(list_node_t *node)
{
	assert(node->prev == NULL);
	assert(node->next == NULL);
	assert(node->data == NULL);
	free(node);
}

/** Insert node between two other nodes.
 *
 * Inserts @a n between neighboring nodes @a a and @a b.
 *
 * @param n	Node to insert.
 * @param a	Node to precede @a n.
 * @param b	Node to follow @a n.
 */
static void list_node_insert_between(list_node_t *n, list_node_t *a,
    list_node_t *b)
{
	assert(n->prev == NULL);
	assert(n->next == NULL);
	n->prev = a;
	n->next = b;

	assert(a->next == b);
	assert(b->prev == a);
	a->next = n;
	b->prev = n;
}

/** Unlink node.
 *
 * Unlink node from the list it is currently in.
 *
 * @param n	Node to unlink from its current list.
 */
static void list_node_unlink(list_node_t *n)
{
	list_node_t *a, *b;
	assert(n->prev != NULL);
	assert(n->next != NULL);

	a = n->prev;
	b = n->next;

	assert(a->next == n);
	assert(b->prev == n);

	a->next = b;
	b->prev = a;

	n->prev = NULL;
	n->next = NULL;
}

/** Check whether @a node is in list @a list.
 *
 * @param list	Linked list.
 * @param node	Node.
 * @return	@c b_true if @a node is part of @a list, @c b_false otherwise.
 */
static bool_t list_node_present(list_t *list, list_node_t *node)
{
	list_node_t *m;

	m = list->head.next;
	while (m != &list->head) {
		if (m == node)
			return b_true;
		m = m->next;
	}

	return b_false;
}