2003-08-30 Havoc Pennington <hp@pobox.com>

	* test/data/valid-config-files/system.d/test.conf: change to
	root for the user so warnings don't get printed

	* dbus/dbus-message.c: add dbus_message_get_path,
	dbus_message_set_path

	* dbus/dbus-object-tree.c (do_test_dispatch): add test of
	dispatching to a path

	* dbus/dbus-string.c (_dbus_string_validate_path): add

	* dbus/dbus-marshal.c (_dbus_demarshal_object_path): implement
	(_dbus_marshal_object_path): implement

	* dbus/dbus-protocol.h (DBUS_HEADER_FIELD_PATH): new header field
	to contain the path to the target object
	(DBUS_HEADER_FIELD_SENDER_SERVICE): rename
	DBUS_HEADER_FIELD_SENDER to explicitly say it's the sender service

1 files changed, 623 insertions, 521 deletions

diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c
index 379e2f04..24e402a2 100644
--- a/dbus/dbus-object-tree.c
+++ b/dbus/dbus-object-tree.c
@@ -36,12 +36,18 @@
  * Types and functions related to DBusObjectTree. These
  * are all internal.
  *
+ * @todo this is totally broken, because of the following case:
+ *    /foo, /foo/bar, /foo/baz
+ *  if we then receive a message to /foo/baz we need to hand it
+ * to /foo/baz and /foo but not /foo/bar. So we should be
+ * using a real tree structure as with GConfListeners.
+ *
  * @{
  */
 
 typedef struct DBusObjectSubtree DBusObjectSubtree;
 
-static DBusObjectSubtree* _dbus_object_subtree_new   (const char                 **path,
+static DBusObjectSubtree* _dbus_object_subtree_new   (const char                  *name,
                                                       const DBusObjectPathVTable  *vtable,
                                                       void                        *user_data);
 static void               _dbus_object_subtree_ref   (DBusObjectSubtree           *subtree);
@@ -52,41 +58,42 @@ struct DBusObjectTree
   int                 refcount;
   DBusConnection     *connection;
 
-  /* Each subtree is a separate malloc block since that
-   * lets us refcount them and maybe helps with
-   * reentrancy issues when calling back to application code
-   */
-  DBusObjectSubtree **subtrees;
-  int                 n_subtrees;
-  unsigned int        subtrees_sorted : 1;
+  DBusObjectSubtree  *root;
 };
 
 struct DBusObjectSubtree
 {
   DBusAtomic                         refcount;
+  DBusObjectSubtree                 *parent;
   DBusObjectPathUnregisterFunction   unregister_function;
   DBusObjectPathMessageFunction      message_function;
   void                              *user_data;
-  char                              *path[1]; /**< Allocated as large as necessary */
+  DBusObjectSubtree                **subtrees;
+  int                                n_subtrees;
+  unsigned int                       subtrees_sorted : 1;
+  char                               name[1]; /**< Allocated as large as necessary */
 };
 
 DBusObjectTree*
 _dbus_object_tree_new (DBusConnection *connection)
 {
   DBusObjectTree *tree;
-  
+
   /* the connection passed in here isn't fully constructed,
    * so don't do anything more than store a pointer to
    * it
    */
-  
+
   tree = dbus_new0 (DBusObjectTree, 1);
   if (tree == NULL)
     goto oom;
-  
+
   tree->refcount = 1;
   tree->connection = connection;
-  
+  tree->root = _dbus_object_subtree_new ("/", NULL, NULL);
+  if (tree->root == NULL)
+    goto oom;
+
   return tree;
 
  oom:
@@ -94,7 +101,7 @@ _dbus_object_tree_new (DBusConnection *connection)
     {
       dbus_free (tree);
     }
-  
+
   return NULL;
 }
 
@@ -117,55 +124,15 @@ _dbus_object_tree_unref (DBusObjectTree *tree)
     {
       _dbus_object_tree_free_all_unlocked (tree);
 
-      dbus_free (tree->subtrees);
       dbus_free (tree);
     }
 }
 
 static int
-path_cmp (const char **path_a,
-          const char **path_b)
-{
-  /* strcmp() considers a shorter string less than a longer string if
-   * the shorter string is the initial part of the longer. We
-   * consider a path with less elements less than a path with more
-   * elements.
-   */
-  int i;
-
-  i = 0;
-  while (path_a[i] != NULL)
-    {
-      int v;
-      
-      if (path_b[i] == NULL)
-        return 1; /* a is longer than b */
-
-      _dbus_assert (path_a[i] != NULL);
-      _dbus_assert (path_b[i] != NULL);
-      
-      v = strcmp (path_a[i], path_b[i]);
-
-      if (v != 0)
-        return v;
-
-      ++i;
-    }
-
-  _dbus_assert (path_a[i] == NULL);
-  if (path_b[i] == NULL)
-    return 0;
-  
-  /* b is longer than a */
-  return -1;
-}
-
-static int
 subtree_cmp (DBusObjectSubtree *subtree_a,
              DBusObjectSubtree *subtree_b)
 {
-  return path_cmp ((const char**) subtree_a->path,
-                   (const char**) subtree_b->path);
+  return strcmp (subtree_a->name, subtree_b->name);
 }
 
 static int
@@ -175,163 +142,198 @@ subtree_qsort_cmp (const void *a,
   DBusObjectSubtree **subtree_a_p = (void*) a;
   DBusObjectSubtree **subtree_b_p = (void*) b;
 
-  return subtree_cmp (*subtree_a_p, *subtree_b_p);  
-}
-
-/* Returns TRUE if container is a parent of child
- */
-static dbus_bool_t
-path_contains (const char **container,
-               const char **child)
-{
-  int i;
-
-  i = 0;
-  while (child[i] != NULL)
-    {
-      int v;
-      
-      if (container[i] == NULL)
-        return TRUE; /* container ran out, child continues;
-                      * thus the container is a parent of the
-                      * child.
-                      */
-
-      _dbus_assert (container[i] != NULL);
-      _dbus_assert (child[i] != NULL);
-      
-      v = strcmp (container[i], child[i]);
-
-      if (v != 0)
-        return FALSE; /* they overlap until here and then are different,
-                       * not overlapping
-                       */
-
-      ++i;
-    }
-
-  /* Child ran out; if container also did, they are equal;
-   * otherwise, the child is a parent of the container.
-   */
-  if (container[i] == NULL)
-    return TRUE; /* equal is counted as containing */
-  else
-    return FALSE;
+  return subtree_cmp (*subtree_a_p, *subtree_b_p);
 }
 
 static void
-ensure_sorted (DBusObjectTree *tree)
+ensure_sorted (DBusObjectSubtree *subtree)
 {
-  if (tree->subtrees && !tree->subtrees_sorted)
+  if (subtree->subtrees && !subtree->subtrees_sorted)
     {
-      qsort (tree->subtrees,
-             tree->n_subtrees,
+      qsort (subtree->subtrees,
+             subtree->n_subtrees,
              sizeof (DBusObjectSubtree*),
              subtree_qsort_cmp);
-      tree->subtrees_sorted = TRUE;
+      subtree->subtrees_sorted = TRUE;
     }
 }
 
-static dbus_bool_t
-find_subtree (DBusObjectTree *tree,
-              const char    **path,
-              int            *idx_p)
+#define VERBOSE_FIND 0
+
+static DBusObjectSubtree*
+find_subtree_recurse (DBusObjectSubtree  *subtree,
+                      const char        **path,
+                      dbus_bool_t         return_deepest_match,
+                      dbus_bool_t         create_if_not_found,
+                      int                *index_in_parent)
 {
   int i;
-  
-  if (tree->subtrees == NULL)
-    return FALSE;
 
-  ensure_sorted (tree);  
+  _dbus_assert (!(return_deepest_match && create_if_not_found));
+
+  if (path[0] == NULL)
+    {
+#if VERBOSE_FIND
+      _dbus_verbose ("  path exhausted, returning %s\n",
+                     subtree->name);
+#endif
+      return subtree;
+    }
 
-  /* FIXME this should be a binary search,
-   * as that's the whole point of the sorting
+#if VERBOSE_FIND
+  _dbus_verbose ("  searching children of %s for %s\n",
+                 subtree->name, path[0]);
+#endif
+  
+  ensure_sorted (subtree);
+
+  /* FIXME we should do a binary search here instead
+   * of O(n)
    */
+
   i = 0;
-  while (i < tree->n_subtrees)
+  while (i < subtree->n_subtrees)
     {
       int v;
 
-      v = path_cmp (path,
-                    (const char**) tree->subtrees[i]->path);
+      v = strcmp (path[0], subtree->subtrees[i]->name);
+
+#if VERBOSE_FIND
+      _dbus_verbose ("  %s cmp %s = %d\n",
+                     path[0], subtree->subtrees[i]->name,
+                     v);
+#endif
       
       if (v == 0)
         {
-          if (idx_p)
-            *idx_p = i;
-          
-          return TRUE;
+          if (index_in_parent)
+            {
+#if VERBOSE_FIND
+              _dbus_verbose ("  storing parent index %d\n", i);
+#endif
+              *index_in_parent = i;
+            }
+
+          if (return_deepest_match)
+            {
+              DBusObjectSubtree *next;
+
+              next = find_subtree_recurse (subtree->subtrees[i],
+                                           &path[1], return_deepest_match,
+                                           create_if_not_found, index_in_parent);
+              if (next == NULL)
+                {
+#if VERBOSE_FIND
+                  _dbus_verbose ("  no deeper match found, returning %s\n",
+                                 subtree->name);
+#endif
+                  return subtree;
+                }
+              else
+                return next;
+            }
+          else
+            return find_subtree_recurse (subtree->subtrees[i],
+                                         &path[1], return_deepest_match,
+                                         create_if_not_found, index_in_parent);
         }
       else if (v < 0)
         {
-          return FALSE;
+          goto not_found;
         }
-      
+
       ++i;
     }
-  
-  return FALSE;
-}
 
-static dbus_bool_t
-find_handler (DBusObjectTree *tree,
-              const char    **path,
-              int            *idx_p)
-{
-  int i;
-  int found_so_far;
-  
-  if (tree->subtrees == NULL)
-    return FALSE;
-  
-  ensure_sorted (tree);
+ not_found:
+#if VERBOSE_FIND
+  _dbus_verbose ("  no match found, current tree %s, create_if_not_found = %d\n",
+                 subtree->name, create_if_not_found);
+#endif
   
-  /* FIXME this should be a binary search,
-   * as that's the whole point of the sorting
-   */
-  found_so_far = -1;
-  i = 0;
-  while (i < tree->n_subtrees)
+  if (create_if_not_found)
     {
-      /* Longer paths are after shorter, so we scan
-       * for the latest containing path in the array.
-       * If we did a binary search we'd start with
-       * the first search match.
-       */
-      if (path_contains ((const char**) tree->subtrees[i]->path,
-                         path))
-        found_so_far = i;
-      else if (found_so_far >= 0)
-        break; /* no need to scan further */
+      DBusObjectSubtree* child;
+      DBusObjectSubtree **new_subtrees;
+      int new_n_subtrees;
+
+#if VERBOSE_FIND
+      _dbus_verbose ("  creating subtree %s\n",
+                     path[0]);
+#endif
       
-      ++i;
-    }
+      child = _dbus_object_subtree_new (path[0],
+                                        NULL, NULL);
+      if (child == NULL)
+        return NULL;
+
+      /* FIXME we should do the "double alloc each time" standard thing */
+      new_n_subtrees = subtree->n_subtrees + 1;
+      new_subtrees = dbus_realloc (subtree->subtrees,
+                                   new_n_subtrees * sizeof (DBusObjectSubtree*));
+      if (new_subtrees == NULL)
+        {
+          child->unregister_function = NULL;
+          child->message_function = NULL;
+          _dbus_object_subtree_unref (child);
+          return FALSE;
+        }
 
-  if (idx_p)
-    *idx_p = found_so_far;
+      new_subtrees[subtree->n_subtrees] = child;
+      if (index_in_parent)
+        *index_in_parent = subtree->n_subtrees;
+      subtree->subtrees_sorted = FALSE;
+      subtree->n_subtrees = new_n_subtrees;
+      subtree->subtrees = new_subtrees;
 
-  return FALSE;
+      child->parent = subtree;
+
+      return find_subtree_recurse (child,
+                                   &path[1], return_deepest_match,
+                                   create_if_not_found, index_in_parent);
+    }
+  else
+    return return_deepest_match ? subtree : NULL;
 }
 
-#ifndef DBUS_DISABLE_CHECKS
-static void
-check_already_exists (DBusObjectTree *tree,
-                      const char    **path)
+static DBusObjectSubtree*
+find_subtree (DBusObjectTree *tree,
+              const char    **path,
+              int            *index_in_parent)
 {
-  int i;
+  DBusObjectSubtree *subtree;
 
-  i = 0;
-  while (i < tree->n_subtrees)
-    {
-      if (path_cmp (path, (const char**) tree->subtrees[i]->path) == 0)
-        {
-          _dbus_warn ("New path (path[0] = %s) already registered\n",
-                      path[0]);
-        }
-      ++i;
-    }
+#if VERBOSE_FIND
+  _dbus_verbose ("Looking for exact registered subtree\n");
+#endif
+  
+  subtree = find_subtree_recurse (tree->root, path, FALSE, FALSE, index_in_parent);
+
+  if (subtree && subtree->message_function == NULL)
+    return NULL;
+  else
+    return subtree;
 }
+
+static DBusObjectSubtree*
+find_handler (DBusObjectTree *tree,
+              const char    **path)
+{
+#if VERBOSE_FIND
+  _dbus_verbose ("Looking for deepest handler\n");
 #endif
+  return find_subtree_recurse (tree->root, path, TRUE, FALSE, NULL);
+}
+
+static DBusObjectSubtree*
+ensure_subtree (DBusObjectTree *tree,
+                const char    **path)
+{
+#if VERBOSE_FIND
+  _dbus_verbose ("Ensuring subtree\n");
+#endif
+  return find_subtree_recurse (tree->root, path, FALSE, TRUE, NULL);
+}
 
 /**
  * Registers a new subtree in the global object tree.
@@ -349,37 +351,25 @@ _dbus_object_tree_register (DBusObjectTree              *tree,
                             void                        *user_data)
 {
   DBusObjectSubtree  *subtree;
-  DBusObjectSubtree **new_subtrees;
-  int new_n_subtrees;
 
   _dbus_assert (tree != NULL);
-  _dbus_assert (vtable->message_function != NULL);  
+  _dbus_assert (vtable->message_function != NULL);
   _dbus_assert (path != NULL);
-#ifndef DBUS_DISABLE_CHECKS
-  check_already_exists (tree, path);
-#endif
-  _dbus_assert (path[0] != NULL);
-  
-  subtree = _dbus_object_subtree_new (path, vtable, user_data);
+
+  subtree = ensure_subtree (tree, path);
   if (subtree == NULL)
     return FALSE;
-  
-  /* FIXME we should do the "double alloc each time" standard thing */
-  new_n_subtrees = tree->n_subtrees + 1;
-  new_subtrees = dbus_realloc (tree->subtrees,
-                               new_n_subtrees * sizeof (DBusObjectSubtree*));
-  if (new_subtrees == NULL)
+
+  if (subtree->message_function != NULL)
     {
-      subtree->unregister_function = NULL;
-      subtree->message_function = NULL;
-      _dbus_object_subtree_unref (subtree);
+      _dbus_warn ("A handler is already registered for the path starting with path[0] = \"%s\"\n",
+                  path[0] ? path[0] : "null");
       return FALSE;
     }
 
-  new_subtrees[tree->n_subtrees] = subtree;
-  tree->subtrees_sorted = FALSE;
-  tree->n_subtrees = new_n_subtrees;
-  tree->subtrees = new_subtrees;
+  subtree->message_function = vtable->message_function;
+  subtree->unregister_function = vtable->unregister_function;
+  subtree->user_data = user_data;
 
   return TRUE;
 }
@@ -397,43 +387,102 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree          *tree,
 {
   int i;
   DBusObjectSubtree *subtree;
+  DBusObjectPathUnregisterFunction unregister_function;
+  void *user_data;
+  DBusConnection *connection;
 
   _dbus_assert (path != NULL);
-  _dbus_assert (path[0] != NULL);
 
-  if (!find_subtree (tree, path, &i))
+  subtree = find_subtree (tree, path, &i);
+
+  if (subtree == NULL)
     {
       _dbus_warn ("Attempted to unregister path (path[0] = %s path[1] = %s) which isn't registered\n",
-                  path[0], path[1] ? path[1] : "null");
+                  path[0] ? path[0] : "null",
+                  path[1] ? path[1] : "null");
       return;
     }
 
-  _dbus_assert (i >= 0);
-  
-  subtree = tree->subtrees[i];
-
-  /* assumes a 0-byte memmove is OK */
-  memmove (&tree->subtrees[i],
-           &tree->subtrees[i+1],
-           (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0]));
-  tree->n_subtrees -= 1;
+  _dbus_assert (subtree->parent == NULL ||
+                (i >= 0 && subtree->parent->subtrees[i] == subtree));
 
   subtree->message_function = NULL;
-  
+
+  unregister_function = subtree->unregister_function;
+  user_data = subtree->user_data;
+
+  subtree->unregister_function = NULL;
+  subtree->user_data = NULL;
+
+  /* If we have no subtrees of our own, remove from
+   * our parent (FIXME could also be more aggressive
+   * and remove our parent if it becomes empty)
+   */
+  if (subtree->parent && subtree->n_subtrees == 0)
+    {
+      /* assumes a 0-byte memmove is OK */
+      memmove (&subtree->parent->subtrees[i],
+               &subtree->parent->subtrees[i+1],
+               (subtree->parent->n_subtrees - i - 1) *
+               sizeof (subtree->parent->subtrees[0]));
+      subtree->parent->n_subtrees -= 1;
+
+      subtree->parent = NULL;
+
+      _dbus_object_subtree_unref (subtree);
+    }
+  subtree = NULL;
+
+  connection = tree->connection;
+
   /* Unlock and call application code */
 #ifdef DBUS_BUILD_TESTS
-  if (tree->connection)
+  if (connection)
 #endif
-    _dbus_connection_unlock (tree->connection);
-  
+    {
+      _dbus_connection_ref_unlocked (connection);
+      _dbus_connection_unlock (connection);
+    }
+
+  if (unregister_function)
+    (* unregister_function) (connection, user_data);
+
+#ifdef DBUS_BUILD_TESTS
+  if (connection)
+#endif
+    dbus_connection_unref (connection);
+}
+
+static void
+free_subtree_recurse (DBusConnection    *connection,
+                      DBusObjectSubtree *subtree)
+{
+  /* Delete them from the end, for slightly
+   * more robustness against odd reentrancy.
+   */
+  while (subtree->n_subtrees > 0)
+    {
+      DBusObjectSubtree *child;
+
+      child = subtree->subtrees[subtree->n_subtrees - 1];
+      subtree->subtrees[subtree->n_subtrees - 1] = NULL;
+      subtree->n_subtrees -= 1;
+      child->parent = NULL;
+
+      free_subtree_recurse (connection, child);
+    }
+
+  /* Call application code */
   if (subtree->unregister_function)
     {
-      (* subtree->unregister_function) (tree->connection,
-                                        (const char**) subtree->path,
+      (* subtree->unregister_function) (connection,
                                         subtree->user_data);
+      subtree->message_function = NULL;
       subtree->unregister_function = NULL;
+      subtree->user_data = NULL;
     }
 
+  /* Now free ourselves */
   _dbus_object_subtree_unref (subtree);
 }
 
@@ -441,37 +490,15 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree          *tree,
  * Free all the handlers in the tree. Lock on tree's connection
  * must not be held.
  *
- * @todo implement
- * 
  * @param tree the object tree
  */
 void
 _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree)
 {
-  /* Delete them from the end, for slightly
-   * more robustness against odd reentrancy.
-   */
-  while (tree->n_subtrees > 0)
-    {
-      DBusObjectSubtree *subtree;
-
-      subtree = tree->subtrees[tree->n_subtrees - 1];
-      tree->subtrees[tree->n_subtrees - 1] = NULL;
-      tree->n_subtrees -= 1;
-
-      subtree->message_function = NULL; /* it's been removed */
-
-      /* Call application code */
-      if (subtree->unregister_function)
-        {
-          (* subtree->unregister_function) (tree->connection,
-                                            (const char**) subtree->path,
-                                            subtree->user_data);
-          subtree->unregister_function = NULL;
-        }
-      
-      _dbus_object_subtree_unref (subtree);      
-    }
+  if (tree->root)
+    free_subtree_recurse (tree->connection,
+                          tree->root);
+  tree->root = NULL;
 }
 
 /**
@@ -482,7 +509,7 @@ _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree)
  * to the handler for /foo/bar before the one for /foo.
  *
  * @todo thread problems
- * 
+ *
  * @param tree the global object tree
  * @param message the message to dispatch
  * @returns whether message was handled successfully
@@ -491,52 +518,82 @@ DBusHandlerResult
 _dbus_object_tree_dispatch_and_unlock (DBusObjectTree          *tree,
                                        DBusMessage             *message)
 {
-  const char **path;
-  int i;
+  char **path;
   DBusList *list;
   DBusList *link;
   DBusHandlerResult result;
+  DBusObjectSubtree *subtree;
+
+#if 0
+  _dbus_verbose ("Dispatch of message by object path\n");
+#endif
   
-  path = NULL; /* dbus_message_get_object_path (message); */
+  path = NULL;
+  if (!dbus_message_get_path_decomposed (message, &path))
+    {
+      _dbus_verbose ("No memory to get decomposed path\n");
+      return DBUS_HANDLER_RESULT_NEED_MEMORY;
+    }
 
   if (path == NULL)
-    return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
+    {
+      _dbus_verbose ("No path field in message\n");
+      return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
+    }
 
   /* Find the deepest path that covers the path in the message */
-  if (!find_handler (tree, path, &i))
-    return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
+  subtree = find_handler (tree, (const char**) path);
 
   /* Build a list of all paths that cover the path in the message */
-  
+
   list = NULL;
-  
-  do 
-    {
-      DBusObjectSubtree *subtree;
 
-      subtree = tree->subtrees[i];
+  while (subtree != NULL)
+    {
+      if (subtree->message_function != NULL)
+        {
+          _dbus_object_subtree_ref (subtree);
+
+          /* run deepest paths first */
+          if (!_dbus_list_append (&list, subtree))
+            {
+              result = DBUS_HANDLER_RESULT_NEED_MEMORY;
+              _dbus_object_subtree_unref (subtree);
+              goto free_and_return;
+            }
+        }
 
-      _dbus_object_subtree_ref (subtree);
-      _dbus_list_append (&list, subtree);
+      subtree = subtree->parent;
+    }
 
-      --i;
-      
-    } while (i > 0 && path_contains ((const char**) tree->subtrees[i]->path,
-                                     path));
+  _dbus_verbose ("%d handlers in the path tree for this message\n",
+                 _dbus_list_get_length (&list));
 
   /* Invoke each handler in the list */
-  
+
   result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
-  
+
   link = _dbus_list_get_first_link (&list);
   while (link != NULL)
     {
-      DBusObjectSubtree *subtree = link->data;
       DBusList *next = _dbus_list_get_next_link (&list, link);
-      
-      /* message_function is NULL if we're unregistered */
+      subtree = link->data;
+
+      /* message_function is NULL if we're unregistered
+       * due to reentrancy
+       */
       if (subtree->message_function)
         {
+          DBusObjectPathMessageFunction message_function;
+          void *user_data;
+
+          message_function = subtree->message_function;
+          user_data = subtree->user_data;
+
+#if 0
+          _dbus_verbose ("  (invoking a handler)\n");
+#endif
+          
 #ifdef DBUS_BUILD_TESTS
           if (tree->connection)
 #endif
@@ -546,19 +603,20 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree          *tree,
            * before we invoke the callback, and I can't figure out a
            * good way to solve this.
            */
-          
-          result = (* subtree->message_function) (tree->connection,
-                                                  message, subtree->user_data);
-          
-          if (result == DBUS_HANDLER_RESULT_HANDLED)
+
+          result = (* message_function) (tree->connection,
+                                         message,
+                                         user_data);
+
+          if (result != DBUS_HANDLER_RESULT_NOT_YET_HANDLED)
             goto free_and_return;
 
 #ifdef DBUS_BUILD_TESTS
           if (tree->connection)
 #endif
             _dbus_connection_lock (tree->connection);
-        }       
-          
+        }
+
       link = next;
     }
 
@@ -574,82 +632,69 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree          *tree,
       _dbus_object_subtree_unref (link->data);
       _dbus_list_remove_link (&list, link);
     }
-  
+  dbus_free_string_array (path);
+
   return result;
 }
 
 /**
- * Allocates a subtree object with a string array appended as one big
- * memory block, so result is freed with one dbus_free(). Returns
- * #NULL if memory allocation fails.
+ * Allocates a subtree object.
  *
- * @param array array to duplicate.
+ * @param name name to duplicate.
  * @returns newly-allocated subtree
  */
 static DBusObjectSubtree*
-allocate_subtree_object (const char **array)
+allocate_subtree_object (const char *name)
 {
   int len;
-  int member_lens;
-  int i;
-  char *p;
-  void *subtree;
-  char **path_dest;
-  const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, path);
-  
-  if (array == NULL)
-    return NULL;
+  DBusObjectSubtree *subtree;
+  const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, name);
 
-  member_lens = 0;
-  for (len = 0; array[len] != NULL; ++len)
-    member_lens += strlen (array[len]) + 1;
-  
-  subtree = dbus_malloc (front_padding +
-                         (len + 1) * sizeof (char*) +
-                         member_lens);
-  if (subtree == NULL)
-    return NULL;
+  _dbus_assert (name != NULL);
 
-  path_dest = (char**) (((char*) subtree) + front_padding);
-  
-  path_dest[len] = NULL; /* NULL-terminate the array portion */
-  p = ((char*) subtree) + (len + 1) * sizeof (char*) + front_padding;
-  
-  i = 0;
-  while (i < len)
-    {
-      int this_len;
+  len = strlen (name);
 
-      path_dest[i] = p;
-      
-      this_len = strlen (array[i]);
-      memcpy (p, array[i], this_len + 1);
-      p += this_len + 1;
+  subtree = dbus_malloc (front_padding + (len + 1));
 
-      ++i;
-    }
+  if (subtree == NULL)
+    return NULL;
+
+  memcpy (subtree->name, name, len + 1);
 
   return subtree;
 }
 
 static DBusObjectSubtree*
-_dbus_object_subtree_new (const char                 **path,
+_dbus_object_subtree_new (const char                  *name,
                           const DBusObjectPathVTable  *vtable,
                           void                        *user_data)
 {
   DBusObjectSubtree *subtree;
 
-  subtree = allocate_subtree_object (path);
+  subtree = allocate_subtree_object (name);
   if (subtree == NULL)
     goto oom;
 
-  _dbus_assert (path != NULL);
-  _dbus_assert (path[0] != NULL);
+  _dbus_assert (name != NULL);
+
+  subtree->parent = NULL;
+
+  if (vtable)
+    {
+      subtree->message_function = vtable->message_function;
+      subtree->unregister_function = vtable->unregister_function;
+    }
+  else
+    {
+      subtree->message_function = NULL;
+      subtree->unregister_function = NULL;
+    }
 
-  subtree->message_function = vtable->message_function;
-  subtree->unregister_function = vtable->unregister_function;
   subtree->user_data = user_data;
   subtree->refcount.value = 1;
+  subtree->subtrees = NULL;
+  subtree->n_subtrees = 0;
+  subtree->subtrees_sorted = TRUE;
   
   return subtree;
 
@@ -658,7 +703,7 @@ _dbus_object_subtree_new (const char                 **path,
     {
       dbus_free (subtree);
     }
-  
+
   return NULL;
 }
 
@@ -678,6 +723,8 @@ _dbus_object_subtree_unref (DBusObjectSubtree *subtree)
     {
       _dbus_assert (subtree->unregister_function == NULL);
       _dbus_assert (subtree->message_function == NULL);
+
+      dbus_free (subtree->subtrees);
       dbus_free (subtree);
     }
 }
@@ -694,7 +741,7 @@ flatten_path (const char **path)
   DBusString str;
   int i;
   char *s;
-  
+
   if (!_dbus_string_init (&str))
     return NULL;
 
@@ -703,10 +750,10 @@ flatten_path (const char **path)
     {
       if (!_dbus_string_append_byte (&str, '/'))
         goto nomem;
-      
+
       if (!_dbus_string_append (&str, path[i]))
         goto nomem;
-      
+
       ++i;
     }
 
@@ -714,154 +761,89 @@ flatten_path (const char **path)
     goto nomem;
 
   _dbus_string_free (&str);
-  
+
   return s;
-  
+
  nomem:
   _dbus_string_free (&str);
   return NULL;
 }
 
-static void
-spew_tree (DBusObjectTree *tree)
+/* Returns TRUE if container is a parent of child
+ */
+static dbus_bool_t
+path_contains (const char **container,
+               const char **child)
 {
   int i;
 
-  printf ("Tree of %d subpaths\n",
-          tree->n_subtrees);
-  
   i = 0;
-  while (i < tree->n_subtrees)
+  while (child[i] != NULL)
     {
-      char *s;
-
-      s = flatten_path ((const char **) tree->subtrees[i]->path);
-
-      printf ("  %d path = %s\n", i, s);
-
-      dbus_free (s);
-      
-      ++i;
-    }
-}
-
-static dbus_bool_t
-test_subtree_cmp (const char **path1,
-                  const char **path2,
-                  int          expected,
-                  dbus_bool_t  reverse)
-{
-  DBusObjectSubtree *subtree1;
-  DBusObjectSubtree *subtree2;
-  dbus_bool_t retval;
-  DBusObjectPathVTable vtable;
-
-  _DBUS_ZERO (vtable);
-
-  retval = FALSE;
-  
-  subtree1 = _dbus_object_subtree_new (path1, &vtable, NULL);
-  subtree2 = _dbus_object_subtree_new (path2, &vtable, NULL);
-  if (subtree1 == NULL || subtree2 == NULL)
-    goto out;
+      int v;
 
-  _dbus_assert (subtree_cmp (subtree1, subtree2) == expected);
+      if (container[i] == NULL)
+        return TRUE; /* container ran out, child continues;
+                      * thus the container is a parent of the
+                      * child.
+                      */
 
-  retval = TRUE;
-  
- out:
+      _dbus_assert (container[i] != NULL);
+      _dbus_assert (child[i] != NULL);
 
-  if (subtree1)
-    _dbus_object_subtree_unref (subtree1);
+      v = strcmp (container[i], child[i]);
 
-  if (subtree2)
-    _dbus_object_subtree_unref (subtree2);
+      if (v != 0)
+        return FALSE; /* they overlap until here and then are different,
+                       * not overlapping
+                       */
 
-  if (retval && reverse)
-    {
-      /* Verify that the reverse also holds */
-      if (expected > 0)
-        return test_subtree_cmp (path2, path1, -1, FALSE);
-      else if (expected < 0)
-        return test_subtree_cmp (path2, path1, 1, FALSE);
-      else
-        return test_subtree_cmp (path2, path1, 0, FALSE);
+      ++i;
     }
-  
-  return retval;
+
+  /* Child ran out; if container also did, they are equal;
+   * otherwise, the child is a parent of the container.
+   */
+  if (container[i] == NULL)
+    return TRUE; /* equal is counted as containing */
+  else
+    return FALSE;
 }
 
 static void
-test_path_contains (const char  **path1,
-                    const char  **path2,
-                    dbus_bool_t   expected)
+spew_subtree_recurse (DBusObjectSubtree *subtree,
+                      int                indent)
 {
-  if (!path_contains (path1, path2) == expected)
-    {
-      char *s1, *s2;
-      s1 = flatten_path (path1);
-      s2 = flatten_path (path2);
-      
-      _dbus_warn ("Expected that path %s %s %s\n",
-                  s1, expected ? "contains" : "doesn't contain", s2);
-      
-      dbus_free (s1);
-      dbus_free (s2);
-      
-      exit (1);
-    }
-  
-  if (path_cmp (path1, path2) == 0)
+  int i;
+
+  i = 0;
+  while (i < indent)
     {
-      if (!path_contains (path2, path1))
-        {
-          char *s1, *s2;
-          s1 = flatten_path (path1);
-          s2 = flatten_path (path2);
-          
-          _dbus_warn ("Expected that path %s contains %s since the paths are equal\n",
-                      s1, s2);
-          
-          dbus_free (s1);
-          dbus_free (s2);
-          
-          exit (1);
-        }
+      _dbus_verbose (" ");
+      ++i;
     }
-  /* If path1 contains path2, then path2 can't contain path1 */
-  else if (expected && path_contains (path2, path1))
-    {
-      char *s1, *s2;
 
-      s1 = flatten_path (path1);
-      s2 = flatten_path (path2);
-      
-      _dbus_warn ("Expected that path %s doesn't contain %s\n",
-                  s1, s2);
+  _dbus_verbose ("%s (%d children)\n",
+                 subtree->name, subtree->n_subtrees);
 
-      dbus_free (s1);
-      dbus_free (s2);
-      
-      exit (1);
+  i = 0;
+  while (i < subtree->n_subtrees)
+    {
+      spew_subtree_recurse (subtree->subtrees[i], indent + 2);
+
+      ++i;
     }
 }
 
 static void
-test_path_copy (const char **path)
+spew_tree (DBusObjectTree *tree)
 {
-  DBusObjectSubtree *subtree;
-
-  subtree = allocate_subtree_object (path);
-  if (subtree == NULL)
-    return;
-  
-  _dbus_assert (path_cmp (path, (const char**) subtree->path) == 0);
-
-  dbus_free (subtree);
+  spew_subtree_recurse (tree->root, 0);
 }
 
 typedef struct
 {
+  const char **path;
   dbus_bool_t message_handled;
   dbus_bool_t handler_unregistered;
 
@@ -870,7 +852,6 @@ typedef struct
 
 static void
 test_unregister_function (DBusConnection  *connection,
-                          const char     **path,
                           void            *user_data)
 {
   TreeTestData *ttd = user_data;
@@ -886,7 +867,7 @@ test_message_function (DBusConnection  *connection,
   TreeTestData *ttd = user_data;
 
   ttd->message_handled = TRUE;
-  
+
   return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
 }
 
@@ -901,7 +882,8 @@ do_register (DBusObjectTree *tree,
 
   tree_test_data[i].message_handled = FALSE;
   tree_test_data[i].handler_unregistered = FALSE;
-  
+  tree_test_data[i].path = path;
+
   if (!_dbus_object_tree_register (tree, path,
                                    &vtable,
                                    &tree_test_data[i]))
@@ -911,6 +893,68 @@ do_register (DBusObjectTree *tree,
 }
 
 static dbus_bool_t
+do_test_dispatch (DBusObjectTree *tree,
+                  const char    **path,
+                  int             i,
+                  TreeTestData   *tree_test_data,
+                  int             n_test_data)
+{
+  DBusMessage *message;
+  int j;
+  DBusHandlerResult result;
+  char *flat;
+
+  message = NULL;
+  
+  flat = flatten_path (path);
+  if (flat == NULL)
+    goto oom;
+
+  message = dbus_message_new_method_call (NULL,
+                                          flat,
+                                          "org.freedesktop.TestInterface",
+                                          "Foo");
+  dbus_free (flat);
+  if (message == NULL)
+    goto oom;
+
+  j = 0;
+  while (j < n_test_data)
+    {
+      tree_test_data[j].message_handled = FALSE;
+      ++j;
+    }
+
+  result = _dbus_object_tree_dispatch_and_unlock (tree, message);
+  if (result == DBUS_HANDLER_RESULT_NEED_MEMORY)
+    goto oom;
+
+  _dbus_assert (tree_test_data[i].message_handled);
+
+  j = 0;
+  while (j < n_test_data)
+    {
+      if (tree_test_data[j].message_handled)
+        _dbus_assert (path_contains (tree_test_data[j].path,
+                                     path));
+      else
+        _dbus_assert (!path_contains (tree_test_data[j].path,
+                                      path));
+
+      ++j;
+    }
+
+  dbus_message_unref (message);
+
+  return TRUE;
+
+ oom:
+  if (message)
+    dbus_message_unref (message);
+  return FALSE;
+}
+
+static dbus_bool_t
 object_tree_test_iteration (void *data)
 {
   const char *path1[] = { "foo", NULL };
@@ -919,103 +963,51 @@ object_tree_test_iteration (void *data)
   const char *path4[] = { "foo", "bar", "boo", NULL };
   const char *path5[] = { "blah", NULL };
   const char *path6[] = { "blah", "boof", NULL };
+  const char *path7[] = { "blah", "boof", "this", "is", "really", "long", NULL };
+  const char *path8[] = { "childless", NULL };
   DBusObjectTree *tree;
-  TreeTestData tree_test_data[6];
+  TreeTestData tree_test_data[8];
   int i;
-  
-  test_path_copy (path1);
-  test_path_copy (path2);
-  test_path_copy (path3);
-  test_path_copy (path4);
-  test_path_copy (path5);
-  test_path_copy (path6);
-  
+
   tree = NULL;
 
-  test_path_contains (path1, path1, TRUE);
-  test_path_contains (path1, path2, TRUE);
-  test_path_contains (path1, path3, TRUE);
-  test_path_contains (path1, path4, TRUE);
-  test_path_contains (path1, path5, FALSE);
-  test_path_contains (path1, path6, FALSE); 
-
-  test_path_contains (path2, path1, FALSE);
-  test_path_contains (path2, path2, TRUE);
-  test_path_contains (path2, path3, TRUE);
-  test_path_contains (path2, path4, TRUE);
-  test_path_contains (path2, path5, FALSE);
-  test_path_contains (path2, path6, FALSE);
-
-  test_path_contains (path3, path1, FALSE);
-  test_path_contains (path3, path2, FALSE);
-  test_path_contains (path3, path3, TRUE);
-  test_path_contains (path3, path4, FALSE);
-  test_path_contains (path3, path5, FALSE);
-  test_path_contains (path3, path6, FALSE);
-
-  test_path_contains (path4, path1, FALSE);
-  test_path_contains (path4, path2, FALSE);
-  test_path_contains (path4, path3, FALSE);
-  test_path_contains (path4, path4, TRUE);
-  test_path_contains (path4, path5, FALSE);
-  test_path_contains (path4, path6, FALSE);
-
-  test_path_contains (path5, path1, FALSE);
-  test_path_contains (path5, path2, FALSE);
-  test_path_contains (path5, path3, FALSE);
-  test_path_contains (path5, path4, FALSE);
-  test_path_contains (path5, path5, TRUE);
-  test_path_contains (path5, path6, TRUE);
-  
-  test_path_contains (path6, path1, FALSE);
-  test_path_contains (path6, path2, FALSE);
-  test_path_contains (path6, path3, FALSE);
-  test_path_contains (path6, path4, FALSE);
-  test_path_contains (path6, path5, FALSE);
-  test_path_contains (path6, path6, TRUE);
-  
-  if (!test_subtree_cmp (path1, path1, 0, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path3, path3, 0, TRUE))
-    goto out;
-  /* When testing -1, the reverse also gets tested */
-  if (!test_subtree_cmp (path1, path2, -1, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path1, path3, -1, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path2, path3, -1, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path2, path4, -1, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path3, path4, -1, TRUE))
-    goto out;
-  if (!test_subtree_cmp (path5, path1, -1, TRUE))
-    goto out;
-  
   tree = _dbus_object_tree_new (NULL);
   if (tree == NULL)
     goto out;
-  
+
   if (!do_register (tree, path1, 0, tree_test_data))
     goto out;
-  
+
   _dbus_assert (find_subtree (tree, path1, NULL));
   _dbus_assert (!find_subtree (tree, path2, NULL));
   _dbus_assert (!find_subtree (tree, path3, NULL));
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
-  
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
+
+  _dbus_assert (find_handler (tree, path1));
+  _dbus_assert (find_handler (tree, path2));
+  _dbus_assert (find_handler (tree, path3));
+  _dbus_assert (find_handler (tree, path4));
+  _dbus_assert (find_handler (tree, path5) == tree->root);
+  _dbus_assert (find_handler (tree, path6) == tree->root);
+  _dbus_assert (find_handler (tree, path7) == tree->root);
+  _dbus_assert (find_handler (tree, path8) == tree->root);
+
   if (!do_register (tree, path2, 1, tree_test_data))
     goto out;
-  
-  _dbus_assert (find_subtree (tree, path1, NULL));  
+
+  _dbus_assert (find_subtree (tree, path1, NULL));
   _dbus_assert (find_subtree (tree, path2, NULL));
   _dbus_assert (!find_subtree (tree, path3, NULL));
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
-  
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
+
   if (!do_register (tree, path3, 2, tree_test_data))
     goto out;
 
@@ -1025,17 +1017,20 @@ object_tree_test_iteration (void *data)
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
   
   if (!do_register (tree, path4, 3, tree_test_data))
     goto out;
 
-
   _dbus_assert (find_subtree (tree, path1, NULL));
   _dbus_assert (find_subtree (tree, path2, NULL));
-  _dbus_assert (find_subtree (tree, path3, NULL));
+  _dbus_assert (find_subtree (tree, path3, NULL));  
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
   
   if (!do_register (tree, path5, 4, tree_test_data))
     goto out;
@@ -1046,7 +1041,18 @@ object_tree_test_iteration (void *data)
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
   
+  _dbus_assert (find_handler (tree, path1) != tree->root);
+  _dbus_assert (find_handler (tree, path2) != tree->root);
+  _dbus_assert (find_handler (tree, path3) != tree->root);
+  _dbus_assert (find_handler (tree, path4) != tree->root);
+  _dbus_assert (find_handler (tree, path5) != tree->root);
+  _dbus_assert (find_handler (tree, path6) != tree->root);
+  _dbus_assert (find_handler (tree, path7) != tree->root);
+  _dbus_assert (find_handler (tree, path8) == tree->root);
+
   if (!do_register (tree, path6, 5, tree_test_data))
     goto out;
 
@@ -1056,7 +1062,42 @@ object_tree_test_iteration (void *data)
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
+
+  if (!do_register (tree, path7, 6, tree_test_data))
+    goto out;
 
+  _dbus_assert (find_subtree (tree, path1, NULL));
+  _dbus_assert (find_subtree (tree, path2, NULL));
+  _dbus_assert (find_subtree (tree, path3, NULL));
+  _dbus_assert (find_subtree (tree, path4, NULL));
+  _dbus_assert (find_subtree (tree, path5, NULL));
+  _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
+
+  if (!do_register (tree, path8, 7, tree_test_data))
+    goto out;
+
+  _dbus_assert (find_subtree (tree, path1, NULL));
+  _dbus_assert (find_subtree (tree, path2, NULL));
+  _dbus_assert (find_subtree (tree, path3, NULL));
+  _dbus_assert (find_subtree (tree, path4, NULL));
+  _dbus_assert (find_subtree (tree, path5, NULL));
+  _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
+  
+  _dbus_assert (find_handler (tree, path1) != tree->root);
+  _dbus_assert (find_handler (tree, path2) != tree->root);
+  _dbus_assert (find_handler (tree, path3) != tree->root);
+  _dbus_assert (find_handler (tree, path4) != tree->root);
+  _dbus_assert (find_handler (tree, path5) != tree->root);
+  _dbus_assert (find_handler (tree, path6) != tree->root);
+  _dbus_assert (find_handler (tree, path7) != tree->root);
+  _dbus_assert (find_handler (tree, path8) != tree->root);
+  
   /* Check that destroying tree calls unregister funcs */
   _dbus_object_tree_unref (tree);
 
@@ -1072,7 +1113,7 @@ object_tree_test_iteration (void *data)
   tree = _dbus_object_tree_new (NULL);
   if (tree == NULL)
     goto out;
-  
+
   if (!do_register (tree, path1, 0, tree_test_data))
     goto out;
   if (!do_register (tree, path2, 1, tree_test_data))
@@ -1085,7 +1126,11 @@ object_tree_test_iteration (void *data)
     goto out;
   if (!do_register (tree, path6, 5, tree_test_data))
     goto out;
-
+  if (!do_register (tree, path7, 6, tree_test_data))
+    goto out;
+  if (!do_register (tree, path8, 7, tree_test_data))
+    goto out;
+  
   _dbus_object_tree_unregister_and_unlock (tree, path1);
 
   _dbus_assert (!find_subtree (tree, path1, NULL));
@@ -1094,7 +1139,9 @@ object_tree_test_iteration (void *data)
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
-  
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
+
   _dbus_object_tree_unregister_and_unlock (tree, path2);
 
   _dbus_assert (!find_subtree (tree, path1, NULL));
@@ -1103,7 +1150,9 @@ object_tree_test_iteration (void *data)
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
-
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
+  
   _dbus_object_tree_unregister_and_unlock (tree, path3);
 
   _dbus_assert (!find_subtree (tree, path1, NULL));
@@ -1112,6 +1161,8 @@ object_tree_test_iteration (void *data)
   _dbus_assert (find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
   
   _dbus_object_tree_unregister_and_unlock (tree, path4);
 
@@ -1121,6 +1172,8 @@ object_tree_test_iteration (void *data)
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
   
   _dbus_object_tree_unregister_and_unlock (tree, path5);
 
@@ -1130,6 +1183,8 @@ object_tree_test_iteration (void *data)
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
   
   _dbus_object_tree_unregister_and_unlock (tree, path6);
 
@@ -1139,6 +1194,30 @@ object_tree_test_iteration (void *data)
   _dbus_assert (!find_subtree (tree, path4, NULL));
   _dbus_assert (!find_subtree (tree, path5, NULL));
   _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
+
+  _dbus_object_tree_unregister_and_unlock (tree, path7);
+
+  _dbus_assert (!find_subtree (tree, path1, NULL));
+  _dbus_assert (!find_subtree (tree, path2, NULL));
+  _dbus_assert (!find_subtree (tree, path3, NULL));
+  _dbus_assert (!find_subtree (tree, path4, NULL));
+  _dbus_assert (!find_subtree (tree, path5, NULL));
+  _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (find_subtree (tree, path8, NULL));
+
+  _dbus_object_tree_unregister_and_unlock (tree, path8);
+
+  _dbus_assert (!find_subtree (tree, path1, NULL));
+  _dbus_assert (!find_subtree (tree, path2, NULL));
+  _dbus_assert (!find_subtree (tree, path3, NULL));
+  _dbus_assert (!find_subtree (tree, path4, NULL));
+  _dbus_assert (!find_subtree (tree, path5, NULL));
+  _dbus_assert (!find_subtree (tree, path6, NULL));
+  _dbus_assert (!find_subtree (tree, path7, NULL));
+  _dbus_assert (!find_subtree (tree, path8, NULL));
   
   i = 0;
   while (i < (int) _DBUS_N_ELEMENTS (tree_test_data))
@@ -1149,7 +1228,7 @@ object_tree_test_iteration (void *data)
     }
 
   /* Register it all again, and test dispatch */
-  
+
   if (!do_register (tree, path1, 0, tree_test_data))
     goto out;
   if (!do_register (tree, path2, 1, tree_test_data))
@@ -1162,13 +1241,36 @@ object_tree_test_iteration (void *data)
     goto out;
   if (!do_register (tree, path6, 5, tree_test_data))
     goto out;
+  if (!do_register (tree, path7, 6, tree_test_data))
+    goto out;
+  if (!do_register (tree, path8, 7, tree_test_data))
+    goto out;
+
+#if 0
+  spew_tree (tree);
+#endif
   
-  /* FIXME (once messages have an object path field) */
+  if (!do_test_dispatch (tree, path1, 0, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path2, 1, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path3, 2, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path4, 3, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path5, 4, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path6, 5, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path7, 6, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
+  if (!do_test_dispatch (tree, path8, 7, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
+    goto out;
   
  out:
   if (tree)
     _dbus_object_tree_unref (tree);
-  
+
   return TRUE;
 }
 
@@ -1183,7 +1285,7 @@ _dbus_object_tree_test (void)
   _dbus_test_oom_handling ("object tree",
                            object_tree_test_iteration,
                            NULL);
-  
+
   return TRUE;
 }