* 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>
*/
-#ifndef MWARE_LIST_H
-#define MWARE_LIST_H
+#ifndef STRUCT_LIST_H
+#define STRUCT_LIST_H
#include <cfg/compiler.h> /* INLINE */
#include <cfg/debug.h> /* ASSERT_VALID_PTR() */
* ADDHEAD(&foo_list, &foo1);
* INSERT_BEFORE(&foo_list, &foo2);
* FOREACH_NODE(fp, &foo_list)
- * fp->a = 10;
+ * fp->a = 10;
* }
*
* \endcode
(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 { \
ASSERT(n == &(l)->tail); \
} while (0)
+ /// Checks that a node isn't part of a given list
+ #define LIST_ASSERT_NOT_CONTAINS(list,node) \
+ do { \
+ Node *ln; \
+ ASSERT_VALID_PTR(list); \
+ ASSERT_VALID_PTR(node); \
+ FOREACH_NODE(ln, list) \
+ ASSERT(ln != (Node *)(node)); \
+ } while (0)
+
#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
+/** Tell whether a list is empty. */
+#define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
+
/** Add node to list head. */
#define ADDHEAD(l,n) \
do { \
- ASSERT_VALID_PTR(l); \
- ASSERT_VALID_PTR(n); \
+ LIST_ASSERT_NOT_CONTAINS((l),(n)); \
(n)->succ = (l)->head.succ; \
(n)->pred = (l)->head.succ->pred; \
(n)->succ->pred = (n); \
/** Add node to list tail. */
#define ADDTAIL(l,n) \
do { \
- ASSERT_VALID_PTR(l); \
- ASSERT_VALID_PTR(n); \
+ LIST_ASSERT_NOT_CONTAINS((l),(n)); \
(n)->succ = &(l)->tail; \
(n)->pred = (l)->tail.pred; \
(n)->pred->succ = (n); \
INVALIDATE_NODE(n); \
} while (0)
-/** Tell whether a list is empty. */
-#define LIST_EMPTY(l) ( (void *)((l)->head.succ) == (void *)(&(l)->tail) )
+/**
+ * Insert a priority node in a priority queue.
+ *
+ * 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.
+ * 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 { \
PriNode *ln; \
- ASSERT_VALID_PTR(list); \
- ASSERT_VALID_PTR(node); \
+ LIST_ASSERT_NOT_CONTAINS((list),(node)); \
FOREACH_NODE(ln, (list)) \
if (ln->pri < (node)->pri) \
break; \
return n;
}
-#endif /* MWARE_LIST_H */
+/** \} */ //defgroup list
+
+#endif /* STRUCT_LIST_H */
projects / bertos.git / blobdiff