#ifndef lib_slist_h #define lib_slist_h /* Cesar project {{{ * * Copyright (C) 2009 Spidcom * * <<>> * * }}} */ /** * \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 #define SLIST_ASSERT dbg_claim #define SLIST_ASSERT_PTR dbg_claim_ptr /** * 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)) \ { \ SLIST_ASSERT_PTR (SLIST_TAIL (prefix, type)); \ SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type));, type) \ SLIST_TAIL (prefix, type)->next = (first); \ } \ else \ { \ SLIST_SIZE_DO (SLIST_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)) \ { \ SLIST_ASSERT_PTR (SLIST_TAIL (prefix, type)); \ SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type));, type) \ (last)->next = SLIST_HEAD (prefix, type); \ } \ else \ { \ SLIST_SIZE_DO (SLIST_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); \ SLIST_ASSERT (popped); \ SLIST_SIZE_DO (SLIST_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 (SLIST_ASSERT (SLIST_SIZE (prefix, type) \ == (size));, type) \ dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \ SLIST_HEAD (prefix, type) = NULL; \ } \ else \ { \ SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type) \ >= (size));, type) \ SLIST_HEAD (prefix, type) = (at)->next; \ } \ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= (size);, type) \ } while (0) /** * Sever a list in the middle. * \param prefix list prefix * \param after element to sever after, or NULL for begin of list * \param until element until which to sever, included * \param size if type includes size, number of element removed * \param type optional list type * * Every elements after first given element excluded and before second given * element included will be removed from the list. */ #define slist_sever(prefix, after, until, size_type...) \ PASTE_EXPAND (_slist_sever_, PREPROC_NARG (size_type)) \ (prefix, after, until, ## size_type) /* As both size and type is optional, here is some trickery: */ #define _slist_sever_0(prefix, after, until) \ _slist_sever_n (prefix, after, until, @unused@) #define _slist_sever_1(prefix, after, until, type) \ _slist_sever_n (prefix, after, until, @unused@, type) #define _slist_sever_2(prefix, after, until, size, type) \ _slist_sever_n (prefix, after, until, size, type) #define _slist_sever_n(prefix, after, until, size, type...) \ do { \ SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type) \ >= (size));, type) \ if (!after) \ { \ if (SLIST_TAIL (prefix, type) == (until)) \ { \ dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \ SLIST_HEAD (prefix, type) = NULL; \ } \ else \ { \ SLIST_HEAD (prefix, type) = (until)->next; \ } \ } \ else \ { \ if (SLIST_TAIL (prefix, type) == (until)) \ { \ SLIST_TAIL (prefix, type) = (after); \ } \ else \ { \ (after)->next = (until)->next; \ } \ } \ SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= (size);, type) \ } while (0) #endif /* lib_slist_h */