- add user feedback

[oweals/gnunet.git] / src / util / container_slist.c

diff --git a/src/util/container_slist.c b/src/util/container_slist.c
index 874068bdb942ce63865272f47a5faa2fb279f327..e75c695c51e56a43082245ddcf3d1da252d1106f 100644 (file)
--- a/src/util/container_slist.c
+++ b/src/util/container_slist.c
@@ -4,7 +4,7 @@
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
 
      GNUnet 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, or (at your
+     by the Free Software Foundation; either version 3, or (at your

      option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but
      option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but


@@ -27,26 +27,57 @@
 #include "platform.h"
 #include "gnunet_container_lib.h"
 
 #include "platform.h"
 #include "gnunet_container_lib.h"
 

+#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
+
+/**
+ * Element in our linked list.
+ */

 struct GNUNET_CONTAINER_SList_Elem
 {
 struct GNUNET_CONTAINER_SList_Elem
 {

+  /**
+   * This is a linked list.
+   */

   struct GNUNET_CONTAINER_SList_Elem *next;
   struct GNUNET_CONTAINER_SList_Elem *next;

-  const void *elem;
+
+  /**
+   * Application data stored at this element.
+   */
+  void *elem;
+
+  /**
+   * Number of bytes stored in elem.
+   */

   size_t len;
   size_t len;

-  int disp;
+
+  /**
+   * Disposition of the element.
+   */
+  enum GNUNET_CONTAINER_SListDisposition disp;

 };
 
 };
 

+
+/**
+ * Handle to a singly linked list
+ */

 struct GNUNET_CONTAINER_SList
 {
 struct GNUNET_CONTAINER_SList
 {

+  /**
+   * Head of the linked list.
+   */

   struct GNUNET_CONTAINER_SList_Elem *head;
   struct GNUNET_CONTAINER_SList_Elem *head;

+
+  /**
+   * Tail of the linked list.
+   */
+  struct GNUNET_CONTAINER_SList_Elem *tail;
+
+  /**
+   * Number of elements in the list.
+   */

   unsigned int length;
 };
 
   unsigned int length;
 };
 

-struct GNUNET_CONTAINER_SList_Iterator
-{
-  struct GNUNET_CONTAINER_SList *list;
-  struct GNUNET_CONTAINER_SList_Elem *last;
-  struct GNUNET_CONTAINER_SList_Elem *elem;
-};
+

 
 /**
  * Create a new element that is to be inserted into the list
 
 /**
  * Create a new element that is to be inserted into the list


@@ -57,21 +88,22 @@ struct GNUNET_CONTAINER_SList_Iterator
  * @return a new element
  */
 static struct GNUNET_CONTAINER_SList_Elem *
  * @return a new element
  */
 static struct GNUNET_CONTAINER_SList_Elem *

-create_elem (int disp, const void *buf, size_t len)
+create_elem (enum GNUNET_CONTAINER_SListDisposition disp, const void *buf,
+             size_t len)

 {
   struct GNUNET_CONTAINER_SList_Elem *e;
 
 {
   struct GNUNET_CONTAINER_SList_Elem *e;
 

-  if (disp == GNUNET_MEM_DISP_TRANSIENT)
-    {
-      e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
-      memcpy (&e[1], buf, len);
-      e->elem = (const void*) &e[1];
-    }
+  if (disp == GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT)
+  {
+    e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem) + len);
+    memcpy (&e[1], buf, len);
+    e->elem = (void *) &e[1];
+  }

   else
   else

-    {
-      e = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Elem));
-      e->elem = buf;
-    }
+  {
+    e = GNUNET_new (struct GNUNET_CONTAINER_SList_Elem);
+    e->elem = (void *) buf;
+  }

   e->disp = disp;
   e->len = len;
   return e;
   e->disp = disp;
   e->len = len;
   return e;


@@ -86,7 +118,8 @@ create_elem (int disp, const void *buf, size_t len)
  * @param len length of the buffer
  */
 void
  * @param len length of the buffer
  */
 void

-GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp,
+GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l,
+                            enum GNUNET_CONTAINER_SListDisposition disp,

                             const void *buf, size_t len)
 {
   struct GNUNET_CONTAINER_SList_Elem *e;
                             const void *buf, size_t len)
 {
   struct GNUNET_CONTAINER_SList_Elem *e;


@@ -94,10 +127,62 @@ GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp,
   e = create_elem (disp, buf, len);
   e->next = l->head;
   l->head = e;
   e = create_elem (disp, buf, len);
   e->next = l->head;
   l->head = e;

+  if (l->tail == NULL)
+    l->tail = e;
+  l->length++;
+}
+
+/**
+ * Add a new element to the end of the list
+ * @param l list
+ * @param disp memory disposition
+ * @param buf payload buffer
+ * @param len length of the buffer
+ */
+void
+GNUNET_CONTAINER_slist_add_end (struct GNUNET_CONTAINER_SList *l,
+                                enum GNUNET_CONTAINER_SListDisposition disp,
+                                const void *buf, size_t len)
+{
+  struct GNUNET_CONTAINER_SList_Elem *e;
+
+  e = create_elem (disp, buf, len);
+  if (l->tail != NULL)
+    l->tail->next = e;
+  if (l->head == NULL)
+    l->head = e;
+  l->tail = e;

   l->length++;
 }
 
 
   l->length++;
 }
 
 

+/**
+ * Append a singly linked list to another
+ * @param dst list to append to
+ * @param src source
+ */
+void
+GNUNET_CONTAINER_slist_append (struct GNUNET_CONTAINER_SList *dst,
+                               struct GNUNET_CONTAINER_SList *src)
+{
+  struct GNUNET_CONTAINER_SList_Iterator i;
+
+  for (i = GNUNET_CONTAINER_slist_begin (src);
+       GNUNET_CONTAINER_slist_end (&i) != GNUNET_YES;
+       GNUNET_CONTAINER_slist_next (&i))
+
+  {
+    GNUNET_CONTAINER_slist_add (dst,
+                                (i.elem->disp ==
+                                 GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC) ?
+                                GNUNET_CONTAINER_SLIST_DISPOSITION_STATIC :
+                                GNUNET_CONTAINER_SLIST_DISPOSITION_TRANSIENT,
+                                i.elem->elem, i.elem->len);
+  }
+  GNUNET_CONTAINER_slist_iter_destroy (&i);
+}
+
+

 /**
  * Create a new singly linked list
  * @return the new list
 /**
  * Create a new singly linked list
  * @return the new list


@@ -105,9 +190,10 @@ GNUNET_CONTAINER_slist_add (struct GNUNET_CONTAINER_SList *l, int disp,
 struct GNUNET_CONTAINER_SList *
 GNUNET_CONTAINER_slist_create ()
 {
 struct GNUNET_CONTAINER_SList *
 GNUNET_CONTAINER_slist_create ()
 {

-  return GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList));
+  return GNUNET_new (struct GNUNET_CONTAINER_SList);

 }
 
 }
 

+

 /**
  * Destroy a singly linked list
  * @param l the list to be destroyed
 /**
  * Destroy a singly linked list
  * @param l the list to be destroyed


@@ -125,14 +211,14 @@ GNUNET_CONTAINER_slist_destroy (struct GNUNET_CONTAINER_SList *l)
  * @param l list
  * @return iterator pointing to the beginning
  */
  * @param l list
  * @return iterator pointing to the beginning
  */

-struct GNUNET_CONTAINER_SList_Iterator *
+struct GNUNET_CONTAINER_SList_Iterator

 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
 {
 GNUNET_CONTAINER_slist_begin (struct GNUNET_CONTAINER_SList *l)
 {

-  struct GNUNET_CONTAINER_SList_Iterator *ret;
+  struct GNUNET_CONTAINER_SList_Iterator ret;

 
 

-  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_SList_Iterator));
-  ret->elem = l->head;
-  ret->list = l;
+  memset (&ret, 0, sizeof (ret));
+  ret.elem = l->head;
+  ret.list = l;

   return ret;
 }
 
   return ret;
 }
 


@@ -149,22 +235,26 @@ GNUNET_CONTAINER_slist_clear (struct GNUNET_CONTAINER_SList *l)
 
   e = l->head;
   while (e != NULL)
 
   e = l->head;
   while (e != NULL)

-    {
-      n = e->next;
-      GNUNET_free (e);
-      e = n;
-    }
+  {
+    n = e->next;
+    if (e->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
+      GNUNET_free (e->elem);
+    GNUNET_free (e);
+    e = n;
+  }

   l->head = NULL;
   l->head = NULL;

+  l->tail = NULL;

   l->length = 0;
 }
 
 
 /**
  * Check if a list contains a certain element
   l->length = 0;
 }
 
 
 /**
  * Check if a list contains a certain element

- *

  * @param l list
  * @param buf payload buffer to find
  * @param l list
  * @param buf payload buffer to find

- * @param lenght of the payload
+ * @param len length of the payload (number of bytes in buf)
+ *
+ * @return GNUNET_YES if found, GNUNET_NO otherwise

  */
 int
 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
  */
 int
 GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,


@@ -173,12 +263,37 @@ GNUNET_CONTAINER_slist_contains (const struct GNUNET_CONTAINER_SList *l,
   struct GNUNET_CONTAINER_SList_Elem *e;
 
   for (e = l->head; e != NULL; e = e->next)
   struct GNUNET_CONTAINER_SList_Elem *e;
 
   for (e = l->head; e != NULL; e = e->next)

-    if ( (e->len == len) && 
-        (memcmp (buf, e->elem, len) == 0) )
+    if ((e->len == len) && (memcmp (buf, e->elem, len) == 0))

       return GNUNET_YES;
   return GNUNET_NO;
 }
 
       return GNUNET_YES;
   return GNUNET_NO;
 }
 

+typedef int (*Comparator)(const void *,  size_t, const void *,  size_t);
+
+/**
+ * Check if a list contains a certain element
+ *
+ * @param l list
+ * @param buf payload buffer to find
+ * @param len length of the payload (number of bytes in buf)
+ * @param compare comparison function, should return 0 if compared elements match
+ *
+ * @return NULL if the 'buf' could not be found, pointer to the
+ *         list element, if found
+ */
+void *
+GNUNET_CONTAINER_slist_contains2 (const struct GNUNET_CONTAINER_SList *l,
+                                  const void *buf, size_t len,
+                                  Comparator compare)
+{
+  struct GNUNET_CONTAINER_SList_Elem *e;
+
+  for (e = l->head; e != NULL; e = e->next)
+    if ((e->len == len) && (*compare)(buf, len, e->elem, e->len) == 0)
+      return e->elem;
+  return NULL;
+}
+

 
 /**
  * Count the elements of a list
 
 /**
  * Count the elements of a list


@@ -207,6 +322,10 @@ GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
     i->last->next = next;
   else
     i->list->head = next;
     i->last->next = next;
   else
     i->list->head = next;

+  if (next == NULL)
+    i->list->tail = i->last;
+  if (i->elem->disp == GNUNET_CONTAINER_SLIST_DISPOSITION_DYNAMIC)
+    GNUNET_free (i->elem->elem);

   GNUNET_free (i->elem);
   i->list->length--;
   i->elem = next;
   GNUNET_free (i->elem);
   i->list->length--;
   i->elem = next;


@@ -222,7 +341,8 @@ GNUNET_CONTAINER_slist_erase (struct GNUNET_CONTAINER_SList_Iterator *i)
  */
 void
 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
  */
 void
 GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,

-                               int disp, const void *buf, size_t len)
+                               enum GNUNET_CONTAINER_SListDisposition disp,
+                               const void *buf, size_t len)

 {
   struct GNUNET_CONTAINER_SList_Elem *e;
 
 {
   struct GNUNET_CONTAINER_SList_Elem *e;
 


@@ -232,6 +352,8 @@ GNUNET_CONTAINER_slist_insert (struct GNUNET_CONTAINER_SList_Iterator *before,
     before->last->next = e;
   else
     before->list->head = e;
     before->last->next = e;
   else
     before->list->head = e;

+  if (e->next == NULL)
+    before->list->tail = e;

   before->list->length++;
 }
 
   before->list->length++;
 }
 


@@ -271,7 +393,7 @@ GNUNET_CONTAINER_slist_end (struct GNUNET_CONTAINER_SList_Iterator *i)
  * @param len payload length
  * @return payload
  */
  * @param len payload length
  * @return payload
  */

-const void *
+void *

 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
                             size_t * len)
 {
 GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
                             size_t * len)
 {


@@ -280,4 +402,13 @@ GNUNET_CONTAINER_slist_get (const struct GNUNET_CONTAINER_SList_Iterator *i,
   return i->elem->elem;
 }
 
   return i->elem->elem;
 }
 

+/**
+ * Release an iterator
+ * @param i iterator
+ */
+void
+GNUNET_CONTAINER_slist_iter_destroy (struct GNUNET_CONTAINER_SList_Iterator *i)
+{
+}
+

 /* end of container_slist.c */
 /* end of container_slist.c */