[SCM] GNU Mailutils branch, master, updated. release-3.1.1-20-gda63ec1

[Sergey Poznyakoff]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU Mailutils".

http://git.savannah.gnu.org/cgit/mailutils.git/commit/?id=da63ec15b4c8fb3084075730332a8d20a9af374f

The branch, master has been updated
       via  da63ec15b4c8fb3084075730332a8d20a9af374f (commit)
      from  eae41894c2614ddc2c3732014cb62bf68ab4e16a (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit da63ec15b4c8fb3084075730332a8d20a9af374f
Author: Sergey Poznyakoff <address@hidden>
Date:   Wed Dec 28 20:57:26 2016 +0200

    Provide sort function for associative arrays.
    
    The mu_assoc_sort_r call sorts the elements of mu_assoc_t for
    subsequent iterative access.  Random access facilities remain
    undistrurbed.
    
    * include/mailutils/assoc.h (mu_assoc_comparator_t): New typedef.
    (mu_assoc_sort_r): New proto.
    * libmailutils/base/assoc.c (mu_assoc_sort_r): New function.
    * libmailutils/tests/mimehdr.c: Sort assoc elements prior to
    iteration.

-----------------------------------------------------------------------

Summary of changes:
 include/mailutils/assoc.h     |    7 ++
 libmailutils/base/assoc.c     |  141 +++++++++++++++++++++++++++++++++++++----
 libmailutils/tests/.gitignore |    2 +
 libmailutils/tests/mimehdr.c  |   45 +++----------
 4 files changed, 144 insertions(+), 51 deletions(-)

diff --git a/include/mailutils/assoc.h b/include/mailutils/assoc.h
index 5db9f85..00514c0 100644
--- a/include/mailutils/assoc.h
+++ b/include/mailutils/assoc.h
@@ -46,6 +46,13 @@ int mu_assoc_is_empty (mu_assoc_t assoc);
 
 typedef int (*mu_assoc_action_t) (char const *, void *, void *);
 int mu_assoc_foreach (mu_assoc_t assoc, mu_assoc_action_t action, void *data);
+
+typedef int (*mu_assoc_comparator_t) (const char *, const void *,
+                                     const char *, const void *,
+                                     void *);
+
+int mu_assoc_sort_r (mu_assoc_t assoc, mu_assoc_comparator_t cmp, void *data);
+  
   
 #ifdef __cplusplus
 }
diff --git a/libmailutils/base/assoc.c b/libmailutils/base/assoc.c
index 8b42f82..d595ee8 100644
--- a/libmailutils/base/assoc.c
+++ b/libmailutils/base/assoc.c
@@ -625,20 +625,17 @@ mu_assoc_get_iterator (mu_assoc_t assoc, mu_iterator_t 
*piterator)
 int
 mu_assoc_count (mu_assoc_t assoc, size_t *pcount)
 {
-  mu_iterator_t itr;
-  int rc;
-  size_t count = 0;
-  
-  if (!assoc || !pcount)
-    return EINVAL;
-  rc = mu_assoc_get_iterator (assoc, &itr);
-  if (rc)
-    return rc;
-  for (mu_iterator_first (itr); !mu_iterator_is_done (itr);
-       mu_iterator_next (itr))
-    count++;
-  mu_iterator_destroy (&itr);
-  *pcount = count;
+  size_t length = 0;
+
+  if (!pcount)
+    return MU_ERR_OUT_PTR_NULL;
+  if (assoc)
+    {
+      struct _mu_assoc_elem *elt;
+      for (elt = assoc->head; elt; elt = elt->next)
+       length++;
+    }
+  *pcount = length;
   return 0;
 }
 
@@ -676,3 +673,119 @@ mu_assoc_foreach (mu_assoc_t assoc, mu_assoc_action_t 
action, void *data)
   mu_iterator_destroy (&itr);
   return rc;
 }
+
+/* Merges the two NULL-terminated lists, LEFT and RIGHT, using CMP for
+   element comparison.  DATA supplies call-specific data for CMP.
+
+   Both LEFT and RIGHT are treated as singly-linked lists, with NEXT pointing
+   to the successive element.  PREV pointers are ignored.
+   
+   Returns the resulting list.
+ */
+static struct _mu_assoc_elem *
+merge (struct _mu_assoc_elem *left, struct _mu_assoc_elem *right,
+       mu_assoc_comparator_t cmp, void *data)
+{
+  struct _mu_assoc_elem *head = NULL, **tailptr = &head, *tmp;
+
+  while (left && right)
+    {
+      if (cmp (left->name, left->data, right->name, right->data, data) < 0)
+       {
+         tmp = left->next;
+         *tailptr = left;
+         tailptr = &left->next;
+         left = tmp;
+       }
+      else
+       {
+         tmp = right->next;
+         *tailptr = right;
+         tailptr = &right->next;
+         right = tmp;
+       }
+    }
+
+  *tailptr = left ? left : right;
+
+  return head;
+}
+
+/* Sort the singly-linked LIST of LENGTH elements using merge sort algorithm.
+   Elements are compared using the CMP function with DATA pointing to
+   call-specific data.
+   The elements of LIST are linked by the NEXT pointer.  The NEXT pointer of
+   the last element (LIST[LENGTH], 1-based) must be NULL.
+
+   Returns the resulting list.
+
+   Side-effects: PREV pointers in the returned list are messed up.
+*/
+static struct _mu_assoc_elem *
+merge_sort (struct _mu_assoc_elem *list, size_t length,
+           mu_assoc_comparator_t cmp, void *data)
+{
+  struct _mu_assoc_elem *left, *right;
+  size_t left_len, right_len, i;
+  struct _mu_assoc_elem *elt;
+  
+  if (length == 1)
+    return list;
+
+  if (length == 2)
+    {
+      elt = list->next;
+      if (cmp (list->name, list->data, elt->name, elt->data, cmp) > 0)
+       {
+         elt->next = list;
+         list->next = NULL;
+         return elt;
+       }
+      return list;
+    }
+
+  left = list;
+  left_len = (length + 1) / 2;
+
+  right_len = length / 2;
+  for (elt = list, i = left_len - 1; i; i--)
+    elt = elt->next;
+
+  right = elt->next;
+  elt->next = NULL;
+
+  left = merge_sort (left, left_len, cmp, data);
+  right = merge_sort (right, right_len, cmp, data);
+
+  return merge (left, right, cmp, data);
+}
+
+/* Sort the linked list of elements in ASSOC using merge sort.  CMP points
+   to the function to use for comparing two elements.  DATA supplies call-
+   specific data for CMP.
+*/
+int
+mu_assoc_sort_r (mu_assoc_t assoc, mu_assoc_comparator_t cmp, void *data)
+{
+  struct _mu_assoc_elem *head, *prev, *p;
+  size_t length;
+  
+  if (!assoc)
+    return EINVAL;
+  if (!cmp)
+    return 0;
+
+  mu_assoc_count (assoc, &length);
+  head = merge_sort (assoc->head, length, cmp, data);
+  /* The above call leaves PREV pointers in inconsistent state.  Fix them
+     up: */
+  for (prev = NULL, p = head; p; prev = p, p = p->next)
+    p->prev = prev;
+
+  /* Update list head and tail */
+  assoc->head = head;
+  assoc->tail = prev;
+
+  return 0;
+}
+  
diff --git a/libmailutils/tests/.gitignore b/libmailutils/tests/.gitignore
index b8c5ee6..10ebd32 100644
--- a/libmailutils/tests/.gitignore
+++ b/libmailutils/tests/.gitignore
@@ -1,6 +1,7 @@
 atconfig
 atlocal
 cidr
+conttype
 package.m4
 testsuite
 testsuite.dir
@@ -14,6 +15,7 @@ fltst
 fsaf
 fsaftomod
 fsfolder
+globtest
 imapio
 listop
 mailcap
diff --git a/libmailutils/tests/mimehdr.c b/libmailutils/tests/mimehdr.c
index 2564de6..67b4b42 100644
--- a/libmailutils/tests/mimehdr.c
+++ b/libmailutils/tests/mimehdr.c
@@ -33,27 +33,19 @@
 #include <mailutils/error.h>
 #include <mailutils/errno.h>
 
-struct named_param
-{
-  const char *name;
-  struct mu_mime_param const *param;
-};
-
 static int
-sort_names (void const *a, void const *b)
+sort_names (char const *aname, void const *adata,
+           char const *bname, void const *bdata, void *data)
 {
-  struct named_param const *pa = a;
-  struct named_param const *pb = b;
-  return mu_c_strcasecmp (pa->name, pb->name);
+  return mu_c_strcasecmp (aname, bname);
 }
 
 static int
-print_named_param (void *item, void *data)
+print_param (const char *name, void *item, void *data)
 {
-  struct named_param const *p = item;
-  struct mu_mime_param const *param = p->param;
+  struct mu_mime_param *param = item;
   
-  mu_printf ("%s", p->name);
+  mu_printf ("%s", name);
   if (param->lang)
     mu_printf ("(lang:%s/%s)", param->lang, param->cset);
   mu_printf ("=%s\n", param->value);
@@ -68,8 +60,6 @@ main (int argc, char **argv)
   mu_transport_t trans[2];
   char *value;
   mu_assoc_t assoc;
-  mu_iterator_t itr;
-  mu_list_t list;
   char *charset = NULL;
   
   mu_set_program_name (argv[0]);
@@ -108,27 +98,8 @@ main (int argc, char **argv)
   MU_ASSERT (mu_mime_header_parse ((char*)trans[0], charset, &value, &assoc));
 
   mu_printf ("%s\n", value);
-  MU_ASSERT (mu_list_create (&list));
-  MU_ASSERT (mu_assoc_get_iterator (assoc, &itr));
-  for (mu_iterator_first (itr); !mu_iterator_is_done (itr);
-       mu_iterator_next (itr))
-    {
-      const char *name;
-      struct mu_mime_param *p;
-      struct named_param *np;
-      
-      mu_iterator_current_kv (itr, (const void **)&name, (void**)&p);
-      np = malloc (sizeof (*np));
-      if (!np)
-       abort ();
-      np->name = name;
-      np->param = p;
-      MU_ASSERT (mu_list_append (list, np));
-    }
-  mu_iterator_destroy (&itr);
-
-  mu_list_sort (list, sort_names);
-  mu_list_foreach (list, print_named_param, NULL);
+  mu_assoc_sort_r (assoc, sort_names, NULL);
+  mu_assoc_foreach (assoc, print_param, NULL);
   
   return 0;
 }


hooks/post-receive
-- 
GNU Mailutils