From 24e0817b6afaac9e014f1c4c2f9ee3728f012f02 Mon Sep 17 00:00:00 2001 From: Dana Jansens Date: Thu, 12 Nov 2009 18:38:10 -0500 Subject: [PATCH] Allow you to delete all versions <= x from a GTree. --- glib/gtree.c | 218 ++++++++++++++++++++++++++++++++++++++++++++-- glib/gtree.h | 2 + tests/tree-test.c | 71 ++++++++++++++- 3 files changed, 284 insertions(+), 7 deletions(-) diff --git a/glib/gtree.c b/glib/gtree.c index 34946f80..7f5e81ce 100644 --- a/glib/gtree.c +++ b/glib/gtree.c @@ -298,9 +298,10 @@ g_tree_root_find_version (GTree *tree, GTreeRootVersion *const v = tree->r; const guint nv = tree->nr; GTreeRootVersion *l, *r; - - /* note: we never search for a version smaller than the smallest - version in the array */ + static GTreeRootVersion none = { + .root = NULL, + .version = 0 + }; if (v[0].version <= version) return v; @@ -317,11 +318,16 @@ g_tree_root_find_version (GTree *tree, else l = m+1; } - g_assert (r->version < version); + /* If searching earlier than the first root in the tree, r will be off + the start of the list (in the first position in the array) */ + g_assert (r == v || r->version < version); /* When searching for the second last root (the last position in the array), l will be off the end of the list */ g_assert (l == v+nv || l->version > version); - return r; + if (r == v) + return &none; + else + return r; } static inline GTreeNodeVersion * @@ -343,6 +349,7 @@ g_tree_node_find_version(GTreeNode *node, for (n = v+(nv-1); n != v; --n) if (n->version <= version) break; + /* searched for something smaller than the lowest version in the node */ g_assert (n != v); return n; } @@ -583,9 +590,203 @@ g_tree_current_version (GTree *tree) guint g_tree_next_version (GTree *tree) { + g_assert (tree->version+1 != 0); return ++tree->version; } +/* Given the length of the array of versions, return the index of the + first (oldest) version, or @n if there is none. */ +#define first_v(n) ((n) > 1 ? 1 : 0) + +/* Given a current index, and the length of the array of versions, return + the index of the next (newer) version, or @n if there is none. */ +#define next_v(i, n) \ + ((i) == 0 ? (n) : /* it was the last version, return something invalid */ \ + ((i) == (n)-1 ? 0 : /* it was the second last, return the last */ \ + (i)+1)) /* it was somewhere else in the array, return the next */ + +/* Given a current index, and the length of the array of versions, return + the index of the previous (older) version, or @n if there is none. */ +#define prev_v(i, n) \ + ((i) == 0 ? (n)-1 : /* it was the last version, return the second last */ \ + ((i) == 1 ? (n) : /* it was the first, return something invalid */ \ + (i)-1)); /* it was somewhere else in the array, return the previous */ + +static guint +g_tree_node_delete_versions (GTree *tree, + GTreeNode *node, + guint pnext, + guint version) +{ + guint rm, i, nv, next, nextv, lnext, rnext, ret; + + if (!node) + return 0; + + nv = node->nv; + + ret = 0; + rm = 0; + for (i = first_v (nv); i < nv && node->v[i].version <= version; i = next) + { + next = next_v (i, nv); + + if (next < nv) + nextv = node->v[next].version - 1; + else + nextv = version; + + if (next < nv && node->v[i].left && + node->v[next].left == node->v[i].left && + (!pnext || node->v[next].version <= pnext)) + lnext = node->v[next].version; + else if (next == nv || node->v[next].version > pnext) + lnext = pnext; + else + lnext = 0; + lnext = g_tree_node_delete_versions (tree, node->v[i].left, lnext, + nextv); + + if (next < nv && node->v[i].right && + node->v[next].right == node->v[i].right && + (!pnext || node->v[next].version <= pnext)) + rnext = node->v[next].version; + else if (next == nv || node->v[next].version > pnext) + rnext = pnext; + else + rnext = 0; + rnext = g_tree_node_delete_versions (tree, node->v[i].right, rnext, + nextv); + + /* smallest non-zero of pnext, rnext, and lnext (or zero if all 3 are) */ + nextv = MIN ((pnext ? pnext : (lnext ? lnext : rnext)), + MIN ((lnext ? lnext : (rnext ? rnext : pnext)), + (rnext ? rnext : (lnext ? lnext : pnext)))); + + if (nextv && (next == nv || node->v[next].version > nextv)) + { /* leave this one behind as there are more pointers coming here */ + ret = node->v[i].version = nextv; + break; + } + + ++rm; + } + + /* remove the first 'rm' versioned pointers from the node, they are <= + 'version' */ + for (i = 1; rm && i+rm < nv; ++i) + node->v[i] = node->v[i+rm]; + node->nv -= rm; + + /* if we removed the last version inside the node, then we can free it */ + if (node->nv == 0) + { + g_tree_node_free (tree, node); + node = NULL; + } + + /* if we saved a version here, then it's because a child still needs it + or the parent still needs it. if the child needs it, then we will + still have a pointer back to the parent, so it needs to also know. so + either way the parent needs it. + if we did not save a version, but the parent needs us to stick around for + something, then we can let it know that we did + */ + if (!ret && node && pnext) + { + g_assert (node->v[first_v (node->nv)].version == pnext); + ret = pnext; + } + + return ret; +} + +/** + * g_tree_delete_versions: + * @tree: a #GTree. + * @version: the highest version to delete. + * + * Deletes all versions in the #GTree which are at most @version. You can not + * delete the latest version of the #GTree, so @version must be less than the + * value returned by g_tree_current_version(). + + * Deleting a version from the #GTree frees all resources used that are not + * needed for later versions in the #GTree. All elements which have been + * removed from the tree in a version no later than @version will be freed, + * and if you supplied a @key_destroy_func or @value_destroy_func when + * creating the #GTree, any such nodes will have their keys and values + * freed using these functions (unless it was removed from the #GTree by + * g_tree_steal(), in which case the key and value is not freed). + **/ +void +g_tree_delete_versions (GTree *tree, + guint version) +{ + guint rm, i, l, keep, next; + + g_return_if_fail (tree != NULL); + g_return_if_fail (version < tree->version); + + if (version < tree->r[first_v (tree->nr)].version) + return; + + rm = 0; + keep = i = first_v (tree->nr); + next = next_v (i, tree->nr); + while (i < tree->nr && tree->r[i].version < version + 1) + { + guint nextv, v; + + if (next == tree->nr || tree->r[next].version > version + 1) + nextv = version + 1; + else if (next < tree->nr && tree->r[next].root == tree->r[i].root) + nextv = tree->r[next].version; + else + nextv = 0; + + if (next < tree->nr && tree->r[next].version <= version) + v = tree->r[next].version - 1; + else + v = version; + + l = g_tree_node_delete_versions (tree, tree->r[i].root, nextv, v); + g_assert (l == 0 || l > v); + + if (l > v) + tree->r[i].version = l; + else + { + ++rm; + keep = next; + } + + i = next; + next = next_v (i, tree->nr); + } + + if (rm) + { + guint j; + for (j = first_v (tree->nr - rm); + j < tree->nr - rm; + j = next_v (j, tree->nr - rm), keep = next_v (keep, tree->nr)) + { + tree->r[j] = tree->r[keep]; + } + } + + tree->nr -= rm; + tree->r = g_renew(GTreeRootVersion, tree->r, tree->nr); + +#ifdef G_TREE_DEBUG + { + guint i; + for (i = 0; i <= tree->version; ++i) + g_tree_node_check (g_tree_root_find_version (tree, i)->root, i); + } +#endif +} + /* Make a new root pointer if the current one is not for the current version of the tree */ static void @@ -985,7 +1186,12 @@ g_tree_remove (GTree *tree, * Removes a key and its associated value from a #GTree without calling * the key and value destroy functions. Note that if the key existed in * earlier versions of the tree (g_tree_next_version() has been called since - * it was inserted), then it cannot be removed from the tree. * + * it was inserted), then it cannot be removed from the tree until all + * versions containing the node are removed from the tree, by calling + * g_tree_delete_versions(). However, if the node is removed from the current + * version of the tree with g_tree_steal() then the key and value destroy + * functions will not be called once the last version of the key/value pair + * is removed. * If the key does not exist in the #GTree, the function does nothing. * * Returns: %TRUE if the key was found and able to be removed diff --git a/glib/gtree.h b/glib/gtree.h index 9665d70b..5b1a0f30 100644 --- a/glib/gtree.h +++ b/glib/gtree.h @@ -63,6 +63,8 @@ void g_tree_unref (GTree *tree); void g_tree_destroy (GTree *tree); guint g_tree_current_version (GTree *tree); guint g_tree_next_version (GTree *tree); +void g_tree_delete_versions (GTree *tree, + guint version); void g_tree_insert (GTree *tree, gpointer key, gpointer value); diff --git a/tests/tree-test.c b/tests/tree-test.c index 6e32ea05..a2f08a07 100644 --- a/tests/tree-test.c +++ b/tests/tree-test.c @@ -257,6 +257,8 @@ main (int argc, g_assert (p == NULL); g_tree_unref (tree); + + /* test adding and removing items in a versioned tree */ tree = g_tree_new (my_compare); for (i = 0; chars[i]; i++) { @@ -361,7 +363,74 @@ main (int argc, } } - g_tree_destroy (tree); + g_tree_unref (tree); + + /* test removing versions from a tree */ + tree = g_tree_new (my_compare); + + for (i = 0; i < chars[i]; i++) { + g_tree_insert (tree, &chars[i], &chars[i]); + g_tree_next_version (tree); + } + g_assert(i == g_tree_nnodes(tree)); + + /* remove everything from the last version */ + for (i = 0; chars[i]; i++) + g_tree_remove (tree, &chars[i]); + g_assert(g_tree_nnodes(tree) == 0); + + g_assert (g_tree_current_version (tree) == i); + + for (i = 0; i < g_tree_current_version (tree); ++i) + { + char *r; + int j; + + for (j = 0; chars[j]; j++) + { + r = g_tree_lookup_related (tree, &chars[j], + G_TREE_SEARCH_PREDECESSOR, i); + g_assert (r && *r == chars[MIN(j,i)]); + } + } + + for (i = 0; i < g_tree_current_version (tree); ++i) + { + guint k; + if (i%2==0) + g_tree_delete_versions (tree, i); + + for (k = 0; k < g_tree_current_version (tree); ++k) + { + char *r; + int j; + + for (j = 0; chars[j]; j++) + { + r = g_tree_lookup_related (tree, &chars[j], + G_TREE_SEARCH_PREDECESSOR, k); + g_assert ((k <= i/2*2 && r == NULL) || + (k > i/2*2 && r && *r == chars[MIN(j,k)])); + } + } + } + + g_tree_delete_versions (tree, g_tree_current_version (tree)-1); + + for (i = 0; i < g_tree_current_version (tree); ++i) + { + char *r; + int j; + + for (j = 0; chars[j]; j++) + { + r = g_tree_lookup_related (tree, &chars[j], + G_TREE_SEARCH_PREDECESSOR, i); + g_assert (r == NULL); + } + } + + g_tree_unref (tree); /* test destroying a versioned tree */ tree = g_tree_new (my_compare); -- 2.34.1