/*
** Copyright (C) 2005-2008 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@
*/
#ifndef _SKLINKEDLIST_H
#define _SKLINKEDLIST_H

#include "silk.h"

RCSIDENTVAR(rcsID_SKLINKEDLIST_H, "$SiLK: sklinkedlist.h 10004 2008-01-04 23:08:59Z mthomas $");

/*
** sklinkedlist.h
**
** Simple doubly-linked list implementation.  Not threadsafe.
**
*/

/* return status from linked list functions */
typedef enum sk_link_err_en {
    SKLINK_OK = 0,
    SKLINK_ERR_INPUT,
    SKLINK_ERR_MEM,
    SKLINK_ERR_NOT_FOUND
} sk_link_err_t;


/* linked list type and the type of the items in the list */
struct sk_link_list_st;
struct sk_link_item_st;
typedef struct sk_link_list_st sk_link_list_t;
typedef struct sk_link_item_st sk_link_item_t;

/* Type to describe the deallocation function */
typedef void (*sk_link_free_fn_t)(void*);



/*
 * skLinkAllocList
 *
 * Allocate space for a new linked list header.
 *
 * Arguments
 *
 *   sk_link_list_t **new_list - The contents of this pointer are
 *   modified to point to the newly allocated list.
 *
 *   void (*deallocator)( void * ) - A pointer to the function to call
 *   to deallocate the data for nodes in the list.  If the user wants
 *   to manage the memory, and does not want the list to deallocate
 *   the data upon list destruction, set this argument to NULL.  The
 *   function must take a single void pointer argument, which will
 *   point to the data to be deallocated.
 */
sk_link_err_t skLinkAllocList(
    sk_link_list_t    **new_list,
    sk_link_free_fn_t   deallocator);



/*
 * skLinkGenericDeallocator
 *
 * A generic deallocator function which takes a single pointer and
 * calls free() on it.  This function may be passed as the deallocator
 * to allocList() if the user has a simple data structure he/she
 * wishes to deallocate upon list destruction.
 *
 * Arguments
 *
 *   void *p_structure - A pointer to the structure to be deallocated
 */
void skLinkGenericDeallocator(void *p_structure);



/*
 * skLinkFreeList
 *
 * Free space used by the linked list header and any allocated linked list
 * nodes.
 *
 * Arguments
 *
 *   sk_link_item_t *list - The list to be deallocated.
 *
 * Note
 *
 *   If the user passed in a NULL deallocator function pointer to
 *   skLinkAllocList(), he/she is responsible for deallocating the
 *   data in the linked list prior to freeing the list.  If a
 *   deallocator was specified, it will be called automatically on
 *   node removal.
 */
sk_link_err_t skLinkFreeList(sk_link_list_t *list);


/*
 * skLinkRemoveNode
 *
 * Remove a single node from the list (while maintaining list
 * consistency), and free memory used to hold that node.  If a
 * deallocator for the list is set, it also calls that deallocator on
 * the data pointer in the node.
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list from which the node is being
 *   removed
 *
 *   sk_link_item_t *current_node - The node to remove from the list.
 *
 * Note
 *
 *   If the user passed in a NULL deallocator function pointer to
 *   skLinkAllocList(), he/she is responsible for deallocating the
 *   data in the linked list prior to freeing the list.  If a
 *   deallocator was specified, it will be called automatically on
 *   node removal.
 */
sk_link_err_t skLinkRemoveNode(
    sk_link_list_t     *list,
    sk_link_item_t     *current_node);



/*
 * skLinkRemoveNodeKeepData
 *
 * Remove a single node from the list (while maintaining list
 * consistency), and free memory used to hold that node.  The data
 * stored in that node is NOT deallocated, even if a deallocator for
 * the list is set.
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list from which the node is being
 *   removed
 *
 *   sk_link_item_t *current_node - The node to remove from the list.
 *
 * Note
 *
 *   The user is responsible for deallocating the data that was
 *   contained in this node.
 */
sk_link_err_t skLinkRemoveNodeKeepData(
    sk_link_list_t *list,
    sk_link_item_t *current_node);


/*
 * skLinkLength
 *
 * Returns the number of entries in the linked list.
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list whose length is being calculated
 *
 *   int *length - pointer to an int which will be set to the length
 *   of the list
 *
 */
sk_link_err_t skLinkLength(
    sk_link_list_t     *list,
    int                *length);


/*
 * Get operations
 */

/*
 * skLinkGetHead
 *
 * Retrieve the first node from the linked list
 *
 * Arguments
 *
 *   sk_link_item_t **result_node - The contents of this pointer will be
 *   overwritten with a pointer to the head node.
 *
 *   sk_link_list_t *list - The linked list whose head is to be retrieved.
 */
sk_link_err_t skLinkGetHead(
    sk_link_item_t        **result_node,
    const sk_link_list_t   *list);


/*
 * skLinkGetTail
 *
 * Retrieve the last node from the linked list
 *
 * Arguments
 *
 *   sk_link_item_t **result_node - The contents of this pointer will
 *   be overwritten with a pointer to the tail node.
 *
 *   sk_link_list_t *list - The linked list whose tail is to be retrieved.
 */
sk_link_err_t skLinkGetTail(
    sk_link_item_t        **result_node,
    const sk_link_list_t   *list);


/*
 * skLinkGetNext
 *
 * Given a node in a linked list, retrieve the next node
 *
 * Arguments
 *
 *   sk_link_item_t **result_node - The contents of this pointer will
 *   be overwritten with a pointer to the next node.
 *
 *   sk_link_item_t *current_node - The node whose successor is to be
 *   retrieved.
 */
sk_link_err_t skLinkGetNext(
    sk_link_item_t        **result_node,
    const sk_link_item_t   *current_node);


/*
 * skLinkGetPrev
 *
 * Given a node in a linked list, retrieve the previous node
 *
 * Arguments
 *
 *   sk_link_item_t **result_node - The contents of this pointer will
 *   be overwritten with a pointer to the previous node.
 *
 *   sk_link_item_t *current_node - The node whose predecessor is to be
 *   retrieved.
 */
sk_link_err_t skLinkGetPrev(
    sk_link_item_t        **result_node,
    const sk_link_item_t   *current_node);


/*
 * skLinkGetData
 *
 * Given a node in a linked list, retrieve the user-allocated data for
 * that node
 *
 * Arguments
 *
 *   void **data - The contents of this pointer will be overwritten
 *   with a pointer to data for the current node
 *
 *   sk_link_item_t *node - The node whose data is to be retrieved.
 */
sk_link_err_t skLinkGetData(
    void                  **data,
    const sk_link_item_t   *node);


/*
 * Insert operations
 */

/*
 * skLinkAppendData
 *
 * Append a new node to the end of the list
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list to which to append the new node
 *
 *   void *data - A pointer to the data that will be contained by the
 *   new node
 */
sk_link_err_t skLinkAppendData(
    sk_link_list_t     *list,
    void               *data);


/*
 * skLinkInsertNext
 *
 * Given a node in a linked list, create a new linked list node after
 * it
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list into which the new node is being
 *   inserted
 *
 *   sk_link_item_t *current_node - The node after which the new node
 *   will be appended
 *
 *   void *data - A pointer to the data that will be contained by the
 *   new node
 */
sk_link_err_t skLinkInsertNext(
    sk_link_list_t     *list,
    sk_link_item_t     *current_node,
    void               *data);


/*
 * skLinkInsertPrev
 *
 * Given a node in a linked list, create a new linked list node before
 * it
 *
 * Arguments
 *
 *   sk_link_list_t *list - The list into which the new node is being
 *   inserted
 *
 *   sk_link_item_t *current_node - The node before which the new node
 *   will be inserted
 *
 *   void *data - A pointer to the data that will be contained by the
 *   new node
 */
sk_link_err_t skLinkInsertPrev(
    sk_link_list_t     *list,
    sk_link_item_t     *current_node,
    void               *data);

#endif /* _SKLINKEDLIST_H */

/*
** Local Variables:
** mode:c
** indent-tabs-mode:nil
** c-basic-offset:4
** End:
*/
