From c895b359f97718dac32229a249818830124ccdbb Mon Sep 17 00:00:00 2001
From: Dana Jansens <danakj@orodu.net>
Date: Fri, 30 Oct 2009 10:51:47 -0400
Subject: [PATCH] Add functions g_tree_root_find_version() and
 g_tree_node_find_version(), which take a version number, and find the
 versioned-pointers which match for that version (the largest ones <= the
 version).

---
 glib/gtree.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 60 insertions(+), 5 deletions(-)

diff --git a/glib/gtree.c b/glib/gtree.c
index 5285fb6f..6a8e1ef3 100644
--- a/glib/gtree.c
+++ b/glib/gtree.c
@@ -38,12 +38,12 @@
 #define MAX_OUT_DEGREE 3
 #define MAX_IN_DEGREE 5
 
-typedef struct _GTreeRoot          GTreeRoot;
+typedef struct _GTreeRootVersion   GTreeRootVersion;
 typedef struct _GTreeNodeVersion   GTreeNodeVersion;
 typedef struct _GTreeNodeData      GTreeNodeData;
 typedef struct _GTreeNode          GTreeNode;
 
-struct _GTreeRoot
+struct _GTreeRootVersion
 {
   GTreeNode *root;
   guint      version;
@@ -51,7 +51,7 @@ struct _GTreeRoot
 
 struct _GTree
 {
-  GTreeRoot        *roots; /* versioned root nodes of the tree.  roots[0] is
+  GTreeRootVersion *roots; /* versioned root nodes of the tree.  roots[0] is
                               the highest (latest) version.  then
                               roots[1]..roots[nroots-1] are
                               older versions in ascending order */
@@ -237,7 +237,7 @@ g_tree_new_full (GCompareDataFunc key_compare_func,
   g_return_val_if_fail (key_compare_func != NULL, NULL);
   
   tree = g_slice_new (GTree);
-  tree->roots              = g_new(GTreeRoot, 1);
+  tree->roots              = g_new(GTreeRootVersion, 1);
   tree->nroots             = 1;
   tree->key_compare        = key_compare_func;
   tree->key_destroy_func   = key_destroy_func;
@@ -432,7 +432,7 @@ g_tree_root_next_version (GTree *tree)
     {
       /* add a new version of the root */
       tree->nroots++;
-      tree->roots = g_renew(GTreeRoot, tree->roots, tree->nroots);
+      tree->roots = g_renew(GTreeRootVersion, tree->roots, tree->nroots);
       /* copy the latest version from roots[0] */
       tree->roots[tree->nroots-1] = tree->roots[0];
       tree->roots[0].version = tree->version;
@@ -525,6 +525,61 @@ g_tree_node_next_version (GTree     *tree,
     }
 }
 
+/* finds the largest version in the array, that is <= the query version */
+static inline GTreeRootVersion *
+g_tree_root_find_version (GTree *tree,
+                          guint  version)
+{
+  GTreeRootVersion *const v = tree->roots;
+  const guint nv = tree->nroots;
+  GTreeRootVersion *l, *r;
+
+  /* note: we never search for a version smaller than the smallest
+     version in the array */
+
+  if (v[0].version <= version)
+    return v;
+
+  l = v+1;
+  r = v+(nv-1);
+  while (l <= r) /* binary search */
+    {
+      GTreeRootVersion *const m = l + (r - l) / 2;
+      if (version == m->version)
+        return m;
+      else if (version < m->version)
+        r = m-1;
+      else
+        l = m+1;
+    }
+  g_assert (r->version < version);
+  g_assert (l->version > version);
+  return r;
+}
+
+static inline GTreeNodeVersion *
+g_tree_node_find_version(GTreeNode *node,
+                         guint      version)
+{
+  GTreeNodeVersion *const v = node->v;
+  const guint nv = node->nv;
+  GTreeNodeVersion *n;
+
+  /* note: we never search for a version smaller than the smallest
+     version in the array */
+
+  if (v[0].version <= version)
+    return v;
+
+  /* there are at most MAX_IN_DEGREE+1 things to look through, which is small,
+     so just scan through them from largest version to smallest */
+  for (n = v+(nv-1); n != v; --n)
+    if (n->version <= version)
+      break;
+  g_assert (n != v);
+  return n;
+}
+
 /**
  * g_tree_insert:
  * @tree: a #GTree.
-- 
2.34.1