lili.c

Go to the documentation of this file.

/*
 * Copyright 2010 by egnite GmbH
 *
 * 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 the copyright holders nor the names of
 *    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 THE
 * COPYRIGHT OWNER 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.
 *
 * For additional information see http://www.ethernut.de/
 */

/*
 * \file gorp/list/lili.c
 * \brief Linked list main functions.
 *
 * \verbatim
 * $Id$
 * \endverbatim
 */

#include <memdebug.h>
#include <sys/nutdebug.h>

#include <stdlib.h>
#include <gorp/lili.h>


static int LiLiDefaultItemCompare(LILI_ITEMREF ref1, LILI_ITEMREF ref2)
{
    return ref1 - ref2;
}

/*
 * \brief Add the first node object to an empty list.
 *
 * \param list Pointer to a list object, obtained from a previous call
 *             to LiLiCreate().
 * \param node Pointer to the node object to add.
 */
static void LiLiNodeAddFirst(LILI *list, LILI_NODE *node)
{
    /* The list must be empty. */
    NUTASSERT(list->lst_head == NULL);
    NUTASSERT(list->lst_tail == NULL);
    /* Insert the first node. */
    list->lst_head = node;
    list->lst_tail = node;
    node->nod_nxt = NULL;
    node->nod_prv = NULL;
}

void LiLiRemoveNode(LILI *list, LILI_NODE *node)
{
    /* Sanity checks. */
    NUTASSERT(list != NULL);
    if (node) {
        NUTASSERT(list->lst_head != NULL);
        NUTASSERT(list->lst_tail != NULL);

        /* Remove the forward link. */
        if (node->nod_nxt) {
            node->nod_nxt->nod_prv = node->nod_prv;
        } else {
            list->lst_tail = node->nod_prv;
        }
        /* Remove the backward link. */
        if (node->nod_prv) {
            node->nod_prv->nod_nxt = node->nod_nxt;
        } else {
            list->lst_head = node->nod_nxt;
        }
        free(node);
    }
}

/*
 * \brief Insert a new node object after a given node.
 *
 * Note, that list attributes are ignored. Anyway, special applications may 
 * use this function instead of LiLiPushItem().
 *
 * \param list Pointer to a list object, obtained from a previous call
 *             to LiLiCreate().
 * \param node Pointer to the node after which the a new node will be 
 *             inserted. If the list is empty, this must be set to NULL.
 * \param ref  The reference of the item to associate with the new node.
 *             If a function for creating an item copy has been specified, 
 *             it will be called before inserting the new node.
 *
 * \return Pointer to the new node object or NULL on errors.
 */
LILI_NODE *LiLiInsertItemAfterNode(LILI *list, LILI_NODE *node, LILI_ITEMREF ref)
{
    LILI_NODE *newnode;

    /* Sanity check. */
    NUTASSERT(list != NULL);

    newnode = malloc(sizeof(LILI_NODE));
    if (newnode) {
        /* Optionally create a duplicate of the item. */
        newnode->nod_itm = list->lst_icreate ? list->lst_icreate(ref) : ref;
        if (node) {
            /* A node is provided. The list must have members. */
            NUTASSERT(list->lst_head != NULL);
            NUTASSERT(list->lst_tail != NULL);
            /* Link the new node to the list. */
            newnode->nod_nxt = node->nod_nxt;
            newnode->nod_prv = node;
            node->nod_nxt = newnode;
            if (newnode->nod_nxt) {
                newnode->nod_nxt->nod_prv = newnode;
            }
            if (node == list->lst_tail) {
                list->lst_tail = newnode;
            }
        } else {
            /* No node provided. Add the first node to an empty list. */
            LiLiNodeAddFirst(list, newnode);
        }
    }
    return newnode;
}

/*
 * \brief Insert new data node before a given node.
 *
 * Note, that list attributes are ignored. Anyway, special applications may 
 * use this function instead of LiLiPushItem().
 *
 * \param list Pointer to a list object, obtained from a previous call
 *             to LiLiCreate().
 * \param ref  The reference of the item to associate with the new node.
 *             If a function for creating an item copy has been specified, 
 *             it will be called before inserting the new node.
 *
 * \return Pointer to the new node object or NULL on errors.
 */
LILI_NODE *LiLiInsertItemBeforeNode(LILI *list, LILI_NODE *node, LILI_ITEMREF ref)
{
    LILI_NODE *newnode;

    /* Sanity checks. */
    NUTASSERT(list != NULL);

    newnode = malloc(sizeof(LILI_NODE));
    if (newnode) {
        newnode->nod_itm = list->lst_icreate ? list->lst_icreate(ref) : ref;
        if (node) {
            /* A node is provided. The list must have members. */
            NUTASSERT(list->lst_head != NULL);
            NUTASSERT(list->lst_tail != NULL);
            /* Link the new node to the list. */
            newnode->nod_nxt = node;
            newnode->nod_prv = node->nod_prv;
            if (newnode->nod_prv) {
                newnode->nod_prv->nod_nxt = newnode;
            }
            node->nod_prv = newnode;
            if (node == list->lst_head) {
                list->lst_head = newnode;
            }
        } else {
            /* No node provided. Add the first node to an empty list. */
            LiLiNodeAddFirst(list, newnode);
        }
    }
    return newnode;
}

LILI *LiLiCreate(uint8_t flags, LiLiItemCreateFunc icre, LiLiItemDestroyFunc ides, LiLiItemCompareFunc icmp)
{
    LILI *list = calloc(1, sizeof(LILI));

    if (list) {
        list->lst_icreate = icre;
        list->lst_idestroy = ides;
        if (icmp) {
            list->lst_icompare = icmp;
        } else {
            list->lst_icompare = LiLiDefaultItemCompare;
        }
        list->lst_flags = flags;
    }
    return list;
}

void LiLiClean(LILI *list)
{
    LILI_NODE *node;

    /* Sanity checks. */
    NUTASSERT(list != NULL);

    if (list->lst_head) {
        while ((node = list->lst_head) != NULL) {
            list->lst_head = node->nod_nxt;
            if (list->lst_idestroy) {
                list->lst_idestroy(LiLiNodeItem(node));
            }
            free(node);
        }
        list->lst_tail = NULL;
    }
}

void LiLiDestroy(LILI *list)
{
    /* Remove all node objects. */
    LiLiClean(list);
    /* Release the list object. */
    free(list);
}