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

   1 /* GNU LGPL version 2 (or later) - see LICENSE file for details */
   2 #ifndef CCAN_LPQ_H
   3 #define CCAN_LPQ_H
   4
   5 #include <stdbool.h>
   6
   7 #include <ccan/cast/cast.h>
   8 #include <ccan/tcon/tcon.h>
   9 #include <ccan/order/order.h>
  10
  11 /**
  12  * struct lpq_link - a priority link
  13  * @next: next entry in the list of items in the priority queue
  14  *
  15  * This is used as a link within a priority queue entry.
  16  *
  17  * Example:
  18  *      struct waiter {
  19  *              char *name;
  20  *              int priority;
  21  *              struct lpq_link pql;
  22  *      };
  23  */
  24 struct lpq_link {
  25         struct lpq_link *next;
  26 };
  27
  28 /**
  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
  32  */
  33 struct lpq_ {
  34         struct _total_order order;
  35         struct lpq_link *list;
  36 };
  37
  38 /**
  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
  42  *
  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
  45  * lpq.
  46  *
  47  * See also:
  48  *      lpq_init()
  49  */
  50 #define LPQ(etype_, link_)                              \
  51         TCON_WRAP(struct lpq_,                          \
  52                   TCON_CONTAINER(canary, etype_, link_))
  53
  54 /**
  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
  58  *
  59  * Example:
  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);
  63  */
  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),  \
  68                                    (order_ctx_)),                       \
  69                   (order_ctx_))
  70 static inline void lpq_init_(struct lpq_ *pq,
  71                              _total_order_cb order_cb, void *order_ctx)
  72 {
  73         pq->order.cb = order_cb;
  74         pq->order.ctx = order_ctx;
  75         pq->list = NULL;
  76 }
  77
  78 /**
  79  * lpq_empty - is a priority queue empty?
  80  * @pq: the priority queue
  81  *
  82  * If the priority queue is empty, returns true.
  83  */
  84 #define lpq_empty(pq_) \
  85         lpq_empty_(tcon_unwrap(pq_))
  86 static inline bool lpq_empty_(const struct lpq_ *pq)
  87 {
  88         return (pq->list == NULL);
  89 }
  90
  91 /**
  92  * lpq_entry - convert an lpq_link back into the structure containing it.
  93  * @pq: the priority queue
  94  * @l: the lpq_link
  95  */
  96 #define lpq_entry(pq_, l_) tcon_container_of((pq_), canary, (l_))
  97
  98 /**
  99  * lpq_frontp_ - get pointer to pointer to front element (internal function)
 100  */
 101 struct lpq_link **lpq_frontp_(struct lpq_ *pq, size_t offset);
 102
 103 /**
 104  * lpq_front - get front (highest priority) entry in a priority queue
 105  * @pq: the priority queue
 106  *
 107  * If the priority queue is empty, returns NULL.
 108  *
 109  * Example:
 110  *      struct waiter *f;
 111  *
 112  *      f = lpq_front(pqp);
 113  *      assert(lpq_dequeue(pqp) == f);
 114  */
 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)
 119 {
 120         struct lpq_link **frontp = lpq_frontp_(cast_const(struct lpq_ *, pq),
 121                                                offset);
 122
 123         return frontp ? *frontp : NULL;
 124 }
 125
 126 /**
 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
 130  *
 131  * The lpq_link does not need to be initialized; it will be overwritten.
 132  */
 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)
 136 {
 137         e->next = pq->list;
 138         pq->list = e;
 139 }
 140
 141 /**
 142  * lpq_dequeue - remove and return the highest priority item from the
 143  *               priority queue
 144  * @pq: the priority queue
 145  *
 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.
 148  */
 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)
 153 {
 154         struct lpq_link **frontp = lpq_frontp_(pq, offset);
 155         struct lpq_link *front;
 156
 157         if (!frontp)
 158                 return NULL;
 159
 160         front = *frontp;
 161         *frontp = front->next;
 162         return front;
 163 }
 164
 165 /**
 166  * lpq_reorder - adjust the queue after an element changes priority
 167  * @pq: the priority queue
 168  * @e: the entry which has changed priority
 169  *
 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
 172  * called on @pq.
 173  *
 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
 177  * later.
 178  */
 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)
 182 {
 183 }
 184
 185 #endif /* CCAN_LPQ_H */