From a21d9f936fe5e795cbea48aa4a4e72adc19e45dd Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Fri, 21 Jun 2024 18:19:04 +0200 Subject: Restore and update doubly linked lists. --- src/common/Makefile.am | 4 ++-- src/common/dllist.c | 26 +++++++++++++------------- src/common/dllist.h | 39 +++++++++++++++++++++------------------ 3 files changed, 36 insertions(+), 33 deletions(-) diff --git a/src/common/Makefile.am b/src/common/Makefile.am index 8161f8e..27ead1d 100644 --- a/src/common/Makefile.am +++ b/src/common/Makefile.am @@ -10,7 +10,6 @@ libcommon_la_SOURCES = \ compression.h compression.c \ cpp.h \ cpu.h cpu.c \ - dllist.h dllist.c \ environment.h environment.c \ extstr.h extstr.c \ hex.h hex.c \ @@ -18,7 +17,6 @@ libcommon_la_SOURCES = \ io.h io.c \ itoa.h itoa.c \ leb128.h leb128.c \ - macros.h \ net.h net.c \ packed.h packed.c \ pathname.h pathname.c \ @@ -55,11 +53,13 @@ libcommon4_la_SOURCES = \ bits.h bits.c \ compiler.h \ datatypes.h \ + dllist.h dllist.c \ environment.h environment.c \ extstr.h extstr.c \ fnv1a.h fnv1a.c \ io.h io.c \ leb128.h leb128.c \ + macros.h \ packed.h packed.c \ pathname.h pathname.c \ sort.h sort.c \ diff --git a/src/common/dllist.c b/src/common/dllist.c index 1ee7b0d..92406d7 100644 --- a/src/common/dllist.c +++ b/src/common/dllist.c @@ -29,10 +29,10 @@ /* Découpe une liste en deux parties. */ -static void split_dl_lists(dl_list_head, dl_list_head *, dl_list_head *); +static void split_dl_lists(dl_list_head_t, dl_list_head_t *, dl_list_head_t *); /* 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 *); +static dl_list_head_t sort_and_merge_dl_lists_no_dup(dl_list_head_t *, dl_list_head_t *, size_t *, __dl_item_compar_fn_t, dl_list_head_t *); @@ -51,7 +51,7 @@ static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *, dl_list_head * * ******************************************************************************/ -void __dl_list_add(dl_list_item *new, dl_list_head *head, dl_list_item *prev, dl_list_item *next) +void __dl_list_add(dl_list_item_t *new, dl_list_head_t *head, dl_list_item_t *prev, dl_list_item_t *next) { prev->next = new; new->prev = prev; @@ -78,7 +78,7 @@ void __dl_list_add(dl_list_item *new, dl_list_head *head, dl_list_item *prev, dl * * ******************************************************************************/ -void __dl_list_del(dl_list_item *item, dl_list_head *head) +void __dl_list_del(dl_list_item_t *item, dl_list_head_t *head) { item->next->prev = item->prev; item->prev->next = item->next; @@ -106,10 +106,10 @@ void __dl_list_del(dl_list_item *item, dl_list_head *head) * * ******************************************************************************/ -static void split_dl_lists(dl_list_head list, dl_list_head *part1, dl_list_head *part2) +static void split_dl_lists(dl_list_head_t list, dl_list_head_t *part1, dl_list_head_t *part2) { - dl_list_item *iter_slow; /* Boucle de parcours #1 */ - dl_list_item *iter_fast; /* Boucle de parcours #2 */ + dl_list_item_t *iter_slow; /* Boucle de parcours #1 */ + dl_list_item_t *iter_fast; /* Boucle de parcours #2 */ *part1 = list; @@ -159,11 +159,11 @@ static void split_dl_lists(dl_list_head list, dl_list_head *part1, dl_list_head * * ******************************************************************************/ -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) +static dl_list_head_t sort_and_merge_dl_lists_no_dup(dl_list_head_t *a, dl_list_head_t *b, size_t *length, __dl_item_compar_fn_t compar, dl_list_head_t *duplicated) { - dl_list_head result; /* Liste fusionnée à renvoyer */ + dl_list_head_t result; /* Liste fusionnée à renvoyer */ int ret; /* Bilan d'une comparaison */ - dl_list_head next; /* Maillons de liste suivants */ + dl_list_head_t next; /* Maillons de liste suivants */ if (dl_list_empty(*a)) result = *b; @@ -253,10 +253,10 @@ static dl_list_head sort_and_merge_dl_lists_no_dup(dl_list_head *a, dl_list_head * * ******************************************************************************/ -void sort_dl_list_no_dup(dl_list_head *head, size_t *length, __dl_item_compar_fn_t compar, dl_list_head *duplicated) +void sort_dl_list_no_dup(dl_list_head_t *head, size_t *length, __dl_item_compar_fn_t compar, dl_list_head_t *duplicated) { - dl_list_head part1; /* Première moitiée à traiter */ - dl_list_head part2; /* Seconde moitiée à traiter */ + dl_list_head_t part1; /* Première moitiée à traiter */ + dl_list_head_t 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)) diff --git a/src/common/dllist.h b/src/common/dllist.h index 1fb010a..f7b500e 100644 --- a/src/common/dllist.h +++ b/src/common/dllist.h @@ -30,17 +30,17 @@ /* Structure à inclure en tête de structure */ -typedef struct _dl_list_item +typedef struct _dl_list_item_t { - struct _dl_list_item *prev; /* Elément précédent */ - struct _dl_list_item *next; /* Elément suivant */ + struct _dl_list_item_t *prev; /* Elément précédent */ + struct _dl_list_item_t *next; /* Elément suivant */ -} dl_list_item; +} dl_list_item_t; -typedef dl_list_item *dl_list_head; +typedef dl_list_item_t *dl_list_head_t; -#define DL_LIST_ITEM(name) dl_list_item name +#define DL_LIST_ITEM(name) dl_list_item_t name #define DL_LIST_ITEM_INIT(item) \ @@ -51,12 +51,15 @@ typedef dl_list_item *dl_list_head; \ } while(0) +#define DL_LIST_HEAD_INIT(head) \ + head = NULL + /* Ajoute un élément dans une liste doublement chaînée. */ -void __dl_list_add(dl_list_item *, dl_list_head *, dl_list_item *, dl_list_item *); +void __dl_list_add(dl_list_item_t *, dl_list_head_t *, dl_list_item_t *, dl_list_item_t *); /* Supprime un élément d'une liste doublement chaînée. */ -void __dl_list_del(dl_list_item *, dl_list_head *); +void __dl_list_del(dl_list_item_t *, dl_list_head_t *); #define dl_list_empty(head) \ @@ -74,7 +77,7 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define dl_list_add(new, head, type, member) \ do \ { \ - dl_list_item *hmbr = (dl_list_empty(*(head)) ? NULL : &(*head)->member); \ + dl_list_item_t *hmbr = (dl_list_empty(*(head)) ? NULL : &(*head)->member); \ __dl_list_add(&new->member, &hmbr, \ dl_list_empty(*(head)) ? &new->member : hmbr->prev, \ dl_list_empty(*(head)) ? &new->member : hmbr); \ @@ -96,7 +99,7 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define dl_list_add_tail(new, head, type, member) \ do \ { \ - dl_list_item *hmbr = (dl_list_empty(*(head)) ? NULL : &(*head)->member); \ + dl_list_item_t *hmbr = (dl_list_empty(*(head)) ? NULL : &(*head)->member); \ __dl_list_add(&new->member, &hmbr, \ dl_list_empty(*(head)) ? &new->member : hmbr->prev, \ dl_list_empty(*(head)) ? &new->member : hmbr); \ @@ -107,7 +110,7 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define dl_list_del(item, head, type, member) \ do \ { \ - dl_list_item *hmbr = &(*head)->member; \ + dl_list_item_t *hmbr = &(*head)->member; \ __dl_list_del(&item->member, &hmbr); \ *(head) = (hmbr ? container_of(hmbr, type, member) : NULL); \ DL_LIST_ITEM_INIT(&item->member); \ @@ -117,7 +120,7 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define _dl_list_merge(head1, head2) \ do \ { \ - dl_list_item *mid = head1->prev; \ + dl_list_item_t *mid = head1->prev; \ mid->next = head2; \ head1->prev = head2->prev; \ head2->prev->next = head1; \ @@ -131,9 +134,9 @@ void __dl_list_del(dl_list_item *, dl_list_head *); if (dl_list_empty(*head1)) *head1 = *head2; \ else if (!dl_list_empty(*head2)) \ { \ - dl_list_item *hmbr1 = &(*head1)->member; \ - dl_list_item *hmbr2 = &(*head2)->member; \ - dl_list_item *mid = hmbr1->prev; \ + dl_list_item_t *hmbr1 = &(*head1)->member; \ + dl_list_item_t *hmbr2 = &(*head2)->member; \ + dl_list_item_t *mid = hmbr1->prev; \ mid->next = hmbr2; \ hmbr1->prev = hmbr2->prev; \ hmbr2->prev->next = hmbr1; \ @@ -153,7 +156,7 @@ void __dl_list_del(dl_list_item *, dl_list_head *); #define _dl_list_next(iter, head) \ ({ \ - dl_list_item *__next; \ + dl_list_item_t *__next; \ __next = iter->next; \ if (__next == head) \ __next = NULL; \ @@ -192,10 +195,10 @@ void __dl_list_del(dl_list_item *, dl_list_head *); /* Prototype pour un comparateur d'éléments */ -typedef int (*__dl_item_compar_fn_t) (const dl_list_item *, const dl_list_item *); +typedef int (*__dl_item_compar_fn_t) (const dl_list_item_t *, const dl_list_item_t *); /* 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 *); +void sort_dl_list_no_dup(dl_list_head_t *, size_t *, __dl_item_compar_fn_t, dl_list_head_t *); -- cgit v0.11.2-87-g4458