From f7837cb683bc4da9cd27c84ac4a22dd11187539e Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Thu, 12 Nov 2009 18:23:09 -0500 Subject: [PATCH] Add the versioned/persistent GTree interface. Change g_tree_lookup_related() to not take a version, but search on the current/latest version of the GTree. Add a func_v() version for each of the g_tree_lookup/foreach/search/height functions, which takes an extra version argument, which is the version of the GTree for which to query. --- glib/gtree.c | 265 ++++++++++++++++++++++++++++++++++++++++++---- glib/gtree.h | 32 +++++- tests/tree-test.c | 46 ++++---- 3 files changed, 301 insertions(+), 42 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 7f5e81ce..9dbe6b37 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -124,7 +124,6 @@ static gpointer g_tree_node_search (GTreeNode *node, gconstpointer data, GTreeSearchType search_type, guint version); -static gint g_tree_node_height (GTreeNode *node); static GTreeNode* g_tree_node_rotate_left (GTree *tree, GTreeNode *node); static GTreeNode* g_tree_node_rotate_right (GTree *tree, @@ -304,7 +303,7 @@ g_tree_root_find_version (GTree *tree, }; if (v[0].version <= version) - return v; + return v; /* fast when looking for the current version */ l = v+1; r = v+(nv-1); @@ -1382,7 +1381,32 @@ gpointer g_tree_lookup (GTree *tree, gconstpointer key) { - return g_tree_lookup_related (tree, key, G_TREE_SEARCH_EXACT, tree->version); + return g_tree_lookup_related_v (tree, tree->version, key, + G_TREE_SEARCH_EXACT); +} + +/** + * g_tree_lookup_v: + * @tree: a #GTree. + * @version: the version of the tree within which to search. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @key: the key to look up. + * + * Gets the value corresponding to the given key in a specified @version of + * the #GTree. Since a #GTree is + * automatically balanced as key/value pairs are added, key lookup is very + * fast. + * + * Return value: the value corresponding to the key, or %NULL if the key was + * not found. + **/ +gpointer +g_tree_lookup_v (GTree *tree, + guint version, + gconstpointer key) +{ + return g_tree_lookup_related_v (tree, version, key, G_TREE_SEARCH_EXACT); } /** @@ -1392,8 +1416,6 @@ g_tree_lookup (GTree *tree, * @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. - * @version: the version of the tree within which to search. If - * g_tree_next_version() has not been used, then this is 0. * * Gets a value corresponding to the given key. * @@ -1417,8 +1439,47 @@ g_tree_lookup (GTree *tree, gpointer g_tree_lookup_related (GTree *tree, gconstpointer key, - GTreeSearchType search_type, - guint version) + GTreeSearchType search_type) +{ + return g_tree_lookup_related_v (tree, tree->version, key, search_type); +} + +/** + * g_tree_lookup_related_v: + * @tree: a #GTree. + * @version: the version of the tree within which to search. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @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 in a specified @version of the + * #GTree. + * + * 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_v (GTree *tree, + guint version, + gconstpointer key, + GTreeSearchType search_type) { GTreeNode *node; @@ -1449,12 +1510,42 @@ g_tree_lookup_extended (GTree *tree, gconstpointer lookup_key, gpointer *orig_key, gpointer *value) +{ + return g_tree_lookup_extended_v (tree, tree->version, lookup_key, orig_key, + value); +} + +/** + * g_tree_lookup_extended_v: + * @tree: a #GTree. + * @version: the version of the tree within which to search. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @lookup_key: the key to 5Blook up. + * @orig_key: returns the original key. + * @value: returns the value associated with the key. + * + * Looks up a key in a specified @version of the #GTree, returning the + * original key and the + * associated value and a #gboolean which is %TRUE if the key was found. This + * is useful if you need to free the memory allocated for the original key, + * for example before calling g_tree_remove(). + * + * Return value: %TRUE if the key was found in the #GTree. + **/ +gboolean +g_tree_lookup_extended_v (GTree *tree, + guint version, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value) { GTreeNode *node; g_return_val_if_fail (tree != NULL, FALSE); + g_return_val_if_fail (version <= tree->version, FALSE); - node = g_tree_find_node (tree, lookup_key, G_TREE_SEARCH_EXACT, tree->version); + node = g_tree_find_node (tree, lookup_key, G_TREE_SEARCH_EXACT, version); if (node) { @@ -1488,22 +1579,52 @@ void g_tree_foreach (GTree *tree, GTraverseFunc func, gpointer user_data) +{ + g_tree_foreach_v (tree, tree->version, func, user_data); +} + +/** + * g_tree_foreach_v: + * @tree: a #GTree. + * @version: the version of the tree to traverse. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @func: the function to call for each node visited. If this function + * returns %TRUE, the traversal is stopped. + * @user_data: user data to pass to the function. + * + * Calls the given function for each of the key/value pairs in a + * specified @version of the #GTree. + * The function is passed the key and value of each pair, and the given + * @data parameter. The tree is traversed in sorted order. + * + * The tree may not be modified while iterating over it (you can't + * add/remove items). To remove all items matching a predicate, you need + * to add each item to a list in your #GTraverseFunc as you walk over + * the tree, then walk the list and remove each item. + **/ +void +g_tree_foreach_v (GTree *tree, + guint version, + GTraverseFunc func, + gpointer user_data) { GTreeNode *node; g_return_if_fail (tree != NULL); + g_return_if_fail (version <= tree->version); if (!tree->r[0].root) return; - node = g_tree_first_node (tree, tree->version); + node = g_tree_first_node (tree, version); while (node) { if ((*func) (node->data->key, node->data->value, user_data)) break; - node = g_tree_node_next (node, tree->version); + node = g_tree_node_next (node, version); } } @@ -1578,8 +1699,43 @@ 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); + return g_tree_search_v (tree, tree->version, search_func, user_data); +} + +/** + * g_tree_search_v: + * @tree: a #GTree. + * @version: the version of the tree within which to search. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @search_func: a function used to search the #GTree. + * @user_data: the data passed as the second argument to the @search_func + * function. + * + * Searches a specified @version of the #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. + * + * Return value: the value corresponding to the found key, or %NULL if the key + * was not found. + **/ +gpointer +g_tree_search_v (GTree *tree, + guint version, + GCompareFunc search_func, + gconstpointer user_data) +{ + g_return_val_if_fail (tree != NULL, NULL); + g_return_val_if_fail (version <= tree->version, NULL); + + return g_tree_node_search (g_tree_root_find_version (tree, version)->root, + search_func, user_data, G_TREE_SEARCH_EXACT, + version); } /** @@ -1618,21 +1774,70 @@ g_tree_search_related (GTree *tree, GCompareFunc search_func, gconstpointer user_data, GTreeSearchType search_type) +{ + return g_tree_search_related_v (tree, tree->version, search_func, user_data, + search_type); +} + +/** + * g_tree_search_related_v: + * @tree: a #GTree. + * @version: the version of the tree within which to search. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * @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 specified @version of the #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_v (GTree *tree, + guint version, + GCompareFunc search_func, + gconstpointer user_data, + GTreeSearchType search_type) { g_return_val_if_fail (tree != NULL, NULL); + g_return_val_if_fail (version <= tree->version, NULL); - return g_tree_node_search (tree->r[0].root, + return g_tree_node_search (g_tree_root_find_version (tree, version)->root, search_func, user_data, search_type, - tree->version); + version); } static gint -g_tree_node_height(GTreeNode *node) +g_tree_node_height (GTreeNode *node, + guint version) { + GTreeNodeVersion *nv; gint l = 0, r = 0; if (node == NULL) return 0; - if (node->v[0].left) l = g_tree_node_height (node->v[0].left); - if (node->v[0].right) r = g_tree_node_height (node->v[0].right); + nv = g_tree_node_find_version (node, version); + if (nv->left) l = g_tree_node_height (nv->left, version); + if (nv->right) r = g_tree_node_height (nv->right, version); return 1 + MAX(l, r); } @@ -1650,10 +1855,34 @@ g_tree_node_height(GTreeNode *node) **/ gint g_tree_height (GTree *tree) +{ + return g_tree_height_v (tree, tree->version); +} + +/** + * g_tree_height_v: + * @tree: a #GTree. + * @version: the version of the tree which should be queried. If + * g_tree_next_version() has not been used, then this is 0. This value + * must be at most the value returned by g_tree_current_version(). + * + * Gets the height of a specified @version of the #GTree. + * + * If the #GTree contains no nodes, the height is 0. + * If the #GTree contains only one root node the height is 1. + * If the root node has children the height is 2, etc. + * + * Return value: the height of the #GTree. + **/ +gint +g_tree_height_v (GTree *tree, + guint version) { g_return_val_if_fail (tree != NULL, 0); + g_return_val_if_fail (version <= tree->version, 0); - return g_tree_node_height (tree->r[0].root); + return g_tree_node_height (g_tree_root_find_version (tree, version)->root, + version); } /** diff --git a/glib/gtree.h b/glib/gtree.h index 5b1a0f30..a801caf3 100644 --- a/glib/gtree.h +++ b/glib/gtree.h @@ -49,7 +49,7 @@ typedef gboolean (*GTraverseFunc) (gpointer key, gpointer value, gpointer data); -/* Balanced binary trees +/* Persistent balanced binary trees */ GTree* g_tree_new (GCompareFunc key_compare_func); GTree* g_tree_new_with_data (GCompareDataFunc key_compare_func, @@ -83,11 +83,26 @@ gboolean g_tree_lookup_extended (GTree *tree, gpointer *value); gpointer g_tree_lookup_related (GTree *tree, gconstpointer key, - GTreeSearchType search_type, - guint version); + GTreeSearchType search_type); +gpointer g_tree_lookup_v (GTree *tree, + guint version, + gconstpointer key); +gboolean g_tree_lookup_extended_v (GTree *tree, + guint version, + gconstpointer lookup_key, + gpointer *orig_key, + gpointer *value); +gpointer g_tree_lookup_related_v (GTree *tree, + guint version, + gconstpointer key, + GTreeSearchType search_type); void g_tree_foreach (GTree *tree, GTraverseFunc func, gpointer user_data); +void g_tree_foreach_v (GTree *tree, + guint version, + GTraverseFunc func, + gpointer user_data); #ifndef G_DISABLE_DEPRECATED void g_tree_traverse (GTree *tree, @@ -103,7 +118,18 @@ gpointer g_tree_search_related (GTree *tree, GCompareFunc search_func, gconstpointer user_data, GTreeSearchType search_type); +gpointer g_tree_search_v (GTree *tree, + guint version, + GCompareFunc search_func, + gconstpointer user_data); +gpointer g_tree_search_related_v(GTree *tree, + guint version, + GCompareFunc search_func, + gconstpointer user_data, + GTreeSearchType search_type); gint g_tree_height (GTree *tree); +gint g_tree_height_v (GTree *tree, + guint version); gint g_tree_nnodes (GTree *tree); G_END_DECLS diff --git a/tests/tree-test.c b/tests/tree-test.c index a2f08a07..1bda05e6 100644 --- a/tests/tree-test.c +++ b/tests/tree-test.c @@ -162,16 +162,16 @@ main (int argc, gchar *r; r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_SUCCESSOR, 0); + 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, 0); + G_TREE_SEARCH_PREDECESSOR); g_assert(r && *r == chars[i]); r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_SUCCESSOR, 0); + G_TREE_SEARCH_SUCCESSOR); g_assert(r && *r == chars[i]); } g_assert(n == g_tree_nnodes(tree)); @@ -265,33 +265,37 @@ main (int argc, gchar *r; gint j; - r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_PREDECESSOR, i); + r = g_tree_lookup_related_v (tree, i, &chars[i], + G_TREE_SEARCH_PREDECESSOR); g_assert((i == 0 && r == NULL) || (r && *r == chars[i-1])); if (i > 0) { - r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_PREDECESSOR, i-1); + r = g_tree_lookup_related_v (tree, i-1, &chars[i], + G_TREE_SEARCH_PREDECESSOR); g_assert((i == 1 && r == NULL) || (r && *r == chars[i-2])); } g_tree_next_version (tree); g_tree_insert (tree, &chars[i], &chars[i]); - r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_PREDECESSOR, i+1); + r = g_tree_lookup_related_v (tree, i+1, &chars[i], + G_TREE_SEARCH_PREDECESSOR); g_assert(r && *r == chars[i]); - r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_SUCCESSOR, i+1); + r = g_tree_lookup_related_v (tree, i+1, &chars[i], + G_TREE_SEARCH_SUCCESSOR); g_assert(r && *r == chars[i]); for (j = 0; j <= i+1; ++j) { - r = g_tree_lookup_related (tree, &chars[i], - G_TREE_SEARCH_PREDECESSOR, j); + r = g_tree_lookup_related_v (tree, j, &chars[i], + G_TREE_SEARCH_PREDECESSOR); g_assert((j == 0 && r == NULL) || (r && *r == chars[j-1])); } + + traverse_num = 0; + g_tree_foreach_v (tree, i+1, my_traverse, NULL); + g_assert(traverse_num == i+1); } g_assert(i == g_tree_nnodes(tree)); @@ -336,8 +340,8 @@ main (int argc, for (j = 0; chars[j]; ++j) { - r = g_tree_lookup_related (tree, &chars[j], - G_TREE_SEARCH_PREDECESSOR, i); + r = g_tree_lookup_related_v (tree, i, &chars[j], + G_TREE_SEARCH_PREDECESSOR); if (i == 0) /* the tree was empty */ g_assert (r == NULL); @@ -388,8 +392,8 @@ main (int argc, for (j = 0; chars[j]; j++) { - r = g_tree_lookup_related (tree, &chars[j], - G_TREE_SEARCH_PREDECESSOR, i); + r = g_tree_lookup_related_v (tree, i, &chars[j], + G_TREE_SEARCH_PREDECESSOR); g_assert (r && *r == chars[MIN(j,i)]); } } @@ -407,8 +411,8 @@ main (int argc, for (j = 0; chars[j]; j++) { - r = g_tree_lookup_related (tree, &chars[j], - G_TREE_SEARCH_PREDECESSOR, k); + r = g_tree_lookup_related_v (tree, k, &chars[j], + G_TREE_SEARCH_PREDECESSOR); g_assert ((k <= i/2*2 && r == NULL) || (k > i/2*2 && r && *r == chars[MIN(j,k)])); } @@ -424,8 +428,8 @@ main (int argc, for (j = 0; chars[j]; j++) { - r = g_tree_lookup_related (tree, &chars[j], - G_TREE_SEARCH_PREDECESSOR, i); + r = g_tree_lookup_related_v (tree, i, &chars[j], + G_TREE_SEARCH_PREDECESSOR); g_assert (r == NULL); } } -- 2.34.1