lib: add DECLARE_DLIST (double-linked list)

Turns out we need one of these.  Same API as DECLARE_LIST, but deleting
random items is much faster.

Signed-off-by: David Lamparter <equinox@diac24.net>
(cherry picked from commit fdad523b547e68a2170a7e5fec4bad98222cb9a0)

diff --git a/doc/developer/lists.rst b/doc/developer/lists.rst
index 6d60420b2fb2b675596e513bf3f2678e7286b1f6..cd268f3c5f3e634a22d03f55ce7336348a16efa1 100644 (file)
--- a/doc/developer/lists.rst
+++ b/doc/developer/lists.rst
@@ -19,6 +19,8 @@ For unsorted lists, the following implementations exist:
 
 - single-linked list with tail pointer (e.g. STAILQ in BSD)
 
+- double-linked list
+
 - atomic single-linked list with tail pointer
 
 
@@ -70,6 +72,7 @@ Available types:
 
    DECLARE_LIST
    DECLARE_ATOMLIST
+   DECLARE_DLIST
 
    DECLARE_SORTLIST_UNIQ
    DECLARE_SORTLIST_NONUNIQ
@@ -311,8 +314,8 @@ are several functions exposed to insert data:
 
 .. c:function:: DECLARE_XXX(Z, type, field)
 
-   :param listtype XXX: ``LIST`` or ``ATOMLIST`` to select a data structure
-      implementation.
+   :param listtype XXX: ``LIST``, ``DLIST`` or ``ATOMLIST`` to select a data
+      structure implementation.
    :param token Z: Gives the name prefix that is used for the functions
       created for this instantiation.  ``DECLARE_XXX(foo, ...)``
       gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc.  Note

diff --git a/lib/typesafe.h b/lib/typesafe.h
index bbf3ce8f1cb508c8aaa447064f02d67d954509ba..9db7bc8274fbbdc5897fae65a2d3257b18f57685 100644 (file)
--- a/lib/typesafe.h
+++ b/lib/typesafe.h
@@ -151,6 +151,107 @@ macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 }                                                                              \
 /* ... */
 
+/* don't use these structs directly */
+struct dlist_item {
+       struct dlist_item *next;
+       struct dlist_item *prev;
+};
+
+struct dlist_head {
+       struct dlist_item hitem;
+       size_t count;
+};
+
+static inline void typesafe_dlist_add(struct dlist_head *head,
+               struct dlist_item *prev, struct dlist_item *item)
+{
+       item->next = prev->next;
+       item->next->prev = item;
+       item->prev = prev;
+       prev->next = item;
+       head->count++;
+}
+
+/* double-linked list, for fast item deletion
+ */
+#define PREDECL_DLIST(prefix)                                                  \
+struct prefix ## _head { struct dlist_head dh; };                              \
+struct prefix ## _item { struct dlist_item di; };
+
+#define INIT_DLIST(var) { .dh = { \
+       .hitem = { &var.dh.hitem, &var.dh.hitem }, }, }
+
+#define DECLARE_DLIST(prefix, type, field)                                     \
+                                                                               \
+macro_inline void prefix ## _init(struct prefix##_head *h)                     \
+{                                                                              \
+       memset(h, 0, sizeof(*h));                                              \
+       h->dh.hitem.prev = &h->dh.hitem;                                       \
+       h->dh.hitem.next = &h->dh.hitem;                                       \
+}                                                                              \
+macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
+{                                                                              \
+       memset(h, 0, sizeof(*h));                                              \
+}                                                                              \
+macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item)     \
+{                                                                              \
+       typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di);             \
+}                                                                              \
+macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item)     \
+{                                                                              \
+       typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di);         \
+}                                                                              \
+macro_inline void prefix ## _add_after(struct prefix##_head *h,                \
+               type *after, type *item)                                       \
+{                                                                              \
+       struct dlist_item *prev;                                               \
+       prev = after ? &after->field.di : &h->dh.hitem;                        \
+       typesafe_dlist_add(&h->dh, prev, &item->field.di);                     \
+}                                                                              \
+macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
+{                                                                              \
+       struct dlist_item *ditem = &item->field.di;                            \
+       ditem->prev->next = ditem->next;                                       \
+       ditem->next->prev = ditem->prev;                                       \
+       h->dh.count--;                                                         \
+       ditem->prev = ditem->next = NULL;                                      \
+}                                                                              \
+macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
+{                                                                              \
+       struct dlist_item *ditem = h->dh.hitem.next;                           \
+       if (ditem == &h->dh.hitem)                                             \
+               return NULL;                                                   \
+       ditem->prev->next = ditem->next;                                       \
+       ditem->next->prev = ditem->prev;                                       \
+       h->dh.count--;                                                         \
+       return container_of(ditem, type, field.di);                            \
+}                                                                              \
+macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
+{                                                                              \
+       struct dlist_item *ditem = h->dh.hitem.next;                           \
+       if (ditem == &h->dh.hitem)                                             \
+               return NULL;                                                   \
+       return container_of(ditem, type, field.di);                            \
+}                                                                              \
+macro_pure type *prefix ## _next(struct prefix##_head * h, type *item)         \
+{                                                                              \
+       struct dlist_item *ditem = &item->field.di;                            \
+       if (ditem->next == &h->dh.hitem)                                       \
+               return NULL;                                                   \
+       return container_of(ditem->next, type, field.di);                      \
+}                                                                              \
+macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
+{                                                                              \
+       if (!item)                                                             \
+               return NULL;                                                   \
+       return prefix ## _next(h, item);                                       \
+}                                                                              \
+macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
+{                                                                              \
+       return h->dh.count;                                                    \
+}                                                                              \
+/* ... */
+
 /* single-linked list, sorted.
  * can be used as priority queue with add / pop
  */