summaryrefslogtreecommitdiff
path: root/cesar/lib/slist.h
diff options
context:
space:
mode:
authorschodet2009-04-16 14:14:14 +0000
committerschodet2009-04-16 14:14:14 +0000
commit0a25a3317873ca79b5eb406b1fe6207977dce84b (patch)
tree1d4d6fb27f9ec28dcd491f6a59753d3a7bbe1a77 /cesar/lib/slist.h
parent8442f6fa2ff2ddb1bcb9fbf829b19353ea816ccf (diff)
* lib/slist:
- added single linked list service. git-svn-id: svn+ssh://pessac/svn/cesar/trunk@4488 017c9cb6-072f-447c-8318-d5b54f68fe89
Diffstat (limited to 'cesar/lib/slist.h')
-rw-r--r--cesar/lib/slist.h273
1 files changed, 273 insertions, 0 deletions
diff --git a/cesar/lib/slist.h b/cesar/lib/slist.h
new file mode 100644
index 0000000000..222dda3a92
--- /dev/null
+++ b/cesar/lib/slist.h
@@ -0,0 +1,273 @@
+#ifndef lib_slist_h
+#define lib_slist_h
+/* Cesar project {{{
+ *
+ * Copyright (C) 2009 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file lib/slist.h
+ * \brief Single linked lists.
+ * \ingroup lib
+ *
+ * Provide a set of macro to help single linked list manipulation.
+ *
+ * A single linked list is defined as two node pointers (head and tail) and an
+ * optional size. Macros defined in this file can handle several kind of
+ * definitions types:
+ *
+ * Type paste (default):
+ *
+ * \code
+ * struct {
+ * node_t *mylist_head, *mylist_tail;
+ * } s;
+ * slist_init (s.mylist_);
+ * \endcode
+ *
+ * Type paste_size:
+ *
+ * \code
+ * struct {
+ * node_t *mylist_head, *mylist_tail;
+ * uint mylist_size
+ * } s;
+ * slist_init (s.mylist_, paste_size);
+ * \endcode
+ *
+ * Type bare:
+ *
+ * \code
+ * struct {
+ * node_t *head, *tail;
+ * } s;
+ * slist_init (s., bare);
+ * \endcode
+ *
+ * Type bare_size:
+ *
+ * \code
+ * struct {
+ * node_t *head, *tail;
+ * uint size
+ * } s;
+ * slist_init (s., bare_size);
+ * \endcode
+ */
+
+/* Internal macros to evaluate type. */
+#define SLIST_HEAD(prefix, type) (SLIST_HEAD_ ## type (prefix))
+#define SLIST_TAIL(prefix, type) (SLIST_TAIL_ ## type (prefix))
+#define SLIST_SIZE(prefix, type) (SLIST_SIZE_ ## type (prefix))
+#define SLIST_SIZE_DO(smth, type) SLIST_SIZE_DO_ ## type (smth)
+
+/* Default type is paste. */
+#define SLIST_HEAD_ SLIST_HEAD_paste
+#define SLIST_TAIL_ SLIST_TAIL_paste
+#define SLIST_SIZE_ SLIST_SIZE_paste
+#define SLIST_SIZE_DO_ SLIST_SIZE_DO_paste
+
+/* Type paste: append head or tail to prefix, no size. */
+#define SLIST_HEAD_paste(prefix) PASTE (prefix, head)
+#define SLIST_TAIL_paste(prefix) PASTE (prefix, tail)
+#define SLIST_SIZE_paste(prefix) @undef@
+#define SLIST_SIZE_DO_paste(smth)
+
+/* Type paste_size: append head, tail or size to prefix. */
+#define SLIST_HEAD_paste_size(prefix) PASTE (prefix, head)
+#define SLIST_TAIL_paste_size(prefix) PASTE (prefix, tail)
+#define SLIST_SIZE_paste_size(prefix) PASTE (prefix, size)
+#define SLIST_SIZE_DO_paste_size(smth) smth
+
+/* Type bare: use head or tail with no prefix, no size. */
+#define SLIST_HEAD_bare(prefix) prefix head
+#define SLIST_TAIL_bare(prefix) prefix tail
+#define SLIST_SIZE_bare(prefix) @undef@
+#define SLIST_SIZE_DO_bare(smth)
+
+/* Type bare_size: use head, tail or size with no prefix. */
+#define SLIST_HEAD_bare_size(prefix) prefix head
+#define SLIST_TAIL_bare_size(prefix) prefix tail
+#define SLIST_SIZE_bare_size(prefix) prefix size
+#define SLIST_SIZE_DO_bare_size(smth) smth
+
+/**
+ * Initialise a single linked list.
+ * \param prefix list prefix
+ * \param type optional list type
+ */
+#define slist_init(prefix, type...) \
+ do { \
+ SLIST_HEAD (prefix, type) = NULL; \
+ dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
+ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) = 0;, type) \
+ } while (0)
+
+/**
+ * Test whether a list is empty.
+ * \param prefix list prefix
+ * \param type optional list type
+ * \return true if empty
+ */
+#define slist_empty(prefix, type...) \
+ (!(SLIST_HEAD (prefix, type)))
+
+/**
+ * Push a single element at end of list.
+ * \param prefix list prefix
+ * \param node node to push
+ * \param type optional list type
+ */
+#define slist_push_back(prefix, node, type...) \
+ slist_push_back_range (prefix, node, node, 1, type)
+
+/**
+ * Push multiple elements at end of list.
+ * \param prefix list prefix
+ * \param first first element to push
+ * \param last last element to push
+ * \param size if type includes size, number of element pushed
+ * \param type optional list type
+ */
+#define slist_push_back_range(prefix, first, last, size_type...) \
+ PASTE_EXPAND (_slist_push_back_range_, PREPROC_NARG (size_type)) \
+ (prefix, first, last, ## size_type)
+
+/* As both size and type is optional, here is some trickery: */
+#define _slist_push_back_range_0(prefix, first, last) \
+ _slist_push_back_range_n (prefix, first, last, @unused@)
+#define _slist_push_back_range_1(prefix, first, last, type) \
+ _slist_push_back_range_n (prefix, first, last, @unused@, type)
+#define _slist_push_back_range_2(prefix, first, last, size, type) \
+ _slist_push_back_range_n (prefix, first, last, size, type)
+
+#define _slist_push_back_range_n(prefix, first, last, size, type...) \
+ do { \
+ if (SLIST_HEAD (prefix, type)) \
+ { \
+ dbg_assert_ptr (SLIST_TAIL (prefix, type)); \
+ SLIST_SIZE_DO (dbg_assert (SLIST_SIZE (prefix, type));, type) \
+ SLIST_TAIL (prefix, type)->next = (first); \
+ } \
+ else \
+ { \
+ SLIST_SIZE_DO (dbg_assert (!SLIST_SIZE (prefix, type));, type) \
+ SLIST_HEAD (prefix, type) = (first); \
+ } \
+ SLIST_TAIL (prefix, type) = (last); \
+ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) += (size);, type) \
+ } while (0)
+
+/**
+ * Push a single element at begin of list.
+ * \param prefix list prefix
+ * \param node node to push
+ * \param type optional list type
+ */
+#define slist_push_front(prefix, node, type...) \
+ slist_push_front_range (prefix, node, node, 1, type)
+
+/**
+ * Push multiple elements at begin of list.
+ * \param prefix list prefix
+ * \param first first element to push_front
+ * \param last last element to push_front
+ * \param size if type includes size, number of element pushed
+ * \param type optional list type
+ */
+#define slist_push_front_range(prefix, first, last, size_type...) \
+ PASTE_EXPAND (_slist_push_front_range_, PREPROC_NARG (size_type)) \
+ (prefix, first, last, ## size_type)
+
+/* As both size and type is optional, here is some trickery: */
+#define _slist_push_front_range_0(prefix, first, last) \
+ _slist_push_front_range_n (prefix, first, last, @unused@)
+#define _slist_push_front_range_1(prefix, first, last, type) \
+ _slist_push_front_range_n (prefix, first, last, @unused@, type)
+#define _slist_push_front_range_2(prefix, first, last, size, type) \
+ _slist_push_front_range_n (prefix, first, last, size, type)
+
+#define _slist_push_front_range_n(prefix, first, last, size, type...) \
+ do { \
+ if (SLIST_HEAD (prefix, type)) \
+ { \
+ dbg_assert_ptr (SLIST_TAIL (prefix, type)); \
+ SLIST_SIZE_DO (dbg_assert (SLIST_SIZE (prefix, type));, type) \
+ (last)->next = SLIST_HEAD (prefix, type); \
+ } \
+ else \
+ { \
+ SLIST_SIZE_DO (dbg_assert (!SLIST_SIZE (prefix, type));, type) \
+ SLIST_TAIL (prefix, type) = (last); \
+ } \
+ SLIST_HEAD (prefix, type) = (first); \
+ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) += (size);, type) \
+ } while (0)
+
+/**
+ * Pop a single element from begin of list.
+ * \param prefix list prefix
+ * \param type optional list type
+ * \return popped element
+ */
+#define slist_pop_front(prefix, type...) \
+ ({ \
+ typeof (SLIST_HEAD (prefix, type)) popped = \
+ SLIST_HEAD (prefix, type); \
+ dbg_assert (popped); \
+ SLIST_SIZE_DO (dbg_assert (SLIST_SIZE (prefix, type));, type) \
+ if (popped == SLIST_TAIL (prefix, type)) \
+ { \
+ SLIST_HEAD (prefix, type) = NULL; \
+ dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
+ } \
+ else \
+ { \
+ SLIST_HEAD (prefix, type) = popped->next; \
+ } \
+ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= 1;, type) \
+ popped; \
+ })
+
+/**
+ * Slice a list at given element.
+ * \param prefix list prefix
+ * \param at element to slice at
+ * \param size if type includes size, number of element removed
+ * \param type optional list type
+ *
+ * Every elements before given element included will be removed from the list.
+ */
+#define slist_slice(prefix, at, size_type...) \
+ PASTE_EXPAND (_slist_slice_, PREPROC_NARG (size_type)) \
+ (prefix, at, ## size_type)
+
+/* As both size and type is optional, here is some trickery: */
+#define _slist_slice_0(prefix, at) \
+ _slist_slice_n (prefix, at, @unused@)
+#define _slist_slice_1(prefix, at, type) \
+ _slist_slice_n (prefix, at, @unused@, type)
+#define _slist_slice_2(prefix, at, size, type) \
+ _slist_slice_n (prefix, at, size, type)
+
+#define _slist_slice_n(prefix, at, size, type...) \
+ do { \
+ if (SLIST_TAIL (prefix, type) == (at)) \
+ { \
+ SLIST_SIZE_DO (dbg_assert (SLIST_SIZE (prefix, type) \
+ == (size));, type) \
+ dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
+ SLIST_HEAD (prefix, type) = NULL; \
+ } \
+ else \
+ { \
+ SLIST_SIZE_DO (dbg_assert (SLIST_SIZE (prefix, type) \
+ >= (size));, type) \
+ SLIST_HEAD (prefix, type) = (at)->next; \
+ } \
+ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= (size);, type) \
+ } while (0)
+
+#endif /* lib_slist_h */