dbus/dbus-object-tree.c

   1 /* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
   2 /* dbus-object-tree.c  DBusObjectTree (internals of DBusConnection)
   3  *
   4  * Copyright (C) 2003, 2005  Red Hat Inc.
   5  *
   6  * Licensed under the Academic Free License version 2.1
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with this program; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  *
  22  */
  23
  24 #include <config.h>
  25 #include "dbus-object-tree.h"
  26 #include "dbus-connection-internal.h"
  27 #include "dbus-internals.h"
  28 #include "dbus-hash.h"
  29 #include "dbus-protocol.h"
  30 #include "dbus-string.h"
  31 #include <string.h>
  32 #include <stdlib.h>
  33
  34 /**
  35  * @defgroup DBusObjectTree A hierarchy of objects with container-contained relationship
  36  * @ingroup  DBusInternals
  37  * @brief DBusObjectTree is used by DBusConnection to track the object tree
  38  *
  39  * Types and functions related to DBusObjectTree. These
  40  * are all library-internal.
  41  *
  42  * @{
  43  */
  44
  45 /** Subnode of the object hierarchy */
  46 typedef struct DBusObjectSubtree DBusObjectSubtree;
  47
  48 static DBusObjectSubtree* _dbus_object_subtree_new   (const char                  *name,
  49                                                       const DBusObjectPathVTable  *vtable,
  50                                                       void                        *user_data);
  51 static DBusObjectSubtree* _dbus_object_subtree_ref   (DBusObjectSubtree           *subtree);
  52 static void               _dbus_object_subtree_unref (DBusObjectSubtree           *subtree);
  53
  54 /**
  55  * Internals of DBusObjectTree
  56  */
  57 struct DBusObjectTree
  58 {
  59   int                 refcount;   /**< Reference count */
  60   DBusConnection     *connection; /**< Connection this tree belongs to */
  61
  62   DBusObjectSubtree  *root;       /**< Root of the tree ("/" node) */
  63 };
  64
  65 /**
  66  * Struct representing a single registered subtree handler, or node
  67  * that's a parent of a registered subtree handler. If
  68  * message_function != NULL there's actually a handler at this node.
  69  */
  70 struct DBusObjectSubtree
  71 {
  72   DBusAtomic                         refcount;            /**< Reference count */
  73   DBusObjectSubtree                 *parent;              /**< Parent node */
  74   DBusObjectPathUnregisterFunction   unregister_function; /**< Function to call on unregister */
  75   DBusObjectPathMessageFunction      message_function;    /**< Function to handle messages */
  76   void                              *user_data;           /**< Data for functions */
  77   DBusObjectSubtree                **subtrees;            /**< Child nodes */
  78   int                                n_subtrees;          /**< Number of child nodes */
  79   int                                max_subtrees;        /**< Number of allocated entries in subtrees */
  80   unsigned int                       invoke_as_fallback : 1; /**< Whether to invoke message_function when child nodes don't handle the message */
  81   char                               name[1]; /**< Allocated as large as necessary */
  82 };
  83
  84 /**
  85  * Creates a new object tree, representing a mapping from paths
  86  * to handler vtables.
  87  *
  88  * @param connection the connection this tree belongs to
  89  * @returns the new tree or #NULL if no memory
  90  */
  91 DBusObjectTree*
  92 _dbus_object_tree_new (DBusConnection *connection)
  93 {
  94   DBusObjectTree *tree;
  95
  96   /* the connection passed in here isn't fully constructed,
  97    * so don't do anything more than store a pointer to
  98    * it
  99    */
 100
 101   tree = dbus_new0 (DBusObjectTree, 1);
 102   if (tree == NULL)
 103     goto oom;
 104
 105   tree->refcount = 1;
 106   tree->connection = connection;
 107   tree->root = _dbus_object_subtree_new ("/", NULL, NULL);
 108   if (tree->root == NULL)
 109     goto oom;
 110   tree->root->invoke_as_fallback = TRUE;
 111
 112   return tree;
 113
 114  oom:
 115   if (tree)
 116     {
 117       dbus_free (tree);
 118     }
 119
 120   return NULL;
 121 }
 122
 123 /**
 124  * Increment the reference count
 125  * @param tree the object tree
 126  * @returns the object tree
 127  */
 128 DBusObjectTree *
 129 _dbus_object_tree_ref (DBusObjectTree *tree)
 130 {
 131   _dbus_assert (tree->refcount > 0);
 132
 133   tree->refcount += 1;
 134
 135   return tree;
 136 }
 137
 138 /**
 139  * Decrement the reference count
 140  * @param tree the object tree
 141  */
 142 void
 143 _dbus_object_tree_unref (DBusObjectTree *tree)
 144 {
 145   _dbus_assert (tree->refcount > 0);
 146
 147   tree->refcount -= 1;
 148
 149   if (tree->refcount == 0)
 150     {
 151       _dbus_object_tree_free_all_unlocked (tree);
 152
 153       dbus_free (tree);
 154     }
 155 }
 156
 157 /** Set to 1 to get a bunch of debug spew about finding the
 158  * subtree nodes
 159  */
 160 #define VERBOSE_FIND 0
 161
 162 static DBusObjectSubtree*
 163 find_subtree_recurse (DBusObjectSubtree  *subtree,
 164                       const char        **path,
 165                       dbus_bool_t         create_if_not_found,
 166                       int                *index_in_parent,
 167                       dbus_bool_t        *exact_match)
 168 {
 169   int i, j;
 170   dbus_bool_t return_deepest_match;
 171
 172   return_deepest_match = exact_match != NULL;
 173
 174   _dbus_assert (!(return_deepest_match && create_if_not_found));
 175
 176   if (path[0] == NULL)
 177     {
 178 #if VERBOSE_FIND
 179       _dbus_verbose ("  path exhausted, returning %s\n",
 180                      subtree->name);
 181 #endif
 182       if (exact_match != NULL)
 183         *exact_match = TRUE;
 184       return subtree;
 185     }
 186
 187 #if VERBOSE_FIND
 188   _dbus_verbose ("  searching children of %s for %s\n",
 189                  subtree->name, path[0]);
 190 #endif
 191
 192   i = 0;
 193   j = subtree->n_subtrees;
 194   while (i < j)
 195     {
 196       int k, v;
 197
 198       k = (i + j) / 2;
 199       v = strcmp (path[0], subtree->subtrees[k]->name);
 200
 201 #if VERBOSE_FIND
 202       _dbus_verbose ("  %s cmp %s = %d\n",
 203                      path[0], subtree->subtrees[k]->name,
 204                      v);
 205 #endif
 206
 207       if (v == 0)
 208         {
 209           if (index_in_parent)
 210             {
 211 #if VERBOSE_FIND
 212               _dbus_verbose ("  storing parent index %d\n", k);
 213 #endif
 214               *index_in_parent = k;
 215             }
 216
 217           if (return_deepest_match)
 218             {
 219               DBusObjectSubtree *next;
 220
 221               next = find_subtree_recurse (subtree->subtrees[k],
 222                                            &path[1], create_if_not_found,
 223                                            index_in_parent, exact_match);
 224               if (next == NULL &&
 225                   subtree->invoke_as_fallback)
 226                 {
 227 #if VERBOSE_FIND
 228                   _dbus_verbose ("  no deeper match found, returning %s\n",
 229                                  subtree->name);
 230 #endif
 231                   if (exact_match != NULL)
 232                     *exact_match = FALSE;
 233                   return subtree;
 234                 }
 235               else
 236                 return next;
 237             }
 238           else
 239             return find_subtree_recurse (subtree->subtrees[k],
 240                                          &path[1], create_if_not_found,
 241                                          index_in_parent, exact_match);
 242         }
 243       else if (v < 0)
 244         {
 245           j = k;
 246         }
 247       else
 248         {
 249           i = k + 1;
 250         }
 251     }
 252
 253 #if VERBOSE_FIND
 254   _dbus_verbose ("  no match found, current tree %s, create_if_not_found = %d\n",
 255                  subtree->name, create_if_not_found);
 256 #endif
 257
 258   if (create_if_not_found)
 259     {
 260       DBusObjectSubtree* child;
 261       int child_pos, new_n_subtrees;
 262
 263 #if VERBOSE_FIND
 264       _dbus_verbose ("  creating subtree %s\n",
 265                      path[0]);
 266 #endif
 267
 268       child = _dbus_object_subtree_new (path[0],
 269                                         NULL, NULL);
 270       if (child == NULL)
 271         return NULL;
 272
 273       new_n_subtrees = subtree->n_subtrees + 1;
 274       if (new_n_subtrees > subtree->max_subtrees)
 275         {
 276           int new_max_subtrees;
 277           DBusObjectSubtree **new_subtrees;
 278
 279           new_max_subtrees = subtree->max_subtrees == 0 ? 1 : 2 * subtree->max_subtrees;
 280           new_subtrees = dbus_realloc (subtree->subtrees,
 281                                        new_max_subtrees * sizeof (DBusObjectSubtree*));
 282           if (new_subtrees == NULL)
 283             {
 284               _dbus_object_subtree_unref (child);
 285               return NULL;
 286             }
 287           subtree->subtrees = new_subtrees;
 288           subtree->max_subtrees = new_max_subtrees;
 289         }
 290
 291       /* The binary search failed, so i == j points to the
 292          place the child should be inserted. */
 293       child_pos = i;
 294       _dbus_assert (child_pos < new_n_subtrees &&
 295                     new_n_subtrees <= subtree->max_subtrees);
 296       if (child_pos + 1 < new_n_subtrees)
 297         {
 298           memmove (&subtree->subtrees[child_pos+1],
 299                    &subtree->subtrees[child_pos],
 300                    (new_n_subtrees - child_pos - 1) *
 301                    sizeof subtree->subtrees[0]);
 302         }
 303       subtree->subtrees[child_pos] = child;
 304
 305       if (index_in_parent)
 306         *index_in_parent = child_pos;
 307       subtree->n_subtrees = new_n_subtrees;
 308       child->parent = subtree;
 309
 310       return find_subtree_recurse (child,
 311                                    &path[1], create_if_not_found,
 312                                    index_in_parent, exact_match);
 313     }
 314   else
 315     {
 316       if (exact_match != NULL)
 317         *exact_match = FALSE;
 318       return (return_deepest_match && subtree->invoke_as_fallback) ? subtree : NULL;
 319     }
 320 }
 321
 322 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 323 static DBusObjectSubtree*
 324 find_subtree (DBusObjectTree *tree,
 325               const char    **path,
 326               int            *index_in_parent)
 327 {
 328   DBusObjectSubtree *subtree;
 329
 330 #if VERBOSE_FIND
 331   _dbus_verbose ("Looking for exact registered subtree\n");
 332 #endif
 333
 334   subtree = find_subtree_recurse (tree->root, path, FALSE, index_in_parent, NULL);
 335
 336   if (subtree && subtree->message_function == NULL)
 337     return NULL;
 338   else
 339     return subtree;
 340 }
 341 #endif
 342
 343 static DBusObjectSubtree*
 344 lookup_subtree (DBusObjectTree *tree,
 345                 const char    **path)
 346 {
 347 #if VERBOSE_FIND
 348   _dbus_verbose ("Looking for subtree\n");
 349 #endif
 350   return find_subtree_recurse (tree->root, path, FALSE, NULL, NULL);
 351 }
 352
 353 static DBusObjectSubtree*
 354 find_handler (DBusObjectTree *tree,
 355               const char    **path,
 356               dbus_bool_t    *exact_match)
 357 {
 358 #if VERBOSE_FIND
 359   _dbus_verbose ("Looking for deepest handler\n");
 360 #endif
 361   _dbus_assert (exact_match != NULL);
 362
 363   *exact_match = FALSE; /* ensure always initialized */
 364
 365   return find_subtree_recurse (tree->root, path, FALSE, NULL, exact_match);
 366 }
 367
 368 static DBusObjectSubtree*
 369 ensure_subtree (DBusObjectTree *tree,
 370                 const char    **path)
 371 {
 372 #if VERBOSE_FIND
 373   _dbus_verbose ("Ensuring subtree\n");
 374 #endif
 375   return find_subtree_recurse (tree->root, path, TRUE, NULL, NULL);
 376 }
 377
 378 static char *flatten_path (const char **path);
 379
 380 /**
 381  * Registers a new subtree in the global object tree.
 382  *
 383  * @param tree the global object tree
 384  * @param fallback #TRUE to handle messages to children of this path
 385  * @param path NULL-terminated array of path elements giving path to subtree
 386  * @param vtable the vtable used to traverse this subtree
 387  * @param user_data user data to pass to methods in the vtable
 388  * @param error address where an error can be returned
 389  * @returns #FALSE if an error (#DBUS_ERROR_NO_MEMORY or
 390  *    #DBUS_ERROR_OBJECT_PATH_IN_USE) is reported
 391  */
 392 dbus_bool_t
 393 _dbus_object_tree_register (DBusObjectTree              *tree,
 394                             dbus_bool_t                  fallback,
 395                             const char                 **path,
 396                             const DBusObjectPathVTable  *vtable,
 397                             void                        *user_data,
 398                             DBusError                   *error)
 399 {
 400   DBusObjectSubtree  *subtree;
 401
 402   _dbus_assert (tree != NULL);
 403   _dbus_assert (vtable->message_function != NULL);
 404   _dbus_assert (path != NULL);
 405
 406   subtree = ensure_subtree (tree, path);
 407   if (subtree == NULL)
 408     {
 409       _DBUS_SET_OOM (error);
 410       return FALSE;
 411     }
 412
 413   if (subtree->message_function != NULL)
 414     {
 415       if (error != NULL)
 416         {
 417           char *complete_path = flatten_path (path);
 418
 419           dbus_set_error (error, DBUS_ERROR_OBJECT_PATH_IN_USE,
 420                           "A handler is already registered for %s",
 421                           complete_path ? complete_path
 422                                         : "(cannot represent path: out of memory!)");
 423
 424           dbus_free (complete_path);
 425         }
 426
 427       return FALSE;
 428     }
 429
 430   subtree->message_function = vtable->message_function;
 431   subtree->unregister_function = vtable->unregister_function;
 432   subtree->user_data = user_data;
 433   subtree->invoke_as_fallback = fallback != FALSE;
 434
 435   return TRUE;
 436 }
 437
 438 /**
 439  * Attempts to unregister the given subtree.  If the subtree is registered,
 440  * stores its unregister function and user data for later use and returns
 441  * #TRUE.  If subtree is not registered, simply returns #FALSE.  Does not free
 442  * subtree or remove it from the object tree.
 443  *
 444  * @param subtree the subtree to unregister
 445  * @param unregister_function_out stores subtree's unregister_function
 446  * @param user_data_out stores subtree's user_data
 447  * @return #FALSE if the subtree was not registered, #TRUE on success
 448  */
 449 static dbus_bool_t
 450 unregister_subtree (DBusObjectSubtree                 *subtree,
 451                     DBusObjectPathUnregisterFunction  *unregister_function_out,
 452                     void                             **user_data_out)
 453 {
 454   _dbus_assert (subtree != NULL);
 455   _dbus_assert (unregister_function_out != NULL);
 456   _dbus_assert (user_data_out != NULL);
 457
 458   /* Confirm subtree is registered */
 459   if (subtree->message_function != NULL)
 460     {
 461       subtree->message_function = NULL;
 462
 463       *unregister_function_out = subtree->unregister_function;
 464       *user_data_out = subtree->user_data;
 465
 466       subtree->unregister_function = NULL;
 467       subtree->user_data = NULL;
 468
 469       return TRUE;
 470     }
 471   else
 472     {
 473       /* Assert that this unregistered subtree is either the root node or has
 474          children, otherwise we have a dangling path which should never
 475          happen */
 476       _dbus_assert (subtree->parent == NULL || subtree->n_subtrees > 0);
 477
 478       /* The subtree is not registered */
 479       return FALSE;
 480     }
 481 }
 482
 483 /**
 484  * Attempts to remove a child subtree from its parent.  If removal is
 485  * successful, also frees the child.  Returns #TRUE on success, #FALSE
 486  * otherwise.  A #FALSE return value tells unregister_and_free_path_recurse to
 487  * stop attempting to remove ancestors, i.e., that no ancestors of the
 488  * specified child are eligible for removal.
 489  *
 490  * @param parent parent from which to remove child
 491  * @param child_index parent->subtrees index of child to remove
 492  * @return #TRUE if removal and free succeed, #FALSE otherwise
 493  */
 494 static dbus_bool_t
 495 attempt_child_removal (DBusObjectSubtree  *parent,
 496                        int child_index)
 497 {
 498   /* Candidate for removal */
 499   DBusObjectSubtree* candidate;
 500
 501   _dbus_assert (parent != NULL);
 502   _dbus_assert (child_index >= 0 && child_index < parent->n_subtrees);
 503
 504   candidate = parent->subtrees[child_index];
 505   _dbus_assert (candidate != NULL);
 506
 507   if (candidate->n_subtrees == 0 && candidate->message_function == NULL)
 508     {
 509       /* The candidate node is childless and is not a registered
 510          path, so... */
 511
 512       /* ... remove it from its parent... */
 513       /* Assumes a 0-byte memmove is OK */
 514       memmove (&parent->subtrees[child_index],
 515                &parent->subtrees[child_index + 1],
 516                (parent->n_subtrees - child_index - 1)
 517                * sizeof (parent->subtrees[0]));
 518       parent->n_subtrees -= 1;
 519
 520       /* ... and free it */
 521       candidate->parent = NULL;
 522       _dbus_object_subtree_unref (candidate);
 523
 524       return TRUE;
 525     }
 526   return FALSE;
 527 }
 528
 529 /**
 530  * Searches the object tree for a registered subtree node at the given path.
 531  * If a registered node is found, it is removed from the tree and freed, and
 532  * TRUE is returned.  If a registered subtree node is not found at the given
 533  * path, the tree is not modified and FALSE is returned.
 534  *
 535  * The found node's unregister_function and user_data are returned in the
 536  * corresponding _out arguments.  The caller should define these variables and
 537  * pass their addresses as arguments.
 538  *
 539  * Likewise, the caller should define and set to TRUE a boolean variable, then
 540  * pass its address as the continue_removal_attempts argument.
 541  *
 542  * Once a matching registered node is found, removed and freed, the recursive
 543  * return path is traversed.  Along the way, eligible ancestor nodes are
 544  * removed and freed.  An ancestor node is eligible for removal if and only if
 545  * 1) it has no children, i.e., it has become childless and 2) it is not itself
 546  * a registered handler.
 547  *
 548  * For example, suppose /A/B and /A/C are registered paths, and that these are
 549  * the only paths in the tree.  If B is removed and freed, C is still reachable
 550  * through A, so A cannot be removed and freed.  If C is subsequently removed
 551  * and freed, then A becomes a childless node and it becomes eligible for
 552  * removal, and will be removed and freed.
 553  *
 554  * Similarly, suppose /A is a registered path, and /A/B is also a registered
 555  * path, and that these are the only paths in the tree.  If B is removed and
 556  * freed, then even though A has become childless, it can't be freed because it
 557  * refers to a path that is still registered.
 558  *
 559  * @param subtree subtree from which to start the search, root for initial call
 560  * @param path path to subtree (same as _dbus_object_tree_unregister_and_unlock)
 561  * @param continue_removal_attempts pointer to a bool, #TRUE for initial call
 562  * @param unregister_function_out returns the found node's unregister_function
 563  * @param user_data_out returns the found node's user_data
 564  * @returns #TRUE if a registered node was found at path, #FALSE otherwise
 565  */
 566 static dbus_bool_t
 567 unregister_and_free_path_recurse
 568 (DBusObjectSubtree                 *subtree,
 569  const char                       **path,
 570  dbus_bool_t                       *continue_removal_attempts,
 571  DBusObjectPathUnregisterFunction  *unregister_function_out,
 572  void                             **user_data_out)
 573 {
 574   int i, j;
 575
 576   _dbus_assert (continue_removal_attempts != NULL);
 577   _dbus_assert (*continue_removal_attempts);
 578   _dbus_assert (unregister_function_out != NULL);
 579   _dbus_assert (user_data_out != NULL);
 580
 581   if (path[0] == NULL)
 582     return unregister_subtree (subtree, unregister_function_out, user_data_out);
 583
 584   i = 0;
 585   j = subtree->n_subtrees;
 586   while (i < j)
 587     {
 588       int k, v;
 589
 590       k = (i + j) / 2;
 591       v = strcmp (path[0], subtree->subtrees[k]->name);
 592
 593       if (v == 0)
 594         {
 595           dbus_bool_t freed;
 596           freed = unregister_and_free_path_recurse (subtree->subtrees[k],
 597                                                     &path[1],
 598                                                     continue_removal_attempts,
 599                                                     unregister_function_out,
 600                                                     user_data_out);
 601           if (freed && *continue_removal_attempts)
 602             *continue_removal_attempts = attempt_child_removal (subtree, k);
 603           return freed;
 604         }
 605       else if (v < 0)
 606         {
 607           j = k;
 608         }
 609       else
 610         {
 611           i = k + 1;
 612         }
 613     }
 614   return FALSE;
 615 }
 616
 617 /**
 618  * Unregisters an object subtree that was registered with the
 619  * same path.
 620  *
 621  * @param tree the global object tree
 622  * @param path path to the subtree (same as the one passed to _dbus_object_tree_register())
 623  */
 624 void
 625 _dbus_object_tree_unregister_and_unlock (DBusObjectTree          *tree,
 626                                          const char             **path)
 627 {
 628   dbus_bool_t found_subtree;
 629   dbus_bool_t continue_removal_attempts;
 630   DBusObjectPathUnregisterFunction unregister_function;
 631   void *user_data;
 632   DBusConnection *connection;
 633
 634   _dbus_assert (tree != NULL);
 635   _dbus_assert (path != NULL);
 636
 637   continue_removal_attempts = TRUE;
 638   unregister_function = NULL;
 639   user_data = NULL;
 640
 641   found_subtree = unregister_and_free_path_recurse (tree->root,
 642                                                     path,
 643                                                     &continue_removal_attempts,
 644                                                     &unregister_function,
 645                                                     &user_data);
 646
 647 #ifndef DBUS_DISABLE_CHECKS
 648   if (found_subtree == FALSE)
 649     {
 650       _dbus_warn ("Attempted to unregister path (path[0] = %s path[1] = %s) which isn't registered",
 651                   path[0] ? path[0] : "null",
 652                   (path[0] && path[1]) ? path[1] : "null");
 653       goto unlock;
 654     }
 655 #else
 656   _dbus_assert (found_subtree == TRUE);
 657 #endif
 658
 659 unlock:
 660   connection = tree->connection;
 661
 662   /* Unlock and call application code */
 663 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 664   if (connection)
 665 #endif
 666     {
 667       _dbus_connection_ref_unlocked (connection);
 668       _dbus_verbose ("unlock\n");
 669       _dbus_connection_unlock (connection);
 670     }
 671
 672   if (unregister_function)
 673     (* unregister_function) (connection, user_data);
 674
 675 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 676   if (connection)
 677 #endif
 678     dbus_connection_unref (connection);
 679 }
 680
 681 static void
 682 free_subtree_recurse (DBusConnection    *connection,
 683                       DBusObjectSubtree *subtree)
 684 {
 685   /* Delete them from the end, for slightly
 686    * more robustness against odd reentrancy.
 687    */
 688   while (subtree->n_subtrees > 0)
 689     {
 690       DBusObjectSubtree *child;
 691
 692       child = subtree->subtrees[subtree->n_subtrees - 1];
 693       subtree->subtrees[subtree->n_subtrees - 1] = NULL;
 694       subtree->n_subtrees -= 1;
 695       child->parent = NULL;
 696
 697       free_subtree_recurse (connection, child);
 698     }
 699
 700   /* Call application code */
 701   if (subtree->unregister_function)
 702     (* subtree->unregister_function) (connection,
 703                                       subtree->user_data);
 704
 705   subtree->message_function = NULL;
 706   subtree->unregister_function = NULL;
 707   subtree->user_data = NULL;
 708
 709   /* Now free ourselves */
 710   _dbus_object_subtree_unref (subtree);
 711 }
 712
 713 /**
 714  * Free all the handlers in the tree. Lock on tree's connection
 715  * must not be held.
 716  *
 717  * @param tree the object tree
 718  */
 719 void
 720 _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree)
 721 {
 722   if (tree->root)
 723     free_subtree_recurse (tree->connection,
 724                           tree->root);
 725   tree->root = NULL;
 726 }
 727
 728 static dbus_bool_t
 729 _dbus_object_tree_list_registered_unlocked (DBusObjectTree *tree,
 730                                             const char    **parent_path,
 731                                             char         ***child_entries)
 732 {
 733   DBusObjectSubtree *subtree;
 734   char **retval;
 735
 736   _dbus_assert (parent_path != NULL);
 737   _dbus_assert (child_entries != NULL);
 738
 739   *child_entries = NULL;
 740
 741   subtree = lookup_subtree (tree, parent_path);
 742   if (subtree == NULL)
 743     {
 744       retval = dbus_new0 (char *, 1);
 745     }
 746   else
 747     {
 748       int i;
 749       retval = dbus_new0 (char*, subtree->n_subtrees + 1);
 750       if (retval == NULL)
 751         goto out;
 752       i = 0;
 753       while (i < subtree->n_subtrees)
 754         {
 755           retval[i] = _dbus_strdup (subtree->subtrees[i]->name);
 756           if (retval[i] == NULL)
 757             {
 758               dbus_free_string_array (retval);
 759               retval = NULL;
 760               goto out;
 761             }
 762           ++i;
 763         }
 764     }
 765
 766  out:
 767
 768   *child_entries = retval;
 769   return retval != NULL;
 770 }
 771
 772 static DBusHandlerResult
 773 handle_default_introspect_and_unlock (DBusObjectTree          *tree,
 774                                       DBusMessage             *message,
 775                                       const char             **path)
 776 {
 777   DBusString xml;
 778   DBusHandlerResult result;
 779   char **children;
 780   int i;
 781   DBusMessage *reply;
 782   DBusMessageIter iter;
 783   const char *v_STRING;
 784   dbus_bool_t already_unlocked;
 785
 786   /* We have the connection lock here */
 787
 788   already_unlocked = FALSE;
 789
 790   _dbus_verbose (" considering default Introspect() handler...\n");
 791
 792   reply = NULL;
 793
 794   if (!dbus_message_is_method_call (message,
 795                                     DBUS_INTERFACE_INTROSPECTABLE,
 796                                     "Introspect"))
 797     {
 798 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 799       if (tree->connection)
 800 #endif
 801         {
 802           _dbus_verbose ("unlock\n");
 803           _dbus_connection_unlock (tree->connection);
 804         }
 805
 806       return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
 807     }
 808
 809   _dbus_verbose (" using default Introspect() handler!\n");
 810
 811   if (!_dbus_string_init (&xml))
 812     {
 813 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 814       if (tree->connection)
 815 #endif
 816         {
 817           _dbus_verbose ("unlock\n");
 818           _dbus_connection_unlock (tree->connection);
 819         }
 820
 821       return DBUS_HANDLER_RESULT_NEED_MEMORY;
 822     }
 823
 824   result = DBUS_HANDLER_RESULT_NEED_MEMORY;
 825
 826   children = NULL;
 827   if (!_dbus_object_tree_list_registered_unlocked (tree, path, &children))
 828     goto out;
 829
 830   if (!_dbus_string_append (&xml, DBUS_INTROSPECT_1_0_XML_DOCTYPE_DECL_NODE))
 831     goto out;
 832
 833   if (!_dbus_string_append (&xml, "<node>\n"))
 834     goto out;
 835
 836   i = 0;
 837   while (children[i] != NULL)
 838     {
 839       if (!_dbus_string_append_printf (&xml, "  <node name=\"%s\"/>\n",
 840                                        children[i]))
 841         goto out;
 842
 843       ++i;
 844     }
 845
 846   if (!_dbus_string_append (&xml, "</node>\n"))
 847     goto out;
 848
 849   reply = dbus_message_new_method_return (message);
 850   if (reply == NULL)
 851     goto out;
 852
 853   dbus_message_iter_init_append (reply, &iter);
 854   v_STRING = _dbus_string_get_const_data (&xml);
 855   if (!dbus_message_iter_append_basic (&iter, DBUS_TYPE_STRING, &v_STRING))
 856     goto out;
 857
 858 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 859   if (tree->connection)
 860 #endif
 861     {
 862       already_unlocked = TRUE;
 863
 864       if (!_dbus_connection_send_and_unlock (tree->connection, reply, NULL))
 865         goto out;
 866     }
 867
 868   result = DBUS_HANDLER_RESULT_HANDLED;
 869
 870  out:
 871 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 872   if (tree->connection)
 873 #endif
 874     {
 875       if (!already_unlocked)
 876         {
 877           _dbus_verbose ("unlock\n");
 878           _dbus_connection_unlock (tree->connection);
 879         }
 880     }
 881
 882   _dbus_string_free (&xml);
 883   dbus_free_string_array (children);
 884   if (reply)
 885     dbus_message_unref (reply);
 886
 887   return result;
 888 }
 889
 890 /**
 891  * Tries to dispatch a message by directing it to handler for the
 892  * object path listed in the message header, if any. Messages are
 893  * dispatched first to the registered handler that matches the largest
 894  * number of path elements; that is, message to /foo/bar/baz would go
 895  * to the handler for /foo/bar before the one for /foo.
 896  *
 897  * @todo thread problems
 898  *
 899  * @param tree the global object tree
 900  * @param message the message to dispatch
 901  * @param found_object return location for the object
 902  * @returns whether message was handled successfully
 903  */
 904 DBusHandlerResult
 905 _dbus_object_tree_dispatch_and_unlock (DBusObjectTree          *tree,
 906                                        DBusMessage             *message,
 907                                        dbus_bool_t             *found_object)
 908 {
 909   char **path;
 910   dbus_bool_t exact_match;
 911   DBusList *list;
 912   DBusList *link;
 913   DBusHandlerResult result;
 914   DBusObjectSubtree *subtree;
 915
 916 #if 0
 917   _dbus_verbose ("Dispatch of message by object path\n");
 918 #endif
 919
 920   path = NULL;
 921   if (!dbus_message_get_path_decomposed (message, &path))
 922     {
 923 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 924       if (tree->connection)
 925 #endif
 926         {
 927           _dbus_verbose ("unlock\n");
 928           _dbus_connection_unlock (tree->connection);
 929         }
 930
 931       _dbus_verbose ("No memory to get decomposed path\n");
 932
 933       return DBUS_HANDLER_RESULT_NEED_MEMORY;
 934     }
 935
 936   if (path == NULL)
 937     {
 938 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
 939       if (tree->connection)
 940 #endif
 941         {
 942           _dbus_verbose ("unlock\n");
 943           _dbus_connection_unlock (tree->connection);
 944         }
 945
 946       _dbus_verbose ("No path field in message\n");
 947       return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
 948     }
 949
 950   /* Find the deepest path that covers the path in the message */
 951   subtree = find_handler (tree, (const char**) path, &exact_match);
 952
 953   if (found_object)
 954     *found_object = !!subtree;
 955
 956   /* Build a list of all paths that cover the path in the message */
 957
 958   list = NULL;
 959
 960   while (subtree != NULL)
 961     {
 962       if (subtree->message_function != NULL && (exact_match || subtree->invoke_as_fallback))
 963         {
 964           _dbus_object_subtree_ref (subtree);
 965
 966           /* run deepest paths first */
 967           if (!_dbus_list_append (&list, subtree))
 968             {
 969               result = DBUS_HANDLER_RESULT_NEED_MEMORY;
 970               _dbus_object_subtree_unref (subtree);
 971               goto free_and_return;
 972             }
 973         }
 974
 975       exact_match = FALSE;
 976       subtree = subtree->parent;
 977     }
 978
 979   _dbus_verbose ("%d handlers in the path tree for this message\n",
 980                  _dbus_list_get_length (&list));
 981
 982   /* Invoke each handler in the list */
 983
 984   result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
 985
 986   link = _dbus_list_get_first_link (&list);
 987   while (link != NULL)
 988     {
 989       DBusList *next = _dbus_list_get_next_link (&list, link);
 990       subtree = link->data;
 991
 992       /* message_function is NULL if we're unregistered
 993        * due to reentrancy
 994        */
 995       if (subtree->message_function)
 996         {
 997           DBusObjectPathMessageFunction message_function;
 998           void *user_data;
 999
1000           message_function = subtree->message_function;
1001           user_data = subtree->user_data;
1002
1003 #if 0
1004           _dbus_verbose ("  (invoking a handler)\n");
1005 #endif
1006
1007 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1008           if (tree->connection)
1009 #endif
1010             {
1011               _dbus_verbose ("unlock\n");
1012               _dbus_connection_unlock (tree->connection);
1013             }
1014
1015           /* FIXME you could unregister the subtree in another thread
1016            * before we invoke the callback, and I can't figure out a
1017            * good way to solve this.
1018            */
1019
1020           result = (* message_function) (tree->connection,
1021                                          message,
1022                                          user_data);
1023
1024 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1025           if (tree->connection)
1026 #endif
1027             _dbus_connection_lock (tree->connection);
1028
1029           if (result != DBUS_HANDLER_RESULT_NOT_YET_HANDLED)
1030             goto free_and_return;
1031         }
1032
1033       link = next;
1034     }
1035
1036  free_and_return:
1037
1038   if (result == DBUS_HANDLER_RESULT_NOT_YET_HANDLED)
1039     {
1040       /* This hardcoded default handler does a minimal Introspect()
1041        */
1042       result = handle_default_introspect_and_unlock (tree, message,
1043                                                      (const char**) path);
1044     }
1045   else
1046     {
1047 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1048       if (tree->connection)
1049 #endif
1050         {
1051           _dbus_verbose ("unlock\n");
1052           _dbus_connection_unlock (tree->connection);
1053         }
1054     }
1055
1056   while (list != NULL)
1057     {
1058       link = _dbus_list_get_first_link (&list);
1059       _dbus_object_subtree_unref (link->data);
1060       _dbus_list_remove_link (&list, link);
1061     }
1062
1063   dbus_free_string_array (path);
1064
1065   return result;
1066 }
1067
1068 /**
1069  * Looks up the data passed to _dbus_object_tree_register() for a
1070  * handler at the given path.
1071  *
1072  * @param tree the global object tree
1073  * @param path NULL-terminated array of path elements giving path to subtree
1074  * @returns the object's user_data or #NULL if none found
1075  */
1076 void*
1077 _dbus_object_tree_get_user_data_unlocked (DBusObjectTree *tree,
1078                                           const char    **path)
1079 {
1080   dbus_bool_t exact_match;
1081   DBusObjectSubtree *subtree;
1082
1083   _dbus_assert (tree != NULL);
1084   _dbus_assert (path != NULL);
1085
1086   /* Find the deepest path that covers the path in the message */
1087   subtree = find_handler (tree, (const char**) path, &exact_match);
1088
1089   if ((subtree == NULL) || !exact_match)
1090     {
1091       _dbus_verbose ("No object at specified path found\n");
1092       return NULL;
1093     }
1094
1095   return subtree->user_data;
1096 }
1097
1098 /**
1099  * Allocates a subtree object.
1100  *
1101  * @param name name to duplicate.
1102  * @returns newly-allocated subtree
1103  */
1104 static DBusObjectSubtree*
1105 allocate_subtree_object (const char *name)
1106 {
1107   int len;
1108   DBusObjectSubtree *subtree;
1109   const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, name);
1110
1111   _dbus_assert (name != NULL);
1112
1113   len = strlen (name);
1114
1115   subtree = dbus_malloc0 (MAX (front_padding + (len + 1), sizeof (DBusObjectSubtree)));
1116
1117   if (subtree == NULL)
1118     return NULL;
1119
1120   memcpy (subtree->name, name, len + 1);
1121
1122   return subtree;
1123 }
1124
1125 static DBusObjectSubtree*
1126 _dbus_object_subtree_new (const char                  *name,
1127                           const DBusObjectPathVTable  *vtable,
1128                           void                        *user_data)
1129 {
1130   DBusObjectSubtree *subtree;
1131
1132   subtree = allocate_subtree_object (name);
1133   if (subtree == NULL)
1134     goto oom;
1135
1136   _dbus_assert (name != NULL);
1137
1138   subtree->parent = NULL;
1139
1140   if (vtable)
1141     {
1142       subtree->message_function = vtable->message_function;
1143       subtree->unregister_function = vtable->unregister_function;
1144     }
1145   else
1146     {
1147       subtree->message_function = NULL;
1148       subtree->unregister_function = NULL;
1149     }
1150
1151   subtree->user_data = user_data;
1152   _dbus_atomic_inc (&subtree->refcount);
1153   subtree->subtrees = NULL;
1154   subtree->n_subtrees = 0;
1155   subtree->max_subtrees = 0;
1156   subtree->invoke_as_fallback = FALSE;
1157
1158   return subtree;
1159
1160  oom:
1161   return NULL;
1162 }
1163
1164 static DBusObjectSubtree *
1165 _dbus_object_subtree_ref (DBusObjectSubtree *subtree)
1166 {
1167 #ifdef DBUS_DISABLE_ASSERT
1168   _dbus_atomic_inc (&subtree->refcount);
1169 #else
1170   dbus_int32_t old_value;
1171
1172   old_value = _dbus_atomic_inc (&subtree->refcount);
1173   _dbus_assert (old_value > 0);
1174 #endif
1175
1176   return subtree;
1177 }
1178
1179 static void
1180 _dbus_object_subtree_unref (DBusObjectSubtree *subtree)
1181 {
1182   dbus_int32_t old_value;
1183
1184   old_value = _dbus_atomic_dec (&subtree->refcount);
1185   _dbus_assert (old_value > 0);
1186
1187   if (old_value == 1)
1188     {
1189       _dbus_assert (subtree->unregister_function == NULL);
1190       _dbus_assert (subtree->message_function == NULL);
1191
1192       dbus_free (subtree->subtrees);
1193       dbus_free (subtree);
1194     }
1195 }
1196
1197 /**
1198  * Lists the registered fallback handlers and object path handlers at
1199  * the given parent_path. The returned array should be freed with
1200  * dbus_free_string_array().
1201  *
1202  * @param tree the object tree
1203  * @param parent_path the path to list the child handlers of
1204  * @param child_entries returns #NULL-terminated array of children
1205  * @returns #FALSE if no memory to allocate the child entries
1206  */
1207 dbus_bool_t
1208 _dbus_object_tree_list_registered_and_unlock (DBusObjectTree *tree,
1209                                               const char    **parent_path,
1210                                               char         ***child_entries)
1211 {
1212   dbus_bool_t result;
1213
1214   result = _dbus_object_tree_list_registered_unlocked (tree,
1215                                                        parent_path,
1216                                                        child_entries);
1217
1218 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1219   if (tree->connection)
1220 #endif
1221     {
1222       _dbus_verbose ("unlock\n");
1223       _dbus_connection_unlock (tree->connection);
1224     }
1225
1226   return result;
1227 }
1228
1229
1230 /** Set to 1 to get a bunch of spew about disassembling the path string */
1231 #define VERBOSE_DECOMPOSE 0
1232
1233 /**
1234  * Decompose an object path.  A path of just "/" is
1235  * represented as an empty vector of strings.
1236  * The path need not be nul terminated.
1237  *
1238  * @param data the path data
1239  * @param len  the length of the path string
1240  * @param path address to store new object path
1241  * @param path_len length of stored path
1242  */
1243 dbus_bool_t
1244 _dbus_decompose_path (const char*     data,
1245                       int             len,
1246                       char         ***path,
1247                       int            *path_len)
1248 {
1249   char **retval;
1250   int n_components;
1251   int i, j, comp;
1252
1253   _dbus_assert (data != NULL);
1254   _dbus_assert (path != NULL);
1255
1256 #if VERBOSE_DECOMPOSE
1257   _dbus_verbose ("Decomposing path \"%s\"\n",
1258                  data);
1259 #endif
1260
1261   n_components = 0;
1262   if (len > 1) /* if path is not just "/" */
1263     {
1264       i = 0;
1265       while (i < len)
1266         {
1267           _dbus_assert (data[i] != '\0');
1268           if (data[i] == '/')
1269             n_components += 1;
1270           ++i;
1271         }
1272     }
1273
1274   retval = dbus_new0 (char*, n_components + 1);
1275
1276   if (retval == NULL)
1277     return FALSE;
1278
1279   comp = 0;
1280   if (n_components == 0)
1281     i = 1;
1282   else
1283     i = 0;
1284   while (comp < n_components)
1285     {
1286       _dbus_assert (i < len);
1287
1288       if (data[i] == '/')
1289         ++i;
1290       j = i;
1291
1292       while (j < len && data[j] != '/')
1293         ++j;
1294
1295       /* Now [i, j) is the path component */
1296       _dbus_assert (i < j);
1297       _dbus_assert (data[i] != '/');
1298       _dbus_assert (j == len || data[j] == '/');
1299
1300 #if VERBOSE_DECOMPOSE
1301       _dbus_verbose ("  (component in [%d,%d))\n",
1302                      i, j);
1303 #endif
1304
1305       retval[comp] = _dbus_memdup (&data[i], j - i + 1);
1306       if (retval[comp] == NULL)
1307         {
1308           dbus_free_string_array (retval);
1309           return FALSE;
1310         }
1311       retval[comp][j-i] = '\0';
1312 #if VERBOSE_DECOMPOSE
1313       _dbus_verbose ("  (component %d = \"%s\")\n",
1314                      comp, retval[comp]);
1315 #endif
1316
1317       ++comp;
1318       i = j;
1319     }
1320   _dbus_assert (i == len);
1321
1322   *path = retval;
1323   if (path_len)
1324     *path_len = n_components;
1325
1326   return TRUE;
1327 }
1328
1329 /** @} */
1330
1331 static char*
1332 flatten_path (const char **path)
1333 {
1334   DBusString str;
1335   char *s;
1336
1337   if (!_dbus_string_init (&str))
1338     return NULL;
1339
1340   if (path[0] == NULL)
1341     {
1342       if (!_dbus_string_append_byte (&str, '/'))
1343         goto nomem;
1344     }
1345   else
1346     {
1347       int i;
1348
1349       i = 0;
1350       while (path[i])
1351         {
1352           if (!_dbus_string_append_byte (&str, '/'))
1353             goto nomem;
1354
1355           if (!_dbus_string_append (&str, path[i]))
1356             goto nomem;
1357
1358           ++i;
1359         }
1360     }
1361
1362   if (!_dbus_string_steal_data (&str, &s))
1363     goto nomem;
1364
1365   _dbus_string_free (&str);
1366
1367   return s;
1368
1369  nomem:
1370   _dbus_string_free (&str);
1371   return NULL;
1372 }
1373
1374
1375 #ifdef DBUS_ENABLE_EMBEDDED_TESTS
1376
1377 #ifndef DOXYGEN_SHOULD_SKIP_THIS
1378
1379 #include "dbus-test.h"
1380 #include <stdio.h>
1381
1382 typedef enum
1383 {
1384   STR_EQUAL,
1385   STR_PREFIX,
1386   STR_DIFFERENT
1387 } StrComparison;
1388
1389 /* Returns TRUE if container is a parent of child
1390  */
1391 static StrComparison
1392 path_contains (const char **container,
1393                const char **child)
1394 {
1395   int i;
1396
1397   i = 0;
1398   while (child[i] != NULL)
1399     {
1400       int v;
1401
1402       if (container[i] == NULL)
1403         return STR_PREFIX; /* container ran out, child continues;
1404                             * thus the container is a parent of the
1405                             * child.
1406                             */
1407
1408       _dbus_assert (container[i] != NULL);
1409       _dbus_assert (child[i] != NULL);
1410
1411       v = strcmp (container[i], child[i]);
1412
1413       if (v != 0)
1414         return STR_DIFFERENT; /* they overlap until here and then are different,
1415                                * not overlapping
1416                                */
1417
1418       ++i;
1419     }
1420
1421   /* Child ran out; if container also did, they are equal;
1422    * otherwise, the child is a parent of the container.
1423    */
1424   if (container[i] == NULL)
1425     return STR_EQUAL;
1426   else
1427     return STR_DIFFERENT;
1428 }
1429
1430 #if 0
1431 static void
1432 spew_subtree_recurse (DBusObjectSubtree *subtree,
1433                       int                indent)
1434 {
1435   int i;
1436
1437   i = 0;
1438   while (i < indent)
1439     {
1440       _dbus_verbose (" ");
1441       ++i;
1442     }
1443
1444   _dbus_verbose ("%s (%d children)\n",
1445                  subtree->name, subtree->n_subtrees);
1446
1447   i = 0;
1448   while (i < subtree->n_subtrees)
1449     {
1450       spew_subtree_recurse (subtree->subtrees[i], indent + 2);
1451
1452       ++i;
1453     }
1454 }
1455
1456 static void
1457 spew_tree (DBusObjectTree *tree)
1458 {
1459   spew_subtree_recurse (tree->root, 0);
1460 }
1461 #endif
1462
1463 /**
1464  * Callback data used in tests
1465  */
1466 typedef struct
1467 {
1468   const char **path; /**< Path */
1469   dbus_bool_t handler_fallback; /**< true if the handler may be called as fallback */
1470   dbus_bool_t message_handled; /**< Gets set to true if message handler called */
1471   dbus_bool_t handler_unregistered; /**< gets set to true if handler is unregistered */
1472 } TreeTestData;
1473
1474
1475 static void
1476 test_unregister_function (DBusConnection  *connection,
1477                           void            *user_data)
1478 {
1479   TreeTestData *ttd = user_data;
1480
1481   ttd->handler_unregistered = TRUE;
1482 }
1483
1484 static DBusHandlerResult
1485 test_message_function (DBusConnection  *connection,
1486                        DBusMessage     *message,
1487                        void            *user_data)
1488 {
1489   TreeTestData *ttd = user_data;
1490
1491   ttd->message_handled = TRUE;
1492
1493   return DBUS_HANDLER_RESULT_NOT_YET_HANDLED;
1494 }
1495
1496 static dbus_bool_t
1497 do_register (DBusObjectTree *tree,
1498              const char    **path,
1499              dbus_bool_t     fallback,
1500              int             i,
1501              TreeTestData   *tree_test_data)
1502 {
1503   DBusObjectPathVTable vtable = { test_unregister_function,
1504                                   test_message_function, NULL };
1505
1506   tree_test_data[i].message_handled = FALSE;
1507   tree_test_data[i].handler_unregistered = FALSE;
1508   tree_test_data[i].handler_fallback = fallback;
1509   tree_test_data[i].path = path;
1510
1511   if (!_dbus_object_tree_register (tree, fallback, path,
1512                                    &vtable,
1513                                    &tree_test_data[i],
1514                                    NULL))
1515     return FALSE;
1516
1517   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path) ==
1518                 &tree_test_data[i]);
1519
1520   return TRUE;
1521 }
1522
1523 static dbus_bool_t
1524 do_test_dispatch (DBusObjectTree *tree,
1525                   const char    **path,
1526                   int             i,
1527                   TreeTestData   *tree_test_data,
1528                   int             n_test_data)
1529 {
1530   DBusMessage *message;
1531   int j;
1532   DBusHandlerResult result;
1533   char *flat;
1534
1535   message = NULL;
1536
1537   flat = flatten_path (path);
1538   if (flat == NULL)
1539     goto oom;
1540
1541   message = dbus_message_new_method_call (NULL,
1542                                           flat,
1543                                           "org.freedesktop.TestInterface",
1544                                           "Foo");
1545   dbus_free (flat);
1546   if (message == NULL)
1547     goto oom;
1548
1549   j = 0;
1550   while (j < n_test_data)
1551     {
1552       tree_test_data[j].message_handled = FALSE;
1553       ++j;
1554     }
1555
1556   result = _dbus_object_tree_dispatch_and_unlock (tree, message, NULL);
1557   if (result == DBUS_HANDLER_RESULT_NEED_MEMORY)
1558     goto oom;
1559
1560   _dbus_assert (tree_test_data[i].message_handled);
1561
1562   j = 0;
1563   while (j < n_test_data)
1564     {
1565       if (tree_test_data[j].message_handled)
1566         {
1567           if (tree_test_data[j].handler_fallback)
1568             _dbus_assert (path_contains (tree_test_data[j].path,
1569                                          path) != STR_DIFFERENT);
1570           else
1571             _dbus_assert (path_contains (tree_test_data[j].path, path) == STR_EQUAL);
1572         }
1573       else
1574         {
1575           if (tree_test_data[j].handler_fallback)
1576             _dbus_assert (path_contains (tree_test_data[j].path,
1577                                          path) == STR_DIFFERENT);
1578           else
1579             _dbus_assert (path_contains (tree_test_data[j].path, path) != STR_EQUAL);
1580         }
1581
1582       ++j;
1583     }
1584
1585   dbus_message_unref (message);
1586
1587   return TRUE;
1588
1589  oom:
1590   if (message)
1591     dbus_message_unref (message);
1592   return FALSE;
1593 }
1594
1595 typedef struct
1596 {
1597   const char *path;
1598   const char *result[20];
1599 } DecomposePathTest;
1600
1601 static DecomposePathTest decompose_tests[] = {
1602   { "/foo", { "foo", NULL } },
1603   { "/foo/bar", { "foo", "bar", NULL } },
1604   { "/", { NULL } },
1605   { "/a/b", { "a", "b", NULL } },
1606   { "/a/b/c", { "a", "b", "c", NULL } },
1607   { "/a/b/c/d", { "a", "b", "c", "d", NULL } },
1608   { "/foo/bar/q", { "foo", "bar", "q", NULL } },
1609   { "/foo/bar/this/is/longer", { "foo", "bar", "this", "is", "longer", NULL } }
1610 };
1611
1612 /* Return TRUE on success, FALSE on OOM, die with an assertion failure
1613  * on failure. */
1614 static dbus_bool_t
1615 run_decompose_tests (void)
1616 {
1617   int i;
1618
1619   i = 0;
1620   while (i < _DBUS_N_ELEMENTS (decompose_tests))
1621     {
1622       char **result;
1623       int    result_len;
1624       int    expected_len;
1625
1626       if (!_dbus_decompose_path (decompose_tests[i].path,
1627                                  strlen (decompose_tests[i].path),
1628                                  &result, &result_len))
1629         return FALSE;
1630
1631       expected_len = _dbus_string_array_length (decompose_tests[i].result);
1632
1633       if (result_len != (int) _dbus_string_array_length ((const char**)result) ||
1634           expected_len != result_len ||
1635           path_contains (decompose_tests[i].result,
1636                          (const char**) result) != STR_EQUAL)
1637         {
1638           int real_len = _dbus_string_array_length ((const char**)result);
1639           _dbus_warn ("Expected decompose of %s to have len %d, returned %d, appears to have %d",
1640                       decompose_tests[i].path, expected_len, result_len,
1641                       real_len);
1642           _dbus_warn ("Decompose resulted in elements: { ");
1643           i = 0;
1644           while (i < real_len)
1645             {
1646               _dbus_warn ("\"%s\"%s", result[i],
1647                           (i + 1) == real_len ? "" : ", ");
1648               ++i;
1649             }
1650           _dbus_warn ("}");
1651           _dbus_assert_not_reached ("path decompose failed");
1652         }
1653
1654       dbus_free_string_array (result);
1655
1656       ++i;
1657     }
1658
1659   return TRUE;
1660 }
1661
1662 static DBusObjectSubtree*
1663 find_subtree_registered_or_unregistered (DBusObjectTree *tree,
1664                                          const char    **path)
1665 {
1666 #if VERBOSE_FIND
1667   _dbus_verbose ("Looking for exact subtree, registered or unregistered\n");
1668 #endif
1669
1670   return find_subtree_recurse (tree->root, path, FALSE, NULL, NULL);
1671 }
1672
1673 /* Returns TRUE if the right thing happens, but the right thing might
1674  * be OOM. */
1675 static dbus_bool_t
1676 object_tree_test_iteration (void *data)
1677 {
1678   const char *path0[] = { NULL };
1679   const char *path1[] = { "foo", NULL };
1680   const char *path2[] = { "foo", "bar", NULL };
1681   const char *path3[] = { "foo", "bar", "baz", NULL };
1682   const char *path4[] = { "foo", "bar", "boo", NULL };
1683   const char *path5[] = { "blah", NULL };
1684   const char *path6[] = { "blah", "boof", NULL };
1685   const char *path7[] = { "blah", "boof", "this", "is", "really", "long", NULL };
1686   const char *path8[] = { "childless", NULL };
1687   const char *path9[] = { "blah", "a", NULL };
1688   const char *path10[] = { "blah", "b", NULL };
1689   const char *path11[] = { "blah", "c", NULL };
1690   const char *path12[] = { "blah", "a", "d", NULL };
1691   const char *path13[] = { "blah", "b", "d", NULL };
1692   const char *path14[] = { "blah", "c", "d", NULL };
1693   DBusObjectPathVTable test_vtable = { NULL, test_message_function, NULL };
1694   DBusObjectTree *tree;
1695   TreeTestData tree_test_data[9];
1696   int i;
1697   dbus_bool_t exact_match;
1698
1699   if (!run_decompose_tests ())
1700     return TRUE; /* OOM is OK */
1701
1702   tree = NULL;
1703
1704   tree = _dbus_object_tree_new (NULL);
1705   if (tree == NULL)
1706     goto out;
1707
1708   if (!do_register (tree, path0, TRUE, 0, tree_test_data))
1709     goto out;
1710
1711   _dbus_assert (find_subtree (tree, path0, NULL));
1712   _dbus_assert (!find_subtree (tree, path1, NULL));
1713   _dbus_assert (!find_subtree (tree, path2, NULL));
1714   _dbus_assert (!find_subtree (tree, path3, NULL));
1715   _dbus_assert (!find_subtree (tree, path4, NULL));
1716   _dbus_assert (!find_subtree (tree, path5, NULL));
1717   _dbus_assert (!find_subtree (tree, path6, NULL));
1718   _dbus_assert (!find_subtree (tree, path7, NULL));
1719   _dbus_assert (!find_subtree (tree, path8, NULL));
1720
1721   _dbus_assert (find_handler (tree, path0, &exact_match) && exact_match);
1722   _dbus_assert (find_handler (tree, path1, &exact_match) == tree->root && !exact_match);
1723   _dbus_assert (find_handler (tree, path2, &exact_match) == tree->root && !exact_match);
1724   _dbus_assert (find_handler (tree, path3, &exact_match) == tree->root && !exact_match);
1725   _dbus_assert (find_handler (tree, path4, &exact_match) == tree->root && !exact_match);
1726   _dbus_assert (find_handler (tree, path5, &exact_match) == tree->root && !exact_match);
1727   _dbus_assert (find_handler (tree, path6, &exact_match) == tree->root && !exact_match);
1728   _dbus_assert (find_handler (tree, path7, &exact_match) == tree->root && !exact_match);
1729   _dbus_assert (find_handler (tree, path8, &exact_match) == tree->root && !exact_match);
1730
1731   if (!do_register (tree, path1, TRUE, 1, tree_test_data))
1732     goto out;
1733
1734   _dbus_assert (find_subtree (tree, path0, NULL));
1735   _dbus_assert (find_subtree (tree, path1, NULL));
1736   _dbus_assert (!find_subtree (tree, path2, NULL));
1737   _dbus_assert (!find_subtree (tree, path3, NULL));
1738   _dbus_assert (!find_subtree (tree, path4, NULL));
1739   _dbus_assert (!find_subtree (tree, path5, NULL));
1740   _dbus_assert (!find_subtree (tree, path6, NULL));
1741   _dbus_assert (!find_subtree (tree, path7, NULL));
1742   _dbus_assert (!find_subtree (tree, path8, NULL));
1743
1744   _dbus_assert (find_handler (tree, path0, &exact_match) &&  exact_match);
1745   _dbus_assert (find_handler (tree, path1, &exact_match) &&  exact_match);
1746   _dbus_assert (find_handler (tree, path2, &exact_match) && !exact_match);
1747   _dbus_assert (find_handler (tree, path3, &exact_match) && !exact_match);
1748   _dbus_assert (find_handler (tree, path4, &exact_match) && !exact_match);
1749   _dbus_assert (find_handler (tree, path5, &exact_match) == tree->root && !exact_match);
1750   _dbus_assert (find_handler (tree, path6, &exact_match) == tree->root && !exact_match);
1751   _dbus_assert (find_handler (tree, path7, &exact_match) == tree->root && !exact_match);
1752   _dbus_assert (find_handler (tree, path8, &exact_match) == tree->root && !exact_match);
1753
1754   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
1755     goto out;
1756
1757   _dbus_assert (find_subtree (tree, path1, NULL));
1758   _dbus_assert (find_subtree (tree, path2, NULL));
1759   _dbus_assert (!find_subtree (tree, path3, NULL));
1760   _dbus_assert (!find_subtree (tree, path4, NULL));
1761   _dbus_assert (!find_subtree (tree, path5, NULL));
1762   _dbus_assert (!find_subtree (tree, path6, NULL));
1763   _dbus_assert (!find_subtree (tree, path7, NULL));
1764   _dbus_assert (!find_subtree (tree, path8, NULL));
1765
1766   if (!do_register (tree, path3, TRUE, 3, tree_test_data))
1767     goto out;
1768
1769   _dbus_assert (find_subtree (tree, path0, NULL));
1770   _dbus_assert (find_subtree (tree, path1, NULL));
1771   _dbus_assert (find_subtree (tree, path2, NULL));
1772   _dbus_assert (find_subtree (tree, path3, NULL));
1773   _dbus_assert (!find_subtree (tree, path4, NULL));
1774   _dbus_assert (!find_subtree (tree, path5, NULL));
1775   _dbus_assert (!find_subtree (tree, path6, NULL));
1776   _dbus_assert (!find_subtree (tree, path7, NULL));
1777   _dbus_assert (!find_subtree (tree, path8, NULL));
1778
1779   if (!do_register (tree, path4, TRUE, 4, tree_test_data))
1780     goto out;
1781
1782   _dbus_assert (find_subtree (tree, path0, NULL));
1783   _dbus_assert (find_subtree (tree, path1, NULL));
1784   _dbus_assert (find_subtree (tree, path2, NULL));
1785   _dbus_assert (find_subtree (tree, path3, NULL));
1786   _dbus_assert (find_subtree (tree, path4, NULL));
1787   _dbus_assert (!find_subtree (tree, path5, NULL));
1788   _dbus_assert (!find_subtree (tree, path6, NULL));
1789   _dbus_assert (!find_subtree (tree, path7, NULL));
1790   _dbus_assert (!find_subtree (tree, path8, NULL));
1791
1792   if (!do_register (tree, path5, TRUE, 5, tree_test_data))
1793     goto out;
1794
1795   _dbus_assert (find_subtree (tree, path0, NULL));
1796   _dbus_assert (find_subtree (tree, path1, NULL));
1797   _dbus_assert (find_subtree (tree, path2, NULL));
1798   _dbus_assert (find_subtree (tree, path3, NULL));
1799   _dbus_assert (find_subtree (tree, path4, NULL));
1800   _dbus_assert (find_subtree (tree, path5, NULL));
1801   _dbus_assert (!find_subtree (tree, path6, NULL));
1802   _dbus_assert (!find_subtree (tree, path7, NULL));
1803   _dbus_assert (!find_subtree (tree, path8, NULL));
1804
1805   _dbus_assert (find_handler (tree, path0, &exact_match) == tree->root &&  exact_match);
1806   _dbus_assert (find_handler (tree, path1, &exact_match) != tree->root &&  exact_match);
1807   _dbus_assert (find_handler (tree, path2, &exact_match) != tree->root &&  exact_match);
1808   _dbus_assert (find_handler (tree, path3, &exact_match) != tree->root &&  exact_match);
1809   _dbus_assert (find_handler (tree, path4, &exact_match) != tree->root &&  exact_match);
1810   _dbus_assert (find_handler (tree, path5, &exact_match) != tree->root &&  exact_match);
1811   _dbus_assert (find_handler (tree, path6, &exact_match) != tree->root && !exact_match);
1812   _dbus_assert (find_handler (tree, path7, &exact_match) != tree->root && !exact_match);
1813   _dbus_assert (find_handler (tree, path8, &exact_match) == tree->root && !exact_match);
1814
1815   if (!do_register (tree, path6, TRUE, 6, tree_test_data))
1816     goto out;
1817
1818   _dbus_assert (find_subtree (tree, path0, NULL));
1819   _dbus_assert (find_subtree (tree, path1, NULL));
1820   _dbus_assert (find_subtree (tree, path2, NULL));
1821   _dbus_assert (find_subtree (tree, path3, NULL));
1822   _dbus_assert (find_subtree (tree, path4, NULL));
1823   _dbus_assert (find_subtree (tree, path5, NULL));
1824   _dbus_assert (find_subtree (tree, path6, NULL));
1825   _dbus_assert (!find_subtree (tree, path7, NULL));
1826   _dbus_assert (!find_subtree (tree, path8, NULL));
1827
1828   if (!do_register (tree, path7, TRUE, 7, tree_test_data))
1829     goto out;
1830
1831   _dbus_assert (find_subtree (tree, path0, NULL));
1832   _dbus_assert (find_subtree (tree, path1, NULL));
1833   _dbus_assert (find_subtree (tree, path2, NULL));
1834   _dbus_assert (find_subtree (tree, path3, NULL));
1835   _dbus_assert (find_subtree (tree, path4, NULL));
1836   _dbus_assert (find_subtree (tree, path5, NULL));
1837   _dbus_assert (find_subtree (tree, path6, NULL));
1838   _dbus_assert (find_subtree (tree, path7, NULL));
1839   _dbus_assert (!find_subtree (tree, path8, NULL));
1840
1841   if (!do_register (tree, path8, TRUE, 8, tree_test_data))
1842     goto out;
1843
1844   _dbus_assert (find_subtree (tree, path0, NULL));
1845   _dbus_assert (find_subtree (tree, path1, NULL));
1846   _dbus_assert (find_subtree (tree, path2, NULL));
1847   _dbus_assert (find_subtree (tree, path3, NULL));
1848   _dbus_assert (find_subtree (tree, path4, NULL));
1849   _dbus_assert (find_subtree (tree, path5, NULL));
1850   _dbus_assert (find_subtree (tree, path6, NULL));
1851   _dbus_assert (find_subtree (tree, path7, NULL));
1852   _dbus_assert (find_subtree (tree, path8, NULL));
1853
1854   _dbus_assert (find_handler (tree, path0, &exact_match) == tree->root &&  exact_match);
1855   _dbus_assert (find_handler (tree, path1, &exact_match) != tree->root && exact_match);
1856   _dbus_assert (find_handler (tree, path2, &exact_match) != tree->root && exact_match);
1857   _dbus_assert (find_handler (tree, path3, &exact_match) != tree->root && exact_match);
1858   _dbus_assert (find_handler (tree, path4, &exact_match) != tree->root && exact_match);
1859   _dbus_assert (find_handler (tree, path5, &exact_match) != tree->root && exact_match);
1860   _dbus_assert (find_handler (tree, path6, &exact_match) != tree->root && exact_match);
1861   _dbus_assert (find_handler (tree, path7, &exact_match) != tree->root && exact_match);
1862   _dbus_assert (find_handler (tree, path8, &exact_match) != tree->root && exact_match);
1863
1864   /* test the list_registered function */
1865
1866   {
1867     const char *root[] = { NULL };
1868     char **child_entries;
1869     int nb;
1870
1871     _dbus_object_tree_list_registered_unlocked (tree, path1, &child_entries);
1872     if (child_entries != NULL)
1873       {
1874         nb = _dbus_string_array_length ((const char**)child_entries);
1875         _dbus_assert (nb == 1);
1876         dbus_free_string_array (child_entries);
1877       }
1878
1879     _dbus_object_tree_list_registered_unlocked (tree, path2, &child_entries);
1880     if (child_entries != NULL)
1881       {
1882         nb = _dbus_string_array_length ((const char**)child_entries);
1883         _dbus_assert (nb == 2);
1884         dbus_free_string_array (child_entries);
1885       }
1886
1887     _dbus_object_tree_list_registered_unlocked (tree, path8, &child_entries);
1888     if (child_entries != NULL)
1889       {
1890         nb = _dbus_string_array_length ((const char**)child_entries);
1891         _dbus_assert (nb == 0);
1892         dbus_free_string_array (child_entries);
1893       }
1894
1895     _dbus_object_tree_list_registered_unlocked (tree, root, &child_entries);
1896     if (child_entries != NULL)
1897       {
1898         nb = _dbus_string_array_length ((const char**)child_entries);
1899         _dbus_assert (nb == 3);
1900         dbus_free_string_array (child_entries);
1901       }
1902   }
1903
1904   /* Check that destroying tree calls unregister funcs */
1905   _dbus_object_tree_unref (tree);
1906
1907   i = 0;
1908   while (i < (int) _DBUS_N_ELEMENTS (tree_test_data))
1909     {
1910       _dbus_assert (tree_test_data[i].handler_unregistered);
1911       _dbus_assert (!tree_test_data[i].message_handled);
1912       ++i;
1913     }
1914
1915   /* Now start again and try the individual unregister function */
1916   tree = _dbus_object_tree_new (NULL);
1917   if (tree == NULL)
1918     goto out;
1919
1920   if (!do_register (tree, path0, TRUE, 0, tree_test_data))
1921     goto out;
1922   if (!do_register (tree, path1, TRUE, 1, tree_test_data))
1923     goto out;
1924   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
1925     goto out;
1926   if (!do_register (tree, path3, TRUE, 3, tree_test_data))
1927     goto out;
1928   if (!do_register (tree, path4, TRUE, 4, tree_test_data))
1929     goto out;
1930   if (!do_register (tree, path5, TRUE, 5, tree_test_data))
1931     goto out;
1932   if (!do_register (tree, path6, TRUE, 6, tree_test_data))
1933     goto out;
1934   if (!do_register (tree, path7, TRUE, 7, tree_test_data))
1935     goto out;
1936   if (!do_register (tree, path8, TRUE, 8, tree_test_data))
1937     goto out;
1938
1939   _dbus_object_tree_unregister_and_unlock (tree, path0);
1940   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path0) == NULL);
1941
1942   _dbus_assert (!find_subtree (tree, path0, NULL));
1943   _dbus_assert (find_subtree (tree, path1, NULL));
1944   _dbus_assert (find_subtree (tree, path2, NULL));
1945   _dbus_assert (find_subtree (tree, path3, NULL));
1946   _dbus_assert (find_subtree (tree, path4, NULL));
1947   _dbus_assert (find_subtree (tree, path5, NULL));
1948   _dbus_assert (find_subtree (tree, path6, NULL));
1949   _dbus_assert (find_subtree (tree, path7, NULL));
1950   _dbus_assert (find_subtree (tree, path8, NULL));
1951
1952   _dbus_object_tree_unregister_and_unlock (tree, path1);
1953   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path1) == NULL);
1954
1955   _dbus_assert (!find_subtree (tree, path0, NULL));
1956   _dbus_assert (!find_subtree (tree, path1, NULL));
1957   _dbus_assert (find_subtree (tree, path2, NULL));
1958   _dbus_assert (find_subtree (tree, path3, NULL));
1959   _dbus_assert (find_subtree (tree, path4, NULL));
1960   _dbus_assert (find_subtree (tree, path5, NULL));
1961   _dbus_assert (find_subtree (tree, path6, NULL));
1962   _dbus_assert (find_subtree (tree, path7, NULL));
1963   _dbus_assert (find_subtree (tree, path8, NULL));
1964
1965   _dbus_object_tree_unregister_and_unlock (tree, path2);
1966   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path2) == NULL);
1967
1968   _dbus_assert (!find_subtree (tree, path0, NULL));
1969   _dbus_assert (!find_subtree (tree, path1, NULL));
1970   _dbus_assert (!find_subtree (tree, path2, NULL));
1971   _dbus_assert (find_subtree (tree, path3, NULL));
1972   _dbus_assert (find_subtree (tree, path4, NULL));
1973   _dbus_assert (find_subtree (tree, path5, NULL));
1974   _dbus_assert (find_subtree (tree, path6, NULL));
1975   _dbus_assert (find_subtree (tree, path7, NULL));
1976   _dbus_assert (find_subtree (tree, path8, NULL));
1977
1978   _dbus_object_tree_unregister_and_unlock (tree, path3);
1979   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path3) == NULL);
1980
1981   _dbus_assert (!find_subtree (tree, path0, NULL));
1982   _dbus_assert (!find_subtree (tree, path1, NULL));
1983   _dbus_assert (!find_subtree (tree, path2, NULL));
1984   _dbus_assert (!find_subtree (tree, path3, NULL));
1985   _dbus_assert (find_subtree (tree, path4, NULL));
1986   _dbus_assert (find_subtree (tree, path5, NULL));
1987   _dbus_assert (find_subtree (tree, path6, NULL));
1988   _dbus_assert (find_subtree (tree, path7, NULL));
1989   _dbus_assert (find_subtree (tree, path8, NULL));
1990
1991   _dbus_object_tree_unregister_and_unlock (tree, path4);
1992   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path4) == NULL);
1993
1994   _dbus_assert (!find_subtree (tree, path0, NULL));
1995   _dbus_assert (!find_subtree (tree, path1, NULL));
1996   _dbus_assert (!find_subtree (tree, path2, NULL));
1997   _dbus_assert (!find_subtree (tree, path3, NULL));
1998   _dbus_assert (!find_subtree (tree, path4, NULL));
1999   _dbus_assert (find_subtree (tree, path5, NULL));
2000   _dbus_assert (find_subtree (tree, path6, NULL));
2001   _dbus_assert (find_subtree (tree, path7, NULL));
2002   _dbus_assert (find_subtree (tree, path8, NULL));
2003
2004   _dbus_object_tree_unregister_and_unlock (tree, path5);
2005   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path5) == NULL);
2006
2007   _dbus_assert (!find_subtree (tree, path0, NULL));
2008   _dbus_assert (!find_subtree (tree, path1, NULL));
2009   _dbus_assert (!find_subtree (tree, path2, NULL));
2010   _dbus_assert (!find_subtree (tree, path3, NULL));
2011   _dbus_assert (!find_subtree (tree, path4, NULL));
2012   _dbus_assert (!find_subtree (tree, path5, NULL));
2013   _dbus_assert (find_subtree (tree, path6, NULL));
2014   _dbus_assert (find_subtree (tree, path7, NULL));
2015   _dbus_assert (find_subtree (tree, path8, NULL));
2016
2017   _dbus_object_tree_unregister_and_unlock (tree, path6);
2018   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path6) == NULL);
2019
2020   _dbus_assert (!find_subtree (tree, path0, NULL));
2021   _dbus_assert (!find_subtree (tree, path1, NULL));
2022   _dbus_assert (!find_subtree (tree, path2, NULL));
2023   _dbus_assert (!find_subtree (tree, path3, NULL));
2024   _dbus_assert (!find_subtree (tree, path4, NULL));
2025   _dbus_assert (!find_subtree (tree, path5, NULL));
2026   _dbus_assert (!find_subtree (tree, path6, NULL));
2027   _dbus_assert (find_subtree (tree, path7, NULL));
2028   _dbus_assert (find_subtree (tree, path8, NULL));
2029
2030   _dbus_object_tree_unregister_and_unlock (tree, path7);
2031   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path7) == NULL);
2032
2033   _dbus_assert (!find_subtree (tree, path0, NULL));
2034   _dbus_assert (!find_subtree (tree, path1, NULL));
2035   _dbus_assert (!find_subtree (tree, path2, NULL));
2036   _dbus_assert (!find_subtree (tree, path3, NULL));
2037   _dbus_assert (!find_subtree (tree, path4, NULL));
2038   _dbus_assert (!find_subtree (tree, path5, NULL));
2039   _dbus_assert (!find_subtree (tree, path6, NULL));
2040   _dbus_assert (!find_subtree (tree, path7, NULL));
2041   _dbus_assert (find_subtree (tree, path8, NULL));
2042
2043   _dbus_object_tree_unregister_and_unlock (tree, path8);
2044   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path8) == NULL);
2045
2046   _dbus_assert (!find_subtree (tree, path0, NULL));
2047   _dbus_assert (!find_subtree (tree, path1, NULL));
2048   _dbus_assert (!find_subtree (tree, path2, NULL));
2049   _dbus_assert (!find_subtree (tree, path3, NULL));
2050   _dbus_assert (!find_subtree (tree, path4, NULL));
2051   _dbus_assert (!find_subtree (tree, path5, NULL));
2052   _dbus_assert (!find_subtree (tree, path6, NULL));
2053   _dbus_assert (!find_subtree (tree, path7, NULL));
2054   _dbus_assert (!find_subtree (tree, path8, NULL));
2055
2056   i = 0;
2057   while (i < (int) _DBUS_N_ELEMENTS (tree_test_data))
2058     {
2059       _dbus_assert (tree_test_data[i].handler_unregistered);
2060       _dbus_assert (!tree_test_data[i].message_handled);
2061       ++i;
2062     }
2063
2064   /* Test removal of newly-childless unregistered nodes */
2065   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
2066     goto out;
2067
2068   _dbus_object_tree_unregister_and_unlock (tree, path2);
2069   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2070   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2071   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2072
2073   /* Test that unregistered parents cannot be freed out from under their
2074      children */
2075   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
2076     goto out;
2077
2078   _dbus_assert (!find_subtree (tree, path1, NULL));
2079   _dbus_assert (find_subtree_registered_or_unregistered (tree, path1));
2080   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2081
2082 #if 0
2083   /* This triggers the "Attempted to unregister path ..." warning message */
2084   _dbus_object_tree_unregister_and_unlock (tree, path1);
2085 #endif
2086   _dbus_assert (find_subtree (tree, path2, NULL));
2087   _dbus_assert (!find_subtree (tree, path1, NULL));
2088   _dbus_assert (find_subtree_registered_or_unregistered (tree, path1));
2089   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2090
2091   _dbus_object_tree_unregister_and_unlock (tree, path2);
2092   _dbus_assert (!find_subtree (tree, path2, NULL));
2093   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2094   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2095   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2096
2097   /* Test that registered parents cannot be freed out from under their
2098      children, and that if they are unregistered before their children, they
2099      are still freed when their children are unregistered */
2100   if (!do_register (tree, path1, TRUE, 1, tree_test_data))
2101     goto out;
2102   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
2103     goto out;
2104
2105   _dbus_assert (find_subtree (tree, path1, NULL));
2106   _dbus_assert (find_subtree (tree, path2, NULL));
2107
2108   _dbus_object_tree_unregister_and_unlock (tree, path1);
2109   _dbus_assert (!find_subtree (tree, path1, NULL));
2110   _dbus_assert (find_subtree (tree, path2, NULL));
2111   _dbus_assert (find_subtree_registered_or_unregistered (tree, path1));
2112   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2113
2114   _dbus_object_tree_unregister_and_unlock (tree, path2);
2115   _dbus_assert (!find_subtree (tree, path1, NULL));
2116   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2117   _dbus_assert (!find_subtree (tree, path2, NULL));
2118   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2119   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2120
2121   /* Test with NULL unregister_function and user_data */
2122   if (!_dbus_object_tree_register (tree, TRUE, path2,
2123                                    &test_vtable,
2124                                    NULL,
2125                                    NULL))
2126     goto out;
2127
2128   _dbus_assert (_dbus_object_tree_get_user_data_unlocked (tree, path2) == NULL);
2129   _dbus_object_tree_unregister_and_unlock (tree, path2);
2130   _dbus_assert (!find_subtree (tree, path2, NULL));
2131   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2132   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2133   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2134
2135   /* Test freeing a long path */
2136   if (!do_register (tree, path3, TRUE, 3, tree_test_data))
2137     goto out;
2138
2139   _dbus_object_tree_unregister_and_unlock (tree, path3);
2140   _dbus_assert (!find_subtree (tree, path3, NULL));
2141   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path3));
2142   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2143   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2144   _dbus_assert (find_subtree_registered_or_unregistered (tree, path0));
2145
2146   /* Test freeing multiple children from the same path */
2147   if (!do_register (tree, path3, TRUE, 3, tree_test_data))
2148     goto out;
2149   if (!do_register (tree, path4, TRUE, 4, tree_test_data))
2150     goto out;
2151
2152   _dbus_assert (find_subtree (tree, path3, NULL));
2153   _dbus_assert (find_subtree (tree, path4, NULL));
2154
2155   _dbus_object_tree_unregister_and_unlock (tree, path3);
2156   _dbus_assert (!find_subtree (tree, path3, NULL));
2157   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path3));
2158   _dbus_assert (find_subtree (tree, path4, NULL));
2159   _dbus_assert (find_subtree_registered_or_unregistered (tree, path4));
2160   _dbus_assert (find_subtree_registered_or_unregistered (tree, path2));
2161   _dbus_assert (find_subtree_registered_or_unregistered (tree, path1));
2162
2163   _dbus_object_tree_unregister_and_unlock (tree, path4);
2164   _dbus_assert (!find_subtree (tree, path4, NULL));
2165   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path4));
2166   _dbus_assert (!find_subtree (tree, path3, NULL));
2167   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path3));
2168   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path2));
2169   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path1));
2170
2171   /* Test subtree removal */
2172   if (!_dbus_object_tree_register (tree, TRUE, path12,
2173                                    &test_vtable,
2174                                    NULL,
2175                                    NULL))
2176     goto out;
2177
2178   _dbus_assert (find_subtree (tree, path12, NULL));
2179
2180   if (!_dbus_object_tree_register (tree, TRUE, path13,
2181                                    &test_vtable,
2182                                    NULL,
2183                                    NULL))
2184     goto out;
2185
2186   _dbus_assert (find_subtree (tree, path13, NULL));
2187
2188   if (!_dbus_object_tree_register (tree, TRUE, path14,
2189                                    &test_vtable,
2190                                    NULL,
2191                                    NULL))
2192     goto out;
2193
2194   _dbus_assert (find_subtree (tree, path14, NULL));
2195
2196   _dbus_object_tree_unregister_and_unlock (tree, path12);
2197
2198   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path12));
2199   _dbus_assert (find_subtree (tree, path13, NULL));
2200   _dbus_assert (find_subtree (tree, path14, NULL));
2201   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path9));
2202   _dbus_assert (find_subtree_registered_or_unregistered (tree, path5));
2203
2204   if (!_dbus_object_tree_register (tree, TRUE, path12,
2205                                    &test_vtable,
2206                                    NULL,
2207                                    NULL))
2208     goto out;
2209
2210   _dbus_assert (find_subtree (tree, path12, NULL));
2211
2212   _dbus_object_tree_unregister_and_unlock (tree, path13);
2213
2214   _dbus_assert (find_subtree (tree, path12, NULL));
2215   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path13));
2216   _dbus_assert (find_subtree (tree, path14, NULL));
2217   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path10));
2218   _dbus_assert (find_subtree_registered_or_unregistered (tree, path5));
2219
2220   if (!_dbus_object_tree_register (tree, TRUE, path13,
2221                                    &test_vtable,
2222                                    NULL,
2223                                    NULL))
2224     goto out;
2225
2226   _dbus_assert (find_subtree (tree, path13, NULL));
2227
2228   _dbus_object_tree_unregister_and_unlock (tree, path14);
2229
2230   _dbus_assert (find_subtree (tree, path12, NULL));
2231   _dbus_assert (find_subtree (tree, path13, NULL));
2232   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path14));
2233   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path11));
2234   _dbus_assert (find_subtree_registered_or_unregistered (tree, path5));
2235
2236   _dbus_object_tree_unregister_and_unlock (tree, path12);
2237
2238   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path12));
2239   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path9));
2240   _dbus_assert (find_subtree_registered_or_unregistered (tree, path5));
2241
2242   _dbus_object_tree_unregister_and_unlock (tree, path13);
2243
2244   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path13));
2245   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path10));
2246   _dbus_assert (!find_subtree_registered_or_unregistered (tree, path5));
2247
2248 #if 0
2249   /* Test attempting to unregister non-existent paths.  These trigger
2250      "Attempted to unregister path ..." warning messages */
2251   _dbus_object_tree_unregister_and_unlock (tree, path0);
2252   _dbus_object_tree_unregister_and_unlock (tree, path1);
2253   _dbus_object_tree_unregister_and_unlock (tree, path2);
2254   _dbus_object_tree_unregister_and_unlock (tree, path3);
2255   _dbus_object_tree_unregister_and_unlock (tree, path4);
2256 #endif
2257
2258   /* Register it all again, and test dispatch */
2259
2260   if (!do_register (tree, path0, TRUE, 0, tree_test_data))
2261     goto out;
2262   if (!do_register (tree, path1, FALSE, 1, tree_test_data))
2263     goto out;
2264   if (!do_register (tree, path2, TRUE, 2, tree_test_data))
2265     goto out;
2266   if (!do_register (tree, path3, TRUE, 3, tree_test_data))
2267     goto out;
2268   if (!do_register (tree, path4, TRUE, 4, tree_test_data))
2269     goto out;
2270   if (!do_register (tree, path5, TRUE, 5, tree_test_data))
2271     goto out;
2272   if (!do_register (tree, path6, FALSE, 6, tree_test_data))
2273     goto out;
2274   if (!do_register (tree, path7, TRUE, 7, tree_test_data))
2275     goto out;
2276   if (!do_register (tree, path8, TRUE, 8, tree_test_data))
2277     goto out;
2278
2279 #if 0
2280   spew_tree (tree);
2281 #endif
2282
2283   if (!do_test_dispatch (tree, path0, 0, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2284     goto out;
2285   if (!do_test_dispatch (tree, path1, 1, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2286     goto out;
2287   if (!do_test_dispatch (tree, path2, 2, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2288     goto out;
2289   if (!do_test_dispatch (tree, path3, 3, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2290     goto out;
2291   if (!do_test_dispatch (tree, path4, 4, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2292     goto out;
2293   if (!do_test_dispatch (tree, path5, 5, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2294     goto out;
2295   if (!do_test_dispatch (tree, path6, 6, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2296     goto out;
2297   if (!do_test_dispatch (tree, path7, 7, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2298     goto out;
2299   if (!do_test_dispatch (tree, path8, 8, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data)))
2300     goto out;
2301
2302  out:
2303   if (tree)
2304     {
2305       /* test ref */
2306       _dbus_object_tree_ref (tree);
2307       _dbus_object_tree_unref (tree);
2308       _dbus_object_tree_unref (tree);
2309     }
2310
2311   return TRUE;
2312 }
2313
2314 /**
2315  * @ingroup DBusObjectTree
2316  * Unit test for DBusObjectTree
2317  * @returns #TRUE on success.
2318  */
2319 dbus_bool_t
2320 _dbus_object_tree_test (void)
2321 {
2322   return _dbus_test_oom_handling ("object tree",
2323                                   object_tree_test_iteration,
2324                                   NULL);
2325 }
2326
2327 #endif /* !DOXYGEN_SHOULD_SKIP_THIS */
2328
2329 #endif /* DBUS_ENABLE_EMBEDDED_TESTS */