/* ** 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@ */ #ifndef _SKLINKEDLIST_H #define _SKLINKEDLIST_H #include "silk.h" RCSIDENTVAR(rcsID_SKLINKEDLIST_H, "$SiLK: sklinkedlist.h 5714 2006-11-15 23:27:33Z mthomas $"); /* ** sklinkedlist.h ** ** Simple doubly-linked list implementation. Not threadsafe. ** */ /* return status from linked list functions */ typedef enum _sk_link_err_e { 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; struct _sk_link_item; typedef struct _sk_link_list sk_link_list_t; typedef struct _sk_link_item 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 */