1 /* Licensed under BSD-MIT - see LICENSE file for details */
9 #include <ccan/tcon/tcon.h>
12 * struct lqueue_link - a queue link
13 * @next: next entry, or front of queue, if this is the back
15 * This is used as a link within a queue entry.
20 * struct lqueue_link ql;
24 struct lqueue_link *next;
28 * struct lqueue_ - a queue (internal type)
29 * @b: the back of the queue (NULL if empty)
32 struct lqueue_link *back;
36 * LQUEUE - declare a queue
37 * @type: the type of elements in the queue
38 * @link: the field containing the lqueue_link in @type
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.
51 * struct lqueue_link link;
53 * LQUEUE(struct element, link) my_queue;
55 #define LQUEUE(etype, link) \
56 TCON_WRAP(struct lqueue_, \
57 TCON_CONTAINER(canary, etype, link))
60 * LQUEUE_INIT - initializer for an empty queue
62 * The LQUEUE_INIT macro returns a suitable initializer for a queue
63 * defined with LQUEUE.
68 * struct lqueue_link link;
70 * LQUEUE(struct element, link) my_queue = LQUEUE_INIT;
72 * assert(lqueue_empty(&my_queue));
75 TCON_WRAP_INIT({ NULL, })
78 * lqueue_entry - convert an lqueue_link back into the structure containing it.
85 * struct lqueue_link ql;
87 * LQUEUE(struct waiter, ql) my_queue;
88 * assert(lqueue_entry(&my_queue, &w.ql) == &w);
90 #define lqueue_entry(q_, l_) tcon_container_of((q_), canary, (l_))
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
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().
105 * struct lqueue_link link;
107 * LQUEUE(struct element, link) queue1;
108 * LQUEUE(struct element, link) queue2;
110 * lqueue_enqueue(&queue1, &el);
112 * lqueue_init_from_back(&queue2, lqueue_back(&queue1));
114 #define lqueue_init_from_back(q_, e_) \
115 (lqueue_init_(tcon_unwrap(q_), tcon_member_of((q_), canary, (e_))))
118 * lqueue_init - initialize a queue
119 * @h: the lqueue to set to an empty queue
124 * struct lqueue_link link;
126 * LQUEUE(struct element, link) *qp = malloc(sizeof(*qp));
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)
137 * lqueue_empty - is a queue empty?
140 * If the queue is empty, returns true.
142 #define lqueue_empty(q_) \
143 lqueue_empty_(tcon_unwrap(q_))
144 static inline bool lqueue_empty_(const struct lqueue_ *q)
146 return (q->back == NULL);
150 * lqueue_front - get front entry in a queue
153 * If the queue is empty, returns NULL.
158 * f = lqueue_front(qp);
159 * assert(lqueue_dequeue(qp) == f);
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)
168 return q->back->next;
172 * lqueue_back - get back entry in a queue
175 * If the queue is empty, returns NULL.
180 * lqueue_enqueue(qp, &b);
181 * assert(lqueue_back(qp) == &b);
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)
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
195 * The lqueue_link does not need to be initialized; it will be overwritten.
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)
201 if (lqueue_empty_(q)) {
202 /* New entry will be both front and back of queue */
206 e->next = lqueue_front_(q);
213 * lqueue_dequeue - remove and return the entry from the front of the queue
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.
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)
223 struct lqueue_link *front;
225 if (lqueue_empty_(q))
228 front = lqueue_front_(q);
229 if (front == lqueue_back_(q)) {
230 assert(front->next == front);
233 q->back->next = front->next;
238 #endif /* CCAN_LQUEUE_H */