source: mainline/uspace/app/sbi/src/list.c

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