Introduce an algorithm for sorting a linked list.

2 files changed, 229 insertions, 0 deletions

diff --git a/src/common/dllist.c b/src/common/dllist.c
index a953ad0..1ee7b0d 100644
--- a/src/common/dllist.c
+++ b/src/common/dllist.c
@@ -24,6 +24,17 @@
 #include "dllist.h"
 
 
+#include <assert.h>
+
+
+
+/* Découpe une liste en deux parties. */
+static void split_dl_lists(dl_list_head, dl_list_head *, dl_list_head *);
+
+/* Trie une liste chaînée en supprimant les éléments identiques. */
+static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *, dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *);
+
+
 
 /******************************************************************************
 *                                                                             *
@@ -79,3 +90,187 @@ void __dl_list_del(dl_list_item *item, dl_list_head *head)
     }
 
 }
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : list  = liste à découper.                                    *
+*                part1 = première partie constituée. [OUT]                    *
+*                part2 = seconde partie constituée. [OUT]                     *
+*                                                                             *
+*  Description : Découpe une liste en deux parties.                           *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static void split_dl_lists(dl_list_head list, dl_list_head *part1, dl_list_head *part2)
+{
+    dl_list_item *iter_slow;                /* Boucle de parcours #1       */
+    dl_list_item *iter_fast;                /* Boucle de parcours #2       */
+
+    *part1 = list;
+
+    iter_slow = list;
+    iter_fast = _dl_list_next(iter_slow, list);
+
+    while (iter_fast != NULL)
+    {
+        iter_fast = _dl_list_next(iter_fast, list);
+
+        if (iter_fast != NULL)
+        {
+            iter_slow = _dl_list_next(iter_slow, list);
+            iter_fast = _dl_list_next(iter_fast, list);
+        }
+
+    }
+
+    *part2 = _dl_list_next(iter_slow, list);
+
+    /* Réalisation d'une coupure */
+
+    if (*part2 != NULL)
+    {
+        (*part2)->prev = (*part1)->prev;
+        (*part2)->prev->next = (*part2);
+    }
+
+    iter_slow->next = *part1;
+    (*part1)->prev = iter_slow;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : head       = tête de la liste à trier.                       *
+*                length     = taille de la liste fournie.                     *
+*                compar     = méthode de comparaison des éléments.            *
+*                duplicated = liste des éléments présents en double. [OUT]    *
+*                                                                             *
+*  Description : Trie une liste chaînée en supprimant les éléments identiques.*
+*                                                                             *
+*  Retour      : Nouvelle liste obtenue.                                      *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *a, dl_list_head *b, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated)
+{
+    dl_list_head result;                    /* Liste fusionnée à renvoyer  */
+    int ret;                                /* Bilan d'une comparaison     */
+    dl_list_head next;                      /* Maillons de liste suivants  */
+
+    if (dl_list_empty(*a))
+        result = *b;
+
+    else if (dl_list_empty(*b))
+        result = *a;
+
+    else
+    {
+        ret = compar(*a, *b);
+
+        if (ret < 0)
+        {
+            result = *a;
+            __dl_list_del(result, a);
+            DL_LIST_ITEM_INIT(result);
+
+            next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+            assert(!dl_list_empty(next));
+            _dl_list_merge(result, next);
+
+        }
+
+        else if (ret == 0)
+        {
+            result = *a;
+            __dl_list_del(result, a);
+            DL_LIST_ITEM_INIT(result);
+
+            if (length != NULL)
+                (*length)--;
+
+            if (duplicated != NULL)
+            {
+                /**
+                 * L'élément est ici ajouté à la liste sans respect d'un ordre particulier.
+                 */
+
+                if (dl_list_empty(*duplicated))
+                    *duplicated = result;
+                else
+                    __dl_list_add(result, duplicated, (*duplicated)->prev, *duplicated);
+
+            }
+
+            result = *b;
+            __dl_list_del(result, b);
+            DL_LIST_ITEM_INIT(result);
+
+            next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+            if (!dl_list_empty(next))
+                _dl_list_merge(result, next);
+
+        }
+
+        else
+        {
+            result = *b;
+            __dl_list_del(result, b);
+            DL_LIST_ITEM_INIT(result);
+
+            next = sort_and_merge_dl_lists_no_dup(a, b, length, compar, duplicated);
+            assert(!dl_list_empty(next));
+            _dl_list_merge(result, next);
+
+        }
+
+    }
+
+    return result;
+
+}
+
+
+/******************************************************************************
+*                                                                             *
+*  Paramètres  : head       = tête de la liste à trier.                       *
+*                length     = taille de la liste fournie.                     *
+*                compar     = méthode de comparaison des éléments.            *
+*                duplicated = liste des éléments présents en double. [OUT]    *
+*                                                                             *
+*  Description : Trie une liste chaînée en notant les éléments identiques.    *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void sort_dl_list_no_dup(dl_list_head *head, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated)
+{
+    dl_list_head part1;                     /* Première moitiée à traiter  */
+    dl_list_head part2;                     /* Seconde moitiée à traiter   */
+
+    /* S'il y a réellement quelque chose à faire */
+    if (!dl_list_empty(*head) && !_dl_list_is_last(*head, *head))
+    {
+        /* Découpage en deux sous-listes */
+        split_dl_lists(*head, &part1, &part2);
+
+        /* Tri des deux listes obtenues */
+        sort_dl_list_no_dup(&part1, length, compar, duplicated);
+        sort_dl_list_no_dup(&part2, length, compar, duplicated);
+
+        /* Fusion des deux listes triées */
+        *head = sort_and_merge_dl_lists_no_dup(&part1, &part2, length, compar, duplicated);
+
+    }
+
+}
diff --git a/src/common/dllist.h b/src/common/dllist.h
index 111843b..1fb010a 100644
--- a/src/common/dllist.h
+++ b/src/common/dllist.h
@@ -62,6 +62,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
 #define dl_list_empty(head)                                                         \
     ((head) == NULL)
 
+#define _dl_list_is_last(item, head)                                                \
+    ((item)->next == head)
+
+#define dl_list_is_last(item, head, member)                                         \
+    item->member.next == &head->member
+
 #define dl_list_last(head, type, member)                                            \
     (dl_list_empty(head) ? NULL : (type *)container_of(head->member.prev, type, member))
 
@@ -108,6 +114,17 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
     }                                                                               \
     while(0)
 
+#define _dl_list_merge(head1, head2)                                                \
+    do                                                                              \
+    {                                                                               \
+        dl_list_item *mid = head1->prev;                                            \
+        mid->next = head2;                                                          \
+        head1->prev = head2->prev;                                                  \
+        head2->prev->next = head1;                                                  \
+        head2->prev = mid;                                                          \
+    }                                                                               \
+    while(0)
+
 #define dl_list_merge(head1, head2, type, member)                                   \
     do                                                                              \
     {                                                                               \
@@ -134,6 +151,16 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
         _result;                                                                    \
     })
 
+#define _dl_list_next(iter, head)                                                   \
+    ({                                                                              \
+        dl_list_item *__next;                                                       \
+        __next = iter->next;                                                        \
+        if (__next == head)                                                         \
+            __next = NULL;                                                          \
+        __next;                                                                     \
+    })
+
+
 #define dl_list_next_iter(iter, head, type, member)                                 \
     (iter->member.next == &head->member ?                                           \
      NULL : container_of(iter->member.next, type, member))
@@ -164,5 +191,12 @@ void __dl_list_del(dl_list_item *, dl_list_head *);
          pos = dl_list_prev_iter(pos, (head), type, member))
 
 
+/* Prototype pour un comparateur d'éléments */
+typedef int (*__dl_item_compar_fn_t) (const dl_list_item *, const dl_list_item *);
+
+/* Trie une liste chaînée en notant les éléments identiques. */
+void sort_dl_list_no_dup(dl_list_head *, size_t *, __dl_item_compar_fn_t, dl_list_head *);
+
+
 
 #endif  /* _COMMON_DLLIST_H */