[SCM] GNU Mailutils branch, master, updated. release-2.2-492-gbd55279

[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=bd55279a9af52b1e6d88b6d8cb483e17174db106

The branch, master has been updated
       via  bd55279a9af52b1e6d88b6d8cb483e17174db106 (commit)
      from  98ca43a049365269e4052170eba3103a8d35e20b (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 bd55279a9af52b1e6d88b6d8cb483e17174db106
Author: Sergey Poznyakoff <address@hidden>
Date:   Thu Dec 1 03:01:01 2011 +0200

    Implement list sorting.
    
    * include/mailutils/list.h (mu_list_sort): New proto.
    * libmailutils/list/sort.c: New file.
    * libmailutils/list/Makefile.am (liblist_la_SOURCES): Add sort.c
    * libmailutils/tests/listop.c: Implement the sort command.
    * libmailutils/tests/list.at: Test list sorting.

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

Summary of changes:
 include/mailutils/list.h      |   16 +++++-
 libmailutils/list/Makefile.am |    1 +
 libmailutils/list/sort.c      |  121 +++++++++++++++++++++++++++++++++++++++++
 libmailutils/tests/list.at    |   62 +++++++++++++++++++++
 libmailutils/tests/listop.c   |   17 ++++++-
 5 files changed, 215 insertions(+), 2 deletions(-)
 create mode 100644 libmailutils/list/sort.c

diff --git a/include/mailutils/list.h b/include/mailutils/list.h
index 2f860fb..60f0031 100644
--- a/include/mailutils/list.h
+++ b/include/mailutils/list.h
@@ -274,7 +274,9 @@ int mu_list_map (mu_list_t _list, mu_list_mapper_t _map,
                 void *_data, size_t _nelem,
                 mu_list_t *_res);
 
-  /* List fold */
+  /* ************************************************* */
+  /* List folding                                      */
+  /* ************************************************* */
 
 typedef int (*mu_list_folder_t) (void *_item, void *_data,
                                 void *_prev, void **_ret);
@@ -315,6 +317,18 @@ int mu_list_fold (mu_list_t _list, mu_list_folder_t _fold, 
void *_data,
                  void *_init, void *_return_value);
 int mu_list_rfold (mu_list_t _list, mu_list_folder_t _fold, void *_data,
                   void *_init, void *_return_value);
+
+  /* ************************************************* */
+  /* Sorting                                           */
+  /* ************************************************* */
+
+  /* Sort _list using quicksort algorithm.  Use _comp to compare elements.
+     If it is NULL, use the comparator method of _list.
+
+     Comparator must return 0 if the two elements are equal, -1 if
+     first of them is less than the second, and +1 otherwise.
+  */
+void mu_list_sort (mu_list_t _list, mu_list_comparator_t _comp);
   
 #ifdef __cplusplus
 }
diff --git a/libmailutils/list/Makefile.am b/libmailutils/list/Makefile.am
index cd17a9e..eb6084a 100644
--- a/libmailutils/list/Makefile.am
+++ b/libmailutils/list/Makefile.am
@@ -45,6 +45,7 @@ liblist_la_SOURCES = \
  setdestr.c\
  slice.c\
  slice2.c\
+ sort.c\
  tail.c
 
 INCLUDES = @MU_LIB_COMMON_INCLUDES@ -I/libmailutils
diff --git a/libmailutils/list/sort.c b/libmailutils/list/sort.c
new file mode 100644
index 0000000..a021abb
--- /dev/null
+++ b/libmailutils/list/sort.c
@@ -0,0 +1,121 @@
+/* GNU Mailutils -- a suite of utilities for electronic mail
+   Copyright (C) 2011 Free Software Foundation, Inc.
+
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 3 of the License, or (at your option) any later version.
+
+   This library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General
+   Public License along with this library.  If not, see 
+   <http://www.gnu.org/licenses/>. */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+#include <stdlib.h>
+#include <string.h>
+#include <mailutils/errno.h>
+#include <mailutils/sys/list.h>
+
+static void
+_list_append_entry (struct _mu_list *list, struct list_data *ent)
+{
+  ent->prev = list->head.prev ? list->head.prev : &list->head;
+  ent->next = &list->head;
+  if (list->head.prev)
+    list->head.prev->next = ent;
+  else
+    list->head.next = ent;
+  list->head.prev = ent;
+  list->count++;
+}
+
+static void
+_list_qsort (mu_list_t list, mu_list_comparator_t cmp)
+{
+  struct list_data *cur, *middle;
+  struct _mu_list high_list, low_list;
+  int rc;
+
+  if (list->count < 2)
+    return;
+  if (list->count == 2)
+    {
+      if (cmp (list->head.prev->item, list->head.next->item) < 0)
+       {
+         cur = list->head.prev;
+         list->head.prev = list->head.next;
+         list->head.next = cur;
+         
+         list->head.next->prev = &list->head;
+         list->head.next->next = list->head.prev;
+         
+         list->head.prev->next = &list->head;
+         list->head.prev->prev = list->head.next;
+       }
+      return;
+    }
+  
+  cur = list->head.next;
+  do {
+    cur = cur->next;
+    if (!cur)
+      return;
+  } while ((rc = cmp (list->head.next->item, cur->item)) == 0);
+
+  /* Select the lower of the two as the middle value */
+  middle = (rc > 0) ? cur : list->head.next;
+
+  /* Split into two sublists */
+  memset (&high_list, 0, sizeof (high_list));
+  memset (&low_list, 0, sizeof (low_list));
+
+  for (cur = list->head.next; cur != &list->head; )
+    {
+      struct list_data *next = cur->next;
+      cur->next = NULL;
+
+      if (cmp (middle->item, cur->item) < 0)
+       _list_append_entry (&high_list, cur);
+      else
+       _list_append_entry (&low_list, cur);
+      cur = next;
+    }
+
+  /* Sort both sublists recursively */
+  _list_qsort (&low_list, cmp);
+  _list_qsort (&high_list, cmp);
+
+  /* Join both lists in order */
+  if (low_list.head.prev)
+    cur = low_list.head.prev;
+  else
+    cur = &low_list.head;
+  cur->next = high_list.head.next;
+  if (high_list.head.next)
+    high_list.head.next->prev = cur;
+  
+  low_list.head.prev = high_list.head.prev;
+  high_list.head.prev = &low_list.head;
+  low_list.count += high_list.count;
+    
+  /* Return the resulting list */
+  list->head = low_list.head;
+  if (list->head.next)
+    list->head.next->prev = &list->head;
+  if (list->head.prev)
+    list->head.prev->next = &list->head;
+}
+
+void
+mu_list_sort (mu_list_t list, mu_list_comparator_t comp)
+{
+  if (list)
+    _list_qsort (list, comp ? comp : list->comp);
+}
diff --git a/libmailutils/tests/list.at b/libmailutils/tests/list.at
index fcc578e..d49ab43 100644
--- a/libmailutils/tests/list.at
+++ b/libmailutils/tests/list.at
@@ -445,6 +445,68 @@ rfold
 
 m4_popdef([MU_TEST_KEYWORDS])
 
+# ------------------------------------------------------------
+# Sort
+# ------------------------------------------------------------
+
+m4_define([MU_TEST_GROUP],[Sort])
+m4_pushdef([MU_TEST_KEYWORDS],MU_TEST_KEYWORDS[ sort])
+
+TESTLIST([empty list],[],
+[sort
+print
+],
+[# items: 0
+])
+
+TESTLIST([sorted list asc],[],
+[add a b c d e f
+sort
+print
+],
+[# items: 6
+a
+b
+c
+d
+e
+f
+])
+
+TESTLIST([sorted list desc],[],
+[add f e d c b a
+sort
+print
+],
+[# items: 6
+a
+b
+c
+d
+e
+f
+])
+
+TESTLIST([unsorted list],[],
+[add en to tre fire fem seks syv atte ni ti
+sort
+print
+],
+[# items: 10
+atte
+en
+fem
+fire
+ni
+seks
+syv
+ti
+to
+tre
+])
+
+m4_popdef([MU_TEST_KEYWORDS])
+
 dnl ------------------------------------------------------------
 dnl Cleanup
 m4_popdef([TESTLIST])
diff --git a/libmailutils/tests/listop.c b/libmailutils/tests/listop.c
index 93362ec..00d3949 100644
--- a/libmailutils/tests/listop.c
+++ b/libmailutils/tests/listop.c
@@ -773,7 +773,13 @@ rfold (mu_list_t list)
   else
     printf ("NULL\n");
 }
-  
+
+void
+sort (mu_list_t list)
+{
+  mu_list_sort (list, NULL);
+}
+
 void
 help ()
 {
@@ -802,6 +808,7 @@ help ()
   printf ("help\n");
   printf ("head\n");
   printf ("tail\n");
+  printf ("sort\n");
   printf ("NUMBER\n");
 }
 
@@ -921,6 +928,14 @@ shell (mu_list_t list)
            head (ws.ws_wordc, list);
          else if (strcmp (ws.ws_wordv[0], "tail") == 0)
            tail (ws.ws_wordc, list);
+         else if (strcmp (ws.ws_wordv[0], "sort") == 0)
+           {
+             int i;
+             sort (list);
+
+             for (i = 0; i < NITR; i++)
+               mu_iterator_destroy (&itr[i]);
+           }
          else if (ws.ws_wordc == 1)
            {
              char *p;


hooks/post-receive
-- 
GNU Mailutils