git.ozlabs.org Git - ccan/blob - ccan/lqueue/lqueue.h

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #ifndef CCAN_LQUEUE_H
   3 #define CCAN_LQUEUE_H
   4
   5 #include <stdbool.h>
   6 #include <stdio.h>
   7 #include <assert.h>
   8
   9 #include <ccan/tcon/tcon.h>
  10
  11 /**
  12  * struct lqueue_link - a queue link
  13  * @next: next entry, or front of queue, if this is the back
  14  *
  15  * This is used as a link within a queue entry.
  16  *
  17  * Example:
  18  *      struct waiter {
  19  *              char *name;
  20  *              struct lqueue_link ql;
  21  *      };
  22  */
  23 struct lqueue_link {
  24         struct lqueue_link *next;
  25 };
  26
  27 /**
  28  * struct lqueue_ - a queue (internal type)
  29  * @b: the back of the queue (NULL if empty)
  30  */
  31 struct lqueue_ {
  32         struct lqueue_link *back;
  33 };
  34
  35 /**
  36  * LQUEUE - declare a queue
  37  * @type: the type of elements in the queue
  38  * @link: the field containing the lqueue_link in @type
  39  *
  40  * The LQUEUE macro declares an lqueue.  It can be prepended by
  41  * "static" to define a static lqueue.  The queue begins in undefined
  42  * state, you must either initialize with LQUEUE_INIT, or call
  43  * lqueue_init() before using it.
  44  *
  45  * See also:
  46  *      lqueue_init()
  47  *
  48  * Example:
  49  *      struct element {
  50  *              int value;
  51  *              struct lqueue_link link;
  52  *      };
  53  *      LQUEUE(struct element, link) my_queue;
  54  */
  55 #define LQUEUE(etype, link)                                             \
  56         TCON_WRAP(struct lqueue_,                                       \
  57                   TCON_CONTAINER(canary, etype, link))
  58
  59 /**
  60  * LQUEUE_INIT - initializer for an empty queue
  61  *
  62  * The LQUEUE_INIT macro returns a suitable initializer for a queue
  63  * defined with LQUEUE.
  64  *
  65  * Example:
  66  *      struct element {
  67  *              int value;
  68  *              struct lqueue_link link;
  69  *      };
  70  *      LQUEUE(struct element, link) my_queue = LQUEUE_INIT;
  71  *
  72  *      assert(lqueue_empty(&my_queue));
  73  */
  74 #define LQUEUE_INIT                             \
  75         TCON_WRAP_INIT({ NULL, })
  76
  77 /**
  78  * lqueue_entry - convert an lqueue_link back into the structure containing it.
  79  * @q: the queue
  80  * @l: the lqueue_link
  81  *
  82  * Example:
  83  *      struct waiter {
  84  *              char *name;
  85  *              struct lqueue_link ql;
  86  *      } w;
  87  *      LQUEUE(struct waiter, ql) my_queue;
  88  *      assert(lqueue_entry(&my_queue, &w.ql) == &w);
  89  */
  90 #define lqueue_entry(q_, l_) tcon_container_of((q_), canary, (l_))
  91
  92 /**
  93  * lqueue_init_from_back - initialize a queue with a specific back element
  94  * @s: the lqueue to initialize
  95  * @e: pointer to the back element of the new queue
  96  *
  97  * USE WITH CAUTION: This is for handling unusual cases where you have
  98  * a pointer to an element in a previously constructed queue but can't
  99  * conveniently pass around a normal struct lqueue.  Usually you
 100  * should use lqueue_init().
 101  *
 102  * Example:
 103  *      struct element {
 104  *              int value;
 105  *              struct lqueue_link link;
 106  *      } el;
 107  *      LQUEUE(struct element, link) queue1;
 108  *      LQUEUE(struct element, link) queue2;
 109  *
 110  *      lqueue_enqueue(&queue1, &el);
 111  *
 112  *      lqueue_init_from_back(&queue2, lqueue_back(&queue1));
 113  */
 114 #define lqueue_init_from_back(q_, e_)                                   \
 115         (lqueue_init_(tcon_unwrap(q_), tcon_member_of((q_), canary, (e_))))
 116
 117 /**
 118  * lqueue_init - initialize a queue
 119  * @h: the lqueue to set to an empty queue
 120  *
 121  * Example:
 122  *      struct element {
 123  *              int value;
 124  *              struct lqueue_link link;
 125  *      };
 126  *      LQUEUE(struct element, link) *qp = malloc(sizeof(*qp));
 127  *      lqueue_init(qp);
 128  */
 129 #define lqueue_init(q_) \
 130         (lqueue_init_(tcon_unwrap(q_), NULL))
 131 static inline void lqueue_init_(struct lqueue_ *q, struct lqueue_link *back)
 132 {
 133         q->back = back;
 134 }
 135
 136 /**
 137  * lqueue_empty - is a queue empty?
 138  * @q: the queue
 139  *
 140  * If the queue is empty, returns true.
 141  */
 142 #define lqueue_empty(q_) \
 143         lqueue_empty_(tcon_unwrap(q_))
 144 static inline bool lqueue_empty_(const struct lqueue_ *q)
 145 {
 146         return (q->back == NULL);
 147 }
 148
 149 /**
 150  * lqueue_front - get front entry in a queue
 151  * @q: the queue
 152  *
 153  * If the queue is empty, returns NULL.
 154  *
 155  * Example:
 156  *      struct element *f;
 157  *
 158  *      f = lqueue_front(qp);
 159  *      assert(lqueue_dequeue(qp) == f);
 160  */
 161 #define lqueue_front(q_) \
 162         lqueue_entry((q_), lqueue_front_(tcon_unwrap(q_)))
 163 static inline struct lqueue_link *lqueue_front_(const struct lqueue_ *q)
 164 {
 165         if (!q->back)
 166                 return NULL;
 167         else
 168                 return q->back->next;
 169 }
 170
 171 /**
 172  * lqueue_back - get back entry in a queue
 173  * @q: the queue
 174  *
 175  * If the queue is empty, returns NULL.
 176  *
 177  * Example:
 178  *      struct element b;
 179  *
 180  *      lqueue_enqueue(qp, &b);
 181  *      assert(lqueue_back(qp) == &b);
 182  */
 183 #define lqueue_back(q_) \
 184         lqueue_entry((q_), lqueue_back_(tcon_unwrap(q_)))
 185 static inline struct lqueue_link *lqueue_back_(const struct lqueue_ *q)
 186 {
 187         return q->back;
 188 }
 189
 190 /**
 191  * lqueue_enqueue - add an entry to the back of a queue
 192  * @q: the queue to add the node to
 193  * @e: the item to enqueue
 194  *
 195  * The lqueue_link does not need to be initialized; it will be overwritten.
 196  */
 197 #define lqueue_enqueue(q_, e_)                  \
 198         lqueue_enqueue_(tcon_unwrap(q_), tcon_member_of((q_), canary, (e_)))
 199 static inline void lqueue_enqueue_(struct lqueue_ *q, struct lqueue_link *e)
 200 {
 201         if (lqueue_empty_(q)) {
 202                 /* New entry will be both front and back of queue */
 203                 e->next = e;
 204                 q->back = e;
 205         } else {
 206                 e->next = lqueue_front_(q);
 207                 q->back->next = e;
 208                 q->back = e;
 209         }
 210 }
 211
 212 /**
 213  * lqueue_dequeue - remove and return the entry from the front of the queue
 214  * @q: the queue
 215  *
 216  * Note that this leaves the returned entry's link in an undefined
 217  * state; it can be added to another queue, but not deleted again.
 218  */
 219 #define lqueue_dequeue(q_) \
 220         lqueue_entry((q_), lqueue_dequeue_(tcon_unwrap(q_)))
 221 static inline struct lqueue_link *lqueue_dequeue_(struct lqueue_ *q)
 222 {
 223         struct lqueue_link *front;
 224
 225         if (lqueue_empty_(q))
 226                 return NULL;
 227
 228         front = lqueue_front_(q);
 229         if (front == lqueue_back_(q)) {
 230                 assert(front->next == front);
 231                 q->back = NULL;
 232         } else {
 233                 q->back->next = front->next;
 234         }
 235         return front;
 236 }
 237
 238 #endif /* CCAN_LQUEUE_H */