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 A
  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
  64 /*!
  65  @brief iterate over a list safe against removal of list entry
  66  @param it the &a_slist_node to use as a loop counter
  67  @param at another &a_slist_node to use as temporary storage
  68  @param ctx points to singly linked list head
  69 */
  70 #define a_slist_forsafe(it, at, ctx)                      \
  71     for (a_slist_node *at = &(ctx)->head, *it = at->next; \
  72          it; at = it ? it : at, it = at->next)
  73
  74 /*!
  75  @brief constructor for singly linked list head
  76  @param[in,out] ctx points to singly linked list head
  77 */
  78 A_INTERN void a_slist_ctor(a_slist *ctx)
  79 {
  80     ctx->head.next = A_NULL;
  81     ctx->tail = &ctx->head;
  82 }
  83
  84 /*!
  85  @brief initialize for singly linked list head
  86  @param[in,out] ctx points to singly linked list head
  87 */
  88 A_INTERN void a_slist_init(a_slist *ctx)
  89 {
  90     ctx->head.next = A_NULL;
  91     ctx->tail = &ctx->head;
  92 }
  93
  94 /*!
  95  @brief destructor for singly linked list head
  96  @param[in,out] ctx points to singly linked list head
  97 */
  98 A_INTERN void a_slist_dtor(a_slist *ctx)
  99 {
 100     ctx->head.next = A_NULL;
 101     ctx->tail = &ctx->head;
 102 }
 103
 104 /*!
 105  @brief link head node and tail node
 106  @param[in,out] head the head node of a list
 107  @param[in,out] tail the tail node of a list
 108 */
 109 A_INTERN void a_slist_link(a_slist_node *head, a_slist_node *tail) { head->next = tail; }
 110
 111 /*!
 112  @brief insert a node to a list
 113  @param[in,out] ctx points to singly linked list head
 114  @param[in] prev previous singly linked list node
 115  @param[in] node a singly linked list node
 116 */
 117 A_INTERN void a_slist_add(a_slist *ctx, a_slist_node *prev, a_slist_node *node)
 118 {
 119     if (!prev->next) { ctx->tail = node; }
 120     a_slist_link(node, prev->next);
 121     a_slist_link(prev, node);
 122 }
 123
 124 /*!
 125  @brief insert a node to a list head
 126  @param[in,out] ctx points to singly linked list head
 127  @param[in] node a singly linked list node
 128 */
 129 A_INTERN void a_slist_add_head(a_slist *ctx, a_slist_node *node)
 130 {
 131     a_slist_add(ctx, &ctx->head, node);
 132 }
 133
 134 /*!
 135  @brief insert a node to a list tail
 136  @param[in,out] ctx points to singly linked list head
 137  @param[in] node a singly linked list node
 138 */
 139 A_INTERN void a_slist_add_tail(a_slist *ctx, a_slist_node *node)
 140 {
 141     a_slist_link(ctx->tail, node);
 142     node->next = A_NULL;
 143     ctx->tail = node;
 144 }
 145
 146 /*!
 147  @brief delete a node from a list
 148  @param[in,out] ctx points to singly linked list head
 149  @param[in] prev previous singly linked list node
 150 */
 151 A_INTERN void a_slist_del(a_slist *ctx, a_slist_node *prev)
 152 {
 153     a_slist_node *const node = prev->next;
 154     if (node)
 155     {
 156         a_slist_link(prev, node->next);
 157         if (!node->next) { ctx->tail = prev; }
 158     }
 159 }
 160
 161 /*!
 162  @brief delete a node from a list head
 163  @param[in,out] ctx points to singly linked list head
 164 */
 165 A_INTERN void a_slist_del_head(a_slist *ctx)
 166 {
 167     a_slist_node *const node = ctx->head.next;
 168     if (node)
 169     {
 170         a_slist_link(&ctx->head, node->next);
 171         if (!node->next) { ctx->tail = &ctx->head; }
 172     }
 173 }
 174
 175 /*!
 176  @brief moving a list to another list
 177  @param[in] ctx points to singly linked list head
 178  @param[in,out] to another linked list to be inserted
 179  @param[in] at the previous &a_slist_node of the inserted node
 180 */
 181 A_INTERN void a_slist_mov(a_slist *ctx, a_slist *to, a_slist_node *at)
 182 {
 183     a_slist_node *const node = ctx->head.next;
 184     if (node)
 185     {
 186         if (!at->next) { to->tail = ctx->tail; }
 187         a_slist_link(ctx->tail, at->next);
 188         a_slist_link(at, node);
 189     }
 190 }
 191
 192 /*!
 193  @brief rotate a node in the list
 194  @param[in,out] ctx points to singly linked list head
 195 */
 196 A_INTERN void a_slist_rot(a_slist *ctx)
 197 {
 198     a_slist_node *const node = ctx->head.next;
 199     if (node)
 200     {
 201         a_slist_link(&ctx->head, node->next);
 202         a_slist_link(ctx->tail, node);
 203         node->next = A_NULL;
 204         ctx->tail = node;
 205     }
 206 }
 207
 208 /*! @} A_SLIST */
 209
 210 #endif /* a/slist.h */