/*
 * doll - Doubly linked list implementation
 * Copyright (c) 2012 Guillermo Ramos Gutiérrez <0xwille@gmail.com>
 * 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 copyright holders 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 COPYRIGHT HOLDERS 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.
 */

#include <stdlib.h>
#include "doll.h"


static struct doll_node *doll_new_node(void *data)
{
	struct doll_node *new_node = malloc(sizeof(struct doll_node));
	new_node->data = data;
	return new_node;
}


static void doll_destroy_node(struct doll_node *node)
{
	free(node);
}


static struct doll_node *doll_find(struct doll *list, void *data)
{
	struct doll_node *node;
	doll_foreach_node(node, list)
		if (node->data == data)
			return node;
	return NULL;
}


static struct doll_node *doll_insert_before(struct doll *list,
		struct doll_node *new, struct doll_node *base)
{
	if (base == list->head) {
		base->prev = new;
		new->next = base;
		new->prev = NULL;
		list->head = new;
	} else {
		base->prev->next = new;
		new->prev = base->prev;
		base->prev = new;
		new->next = base;
	}

	list->length++;

	return new;
}


static struct doll_node *doll_insert_after(struct doll *list,
		struct doll_node *new, struct doll_node *base)
{
	if (base == list->tail) {
		base->next = new;
		new->prev = base;
		new->next = NULL;
		list->tail = new;
	} else {
		base->next->prev = new;
		new->next = base->next;
		base->next = new;
		new->prev = base;
	}

	list->length++;

	return new;
}


static struct doll_node *doll_prepend_node(struct doll *list, struct doll_node *node)
{
	if (node == NULL) {
		return NULL;
	} else if (list->head == NULL && list->tail == NULL) {
		list->head = list->tail = node;
		node->prev = node->next = NULL;
		list->length++;
	} else {
		doll_insert_before(list, node, list->head);
	}

	return node;
}


static struct doll_node *doll_append_node(struct doll *list, struct doll_node *node)
{
	if (node == NULL) {
		return NULL;
	} else if (list->head == NULL && list->tail == NULL) {
		list->head = list->tail = node;
		node->prev = node->next = NULL;
		list->length++;
	} else {
		doll_insert_after(list, node, list->tail);
	}

	return node;
}


static void doll_remove_node(struct doll *list, struct doll_node *node)
{
	if (node->prev)
		node->prev->next = node->next;
	else
		list->head = node->next;

	if (node->next)
		node->next->prev = node->prev;
	else
		list->tail = node->prev;

	list->length--;

	doll_destroy_node(node);
}


struct doll *doll_new(void)
{
	struct doll *newlist = malloc(sizeof(struct doll));
	newlist->head = newlist->tail = NULL;
	newlist->length = 0;
	return newlist;
}


void doll_destroy(struct doll *list)
{
	struct doll_node *node;
	doll_foreach_node(node, list)
		doll_destroy_node(node);
	free(list);
}


int doll_prepend(struct doll *list, void *data)
{
	return doll_prepend_node(list, doll_new_node(data)) ? 0 : -1;
}


int doll_append(struct doll *list, void *data)
{
	return doll_append_node(list, doll_new_node(data)) ? 0 : -1;
}


int doll_remove(struct doll *list, void *data)
{
	struct doll_node *node = doll_find(list, data);
	if (node == NULL)
		return -1;

	doll_remove_node(list, node);
	return 0;
}


void *doll_first(struct doll *list)
{
	return list->head->data;
}


void *doll_last(struct doll *list)
{
	return list->tail->data;
}


void *doll_pop(struct doll *list)
{
	struct doll_node *head = list->tail;
	if (head)
		doll_remove_node(list, head);
	return head ? head->data : NULL;
}



void *doll_at(struct doll *list, int idx)
{
	struct doll_node *aux = list->head;

	if (idx < 0)
		idx = list->length + idx;
	if (idx < 0 || idx >= list->length)
		return NULL;

	while (idx--)
		aux = aux->next;
	return aux->data;
}