--- a/ucx/avl.h Fri Sep 22 20:19:00 2017 +0200 +++ b/ucx/avl.h Fri Sep 22 20:42:33 2017 +0200 @@ -164,6 +164,68 @@ void *ucx_avl_get(UcxAVLTree *tree, intptr_t key); /** + * A mode for #ucx_avl_find_node() with the same behavior as + * #ucx_avl_get_node(). + */ +#define UCX_AVL_FIND_EXACT 0 +/** + * A mode for #ucx_avl_find_node() finding the node whose key is at least + * as large as the specified key. + */ +#define UCX_AVL_FIND_LOWER_BOUNDED 1 +/** + * A mode for #ucx_avl_find_node() finding the node whose key is at most + * as large as the specified key. + */ +#define UCX_AVL_FIND_UPPER_BOUNDED 2 +/** + * A mode for #ucx_avl_find_node() finding the node with a key that is as close + * to the specified key as possible. If the key is present, the behavior is + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on + * empty trees. + */ +#define UCX_AVL_FIND_CLOSEST 3 + +/** + * Finds a node within the tree. The following modes are supported: + * <ul> + * <li>#UCX_AVL_FIND_EXACT: the same behavior as #ucx_avl_get_node()</li> + * <li>#UCX_AVL_FIND_LOWER_BOUNDED: finds the node whose key is at least + * as large as the specified key</li> + * <li>#UCX_AVL_FIND_UPPER_BOUNDED: finds the node whose key is at most + * as large as the specified key</li> + * <li>#UCX_AVL_FIND_CLOSEST: finds the node with a key that is as close to + * the specified key as possible. If the key is present, the behavior is + * like #ucx_avl_get_node(). This mode only returns <code>NULL</code> on + * empty trees.</li> + * </ul> + * + * The distance function provided MUST agree with the compare function of + * the AVL tree. + * + * @param tree the UcxAVLTree + * @param key the key + * @param dfnc the distance function + * @param mode the find mode + * @return the node (or <code>NULL</code>, if no node can be found) + */ +UcxAVLNode *ucx_avl_find_node(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode); + +/** + * Finds a value within the tree. + * See #ucx_avl_find_node() for details. + * + * @param tree the UcxAVLTree + * @param key the key + * @param dfnc the distance function + * @param mode the find mode + * @return the value (or <code>NULL</code>, if no value can be found) + */ +void *ucx_avl_find(UcxAVLTree *tree, intptr_t key, + distance_func dfnc, int mode); + +/** * Puts a key/value pair into the tree. * * Attention: use this function only, if a possible old value does not need @@ -196,7 +258,7 @@ * * Note: the specified node is logically removed. The tree implementation * decides which memory area is freed. In most cases the here provided node - * is freed, so it's further use is generally undefined. + * is freed, so its further use is generally undefined. * * @param tree the UcxAVLTree * @param node the node to remove @@ -241,6 +303,22 @@ */ size_t ucx_avl_count(UcxAVLTree *tree); +/** + * Finds the in-order predecessor of the given node. + * @param node an AVL node + * @return the in-order predecessor of the given node, or <code>NULL</code> if + * the given node is the in-order minimum + */ +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node); + +/** + * Finds the in-order successor of the given node. + * @param node an AVL node + * @return the in-order successor of the given node, or <code>NULL</code> if + * the given node is the in-order maximum + */ +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node); + #ifdef __cplusplus } #endif