diff options
Diffstat (limited to 'src/common/dllist.c')
| -rw-r--r-- | src/common/dllist.c | 195 |
1 files changed, 195 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); + + } + +} |