From a0b5981329002f52cd96ebc08625e9cffb36fda0 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Sat, 20 Jan 2024 23:57:38 +0100
Subject: Introduce an algorithm for sorting a linked list.
---
src/common/dllist.c | 195 ++++++++++++++++++++++++++++++++++++++++++++++++++++
src/common/dllist.h | 34 +++++++++
2 files changed, 229 insertions(+)
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 */
--
cgit v0.11.2-87-g4458