include/a/que.h

   1 /*!
   2  @file que.h
   3  @brief basic queue library
   4 */
   5
   6 #ifndef LIBA_QUE_H
   7 #define LIBA_QUE_H
   8
   9 #include "a.h"
  10 #include "list.h"
  11
  12 /*!
  13  @ingroup A
  14  @addtogroup A_QUE basic queue library
  15  @{
  16 */
  17
  18 /*!
  19  @brief instance structure for basic queue
  20 */
  21 typedef struct a_que
  22 {
  23     a_list head_; /*!< element head */
  24     a_list **ptr_; /*!< mempool block */
  25     a_size siz_; /*!< element sizeof */
  26     a_size num_; /*!< element number */
  27     a_size cur_; /*!< mempool cursor */
  28     a_size mem_; /*!< mempool memory */
  29 } a_que;
  30
  31 /*!
  32  @brief access size of a element for a pointer to queue structure
  33  @param[in] ctx points to an instance of queue structure
  34 */
  35 A_INTERN a_size a_que_siz(a_que const *ctx) { return ctx->siz_; }
  36
  37 /*!
  38  @brief access number of element for a pointer to queue structure
  39  @param[in] ctx points to an instance of queue structure
  40 */
  41 A_INTERN a_size a_que_num(a_que const *ctx) { return ctx->num_; }
  42
  43 /*!
  44  @brief access foremost element for a pointer to queue structure
  45  @param[in] ctx points to an instance of queue structure
  46  @note should check if queue is empty
  47  @return element pointer
  48 */
  49 A_INTERN void *a_que_fore_(a_que const *ctx)
  50 {
  51     return a_cast_s(void *, ctx->head_.next + 1);
  52 }
  53
  54 /*!
  55  @brief access backmost element for a pointer to queue structure
  56  @param[in] ctx points to an instance of queue structure
  57  @note should check if queue is empty
  58  @return element pointer
  59 */
  60 A_INTERN void *a_que_back_(a_que const *ctx)
  61 {
  62     return a_cast_s(void *, ctx->head_.prev + 1);
  63 }
  64
  65 /*!
  66  @brief access foremost element for a pointer to queue structure
  67  @param[in] ctx points to an instance of queue structure
  68  @return element pointer
  69   @retval 0 empty queue
  70 */
  71 A_INTERN void *a_que_fore(a_que const *ctx)
  72 {
  73     return a_likely(ctx->head_.next != &ctx->head_) ? a_que_fore_(ctx) : A_NULL;
  74 }
  75
  76 /*!
  77  @brief access backmost element for a pointer to queue structure
  78  @param[in] ctx points to an instance of queue structure
  79  @return element pointer
  80   @retval 0 empty queue
  81 */
  82 A_INTERN void *a_que_back(a_que const *ctx)
  83 {
  84     return a_likely(ctx->head_.prev != &ctx->head_) ? a_que_back_(ctx) : A_NULL;
  85 }
  86
  87 /*!
  88  @brief swap elements lhs and rhs for a pointer to queue structure
  89  @param[in] lhs element pointer on the left
  90  @param[in] rhs element pointer on the right
  91 */
  92 A_INTERN void a_que_swap_(void *lhs, void *rhs)
  93 {
  94     a_list_swap_node(a_cast_s(a_list *, lhs) - 1, a_cast_s(a_list *, rhs) - 1);
  95 }
  96
  97 #if defined(__cplusplus)
  98 extern "C" {
  99 #endif /* __cplusplus */
 100
 101 /*!
 102  @brief allocate a pointer to queue structure from memory
 103  @param[in] size size of element
 104 */
 105 A_EXTERN a_que *a_que_new(a_size size);
 106
 107 /*!
 108  @brief deallocate a pointer to queue structure
 109  @param[in] ctx points to an instance of queue structure
 110  @param[in] dtor element destructor
 111 */
 112 A_EXTERN void a_que_die(a_que *ctx, void (*dtor)(void *));
 113
 114 /*!
 115  @brief constructor for queue structure
 116  @param[in] ctx points to an instance of queue structure
 117  @param[in] size size of element
 118 */
 119 A_EXTERN void a_que_ctor(a_que *ctx, a_size size);
 120
 121 /*!
 122  @brief destructor for queue structure
 123  @param[in] ctx points to an instance of queue structure
 124  @param[in] dtor element destructor
 125 */
 126 A_EXTERN void a_que_dtor(a_que *ctx, void (*dtor)(void *));
 127
 128 /*!
 129  @brief initialize a pointer to queue structure by moving
 130  @param[in] ctx points to an instance of queue structure
 131  @param[in] obj input source pointing to an instance
 132 */
 133 A_EXTERN void a_que_move(a_que *ctx, a_que *obj);
 134
 135 /*!
 136  @brief access specified element for a pointer to queue structure
 137  @param[in] ctx points to an instance of queue structure
 138  @param[in] idx index of element, 0 ~ n-1, -n ~ -1
 139  @return element pointer
 140   @retval 0 out of bounds
 141 */
 142 A_EXTERN void *a_que_at(a_que const *ctx, a_imax idx);
 143
 144 /*!
 145  @brief drop all the elements for a pointer to queue structure
 146  @param[in] ctx points to an instance of queue structure
 147  @param[in] dtor current element destructor
 148  @return the execution state of the function
 149   @retval 0 success
 150   @retval 1 failure
 151 */
 152 A_EXTERN int a_que_drop(a_que *ctx, void (*dtor)(void *));
 153
 154 /*!
 155  @brief edit size of a element for a pointer to queue structure
 156  @param[in] ctx points to an instance of queue structure
 157  @param[in] size the size of the new element
 158  @param[in] dtor previous element destructor
 159  @return the execution state of the function
 160   @retval 0 success
 161   @retval 1 failure
 162 */
 163 A_EXTERN int a_que_edit(a_que *ctx, a_size size, void (*dtor)(void *));
 164
 165 /*!
 166  @brief swap elements lhs and rhs for a pointer to queue structure
 167  @param[in] ctx points to an instance of queue structure
 168  @param[in] lhs element index on the left
 169  @param[in] rhs element index on the right
 170  @return the execution state of the function
 171   @retval 0 success
 172   @retval 1 failure
 173 */
 174 A_EXTERN int a_que_swap(a_que const *ctx, a_size lhs, a_size rhs);
 175
 176 /*!
 177  @brief insert sort foremost element for a pointer to queue structure
 178  @code{.c}
 179  T *obj = a_que_push_fore(T, ctx);
 180  if (obj)
 181  {
 182      CTOR(obj);
 183      INIT(obj);
 184      a_que_sort_fore(ctx, cmp);
 185  }
 186  @endcode
 187  @param[in] ctx points to an instance of queue structure
 188  @param[in] cmp a function that compares two elements
 189   @arg cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
 190   @arg cmp(lhs,rhs)<0 *lhs goes before *rhs
 191   @arg cmp(lhs,rhs)>0 *lhs goes after *rhs
 192 */
 193 A_EXTERN void a_que_sort_fore(a_que const *ctx, int (*cmp)(void const *, void const *));
 194
 195 /*!
 196  @brief insert sort backmost element for a pointer to queue structure
 197  @code{.c}
 198  T *obj = a_que_push_back(T, ctx);
 199  if (obj)
 200  {
 201      CTOR(obj);
 202      INIT(obj);
 203      a_que_sort_back(ctx, cmp);
 204  }
 205  @endcode
 206  @param[in] ctx points to an instance of queue structure
 207  @param[in] cmp a function that compares two elements
 208   @arg cmp(lhs,rhs)==0 *lhs is equivalent to *rhs
 209   @arg cmp(lhs,rhs)<0 *lhs goes before *rhs
 210   @arg cmp(lhs,rhs)>0 *lhs goes after *rhs
 211 */
 212 A_EXTERN void a_que_sort_back(a_que const *ctx, int (*cmp)(void const *, void const *));
 213
 214 /*!
 215  @brief push an element into the queue forward
 216  @param[in] ctx points to an instance of queue structure
 217  @return element pointer
 218   @retval 0 failure
 219 */
 220 A_EXTERN void *a_que_push_fore(a_que *ctx);
 221
 222 /*!
 223  @brief push an element into the queue backward
 224  @param[in] ctx points to an instance of queue structure
 225  @return element pointer
 226   @retval 0 failure
 227 */
 228 A_EXTERN void *a_que_push_back(a_que *ctx);
 229
 230 /*!
 231  @brief pull an element from the queue forward
 232  @param[in] ctx points to an instance of queue structure
 233  @return element pointer
 234   @retval 0 failure
 235 */
 236 A_EXTERN void *a_que_pull_fore(a_que *ctx);
 237
 238 /*!
 239  @brief pull an element from the queue backward
 240  @param[in] ctx points to an instance of queue structure
 241  @return element pointer
 242   @retval 0 failure
 243 */
 244 A_EXTERN void *a_que_pull_back(a_que *ctx);
 245
 246 /*!
 247  @brief insert an element into the queue
 248  @param[in] ctx points to an instance of queue structure
 249  @param[in] idx index of element in this queue
 250   @arg 0 a_que_push_fore
 251   @arg n a_que_push_back
 252  @return element pointer
 253   @retval 0 failure
 254 */
 255 A_EXTERN void *a_que_insert(a_que *ctx, a_size idx);
 256
 257 /*!
 258  @brief remove an element from the queue
 259  @param[in] ctx points to an instance of queue structure
 260  @param[in] idx index of element in this queue
 261   @arg 0 a_que_pull_fore
 262   @arg n a_que_pull_back
 263  @return element pointer
 264   @retval 0 failure
 265 */
 266 A_EXTERN void *a_que_remove(a_que *ctx, a_size idx);
 267
 268 #if defined(__cplusplus)
 269 } /* extern "C" */
 270 #endif /* __cplusplus */
 271
 272 /*!
 273  @brief iterate over a queue
 274  @code{.c}
 275  a_que_foreach(T, it, ctx)
 276  {
 277      assert(a_que_siz(ctx) >= sizeof(*it));
 278  }
 279  @endcode
 280  @param T type of elements in the queue
 281  @param it the &a_que to use as a loop counter
 282  @param ctx points to an instance of queue structure
 283 */
 284 #define a_que_foreach(T, it, ctx)                                  \
 285     for (T *it = a_cast_r(T *, (ctx)->head_.next),                 \
 286            *it##_ = a_cast_r(T *, a_list_(*, it)->next);           \
 287          a_list_(*, it) != &(ctx)->head_                           \
 288              ? ((void)(it = a_cast_r(T *, a_list_(*, it) + 1)), 1) \
 289              : (0);                                                \
 290          it = it##_, it##_ = a_cast_r(T *, a_list_(*, it)->next))
 291
 292 /*!
 293  @brief iterate over a queue in reverse
 294  @code{.c}
 295  a_que_foreach_reverse(T, it, ctx)
 296  {
 297      assert(a_que_siz(ctx) >= sizeof(*it));
 298  }
 299  @endcode
 300  @param T type of elements in the queue
 301  @param it the &a_que to use as a loop counter
 302  @param ctx points to an instance of queue structure
 303 */
 304 #define a_que_foreach_reverse(T, it, ctx)                          \
 305     for (T *it = a_cast_r(T *, (ctx)->head_.prev),                 \
 306            *it##_ = a_cast_r(T *, a_list_(*, it)->prev);           \
 307          a_list_(*, it) != &(ctx)->head_                           \
 308              ? ((void)(it = a_cast_r(T *, a_list_(*, it) + 1)), 1) \
 309              : (0);                                                \
 310          it = it##_, it##_ = a_cast_r(T *, a_list_(*, it)->prev))
 311
 312 #define a_que_fore(T, ctx) a_cast_s(T *, a_que_fore(ctx))
 313 #define a_que_back(T, ctx) a_cast_s(T *, a_que_back(ctx))
 314 #define a_que_fore_(T, ctx) a_cast_s(T *, a_que_fore_(ctx))
 315 #define a_que_back_(T, ctx) a_cast_s(T *, a_que_back_(ctx))
 316 #define a_que_at(T, ctx, idx) a_cast_s(T *, a_que_at(ctx, idx))
 317 #define a_que_push_fore(T, ctx) a_cast_s(T *, a_que_push_fore(ctx))
 318 #define a_que_push_back(T, ctx) a_cast_s(T *, a_que_push_back(ctx))
 319 #define a_que_pull_fore(T, ctx) a_cast_s(T *, a_que_pull_fore(ctx))
 320 #define a_que_pull_back(T, ctx) a_cast_s(T *, a_que_pull_back(ctx))
 321 #define a_que_insert(T, ctx, idx) a_cast_s(T *, a_que_insert(ctx, idx))
 322 #define a_que_remove(T, ctx, idx) a_cast_s(T *, a_que_remove(ctx, idx))
 323
 324 /*! @} A_QUE */
 325
 326 #endif /* a/que.h */