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;
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 *
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;
}
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
* 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
projects / dana / cg-glib.git / blobdiff