};
-static GTreeNode* g_tree_node_new (gpointer key,
- gpointer value);
-static guint g_tree_priority (GTreeNode *node);
-static void g_tree_insert_internal (GTree *tree,
- gpointer key,
- gpointer value,
- gboolean replace);
-static gboolean g_tree_remove_internal (GTree *tree,
- gconstpointer key,
- gboolean steal);
-static GTreeNode *g_tree_find_node (GTree *tree,
- gconstpointer key);
-static gint g_tree_node_pre_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gint g_tree_node_in_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gint g_tree_node_post_order (GTreeNode *node,
- GTraverseFunc traverse_func,
- gpointer data);
-static gpointer g_tree_node_search (GTreeNode *node,
- GCompareFunc search_func,
- gconstpointer data);
-static gint g_tree_node_height (GTreeNode *node);
-static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
-static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
+static GTreeNode* g_tree_node_new (gpointer key,
+ gpointer value);
+static guint g_tree_priority (GTreeNode *node);
+static void g_tree_insert_internal (GTree *tree,
+ gpointer key,
+ gpointer value,
+ gboolean replace);
+static gboolean g_tree_remove_internal (GTree *tree,
+ gconstpointer key,
+ gboolean steal);
+static GTreeNode *g_tree_find_node (GTree *tree,
+ gconstpointer key,
+ GTreeSearchType search_type);
+static gint g_tree_node_pre_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_tree_node_in_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gint g_tree_node_post_order (GTreeNode *node,
+ GTraverseFunc traverse_func,
+ gpointer data);
+static gpointer g_tree_node_search (GTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data,
+ GTreeSearchType search_type);
+static gint g_tree_node_height (GTreeNode *node);
+static GTreeNode* g_tree_node_rotate_left (GTreeNode *node);
+static GTreeNode* g_tree_node_rotate_right (GTreeNode *node);
#ifdef G_TREE_DEBUG
-static void g_tree_node_check (GTreeNode *node);
+static void g_tree_node_check (GTreeNode *node);
#endif
static GTreeNode*
g_tree_lookup (GTree *tree,
gconstpointer key)
{
+ return g_tree_lookup_related (tree, key, G_TREE_SEARCH_EXACT);
+}
+
+/**
+ * g_tree_lookup_related:
+ * @tree: a #GTree.
+ * @key: the key to look up.
+ * @search_type: the search behavior if the @key is not present in the #GTree,
+ * one of %G_TREE_SEARCH_EXACT, %G_TREE_SEARCH_SUCCESSOR, and
+ * %G_TREE_SEARCH_PREDECESSOR.
+ *
+ * Gets a value corresponding to the given key.
+ *
+ * If the given @key is present in the tree, then its corresponding value is
+ * always returned. If it is not, then the @search_type will define the
+ * function's behavior. If @search_type is %G_TREE_SEARCH_EXACT, the
+ * function will return %NULL if the @key is not found. If @search_type is
+ * %G_TREE_SEARCH_SUCCESSOR, the function will find the next larger key that
+ * is present in the tree and return its value, or %NULL if there are no keys
+ * larger than @key in the tree. If @search_type is
+ * %G_TREE_SEARCH_PREDECESSOR, the function will find the next smaller key that
+ * is present in the tree and return its value, or %NULL if there are no keys
+ * smaller than @key in the tree.
+ * Since a #GTree is
+ * automatically balanced as key/value pairs are added, key lookup is very
+ * fast.
+ *
+ * Return value: the value corresponding to the found key, or %NULL if no
+ * matching key was found.
+ **/
+gpointer
+g_tree_lookup_related (GTree *tree,
+ gconstpointer key,
+ GTreeSearchType search_type)
+{
GTreeNode *node;
g_return_val_if_fail (tree != NULL, NULL);
- node = g_tree_find_node (tree, key);
+ node = g_tree_find_node (tree, key, search_type);
return node ? node->value : NULL;
}
g_return_val_if_fail (tree != NULL, FALSE);
- node = g_tree_find_node (tree, lookup_key);
+ node = g_tree_find_node (tree, lookup_key, G_TREE_SEARCH_EXACT);
if (node)
{
GCompareFunc search_func,
gconstpointer user_data)
{
+ return g_tree_search_related (tree, search_func, user_data,
+ G_TREE_SEARCH_EXACT);
+}
+
+/**
+ * g_tree_search_related:
+ * @tree: a #GTree.
+ * @search_func: a function used to search the #GTree.
+ * @user_data: the data passed as the second argument to the @search_func
+ * @search_type: the search behavior if the @key is not present in the #GTree,
+ * one of %G_TREE_SEARCH_EXACT, %G_TREE_SEARCH_SUCCESSOR, and
+ * %G_TREE_SEARCH_PREDECESSOR.
+ *
+ * Searches a #GTree using @search_func.
+ *
+ * The @search_func is called with a pointer to the key of a key/value pair in
+ * the tree, and the passed in @user_data. If @search_func returns 0 for a
+ * key/value pair, then g_tree_search_func() will return the value of that
+ * pair. If @search_func returns -1, searching will proceed among the
+ * key/value pairs that have a smaller key; if @search_func returns 1,
+ * searching will proceed among the key/value pairs that have a larger key.
+ * If @search_func never returns 0 before searching the entire height of the
+ * tree, then the @search_type will define what the function returns.
+ * If @search_type is %G_TREE_SEARCH_EXACT, the
+ * function will return %NULL. If @search_type is
+ * %G_TREE_SEARCH_SUCCESSOR, the function will return the value corresponding
+ * to the last key at which @search_func returned -1. This key would be the
+ * successor to the element being searched for. If @search_type is
+ * %G_TREE_SEARCH_PREDECESSOR, the function return the value corresponding
+ * to the last key at which @search_func returned 1. This key would be the
+ * predecessor to the element being searched for.
+ *
+ * Return value: the value corresponding to the found key, or %NULL if no
+ * matching key was found.
+ **/
+gpointer
+g_tree_search_related (GTree *tree,
+ GCompareFunc search_func,
+ gconstpointer user_data,
+ GTreeSearchType search_type)
+{
g_return_val_if_fail (tree != NULL, NULL);
- if (tree->root)
- return g_tree_node_search (tree->root, search_func, user_data);
- else
- return NULL;
+ return g_tree_node_search (tree->root, search_func, user_data, search_type);
}
static gint
}
static GTreeNode *
-g_tree_find_node (GTree *tree,
- gconstpointer key)
+g_tree_find_node (GTree *tree,
+ gconstpointer key,
+ GTreeSearchType search_type)
{
- GTreeNode *node;
+ GTreeNode *node, *remember;
gint cmp;
node = tree->root;
if (!node)
return NULL;
+ remember = NULL;
while (1)
{
cmp = tree->key_compare (key, node->key, tree->key_compare_data);
return node;
else if (cmp < 0)
{
+ if (search_type == G_TREE_SEARCH_SUCCESSOR)
+ remember = node;
if (!node->left_child)
- return NULL;
+ return remember;
node = node->left;
}
else
{
+ if (search_type == G_TREE_SEARCH_PREDECESSOR)
+ remember = node;
if (!node->right_child)
- return NULL;
+ return remember;
node = node->right;
}
}
static gpointer
-g_tree_node_search (GTreeNode *node,
- GCompareFunc search_func,
- gconstpointer data)
+g_tree_node_search (GTreeNode *node,
+ GCompareFunc search_func,
+ gconstpointer data,
+ GTreeSearchType search_type)
{
gint dir;
+ GTreeNode *remember;
if (!node)
return NULL;
+ remember = NULL;
while (1)
{
dir = (* search_func) (node->key, data);
return node->value;
else if (dir < 0)
{
+ if (search_type == G_TREE_SEARCH_SUCCESSOR)
+ remember = node;
if (!node->left_child)
- return NULL;
+ return remember;
node = node->left;
}
else
{
+ if (search_type == G_TREE_SEARCH_PREDECESSOR)
+ remember = node;
if (!node->right_child)
- return NULL;
+ return remember;
node = node->right;
}
projects / dana / cg-glib.git / blobdiff