Managed double linked lists in a more powerful way.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@56 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

3 files changed, 114 insertions, 158 deletions

diff --git a/src/common/Makefile.am b/src/common/Makefile.am
index 5b21da3..f23941b 100755
--- a/src/common/Makefile.am
+++ b/src/common/Makefile.am
@@ -4,7 +4,8 @@ lib_LIBRARIES = libcommon.a
 libcommon_a_SOURCES =					\
 	dllist.h dllist.c					\
 	endianness.h endianness.c			\
-	extstr.h extstr.c
+	extstr.h extstr.c					\
+	macros.h
 
 libcommon_a_CFLAGS = $(AM_CFLAGS)
 
diff --git a/src/common/dllist.c b/src/common/dllist.c
index 7e56bf4..5de3cd9 100644
--- a/src/common/dllist.c
+++ b/src/common/dllist.c
@@ -24,9 +24,6 @@
 #include "dllist.h"
 
 
-#include <stdbool.h>
-
-
 
 /******************************************************************************
 *                                                                             *
@@ -59,8 +56,8 @@ void __dl_list_add(dl_list_item *new, dl_list_head *head, dl_list_item *prev, dl
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : prev = élément précédent dans la liste.                      *
-*                next = élément suivant dans la liste.                        *
+*  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.          *
 *                                                                             *
@@ -70,85 +67,39 @@ void __dl_list_add(dl_list_item *new, dl_list_head *head, dl_list_item *prev, dl
 *                                                                             *
 ******************************************************************************/
 
-void __dl_list_del(dl_list_item *prev, dl_list_item *next)
+void __dl_list_del(dl_list_item *item, dl_list_head *head)
 {
-    next->prev = prev;
-    prev->next = next;
+    item->next->prev = item->prev;
+    item->prev->next = item->next;
 
-}
-
-
-/******************************************************************************
-*                                                                             *
-*  Paramètres  : head = début de la liste, à mettre éventuellement à jour.    *
-*                a    = premier élément à traiter.                            *
-*                b    = second élément à traiter.                             *
-*                                                                             *
-*  Description : Intervertit deux éléments dans une liste doublement chaînée. *
-*                                                                             *
-*  Retour      : -                                                            *
-*                                                                             *
-*  Remarques   : -                                                            *
-*                                                                             *
-******************************************************************************/
-
-void swap_dl_list_items(dl_list_head *head, dl_list_item *a, dl_list_item *b)
-{
-    bool a_is_head;                         /* Indique si a est le début   */
-    bool b_is_head;                         /* Indique si b est le début   */
-    dl_list_item tmp;                       /* Stockage temporaire         */
-
-    a_is_head = (*head == a);
-    b_is_head = (*head == b);
-
-    /* Liens vers l'extérieur et l'intérieur */
-
-    if (a->prev != b) a->prev->next = b;
-    if (a->next != b) a->next->prev = b;
-
-    if (b->prev != a) b->prev->next = a;
-    if (b->next != a) b->next->prev = a;
-
-    /* Liens propres aux éléments */
-
-    tmp = *a;
-
-    a->prev = (b->prev == a ? b : b->prev);
-    a->next = (b->next == a ? b : b->next);
-
-    b->prev = (tmp.prev == b ? a : tmp.prev);
-    b->next = (tmp.next == b ? a : tmp.next);
-
-    /* Mise à jour éventuelle de la tête */
-
-    if (a_is_head) *head = b;
-    else if (b_is_head) *head = a;
+    if (*head == item)
+    {
+        *head = item->next;
+        if (*head == item) *head = NULL;
+    }
 
 }
 
 
 /******************************************************************************
 *                                                                             *
-*  Paramètres  : list = liste à parcourir.                                    *
+*  Paramètres  : item = point d'insertion.                                    *
+*                head = seconde liste à intégrer.                             *
 *                                                                             *
-*  Description : Compte le nombre d'éléments présents dans une liste.         *
+*  Description : Insère une liste au sein d'une autre.                        *
 *                                                                             *
-*  Retour      : Nombre d'éléments comptabilisés.                             *
+*  Retour      : -                                                            *
 *                                                                             *
 *  Remarques   : -                                                            *
 *                                                                             *
 ******************************************************************************/
 
-unsigned int count_dl_list_items(dl_list_head list)
+void __dl_list_splice(dl_list_item *pos, dl_list_head head)
 {
-    unsigned int result;                    /* Résultat à renvoyer         */
-    dl_list_item *iter;                     /* Boucle de parcours          */
-
-    result = 0;
-
-    dl_list_for_each(iter, list, dl_list_item *)
-        result++;
+    pos->next->prev = head;
+    head->prev->next = pos->next;
 
-    return result;
+    pos->next = head;
+    head->prev = pos;
 
 }
diff --git a/src/common/dllist.h b/src/common/dllist.h
index 670d3b9..1bd1ead 100644
--- a/src/common/dllist.h
+++ b/src/common/dllist.h
@@ -21,11 +21,11 @@
  */
 
 
-#ifndef _DLLIST_H
-#define _DLLIST_H
+#ifndef _COMMON_DLLIST_H
+#define _COMMON_DLLIST_H
 
 
-#define NULL ((void *)0)
+#include "macros.h"
 
 
 
@@ -37,106 +37,110 @@ typedef struct _dl_list_item
 
 } dl_list_item;
 
-
 typedef dl_list_item *dl_list_head;
 
 
-#define DL_LIST_ITEM dl_list_item dummy
-
-#define DLL_CAST(item) ((dl_list_item *)item)
-#define DLL_HCAST(item) ((dl_list_item **)item)
+#define DL_LIST_ITEM(name) dl_list_item name
 
-#define DL_LIST_HEAD_INIT(head)                                         \
-    *(head) = NULL
 
-#define DL_LIST_ITEM_INIT(item)                                         \
-    do                                                                  \
-    {                                                                   \
-        DLL_CAST(item)->prev = NULL;                                    \
-        DLL_CAST(item)->next = NULL;                                    \
-                                                                        \
+#define DL_LIST_ITEM_INIT(item)                                                     \
+    do                                                                              \
+    {                                                                               \
+        (item)->prev = (item);                                                      \
+        (item)->next = (item);                                                      \
+                                                                                    \
     } while(0)
 
-#define DL_LIST_NEXT(item, type) (type)DLL_CAST(item)->next
-#define DL_LIST_PREV(item, type) (type)DLL_CAST(item)->prev
 
-#define DL_LIST_IS_ALONE(head) (DLL_CAST(head)->next == DLL_CAST(head))
-
- 
 /* 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 *);
 
 /* Supprime un élément d'une liste doublement chaînée. */
-void __dl_list_del(dl_list_item *, dl_list_item *);
-
-/* Intervertit deux éléments dans une liste doublement chaînée. */
-void swap_dl_list_items(dl_list_head *, dl_list_item *, dl_list_item *);
+void __dl_list_del(dl_list_item *, dl_list_head *);
 
-/* Compte le nombre d'éléments présents dans une liste. */
-unsigned int count_dl_list_items(dl_list_head);
+/* Insère une liste au sein d'une autre. */
+void __dl_list_splice(dl_list_item *, dl_list_head);
 
 
-#define dl_list_empty(head)                                             \
+#define dl_list_empty(head)                                                         \
     ((head) == NULL)
 
-#define dl_list_last(head, type)                                        \
-    (dl_list_empty(head) ? NULL : (type)((head)->prev == NULL ? (head) : (head)->prev))
-
-#define dl_list_add(new, head)                                          \
-    __dl_list_add(DLL_CAST(new), (head), (dl_list_empty(*(head)) ? DLL_CAST(new) : dl_list_last(*head, dl_list_item *)), (dl_list_empty(*(head)) ? DLL_CAST(new) : *(head)))
-
-#define dl_list_add_tail(new, head)                                     \
-    __dl_list_add(DLL_CAST(new), (head), (dl_list_empty(*(head)) ? DLL_CAST(new) : (*(head))->prev), (dl_list_empty(*(head)) ? DLL_CAST(new) : *(head)))
-
-#define dl_list_insert_before(new, target, head)                        \
-    do                                                                  \
-    {                                                                   \
-        DLL_CAST(new)->prev = DLL_CAST(target)->prev;                   \
-        DLL_CAST(target)->prev->next = DLL_CAST(new);                   \
-        DLL_CAST(new)->next = DLL_CAST(target);                         \
-        DLL_CAST(target)->prev = DLL_CAST(new);                         \
-        if (DLL_CAST(target) == *head) *head = DLL_CAST(target);        \
-                                                                        \
-    } while (0)
-
-#define dl_list_del(item, head)                                         \
-    do                                                                  \
-    {                                                                   \
-        __dl_list_del(DLL_CAST(item)->prev, DLL_CAST(item)->next);      \
-        if (*head == DLL_CAST(item)) *head = DLL_CAST(item)->next;      \
-        if (*head == DLL_CAST(item)) *head = NULL;                      \
-        DLL_CAST(item)->next = NULL;                                    \
-        DLL_CAST(item)->prev = NULL;                                    \
-                                                                        \
-    } while(0)
-
-#define dl_list_move_tail(item, head)                                   \
-    do                                                                  \
-    {                                                                   \
-        dl_list_del(item, head);                                        \
-        dl_list_add_tail(item, head);                                   \
-                                                                        \
-    } while(0)
-
-#define dl_list_for_each(pos, head, type)                               \
-	for (pos = (type)(head);                                            \
-         pos != NULL;                                                   \
-         pos = (type)(DLL_CAST(pos)->next == (head) ? NULL : DLL_CAST(pos)->next))
-
-#define dl_list_for_each_safe(pos, head, tmp, type)                     \
-	for (pos = (type)*(head),                                           \
-             tmp = (type)(pos != NULL && DLL_CAST(pos)->next != *(head) ?\
-                 DLL_CAST(pos)->next : NULL);                           \
-         pos != NULL;                                                   \
-         pos = tmp,                                                     \
-             tmp = (type)(pos != NULL && DLL_CAST(pos)->next != *(head) ?\
-                 DLL_CAST(pos)->next : NULL))
-
-#define dl_list_for_each_prev(pos, head, type)                          \
-	for (pos = dl_list_last(head, type);                                \
-         pos != NULL;                                                   \
-         pos = (type)(DLL_CAST(pos) == (head) ? NULL : DLL_CAST(pos)->prev))
-
-
-
-#endif  /* _DLLIST_H */
+#define dl_list_last(head, type, member)                                            \
+    (dl_list_empty(head) ? NULL : (type *)container_of(head->member.prev, type, member))
+
+#define dl_list_add(new, head, type, member)                                        \
+    do                                                                              \
+    {                                                                               \
+        dl_list_item *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);                \
+        *(head) = new;                                                              \
+    }                                                                               \
+    while (0)
+
+#define dl_list_add_tail(new, head, type, member)                                   \
+    do                                                                              \
+    {                                                                               \
+        dl_list_item *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);                \
+        *(head) = container_of(hmbr, type, member);                                 \
+    }                                                                               \
+    while (0)
+
+#define dl_list_del(item, head, type, member)                                       \
+    do                                                                              \
+    {                                                                               \
+        dl_list_item *hmbr = &(*head)->member;                                      \
+        __dl_list_del(&item->member, &hmbr);                                        \
+        *(head) = container_of(hmbr, type, member);                                 \
+        DL_LIST_ITEM_INIT(&item->member);                                           \
+    }                                                                               \
+    while(0)
+
+#define dl_list_splice_before(pos, head1, head2, type, member)                      \
+    do                                                                              \
+    {                                                                               \
+        if (pos == *head1)                                                          \
+        {                                                                           \
+            __dl_list_splice(head2->member.prev, &(*head1)->member);                \
+            *head1 = head2;                                                         \
+        }                                                                           \
+        else __dl_list_splice(pos->member.prev, &head2->member);                    \
+    }                                                                               \
+    while(0)
+
+#define dl_list_splice_after(pos, head2, type, member)                              \
+        __dl_list_splice(&pos->member, &head2->member);
+
+#define dl_list_next_iter(iter, head, type, member)                                 \
+    (iter->member.next == &head->member ?                                           \
+     NULL : container_of(iter->member.next, type, member))
+
+#define dl_list_for_each(pos, head, type, member)                                   \
+	for (pos = head;                                                                \
+         pos != NULL;                                                               \
+         pos = dl_list_next_iter(pos, (head), type, member))
+
+#define dl_list_next_iter_safe(iter, head, type, member)                            \
+    (iter == NULL || iter->member.next == &(*head)->member ?                        \
+     NULL : container_of(iter->member.next, type, member))
+
+#define dl_list_for_each_safe(pos, head, next, type, member)                        \
+	for (pos = *head,                                                               \
+             next = dl_list_next_iter_safe(pos, (head), type, member);              \
+         pos != NULL;                                                               \
+         pos = next,                                                                \
+             next = dl_list_next_iter_safe(pos, (head), type, member))
+
+#define dl_list_for_each_rev(pos, head, type, member)                               \
+	for (pos = dl_list_last(head, type, member);                                    \
+         pos != NULL;                                                               \
+         pos = (pos == head ?                                                       \
+                NULL : container_of(pos->member.prev, type, member)))
+
+
+
+#endif  /* _COMMON_DLLIST_H */