X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=dbus%2Fdbus-list.c;h=525e067868140df86d35c25e7f45ddc94d9578d8;hb=67f9cca382df0d03adfe6b619aa613d103fa77f6;hp=31e5ae3f4571f7fc990a599d5ea7f7b21be740c3;hpb=041b0767b284034aee09e9a0de2a3844b8cc546a;p=platform%2Fupstream%2Fdbus.git

diff --git a/dbus/dbus-list.c b/dbus/dbus-list.c
index 31e5ae3..525e067 100644
--- a/dbus/dbus-list.c
+++ b/dbus/dbus-list.c
@@ -1,9 +1,9 @@
-/* -*- mode: C; c-file-style: "gnu" -*- */
-/* dbus-list.c Generic linked list utility (internal to D-BUS implementation)
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+/* dbus-list.c Generic linked list utility (internal to D-Bus implementation)
  * 
  * Copyright (C) 2002  Red Hat, Inc.
  *
- * Licensed under the Academic Free License version 1.2
+ * 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
@@ -17,12 +17,15 @@
  * 
  * 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
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  *
  */
 
+#include <config.h>
 #include "dbus-internals.h"
 #include "dbus-list.h"
+#include "dbus-mempool.h"
+#include "dbus-threads-internal.h"
 
 /**
  * @defgroup DBusList Linked list
@@ -32,6 +35,9 @@
  * Types and functions related to DBusList.
  */
 
+/* Protected by _DBUS_LOCK (list) */
+static DBusMemPool *list_pool;
+
 /**
  * @defgroup DBusListInternals Linked list implementation details
  * @ingroup  DBusInternals
@@ -39,26 +45,66 @@
  *
  * The guts of DBusList.
  *
- * @todo should use a memory pool for the list nodes, to avoid
- * a memory allocation for every link.
  * @{
  */
 
+/* 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;
 
-  link = dbus_new0 (DBusList, 1);
-  link->data = data;
+  if (!_DBUS_LOCK (list))
+    return FALSE;
+
+  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_free (link);
+{  
+  if (!_DBUS_LOCK (list))
+    _dbus_assert_not_reached ("we should have initialized global locks "
+        "before we allocated a linked-list link");
+
+  if (_dbus_mem_pool_dealloc (list_pool, link))
+    {
+      _dbus_mem_pool_free (list_pool);
+      list_pool = NULL;
+    }
+  
+  _DBUS_UNLOCK (list);
 }
 
 static void
@@ -104,6 +150,25 @@ link_after (DBusList **list,
     }
 }
 
+#ifdef DBUS_ENABLE_STATS
+void
+_dbus_list_get_stats     (dbus_uint32_t *in_use_p,
+                          dbus_uint32_t *in_free_list_p,
+                          dbus_uint32_t *allocated_p)
+{
+  if (!_DBUS_LOCK (list))
+    {
+      *in_use_p = 0;
+      *in_free_list_p = 0;
+      *allocated_p = 0;
+      return;
+    }
+
+  _dbus_mem_pool_get_stats (list_pool, in_use_p, in_free_list_p, allocated_p);
+  _DBUS_UNLOCK (list);
+}
+#endif
+
 /** @} */
 
 /**
@@ -133,7 +198,7 @@ link_after (DBusList **list,
  * while (link != NULL)
  *   {
  *     printf ("value is %p\n", link->data);
- *     link = _dbus_list_get_next_link (&list);
+ *     link = _dbus_list_get_next_link (&link);
  *   }
  * @endcode
  *
@@ -155,7 +220,7 @@ link_after (DBusList **list,
  * while (link != NULL)
  *   {
  *     printf ("value is %p\n", link->data);
- *     link = _dbus_list_get_prev_link (&list);
+ *     link = _dbus_list_get_prev_link (&link);
  *   }
  * @endcode
  *
@@ -166,6 +231,33 @@ link_after (DBusList **list,
  */
 
 /**
+ * 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.
+ */
+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
+ */
+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.
@@ -212,32 +304,36 @@ _dbus_list_prepend (DBusList **list,
 }
 
 /**
- * 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
+ * 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.
  */
-dbus_bool_t
-_dbus_list_insert_before (DBusList **list,
-                          DBusList  *before_this_link,
-                          void      *data)
+void
+_dbus_list_append_link (DBusList **list,
+			DBusList *link)
 {
-  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;
+  _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.
+ */
+void
+_dbus_list_prepend_link (DBusList **list,
+			 DBusList *link)
+{
+  link_before (list, *list, link);
 }
 
 /**
@@ -270,6 +366,42 @@ _dbus_list_insert_after (DBusList **list,
 }
 
 /**
+ * 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
+ */
+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
+ */
+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.
@@ -301,20 +433,76 @@ _dbus_list_remove (DBusList **list,
 }
 
 /**
- * Removes a link from the list. This is a constant-time operation.
+ * 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 link the list link to remove.
+ * @param data the value to remove.
+ * @returns #TRUE if a value was found to remove.
+ */
+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.
+ * @returns the link if found
+ */
+DBusList*
+_dbus_list_find_last (DBusList **list,
+                      void      *data)
+{
+  DBusList *link;
+
+  link = _dbus_list_get_last_link (list);
+
+  while (link != NULL)
+    {
+      if (link->data == data)
+        return link;
+      
+      link = _dbus_list_get_prev_link (list, link);
+    }
+
+  return NULL;
+}
+
+/**
+ * Removes the given link from the list, but doesn't
+ * free it. _dbus_list_remove_link() both removes the
+ * link and also frees it.
+ *
+ * @param list the list
+ * @param link the link in the list
  */
 void
-_dbus_list_remove_link (DBusList **list,
-                        DBusList  *link)
+_dbus_list_unlink (DBusList **list,
+                   DBusList  *link)
 {
   if (link->next == link)
     {
       /* one-element list */
       *list = NULL;
-      free_link (link);
     }
   else
     {      
@@ -323,9 +511,24 @@ _dbus_list_remove_link (DBusList **list,
       
       if (*list == link)
         *list = link->next;
-
-      free_link (link);
     }
+
+  link->next = NULL;
+  link->prev = NULL;
+}
+
+/**
+ * Removes a link from the list. This is a constant-time operation.
+ *
+ * @param list address of the list head.
+ * @param link the list link to remove.
+ */
+void
+_dbus_list_remove_link (DBusList **list,
+                        DBusList  *link)
+{
+  _dbus_list_unlink (list, link);
+  free_link (link);
 }
 
 /**
@@ -415,6 +618,27 @@ _dbus_list_get_first (DBusList **list)
 }
 
 /**
+ * Removes the first link in the list and returns it.  This is a
+ * constant-time operation.
+ *
+ * @param list address of the list head.
+ * @returns the first link in the list, or #NULL for an empty list.
+ */
+DBusList*
+_dbus_list_pop_first_link (DBusList **list)
+{
+  DBusList *link;
+  
+  link = _dbus_list_get_first_link (list);
+  if (link == NULL)
+    return NULL;
+
+  _dbus_list_unlink (list, link);
+
+  return link;
+}
+
+/**
  * Removes the first value in the list and returns it.  This is a
  * constant-time operation.
  *
@@ -549,6 +773,19 @@ _dbus_list_foreach (DBusList          **list,
     }
 }
 
+/**
+ * Check whether length is exactly one.
+ *
+ * @param list the list
+ * @returns #TRUE if length is exactly one
+ */
+dbus_bool_t
+_dbus_list_length_is_one (DBusList **list)
+{
+  return (*list != NULL &&
+          (*list)->next == *list);
+}
+
 /** @} */
 
 #ifdef DBUS_BUILD_TESTS
@@ -584,6 +821,11 @@ verify_list (DBusList **list)
   while (link != *list);
 
   _dbus_assert (length == _dbus_list_get_length (list));
+
+  if (length == 1)
+    _dbus_assert (_dbus_list_length_is_one (list));
+  else
+    _dbus_assert (!_dbus_list_length_is_one (list));
 }
 
 static dbus_bool_t
@@ -787,6 +1029,58 @@ _dbus_list_test (void)
   _dbus_assert (list1 == NULL);
   _dbus_assert (list2 == NULL);
 
+  /* Test get_first_link, get_last_link, pop_first_link, pop_last_link */
+  
+  i = 0;
+  while (i < 10)
+    {
+      _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (i));
+      _dbus_list_prepend (&list2, _DBUS_INT_TO_POINTER (i));
+      ++i;
+    }
+
+  --i;
+  while (i >= 0)
+    {
+      DBusList *got_link1;
+      DBusList *got_link2;
+
+      DBusList *link2;
+      
+      void *data1_indirect;
+      void *data1;
+      void *data2;
+      
+      got_link1 = _dbus_list_get_last_link (&list1);
+      got_link2 = _dbus_list_get_first_link (&list2);
+
+      link2 = _dbus_list_pop_first_link (&list2);
+
+      _dbus_assert (got_link2 == link2);
+
+      data1_indirect = got_link1->data;
+      /* this call makes got_link1 invalid */
+      data1 = _dbus_list_pop_last (&list1);
+      _dbus_assert (data1 == data1_indirect);
+      data2 = link2->data;
+
+      _dbus_list_free_link (link2);
+      
+      _dbus_assert (_DBUS_POINTER_TO_INT (data1) == i);
+      _dbus_assert (_DBUS_POINTER_TO_INT (data2) == i);
+
+      verify_list (&list1);
+      verify_list (&list2);
+
+      _dbus_assert (is_ascending_sequence (&list1));
+      _dbus_assert (is_descending_sequence (&list2));
+      
+      --i;
+    }
+
+  _dbus_assert (list1 == NULL);
+  _dbus_assert (list2 == NULL);
+  
   /* Test iteration */
   
   i = 0;
@@ -829,10 +1123,22 @@ _dbus_list_test (void)
       link1 = _dbus_list_get_next_link (&list1, link1);
       ++i;
     }
-  
+
+  --i;
+  link1 = _dbus_list_get_last_link (&list1);
+  while (link1 != NULL)
+    {
+      verify_list (&link1); /* pretend this link is the head */
+
+      _dbus_assert (_DBUS_POINTER_TO_INT (link1->data) == i);
+      
+      link1 = _dbus_list_get_prev_link (&list1, link1);
+      --i;
+    }
+
   _dbus_list_clear (&list1);
   _dbus_list_clear (&list2);
-  
+
   /* Test remove */
   
   i = 0;
@@ -1000,31 +1306,6 @@ _dbus_list_test (void)
 
   _dbus_list_clear (&list1);
   _dbus_list_clear (&list2);
-  
-  /* insert_before on empty list */
-  _dbus_list_insert_before (&list1, NULL,
-                            _DBUS_INT_TO_POINTER (0));
-  verify_list (&list1);
-
-  /* inserting before first element */
-  _dbus_list_insert_before (&list1, list1,
-                            _DBUS_INT_TO_POINTER (2));
-  verify_list (&list1);
-  _dbus_assert (is_descending_sequence (&list1));
-
-  /* inserting in the middle */
-  _dbus_list_insert_before (&list1, list1->next,
-                            _DBUS_INT_TO_POINTER (1));
-  verify_list (&list1);
-  _dbus_assert (is_descending_sequence (&list1));  
-
-  /* using insert_before to append */
-  _dbus_list_insert_before (&list1, NULL,
-                            _DBUS_INT_TO_POINTER (-1));
-  verify_list (&list1);
-  _dbus_assert (is_descending_sequence (&list1));
-  
-  _dbus_list_clear (&list1);
 
   /* insert_after on empty list */
   _dbus_list_insert_after (&list1, NULL,
@@ -1051,6 +1332,18 @@ _dbus_list_test (void)
   
   _dbus_list_clear (&list1);
 
+  /* using remove_last */
+  _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (2));
+  _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (1));
+  _dbus_list_append (&list1, _DBUS_INT_TO_POINTER (3));
+
+  _dbus_list_remove_last (&list1, _DBUS_INT_TO_POINTER (2));
+  
+  verify_list (&list1);
+  _dbus_assert (is_ascending_sequence (&list1));
+  
+  _dbus_list_clear (&list1);
+  
   return TRUE;
 }