1 /* Licensed under BSD-MIT - see LICENSE file for details */
9 #include <ccan/container_of/container_of.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 - the head of a queue
29 * @b: the back of the queue (NULL if empty)
32 struct lqueue_link *back;
36 * LQUEUE - define and initialize an empty queue
37 * @name: the name of the lqueue.
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.
48 * assert(lqueue_empty(&my_queue));
50 #define LQUEUE(name) \
51 struct lqueue name = { NULL, }
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
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().
66 * struct lqueue queue2;
69 * struct lqueue_link link;
72 * lqueue_enqueue(&queue1, &el, link);
74 * lqueue_init_from_back(&queue2,
75 * lqueue_back(&queue1, struct element, link), link);
77 #define lqueue_init_from_back(s, e, member) \
78 (lqueue_init_((s), &(e)->member))
81 * lqueue_init - initialize a queue
82 * @h: the lqueue to set to an empty queue
85 * struct lqueue *qp = malloc(sizeof(*qp));
88 #define lqueue_init(s) \
89 (lqueue_init_((s), NULL))
90 static inline void lqueue_init_(struct lqueue *q, struct lqueue_link *back)
96 * lqueue_empty - is a queue empty?
99 * If the queue is empty, returns true.
102 * assert(lqueue_empty(qp));
104 static inline bool lqueue_empty(const struct lqueue *q)
106 return (q->back == NULL);
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
118 * struct lqueue_link ql;
120 * assert(lqueue_entry(&w.ql, struct waiter, ql) == &w);
122 #define lqueue_entry(n, type, member) container_of_or_null(n, type, member)
125 * lqueue_front - get front entry in a queue
127 * @type: the type of queue entries
128 * @member: the lqueue_link entry
130 * If the queue is empty, returns NULL.
135 * f = lqueue_front(qp, struct waiter, ql);
136 * assert(lqueue_dequeue(qp, struct waiter, ql) == f);
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)
145 return q->back->next;
149 * lqueue_back - get back entry in a queue
151 * @type: the type of queue entries
152 * @member: the lqueue_link entry
154 * If the queue is empty, returns NULL.
159 * lqueue_enqueue(qp, &b, ql);
160 * assert(lqueue_back(qp, struct waiter, ql) == &b);
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)
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
175 * The lqueue_link does not need to be initialized; it will be overwritten.
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)
181 if (lqueue_empty(q)) {
182 /* New entry will be both front and back of queue */
186 e->next = lqueue_front_(q);
193 * lqueue_dequeue - remove and return the entry from the front of the queue
195 * @type: the type of queue entries
196 * @member: the lqueue_link field of @type
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.
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)
205 struct lqueue_link *front;
210 front = lqueue_front_(q);
211 if (front == lqueue_back_(q)) {
212 assert(front->next == front);
215 q->back->next = front->next;
220 #endif /* CCAN_LQUEUE_H */