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

/* dbus-list.c Generic linked list utility (internal to D-Bus implementation)

 * 

 * Copyright (C) 2002  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-internals.h"

#include "dbus-list.h"

#include "dbus-mempool.h"

#include "dbus-threads-internal.h"

#ifdef __SYMBIAN32__

#include "libdbus_wsd_solution.h"

#endif

/**

 * @defgroup DBusList Linked list

 * @ingroup  DBusInternals

 * @brief DBusList data structure

 *

 * Types and functions related to DBusList.

 */

#if EMULATOR

GET_STATIC_VAR_FROM_TLS(list_pool,dbus_list,DBusMemPool *)

#define list_pool (*GET_DBUS_WSD_VAR_NAME(list_pool,dbus_list,s)())

#else

static DBusMemPool *list_pool;

#endif

#if EMULATOR

GET_GLOBAL_VAR_FROM_TLS(_dbus_lock_list,dbus_list,DBusMutex *)

#define _dbus_lock_list (*GET_DBUS_WSD_VAR_NAME(_dbus_lock_list,dbus_list,g)())

#else

_DBUS_DEFINE_GLOBAL_LOCK (list);

#endif

/**

 * @defgroup DBusListInternals Linked list implementation details

 * @ingroup  DBusInternals

 * @brief DBusList implementation details

 *

 * The guts of DBusList.

 *

 * @{

 */

/* the mem pool is probably a speed hit, with the thread

 * lock, though it does still save memory - unknown.

 */

static DBusList*

alloc_link (void *data)

{

  DBusList *link;

  _DBUS_LOCK (list);

  if (list_pool == NULL)

    {      

      list_pool = _dbus_mem_pool_new (sizeof (DBusList), TRUE);

      if (list_pool == NULL)

        {

          _DBUS_UNLOCK (list);

          return NULL;

        }

      link = _dbus_mem_pool_alloc (list_pool);

      if (link == NULL)

        {

          _dbus_mem_pool_free (list_pool);

          list_pool = NULL;

          _DBUS_UNLOCK (list);

          return NULL;

        }

    }

  else

    {

      link = _dbus_mem_pool_alloc (list_pool);

    }

  if (link)

    link->data = data;

  _DBUS_UNLOCK (list);

  return link;

}

static void

free_link (DBusList *link)

{  

  _DBUS_LOCK (list);

  if (_dbus_mem_pool_dealloc (list_pool, link))

    {

      _dbus_mem_pool_free (list_pool);

      list_pool = NULL;

    }

  _DBUS_UNLOCK (list);

}

static void

link_before (DBusList **list,

             DBusList  *before_this_link,

             DBusList  *link)

{

  if (*list == NULL)

    {

      link->prev = link;

      link->next = link;

      *list = link;

    }

  else

    {      

      link->next = before_this_link;

      link->prev = before_this_link->prev;

      before_this_link->prev = link;

      link->prev->next = link;

      if (before_this_link == *list)

        *list = link;

    }

}

static void

link_after (DBusList **list,

            DBusList  *after_this_link,

            DBusList  *link)

{

  if (*list == NULL)

    {

      link->prev = link;

      link->next = link;

      *list = link;

    }

  else

    {

      link->prev = after_this_link;

      link->next = after_this_link->next;

      after_this_link->next = link;

      link->next->prev = link;

    }

}

/** @} */

/**

 * @addtogroup DBusList

 * @{

 */

/**

 * @struct DBusList

 *

 * A node in a linked list.

 *

 * DBusList is a circular list; that is, the tail of the list

 * points back to the head of the list. The empty list is

 * represented by a #NULL pointer.

 */

/**

 * @def _dbus_list_get_next_link

 *

 * Gets the next link in the list, or #NULL if

 * there are no more links. Used for iteration.

 *

 * @code

 * DBusList *link;

 * link = _dbus_list_get_first_link (&list);

 * while (link != NULL)

 *   {

 *     printf ("value is %p\n", link->data);

 *     link = _dbus_list_get_next_link (&link);

 *   }

 * @endcode

 *

 * @param list address of the list head.

 * @param link current link.

 * @returns the next link, or %NULL if none.

 * 

 */

/**

 * @def _dbus_list_get_prev_link

 *

 * Gets the previous link in the list, or #NULL if

 * there are no more links. Used for iteration.

 *

 * @code

 * DBusList *link;

 * link = _dbus_list_get_last_link (&list);

 * while (link != NULL)

 *   {

 *     printf ("value is %p\n", link->data);

 *     link = _dbus_list_get_prev_link (&link);

 *   }

 * @endcode

 *

 * @param list address of the list head.

 * @param link current link.

 * @returns the previous link, or %NULL if none.

 * 

 */

/**

 * Allocates a linked list node. Useful for preallocating

 * nodes and using _dbus_list_append_link() to avoid

 * allocations.

 * 

 * @param data the value to store in the link.

 * @returns a newly allocated link.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

DBusList*

_dbus_list_alloc_link (void *data)

{

  return alloc_link (data);

}

/**

 * Frees a linked list node allocated with _dbus_list_alloc_link.

 * Does not free the data in the node.

 *

 * @param link the list node

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

void

_dbus_list_free_link (DBusList *link)

{

  free_link (link);

}

/**

 * Appends a value to the list. May return #FALSE

 * if insufficient memory exists to add a list link.

 * This is a constant-time operation.

 *

 * @param list address of the list head.

 * @param data the value to append.

 * @returns #TRUE on success.

 */

 #ifdef __SYMBIAN32__

 EXPORT_C

 #endif

dbus_bool_t

_dbus_list_append (DBusList **list,

                   void      *data)

{

  if (!_dbus_list_prepend (list, data))

    return FALSE;

  /* Now cycle the list forward one so the prepended node is the tail */

  *list = (*list)->next;

  return TRUE;

}

/**

 * Prepends a value to the list. May return #FALSE

 * if insufficient memory exists to add a list link.

 * This is a constant-time operation.

 *

 * @param list address of the list head.

 * @param data the value to prepend.

 * @returns #TRUE on success.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

dbus_bool_t

_dbus_list_prepend (DBusList **list,

                    void      *data)

{

  DBusList *link;

  link = alloc_link (data);

  if (link == NULL)

    return FALSE;

  link_before (list, *list, link);

  return TRUE;

}

/**

 * Appends a link to the list.

 * Cannot fail due to out of memory.

 * This is a constant-time operation.

 *

 * @param list address of the list head.

 * @param link the link to append.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

void

_dbus_list_append_link (DBusList **list,

			DBusList *link)

{

  _dbus_list_prepend_link (list, link);

  /* Now cycle the list forward one so the prepended node is the tail */

  *list = (*list)->next;

}

/**

 * Prepends a link to the list. 

 * Cannot fail due to out of memory.

 * This is a constant-time operation.

 *

 * @param list address of the list head.

 * @param link the link to prepend.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

void

_dbus_list_prepend_link (DBusList **list,

			 DBusList *link)

{

  link_before (list, *list, link);

}

#ifdef DBUS_BUILD_TESTS

/**

 * Inserts data into the list before the given existing link.

 * 

 * @param list the list to modify

 * @param before_this_link existing link to insert before, or #NULL to append

 * @param data the value to insert

 * @returns #TRUE on success, #FALSE if memory allocation fails

 */

dbus_bool_t

_dbus_list_insert_before (DBusList **list,

                          DBusList  *before_this_link,

                          void      *data)

{

  DBusList *link;

  if (before_this_link == NULL)

    return _dbus_list_append (list, data);

  else

    {

      link = alloc_link (data);

      if (link == NULL)

        return FALSE;

      link_before (list, before_this_link, link);

    }

  return TRUE;

}

#endif /* DBUS_BUILD_TESTS */

/**

 * Inserts data into the list after the given existing link.

 * 

 * @param list the list to modify

 * @param after_this_link existing link to insert after, or #NULL to prepend

 * @param data the value to insert

 * @returns #TRUE on success, #FALSE if memory allocation fails

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

dbus_bool_t

_dbus_list_insert_after (DBusList **list,

                         DBusList  *after_this_link,

                         void      *data)

{

  DBusList *link;  

  if (after_this_link == NULL)

    return _dbus_list_prepend (list, data);

  else

    {

      link = alloc_link (data);

      if (link == NULL)

        return FALSE;

      link_after (list, after_this_link, link);

    }

  return TRUE;

}

/**

 * Inserts a link into the list before the given existing link.

 * 

 * @param list the list to modify

 * @param before_this_link existing link to insert before, or #NULL to append

 * @param link the link to insert

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

void

_dbus_list_insert_before_link (DBusList **list,

                               DBusList  *before_this_link,

                               DBusList  *link)

{

  if (before_this_link == NULL)

    _dbus_list_append_link (list, link);

  else

    link_before (list, before_this_link, link);

}

/**

 * Inserts a link into the list after the given existing link.

 * 

 * @param list the list to modify

 * @param after_this_link existing link to insert after, or #NULL to prepend

 * @param link the link to insert

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

void

_dbus_list_insert_after_link (DBusList **list,

                              DBusList  *after_this_link,

                              DBusList  *link)

{

  if (after_this_link == NULL)

    _dbus_list_prepend_link (list, link);

  else  

    link_after (list, after_this_link, link);

}

/**

 * Removes a value from the list. Only removes the

 * first value equal to the given data pointer,

 * even if multiple values exist which match.

 * This is a linear-time operation.

 *

 * @param list address of the list head.

 * @param data the value to remove.

 * @returns #TRUE if a value was found to remove.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

dbus_bool_t

_dbus_list_remove (DBusList **list,

                   void      *data)

{

  DBusList *link;

  link = *list;

  while (link != NULL)

    {

      if (link->data == data)

        {

          _dbus_list_remove_link (list, link);

          return TRUE;

        }

      link = _dbus_list_get_next_link (list, link);

    }

  return FALSE;

}

/**

 * Removes a value from the list. Only removes the

 * last value equal to the given data pointer,

 * even if multiple values exist which match.

 * This is a linear-time operation.

 *

 * @param list address of the list head.

 * @param data the value to remove.

 * @returns #TRUE if a value was found to remove.

 */

#ifdef __SYMBIAN32__

EXPORT_C

#endif

dbus_bool_t

_dbus_list_remove_last (DBusList **list,

                        void      *data)

{

  DBusList *link;

  link = _dbus_list_find_last (list, data);

  if (link)

    {

      _dbus_list_remove_link (list, link);

      return TRUE;

    }

  else

    return FALSE;

}

/**

 * Finds a value in the list. Returns the last link

 * with value equal to the given data pointer.

 * This is a linear-time operation.

 * Returns #NULL if no value found that matches.

 *

 * @param list address of the list head.

 * @param data the value to find.