include/a/slist.h

   1 /*!
   2  @file slist.h
   3  @brief singly linked list implementation
   4 */
   5
   6 #ifndef LIBA_SLIST_H
   7 #define LIBA_SLIST_H
   8
   9 #include "a.h"
  10
  11 /*!
  12  @ingroup liba
  13  @addtogroup a_slist singly linked list
  14  @{
  15 */
  16
  17 /* clang-format off */
  18 #define A_SLIST_NODE {A_NULL}
  19 #define A_SLIST_INIT(list) {{A_NULL}, &(list).head}
  20 /* clang-format on */
  21
  22 /*!
  23  @brief instance structure for singly linked list node
  24 */
  25 typedef struct a_slist_node
  26 {
  27     struct a_slist_node *next;
  28 } a_slist_node;
  29
  30 /*!
  31  @brief cast a list pointer from another type pointer
  32  @param[in] _ additional attributes of specified type
  33  @param[in] x points to singly linked list node
  34  @return a pointer to singly linked list node
  35 */
  36 #define a_slist_(_, x) a_cast_s(a_slist_node _, a_cast_s(void _, x))
  37
  38 /*!
  39  @brief instance structure for singly linked list head
  40 */
  41 typedef struct a_slist
  42 {
  43     a_slist_node head;
  44     a_slist_node *tail;
  45 } a_slist;
  46
  47 /*!
  48  @brief access the struct for this entry
  49  @param ptr the &a_slist_node pointer
  50  @param type the type of the struct this is embedded in
  51  @param member the name of the a_slist_node within the struct
  52 */
  53 #define a_slist_entry(ptr, type, member) a_container_of(ptr, type, member)
  54 #define a_slist_entry_next(ptr, type, member) a_slist_entry((ptr)->next, type, member)
  55
  56 /*!
  57  @brief iterate over a list
  58  @param it the &a_slist_node to use as a loop counter
  59  @param ctx points to singly linked list head
  60 */
  61 #define a_slist_foreach(it, ctx) \
  62     for (a_slist_node *it = (ctx)->head.next; it; it = it->next)
  63 #define A_SLIST_FOREACH(it, ctx) \
  64     for (it = (ctx)->head.next; it; it = it->next)
  65
  66 /*!
  67  @brief iterate over a list safe against removal of list entry
  68  @param it the &a_slist_node to use as a loop counter
  69  @param at another &a_slist_node to use as temporary storage
  70  @param ctx points to singly linked list head
  71 */
  72 #define a_slist_forsafe(it, at, ctx)                      \
  73     for (a_slist_node *at = &(ctx)->head, *it = at->next; \
  74          it; at = it ? it : at, it = at->next)
  75 #define A_SLIST_FORSAFE(it, at, ctx)           \
  76     for (at = &(ctx)->head, it = at->next; it; \
  77          at = it ? it : at, it = at->next)
  78
  79 /*!
  80  @brief constructor for singly linked list head
  81  @param[in,out] ctx points to singly linked list head
  82 */
  83 A_INTERN void a_slist_ctor(a_slist *ctx)
  84 {
  85     ctx->head.next = A_NULL;
  86     ctx->tail = &ctx->head;
  87 }
  88
  89 /*!
  90  @brief initialize for singly linked list head
  91  @param[in,out] ctx points to singly linked list head
  92 */
  93 A_INTERN void a_slist_init(a_slist *ctx)
  94 {
  95     ctx->head.next = A_NULL;
  96     ctx->tail = &ctx->head;
  97 }
  98
  99 /*!
 100  @brief destructor for singly linked list head
 101  @param[in,out] ctx points to singly linked list head
 102 */
 103 A_INTERN void a_slist_dtor(a_slist *ctx)
 104 {
 105     ctx->head.next = A_NULL;
 106     ctx->tail = &ctx->head;
 107 }
 108
 109 /*!
 110  @brief link head node and tail node
 111  @param[in,out] head the head node of a list
 112  @param[in,out] tail the tail node of a list
 113 */
 114 A_INTERN void a_slist_link(a_slist_node *head, a_slist_node *tail) { head->next = tail; }
 115
 116 /*!
 117  @brief insert a node to a list
 118  @param[in,out] ctx points to singly linked list head
 119  @param[in] prev previous singly linked list node
 120  @param[in] node a singly linked list node
 121 */
 122 A_INTERN void a_slist_add(a_slist *ctx, a_slist_node *prev, a_slist_node *node)
 123 {
 124     if (!prev->next) { ctx->tail = node; }
 125     a_slist_link(node, prev->next);
 126     a_slist_link(prev, node);
 127 }
 128
 129 /*!
 130  @brief insert a node to a list head
 131  @param[in,out] ctx points to singly linked list head
 132  @param[in] node a singly linked list node
 133 */
 134 A_INTERN void a_slist_add_head(a_slist *ctx, a_slist_node *node)
 135 {
 136     a_slist_add(ctx, &ctx->head, node);
 137 }
 138
 139 /*!
 140  @brief insert a node to a list tail
 141  @param[in,out] ctx points to singly linked list head
 142  @param[in] node a singly linked list node
 143 */
 144 A_INTERN void a_slist_add_tail(a_slist *ctx, a_slist_node *node)
 145 {
 146     a_slist_link(ctx->tail, node);
 147     node->next = A_NULL;
 148     ctx->tail = node;
 149 }
 150
 151 /*!
 152  @brief delete a node from a list
 153  @param[in,out] ctx points to singly linked list head
 154  @param[in] prev previous singly linked list node
 155 */
 156 A_INTERN void a_slist_del(a_slist *ctx, a_slist_node *prev)
 157 {
 158     a_slist_node *const node = prev->next;
 159     if (node)
 160     {
 161         a_slist_link(prev, node->next);
 162         if (!node->next) { ctx->tail = prev; }
 163     }
 164 }
 165
 166 /*!
 167  @brief delete a node from a list head
 168  @param[in,out] ctx points to singly linked list head
 169 */
 170 A_INTERN void a_slist_del_head(a_slist *ctx)
 171 {
 172     a_slist_node *const node = ctx->head.next;
 173     if (node)
 174     {
 175         a_slist_link(&ctx->head, node->next);
 176         if (!node->next) { ctx->tail = &ctx->head; }
 177     }
 178 }
 179
 180 /*!
 181  @brief moving a list to another list
 182  @param[in] ctx points to singly linked list head
 183  @param[in,out] to another linked list to be inserted
 184  @param[in] at the previous &a_slist_node of the inserted node
 185 */
 186 A_INTERN void a_slist_mov(a_slist *ctx, a_slist *to, a_slist_node *at)
 187 {
 188     a_slist_node *const node = ctx->head.next;
 189     if (node)
 190     {
 191         if (!at->next) { to->tail = ctx->tail; }
 192         a_slist_link(ctx->tail, at->next);
 193         a_slist_link(at, node);
 194     }
 195 }
 196
 197 /*!
 198  @brief rotate a node in the list
 199  @param[in,out] ctx points to singly linked list head
 200 */
 201 A_INTERN void a_slist_rot(a_slist *ctx)
 202 {
 203     a_slist_node *const node = ctx->head.next;
 204     if (node)
 205     {
 206         a_slist_link(&ctx->head, node->next);
 207         a_slist_link(ctx->tail, node);
 208         node->next = A_NULL;
 209         ctx->tail = node;
 210     }
 211 }
 212
 213 /*! @} a_slist */
 214
 215 #endif /* a/slist.h */