dbus/dbus-object-tree.c

   1 /* -*- mode: C; c-file-style: "gnu" -*- */
   2 /* dbus-object-tree.c  DBusObjectTree (internals of DBusConnection)
   3  *
   4  * Copyright (C) 2003  Red Hat Inc.
   5  *
   6  * Licensed under the Academic Free License version 1.2
   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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  *
  22  */
  23 #include "dbus-object-tree.h"
  24 #include "dbus-connection-internal.h"
  25 #include "dbus-internals.h"
  26 #include "dbus-hash.h"
  27 #include "dbus-protocol.h"
  28 #include <string.h>
  29 #include <stdlib.h>
  30
  31 /**
  32  * @defgroup DBusObjectTree A hierarchy of objects with container-contained relationship
  33  * @ingroup  DBusInternals
  34  * @brief DBusObjectTree is used by DBusConnection to track the object tree
  35  *
  36  * Types and functions related to DBusObjectTree. These
  37  * are all internal.
  38  *
  39  * @{
  40  */
  41
  42 typedef struct DBusObjectSubtree DBusObjectSubtree;
  43
  44 DBusObjectSubtree* _dbus_object_subtree_new   (const char                 **path,
  45                                                const DBusObjectTreeVTable  *vtable,
  46                                                void                        *user_data);
  47 void               _dbus_object_subtree_ref   (DBusObjectSubtree           *subtree);
  48 void               _dbus_object_subtree_unref (DBusObjectSubtree           *subtree);
  49
  50 struct DBusObjectTree
  51 {
  52   int                 refcount;
  53   DBusConnection     *connection;
  54
  55   /* Each subtree is a separate malloc block since that
  56    * lets us refcount them and maybe helps with
  57    * reentrancy issues when calling back to application code
  58    */
  59   DBusObjectSubtree **subtrees;
  60   int                 n_subtrees;
  61   unsigned int        subtrees_sorted : 1;
  62 };
  63
  64 struct DBusObjectSubtree
  65 {
  66   int                   refcount;
  67   char                **path;
  68   int                   n_path_elements;
  69   DBusObjectTreeVTable  vtable;
  70   void                 *user_data;
  71 };
  72
  73 DBusObjectTree*
  74 _dbus_object_tree_new (DBusConnection *connection)
  75 {
  76   DBusObjectTree *tree;
  77
  78   /* the connection passed in here isn't fully constructed,
  79    * so don't do anything more than store a pointer to
  80    * it
  81    */
  82
  83   tree = dbus_new0 (DBusObjectTree, 1);
  84   if (tree == NULL)
  85     goto oom;
  86
  87   tree->refcount = 1;
  88   tree->connection = connection;
  89
  90   return tree;
  91
  92  oom:
  93   if (tree)
  94     {
  95       dbus_free (tree);
  96     }
  97
  98   return NULL;
  99 }
 100
 101 void
 102 _dbus_object_tree_ref (DBusObjectTree *tree)
 103 {
 104   _dbus_assert (tree->refcount > 0);
 105
 106   tree->refcount += 1;
 107 }
 108
 109 void
 110 _dbus_object_tree_unref (DBusObjectTree *tree)
 111 {
 112   _dbus_assert (tree->refcount > 0);
 113
 114   tree->refcount -= 1;
 115
 116   if (tree->refcount == 0)
 117     {
 118       if (tree->subtrees)
 119         {
 120           int i;
 121           i = 0;
 122           while (i < tree->n_subtrees)
 123             {
 124               _dbus_object_subtree_unref (tree->subtrees[i]);
 125               ++i;
 126             }
 127         }
 128
 129       dbus_free (tree);
 130     }
 131 }
 132
 133 static int
 134 path_cmp (const char **path_a,
 135           const char **path_b)
 136 {
 137   /* The comparison is as if the path were flattened
 138    * into a single string. strcmp() considers
 139    * a shorter string less than a longer string
 140    * if the shorter string is the initial part
 141    * of the longer
 142    */
 143   int i;
 144
 145   i = 0;
 146   while (path_a[i] != NULL)
 147     {
 148       int v;
 149
 150       if (path_b[i] == NULL)
 151         return 1; /* a is longer than b */
 152
 153       _dbus_assert (path_a[i] != NULL);
 154       _dbus_assert (path_b[i] != NULL);
 155
 156       v = strcmp (path_a[i], path_b[i]);
 157
 158       if (v != 0)
 159         return v;
 160
 161       ++i;
 162     }
 163
 164   _dbus_assert (path_a[i] == NULL);
 165   if (path_b[i] == NULL)
 166     return 0;
 167
 168   /* b is longer than a */
 169   return -1;
 170 }
 171
 172 static int
 173 subtree_cmp (DBusObjectSubtree *subtree_a,
 174              DBusObjectSubtree *subtree_b)
 175 {
 176   return path_cmp ((const char**) subtree_a->path,
 177                    (const char**) subtree_b->path);
 178 }
 179
 180 static int
 181 subtree_qsort_cmp (const void *a,
 182                    const void *b)
 183 {
 184   DBusObjectSubtree **subtree_a_p = (void*) a;
 185   DBusObjectSubtree **subtree_b_p = (void*) b;
 186
 187   return subtree_cmp (*subtree_a_p, *subtree_b_p);
 188 }
 189
 190 /* Returns TRUE if a is a subdir of b or vice
 191  * versa. This is the case if one is a subpath
 192  * of the other.
 193  */
 194 static dbus_bool_t
 195 path_overlaps (const char **path_a,
 196                const char **path_b)
 197 {
 198   int i;
 199
 200   i = 0;
 201   while (path_a[i] != NULL)
 202     {
 203       int v;
 204
 205       if (path_b[i] == NULL)
 206         return TRUE; /* b is subpath of a */
 207
 208       _dbus_assert (path_a[i] != NULL);
 209       _dbus_assert (path_b[i] != NULL);
 210
 211       v = strcmp (path_a[i], path_b[i]);
 212
 213       if (v != 0)
 214         return FALSE; /* they overlap until here and then are different,
 215                        * not overlapping
 216                        */
 217
 218       ++i;
 219     }
 220
 221   /* b is either the same as or a superset of a */
 222   _dbus_assert (path_a[i] == NULL);
 223   return TRUE;
 224 }
 225
 226 static dbus_bool_t
 227 find_subtree (DBusObjectTree *tree,
 228               const char    **path,
 229               int            *idx_p)
 230 {
 231   int i;
 232
 233   if (tree->subtrees == NULL)
 234     return FALSE;
 235
 236   if (!tree->subtrees_sorted)
 237     {
 238       qsort (tree->subtrees,
 239              tree->n_subtrees,
 240              sizeof (DBusObjectSubtree*),
 241              subtree_qsort_cmp);
 242       tree->subtrees_sorted = TRUE;
 243     }
 244
 245   /* FIXME this should be a binary search,
 246    * as that's the whole point of the sorting
 247    */
 248   i = 0;
 249   while (i < tree->n_subtrees)
 250     {
 251       int v;
 252
 253       v = path_cmp (path,
 254                     (const char**) tree->subtrees[i]->path);
 255       if (v == 0)
 256         {
 257           if (idx_p)
 258             *idx_p = i;
 259           return TRUE;
 260         }
 261       else if (v > 0)
 262         return FALSE;
 263
 264       ++i;
 265     }
 266
 267   return FALSE;
 268 }
 269
 270 #ifndef DBUS_DISABLE_CHECKS
 271 static void
 272 check_overlap (DBusObjectTree *tree,
 273                const char    **path)
 274 {
 275   int i;
 276
 277   i = 0;
 278   while (i < tree->n_subtrees)
 279     {
 280       if (path_overlaps (path, (const char**) tree->subtrees[i]->path))
 281         {
 282           _dbus_warn ("New path (path[0] = %s) overlaps old path (path[0] = %s)\n",
 283                       path[0], tree->subtrees[i]->path[0]);
 284         }
 285       ++i;
 286     }
 287 }
 288 #endif
 289
 290 /**
 291  * Registers a new subtree in the global object tree.
 292  *
 293  * @param tree the global object tree
 294  * @param path NULL-terminated array of path elements giving path to subtree
 295  * @param vtable the vtable used to traverse this subtree
 296  * @param user_data user data to pass to methods in the vtable
 297  * @returns #FALSE if not enough memory
 298  */
 299 dbus_bool_t
 300 _dbus_object_tree_register (DBusObjectTree              *tree,
 301                             const char                 **path,
 302                             const DBusObjectTreeVTable  *vtable,
 303                             void                        *user_data)
 304 {
 305   DBusObjectSubtree  *subtree;
 306   DBusObjectSubtree **new_subtrees;
 307   int new_n_subtrees;
 308
 309   _dbus_assert (path != NULL);
 310 #ifndef DBUS_DISABLE_CHECKS
 311   check_overlap (tree, path);
 312 #endif
 313   _dbus_assert (path[0] != NULL);
 314
 315   subtree = _dbus_object_subtree_new (path, vtable, user_data);
 316   if (subtree == NULL)
 317     return FALSE;
 318
 319   /* FIXME we should do the "double alloc each time" standard thing */
 320   new_n_subtrees = tree->n_subtrees + 1;
 321   new_subtrees = dbus_realloc (tree->subtrees,
 322                                new_n_subtrees);
 323   if (new_subtrees == NULL)
 324     {
 325       _DBUS_ZERO (subtree->vtable); /* to avoid assertion in unref() */
 326       _dbus_object_subtree_unref (subtree);
 327       return FALSE;
 328     }
 329
 330   tree->subtrees[tree->n_subtrees] = subtree;
 331   tree->subtrees_sorted = FALSE;
 332   tree->n_subtrees = new_n_subtrees;
 333   tree->subtrees = new_subtrees;
 334
 335   return TRUE;
 336 }
 337
 338 /**
 339  * Unregisters an object subtree that was registered with the
 340  * same path.
 341  *
 342  * @param tree the global object tree
 343  * @param path path to the subtree (same as the one passed to _dbus_object_tree_register())
 344  */
 345 void
 346 _dbus_object_tree_unregister_and_unlock (DBusObjectTree          *tree,
 347                                          const char             **path)
 348 {
 349   int i;
 350   DBusObjectSubtree *subtree;
 351
 352   _dbus_assert (path != NULL);
 353   _dbus_assert (path[0] != NULL);
 354
 355   if (!find_subtree (tree, path, &i))
 356     {
 357       _dbus_warn ("Attempted to unregister subtree (path[0] = %s) which isn't registered\n",
 358                   path[0]);
 359       return;
 360     }
 361
 362   subtree = tree->subtrees[i];
 363
 364   /* assumes a 0-byte memmove is OK */
 365   memmove (&tree->subtrees[i],
 366            &tree->subtrees[i+1],
 367            (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0]));
 368   tree->n_subtrees -= 1;
 369
 370   _dbus_object_subtree_ref (subtree);
 371
 372   /* Unlock and call application code */
 373   _dbus_connection_unlock (tree->connection);
 374
 375   if (subtree->vtable.unregister_function)
 376     {
 377       (* subtree->vtable.unregister_function) (tree->connection,
 378                                                (const char**) subtree->path,
 379                                                subtree->user_data);
 380       _DBUS_ZERO (subtree->vtable);
 381     }
 382 }
 383
 384 /**
 385  * Tries to dispatch a message by directing it to the object tree
 386  * node listed in the message header, if any.
 387  *
 388  * @param tree the global object tree
 389  * @param message the message to dispatch
 390  * @returns whether message was handled successfully
 391  */
 392 DBusHandlerResult
 393 _dbus_object_tree_dispatch_and_unlock (DBusObjectTree          *tree,
 394                                        DBusMessage             *message)
 395 {
 396
 397
 398 }
 399
 400 DBusObjectSubtree*
 401 _dbus_object_subtree_new (const char                 **path,
 402                           const DBusObjectTreeVTable  *vtable,
 403                           void                        *user_data)
 404 {
 405   DBusObjectSubtree *subtree;
 406
 407   subtree = dbus_new0 (DBusObjectSubtree, 1);
 408   if (subtree == NULL)
 409     goto oom;
 410
 411   _dbus_assert (path != NULL);
 412   _dbus_assert (path[0] != NULL);
 413
 414   subtree->path = _dbus_dup_string_array (path);
 415   if (subtree->path == NULL)
 416     goto oom;
 417
 418   subtree->vtable = *vtable;
 419   subtree->user_data = user_data;
 420
 421   subtree->refcount = 1;
 422
 423   /* count path elements */
 424   while (subtree->path[subtree->n_path_elements])
 425     subtree->n_path_elements += 1;
 426
 427   return subtree;
 428
 429  oom:
 430   if (subtree)
 431     {
 432       dbus_free_string_array (subtree->path);
 433       dbus_free (subtree);
 434     }
 435
 436   return NULL;
 437 }
 438
 439 void
 440 _dbus_object_subtree_ref (DBusObjectSubtree *subtree)
 441 {
 442   _dbus_assert (subtree->refcount > 0);
 443
 444   subtree->refcount += 1;
 445 }
 446
 447 void
 448 _dbus_object_subtree_unref (DBusObjectSubtree *subtree)
 449 {
 450   _dbus_assert (subtree->refcount > 0);
 451
 452   subtree->refcount -= 1;
 453
 454   if (subtree->refcount == 0)
 455     {
 456       _dbus_assert (subtree->vtable.unregister_function == NULL);
 457
 458       dbus_free_string_array (subtree->path);
 459
 460       dbus_free (subtree);
 461     }
 462 }
 463
 464 /** @} */
 465
 466 #ifdef DBUS_BUILD_TESTS
 467 #include "dbus-test.h"
 468 #include <stdio.h>
 469
 470 static dbus_bool_t
 471 test_subtree_cmp (const char **path1,
 472                   const char **path2,
 473                   int          expected,
 474                   dbus_bool_t  reverse)
 475 {
 476   DBusObjectSubtree *subtree1;
 477   DBusObjectSubtree *subtree2;
 478   dbus_bool_t retval;
 479   DBusObjectTreeVTable vtable;
 480
 481   _DBUS_ZERO (vtable);
 482
 483   retval = FALSE;
 484
 485   subtree1 = _dbus_object_subtree_new (path1, &vtable, NULL);
 486   subtree2 = _dbus_object_subtree_new (path2, &vtable, NULL);
 487   if (subtree1 == NULL || subtree2 == NULL)
 488     goto out;
 489
 490   _dbus_assert (subtree_cmp (subtree1, subtree2) == expected);
 491
 492   retval = TRUE;
 493
 494  out:
 495
 496   if (subtree1)
 497     _dbus_object_subtree_unref (subtree1);
 498
 499   if (subtree2)
 500     _dbus_object_subtree_unref (subtree2);
 501
 502   if (retval && reverse)
 503     {
 504       /* Verify that the reverse also holds */
 505       if (expected > 0)
 506         return test_subtree_cmp (path2, path1, -1, FALSE);
 507       else if (expected < 0)
 508         return test_subtree_cmp (path2, path1, 1, FALSE);
 509       else
 510         return test_subtree_cmp (path2, path1, 0, FALSE);
 511     }
 512
 513   return retval;
 514 }
 515
 516 static void
 517 test_path_overlap (const char  **path1,
 518                    const char  **path2,
 519                    dbus_bool_t   expected)
 520 {
 521   _dbus_assert (path_overlaps (path1, path2) == expected);
 522   _dbus_assert (path_overlaps (path2, path1) == expected);
 523 }
 524
 525 static dbus_bool_t
 526 object_tree_test_iteration (void *data)
 527 {
 528   const char *path1[] = { "foo", NULL };
 529   const char *path2[] = { "foo", "bar", NULL };
 530   const char *path3[] = { "foo", "bar", "baz", NULL };
 531   const char *path4[] = { "foo", "bar", "boo", NULL };
 532   const char *path5[] = { "blah", NULL };
 533   DBusObjectSubtree *subtree1;
 534   DBusObjectSubtree *subtree2;
 535   DBusObjectTree *tree;
 536
 537   tree = NULL;
 538   subtree1 = NULL;
 539   subtree2 = NULL;
 540
 541   test_path_overlap (path1, path1, TRUE);
 542   test_path_overlap (path1, path2, TRUE);
 543   test_path_overlap (path1, path3, TRUE);
 544   test_path_overlap (path1, path4, TRUE);
 545   test_path_overlap (path1, path5, FALSE);
 546
 547   test_path_overlap (path2, path2, TRUE);
 548   test_path_overlap (path2, path3, TRUE);
 549   test_path_overlap (path2, path4, TRUE);
 550   test_path_overlap (path2, path5, FALSE);
 551
 552   test_path_overlap (path3, path3, TRUE);
 553   test_path_overlap (path3, path4, FALSE);
 554   test_path_overlap (path3, path5, FALSE);
 555
 556   test_path_overlap (path4, path4, TRUE);
 557   test_path_overlap (path4, path5, FALSE);
 558
 559   test_path_overlap (path5, path5, TRUE);
 560
 561   if (!test_subtree_cmp (path1, path1, 0, TRUE))
 562     goto out;
 563   if (!test_subtree_cmp (path3, path3, 0, TRUE))
 564     goto out;
 565   /* When testing -1, the reverse also gets tested */
 566   if (!test_subtree_cmp (path1, path2, -1, TRUE))
 567     goto out;
 568   if (!test_subtree_cmp (path1, path3, -1, TRUE))
 569     goto out;
 570   if (!test_subtree_cmp (path2, path3, -1, TRUE))
 571     goto out;
 572   if (!test_subtree_cmp (path2, path4, -1, TRUE))
 573     goto out;
 574   if (!test_subtree_cmp (path3, path4, -1, TRUE))
 575     goto out;
 576   if (!test_subtree_cmp (path5, path1, -1, TRUE))
 577     goto out;
 578
 579   tree = _dbus_object_tree_new (NULL);
 580   if (tree == NULL)
 581     goto out;
 582
 583  out:
 584   if (subtree1)
 585     _dbus_object_subtree_unref (subtree1);
 586   if (subtree2)
 587     _dbus_object_subtree_unref (subtree2);
 588   if (tree)
 589     _dbus_object_tree_unref (tree);
 590
 591   return TRUE;
 592 }
 593
 594 /**
 595  * @ingroup DBusObjectTree
 596  * Unit test for DBusObjectTree
 597  * @returns #TRUE on success.
 598  */
 599 dbus_bool_t
 600 _dbus_object_tree_test (void)
 601 {
 602   _dbus_test_oom_handling ("object tree",
 603                            object_tree_test_iteration,
 604                            NULL);
 605
 606   return TRUE;
 607 }
 608
 609 #endif /* DBUS_BUILD_TESTS */