--- a/ucx/avl.h Wed Nov 22 12:59:13 2017 +0100
+++ b/ucx/avl.h Sun Jan 21 12:13:09 2018 +0100
@@ -1,7 +1,7 @@
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
- * Copyright 2015 Olaf Wintermann. All rights reserved.
+ * Copyright 2016 Olaf Wintermann. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
@@ -44,7 +44,7 @@
#include "ucx.h"
#include "allocator.h"
-#include <stdint.h>
+#include <inttypes.h>
#ifdef __cplusplus
extern "C" {
@@ -134,7 +134,7 @@
UcxAVLTree *ucx_avl_new_a(cmp_func cmpfunc, UcxAllocator *allocator);
/**
- * Destroys an UcxAVLTree.
+ * Destroys a UcxAVLTree.
* @param tree the tree to destroy
*/
void ucx_avl_free(UcxAVLTree *tree);
@@ -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