Created attachment 133325 [details] [review]
Patch

Created attachment 149802 [details] [review]
Updated the patch.

It looks generally good. Have you checked that it's consistent with Glib::Node where/if necessary?

I would rename nnodes() to something more obvious/consistent.

GNode and GTree seem badly named. Both are trees, but one is like a map, right?

(In reply to comment #3)
> It looks generally good. Have you checked that it's consistent with Glib::Node
> where/if necessary?

Thanks. I've checked it now. The only change is the ref/unref functions in the version 2.22. Do you think it necessary in glibmm?

> 
> I would rename nnodes() to something more obvious/consistent.

This is the original name in Glib, that's why I named it nnodes.
http://library.gnome.org/devel/glib/stable/glib-Balanced-Binary-Trees.html#g-tree-nnodes

> 
> GNode and GTree seem badly named. Both are trees, but one is like a map, right?

First is an N-ary tree, the second is a binary tree, but the name Tree is "taken" in glibmm for Glib::NodeTree. I think B-tree is widely used name that's why I choose this.

(In reply to comment #4)
> (In reply to comment #3)
> > It looks generally good. Have you checked that it's consistent with Glib::Node
> > where/if necessary?
> 
> Thanks. I've checked it now. The only change is the ref/unref functions in the
> version 2.22. Do you think it necessary in glibmm?

What do you mean?

> > I would rename nnodes() to something more obvious/consistent.
> 
> This is the original name in Glib, that's why I named it nnodes.
> http://library.gnome.org/devel/glib/stable/glib-Balanced-Binary-Trees.html#g-tree-nnodes

We often rename bad API.

(In reply to comment #5)
> (In reply to comment #4)
> > (In reply to comment #3)
> > > It looks generally good. Have you checked that it's consistent with Glib::Node
> > > where/if necessary?
> > 
> > Thanks. I've checked it now. The only change is the ref/unref functions in the
> > version 2.22. Do you think it necessary in glibmm?
> 
> What do you mean?

I've implemented the ref/unref functions (with names reference and unreference which are required by Glib::RefPtr) and other necessary changes. 

> 
> > > I would rename nnodes() to something more obvious/consistent.
> > 
> > This is the original name in Glib, that's why I named it nnodes.
> > http://library.gnome.org/devel/glib/stable/glib-Balanced-Binary-Trees.html#g-tree-nnodes
> 
> We often rename bad API.

It's ok for me.

Created attachment 150591 [details] [review]
Reference counting for BalancedTree.

Review of attachment 149802 [details] [review]:

Looks mostly fine.  A few comments follow.

::: glib/src/btree.hg
@@ +26,3 @@
+namespace Glib
+{
+/** N-ary Trees — trees of data with any number of branches

Is this a copy-paste error?  I thought this was a binary tree, not a N-ary tree.

@@ +27,3 @@
+{
+/** N-ary Trees — trees of data with any number of branches
+ * The BalancedTree class and its associated functions provide a balancedctree data structure, in which trees in the tree can contain arbitrary data.

balancedctree?  I assume that's just a typo?

@@ +78,3 @@
+ * supplied a value_destroy_func when creating the #GTree, the old value is 
+ * freed using that function. If you supplied a @key_destroy_func when 
+ * creating the #GTree, the passed key is freed using that function.

This documentation about the key_destroy_func and value_destroy_func does not seem to be valid at all for this implementation since we use them internally and don't allow the user to specify them anywhere (as far as I can see).  Also, in general, if we're copying the C documentation into the C++ source, we should at least use the C++ names instead of the old C names (e.g. change #GTree to BalancedTree, etc).

@@ +87,3 @@
+    g_tree_insert(gobj(), reinterpret_cast<void *>(new K(key)), reinterpret_cast<void *>(new V(value)));
+  }
+  _IGNORE(g_tree_insert)

This obviously requires both K and V to be copyable, perhaps that should be stated in the class documentation more obviously?

@@ +99,3 @@
+ * creating the #GTree, the old value is freed using that function. If you 
+ * supplied a @key_destroy_func when creating the #GTree, the old key is 
+ * freed using that function. 

same documentation issues as mentioned above

@@ +108,3 @@
+    g_tree_replace(gobj(), new K(key), new V(value));
+  }
+  _IGNORE(g_tree_replace)

This function doesn't seem to be different at all from insert() from a user's point of view.  The only things that are getting 'replaced' or 'freed' are the internal copies that we created of the key and value they passed to use.  None of the user's arguments are getting modified or freed in any way.

@@ +117,3 @@
+ *
+ * If the #GTree was created using g_tree_new_full(), the key and value 
+ * are freed using the supplied destroy functions, otherwise you have to 

Again, this documentation doesn't apply to the C++ API.

@@ +146,3 @@
+    return g_tree_steal(gobj(), &key);
+  }
+  _IGNORE(g_tree_steal)

This function could just as well be renamed "leak_memory()".  We *always* want the copies to be freed when they're removed from the tree, since we create the copies internally.  The user of the API should have no reason to call such an API, so it should just be omitted.

@@ +220,3 @@
+    g_tree_foreach(gobj(), c_callback_traverse, reinterpret_cast<gpointer>(&func_copy));
+  }
+  _IGNORE(g_tree_foreach);

Would it be possible to make this function const to enforce the documented restrictions about not modifying the tree while traversing it?

@@ +272,3 @@
+  }
+
+private:

It doesn't look like any of the following helper functions really need to be static class functions.  You could just as well move them down to the .cc file and make them plain C functions.  That might even be more portable.

Review of attachment 150591 [details] [review]:

This patch looks fine other than another documentation issue.

::: glib/src/btree.hg
@@ +98,3 @@
+ * Decrements the reference count of tree by one.  If the reference count
+ * drops to 0, all keys and values will be destroyed (if destroy
+ * functions were specified) and all memory allocated by @tree will be

again, the user can't specify destroy functions in the C++ implementation, so this documentation is a bit misleading.

Created attachment 150871 [details] [review]
fixes of bugs mentioned in comment 8 and comment 9

I fixed the bugs mentioned in comment 8 and comment 9 except the last one in comment 8:

> @@ +272,3 @@
> +  }
> +
> +private:
> 
> It doesn't look like any of the following helper functions really need to be
> static class functions.  You could just as well move them down to the .cc file
> and make them plain C functions.  That might even be more portable.

These functions are using the K and V template parameters, so they must be member functions of the class.

Review of attachment 150871 [details] [review]:

looks good

ok, I've committed this to git, but I've renamed the files themselves balancedtree.h rather than btree.h to follow the existing glibmm header conventions better.