Re: Outstanding GTK+ patches

[Soeren Sandmann <sandmann daimi au dk>]

Owen Taylor <otaylor@redhat.com> writes:

>  Splay tree implementation. Require someone deciding the "what binary
>  trees do we want" questions. Do we want a generic binary
>  tree base-class with implementations?

The actual patch is not there, but essentially the same code can be
found at http://www.daimi.au.dk/~sandmann/splaytrees-1.1.1.tar.gz.

I don't think we want a generic tree class. It would complicate the
code, and in almost any reasonable situation, AVL trees are more than
fast enough.

Also, I don't think the splay trees should go in - they have their
uses in special situations, but they are rare. Keeping GLib small is a
real benefit. 

Alternatively, the AVL trees could be replaced by splay trees. This
might (or might not - the constant in splay trees is larger than the
constant in AVL trees) speed up the memchunk implementation ('young'
pieces of memory die faster than old), but in most other cases it
would just slow things down.

I think that the trees should be left essentially the way they are,
perhaps changing the implementation of g_tree_lookup so that it is
non-recursive, like this patch below does. (It makes g_tree_lookup
work the same way as g_tree_search does). A few other functions
(_insert and _remove) could possibly be made non-recursive in a
similar way.

Index: gtree.c
===================================================================
RCS file: /cvs/gnome/glib/gtree.c,v
retrieving revision 1.10
diff -u -r1.10 gtree.c
--- gtree.c     1999/02/24 06:13:56     1.10
+++ gtree.c     2000/02/23 13:16:09
@@ -499,20 +499,16 @@
   if (!node)
     return NULL;
 
-  cmp = (* compare) (key, node->key);
-  if (cmp == 0)
-    return node->value;
-
-  if (cmp < 0)
-    {
-      if (node->left)
-       return g_tree_node_lookup (node->left, compare, key);
-    }
-  else if (cmp > 0)
-    {
-      if (node->right)
-       return g_tree_node_lookup (node->right, compare, key);
-    }
+  do {
+    cmp = (* compare) (key, node->key);
+    if (cmp == 0)
+      return node->value;
+    
+    if (cmp < 0)
+      node = node->left;
+    else if (cmp > 0)
+      node = node->right;
+  } while (node && (cmp != 0));
 
   return NULL;
 }

> glib-sandmann-990808-0
> 
>  Implements g_tree_lookup_range. Basically returns a GSlist of 
>  all nodes in a tree in a certain range. Might be useful.

g_tree_lookup_range can, contrary to what I said in the README file,
be done without this function using the g_tree_traverse function. But
a g_tree_traverse_range might be a useful method. g_tree_traverse
could then be implemented as a wrapper around it. The
g_tree_lookup_range is a kludge. Don't apply it, IMHO.