Add priority inheritance implementation for Semaphores.

[bertos.git] / bertos / struct / list.h

diff --git a/bertos/struct/list.h b/bertos/struct/list.h
index 05223caa01f70705e23435ce795c968470e98c80..96b71b4fdb05fab95f136eb96c66b0199af767dd 100644 (file)
--- a/bertos/struct/list.h
+++ b/bertos/struct/list.h
@@ -30,9 +30,49 @@
  * Copyright 2001, 2008 Bernie Innocenti <bernie@codewiz.org>
  * -->
  *
+ * \defgroup list General purpose lists
+ * \ingroup struct
+ * \{
+ *
  * \brief General pourpose double-linked lists
  *
- * \version $Id: list.h 1594 2008-08-10 12:20:10Z bernie $
+ * Lists contain nodes. You can put any custom struct into any list as long
+ * as it has a Node struct inside it. If you make the Node struct the first
+ * member of your data type, you can simply cast it to (Node *) when passing
+ * it to list functions.
+ *
+ * Lists must be initialized before use with LIST_INIT(). You can then add
+ * objects using ADDHEAD() and ADDTAIL() macros, and remove them with
+ * list_remHead() and list_remTail().
+ *
+ * You can create lists with priorities by using PriNode instead of Node as
+ * the base member struct.
+ * Use LIST_ENQUEUE() and LIST_ENQUEUE_HEAD() to insert a priority node into
+ * a list.
+ *
+ * To iterate over a list, use the macros FOREACH_NODE() and REVERSE_FOREACH_NODE()
+ * in this way:
+ * \code
+ * struct Foo
+ * {
+ *     Node n;
+ *     int a;
+ * }
+ *
+ * int main()
+ * {
+ *        List foo_list;
+ *        static Foo foo1, foo2;
+ *        Foo *fp;
+ *
+ *        LIST_INIT(&foo_list);
+ *        ADDHEAD(&foo_list, (Node *)&foo1);
+ *        INSERT_BEFORE(&foo_list, (Node *)&foo2);
+ *        FOREACH_NODE(fp, &foo_list)
+ *            fp->a = 10;
+ * }
+ * \endcode
+ *
  * \author Bernie Innocenti <bernie@codewiz.org>
  */
 
@@ -176,6 +216,21 @@ typedef struct _PriNode
                (n) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->pred) \
        )
 
+/**
+ * Iterate on the list safely against node removal.
+ *
+ * This macro generates a "for" statement using the following parameters:
+ * \param n   Node pointer to be used in each iteration.
+ * \param p   Temporal storage for the iterator.
+ * \param l   Pointer to list.
+ */
+#define FOREACH_NODE_SAFE(n, p, l) \
+       for( \
+               (n) = (TYPEOF_OR_VOIDPTR(n))LIST_HEAD(l), (p) = ((Node *)(n))->succ; \
+               ((Node *)(n))->succ; \
+               (n) = (p), (p) = (TYPEOF_OR_VOIDPTR(n))(((Node *)(n))->succ) \
+       )
+
 /** Initialize a list. */
 #define LIST_INIT(l) \
        do { \
@@ -216,6 +271,7 @@ typedef struct _PriNode
        #define INVALIDATE_NODE(n) ((n)->succ = (n)->pred = NULL)
 #else
        #define LIST_ASSERT_VALID(l) do {} while (0)
+       #define LIST_ASSERT_NOT_CONTAINS(list,node) do {} while (0)
        #define INVALIDATE_NODE(n) do {} while (0)
 #endif
 
@@ -275,9 +331,24 @@ typedef struct _PriNode
 /**
  * Insert a priority node in a priority queue.
  *
- * The new node is inserted immediately before the
- * first node with lower priority or appended to
- * the tail if no such node exists.
+ * The new node is inserted immediately before the first node with the same
+ * priority or appended to the tail if no such node exists.
+ */
+#define LIST_ENQUEUE_HEAD(list, node) \
+       do { \
+               PriNode *ln; \
+               LIST_ASSERT_NOT_CONTAINS((list),(node)); \
+               FOREACH_NODE(ln, (list)) \
+                       if (ln->pri <= (node)->pri) \
+                               break; \
+               INSERT_BEFORE(&(node)->link, &ln->link); \
+       } while (0)
+
+/**
+ * Insert a priority node in a priority queue.
+ *
+ * The new node is inserted immediately before the first node with lower
+ * priority or appended to the tail if no such node exists.
  */
 #define LIST_ENQUEUE(list, node) \
        do { \
@@ -334,4 +405,6 @@ INLINE Node *list_remTail(List *l)
        return n;
 }
 
+/** \} */ //defgroup list
+
 #endif /* STRUCT_LIST_H */