From acc3d292dd50d6b89dd7c93058478f65f782c08f Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Wed, 28 Oct 2009 16:05:44 -0400 Subject: [PATCH] Add the g_lookup_related() and g_search_related() functions. These functions search in a GTree for a key, and can return the next larger/smaller key instead if the search key is not found. --- glib/gtree.c | 176 ++++++++++++++++++++++++++++++++++------------ glib/gtree.h | 15 ++++ tests/tree-test.c | 40 ++++++++++- 3 files changed, 185 insertions(+), 46 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 6c69c885..8870a8f5 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -62,35 +62,37 @@ struct _GTreeNode }; -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* @@ -702,12 +704,47 @@ g_tree_remove_internal (GTree *tree, gpointer 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; } @@ -736,7 +773,7 @@ g_tree_lookup_extended (GTree *tree, 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) { @@ -859,13 +896,51 @@ gpointer g_tree_search (GTree *tree, 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 @@ -915,16 +990,18 @@ g_tree_nnodes (GTree *tree) } 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); @@ -932,15 +1009,19 @@ g_tree_find_node (GTree *tree, 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; } @@ -1017,15 +1098,18 @@ g_tree_node_post_order (GTreeNode *node, } 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); @@ -1033,15 +1117,19 @@ g_tree_node_search (GTreeNode *node, 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; } diff --git a/glib/gtree.h b/glib/gtree.h index db06ba3b..45f15b6d 100644 --- a/glib/gtree.h +++ b/glib/gtree.h @@ -35,6 +35,14 @@ G_BEGIN_DECLS +/* Tree Search Types */ +typedef enum +{ + G_TREE_SEARCH_EXACT, + G_TREE_SEARCH_SUCCESSOR, + G_TREE_SEARCH_PREDECESSOR +} GTreeSearchType; + typedef struct _GTree GTree; typedef gboolean (*GTraverseFunc) (gpointer key, @@ -69,6 +77,9 @@ gboolean g_tree_lookup_extended (GTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value); +gpointer g_tree_lookup_related (GTree *tree, + gconstpointer key, + GTreeSearchType search_type); void g_tree_foreach (GTree *tree, GTraverseFunc func, gpointer user_data); @@ -83,6 +94,10 @@ void g_tree_traverse (GTree *tree, gpointer g_tree_search (GTree *tree, GCompareFunc search_func, gconstpointer user_data); +gpointer g_tree_search_related (GTree *tree, + GCompareFunc search_func, + gconstpointer user_data, + GTreeSearchType search_type); gint g_tree_height (GTree *tree); gint g_tree_nnodes (GTree *tree); diff --git a/tests/tree-test.c b/tests/tree-test.c index bd7f13ed..709b5044 100644 --- a/tests/tree-test.c +++ b/tests/tree-test.c @@ -80,7 +80,8 @@ traverse_preorder (gpointer key, static gint calc_height_recur(char *inorder, char *preorder, int l, int r) { - gint i, parentpos_in, left, right; + gint i, left, right; + char *parentpos_in; char parent; if (r < l) return 0; @@ -148,7 +149,7 @@ int main (int argc, char *argv[]) { - gint i; + gint i, n; GTree *tree; gboolean removed; char c, d; @@ -156,8 +157,43 @@ main (int argc, tree = g_tree_new (my_compare); + n = strlen(chars); + for (i = n-1; i >= 0; i--) { + gchar *r; + + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_SUCCESSOR); + g_assert((i == n-1 && r == NULL) || (r && *r == chars[i+1])); + + g_tree_insert (tree, &chars[i], &chars[i]); + + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_PREDECESSOR); + g_assert(r && *r == chars[i]); + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_SUCCESSOR); + g_assert(r && *r == chars[i]); + } + g_assert(n == g_tree_nnodes(tree)); + + g_tree_unref (tree); + tree = g_tree_new (my_compare); + for (i = 0; chars[i]; i++) { + gchar *r; + + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_PREDECESSOR); + g_assert((i == 0 && r == NULL) || (r && *r == chars[i-1])); + g_tree_insert (tree, &chars[i], &chars[i]); + + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_PREDECESSOR); + g_assert(r && *r == chars[i]); + r = g_tree_lookup_related (tree, &chars[i], + G_TREE_SEARCH_SUCCESSOR); + g_assert(r && *r == chars[i]); } g_assert(i == g_tree_nnodes(tree)); -- 2.34.1