/*
* 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;
}