/* * Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com) * Copyright (C) 2003-2008 Benny Prijono * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef __PJ_LIST_H__ #define __PJ_LIST_H__ /** * @file list.h * @brief Linked List data structure. */ #include PJ_BEGIN_DECL /* * @defgroup PJ_DS Data Structure. */ /** * @defgroup PJ_LIST Linked List * @ingroup PJ_DS * @{ * * List in PJLIB is implemented as doubly-linked list, and it won't require * dynamic memory allocation (just as all PJLIB data structures). The list here * should be viewed more like a low level C list instead of high level C++ list * (which normally are easier to use but require dynamic memory allocations), * therefore all caveats with C list apply here too (such as you can NOT put * a node in more than one lists). * * \section pj_list_example_sec Examples * * See below for examples on how to manipulate linked list: * - List sample: \src{pjlib/src/pjlib-samples/list.c} * - List test: \src{pjlib/src/pjlib-test/list.c} */ /** * Use this macro in the start of the structure declaration to declare that * the structure can be used in the linked list operation. This macro simply * declares additional member @a prev and @a next to the structure. * @hideinitializer */ #define PJ_DECL_LIST_MEMBER(type) \ /** List @a prev. */ \ type *prev; \ /** List @a next. */ \ type *next /** * This structure describes generic list node and list. The owner of this list * must initialize the 'value' member to an appropriate value (typically the * owner itself). */ struct pj_list { PJ_DECL_LIST_MEMBER(void); } PJ_ATTR_MAY_ALIAS; /* may_alias avoids warning with gcc-4.4 -Wall -O2 */ /** * Initialize the list. * Initially, the list will have no member, and function pj_list_empty() will * always return nonzero (which indicates TRUE) for the newly initialized * list. * * @param node The list head. */ PJ_INLINE(void) pj_list_init(pj_list_type * node) { ((pj_list*)node)->next = ((pj_list*)node)->prev = node; } /** * Check that the list is empty. * * @param node The list head. * * @return Non-zero if the list is empty, or zero if it is not empty. * */ PJ_INLINE(int) pj_list_empty(const pj_list_type * node) { return ((pj_list*)node)->next == node; } /** * Insert the node to the list before the specified element position. * * @param pos The element to which the node will be inserted before. * @param node The element to be inserted. * */ PJ_IDECL(void) pj_list_insert_before(pj_list_type *pos, pj_list_type *node); /** * Insert the node to the back of the list. This is just an alias for * #pj_list_insert_before(). * * @param list The list. * @param node The element to be inserted. */ PJ_INLINE(void) pj_list_push_back(pj_list_type *list, pj_list_type *node) { pj_list_insert_before(list, node); } /** * Inserts all nodes in \a nodes to the target list. * * @param lst The target list. * @param nodes Nodes list. */ PJ_IDECL(void) pj_list_insert_nodes_before(pj_list_type *lst, pj_list_type *nodes); /** * Insert a node to the list after the specified element position. * * @param pos The element in the list which will precede the inserted * element. * @param node The element to be inserted after the position element. * */ PJ_IDECL(void) pj_list_insert_after(pj_list_type *pos, pj_list_type *node); /** * Insert the node to the front of the list. This is just an alias for * #pj_list_insert_after(). * * @param list The list. * @param node The element to be inserted. */ PJ_INLINE(void) pj_list_push_front(pj_list_type *list, pj_list_type *node) { pj_list_insert_after(list, node); } /** * Insert all nodes in \a nodes to the target list. * * @param lst The target list. * @param nodes Nodes list. */ PJ_IDECL(void) pj_list_insert_nodes_after(pj_list_type *lst, pj_list_type *nodes); /** * Insert a list to another list before the specified element position. * * @param pos The element to which the node will be inserted before. * @param lst The list to be inserted. */ PJ_IDECL(void) pj_list_insert_list_before(pj_list_type *pos, pj_list_type *lst); /** * Insert a list to another list after the specified element position. * * @param pos The element in the list which will precede the inserted * list. * @param lst The list to be inserted. */ PJ_IDECL(void) pj_list_insert_list_after(pj_list_type *pos, pj_list_type *lst); /** * Remove elements from the source list, and insert them to the destination * list. The elements of the source list will occupy the * front elements of the target list. Note that the node pointed by \a list2 * itself is not considered as a node, but rather as the list descriptor, so * it will not be inserted to the \a list1. The elements to be inserted starts * at \a list2->next. If \a list2 is to be included in the operation, use * \a pj_list_insert_nodes_before. * * @param list1 The destination list. * @param list2 The source list. * */ PJ_IDECL(void) pj_list_merge_first(pj_list_type *list1, pj_list_type *list2); /** * Remove elements from the second list argument, and insert them to the list * in the first argument. The elements from the second list will be appended * to the first list. Note that the node pointed by \a list2 * itself is not considered as a node, but rather as the list descriptor, so * it will not be inserted to the \a list1. The elements to be inserted starts * at \a list2->next. If \a list2 is to be included in the operation, use * \a pj_list_insert_nodes_before. * * @param list1 The element in the list which will precede the inserted * element. * @param list2 The element in the list to be inserted. * */ PJ_IDECL(void) pj_list_merge_last( pj_list_type *list1, pj_list_type *list2); /** * Erase the node from the list it currently belongs. * * @param node The element to be erased. */ PJ_IDECL(void) pj_list_erase(pj_list_type *node); /** * Find node in the list. * * @param list The list head. * @param node The node element to be searched. * * @return The node itself if it is found in the list, or NULL if it is not * found in the list. */ PJ_IDECL(pj_list_type*) pj_list_find_node(pj_list_type *list, pj_list_type *node); /** * Search the list for the specified value, using the specified comparison * function. This function iterates on nodes in the list, started with the * first node, and call the user supplied comparison function until the * comparison function returns ZERO. * * @param list The list head. * @param value The user defined value to be passed in the comparison * function * @param comp The comparison function, which should return ZERO to * indicate that the searched value is found. * * @return The first node that matched, or NULL if it is not found. */ PJ_IDECL(pj_list_type*) pj_list_search(pj_list_type *list, void *value, int (*comp)(void *value, const pj_list_type *node) ); /** * Traverse the list to get the number of elements in the list. * * @param list The list head. * * @return Number of elements. */ PJ_IDECL(pj_size_t) pj_list_size(const pj_list_type *list); /** * @} */ #if PJ_FUNCTIONS_ARE_INLINED # include "list_i.h" #endif PJ_END_DECL #endif /* __PJ_LIST_H__ */