From a0b5981329002f52cd96ebc08625e9cffb36fda0 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard 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 + + + +/* 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