/*
** Copyright (C) 2005-2006 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
**
** Use of the SILK system and related source code is subject to the terms
** of the following licenses:
**
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013
**
** NO WARRANTY
**
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE,
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT,
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES.
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE
** DELIVERABLES UNDER THIS LICENSE.
**
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie
** Mellon University, its trustees, officers, employees, and agents from
** all claims or demands made against them (and any related losses,
** expenses, or attorney's fees) arising out of, or relating to Licensee's
** and/or its sub licensees' negligent use or willful misuse of or
** negligent conduct or willful misconduct regarding the Software,
** facilities, or other rights or assistance granted by Carnegie Mellon
** University under this License, including, but not limited to, any
** claims of product liability, personal injury, death, damage to
** property, or violation of any laws or regulations.
**
** Carnegie Mellon University Software Engineering Institute authored
** documents are sponsored by the U.S. Department of Defense under
** Contract F19628-00-C-0003. Carnegie Mellon University retains
** copyrights in all material produced under this contract. The U.S.
** Government retains a non-exclusive, royalty-free license to publish or
** reproduce these documents, or allow others to do so, for U.S.
** Government purposes only pursuant to the copyright license under the
** contract clause at 252.227.7013.
**
** @OPENSOURCE_HEADER_END@
*/

/*
** Simple linked list implementation.  Single threaded only.
**
*/

#include "silk.h"

RCSIDENT("$SiLK: sklinkedlist.c 3409 2006-04-11 23:06:27Z mthomas $");

#include "sklinkedlist.h"



struct _sk_link_list {
    /* the head of the linked list */
    sk_link_item_t     *head;
    /* the tail of the linked list */
    sk_link_item_t     *tail;
    /* the number of entries in the linked list */
    int                 entries;
    /* deallocator for the data portion of each node */
    sk_link_free_fn_t   deallocator;
};


struct _sk_link_item {
    /* pointer to next item, or NULL if tail */
    sk_link_item_t     *next;
    /* pointer to prev item, or NULL if head */
    sk_link_item_t     *prev;
    /* pointer to user-allocated and managed data */
    void               *data;
};



/*
**
**    Allocation operations
**
*/


/* common deallocator which calls free() on each user data pointer */
void skLinkGenericDeallocator(
    void   *p_structure)
{
    if (p_structure != NULL) {
        free(p_structure);
    }
}


/*
 *  _skLinkAllocNode
 *
 *    Helper function to allocate space for a single node.
 *
 *  Arguments
 *
 *    sk_link_item_t **new_node - The contents of this pointer will be
 *    overwritten with a pointer to the newly allocated node.
 */
static sk_link_err_t _skLinkAllocNode(
    sk_link_item_t    **new_node)
{
    assert(new_node);

    *new_node = calloc(1, sizeof(sk_link_item_t));
    if (*new_node == NULL) {
        return SKLINK_ERR_MEM;
    }

    return SKLINK_OK;
}


/*
 *  _skLinkFreeNode
 *
 *    Helper function to free a single node and its associated data.
 *
 *  Arguments
 *
 *    sk_link_list_t *list - The list the node belongs to.
 *
 *    sk_link_item_t *node - The node to be deallocated.
 */
static sk_link_err_t _skLinkFreeNode(
    sk_link_list_t     *list,
    sk_link_item_t     *node)
{
    assert(list != NULL);
    assert(node != NULL);

    /* free data if a deallocator exists */
    if (list->deallocator != NULL) {
        list->deallocator(node->data);
    }

    /* free the node itself */
    free(node);

    return SKLINK_OK;
}


/* create a new linked list header, ready to add nodes */
sk_link_err_t skLinkAllocList(
    sk_link_list_t    **new_list,
    sk_link_free_fn_t   deallocator)
{
    if (new_list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    *new_list = (sk_link_list_t *) calloc(1, sizeof(sk_link_list_t));
    if (*new_list == NULL) {
        return SKLINK_ERR_MEM;
    }

    (*new_list)->deallocator = deallocator;

    return SKLINK_OK;
}


/* free the entire linked list, removing all nodes.  if a deallocator
 * was set on list creation, free user data also. */
sk_link_err_t skLinkFreeList(
    sk_link_list_t     *list)
{
    sk_link_item_t *node;
    sk_link_item_t *next_node;

    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    /* remove any nodes in the list */
    node = list->head;
    while (node != NULL) {
        next_node = node->next;
        (void)_skLinkFreeNode(list, node);
        node = next_node;
    }

    /* free the list itself */
    free(list);

    return SKLINK_OK;
}


/* remove current_node from list.  deallocate the list entry, and if a
 * deallocator was set on list creation, free user data also. */
sk_link_err_t skLinkRemoveNode(
    sk_link_list_t *list,
    sk_link_item_t *current_node)
{
    /* check inputs */
    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    /* update linked list pointers */
    if (current_node->prev != NULL) {
        current_node->prev->next = current_node->next;
    } else {
        list->head = current_node->next;
    }

    if (current_node->next != NULL) {
        current_node->next->prev = current_node->prev;
    } else {
        list->tail = current_node->prev;
    }

    /* free the node and its data */
    (void)_skLinkFreeNode(list, current_node);

    /* decrement entry counter */
    --(list->entries);

    return SKLINK_OK;
}


/*
** remove current_node from list.  deallocate the list entry.  do NOT
** call the deallocator on the data stored in that node.
** (Responsibility for memory ownership is no longer with the linked
** list.)
*/
sk_link_err_t skLinkRemoveNodeKeepData(
    sk_link_list_t *list,
    sk_link_item_t *current_node)
{
    /* check inputs */
    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    /* update linked list pointers */
    if (current_node->prev != NULL) {
        current_node->prev->next = current_node->next;
    } else {
        list->head = current_node->next;
    }

    if (current_node->next != NULL) {
        current_node->next->prev = current_node->prev;
    } else {
        list->tail = current_node->prev;
    }

    /* free the node and its data */
    free( current_node );

    /* decrement entry counter */
    --(list->entries);

    return SKLINK_OK;
}



/* accessor for the length of the list */
sk_link_err_t skLinkLength(
    sk_link_list_t *list,
    int *length ) 
{
    /* check inputs */
    if ( list == NULL || length == NULL ) {
        return SKLINK_ERR_INPUT;
    }

    *length = list->entries;
    return SKLINK_OK;
}


/*
** Get operations
*/

/* set result_node to point to the head of the list */
sk_link_err_t skLinkGetHead(
    sk_link_item_t        **result_node,
    const sk_link_list_t   *list)
{
    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (list->head == NULL) {
        return SKLINK_ERR_NOT_FOUND;
    }

    *result_node = list->head;
    return SKLINK_OK;
}


/* set result_node to point to the tail of the list */
sk_link_err_t skLinkGetTail(
    sk_link_item_t        **result_node,
    const sk_link_list_t   *list)
{
    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (list->tail == NULL) {
        return SKLINK_ERR_NOT_FOUND;
    }

    *result_node = list->tail;
    return SKLINK_OK;
}


/* set result_node to point to the next item after current_node */
sk_link_err_t skLinkGetNext(
    sk_link_item_t        **result_node,
    const sk_link_item_t   *current_node)
{
    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (result_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (current_node->next == NULL) {
        return SKLINK_ERR_NOT_FOUND;
    }

    *result_node = current_node->next;
    return SKLINK_OK;
}


/* set result_node to point to the previous item before
 * current_node */
sk_link_err_t skLinkGetPrev(
    sk_link_item_t        **result_node,
    const sk_link_item_t   *current_node)
{
    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (result_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (current_node->prev == NULL) {
        return SKLINK_ERR_NOT_FOUND;
    }

    *result_node = current_node->prev;
    return SKLINK_OK;

}


/* set data to point to the user data in node */
sk_link_err_t skLinkGetData(
    void                  **data,
    const sk_link_item_t   *node)
{
    if (node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (data == NULL) {
        return SKLINK_ERR_INPUT;
    }

    *data = node->data;
    return SKLINK_OK;
}


/*
** Insert operations
*/

/* create a new node, set its user data, and append it to list. */
sk_link_err_t skLinkAppendData(
    sk_link_list_t     *list,
    void               *data)
{
    sk_link_err_t rv;
    sk_link_item_t *new_node;

    if (list == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (data == NULL) {
        return SKLINK_ERR_INPUT;
    }

    rv = _skLinkAllocNode(&new_node);
    if (rv != SKLINK_OK) {
        return rv;
    }
    new_node->data = data;

    if (list->tail == NULL) {
        /* first entry in list */
        assert(list->head == NULL);
        list->head = new_node;
        list->tail = new_node;
        new_node->next = NULL;
        new_node->prev = NULL;
    } else {
        /* normal insert, not boundary case */
        new_node->prev = list->tail;
        new_node->next = NULL;
        list->tail->next = new_node;
        list->tail = new_node;
    }

    /* increment entry counter */
    ++(list->entries);

    return SKLINK_OK;
}


/* create a new node, set its user data, and insert it after
 * current_node */
sk_link_err_t skLinkInsertNext(
    sk_link_list_t     *list,
    sk_link_item_t     *current_node,
    void               *data)
{
    sk_link_err_t rv;
    sk_link_item_t *new_node;

    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (data == NULL) {
        return SKLINK_ERR_INPUT;
    }

    rv = _skLinkAllocNode(&new_node);
    if (rv != SKLINK_OK) {
        return rv;
    }
    new_node->data = data;

    new_node->prev = current_node;
    new_node->next = current_node->next;
    if (current_node->next != NULL) {
        current_node->next->prev = new_node;
    } else {
        list->tail = new_node;
    }
    current_node->next = new_node;

    /* increment entry counter */
    ++(list->entries);

    return SKLINK_OK;
}


/* create a new node, set its user data, and insert it before
 * current_node */
sk_link_err_t skLinkInsertPrev(
    sk_link_list_t     *list,
    sk_link_item_t     *current_node,
    void *data)
{
    sk_link_err_t rv;
    sk_link_item_t *new_node;

    if (current_node == NULL) {
        return SKLINK_ERR_INPUT;
    }

    if (data == NULL) {
        return SKLINK_ERR_INPUT;
    }

    rv = _skLinkAllocNode(&new_node);
    if (rv != SKLINK_OK) {
        return rv;
    }
    new_node->data = data;

    new_node->next = current_node;
    new_node->prev = current_node->prev;
    if (current_node->prev != NULL) {
        current_node->prev->next = new_node;
    } else {
        list->head = new_node;
    }
    current_node->prev = new_node;

    /* increment entry counter */
    ++(list->entries);

    return SKLINK_OK;
}