add plibsys

1 files changed, 230 insertions, 0 deletions

diff --git a/3rdparty/plibsys/src/ptree.h b/3rdparty/plibsys/src/ptree.h
new file mode 100644
index 0000000..d43e7ae
--- /dev/null
+++ b/3rdparty/plibsys/src/ptree.h
@@ -0,0 +1,230 @@
+/*
+ * The MIT License
+ *
+ * Copyright (C) 2015-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 ptree.h
+ * @brief Binary tree data structure
+ * @author Alexander Saprykin
+ *
+ * #PTree represents a binary search tree structure for faster lookup than
+ * a plain array or a list. It has average O(logN) time complexity to search
+ * a key-value pair, and O(N) in the worst case (when a tree is degenerated into
+ * the list).
+ *
+ * Currently #PTree supports the following tree types:
+ * - unbalanced binary search tree;
+ * - red-black self-balancing tree;
+ * - AVL self-balancing tree.
+ *
+ * Use p_tree_new(), or its detailed variations like p_tree_new_with_data() and
+ * p_tree_new_full() to create a tree structure. Take attention that a caller
+ * owns the key and the value data passed when inserting new nodes, so you
+ * should manually free the memory after the tree usage. Or you can provide
+ * destroy notification functions for the keys and the values separately.
+ *
+ * New key-value pairs can be inserted with p_tree_insert() and removed with
+ * p_tree_remove().
+ *
+ * Use p_tree_lookup() to find the value by a given key. You can also traverse
+ * the tree in-order with p_tree_foreach().
+ *
+ * Release memory with p_tree_free() or clear a tree with p_tree_clear(). Keys
+ * and values would be destroyed only if the corresponding notification
+ * functions were provided.
+ *
+ * Note: all operations with the tree are non-recursive, only iterative calls
+ * are used.
+ */
+
+#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_PTREE_H
+#define PLIBSYS_HEADER_PTREE_H
+
+#include <pmacros.h>
+#include <ptypes.h>
+
+P_BEGIN_DECLS
+
+/** Tree opaque data structure. */
+typedef struct PTree_ PTree;
+
+/** Internal data organization algorithm for #PTree. */
+typedef enum PTreeType_ {
+	P_TREE_TYPE_BINARY	= 0,	/**< Unbalanced binary tree.		*/
+	P_TREE_TYPE_RB		= 1,	/**< Red-black self-balancing tree.	*/
+	P_TREE_TYPE_AVL		= 2	/**< AVL self-balancing tree.		*/
+} PTreeType;
+
+/**
+ * @brief Initializes new #PTree.
+ * @param type Tree algorithm type to use, can't be changed later.
+ * @param func Key compare function.
+ * @return Newly initialized #PTree object in case of success, NULL otherwise.
+ * @since 0.0.1
+ *
+ * The caller takes ownership of all the keys and the values passed to the tree.
+ */
+P_LIB_API PTree *	p_tree_new		(PTreeType		type,
+						 PCompareFunc		func);
+
+/**
+ * @brief Initializes new #PTree with additional data.
+ * @param type Tree algorithm type to use, can't be changed later.
+ * @param func Key compare function.
+ * @param data Data to be passed to @a func along with the keys.
+ * @return Newly initialized #PTree object in case of success, NULL otherwise.
+ * @since 0.0.1
+ *
+ * The caller takes ownership of all the keys and the values passed to the tree.
+ */
+P_LIB_API PTree *	p_tree_new_with_data	(PTreeType		type,
+						 PCompareDataFunc	func,
+						 ppointer		data);
+
+/**
+ * @brief Initializes new #PTree with additional data and memory management.
+ * @param type Tree algorithm type to use, can't be changed later.
+ * @param func Key compare function.
+ * @param data Data to be passed to @a func along with the keys.
+ * @param key_destroy Function to call on every key before the node destruction,
+ * maybe NULL.
+ * @param value_destroy Function to call on every value before the node
+ * destruction, maybe NULL.
+ * @return Newly initialized #PTree object in case of success, NULL otherwise.
+ * @since 0.0.1
+ *
+ * Upon every node destruction the corresponding key and value functions would
+ * be called.
+ */
+P_LIB_API PTree *	p_tree_new_full		(PTreeType		type,
+						 PCompareDataFunc	func,
+						 ppointer		data,
+						 PDestroyFunc		key_destroy,
+						 PDestroyFunc		value_destroy);
+
+/**
+ * @brief Inserts a new key-value pair into a tree.
+ * @param tree #PTree to insert a node in.
+ * @param key Key to insert.
+ * @param value Value corresponding to the given @a key.
+ * @since 0.0.1
+ *
+ * If the @a key already exists in the tree then it will be replaced with the
+ * new one. If a key destroy function was provided it would be called on the old
+ * key. If a value destroy function was provided it would be called on the old
+ * value.
+ */
+P_LIB_API void		p_tree_insert		(PTree			*tree,
+						 ppointer		key,
+						 ppointer		value);
+
+/**
+ * @brief Removes a key from a tree.
+ * @param tree #PTree to remove a key from.
+ * @param key A key to lookup.
+ * @return TRUE if the key was removed, FALSE if the key was not found.
+ * @since 0.0.1
+ *
+ * If a key destroy function was provided it would be called on the key. If a
+ * value destroy function was provided it would be called on the old value.
+ */
+P_LIB_API pboolean	p_tree_remove		(PTree			*tree,
+						 pconstpointer		key);
+
+/**
+ * @brief Lookups a value by a given key.
+ * @param tree #PTree to lookup in.
+ * @param key Key to lookup.
+ * @return Value for the given @a key in case of success, NULL otherwise.
+ * @since 0.0.1
+ */
+P_LIB_API ppointer	p_tree_lookup		(PTree			*tree,
+						 pconstpointer		key);
+
+/**
+ * @brief Iterates in-order through the tree nodes.
+ * @param tree A tree to traverse.
+ * @param traverse_func Function for traversing.
+ * @param user_data Additional (maybe NULL) user-provided data for the
+ * @a traverse_func.
+ * @since 0.0.1
+ * @note Morris (non-recursive, non-stack) traversing algorithm is being used.
+ *
+ * The tree should not be modified while traversing. The internal tree structure
+ * can be modified along the traversing process, so keep it in mind for
+ * concurrent access.
+ */
+P_LIB_API void		p_tree_foreach		(PTree			*tree,
+						 PTraverseFunc		traverse_func,
+						 ppointer		user_data);
+
+/**
+ * @brief Clears a tree.
+ * @param tree #PTree to clear.
+ * @since 0.0.1
+ * @note Modified Morris (non-recursive, non-stack) traversing algorithm is
+ * being used.
+ *
+ * All the keys will be deleted. Key and value destroy functions would be called
+ * on every node if any of them was provided.
+ */
+P_LIB_API void		p_tree_clear		(PTree			*tree);
+
+/**
+ * @brief Gets a tree algorithm type.
+ * @param tree #PTree object to get the type for.
+ * @return Tree internal organization algorithm used for a given object.
+ * @since 0.0.1
+ */
+P_LIB_API PTreeType	p_tree_get_type		(const PTree		*tree);
+
+/**
+ * @brief Gets node count.
+ * @param tree #PTree to get node count for.
+ * @return Node count.
+ * @since 0.0.1
+ *
+ * If the tree is empty or an invalid pointer is given it returns 0.
+ */
+P_LIB_API pint		p_tree_get_nnodes	(const PTree		*tree);
+
+/**
+ * @brief Frees a previously initialized tree object.
+ * @param tree #PTree object to free.
+ * @since 0.0.1
+ * @note Modified Morris (non-recursive, non-stack) traversing algorithm is
+ * being used.
+ *
+ * All the keys will be deleted. Key and value destroy functions would be called
+ * on every node if any of them was provided.
+ */
+P_LIB_API void		p_tree_free		(PTree			*tree);
+
+P_END_DECLS
+
+#endif /* PLIBSYS_HEADER_PTREE_H */