diff options
Diffstat (limited to '3rdparty/plibsys/src/plist.h')
| -rw-r--r-- | 3rdparty/plibsys/src/plist.h | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/3rdparty/plibsys/src/plist.h b/3rdparty/plibsys/src/plist.h new file mode 100644 index 0000000..e72ba0c --- /dev/null +++ b/3rdparty/plibsys/src/plist.h @@ -0,0 +1,199 @@ +/* + * The MIT License + * + * Copyright (C) 2010-2016 Alexander Saprykin <saprykin.spb@gmail.com> + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * 'Software'), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be + * included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * @file plist.h + * @brief Singly linked list + * @author Alexander Saprykin + * + * A singly linked list is a data structure consists of the nodes which + * represent a sequence. Each node contains a data pointer and a pointer to the + * next node. Every node has a link only to the next node, hence list is a + * singly linked (in a single direction). + * + * As the singly linked list is a linear collection of the nodes with the + * sequential access, it has an O(N) average complexity for appending, removing + * and searching operations. Prepending a node takes O(1) constant time. Thus it + * is not intended for heavy usage, please refer to #PHashTable or #PTree if you + * are working with large data sets. + * + * Before the first usage you must initialize a #PList variable to NULL. After + * that you can use the p_list_append(), p_list_prepend(), p_list_remove() and + * p_list_reverse() routines to update that variable: + * @code + * PList *list; + * ppointer data; + * + * list = NULL; + * data = my_obj_new (); + * + * list = p_list_append (list, data); + * @endcode + * #PList stores only the pointers to the data, so you must free used memory + * manually, p_list_free() only frees list's internal memory, not the data it + * stores the pointers for. The best approach to free used memory is the + * p_list_foreach() routine: + * @code + * PList *list; + * ... + * p_list_foreach (list, (PFunc) my_free_func, my_data); + * p_list_free (list); + * @endcode + * Also you can use #P_INT_TO_POINTER and #P_POINTER_TO_INT macros to store + * integers (up to 32-bit) without allocating memory for them: + * @code + * PList *list; + * pint a; + * + * list = p_list_append (list, P_INT_TO_POINTER (12)); + * a = P_POINTER_TO_INT (list->data); + * @endcode + * #PList can store several nodes with the same pointer value, but + * p_list_remove() will remove only the first matching node. + * + * If you need to add large amount of nodes at once it is better to prepend them + * and then reverse the list. + */ + +#if !defined (PLIBSYS_H_INSIDE) && !defined (PLIBSYS_COMPILATION) +# error "Header files shouldn't be included directly, consider using <plibsys.h> instead." +#endif + +#ifndef PLIBSYS_HEADER_PLIST_H +#define PLIBSYS_HEADER_PLIST_H + +#include <pmacros.h> +#include <ptypes.h> + +P_BEGIN_DECLS + +/** Typedef for a list node. */ +typedef struct PList_ PList; + +/** Node for a singly linked list. */ +struct PList_ { + ppointer data; /**< Pointer to the node data. */ + PList *next; /**< Next list node. */ +}; + +/** + * @brief Appends data to a list. + * @param list #PList for appending the data. + * @param data Data to append. + * @return Pointer to the updated list in case of success, @a list otherwise. + * @since 0.0.1 + * + * Before appending the first node to the list, @a list argument must be + * initialized with NULL. Otherwise behavior is unpredictable. + */ +P_LIB_API PList * p_list_append (PList *list, + ppointer data) P_GNUC_WARN_UNUSED_RESULT; + +/** + * @brief Removes data from a list. + * @param list List to remove the data from. + * @param data Data to remove. + * @return Pointer to the updated list in case of success, @a list otherwise. + * @since 0.0.1 + * + * It searches for the first matching occurrence in the @a list and removes + * that node. Note that it removes only the pointer from the @a list, not the + * data it pointers to, so you need to free the data manually. + */ +P_LIB_API PList * p_list_remove (PList *list, + ppointer data) P_GNUC_WARN_UNUSED_RESULT; + +/** + * @brief Calls a specified function for each list node. + * @param list List to go through. + * @param func Pointer for the callback function. + * @param user_data User defined data, may be NULL. + * @since 0.0.1 + * + * This function goes through the whole @a list and calls @a func for each node. + * The @a func will receive pointer to the node's data and @a user_data. You can + * use it to free the data: + * @code + * p_list_foreach (list, (PFunc) free, NULL); + * p_list_free (list); + * @endcode + */ +P_LIB_API void p_list_foreach (PList *list, + PFunc func, + ppointer user_data); + +/** + * @brief Frees list memory. + * @param list List to free. + * @since 0.0.1 + * + * This function frees only the list's internal memory, not the data in the + * pointers stored in the nodes. Don't forget to free all the data stored in the + * list manually. + */ +P_LIB_API void p_list_free (PList *list); + +/** + * @brief Gets the last node from the list. + * @param list List to get the node from. + * @return Pointer to the last @a list node, NULL if the @a list is empty. + * @since 0.0.1 + */ +P_LIB_API PList * p_list_last (PList *list); + +/** + * @brief Gets the number of list nodes. + * @param list List to count nodes in. + * @return Number of nodes in the @a list. + * @since 0.0.1 + * @note This function will iterate through the whole @a list, so don't use it + * in condition of the for-loop or in the code which is repeated a lot of times. + */ +P_LIB_API psize p_list_length (const PList *list); + +/** + * @brief Prepends data to a list. + * @param list #PList for prepending the data. + * @param data Data to prepend. + * @return Pointer to the updated list in case of success, @a list otherwise. + * @since 0.0.1 + * + * Before prepending the first node to the list, @a list argument must be + * initialized with NULL. Otherwise behavior is unpredictable. + */ +P_LIB_API PList * p_list_prepend (PList *list, + ppointer data) P_GNUC_WARN_UNUSED_RESULT; + +/** + * @brief Reverses the list order. + * @param list #PList to reverse the order. + * @return Pointer to the top of the reversed list. + * @since 0.0.1 + */ +P_LIB_API PList * p_list_reverse (PList *list) P_GNUC_WARN_UNUSED_RESULT; + +P_END_DECLS + +#endif /* PLIBSYS_HEADER_PLIST_H */ |