/* Chrysalide - Outil d'analyse de fichiers binaires
* dllist.c - implantation simple des listes doublement chaînées
*
* Copyright (C) 2009-2018 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* Chrysalide is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* Chrysalide 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Chrysalide. If not, see .
*/
#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 *);
/******************************************************************************
* *
* Paramètres : new = nouvel élément à ajouter. *
* head = adresse d'enregistrement de la tête de la liste. *
* prev = élément précédent dans la liste. *
* next = élément suivant dans la liste. *
* *
* Description : Ajoute un élément dans une liste doublement chaînée. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void __dl_list_add(dl_list_item *new, dl_list_head *head, dl_list_item *prev, dl_list_item *next)
{
prev->next = new;
new->prev = prev;
new->next = next;
next->prev = new;
if (*head == NULL)
*head = new;
}
/******************************************************************************
* *
* Paramètres : item = élément à supprimer. *
* head = adresse d'enregistrement de la tête de la liste. *
* *
* Description : Supprime un élément d'une liste doublement chaînée. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void __dl_list_del(dl_list_item *item, dl_list_head *head)
{
item->next->prev = item->prev;
item->prev->next = item->next;
if (*head == item)
{
*head = item->next;
if (*head == item) *head = NULL;
}
}
/******************************************************************************
* *
* 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);
}
}