toolkit: comparison ucx/avl.h

-:11f3bb408051
+:62921b370c60
 /*
 * 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:
 *
 *   1. Redistributions of source code must retain the above copyright
 #ifndef UCX_AVL_H
 #define UCX_AVL_H
 #include "ucx.h"
 #include "allocator.h"
-#include <stdint.h>
+#include <inttypes.h>
 #ifdef	__cplusplus
 extern "C" {
 #endif
 * @return a new UcxAVLTree object
 */
 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);
 /**
 * @param tree the UcxAVLTree
 * @param key the key
 * @return the value (or <code>NULL</code>, if the key is not present)
 */
 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
 /**
 * Removes a node from the AVL tree.
 *
 * 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
 * @return zero, if and only if an element has been removed
 */
 * @param tree the AVL tree
 * @return the node count
 */
 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
 #endif	/* UCX_AVL_H */

Mercurial > hg > toolkit / file comparison

comparison: ucx/avl.h

ucx/avl.h