From 24f411a6a10e4838f57595720642ce83ceae814c Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Mon, 25 Aug 2003 14:56:53 +0000 Subject: 2003-08-25 Havoc Pennington Just noticed that dbus_message_test is hosed, I wonder when I broke that. I thought make check was passing earlier... * dbus/dbus-object-tree.c: add new "object tree" to match DCOP container tree, will replace most of dbus-object-registry * dbus/dbus-string.c (_dbus_string_append_printf_valist): fix C99 screwup --- dbus/dbus-object-tree.c | 609 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 609 insertions(+) create mode 100644 dbus/dbus-object-tree.c (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c new file mode 100644 index 00000000..7f7e6011 --- /dev/null +++ b/dbus/dbus-object-tree.c @@ -0,0 +1,609 @@ +/* -*- mode: C; c-file-style: "gnu" -*- */ +/* dbus-object-tree.c DBusObjectTree (internals of DBusConnection) + * + * Copyright (C) 2003 Red Hat Inc. + * + * Licensed under the Academic Free License version 1.2 + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ +#include "dbus-object-tree.h" +#include "dbus-connection-internal.h" +#include "dbus-internals.h" +#include "dbus-hash.h" +#include "dbus-protocol.h" +#include +#include + +/** + * @defgroup DBusObjectTree A hierarchy of objects with container-contained relationship + * @ingroup DBusInternals + * @brief DBusObjectTree is used by DBusConnection to track the object tree + * + * Types and functions related to DBusObjectTree. These + * are all internal. + * + * @{ + */ + +typedef struct DBusObjectSubtree DBusObjectSubtree; + +DBusObjectSubtree* _dbus_object_subtree_new (const char **path, + const DBusObjectTreeVTable *vtable, + void *user_data); +void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); +void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); + +struct DBusObjectTree +{ + int refcount; + DBusConnection *connection; + + /* Each subtree is a separate malloc block since that + * lets us refcount them and maybe helps with + * reentrancy issues when calling back to application code + */ + DBusObjectSubtree **subtrees; + int n_subtrees; + unsigned int subtrees_sorted : 1; +}; + +struct DBusObjectSubtree +{ + int refcount; + char **path; + int n_path_elements; + DBusObjectTreeVTable vtable; + void *user_data; +}; + +DBusObjectTree* +_dbus_object_tree_new (DBusConnection *connection) +{ + DBusObjectTree *tree; + + /* the connection passed in here isn't fully constructed, + * so don't do anything more than store a pointer to + * it + */ + + tree = dbus_new0 (DBusObjectTree, 1); + if (tree == NULL) + goto oom; + + tree->refcount = 1; + tree->connection = connection; + + return tree; + + oom: + if (tree) + { + dbus_free (tree); + } + + return NULL; +} + +void +_dbus_object_tree_ref (DBusObjectTree *tree) +{ + _dbus_assert (tree->refcount > 0); + + tree->refcount += 1; +} + +void +_dbus_object_tree_unref (DBusObjectTree *tree) +{ + _dbus_assert (tree->refcount > 0); + + tree->refcount -= 1; + + if (tree->refcount == 0) + { + if (tree->subtrees) + { + int i; + i = 0; + while (i < tree->n_subtrees) + { + _dbus_object_subtree_unref (tree->subtrees[i]); + ++i; + } + } + + dbus_free (tree); + } +} + +static int +path_cmp (const char **path_a, + const char **path_b) +{ + /* The comparison is as if the path were flattened + * into a single string. strcmp() considers + * a shorter string less than a longer string + * if the shorter string is the initial part + * of the longer + */ + int i; + + i = 0; + while (path_a[i] != NULL) + { + int v; + + if (path_b[i] == NULL) + return 1; /* a is longer than b */ + + _dbus_assert (path_a[i] != NULL); + _dbus_assert (path_b[i] != NULL); + + v = strcmp (path_a[i], path_b[i]); + + if (v != 0) + return v; + + ++i; + } + + _dbus_assert (path_a[i] == NULL); + if (path_b[i] == NULL) + return 0; + + /* b is longer than a */ + return -1; +} + +static int +subtree_cmp (DBusObjectSubtree *subtree_a, + DBusObjectSubtree *subtree_b) +{ + return path_cmp ((const char**) subtree_a->path, + (const char**) subtree_b->path); +} + +static int +subtree_qsort_cmp (const void *a, + const void *b) +{ + DBusObjectSubtree **subtree_a_p = (void*) a; + DBusObjectSubtree **subtree_b_p = (void*) b; + + return subtree_cmp (*subtree_a_p, *subtree_b_p); +} + +/* Returns TRUE if a is a subdir of b or vice + * versa. This is the case if one is a subpath + * of the other. + */ +static dbus_bool_t +path_overlaps (const char **path_a, + const char **path_b) +{ + int i; + + i = 0; + while (path_a[i] != NULL) + { + int v; + + if (path_b[i] == NULL) + return TRUE; /* b is subpath of a */ + + _dbus_assert (path_a[i] != NULL); + _dbus_assert (path_b[i] != NULL); + + v = strcmp (path_a[i], path_b[i]); + + if (v != 0) + return FALSE; /* they overlap until here and then are different, + * not overlapping + */ + + ++i; + } + + /* b is either the same as or a superset of a */ + _dbus_assert (path_a[i] == NULL); + return TRUE; +} + +static dbus_bool_t +find_subtree (DBusObjectTree *tree, + const char **path, + int *idx_p) +{ + int i; + + if (tree->subtrees == NULL) + return FALSE; + + if (!tree->subtrees_sorted) + { + qsort (tree->subtrees, + tree->n_subtrees, + sizeof (DBusObjectSubtree*), + subtree_qsort_cmp); + tree->subtrees_sorted = TRUE; + } + + /* FIXME this should be a binary search, + * as that's the whole point of the sorting + */ + i = 0; + while (i < tree->n_subtrees) + { + int v; + + v = path_cmp (path, + (const char**) tree->subtrees[i]->path); + if (v == 0) + { + if (idx_p) + *idx_p = i; + return TRUE; + } + else if (v > 0) + return FALSE; + + ++i; + } + + return FALSE; +} + +#ifndef DBUS_DISABLE_CHECKS +static void +check_overlap (DBusObjectTree *tree, + const char **path) +{ + int i; + + i = 0; + while (i < tree->n_subtrees) + { + if (path_overlaps (path, (const char**) tree->subtrees[i]->path)) + { + _dbus_warn ("New path (path[0] = %s) overlaps old path (path[0] = %s)\n", + path[0], tree->subtrees[i]->path[0]); + } + ++i; + } +} +#endif + +/** + * Registers a new subtree in the global object tree. + * + * @param tree the global object tree + * @param path NULL-terminated array of path elements giving path to subtree + * @param vtable the vtable used to traverse this subtree + * @param user_data user data to pass to methods in the vtable + * @returns #FALSE if not enough memory + */ +dbus_bool_t +_dbus_object_tree_register (DBusObjectTree *tree, + const char **path, + const DBusObjectTreeVTable *vtable, + void *user_data) +{ + DBusObjectSubtree *subtree; + DBusObjectSubtree **new_subtrees; + int new_n_subtrees; + + _dbus_assert (path != NULL); +#ifndef DBUS_DISABLE_CHECKS + check_overlap (tree, path); +#endif + _dbus_assert (path[0] != NULL); + + subtree = _dbus_object_subtree_new (path, vtable, user_data); + if (subtree == NULL) + return FALSE; + + /* FIXME we should do the "double alloc each time" standard thing */ + new_n_subtrees = tree->n_subtrees + 1; + new_subtrees = dbus_realloc (tree->subtrees, + new_n_subtrees); + if (new_subtrees == NULL) + { + _DBUS_ZERO (subtree->vtable); /* to avoid assertion in unref() */ + _dbus_object_subtree_unref (subtree); + return FALSE; + } + + tree->subtrees[tree->n_subtrees] = subtree; + tree->subtrees_sorted = FALSE; + tree->n_subtrees = new_n_subtrees; + tree->subtrees = new_subtrees; + + return TRUE; +} + +/** + * Unregisters an object subtree that was registered with the + * same path. + * + * @param tree the global object tree + * @param path path to the subtree (same as the one passed to _dbus_object_tree_register()) + */ +void +_dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, + const char **path) +{ + int i; + DBusObjectSubtree *subtree; + + _dbus_assert (path != NULL); + _dbus_assert (path[0] != NULL); + + if (!find_subtree (tree, path, &i)) + { + _dbus_warn ("Attempted to unregister subtree (path[0] = %s) which isn't registered\n", + path[0]); + return; + } + + subtree = tree->subtrees[i]; + + /* assumes a 0-byte memmove is OK */ + memmove (&tree->subtrees[i], + &tree->subtrees[i+1], + (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0])); + tree->n_subtrees -= 1; + + _dbus_object_subtree_ref (subtree); + + /* Unlock and call application code */ + _dbus_connection_unlock (tree->connection); + + if (subtree->vtable.unregister_function) + { + (* subtree->vtable.unregister_function) (tree->connection, + (const char**) subtree->path, + subtree->user_data); + _DBUS_ZERO (subtree->vtable); + } +} + +/** + * Tries to dispatch a message by directing it to the object tree + * node listed in the message header, if any. + * + * @param tree the global object tree + * @param message the message to dispatch + * @returns whether message was handled successfully + */ +DBusHandlerResult +_dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, + DBusMessage *message) +{ + + +} + +DBusObjectSubtree* +_dbus_object_subtree_new (const char **path, + const DBusObjectTreeVTable *vtable, + void *user_data) +{ + DBusObjectSubtree *subtree; + + subtree = dbus_new0 (DBusObjectSubtree, 1); + if (subtree == NULL) + goto oom; + + _dbus_assert (path != NULL); + _dbus_assert (path[0] != NULL); + + subtree->path = _dbus_dup_string_array (path); + if (subtree->path == NULL) + goto oom; + + subtree->vtable = *vtable; + subtree->user_data = user_data; + + subtree->refcount = 1; + + /* count path elements */ + while (subtree->path[subtree->n_path_elements]) + subtree->n_path_elements += 1; + + return subtree; + + oom: + if (subtree) + { + dbus_free_string_array (subtree->path); + dbus_free (subtree); + } + + return NULL; +} + +void +_dbus_object_subtree_ref (DBusObjectSubtree *subtree) +{ + _dbus_assert (subtree->refcount > 0); + + subtree->refcount += 1; +} + +void +_dbus_object_subtree_unref (DBusObjectSubtree *subtree) +{ + _dbus_assert (subtree->refcount > 0); + + subtree->refcount -= 1; + + if (subtree->refcount == 0) + { + _dbus_assert (subtree->vtable.unregister_function == NULL); + + dbus_free_string_array (subtree->path); + + dbus_free (subtree); + } +} + +/** @} */ + +#ifdef DBUS_BUILD_TESTS +#include "dbus-test.h" +#include + +static dbus_bool_t +test_subtree_cmp (const char **path1, + const char **path2, + int expected, + dbus_bool_t reverse) +{ + DBusObjectSubtree *subtree1; + DBusObjectSubtree *subtree2; + dbus_bool_t retval; + DBusObjectTreeVTable vtable; + + _DBUS_ZERO (vtable); + + retval = FALSE; + + subtree1 = _dbus_object_subtree_new (path1, &vtable, NULL); + subtree2 = _dbus_object_subtree_new (path2, &vtable, NULL); + if (subtree1 == NULL || subtree2 == NULL) + goto out; + + _dbus_assert (subtree_cmp (subtree1, subtree2) == expected); + + retval = TRUE; + + out: + + if (subtree1) + _dbus_object_subtree_unref (subtree1); + + if (subtree2) + _dbus_object_subtree_unref (subtree2); + + if (retval && reverse) + { + /* Verify that the reverse also holds */ + if (expected > 0) + return test_subtree_cmp (path2, path1, -1, FALSE); + else if (expected < 0) + return test_subtree_cmp (path2, path1, 1, FALSE); + else + return test_subtree_cmp (path2, path1, 0, FALSE); + } + + return retval; +} + +static void +test_path_overlap (const char **path1, + const char **path2, + dbus_bool_t expected) +{ + _dbus_assert (path_overlaps (path1, path2) == expected); + _dbus_assert (path_overlaps (path2, path1) == expected); +} + +static dbus_bool_t +object_tree_test_iteration (void *data) +{ + const char *path1[] = { "foo", NULL }; + const char *path2[] = { "foo", "bar", NULL }; + const char *path3[] = { "foo", "bar", "baz", NULL }; + const char *path4[] = { "foo", "bar", "boo", NULL }; + const char *path5[] = { "blah", NULL }; + DBusObjectSubtree *subtree1; + DBusObjectSubtree *subtree2; + DBusObjectTree *tree; + + tree = NULL; + subtree1 = NULL; + subtree2 = NULL; + + test_path_overlap (path1, path1, TRUE); + test_path_overlap (path1, path2, TRUE); + test_path_overlap (path1, path3, TRUE); + test_path_overlap (path1, path4, TRUE); + test_path_overlap (path1, path5, FALSE); + + test_path_overlap (path2, path2, TRUE); + test_path_overlap (path2, path3, TRUE); + test_path_overlap (path2, path4, TRUE); + test_path_overlap (path2, path5, FALSE); + + test_path_overlap (path3, path3, TRUE); + test_path_overlap (path3, path4, FALSE); + test_path_overlap (path3, path5, FALSE); + + test_path_overlap (path4, path4, TRUE); + test_path_overlap (path4, path5, FALSE); + + test_path_overlap (path5, path5, TRUE); + + if (!test_subtree_cmp (path1, path1, 0, TRUE)) + goto out; + if (!test_subtree_cmp (path3, path3, 0, TRUE)) + goto out; + /* When testing -1, the reverse also gets tested */ + if (!test_subtree_cmp (path1, path2, -1, TRUE)) + goto out; + if (!test_subtree_cmp (path1, path3, -1, TRUE)) + goto out; + if (!test_subtree_cmp (path2, path3, -1, TRUE)) + goto out; + if (!test_subtree_cmp (path2, path4, -1, TRUE)) + goto out; + if (!test_subtree_cmp (path3, path4, -1, TRUE)) + goto out; + if (!test_subtree_cmp (path5, path1, -1, TRUE)) + goto out; + + tree = _dbus_object_tree_new (NULL); + if (tree == NULL) + goto out; + + out: + if (subtree1) + _dbus_object_subtree_unref (subtree1); + if (subtree2) + _dbus_object_subtree_unref (subtree2); + if (tree) + _dbus_object_tree_unref (tree); + + return TRUE; +} + +/** + * @ingroup DBusObjectTree + * Unit test for DBusObjectTree + * @returns #TRUE on success. + */ +dbus_bool_t +_dbus_object_tree_test (void) +{ + _dbus_test_oom_handling ("object tree", + object_tree_test_iteration, + NULL); + + return TRUE; +} + +#endif /* DBUS_BUILD_TESTS */ -- cgit From 8d38a2e2c5dc95de992c4d856ec1b0c0948bca3e Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Fri, 29 Aug 2003 01:05:00 +0000 Subject: 2003-08-28 Havoc Pennington purge DBusObjectID * dbus/dbus-connection.c: port to no ObjectID, create a DBusObjectTree, rename ObjectTree to ObjectPath in public API * dbus/dbus-connection.h (struct DBusObjectTreeVTable): delete everything except UnregisterFunction and MessageFunction * dbus/dbus-marshal.c: port away from DBusObjectID, add DBUS_TYPE_OBJECT_PATH * dbus/dbus-object-registry.[hc], dbus/dbus-object.[hc], dbus/dbus-objectid.[hc]: remove these, we are moving to path-based object IDs --- dbus/dbus-object-tree.c | 27 ++++++++++++++++++++++----- 1 file changed, 22 insertions(+), 5 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 7f7e6011..31724b7b 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -42,7 +42,7 @@ typedef struct DBusObjectSubtree DBusObjectSubtree; DBusObjectSubtree* _dbus_object_subtree_new (const char **path, - const DBusObjectTreeVTable *vtable, + const DBusObjectPathVTable *vtable, void *user_data); void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); @@ -66,7 +66,7 @@ struct DBusObjectSubtree int refcount; char **path; int n_path_elements; - DBusObjectTreeVTable vtable; + DBusObjectPathVTable vtable; void *user_data; }; @@ -299,7 +299,7 @@ check_overlap (DBusObjectTree *tree, dbus_bool_t _dbus_object_tree_register (DBusObjectTree *tree, const char **path, - const DBusObjectTreeVTable *vtable, + const DBusObjectPathVTable *vtable, void *user_data) { DBusObjectSubtree *subtree; @@ -381,10 +381,27 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, } } +/** + * Free all the handlers in the tree. Lock on tree's connection + * must not be held. + * + * @todo implement + * + * @param tree the object tree + */ +void +_dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) +{ + + +} + /** * Tries to dispatch a message by directing it to the object tree * node listed in the message header, if any. * + * @todo implement + * * @param tree the global object tree * @param message the message to dispatch * @returns whether message was handled successfully @@ -399,7 +416,7 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, DBusObjectSubtree* _dbus_object_subtree_new (const char **path, - const DBusObjectTreeVTable *vtable, + const DBusObjectPathVTable *vtable, void *user_data) { DBusObjectSubtree *subtree; @@ -476,7 +493,7 @@ test_subtree_cmp (const char **path1, DBusObjectSubtree *subtree1; DBusObjectSubtree *subtree2; dbus_bool_t retval; - DBusObjectTreeVTable vtable; + DBusObjectPathVTable vtable; _DBUS_ZERO (vtable); -- cgit From ce969c6347b69180088c592e9184f05d0d3525c4 Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sat, 30 Aug 2003 02:56:12 +0000 Subject: 2003-08-29 Havoc Pennington * dbus/dbus-object-tree.c: modify to allow overlapping paths to be registered (struct DBusObjectSubtree): shrink this a lot, since we may have a lot of them (_dbus_object_tree_free_all_unlocked): implement (_dbus_object_tree_dispatch_and_unlock): implement --- dbus/dbus-object-tree.c | 547 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 428 insertions(+), 119 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 31724b7b..a2fc49e2 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -41,11 +41,11 @@ typedef struct DBusObjectSubtree DBusObjectSubtree; -DBusObjectSubtree* _dbus_object_subtree_new (const char **path, - const DBusObjectPathVTable *vtable, - void *user_data); -void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); -void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); +static DBusObjectSubtree* _dbus_object_subtree_new (const char **path, + const DBusObjectPathVTable *vtable, + void *user_data); +static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); +static void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); struct DBusObjectTree { @@ -63,11 +63,11 @@ struct DBusObjectTree struct DBusObjectSubtree { - int refcount; - char **path; - int n_path_elements; - DBusObjectPathVTable vtable; - void *user_data; + DBusAtomic refcount; + DBusObjectPathUnregisterFunction unregister_function; + DBusObjectPathMessageFunction message_function; + void *user_data; + char *path[1]; /**< Allocated as large as necessary */ }; DBusObjectTree* @@ -115,17 +115,9 @@ _dbus_object_tree_unref (DBusObjectTree *tree) if (tree->refcount == 0) { - if (tree->subtrees) - { - int i; - i = 0; - while (i < tree->n_subtrees) - { - _dbus_object_subtree_unref (tree->subtrees[i]); - ++i; - } - } + _dbus_object_tree_free_all_unlocked (tree); + dbus_free (tree->subtrees); dbus_free (tree); } } @@ -134,11 +126,10 @@ static int path_cmp (const char **path_a, const char **path_b) { - /* The comparison is as if the path were flattened - * into a single string. strcmp() considers - * a shorter string less than a longer string - * if the shorter string is the initial part - * of the longer + /* strcmp() considers a shorter string less than a longer string if + * the shorter string is the initial part of the longer. We + * consider a path with less elements less than a path with more + * elements. */ int i; @@ -187,28 +178,29 @@ subtree_qsort_cmp (const void *a, return subtree_cmp (*subtree_a_p, *subtree_b_p); } -/* Returns TRUE if a is a subdir of b or vice - * versa. This is the case if one is a subpath - * of the other. +/* Returns TRUE if container is a parent of child */ static dbus_bool_t -path_overlaps (const char **path_a, - const char **path_b) +path_contains (const char **container, + const char **child) { int i; i = 0; - while (path_a[i] != NULL) + while (child[i] != NULL) { int v; - if (path_b[i] == NULL) - return TRUE; /* b is subpath of a */ - - _dbus_assert (path_a[i] != NULL); - _dbus_assert (path_b[i] != NULL); + if (container[i] == NULL) + return TRUE; /* container ran out, child continues; + * thus the container is a parent of the + * child. + */ + + _dbus_assert (container[i] != NULL); + _dbus_assert (child[i] != NULL); - v = strcmp (path_a[i], path_b[i]); + v = strcmp (container[i], child[i]); if (v != 0) return FALSE; /* they overlap until here and then are different, @@ -218,9 +210,26 @@ path_overlaps (const char **path_a, ++i; } - /* b is either the same as or a superset of a */ - _dbus_assert (path_a[i] == NULL); - return TRUE; + /* Child ran out; if container also did, they are equal; + * otherwise, the child is a parent of the container. + */ + if (container[i] == NULL) + return TRUE; /* equal is counted as containing */ + else + return FALSE; +} + +static void +ensure_sorted (DBusObjectTree *tree) +{ + if (tree->subtrees && !tree->subtrees_sorted) + { + qsort (tree->subtrees, + tree->n_subtrees, + sizeof (DBusObjectSubtree*), + subtree_qsort_cmp); + tree->subtrees_sorted = TRUE; + } } static dbus_bool_t @@ -232,15 +241,8 @@ find_subtree (DBusObjectTree *tree, if (tree->subtrees == NULL) return FALSE; - - if (!tree->subtrees_sorted) - { - qsort (tree->subtrees, - tree->n_subtrees, - sizeof (DBusObjectSubtree*), - subtree_qsort_cmp); - tree->subtrees_sorted = TRUE; - } + + ensure_sorted (tree); /* FIXME this should be a binary search, * as that's the whole point of the sorting @@ -267,20 +269,60 @@ find_subtree (DBusObjectTree *tree, return FALSE; } +static dbus_bool_t +find_handler (DBusObjectTree *tree, + const char **path, + int *idx_p) +{ + int i; + int found_so_far; + + if (tree->subtrees == NULL) + return FALSE; + + ensure_sorted (tree); + + /* FIXME this should be a binary search, + * as that's the whole point of the sorting + */ + found_so_far = -1; + i = 0; + while (i < tree->n_subtrees) + { + /* Longer paths are after shorter, so we scan + * for the latest containing path in the array. + * If we did a binary search we'd start with + * the first search match. + */ + if (path_contains ((const char**) tree->subtrees[i]->path, + path)) + found_so_far = i; + else if (found_so_far >= 0) + break; /* no need to scan further */ + + ++i; + } + + if (idx_p) + *idx_p = found_so_far; + + return FALSE; +} + #ifndef DBUS_DISABLE_CHECKS static void -check_overlap (DBusObjectTree *tree, - const char **path) +check_already_exists (DBusObjectTree *tree, + const char **path) { int i; i = 0; while (i < tree->n_subtrees) { - if (path_overlaps (path, (const char**) tree->subtrees[i]->path)) + if (path_cmp (path, (const char**) tree->subtrees[i]->path) == 0) { - _dbus_warn ("New path (path[0] = %s) overlaps old path (path[0] = %s)\n", - path[0], tree->subtrees[i]->path[0]); + _dbus_warn ("New path (path[0] = %s) already registered\n", + path[0]); } ++i; } @@ -306,9 +348,11 @@ _dbus_object_tree_register (DBusObjectTree *tree, DBusObjectSubtree **new_subtrees; int new_n_subtrees; + _dbus_assert (tree != NULL); + _dbus_assert (vtable->message_function != NULL); _dbus_assert (path != NULL); #ifndef DBUS_DISABLE_CHECKS - check_overlap (tree, path); + check_already_exists (tree, path); #endif _dbus_assert (path[0] != NULL); @@ -319,10 +363,10 @@ _dbus_object_tree_register (DBusObjectTree *tree, /* FIXME we should do the "double alloc each time" standard thing */ new_n_subtrees = tree->n_subtrees + 1; new_subtrees = dbus_realloc (tree->subtrees, - new_n_subtrees); + new_n_subtrees * sizeof (DBusObjectSubtree*)); if (new_subtrees == NULL) { - _DBUS_ZERO (subtree->vtable); /* to avoid assertion in unref() */ + subtree->unregister_function = NULL; /* to avoid assertion in unref() */ _dbus_object_subtree_unref (subtree); return FALSE; } @@ -351,13 +395,15 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, _dbus_assert (path != NULL); _dbus_assert (path[0] != NULL); - + +#ifndef DBUS_DISABLE_CHECKS if (!find_subtree (tree, path, &i)) { _dbus_warn ("Attempted to unregister subtree (path[0] = %s) which isn't registered\n", path[0]); return; } +#endif subtree = tree->subtrees[i]; @@ -366,19 +412,21 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, &tree->subtrees[i+1], (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0])); tree->n_subtrees -= 1; - - _dbus_object_subtree_ref (subtree); + subtree->message_function = NULL; + /* Unlock and call application code */ _dbus_connection_unlock (tree->connection); - if (subtree->vtable.unregister_function) + if (subtree->unregister_function) { - (* subtree->vtable.unregister_function) (tree->connection, - (const char**) subtree->path, - subtree->user_data); - _DBUS_ZERO (subtree->vtable); + (* subtree->unregister_function) (tree->connection, + (const char**) subtree->path, + subtree->user_data); + subtree->unregister_function = NULL; } + + _dbus_object_subtree_unref (subtree); } /** @@ -392,15 +440,38 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, void _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) { + /* Delete them from the end, for slightly + * more robustness against odd reentrancy. + */ + while (tree->n_subtrees > 0) + { + DBusObjectSubtree *subtree; + subtree = tree->subtrees[tree->n_subtrees - 1]; + tree->subtrees[tree->n_subtrees - 1] = NULL; + subtree->message_function = NULL; /* it's been removed */ + /* Call application code */ + if (subtree->unregister_function) + { + (* subtree->unregister_function) (tree->connection, + (const char**) subtree->path, + subtree->user_data); + subtree->unregister_function = NULL; + } + + _dbus_object_subtree_unref (subtree); + } } /** - * Tries to dispatch a message by directing it to the object tree - * node listed in the message header, if any. + * Tries to dispatch a message by directing it to handler for the + * object path listed in the message header, if any. Messages are + * dispatched first to the registered handler that matches the largest + * number of path elements; that is, message to /foo/bar/baz would go + * to the handler for /foo/bar before the one for /foo. * - * @todo implement + * @todo thread problems * * @param tree the global object tree * @param message the message to dispatch @@ -410,70 +481,184 @@ DBusHandlerResult _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, DBusMessage *message) { + const char **path; + int i; + DBusList *list; + DBusList *link; + DBusHandlerResult result; + + path = NULL; /* dbus_message_get_object_path (message); */ + + if (path == NULL) + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + /* Find the deepest path that covers the path in the message */ + if (!find_handler (tree, path, &i)) + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + /* Build a list of all paths that cover the path in the message */ + + list = NULL; + + do + { + DBusObjectSubtree *subtree; + + subtree = tree->subtrees[i]; + + _dbus_object_subtree_ref (subtree); + _dbus_list_append (&list, subtree); + + --i; + + } while (i > 0 && path_contains ((const char**) tree->subtrees[i]->path, + path)); + + /* Invoke each handler in the list */ + + result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + link = _dbus_list_get_first_link (&list); + while (link != NULL) + { + DBusObjectSubtree *subtree = link->data; + DBusList *next = _dbus_list_get_next_link (&list, link); + + /* message_function is NULL if we're unregistered */ + if (subtree->message_function) + { + _dbus_connection_unlock (tree->connection); + + /* FIXME you could unregister the subtree in another thread + * before we invoke the callback, and I can't figure out a + * good way to solve this. + */ + + result = (* subtree->message_function) (tree->connection, + message, subtree->user_data); + + if (result == DBUS_HANDLER_RESULT_HANDLED) + goto free_and_return; + + _dbus_connection_lock (tree->connection); + } + + link = next; + } + + _dbus_connection_unlock (tree->connection); + + free_and_return: + while (list != NULL) + { + link = _dbus_list_get_first_link (&list); + _dbus_object_subtree_unref (link->data); + _dbus_list_remove_link (&list, link); + } + + return result; +} + +/** + * Allocates a subtree object with a string array appended as one big + * memory block, so result is freed with one dbus_free(). Returns + * #NULL if memory allocation fails. + * + * @param array array to duplicate. + * @returns newly-allocated subtree + */ +static DBusObjectSubtree* +allocate_subtree_object (const char **array) +{ + int len; + int member_lens; + int i; + char *p; + void *subtree; + char **path_dest; + const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, path); + if (array == NULL) + return NULL; + + member_lens = 0; + for (len = 0; array[len] != NULL; ++len) + member_lens += strlen (array[len]) + 1; + subtree = dbus_malloc (front_padding + + (len + 1) * sizeof (char*) + + member_lens); + if (subtree == NULL) + return NULL; + + path_dest = (char**) (((char*) subtree) + front_padding); + + path_dest[len] = NULL; /* NULL-terminate the array portion */ + p = ((char*) subtree) + (len + 1) * sizeof (char*) + front_padding; + + i = 0; + while (i < len) + { + int this_len; + + path_dest[i] = p; + + this_len = strlen (array[i]); + memcpy (p, array[i], this_len + 1); + p += this_len + 1; + + ++i; + } + + return subtree; } -DBusObjectSubtree* +static DBusObjectSubtree* _dbus_object_subtree_new (const char **path, const DBusObjectPathVTable *vtable, void *user_data) { DBusObjectSubtree *subtree; - subtree = dbus_new0 (DBusObjectSubtree, 1); + subtree = allocate_subtree_object (path); if (subtree == NULL) goto oom; _dbus_assert (path != NULL); _dbus_assert (path[0] != NULL); - - subtree->path = _dbus_dup_string_array (path); - if (subtree->path == NULL) - goto oom; - subtree->vtable = *vtable; + subtree->message_function = vtable->message_function; + subtree->unregister_function = vtable->unregister_function; subtree->user_data = user_data; - - subtree->refcount = 1; - - /* count path elements */ - while (subtree->path[subtree->n_path_elements]) - subtree->n_path_elements += 1; + subtree->refcount.value = 1; return subtree; oom: if (subtree) { - dbus_free_string_array (subtree->path); dbus_free (subtree); } return NULL; } -void +static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree) { - _dbus_assert (subtree->refcount > 0); - - subtree->refcount += 1; + _dbus_assert (subtree->refcount.value > 0); + _dbus_atomic_inc (&subtree->refcount); } -void +static void _dbus_object_subtree_unref (DBusObjectSubtree *subtree) { - _dbus_assert (subtree->refcount > 0); - - subtree->refcount -= 1; + _dbus_assert (subtree->refcount.value > 0); - if (subtree->refcount == 0) + if (_dbus_atomic_dec (&subtree->refcount) == 1) { - _dbus_assert (subtree->vtable.unregister_function == NULL); - - dbus_free_string_array (subtree->path); - + _dbus_assert (subtree->unregister_function == NULL); + _dbus_assert (subtree->message_function == NULL); dbus_free (subtree); } } @@ -484,6 +669,40 @@ _dbus_object_subtree_unref (DBusObjectSubtree *subtree) #include "dbus-test.h" #include +static char* +flatten_path (const char **path) +{ + DBusString str; + int i; + char *s; + + if (!_dbus_string_init (&str)) + return NULL; + + i = 0; + while (path[i]) + { + if (!_dbus_string_append_byte (&str, '/')) + goto nomem; + + if (!_dbus_string_append (&str, path[i])) + goto nomem; + + ++i; + } + + if (!_dbus_string_steal_data (&str, &s)) + goto nomem; + + _dbus_string_free (&str); + + return s; + + nomem: + _dbus_string_free (&str); + return NULL; +} + static dbus_bool_t test_subtree_cmp (const char **path1, const char **path2, @@ -531,12 +750,72 @@ test_subtree_cmp (const char **path1, } static void -test_path_overlap (const char **path1, - const char **path2, - dbus_bool_t expected) +test_path_contains (const char **path1, + const char **path2, + dbus_bool_t expected) +{ + if (!path_contains (path1, path2) == expected) + { + char *s1, *s2; + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s %s %s\n", + s1, expected ? "contains" : "doesn't contain", s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } + + if (path_cmp (path1, path2) == 0) + { + if (!path_contains (path2, path1)) + { + char *s1, *s2; + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s contains %s since the paths are equal\n", + s1, s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } + } + /* If path1 contains path2, then path2 can't contain path1 */ + else if (expected && path_contains (path2, path1)) + { + char *s1, *s2; + + s1 = flatten_path (path1); + s2 = flatten_path (path2); + + _dbus_warn ("Expected that path %s doesn't contain %s\n", + s1, s2); + + dbus_free (s1); + dbus_free (s2); + + exit (1); + } +} + +static void +test_path_copy (const char **path) { - _dbus_assert (path_overlaps (path1, path2) == expected); - _dbus_assert (path_overlaps (path2, path1) == expected); + DBusObjectSubtree *subtree; + + subtree = allocate_subtree_object (path); + if (subtree == NULL) + return; + + _dbus_assert (path_cmp (path, (const char**) subtree->path) == 0); + + dbus_free (subtree); } static dbus_bool_t @@ -547,33 +826,63 @@ object_tree_test_iteration (void *data) const char *path3[] = { "foo", "bar", "baz", NULL }; const char *path4[] = { "foo", "bar", "boo", NULL }; const char *path5[] = { "blah", NULL }; + const char *path6[] = { "blah", "boof", NULL }; DBusObjectSubtree *subtree1; DBusObjectSubtree *subtree2; DBusObjectTree *tree; + test_path_copy (path1); + test_path_copy (path2); + test_path_copy (path3); + test_path_copy (path4); + test_path_copy (path5); + test_path_copy (path6); + tree = NULL; subtree1 = NULL; subtree2 = NULL; - test_path_overlap (path1, path1, TRUE); - test_path_overlap (path1, path2, TRUE); - test_path_overlap (path1, path3, TRUE); - test_path_overlap (path1, path4, TRUE); - test_path_overlap (path1, path5, FALSE); - - test_path_overlap (path2, path2, TRUE); - test_path_overlap (path2, path3, TRUE); - test_path_overlap (path2, path4, TRUE); - test_path_overlap (path2, path5, FALSE); - - test_path_overlap (path3, path3, TRUE); - test_path_overlap (path3, path4, FALSE); - test_path_overlap (path3, path5, FALSE); - - test_path_overlap (path4, path4, TRUE); - test_path_overlap (path4, path5, FALSE); - - test_path_overlap (path5, path5, TRUE); + test_path_contains (path1, path1, TRUE); + test_path_contains (path1, path2, TRUE); + test_path_contains (path1, path3, TRUE); + test_path_contains (path1, path4, TRUE); + test_path_contains (path1, path5, FALSE); + test_path_contains (path1, path6, FALSE); + + test_path_contains (path2, path1, FALSE); + test_path_contains (path2, path2, TRUE); + test_path_contains (path2, path3, TRUE); + test_path_contains (path2, path4, TRUE); + test_path_contains (path2, path5, FALSE); + test_path_contains (path2, path6, FALSE); + + test_path_contains (path3, path1, FALSE); + test_path_contains (path3, path2, FALSE); + test_path_contains (path3, path3, TRUE); + test_path_contains (path3, path4, FALSE); + test_path_contains (path3, path5, FALSE); + test_path_contains (path3, path6, FALSE); + + test_path_contains (path4, path1, FALSE); + test_path_contains (path4, path2, FALSE); + test_path_contains (path4, path3, FALSE); + test_path_contains (path4, path4, TRUE); + test_path_contains (path4, path5, FALSE); + test_path_contains (path4, path6, FALSE); + + test_path_contains (path5, path1, FALSE); + test_path_contains (path5, path2, FALSE); + test_path_contains (path5, path3, FALSE); + test_path_contains (path5, path4, FALSE); + test_path_contains (path5, path5, TRUE); + test_path_contains (path5, path6, TRUE); + + test_path_contains (path6, path1, FALSE); + test_path_contains (path6, path2, FALSE); + test_path_contains (path6, path3, FALSE); + test_path_contains (path6, path4, FALSE); + test_path_contains (path6, path5, FALSE); + test_path_contains (path6, path6, TRUE); if (!test_subtree_cmp (path1, path1, 0, TRUE)) goto out; -- cgit From 9a0e83f509bd927b555ff75319f8df66ca61087e Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sat, 30 Aug 2003 17:09:24 +0000 Subject: 2003-08-30 Havoc Pennington * dbus/dbus-object-tree.c: write tests and fix the discovered bugs --- dbus/dbus-object-tree.c | 303 ++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 279 insertions(+), 24 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index a2fc49e2..379e2f04 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -254,18 +254,22 @@ find_subtree (DBusObjectTree *tree, v = path_cmp (path, (const char**) tree->subtrees[i]->path); + if (v == 0) { if (idx_p) *idx_p = i; + return TRUE; } - else if (v > 0) - return FALSE; + else if (v < 0) + { + return FALSE; + } ++i; } - + return FALSE; } @@ -366,12 +370,13 @@ _dbus_object_tree_register (DBusObjectTree *tree, new_n_subtrees * sizeof (DBusObjectSubtree*)); if (new_subtrees == NULL) { - subtree->unregister_function = NULL; /* to avoid assertion in unref() */ + subtree->unregister_function = NULL; + subtree->message_function = NULL; _dbus_object_subtree_unref (subtree); return FALSE; } - tree->subtrees[tree->n_subtrees] = subtree; + new_subtrees[tree->n_subtrees] = subtree; tree->subtrees_sorted = FALSE; tree->n_subtrees = new_n_subtrees; tree->subtrees = new_subtrees; @@ -396,15 +401,15 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, _dbus_assert (path != NULL); _dbus_assert (path[0] != NULL); -#ifndef DBUS_DISABLE_CHECKS if (!find_subtree (tree, path, &i)) { - _dbus_warn ("Attempted to unregister subtree (path[0] = %s) which isn't registered\n", - path[0]); + _dbus_warn ("Attempted to unregister path (path[0] = %s path[1] = %s) which isn't registered\n", + path[0], path[1] ? path[1] : "null"); return; } -#endif + _dbus_assert (i >= 0); + subtree = tree->subtrees[i]; /* assumes a 0-byte memmove is OK */ @@ -416,7 +421,10 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, subtree->message_function = NULL; /* Unlock and call application code */ - _dbus_connection_unlock (tree->connection); +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); if (subtree->unregister_function) { @@ -449,6 +457,8 @@ _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) subtree = tree->subtrees[tree->n_subtrees - 1]; tree->subtrees[tree->n_subtrees - 1] = NULL; + tree->n_subtrees -= 1; + subtree->message_function = NULL; /* it's been removed */ /* Call application code */ @@ -527,7 +537,10 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, /* message_function is NULL if we're unregistered */ if (subtree->message_function) { - _dbus_connection_unlock (tree->connection); +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); /* FIXME you could unregister the subtree in another thread * before we invoke the callback, and I can't figure out a @@ -539,14 +552,20 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, if (result == DBUS_HANDLER_RESULT_HANDLED) goto free_and_return; - - _dbus_connection_lock (tree->connection); + +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_lock (tree->connection); } link = next; } - - _dbus_connection_unlock (tree->connection); + +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); free_and_return: while (list != NULL) @@ -703,6 +722,29 @@ flatten_path (const char **path) return NULL; } +static void +spew_tree (DBusObjectTree *tree) +{ + int i; + + printf ("Tree of %d subpaths\n", + tree->n_subtrees); + + i = 0; + while (i < tree->n_subtrees) + { + char *s; + + s = flatten_path ((const char **) tree->subtrees[i]->path); + + printf (" %d path = %s\n", i, s); + + dbus_free (s); + + ++i; + } +} + static dbus_bool_t test_subtree_cmp (const char **path1, const char **path2, @@ -818,6 +860,56 @@ test_path_copy (const char **path) dbus_free (subtree); } +typedef struct +{ + dbus_bool_t message_handled; + dbus_bool_t handler_unregistered; + +} TreeTestData; + + +static void +test_unregister_function (DBusConnection *connection, + const char **path, + void *user_data) +{ + TreeTestData *ttd = user_data; + + ttd->handler_unregistered = TRUE; +} + +static DBusHandlerResult +test_message_function (DBusConnection *connection, + DBusMessage *message, + void *user_data) +{ + TreeTestData *ttd = user_data; + + ttd->message_handled = TRUE; + + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; +} + +static dbus_bool_t +do_register (DBusObjectTree *tree, + const char **path, + int i, + TreeTestData *tree_test_data) +{ + DBusObjectPathVTable vtable = { test_unregister_function, + test_message_function, NULL }; + + tree_test_data[i].message_handled = FALSE; + tree_test_data[i].handler_unregistered = FALSE; + + if (!_dbus_object_tree_register (tree, path, + &vtable, + &tree_test_data[i])) + return FALSE; + + return TRUE; +} + static dbus_bool_t object_tree_test_iteration (void *data) { @@ -827,10 +919,10 @@ object_tree_test_iteration (void *data) const char *path4[] = { "foo", "bar", "boo", NULL }; const char *path5[] = { "blah", NULL }; const char *path6[] = { "blah", "boof", NULL }; - DBusObjectSubtree *subtree1; - DBusObjectSubtree *subtree2; DBusObjectTree *tree; - + TreeTestData tree_test_data[6]; + int i; + test_path_copy (path1); test_path_copy (path2); test_path_copy (path3); @@ -839,8 +931,6 @@ object_tree_test_iteration (void *data) test_path_copy (path6); tree = NULL; - subtree1 = NULL; - subtree2 = NULL; test_path_contains (path1, path1, TRUE); test_path_contains (path1, path2, TRUE); @@ -905,12 +995,177 @@ object_tree_test_iteration (void *data) tree = _dbus_object_tree_new (NULL); if (tree == NULL) goto out; + + if (!do_register (tree, path1, 0, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + if (!do_register (tree, path2, 1, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + if (!do_register (tree, path3, 2, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + if (!do_register (tree, path4, 3, tree_test_data)) + goto out; + + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + if (!do_register (tree, path5, 4, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + if (!do_register (tree, path6, 5, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + /* Check that destroying tree calls unregister funcs */ + _dbus_object_tree_unref (tree); + + i = 0; + while (i < (int) _DBUS_N_ELEMENTS (tree_test_data)) + { + _dbus_assert (tree_test_data[i].handler_unregistered); + _dbus_assert (!tree_test_data[i].message_handled); + ++i; + } + /* Now start again and try the individual unregister function */ + tree = _dbus_object_tree_new (NULL); + if (tree == NULL) + goto out; + + if (!do_register (tree, path1, 0, tree_test_data)) + goto out; + if (!do_register (tree, path2, 1, tree_test_data)) + goto out; + if (!do_register (tree, path3, 2, tree_test_data)) + goto out; + if (!do_register (tree, path4, 3, tree_test_data)) + goto out; + if (!do_register (tree, path5, 4, tree_test_data)) + goto out; + if (!do_register (tree, path6, 5, tree_test_data)) + goto out; + + _dbus_object_tree_unregister_and_unlock (tree, path1); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path2); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path3); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path4); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path5); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path6); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + + i = 0; + while (i < (int) _DBUS_N_ELEMENTS (tree_test_data)) + { + _dbus_assert (tree_test_data[i].handler_unregistered); + _dbus_assert (!tree_test_data[i].message_handled); + ++i; + } + + /* Register it all again, and test dispatch */ + + if (!do_register (tree, path1, 0, tree_test_data)) + goto out; + if (!do_register (tree, path2, 1, tree_test_data)) + goto out; + if (!do_register (tree, path3, 2, tree_test_data)) + goto out; + if (!do_register (tree, path4, 3, tree_test_data)) + goto out; + if (!do_register (tree, path5, 4, tree_test_data)) + goto out; + if (!do_register (tree, path6, 5, tree_test_data)) + goto out; + + /* FIXME (once messages have an object path field) */ + out: - if (subtree1) - _dbus_object_subtree_unref (subtree1); - if (subtree2) - _dbus_object_subtree_unref (subtree2); if (tree) _dbus_object_tree_unref (tree); -- cgit From 5fd1e389e1c1c12ad4a55c2af6abdc8e7a2f6d41 Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sun, 31 Aug 2003 01:51:44 +0000 Subject: 2003-08-30 Havoc Pennington * test/data/valid-config-files/system.d/test.conf: change to root for the user so warnings don't get printed * dbus/dbus-message.c: add dbus_message_get_path, dbus_message_set_path * dbus/dbus-object-tree.c (do_test_dispatch): add test of dispatching to a path * dbus/dbus-string.c (_dbus_string_validate_path): add * dbus/dbus-marshal.c (_dbus_demarshal_object_path): implement (_dbus_marshal_object_path): implement * dbus/dbus-protocol.h (DBUS_HEADER_FIELD_PATH): new header field to contain the path to the target object (DBUS_HEADER_FIELD_SENDER_SERVICE): rename DBUS_HEADER_FIELD_SENDER to explicitly say it's the sender service --- dbus/dbus-object-tree.c | 1144 ++++++++++++++++++++++++++--------------------- 1 file changed, 623 insertions(+), 521 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 379e2f04..24e402a2 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -36,12 +36,18 @@ * Types and functions related to DBusObjectTree. These * are all internal. * + * @todo this is totally broken, because of the following case: + * /foo, /foo/bar, /foo/baz + * if we then receive a message to /foo/baz we need to hand it + * to /foo/baz and /foo but not /foo/bar. So we should be + * using a real tree structure as with GConfListeners. + * * @{ */ typedef struct DBusObjectSubtree DBusObjectSubtree; -static DBusObjectSubtree* _dbus_object_subtree_new (const char **path, +static DBusObjectSubtree* _dbus_object_subtree_new (const char *name, const DBusObjectPathVTable *vtable, void *user_data); static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); @@ -52,41 +58,42 @@ struct DBusObjectTree int refcount; DBusConnection *connection; - /* Each subtree is a separate malloc block since that - * lets us refcount them and maybe helps with - * reentrancy issues when calling back to application code - */ - DBusObjectSubtree **subtrees; - int n_subtrees; - unsigned int subtrees_sorted : 1; + DBusObjectSubtree *root; }; struct DBusObjectSubtree { DBusAtomic refcount; + DBusObjectSubtree *parent; DBusObjectPathUnregisterFunction unregister_function; DBusObjectPathMessageFunction message_function; void *user_data; - char *path[1]; /**< Allocated as large as necessary */ + DBusObjectSubtree **subtrees; + int n_subtrees; + unsigned int subtrees_sorted : 1; + char name[1]; /**< Allocated as large as necessary */ }; DBusObjectTree* _dbus_object_tree_new (DBusConnection *connection) { DBusObjectTree *tree; - + /* the connection passed in here isn't fully constructed, * so don't do anything more than store a pointer to * it */ - + tree = dbus_new0 (DBusObjectTree, 1); if (tree == NULL) goto oom; - + tree->refcount = 1; tree->connection = connection; - + tree->root = _dbus_object_subtree_new ("/", NULL, NULL); + if (tree->root == NULL) + goto oom; + return tree; oom: @@ -94,7 +101,7 @@ _dbus_object_tree_new (DBusConnection *connection) { dbus_free (tree); } - + return NULL; } @@ -117,55 +124,15 @@ _dbus_object_tree_unref (DBusObjectTree *tree) { _dbus_object_tree_free_all_unlocked (tree); - dbus_free (tree->subtrees); dbus_free (tree); } } -static int -path_cmp (const char **path_a, - const char **path_b) -{ - /* strcmp() considers a shorter string less than a longer string if - * the shorter string is the initial part of the longer. We - * consider a path with less elements less than a path with more - * elements. - */ - int i; - - i = 0; - while (path_a[i] != NULL) - { - int v; - - if (path_b[i] == NULL) - return 1; /* a is longer than b */ - - _dbus_assert (path_a[i] != NULL); - _dbus_assert (path_b[i] != NULL); - - v = strcmp (path_a[i], path_b[i]); - - if (v != 0) - return v; - - ++i; - } - - _dbus_assert (path_a[i] == NULL); - if (path_b[i] == NULL) - return 0; - - /* b is longer than a */ - return -1; -} - static int subtree_cmp (DBusObjectSubtree *subtree_a, DBusObjectSubtree *subtree_b) { - return path_cmp ((const char**) subtree_a->path, - (const char**) subtree_b->path); + return strcmp (subtree_a->name, subtree_b->name); } static int @@ -175,163 +142,198 @@ subtree_qsort_cmp (const void *a, DBusObjectSubtree **subtree_a_p = (void*) a; DBusObjectSubtree **subtree_b_p = (void*) b; - return subtree_cmp (*subtree_a_p, *subtree_b_p); -} - -/* Returns TRUE if container is a parent of child - */ -static dbus_bool_t -path_contains (const char **container, - const char **child) -{ - int i; - - i = 0; - while (child[i] != NULL) - { - int v; - - if (container[i] == NULL) - return TRUE; /* container ran out, child continues; - * thus the container is a parent of the - * child. - */ - - _dbus_assert (container[i] != NULL); - _dbus_assert (child[i] != NULL); - - v = strcmp (container[i], child[i]); - - if (v != 0) - return FALSE; /* they overlap until here and then are different, - * not overlapping - */ - - ++i; - } - - /* Child ran out; if container also did, they are equal; - * otherwise, the child is a parent of the container. - */ - if (container[i] == NULL) - return TRUE; /* equal is counted as containing */ - else - return FALSE; + return subtree_cmp (*subtree_a_p, *subtree_b_p); } static void -ensure_sorted (DBusObjectTree *tree) +ensure_sorted (DBusObjectSubtree *subtree) { - if (tree->subtrees && !tree->subtrees_sorted) + if (subtree->subtrees && !subtree->subtrees_sorted) { - qsort (tree->subtrees, - tree->n_subtrees, + qsort (subtree->subtrees, + subtree->n_subtrees, sizeof (DBusObjectSubtree*), subtree_qsort_cmp); - tree->subtrees_sorted = TRUE; + subtree->subtrees_sorted = TRUE; } } -static dbus_bool_t -find_subtree (DBusObjectTree *tree, - const char **path, - int *idx_p) +#define VERBOSE_FIND 0 + +static DBusObjectSubtree* +find_subtree_recurse (DBusObjectSubtree *subtree, + const char **path, + dbus_bool_t return_deepest_match, + dbus_bool_t create_if_not_found, + int *index_in_parent) { int i; - - if (tree->subtrees == NULL) - return FALSE; - ensure_sorted (tree); + _dbus_assert (!(return_deepest_match && create_if_not_found)); + + if (path[0] == NULL) + { +#if VERBOSE_FIND + _dbus_verbose (" path exhausted, returning %s\n", + subtree->name); +#endif + return subtree; + } - /* FIXME this should be a binary search, - * as that's the whole point of the sorting +#if VERBOSE_FIND + _dbus_verbose (" searching children of %s for %s\n", + subtree->name, path[0]); +#endif + + ensure_sorted (subtree); + + /* FIXME we should do a binary search here instead + * of O(n) */ + i = 0; - while (i < tree->n_subtrees) + while (i < subtree->n_subtrees) { int v; - v = path_cmp (path, - (const char**) tree->subtrees[i]->path); + v = strcmp (path[0], subtree->subtrees[i]->name); + +#if VERBOSE_FIND + _dbus_verbose (" %s cmp %s = %d\n", + path[0], subtree->subtrees[i]->name, + v); +#endif if (v == 0) { - if (idx_p) - *idx_p = i; - - return TRUE; + if (index_in_parent) + { +#if VERBOSE_FIND + _dbus_verbose (" storing parent index %d\n", i); +#endif + *index_in_parent = i; + } + + if (return_deepest_match) + { + DBusObjectSubtree *next; + + next = find_subtree_recurse (subtree->subtrees[i], + &path[1], return_deepest_match, + create_if_not_found, index_in_parent); + if (next == NULL) + { +#if VERBOSE_FIND + _dbus_verbose (" no deeper match found, returning %s\n", + subtree->name); +#endif + return subtree; + } + else + return next; + } + else + return find_subtree_recurse (subtree->subtrees[i], + &path[1], return_deepest_match, + create_if_not_found, index_in_parent); } else if (v < 0) { - return FALSE; + goto not_found; } - + ++i; } - - return FALSE; -} -static dbus_bool_t -find_handler (DBusObjectTree *tree, - const char **path, - int *idx_p) -{ - int i; - int found_so_far; - - if (tree->subtrees == NULL) - return FALSE; - - ensure_sorted (tree); + not_found: +#if VERBOSE_FIND + _dbus_verbose (" no match found, current tree %s, create_if_not_found = %d\n", + subtree->name, create_if_not_found); +#endif - /* FIXME this should be a binary search, - * as that's the whole point of the sorting - */ - found_so_far = -1; - i = 0; - while (i < tree->n_subtrees) + if (create_if_not_found) { - /* Longer paths are after shorter, so we scan - * for the latest containing path in the array. - * If we did a binary search we'd start with - * the first search match. - */ - if (path_contains ((const char**) tree->subtrees[i]->path, - path)) - found_so_far = i; - else if (found_so_far >= 0) - break; /* no need to scan further */ + DBusObjectSubtree* child; + DBusObjectSubtree **new_subtrees; + int new_n_subtrees; + +#if VERBOSE_FIND + _dbus_verbose (" creating subtree %s\n", + path[0]); +#endif - ++i; - } + child = _dbus_object_subtree_new (path[0], + NULL, NULL); + if (child == NULL) + return NULL; + + /* FIXME we should do the "double alloc each time" standard thing */ + new_n_subtrees = subtree->n_subtrees + 1; + new_subtrees = dbus_realloc (subtree->subtrees, + new_n_subtrees * sizeof (DBusObjectSubtree*)); + if (new_subtrees == NULL) + { + child->unregister_function = NULL; + child->message_function = NULL; + _dbus_object_subtree_unref (child); + return FALSE; + } - if (idx_p) - *idx_p = found_so_far; + new_subtrees[subtree->n_subtrees] = child; + if (index_in_parent) + *index_in_parent = subtree->n_subtrees; + subtree->subtrees_sorted = FALSE; + subtree->n_subtrees = new_n_subtrees; + subtree->subtrees = new_subtrees; - return FALSE; + child->parent = subtree; + + return find_subtree_recurse (child, + &path[1], return_deepest_match, + create_if_not_found, index_in_parent); + } + else + return return_deepest_match ? subtree : NULL; } -#ifndef DBUS_DISABLE_CHECKS -static void -check_already_exists (DBusObjectTree *tree, - const char **path) +static DBusObjectSubtree* +find_subtree (DBusObjectTree *tree, + const char **path, + int *index_in_parent) { - int i; + DBusObjectSubtree *subtree; - i = 0; - while (i < tree->n_subtrees) - { - if (path_cmp (path, (const char**) tree->subtrees[i]->path) == 0) - { - _dbus_warn ("New path (path[0] = %s) already registered\n", - path[0]); - } - ++i; - } +#if VERBOSE_FIND + _dbus_verbose ("Looking for exact registered subtree\n"); +#endif + + subtree = find_subtree_recurse (tree->root, path, FALSE, FALSE, index_in_parent); + + if (subtree && subtree->message_function == NULL) + return NULL; + else + return subtree; } + +static DBusObjectSubtree* +find_handler (DBusObjectTree *tree, + const char **path) +{ +#if VERBOSE_FIND + _dbus_verbose ("Looking for deepest handler\n"); #endif + return find_subtree_recurse (tree->root, path, TRUE, FALSE, NULL); +} + +static DBusObjectSubtree* +ensure_subtree (DBusObjectTree *tree, + const char **path) +{ +#if VERBOSE_FIND + _dbus_verbose ("Ensuring subtree\n"); +#endif + return find_subtree_recurse (tree->root, path, FALSE, TRUE, NULL); +} /** * Registers a new subtree in the global object tree. @@ -349,37 +351,25 @@ _dbus_object_tree_register (DBusObjectTree *tree, void *user_data) { DBusObjectSubtree *subtree; - DBusObjectSubtree **new_subtrees; - int new_n_subtrees; _dbus_assert (tree != NULL); - _dbus_assert (vtable->message_function != NULL); + _dbus_assert (vtable->message_function != NULL); _dbus_assert (path != NULL); -#ifndef DBUS_DISABLE_CHECKS - check_already_exists (tree, path); -#endif - _dbus_assert (path[0] != NULL); - - subtree = _dbus_object_subtree_new (path, vtable, user_data); + + subtree = ensure_subtree (tree, path); if (subtree == NULL) return FALSE; - - /* FIXME we should do the "double alloc each time" standard thing */ - new_n_subtrees = tree->n_subtrees + 1; - new_subtrees = dbus_realloc (tree->subtrees, - new_n_subtrees * sizeof (DBusObjectSubtree*)); - if (new_subtrees == NULL) + + if (subtree->message_function != NULL) { - subtree->unregister_function = NULL; - subtree->message_function = NULL; - _dbus_object_subtree_unref (subtree); + _dbus_warn ("A handler is already registered for the path starting with path[0] = \"%s\"\n", + path[0] ? path[0] : "null"); return FALSE; } - new_subtrees[tree->n_subtrees] = subtree; - tree->subtrees_sorted = FALSE; - tree->n_subtrees = new_n_subtrees; - tree->subtrees = new_subtrees; + subtree->message_function = vtable->message_function; + subtree->unregister_function = vtable->unregister_function; + subtree->user_data = user_data; return TRUE; } @@ -397,43 +387,102 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, { int i; DBusObjectSubtree *subtree; + DBusObjectPathUnregisterFunction unregister_function; + void *user_data; + DBusConnection *connection; _dbus_assert (path != NULL); - _dbus_assert (path[0] != NULL); - if (!find_subtree (tree, path, &i)) + subtree = find_subtree (tree, path, &i); + + if (subtree == NULL) { _dbus_warn ("Attempted to unregister path (path[0] = %s path[1] = %s) which isn't registered\n", - path[0], path[1] ? path[1] : "null"); + path[0] ? path[0] : "null", + path[1] ? path[1] : "null"); return; } - _dbus_assert (i >= 0); - - subtree = tree->subtrees[i]; - - /* assumes a 0-byte memmove is OK */ - memmove (&tree->subtrees[i], - &tree->subtrees[i+1], - (tree->n_subtrees - i - 1) * sizeof (tree->subtrees[0])); - tree->n_subtrees -= 1; + _dbus_assert (subtree->parent == NULL || + (i >= 0 && subtree->parent->subtrees[i] == subtree)); subtree->message_function = NULL; - + + unregister_function = subtree->unregister_function; + user_data = subtree->user_data; + + subtree->unregister_function = NULL; + subtree->user_data = NULL; + + /* If we have no subtrees of our own, remove from + * our parent (FIXME could also be more aggressive + * and remove our parent if it becomes empty) + */ + if (subtree->parent && subtree->n_subtrees == 0) + { + /* assumes a 0-byte memmove is OK */ + memmove (&subtree->parent->subtrees[i], + &subtree->parent->subtrees[i+1], + (subtree->parent->n_subtrees - i - 1) * + sizeof (subtree->parent->subtrees[0])); + subtree->parent->n_subtrees -= 1; + + subtree->parent = NULL; + + _dbus_object_subtree_unref (subtree); + } + subtree = NULL; + + connection = tree->connection; + /* Unlock and call application code */ #ifdef DBUS_BUILD_TESTS - if (tree->connection) + if (connection) #endif - _dbus_connection_unlock (tree->connection); - + { + _dbus_connection_ref_unlocked (connection); + _dbus_connection_unlock (connection); + } + + if (unregister_function) + (* unregister_function) (connection, user_data); + +#ifdef DBUS_BUILD_TESTS + if (connection) +#endif + dbus_connection_unref (connection); +} + +static void +free_subtree_recurse (DBusConnection *connection, + DBusObjectSubtree *subtree) +{ + /* Delete them from the end, for slightly + * more robustness against odd reentrancy. + */ + while (subtree->n_subtrees > 0) + { + DBusObjectSubtree *child; + + child = subtree->subtrees[subtree->n_subtrees - 1]; + subtree->subtrees[subtree->n_subtrees - 1] = NULL; + subtree->n_subtrees -= 1; + child->parent = NULL; + + free_subtree_recurse (connection, child); + } + + /* Call application code */ if (subtree->unregister_function) { - (* subtree->unregister_function) (tree->connection, - (const char**) subtree->path, + (* subtree->unregister_function) (connection, subtree->user_data); + subtree->message_function = NULL; subtree->unregister_function = NULL; + subtree->user_data = NULL; } + /* Now free ourselves */ _dbus_object_subtree_unref (subtree); } @@ -441,37 +490,15 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, * Free all the handlers in the tree. Lock on tree's connection * must not be held. * - * @todo implement - * * @param tree the object tree */ void _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) { - /* Delete them from the end, for slightly - * more robustness against odd reentrancy. - */ - while (tree->n_subtrees > 0) - { - DBusObjectSubtree *subtree; - - subtree = tree->subtrees[tree->n_subtrees - 1]; - tree->subtrees[tree->n_subtrees - 1] = NULL; - tree->n_subtrees -= 1; - - subtree->message_function = NULL; /* it's been removed */ - - /* Call application code */ - if (subtree->unregister_function) - { - (* subtree->unregister_function) (tree->connection, - (const char**) subtree->path, - subtree->user_data); - subtree->unregister_function = NULL; - } - - _dbus_object_subtree_unref (subtree); - } + if (tree->root) + free_subtree_recurse (tree->connection, + tree->root); + tree->root = NULL; } /** @@ -482,7 +509,7 @@ _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) * to the handler for /foo/bar before the one for /foo. * * @todo thread problems - * + * * @param tree the global object tree * @param message the message to dispatch * @returns whether message was handled successfully @@ -491,52 +518,82 @@ DBusHandlerResult _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, DBusMessage *message) { - const char **path; - int i; + char **path; DBusList *list; DBusList *link; DBusHandlerResult result; + DBusObjectSubtree *subtree; + +#if 0 + _dbus_verbose ("Dispatch of message by object path\n"); +#endif - path = NULL; /* dbus_message_get_object_path (message); */ + path = NULL; + if (!dbus_message_get_path_decomposed (message, &path)) + { + _dbus_verbose ("No memory to get decomposed path\n"); + return DBUS_HANDLER_RESULT_NEED_MEMORY; + } if (path == NULL) - return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + { + _dbus_verbose ("No path field in message\n"); + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + } /* Find the deepest path that covers the path in the message */ - if (!find_handler (tree, path, &i)) - return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + subtree = find_handler (tree, (const char**) path); /* Build a list of all paths that cover the path in the message */ - + list = NULL; - - do - { - DBusObjectSubtree *subtree; - subtree = tree->subtrees[i]; + while (subtree != NULL) + { + if (subtree->message_function != NULL) + { + _dbus_object_subtree_ref (subtree); + + /* run deepest paths first */ + if (!_dbus_list_append (&list, subtree)) + { + result = DBUS_HANDLER_RESULT_NEED_MEMORY; + _dbus_object_subtree_unref (subtree); + goto free_and_return; + } + } - _dbus_object_subtree_ref (subtree); - _dbus_list_append (&list, subtree); + subtree = subtree->parent; + } - --i; - - } while (i > 0 && path_contains ((const char**) tree->subtrees[i]->path, - path)); + _dbus_verbose ("%d handlers in the path tree for this message\n", + _dbus_list_get_length (&list)); /* Invoke each handler in the list */ - + result = DBUS_HANDLER_RESULT_NOT_YET_HANDLED; - + link = _dbus_list_get_first_link (&list); while (link != NULL) { - DBusObjectSubtree *subtree = link->data; DBusList *next = _dbus_list_get_next_link (&list, link); - - /* message_function is NULL if we're unregistered */ + subtree = link->data; + + /* message_function is NULL if we're unregistered + * due to reentrancy + */ if (subtree->message_function) { + DBusObjectPathMessageFunction message_function; + void *user_data; + + message_function = subtree->message_function; + user_data = subtree->user_data; + +#if 0 + _dbus_verbose (" (invoking a handler)\n"); +#endif + #ifdef DBUS_BUILD_TESTS if (tree->connection) #endif @@ -546,19 +603,20 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, * before we invoke the callback, and I can't figure out a * good way to solve this. */ - - result = (* subtree->message_function) (tree->connection, - message, subtree->user_data); - - if (result == DBUS_HANDLER_RESULT_HANDLED) + + result = (* message_function) (tree->connection, + message, + user_data); + + if (result != DBUS_HANDLER_RESULT_NOT_YET_HANDLED) goto free_and_return; #ifdef DBUS_BUILD_TESTS if (tree->connection) #endif _dbus_connection_lock (tree->connection); - } - + } + link = next; } @@ -574,82 +632,69 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, _dbus_object_subtree_unref (link->data); _dbus_list_remove_link (&list, link); } - + dbus_free_string_array (path); + return result; } /** - * Allocates a subtree object with a string array appended as one big - * memory block, so result is freed with one dbus_free(). Returns - * #NULL if memory allocation fails. + * Allocates a subtree object. * - * @param array array to duplicate. + * @param name name to duplicate. * @returns newly-allocated subtree */ static DBusObjectSubtree* -allocate_subtree_object (const char **array) +allocate_subtree_object (const char *name) { int len; - int member_lens; - int i; - char *p; - void *subtree; - char **path_dest; - const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, path); - - if (array == NULL) - return NULL; + DBusObjectSubtree *subtree; + const size_t front_padding = _DBUS_STRUCT_OFFSET (DBusObjectSubtree, name); - member_lens = 0; - for (len = 0; array[len] != NULL; ++len) - member_lens += strlen (array[len]) + 1; - - subtree = dbus_malloc (front_padding + - (len + 1) * sizeof (char*) + - member_lens); - if (subtree == NULL) - return NULL; + _dbus_assert (name != NULL); - path_dest = (char**) (((char*) subtree) + front_padding); - - path_dest[len] = NULL; /* NULL-terminate the array portion */ - p = ((char*) subtree) + (len + 1) * sizeof (char*) + front_padding; - - i = 0; - while (i < len) - { - int this_len; + len = strlen (name); - path_dest[i] = p; - - this_len = strlen (array[i]); - memcpy (p, array[i], this_len + 1); - p += this_len + 1; + subtree = dbus_malloc (front_padding + (len + 1)); - ++i; - } + if (subtree == NULL) + return NULL; + + memcpy (subtree->name, name, len + 1); return subtree; } static DBusObjectSubtree* -_dbus_object_subtree_new (const char **path, +_dbus_object_subtree_new (const char *name, const DBusObjectPathVTable *vtable, void *user_data) { DBusObjectSubtree *subtree; - subtree = allocate_subtree_object (path); + subtree = allocate_subtree_object (name); if (subtree == NULL) goto oom; - _dbus_assert (path != NULL); - _dbus_assert (path[0] != NULL); + _dbus_assert (name != NULL); + + subtree->parent = NULL; + + if (vtable) + { + subtree->message_function = vtable->message_function; + subtree->unregister_function = vtable->unregister_function; + } + else + { + subtree->message_function = NULL; + subtree->unregister_function = NULL; + } - subtree->message_function = vtable->message_function; - subtree->unregister_function = vtable->unregister_function; subtree->user_data = user_data; subtree->refcount.value = 1; + subtree->subtrees = NULL; + subtree->n_subtrees = 0; + subtree->subtrees_sorted = TRUE; return subtree; @@ -658,7 +703,7 @@ _dbus_object_subtree_new (const char **path, { dbus_free (subtree); } - + return NULL; } @@ -678,6 +723,8 @@ _dbus_object_subtree_unref (DBusObjectSubtree *subtree) { _dbus_assert (subtree->unregister_function == NULL); _dbus_assert (subtree->message_function == NULL); + + dbus_free (subtree->subtrees); dbus_free (subtree); } } @@ -694,7 +741,7 @@ flatten_path (const char **path) DBusString str; int i; char *s; - + if (!_dbus_string_init (&str)) return NULL; @@ -703,10 +750,10 @@ flatten_path (const char **path) { if (!_dbus_string_append_byte (&str, '/')) goto nomem; - + if (!_dbus_string_append (&str, path[i])) goto nomem; - + ++i; } @@ -714,154 +761,89 @@ flatten_path (const char **path) goto nomem; _dbus_string_free (&str); - + return s; - + nomem: _dbus_string_free (&str); return NULL; } -static void -spew_tree (DBusObjectTree *tree) +/* Returns TRUE if container is a parent of child + */ +static dbus_bool_t +path_contains (const char **container, + const char **child) { int i; - printf ("Tree of %d subpaths\n", - tree->n_subtrees); - i = 0; - while (i < tree->n_subtrees) + while (child[i] != NULL) { - char *s; - - s = flatten_path ((const char **) tree->subtrees[i]->path); - - printf (" %d path = %s\n", i, s); - - dbus_free (s); - - ++i; - } -} - -static dbus_bool_t -test_subtree_cmp (const char **path1, - const char **path2, - int expected, - dbus_bool_t reverse) -{ - DBusObjectSubtree *subtree1; - DBusObjectSubtree *subtree2; - dbus_bool_t retval; - DBusObjectPathVTable vtable; - - _DBUS_ZERO (vtable); - - retval = FALSE; - - subtree1 = _dbus_object_subtree_new (path1, &vtable, NULL); - subtree2 = _dbus_object_subtree_new (path2, &vtable, NULL); - if (subtree1 == NULL || subtree2 == NULL) - goto out; + int v; - _dbus_assert (subtree_cmp (subtree1, subtree2) == expected); + if (container[i] == NULL) + return TRUE; /* container ran out, child continues; + * thus the container is a parent of the + * child. + */ - retval = TRUE; - - out: + _dbus_assert (container[i] != NULL); + _dbus_assert (child[i] != NULL); - if (subtree1) - _dbus_object_subtree_unref (subtree1); + v = strcmp (container[i], child[i]); - if (subtree2) - _dbus_object_subtree_unref (subtree2); + if (v != 0) + return FALSE; /* they overlap until here and then are different, + * not overlapping + */ - if (retval && reverse) - { - /* Verify that the reverse also holds */ - if (expected > 0) - return test_subtree_cmp (path2, path1, -1, FALSE); - else if (expected < 0) - return test_subtree_cmp (path2, path1, 1, FALSE); - else - return test_subtree_cmp (path2, path1, 0, FALSE); + ++i; } - - return retval; + + /* Child ran out; if container also did, they are equal; + * otherwise, the child is a parent of the container. + */ + if (container[i] == NULL) + return TRUE; /* equal is counted as containing */ + else + return FALSE; } static void -test_path_contains (const char **path1, - const char **path2, - dbus_bool_t expected) +spew_subtree_recurse (DBusObjectSubtree *subtree, + int indent) { - if (!path_contains (path1, path2) == expected) - { - char *s1, *s2; - s1 = flatten_path (path1); - s2 = flatten_path (path2); - - _dbus_warn ("Expected that path %s %s %s\n", - s1, expected ? "contains" : "doesn't contain", s2); - - dbus_free (s1); - dbus_free (s2); - - exit (1); - } - - if (path_cmp (path1, path2) == 0) + int i; + + i = 0; + while (i < indent) { - if (!path_contains (path2, path1)) - { - char *s1, *s2; - s1 = flatten_path (path1); - s2 = flatten_path (path2); - - _dbus_warn ("Expected that path %s contains %s since the paths are equal\n", - s1, s2); - - dbus_free (s1); - dbus_free (s2); - - exit (1); - } + _dbus_verbose (" "); + ++i; } - /* If path1 contains path2, then path2 can't contain path1 */ - else if (expected && path_contains (path2, path1)) - { - char *s1, *s2; - s1 = flatten_path (path1); - s2 = flatten_path (path2); - - _dbus_warn ("Expected that path %s doesn't contain %s\n", - s1, s2); + _dbus_verbose ("%s (%d children)\n", + subtree->name, subtree->n_subtrees); - dbus_free (s1); - dbus_free (s2); - - exit (1); + i = 0; + while (i < subtree->n_subtrees) + { + spew_subtree_recurse (subtree->subtrees[i], indent + 2); + + ++i; } } static void -test_path_copy (const char **path) +spew_tree (DBusObjectTree *tree) { - DBusObjectSubtree *subtree; - - subtree = allocate_subtree_object (path); - if (subtree == NULL) - return; - - _dbus_assert (path_cmp (path, (const char**) subtree->path) == 0); - - dbus_free (subtree); + spew_subtree_recurse (tree->root, 0); } typedef struct { + const char **path; dbus_bool_t message_handled; dbus_bool_t handler_unregistered; @@ -870,7 +852,6 @@ typedef struct static void test_unregister_function (DBusConnection *connection, - const char **path, void *user_data) { TreeTestData *ttd = user_data; @@ -886,7 +867,7 @@ test_message_function (DBusConnection *connection, TreeTestData *ttd = user_data; ttd->message_handled = TRUE; - + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; } @@ -901,7 +882,8 @@ do_register (DBusObjectTree *tree, tree_test_data[i].message_handled = FALSE; tree_test_data[i].handler_unregistered = FALSE; - + tree_test_data[i].path = path; + if (!_dbus_object_tree_register (tree, path, &vtable, &tree_test_data[i])) @@ -910,6 +892,68 @@ do_register (DBusObjectTree *tree, return TRUE; } +static dbus_bool_t +do_test_dispatch (DBusObjectTree *tree, + const char **path, + int i, + TreeTestData *tree_test_data, + int n_test_data) +{ + DBusMessage *message; + int j; + DBusHandlerResult result; + char *flat; + + message = NULL; + + flat = flatten_path (path); + if (flat == NULL) + goto oom; + + message = dbus_message_new_method_call (NULL, + flat, + "org.freedesktop.TestInterface", + "Foo"); + dbus_free (flat); + if (message == NULL) + goto oom; + + j = 0; + while (j < n_test_data) + { + tree_test_data[j].message_handled = FALSE; + ++j; + } + + result = _dbus_object_tree_dispatch_and_unlock (tree, message); + if (result == DBUS_HANDLER_RESULT_NEED_MEMORY) + goto oom; + + _dbus_assert (tree_test_data[i].message_handled); + + j = 0; + while (j < n_test_data) + { + if (tree_test_data[j].message_handled) + _dbus_assert (path_contains (tree_test_data[j].path, + path)); + else + _dbus_assert (!path_contains (tree_test_data[j].path, + path)); + + ++j; + } + + dbus_message_unref (message); + + return TRUE; + + oom: + if (message) + dbus_message_unref (message); + return FALSE; +} + static dbus_bool_t object_tree_test_iteration (void *data) { @@ -919,103 +963,51 @@ object_tree_test_iteration (void *data) const char *path4[] = { "foo", "bar", "boo", NULL }; const char *path5[] = { "blah", NULL }; const char *path6[] = { "blah", "boof", NULL }; + const char *path7[] = { "blah", "boof", "this", "is", "really", "long", NULL }; + const char *path8[] = { "childless", NULL }; DBusObjectTree *tree; - TreeTestData tree_test_data[6]; + TreeTestData tree_test_data[8]; int i; - - test_path_copy (path1); - test_path_copy (path2); - test_path_copy (path3); - test_path_copy (path4); - test_path_copy (path5); - test_path_copy (path6); - + tree = NULL; - test_path_contains (path1, path1, TRUE); - test_path_contains (path1, path2, TRUE); - test_path_contains (path1, path3, TRUE); - test_path_contains (path1, path4, TRUE); - test_path_contains (path1, path5, FALSE); - test_path_contains (path1, path6, FALSE); - - test_path_contains (path2, path1, FALSE); - test_path_contains (path2, path2, TRUE); - test_path_contains (path2, path3, TRUE); - test_path_contains (path2, path4, TRUE); - test_path_contains (path2, path5, FALSE); - test_path_contains (path2, path6, FALSE); - - test_path_contains (path3, path1, FALSE); - test_path_contains (path3, path2, FALSE); - test_path_contains (path3, path3, TRUE); - test_path_contains (path3, path4, FALSE); - test_path_contains (path3, path5, FALSE); - test_path_contains (path3, path6, FALSE); - - test_path_contains (path4, path1, FALSE); - test_path_contains (path4, path2, FALSE); - test_path_contains (path4, path3, FALSE); - test_path_contains (path4, path4, TRUE); - test_path_contains (path4, path5, FALSE); - test_path_contains (path4, path6, FALSE); - - test_path_contains (path5, path1, FALSE); - test_path_contains (path5, path2, FALSE); - test_path_contains (path5, path3, FALSE); - test_path_contains (path5, path4, FALSE); - test_path_contains (path5, path5, TRUE); - test_path_contains (path5, path6, TRUE); - - test_path_contains (path6, path1, FALSE); - test_path_contains (path6, path2, FALSE); - test_path_contains (path6, path3, FALSE); - test_path_contains (path6, path4, FALSE); - test_path_contains (path6, path5, FALSE); - test_path_contains (path6, path6, TRUE); - - if (!test_subtree_cmp (path1, path1, 0, TRUE)) - goto out; - if (!test_subtree_cmp (path3, path3, 0, TRUE)) - goto out; - /* When testing -1, the reverse also gets tested */ - if (!test_subtree_cmp (path1, path2, -1, TRUE)) - goto out; - if (!test_subtree_cmp (path1, path3, -1, TRUE)) - goto out; - if (!test_subtree_cmp (path2, path3, -1, TRUE)) - goto out; - if (!test_subtree_cmp (path2, path4, -1, TRUE)) - goto out; - if (!test_subtree_cmp (path3, path4, -1, TRUE)) - goto out; - if (!test_subtree_cmp (path5, path1, -1, TRUE)) - goto out; - tree = _dbus_object_tree_new (NULL); if (tree == NULL) goto out; - + if (!do_register (tree, path1, 0, tree_test_data)) goto out; - + _dbus_assert (find_subtree (tree, path1, NULL)); _dbus_assert (!find_subtree (tree, path2, NULL)); _dbus_assert (!find_subtree (tree, path3, NULL)); _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); - + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); + + _dbus_assert (find_handler (tree, path1)); + _dbus_assert (find_handler (tree, path2)); + _dbus_assert (find_handler (tree, path3)); + _dbus_assert (find_handler (tree, path4)); + _dbus_assert (find_handler (tree, path5) == tree->root); + _dbus_assert (find_handler (tree, path6) == tree->root); + _dbus_assert (find_handler (tree, path7) == tree->root); + _dbus_assert (find_handler (tree, path8) == tree->root); + if (!do_register (tree, path2, 1, tree_test_data)) goto out; - - _dbus_assert (find_subtree (tree, path1, NULL)); + + _dbus_assert (find_subtree (tree, path1, NULL)); _dbus_assert (find_subtree (tree, path2, NULL)); _dbus_assert (!find_subtree (tree, path3, NULL)); _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); - + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); + if (!do_register (tree, path3, 2, tree_test_data)) goto out; @@ -1025,17 +1017,20 @@ object_tree_test_iteration (void *data) _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); if (!do_register (tree, path4, 3, tree_test_data)) goto out; - _dbus_assert (find_subtree (tree, path1, NULL)); _dbus_assert (find_subtree (tree, path2, NULL)); - _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); if (!do_register (tree, path5, 4, tree_test_data)) goto out; @@ -1046,7 +1041,18 @@ object_tree_test_iteration (void *data) _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); + _dbus_assert (find_handler (tree, path1) != tree->root); + _dbus_assert (find_handler (tree, path2) != tree->root); + _dbus_assert (find_handler (tree, path3) != tree->root); + _dbus_assert (find_handler (tree, path4) != tree->root); + _dbus_assert (find_handler (tree, path5) != tree->root); + _dbus_assert (find_handler (tree, path6) != tree->root); + _dbus_assert (find_handler (tree, path7) != tree->root); + _dbus_assert (find_handler (tree, path8) == tree->root); + if (!do_register (tree, path6, 5, tree_test_data)) goto out; @@ -1056,7 +1062,42 @@ object_tree_test_iteration (void *data) _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); + + if (!do_register (tree, path7, 6, tree_test_data)) + goto out; + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); + + if (!do_register (tree, path8, 7, tree_test_data)) + goto out; + + _dbus_assert (find_subtree (tree, path1, NULL)); + _dbus_assert (find_subtree (tree, path2, NULL)); + _dbus_assert (find_subtree (tree, path3, NULL)); + _dbus_assert (find_subtree (tree, path4, NULL)); + _dbus_assert (find_subtree (tree, path5, NULL)); + _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); + + _dbus_assert (find_handler (tree, path1) != tree->root); + _dbus_assert (find_handler (tree, path2) != tree->root); + _dbus_assert (find_handler (tree, path3) != tree->root); + _dbus_assert (find_handler (tree, path4) != tree->root); + _dbus_assert (find_handler (tree, path5) != tree->root); + _dbus_assert (find_handler (tree, path6) != tree->root); + _dbus_assert (find_handler (tree, path7) != tree->root); + _dbus_assert (find_handler (tree, path8) != tree->root); + /* Check that destroying tree calls unregister funcs */ _dbus_object_tree_unref (tree); @@ -1072,7 +1113,7 @@ object_tree_test_iteration (void *data) tree = _dbus_object_tree_new (NULL); if (tree == NULL) goto out; - + if (!do_register (tree, path1, 0, tree_test_data)) goto out; if (!do_register (tree, path2, 1, tree_test_data)) @@ -1085,7 +1126,11 @@ object_tree_test_iteration (void *data) goto out; if (!do_register (tree, path6, 5, tree_test_data)) goto out; - + if (!do_register (tree, path7, 6, tree_test_data)) + goto out; + if (!do_register (tree, path8, 7, tree_test_data)) + goto out; + _dbus_object_tree_unregister_and_unlock (tree, path1); _dbus_assert (!find_subtree (tree, path1, NULL)); @@ -1094,7 +1139,9 @@ object_tree_test_iteration (void *data) _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); - + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); + _dbus_object_tree_unregister_and_unlock (tree, path2); _dbus_assert (!find_subtree (tree, path1, NULL)); @@ -1103,7 +1150,9 @@ object_tree_test_iteration (void *data) _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); - + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); + _dbus_object_tree_unregister_and_unlock (tree, path3); _dbus_assert (!find_subtree (tree, path1, NULL)); @@ -1112,6 +1161,8 @@ object_tree_test_iteration (void *data) _dbus_assert (find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); _dbus_object_tree_unregister_and_unlock (tree, path4); @@ -1121,6 +1172,8 @@ object_tree_test_iteration (void *data) _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); _dbus_object_tree_unregister_and_unlock (tree, path5); @@ -1130,6 +1183,8 @@ object_tree_test_iteration (void *data) _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); _dbus_object_tree_unregister_and_unlock (tree, path6); @@ -1139,6 +1194,30 @@ object_tree_test_iteration (void *data) _dbus_assert (!find_subtree (tree, path4, NULL)); _dbus_assert (!find_subtree (tree, path5, NULL)); _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path7); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (find_subtree (tree, path8, NULL)); + + _dbus_object_tree_unregister_and_unlock (tree, path8); + + _dbus_assert (!find_subtree (tree, path1, NULL)); + _dbus_assert (!find_subtree (tree, path2, NULL)); + _dbus_assert (!find_subtree (tree, path3, NULL)); + _dbus_assert (!find_subtree (tree, path4, NULL)); + _dbus_assert (!find_subtree (tree, path5, NULL)); + _dbus_assert (!find_subtree (tree, path6, NULL)); + _dbus_assert (!find_subtree (tree, path7, NULL)); + _dbus_assert (!find_subtree (tree, path8, NULL)); i = 0; while (i < (int) _DBUS_N_ELEMENTS (tree_test_data)) @@ -1149,7 +1228,7 @@ object_tree_test_iteration (void *data) } /* Register it all again, and test dispatch */ - + if (!do_register (tree, path1, 0, tree_test_data)) goto out; if (!do_register (tree, path2, 1, tree_test_data)) @@ -1162,13 +1241,36 @@ object_tree_test_iteration (void *data) goto out; if (!do_register (tree, path6, 5, tree_test_data)) goto out; + if (!do_register (tree, path7, 6, tree_test_data)) + goto out; + if (!do_register (tree, path8, 7, tree_test_data)) + goto out; + +#if 0 + spew_tree (tree); +#endif - /* FIXME (once messages have an object path field) */ + if (!do_test_dispatch (tree, path1, 0, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path2, 1, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path3, 2, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path4, 3, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path5, 4, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path6, 5, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path7, 6, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; + if (!do_test_dispatch (tree, path8, 7, tree_test_data, _DBUS_N_ELEMENTS (tree_test_data))) + goto out; out: if (tree) _dbus_object_tree_unref (tree); - + return TRUE; } @@ -1183,7 +1285,7 @@ _dbus_object_tree_test (void) _dbus_test_oom_handling ("object tree", object_tree_test_iteration, NULL); - + return TRUE; } -- cgit From 666fe95480c14d7cbf5143b1a4e1bf0558403d4d Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sat, 6 Sep 2003 18:21:00 +0000 Subject: 2003-09-06 Havoc Pennington * dbus/dbus-connection.c (dbus_connection_register_fallback): add this (dbus_connection_register_object_path): make this not handle messages to paths below the given path --- dbus/dbus-object-tree.c | 37 ++++++++++++++++++++++++++++--------- 1 file changed, 28 insertions(+), 9 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 24e402a2..8430b323 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -71,6 +71,7 @@ struct DBusObjectSubtree DBusObjectSubtree **subtrees; int n_subtrees; unsigned int subtrees_sorted : 1; + unsigned int invoke_as_fallback : 1; char name[1]; /**< Allocated as large as necessary */ }; @@ -93,7 +94,8 @@ _dbus_object_tree_new (DBusConnection *connection) tree->root = _dbus_object_subtree_new ("/", NULL, NULL); if (tree->root == NULL) goto oom; - + tree->root->invoke_as_fallback = TRUE; + return tree; oom: @@ -221,7 +223,8 @@ find_subtree_recurse (DBusObjectSubtree *subtree, next = find_subtree_recurse (subtree->subtrees[i], &path[1], return_deepest_match, create_if_not_found, index_in_parent); - if (next == NULL) + if (next == NULL && + subtree->invoke_as_fallback) { #if VERBOSE_FIND _dbus_verbose (" no deeper match found, returning %s\n", @@ -293,7 +296,7 @@ find_subtree_recurse (DBusObjectSubtree *subtree, create_if_not_found, index_in_parent); } else - return return_deepest_match ? subtree : NULL; + return (return_deepest_match && subtree->invoke_as_fallback) ? subtree : NULL; } static DBusObjectSubtree* @@ -339,6 +342,7 @@ ensure_subtree (DBusObjectTree *tree, * Registers a new subtree in the global object tree. * * @param tree the global object tree + * @param fallback #TRUE to handle messages to children of this path * @param path NULL-terminated array of path elements giving path to subtree * @param vtable the vtable used to traverse this subtree * @param user_data user data to pass to methods in the vtable @@ -346,6 +350,7 @@ ensure_subtree (DBusObjectTree *tree, */ dbus_bool_t _dbus_object_tree_register (DBusObjectTree *tree, + dbus_bool_t fallback, const char **path, const DBusObjectPathVTable *vtable, void *user_data) @@ -360,17 +365,22 @@ _dbus_object_tree_register (DBusObjectTree *tree, if (subtree == NULL) return FALSE; +#ifndef DBUS_DISABLE_CHECKS if (subtree->message_function != NULL) { _dbus_warn ("A handler is already registered for the path starting with path[0] = \"%s\"\n", path[0] ? path[0] : "null"); return FALSE; } +#else + _dbus_assert (subtree->message_function == NULL); +#endif subtree->message_function = vtable->message_function; subtree->unregister_function = vtable->unregister_function; subtree->user_data = user_data; - + subtree->invoke_as_fallback = fallback != FALSE; + return TRUE; } @@ -395,6 +405,7 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, subtree = find_subtree (tree, path, &i); +#ifndef DBUS_DISABLE_CHECKS if (subtree == NULL) { _dbus_warn ("Attempted to unregister path (path[0] = %s path[1] = %s) which isn't registered\n", @@ -402,6 +413,9 @@ _dbus_object_tree_unregister_and_unlock (DBusObjectTree *tree, path[1] ? path[1] : "null"); return; } +#else + _dbus_assert (subtree != NULL); +#endif _dbus_assert (subtree->parent == NULL || (i >= 0 && subtree->parent->subtrees[i] == subtree)); @@ -523,7 +537,7 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, DBusList *link; DBusHandlerResult result; DBusObjectSubtree *subtree; - + #if 0 _dbus_verbose ("Dispatch of message by object path\n"); #endif @@ -540,10 +554,10 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, _dbus_verbose ("No path field in message\n"); return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; } - + /* Find the deepest path that covers the path in the message */ subtree = find_handler (tree, (const char**) path); - + /* Build a list of all paths that cover the path in the message */ list = NULL; @@ -884,7 +898,7 @@ do_register (DBusObjectTree *tree, tree_test_data[i].handler_unregistered = FALSE; tree_test_data[i].path = path; - if (!_dbus_object_tree_register (tree, path, + if (!_dbus_object_tree_register (tree, TRUE, path, &vtable, &tree_test_data[i])) return FALSE; @@ -1269,7 +1283,12 @@ object_tree_test_iteration (void *data) out: if (tree) - _dbus_object_tree_unref (tree); + { + /* test ref */ + _dbus_object_tree_ref (tree); + _dbus_object_tree_unref (tree); + _dbus_object_tree_unref (tree); + } return TRUE; } -- cgit From 85ab0327d82e4945ad16630e583d8cc68df25a90 Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Sun, 7 Sep 2003 23:04:54 +0000 Subject: 2003-09-07 Havoc Pennington * Make Doxygen contented. --- dbus/dbus-object-tree.c | 60 ++++++++++++++++++++++++++++++++++++------------- 1 file changed, 45 insertions(+), 15 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 8430b323..9922dec4 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -45,6 +45,7 @@ * @{ */ +/** Subnode of the object hierarchy */ typedef struct DBusObjectSubtree DBusObjectSubtree; static DBusObjectSubtree* _dbus_object_subtree_new (const char *name, @@ -53,28 +54,43 @@ static DBusObjectSubtree* _dbus_object_subtree_new (const char static void _dbus_object_subtree_ref (DBusObjectSubtree *subtree); static void _dbus_object_subtree_unref (DBusObjectSubtree *subtree); +/** + * Internals of DBusObjectTree + */ struct DBusObjectTree { - int refcount; - DBusConnection *connection; + int refcount; /**< Reference count */ + DBusConnection *connection; /**< Connection this tree belongs to */ - DBusObjectSubtree *root; + DBusObjectSubtree *root; /**< Root of the tree ("/" node) */ }; +/** + * Struct representing a single registered subtree handler, or node + * that's a parent of a registered subtree handler. If + * message_function != NULL there's actually a handler at this node. + */ struct DBusObjectSubtree { - DBusAtomic refcount; - DBusObjectSubtree *parent; - DBusObjectPathUnregisterFunction unregister_function; - DBusObjectPathMessageFunction message_function; - void *user_data; - DBusObjectSubtree **subtrees; - int n_subtrees; - unsigned int subtrees_sorted : 1; - unsigned int invoke_as_fallback : 1; + DBusAtomic refcount; /**< Reference count */ + DBusObjectSubtree *parent; /**< Parent node */ + DBusObjectPathUnregisterFunction unregister_function; /**< Function to call on unregister */ + DBusObjectPathMessageFunction message_function; /**< Function to handle messages */ + void *user_data; /**< Data for functions */ + DBusObjectSubtree **subtrees; /**< Child nodes */ + int n_subtrees; /**< Number of child nodes */ + unsigned int subtrees_sorted : 1; /**< Whether children are sorted */ + unsigned int invoke_as_fallback : 1; /**< Whether to invoke message_function when child nodes don't handle the message */ char name[1]; /**< Allocated as large as necessary */ }; +/** + * Creates a new object tree, representing a mapping from paths + * to handler vtables. + * + * @param connection the connection this tree belongs to + * @returns the new tree or #NULL if no memory + */ DBusObjectTree* _dbus_object_tree_new (DBusConnection *connection) { @@ -107,6 +123,10 @@ _dbus_object_tree_new (DBusConnection *connection) return NULL; } +/** + * Increment the reference count + * @param tree the object tree + */ void _dbus_object_tree_ref (DBusObjectTree *tree) { @@ -115,6 +135,10 @@ _dbus_object_tree_ref (DBusObjectTree *tree) tree->refcount += 1; } +/** + * Decrement the reference count + * @param tree the object tree + */ void _dbus_object_tree_unref (DBusObjectTree *tree) { @@ -160,6 +184,9 @@ ensure_sorted (DBusObjectSubtree *subtree) } } +/** Set to 1 to get a bunch of debug spew about finding the + * subtree nodes + */ #define VERBOSE_FIND 0 static DBusObjectSubtree* @@ -855,11 +882,14 @@ spew_tree (DBusObjectTree *tree) spew_subtree_recurse (tree->root, 0); } +/** + * Callback data used in tests + */ typedef struct { - const char **path; - dbus_bool_t message_handled; - dbus_bool_t handler_unregistered; + const char **path; /**< Path */ + dbus_bool_t message_handled; /**< Gets set to true if message handler called */ + dbus_bool_t handler_unregistered; /**< gets set to true if handler is unregistered */ } TreeTestData; -- cgit From 583994cb3b7f5562fb7b8c37b4cb0d5af78e4ce2 Mon Sep 17 00:00:00 2001 From: Havoc Pennington Date: Wed, 17 Sep 2003 03:52:07 +0000 Subject: 2003-09-15 Havoc Pennington * dbus/dbus-pending-call.c: add the get/set object data boilerplate as for DBusConnection, etc. Use generic object data for the notify callback. * glib/dbus-gparser.c (parse_node): parse child nodes * tools/dbus-viewer.c: more hacking on the dbus-viewer * glib/dbus-gutils.c (_dbus_gutils_split_path): add a file to contain functions shared between the convenience lib and the installed lib * glib/Makefile.am (libdbus_glib_1_la_LDFLAGS): add -export-symbols-regex to the GLib library * dbus/dbus-object-tree.c (_dbus_object_tree_dispatch_and_unlock): fix the locking in here, and add a default handler for Introspect() that just returns sub-nodes. 2003-09-14 Havoc Pennington * glib/dbus-gthread.c (dbus_g_thread_init): rename to make g_foo rather than gfoo consistent * glib/dbus-gproxy.h: delete for now, move contents to dbus-glib.h, because the include files don't work right since we aren't in the dbus/ subdir. * glib/dbus-gproxy.c (dbus_gproxy_send): finish implementing (dbus_gproxy_end_call): finish (dbus_gproxy_begin_call): finish * glib/dbus-gmain.c (dbus_set_g_error): new * glib/dbus-gobject.c (handle_introspect): include information about child nodes in the introspection * dbus/dbus-connection.c (dbus_connection_list_registered): new function to help in implementation of introspection * dbus/dbus-object-tree.c (_dbus_object_tree_list_registered_and_unlock): new function 2003-09-12 Havoc Pennington * glib/dbus-gidl.h: add common base class for all the foo_info types * tools/dbus-viewer.c: add GTK-based introspection UI thingy similar to kdcop * test/Makefile.am: try test srcdir -ef . in addition to test srcdir = ., one of them should work (yeah lame) * glib/Makefile.am: build the "idl" parser stuff as a convenience library * glib/dbus-gparser.h: make description_load routines return NodeInfo* not Parser* * Makefile.am (SUBDIRS): build test dir after all library dirs * configure.in: add GTK+ detection --- dbus/dbus-object-tree.c | 164 ++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 152 insertions(+), 12 deletions(-) (limited to 'dbus/dbus-object-tree.c') diff --git a/dbus/dbus-object-tree.c b/dbus/dbus-object-tree.c index 9922dec4..07d3ae59 100644 --- a/dbus/dbus-object-tree.c +++ b/dbus/dbus-object-tree.c @@ -25,6 +25,7 @@ #include "dbus-internals.h" #include "dbus-hash.h" #include "dbus-protocol.h" +#include "dbus-string.h" #include #include @@ -34,13 +35,7 @@ * @brief DBusObjectTree is used by DBusConnection to track the object tree * * Types and functions related to DBusObjectTree. These - * are all internal. - * - * @todo this is totally broken, because of the following case: - * /foo, /foo/bar, /foo/baz - * if we then receive a message to /foo/baz we need to hand it - * to /foo/baz and /foo but not /foo/bar. So we should be - * using a real tree structure as with GConfListeners. + * are all library-internal. * * @{ */ @@ -542,6 +537,101 @@ _dbus_object_tree_free_all_unlocked (DBusObjectTree *tree) tree->root = NULL; } +static dbus_bool_t +_dbus_object_tree_list_registered_unlocked (DBusObjectTree *tree, + const char **parent_path, + char ***child_entries) +{ + DBusObjectSubtree *subtree; + char **retval; + + _dbus_assert (parent_path != NULL); + _dbus_assert (child_entries != NULL); + + *child_entries = NULL; + + subtree = find_subtree (tree, parent_path, NULL); + if (subtree == NULL) + { + retval = dbus_new0 (char *, 1); + if (retval == NULL) + goto out; + } + else + { + int i; + retval = dbus_new0 (char*, subtree->n_subtrees + 1); + if (retval == NULL) + goto out; + i = 0; + while (i < subtree->n_subtrees) + { + retval[i] = _dbus_strdup (subtree->subtrees[i]->name); + if (retval[i] == NULL) + { + dbus_free_string_array (retval); + retval = NULL; + goto out; + } + ++i; + } + } + + out: + + *child_entries = retval; + return retval != NULL; +} + +static DBusHandlerResult +handle_default_introspect_unlocked (DBusObjectTree *tree, + DBusMessage *message, + const char **path) +{ + DBusString xml; + DBusHandlerResult result; + char **children; + int i; + + if (!dbus_message_is_method_call (message, + DBUS_INTERFACE_ORG_FREEDESKTOP_INTROSPECTABLE, + "Introspect")) + return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; + + if (!_dbus_string_init (&xml)) + return DBUS_HANDLER_RESULT_NEED_MEMORY; + + result = DBUS_HANDLER_RESULT_NEED_MEMORY; + + children = NULL; + if (!_dbus_object_tree_list_registered_unlocked (tree, path, &children)) + goto out; + + if (!_dbus_string_append (&xml, "\n")) + goto out; + + i = 0; + while (children[i] != NULL) + { + if (!_dbus_string_append_printf (&xml, " \n", + children[i])) + goto out; + + ++i; + } + + if (!_dbus_string_append (&xml, "\n")) + goto out; + + result = DBUS_HANDLER_RESULT_HANDLED; + + out: + _dbus_string_free (&xml); + dbus_free_string_array (children); + + return result; +} + /** * Tries to dispatch a message by directing it to handler for the * object path listed in the message header, if any. Messages are @@ -572,12 +662,23 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, path = NULL; if (!dbus_message_get_path_decomposed (message, &path)) { +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); + _dbus_verbose ("No memory to get decomposed path\n"); + return DBUS_HANDLER_RESULT_NEED_MEMORY; } if (path == NULL) { +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); + _dbus_verbose ("No path field in message\n"); return DBUS_HANDLER_RESULT_NOT_YET_HANDLED; } @@ -649,30 +750,40 @@ _dbus_object_tree_dispatch_and_unlock (DBusObjectTree *tree, message, user_data); - if (result != DBUS_HANDLER_RESULT_NOT_YET_HANDLED) - goto free_and_return; - #ifdef DBUS_BUILD_TESTS if (tree->connection) #endif _dbus_connection_lock (tree->connection); + + if (result != DBUS_HANDLER_RESULT_NOT_YET_HANDLED) + goto free_and_return; } link = next; } + free_and_return: + + if (result == DBUS_HANDLER_RESULT_NOT_YET_HANDLED) + { + /* This hardcoded default handler does a minimal Introspect() + */ + result = handle_default_introspect_unlocked (tree, message, + (const char**) path); + } + #ifdef DBUS_BUILD_TESTS if (tree->connection) #endif _dbus_connection_unlock (tree->connection); - - free_and_return: + while (list != NULL) { link = _dbus_list_get_first_link (&list); _dbus_object_subtree_unref (link->data); _dbus_list_remove_link (&list, link); } + dbus_free_string_array (path); return result; @@ -770,6 +881,35 @@ _dbus_object_subtree_unref (DBusObjectSubtree *subtree) } } +/** + * Lists the registered fallback handlers and object path handlers at + * the given parent_path. The returned array should be freed with + * dbus_free_string_array(). + * + * @param connection the connection + * @param parent_path the path to list the child handlers of + * @param child_entries returns #NULL-terminated array of children + * @returns #FALSE if no memory to allocate the child entries + */ +dbus_bool_t +_dbus_object_tree_list_registered_and_unlock (DBusObjectTree *tree, + const char **parent_path, + char ***child_entries) +{ + dbus_bool_t result; + + result = _dbus_object_tree_list_registered_unlocked (tree, + parent_path, + child_entries); + +#ifdef DBUS_BUILD_TESTS + if (tree->connection) +#endif + _dbus_connection_unlock (tree->connection); + + return result; +} + /** @} */ #ifdef DBUS_BUILD_TESTS -- cgit