1 /* GNU LGPL version 2 (or later) - see LICENSE file for details */
7 #include <ccan/cast/cast.h>
8 #include <ccan/tcon/tcon.h>
9 #include <ccan/order/order.h>
12 * struct lpq_link - a priority link
13 * @next: next entry in the list of items in the priority queue
15 * This is used as a link within a priority queue entry.
21 * struct lpq_link pql;
25 struct lpq_link *next;
29 * struct lpq_ - a linear priority queue (internal type)
30 * @order: ordering callback to compare entry priorities
31 * @list: head of the list of items in the priority queue
34 struct _total_order order;
35 struct lpq_link *list;
39 * LPQ - define and initialize an empty priority queue
40 * @type: type of items in the queue / items compared by the callback
41 * @link: name of the lpq_link field in @type
43 * The LPQ macro defines an lpq and initializes it to an empty
44 * priority queue. It can be prepended by "static" to define a static
50 #define LPQ(etype_, link_) \
51 TCON_WRAP(struct lpq_, \
52 TCON_CONTAINER(canary, etype_, link_))
55 * lpq_init - initialize a priority queue
56 * @pq: the lpq to set to an empty queue
57 * @order: priority ordering callback for items in the queue
60 * total_order_by_field(my_order, int, struct waiter, priority);
61 * LPQ(struct waiter, pql) *pqp = malloc(sizeof(*pqp));
62 * lpq_init(pqp, my_order.cb, my_order.ctx);
64 #define lpq_init(pq_, order_cb_, order_ctx_) \
65 lpq_init_(tcon_unwrap(pq_), \
66 total_order_cast((order_cb_), \
67 tcon_container_type((pq_), canary), \
70 static inline void lpq_init_(struct lpq_ *pq,
71 _total_order_cb order_cb, void *order_ctx)
73 pq->order.cb = order_cb;
74 pq->order.ctx = order_ctx;
79 * lpq_empty - is a priority queue empty?
80 * @pq: the priority queue
82 * If the priority queue is empty, returns true.
84 #define lpq_empty(pq_) \
85 lpq_empty_(tcon_unwrap(pq_))
86 static inline bool lpq_empty_(const struct lpq_ *pq)
88 return (pq->list == NULL);
92 * lpq_entry - convert an lpq_link back into the structure containing it.
93 * @pq: the priority queue
96 #define lpq_entry(pq_, l_) tcon_container_of((pq_), canary, (l_))
99 * lpq_frontp_ - get pointer to pointer to front element (internal function)
101 struct lpq_link **lpq_frontp_(struct lpq_ *pq, size_t offset);
104 * lpq_front - get front (highest priority) entry in a priority queue
105 * @pq: the priority queue
107 * If the priority queue is empty, returns NULL.
112 * f = lpq_front(pqp);
113 * assert(lpq_dequeue(pqp) == f);
115 #define lpq_front(pq_) \
116 lpq_entry((pq_), lpq_front_(tcon_unwrap(pq_), \
117 tcon_offset((pq_), canary)))
118 static inline struct lpq_link *lpq_front_(const struct lpq_ *pq, size_t offset)
120 struct lpq_link **frontp = lpq_frontp_(cast_const(struct lpq_ *, pq),
123 return frontp ? *frontp : NULL;
127 * lpq_enqueue - add an entry to a priority queue
128 * @pq: the priority queue to add the node to
129 * @e: the item to enqueue
131 * The lpq_link does not need to be initialized; it will be overwritten.
133 #define lpq_enqueue(pq_, e_) \
134 lpq_enqueue_(tcon_unwrap(pq_), tcon_member_of((pq_), canary, (e_)))
135 static inline void lpq_enqueue_(struct lpq_ *pq, struct lpq_link *e)
142 * lpq_dequeue - remove and return the highest priority item from the
144 * @pq: the priority queue
146 * Note that this leaves the returned entry's link in an undefined
147 * state; it can be added to another queue, but not deleted again.
149 #define lpq_dequeue(pq_) \
150 lpq_entry((pq_), lpq_dequeue_(tcon_unwrap(pq_), \
151 tcon_offset((pq_), canary)))
152 static inline struct lpq_link *lpq_dequeue_(struct lpq_ *pq, size_t offset)
154 struct lpq_link **frontp = lpq_frontp_(pq, offset);
155 struct lpq_link *front;
161 *frontp = front->next;
166 * lpq_reorder - adjust the queue after an element changes priority
167 * @pq: the priority queue
168 * @e: the entry which has changed priority
170 * If any element already inserted into @pq is altered to change its
171 * priority, lpq_reorder() must be called before any other function is
174 * NOTE: For the dumb priority queue implementation in lpq, this is
175 * actually a no-op. But this call exists so that users will be more
176 * easily able to change to a better priority queue implementation
179 #define lpq_reorder(pq_, e_) \
180 (lpq_reorder_(tcon_unwrap(pq_), tcon_member_of((pq_), canary, (e_))))
181 static inline void lpq_reorder_(struct lpq_ *pq, struct lpq_link *e)
185 #endif /* CCAN_LPQ_H */