lpushpop.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/lpushpop.c
 * \brief Linked list push and pop functions.
 *
 * \verbatim
 * $Id$
 * \endverbatim
 */

#include <sys/nutdebug.h>

#include <gorp/lili.h>


LILI_NODE *LiLiLocateItem(LILI *list, LILI_ITEMREF ref)
{
    LILI_NODE *node;

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

    for (node = LiLiFirstNode(list); node; node = LiLiNextNode(node)) {
        if (list->lst_icompare(LiLiNodeItem(node), ref) >= 0) {
            break;
        }
    }
    return node;
}

LILI_NODE *LiLiFindItem(LILI *list, LILI_ITEMREF ref)
{
    LILI_NODE *node;
    int rc;

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

    for (node = LiLiFirstNode(list); node; node = LiLiNextNode(node)) {
        rc = list->lst_icompare(LiLiNodeItem(node), ref);
        if (rc == 0) {
            break;
        }
        if (rc > 0 && LiLiIsSorted(list)) {
            return NULL;
        }
    }
    return node;
}

int LiLiPushItem(LILI *list, LILI_ITEMREF ref)
{
    LILI_NODE *node;
    int rc;

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

    node = LiLiLastNode(list);
    if (node) {
        if (LiLiIsSorted(list)) {
            /* A sorted list, compare the new with the last item. */
            rc = list->lst_icompare(LiLiNodeItem(node), ref);
            if (rc <= 0) {
                /* The new item is greater or equal, so we should append 
                ** it. But only, if either the items are not equal or if
                ** this is not a list of unique items only. */
                if (rc || !LiLiHasUniqueItems(list)) {
                    rc = LiLiInsertItemAfterNode(list, node, ref) ? 0 : -1;
                }
                return rc;
            }
            /* The new item is lower than the last one in the list. Search
            ** the first node with an item greater or equal than the new one. */
            node = LiLiLocateItem(list, ref);
            /* If the list has unique items only, then ignore an equal item. */
            if (LiLiHasUniqueItems(list) && list->lst_icompare(LiLiNodeItem(node), ref) == 0) {
                return 0;
            }
        } else {
            /* Do not insert an equal item into a unique list. */
            if (LiLiHasUniqueItems(list) && LiLiFindItem(list, ref)) {
                return 0;
            }
            /* If not a sorted list, add new items in front. */
            node = LiLiFirstNode(list);
        }
    }
    /* Add a new node. */
    return LiLiInsertItemBeforeNode(list, node, ref) ? 0 : -1;
}

int LiLiPopItem(LILI *list, LILI_ITEMREF *refp)
{
    LILI_NODE *node;

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

    /* Get the first node, check if the list is empty. */
    node = LiLiFirstNode(list);
    if (node) {
        /* List is not empty. However, if this is a FIFO queue, remove 
        ** the last node instead. */
        if (LiLiIsFifo(list)) {
            node = LiLiLastNode(list);
        }
        /* Pass the item reference to the caller and remove the node. */
        *refp = LiLiNodeItem(node);
        LiLiRemoveNode(list, node);
    }
    return node ? 0 : -1;
}