[gtk] rbtree: Add gtk_rb_tree_node_get_tree()

[Benjamin Otte <otte src gnome org>]

commit 6a3c2a230a4d1ef9f8c356cc5f24fbb202172e0c
Author: Benjamin Otte <otte redhat com>
Date:   Mon Jan 14 01:55:23 2019 +0100

    rbtree: Add gtk_rb_tree_node_get_tree()
    
    Store a link to the tree in the root node. This allows looking up the
    tree in O(log N) from the node without any extra memory usage.
    
    This is useful because code can just store a pointer to the node and
    doesn't need to keep the tree pointer around. And that can (for large
    trees) save quite a bit of memory.

 gtk/gtkrbtree.c        | 46 +++++++++++++++++++++++++++++++++++++++++-----
 gtk/gtkrbtreeprivate.h |  1 +
 2 files changed, 42 insertions(+), 5 deletions(-)
---
diff --git a/gtk/gtkrbtree.c b/gtk/gtkrbtree.c
index 807c7d1f8f..14b017f181 100644
--- a/gtk/gtkrbtree.c
+++ b/gtk/gtkrbtree.c
@@ -43,17 +43,41 @@ struct _GtkRbNode
 
   GtkRbNode *left;
   GtkRbNode *right;
-  GtkRbNode *parent;
+  /* The difference between tree and parent here is that we OR the tree with 1 and because
+   * pointers are always multiples of 4, we can know if we've stored a parent or the tree here */
+  union {
+    gpointer parent_or_tree;
+    GtkRbNode *parent;
+    GtkRbTree *tree;
+  };
 };
 
 #define NODE_FROM_POINTER(ptr) ((GtkRbNode *) ((ptr) ? (((guchar *) (ptr)) - sizeof (GtkRbNode)) : NULL))
 #define NODE_TO_POINTER(node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkRbNode)) : NULL))
 #define NODE_TO_AUG_POINTER(tree, node) ((gpointer) ((node) ? (((guchar *) (node)) + sizeof (GtkRbNode) + 
(tree)->element_size) : NULL))
 
+static inline gboolean
+is_root (GtkRbNode *node)
+{
+  return GPOINTER_TO_SIZE (node->parent_or_tree) & 1 ? TRUE : FALSE;
+}
+
 static inline GtkRbNode *
 parent (GtkRbNode *node)
 {
-  return node->parent;
+  if (is_root (node))
+    return NULL;
+  else
+    return node->parent;
+}
+
+static GtkRbTree *
+tree (GtkRbNode *node)
+{
+  while (!is_root (node))
+    node = parent (node);
+
+  return GSIZE_TO_POINTER (GPOINTER_TO_SIZE (node->tree) & ~1);
 }
 
 static void
@@ -61,10 +85,16 @@ set_parent (GtkRbTree *tree,
             GtkRbNode *node,
             GtkRbNode *new_parent)
 {
-  node->parent = new_parent;
 
-  if (new_parent == NULL)
-    tree->root = node;
+  if (new_parent != NULL)
+    {
+      node->parent = new_parent;
+    }
+  else
+    {
+      node->tree = GSIZE_TO_POINTER (GPOINTER_TO_SIZE (tree) | 1);
+      tree->root = node;
+    }
 }
 
 static inline gsize
@@ -557,6 +587,12 @@ gtk_rb_tree_get_augment (GtkRbTree *tree,
   return NODE_TO_AUG_POINTER (tree, rbnode);
 }
 
+GtkRbTree *
+gtk_rb_tree_node_get_tree (gpointer node)
+{
+  return tree (NODE_FROM_POINTER (node));
+}
+
 void
 gtk_rb_tree_mark_dirty (GtkRbTree *tree,
                         gpointer   node)
diff --git a/gtk/gtkrbtreeprivate.h b/gtk/gtkrbtreeprivate.h
index 46b6b0db86..8e74c5e19e 100644
--- a/gtk/gtkrbtreeprivate.h
+++ b/gtk/gtkrbtreeprivate.h
@@ -61,6 +61,7 @@ gpointer             gtk_rb_tree_get_right              (GtkRbTree
                                                          gpointer                 node);
 gpointer             gtk_rb_tree_get_augment            (GtkRbTree               *tree,
                                                          gpointer                 node);
+GtkRbTree *          gtk_rb_tree_node_get_tree          (gpointer                 node);
 
 void                 gtk_rb_tree_mark_dirty             (GtkRbTree               *tree,
                                                          gpointer                 node);