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/container_of/container_of.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 - the head of a queue
  29  * @b: the back of the queue (NULL if empty)
  30  */
  31 struct lqueue {
  32         struct lqueue_link *back;
  33 };
  34
  35 /**
  36  * LQUEUE - define and initialize an empty queue
  37  * @name: the name of the lqueue.
  38  *
  39  * The LQUEUE macro defines an lqueue and initializes it to an empty
  40  * queue.  It can be prepended by "static" to define a static lqueue.
  41  *
  42  * See also:
  43  *      lqueue_init()
  44  *
  45  * Example:
  46  *      LQUEUE(my_queue);
  47  *
  48  *      assert(lqueue_empty(&my_queue));
  49  */
  50 #define LQUEUE(name) \
  51         struct lqueue name = { NULL, }
  52
  53 /**
  54  * lqueue_init_from_back - initialize a queue with a specific back element
  55  * @s: the lqueue to initialize
  56  * @e: pointer to the back element of the new queue
  57  * @member: member of the element containing the lqueue_link
  58  *
  59  * USE WITH CAUTION: This is for handling unusual cases where you have
  60  * a pointer to an element in a previously constructed queue but can't
  61  * conveniently pass around a normal struct lqueue.  Usually you
  62  * should use lqueue_init().
  63  *
  64  * Example:
  65  *      LQUEUE(queue1);
  66  *      struct lqueue queue2;
  67  *      struct element {
  68  *              int value;
  69  *              struct lqueue_link link;
  70  *      } el;
  71  *
  72  *      lqueue_enqueue(&queue1, &el, link);
  73  *
  74  *      lqueue_init_from_back(&queue2,
  75  *                            lqueue_back(&queue1, struct element, link), link);
  76  */
  77 #define lqueue_init_from_back(s, e, member) \
  78         (lqueue_init_((s), &(e)->member))
  79
  80 /**
  81  * lqueue_init - initialize a queue
  82  * @h: the lqueue to set to an empty queue
  83  *
  84  * Example:
  85  *      struct lqueue *qp = malloc(sizeof(*qp));
  86  *      lqueue_init(qp);
  87  */
  88 #define lqueue_init(s) \
  89         (lqueue_init_((s), NULL))
  90 static inline void lqueue_init_(struct lqueue *q, struct lqueue_link *back)
  91 {
  92         q->back = back;
  93 }
  94
  95 /**
  96  * lqueue_empty - is a queue empty?
  97  * @q: the queue
  98  *
  99  * If the queue is empty, returns true.
 100  *
 101  * Example:
 102  *      assert(lqueue_empty(qp));
 103  */
 104 static inline bool lqueue_empty(const struct lqueue *q)
 105 {
 106         return (q->back == NULL);
 107 }
 108
 109 /**
 110  * lqueue_entry - convert an lqueue_link back into the structure containing it.
 111  * @e: the lqueue_link
 112  * @type: the type of the entry
 113  * @member: the lqueue_link member of the type
 114  *
 115  * Example:
 116  *      struct waiter {
 117  *              char *name;
 118  *              struct lqueue_link ql;
 119  *      } w;
 120  *      assert(lqueue_entry(&w.ql, struct waiter, ql) == &w);
 121  */
 122 #define lqueue_entry(n, type, member) container_of_or_null(n, type, member)
 123
 124 /**
 125  * lqueue_front - get front entry in a queue
 126  * @q: the queue
 127  * @type: the type of queue entries
 128  * @member: the lqueue_link entry
 129  *
 130  * If the queue is empty, returns NULL.
 131  *
 132  * Example:
 133  *      struct waiter *f;
 134  *
 135  *      f = lqueue_front(qp, struct waiter, ql);
 136  *      assert(lqueue_dequeue(qp, struct waiter, ql) == f);
 137  */
 138 #define lqueue_front(q, type, member) \
 139         lqueue_entry(lqueue_front_((q)), type, member)
 140 static inline struct lqueue_link *lqueue_front_(const struct lqueue *q)
 141 {
 142         if (!q->back)
 143                 return NULL;
 144         else
 145                 return q->back->next;
 146 }
 147
 148 /**
 149  * lqueue_back - get back entry in a queue
 150  * @q: the queue
 151  * @type: the type of queue entries
 152  * @member: the lqueue_link entry
 153  *
 154  * If the queue is empty, returns NULL.
 155  *
 156  * Example:
 157  *      struct waiter b;
 158  *
 159  *      lqueue_enqueue(qp, &b, ql);
 160  *      assert(lqueue_back(qp, struct waiter, ql) == &b);
 161  */
 162 #define lqueue_back(q, type, member) \
 163         lqueue_entry(lqueue_back_((q)), type, member)
 164 static inline struct lqueue_link *lqueue_back_(const struct lqueue *q)
 165 {
 166         return q->back;
 167 }
 168
 169 /**
 170  * lqueue_enqueue - add an entry to the back of a queue
 171  * @q: the queue to add the node to
 172  * @e: the item to enqueue
 173  * @member: the lqueue_link field of *e
 174  *
 175  * The lqueue_link does not need to be initialized; it will be overwritten.
 176  */
 177 #define lqueue_enqueue(q, e, member) \
 178         lqueue_enqueue_((q), &((e)->member))
 179 static inline void lqueue_enqueue_(struct lqueue *q, struct lqueue_link *e)
 180 {
 181         if (lqueue_empty(q)) {
 182                 /* New entry will be both front and back of queue */
 183                 e->next = e;
 184                 q->back = e;
 185         } else {
 186                 e->next = lqueue_front_(q);
 187                 q->back->next = e;
 188                 q->back = e;
 189         }
 190 }
 191
 192 /**
 193  * lqueue_dequeue - remove and return the entry from the front of the queue
 194  * @q: the queue
 195  * @type: the type of queue entries
 196  * @member: the lqueue_link field of @type
 197  *
 198  * Note that this leaves the returned entry's link in an undefined
 199  * state; it can be added to another queue, but not deleted again.
 200  */
 201 #define lqueue_dequeue(q, type, member) \
 202         lqueue_entry(lqueue_dequeue_((q)), type, member)
 203 static inline struct lqueue_link *lqueue_dequeue_(struct lqueue *q)
 204 {
 205         struct lqueue_link *front;
 206
 207         if (lqueue_empty(q))
 208                 return NULL;
 209
 210         front = lqueue_front_(q);
 211         if (front == lqueue_back_(q)) {
 212                 assert(front->next == front);
 213                 q->back = NULL;
 214         } else {
 215                 q->back->next = front->next;
 216         }
 217         return front;
 218 }
 219
 220 #endif /* CCAN_LQUEUE_H */