/* -*- mode: C; c-file-style: "gnu" -*- */

/* dbus-object-tree.c  DBusObjectTree (internals of DBusConnection)

 *

 * Copyright (C) 2003, 2005  Red Hat Inc.

 * Portion Copyright © 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

 * Licensed under the Academic Free License version 2.1

 *

 * 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 "dbus-string.h"

#include <string.h>

#include <stdlib.h>

/**

 * @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 library-internal.

 *

 * @{

 */

/** Subnode of the object hierarchy */

typedef struct DBusObjectSubtree DBusObjectSubtree;

static DBusObjectSubtree* _dbus_object_subtree_new   (const char                  *name,

                                                      const DBusObjectPathVTable  *vtable,

                                                      void                        *user_data);

static DBusObjectSubtree* _dbus_object_subtree_ref   (DBusObjectSubtree           *subtree);

static void               _dbus_object_subtree_unref (DBusObjectSubtree           *subtree);

/**

 * Internals of DBusObjectTree

 */

struct DBusObjectTree

{

  int                 refcount;   /**< Reference count */

  DBusConnection     *connection; /**< Connection this tree belongs to */

  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;            /**< 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 */

  int                                max_subtrees;        /**< Number of allocated entries in subtrees */

  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)

{

  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;

  tree->root->invoke_as_fallback = TRUE;

  return tree;

 oom:

  if (tree)

    {

      dbus_free (tree);

    }

  return NULL;

}

/**

 * Increment the reference count

 * @param tree the object tree

 * @returns the object tree

 */

DBusObjectTree *

_dbus_object_tree_ref (DBusObjectTree *tree)

{

  _dbus_assert (tree->refcount > 0);

  tree->refcount += 1;

  return tree;

}

/**

 * Decrement the reference count

 * @param tree the object tree

 */

void

_dbus_object_tree_unref (DBusObjectTree *tree)

{

  _dbus_assert (tree->refcount > 0);

  tree->refcount -= 1;

  if (tree->refcount == 0)

    {

      _dbus_object_tree_free_all_unlocked (tree);

      dbus_free (tree);

    }

}

/** Set to 1 to get a bunch of debug spew about finding the

 * subtree nodes

 */

#define VERBOSE_FIND 0

static DBusObjectSubtree*

find_subtree_recurse (DBusObjectSubtree  *subtree,

                      const char        **path,

                      dbus_bool_t         create_if_not_found,

                      int                *index_in_parent,

                      dbus_bool_t        *exact_match)

{

  int i, j;

  dbus_bool_t return_deepest_match;

  return_deepest_match = exact_match != NULL;

  _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

      if (exact_match != NULL)

	*exact_match = TRUE;

      return subtree;

    }

#if VERBOSE_FIND

  _dbus_verbose ("  searching children of %s for %s\n",

                 subtree->name, path[0]);

#endif

  i = 0;

  j = subtree->n_subtrees;

  while (i < j)

    {

      int k, v;

      k = (i + j) / 2;

      v = strcmp (path[0], subtree->subtrees[k]->name);

#if VERBOSE_FIND

      _dbus_verbose ("  %s cmp %s = %d\n",

                     path[0], subtree->subtrees[k]->name,

                     v);

#endif

      if (v == 0)

        {

          if (index_in_parent)

            {

#if VERBOSE_FIND

              _dbus_verbose ("  storing parent index %d\n", k);

#endif

              *index_in_parent = k;

            }

          if (return_deepest_match)

            {

              DBusObjectSubtree *next;

              next = find_subtree_recurse (subtree->subtrees[k],

                                           &path[1], create_if_not_found, 

                                           index_in_parent, exact_match);

              if (next == NULL &&

                  subtree->invoke_as_fallback)

                {

#if VERBOSE_FIND

                  _dbus_verbose ("  no deeper match found, returning %s\n",

                                 subtree->name);

#endif

		  if (exact_match != NULL)

		    *exact_match = FALSE;

                  return subtree;

                }

              else

                return next;

            }

          else

            return find_subtree_recurse (subtree->subtrees[k],

                                         &path[1], create_if_not_found, 

                                         index_in_parent, exact_match);

        }

      else if (v < 0)

        {

          j = k;

        }

      else

        {

          i = k + 1;

        }

    }

#if VERBOSE_FIND

  _dbus_verbose ("  no match found, current tree %s, create_if_not_found = %d\n",

                 subtree->name, create_if_not_found);

#endif

  if (create_if_not_found)

    {

      DBusObjectSubtree* child;

      int child_pos, new_n_subtrees;

#if VERBOSE_FIND

      _dbus_verbose ("  creating subtree %s\n",

                     path[0]);

#endif

      child = _dbus_object_subtree_new (path[0],

                                        NULL, NULL);

      if (child == NULL)

        return NULL;

      new_n_subtrees = subtree->n_subtrees + 1;

      if (new_n_subtrees > subtree->max_subtrees)

        {

          int new_max_subtrees;

          DBusObjectSubtree **new_subtrees;

          new_max_subtrees = subtree->max_subtrees == 0 ? 1 : 2 * subtree->max_subtrees;

          new_subtrees = dbus_realloc (subtree->subtrees,

                                       new_max_subtrees * sizeof (DBusObjectSubtree*));

          if (new_subtrees == NULL)

            {

              _dbus_object_subtree_unref (child);

              return NULL;

            }

          subtree->subtrees = new_subtrees;

          subtree->max_subtrees = new_max_subtrees;

        }

      /* The binary search failed, so i == j points to the 

         place the child should be inserted. */

      child_pos = i;

      _dbus_assert (child_pos < new_n_subtrees &&

                    new_n_subtrees <= subtree->max_subtrees);

      if (child_pos + 1 < new_n_subtrees)

	{

	  memmove (&subtree->subtrees[child_pos+1], 

		   &subtree->subtrees[child_pos], 

		   (new_n_subtrees - child_pos - 1) * 

		   sizeof subtree->subtrees[0]);

	}

      subtree->subtrees[child_pos] = child;

      if (index_in_parent)

        *index_in_parent = child_pos;

      subtree->n_subtrees = new_n_subtrees;

      child->parent = subtree;

      return find_subtree_recurse (child,

                                   &path[1], create_if_not_found, 

                                   index_in_parent, exact_match);

    }

  else

    {

      if (exact_match != NULL)

	*exact_match = FALSE;

      return (return_deepest_match && subtree->invoke_as_fallback) ? subtree : NULL;

    }

}

static DBusObjectSubtree*

find_subtree (DBusObjectTree *tree,

              const char    **path,

              int            *index_in_parent)

{

  DBusObjectSubtree *subtree;

#if VERBOSE_FIND

  _dbus_verbose ("Looking for exact registered subtree\n");

#endif

  subtree = find_subtree_recurse (tree->root, path, FALSE, index_in_parent, NULL);

  if (subtree && subtree->message_function == NULL)

    return NULL;

  else

    return subtree;

}

static DBusObjectSubtree*

lookup_subtree (DBusObjectTree *tree,

                const char    **path)

{

#if VERBOSE_FIND

  _dbus_verbose ("Looking for subtree\n");

#endif

  return find_subtree_recurse (tree->root, path, FALSE, NULL, NULL);

}

static DBusObjectSubtree*

find_handler (DBusObjectTree *tree,

              const char    **path,

              dbus_bool_t    *exact_match)

{

#if VERBOSE_FIND

  _dbus_verbose ("Looking for deepest handler\n");

#endif

  _dbus_assert (exact_match != NULL);

  *exact_match = FALSE; /* ensure always initialized */

  return find_subtree_recurse (tree->root, path, FALSE, NULL, exact_match);

}

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, TRUE, NULL, NULL);

}

/**

 * 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

 * @returns #FALSE if not enough memory

 */

dbus_bool_t

_dbus_object_tree_register (DBusObjectTree              *tree,

                            dbus_bool_t                  fallback,

                            const char                 **path,

                            const DBusObjectPathVTable  *vtable,

                            void                        *user_data)

{

  DBusObjectSubtree  *subtree;

  _dbus_assert (tree != NULL);

  _dbus_assert (vtable->message_function != NULL);

  _dbus_assert (path != NULL);

  subtree = ensure_subtree (tree, path);

  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;

}

/**

 * 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;

  DBusObjectPathUnregisterFunction unregister_function;

  void *user_data;

  DBusConnection *connection;

  _dbus_assert (path != NULL);

  unregister_function = NULL;

  user_data = NULL;

  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",

                  path[0] ? path[0] : "null",

                  path[1] ? path[1] : "null");

      goto unlock;    

    }

#else

  _dbus_assert (subtree != NULL);

#endif

  _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;

unlock:

  connection = tree->connection;

  /* Unlock and call application code */

#ifdef DBUS_BUILD_TESTS

  if (connection)

#endif

    {

      _dbus_connection_ref_unlocked (connection);

      _dbus_verbose ("unlock %s\n", _DBUS_FUNCTION_NAME);

      _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);

    }