osfmk/kern/circle_queue.h

   1 /*
   2  * Copyright (c) 2019 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #ifndef _KERN_CIRCLE_QUEUE_H_
  30 #define _KERN_CIRCLE_QUEUE_H_
  31
  32 #include <kern/queue.h>
  33 #include <kern/assert.h>
  34
  35 __BEGIN_DECLS
  36
  37 /*
  38  * Circle Queue Management APIs
  39  *
  40  * These are similar to the queues from queue.h,
  41  * but the circle queue head is a single pointer to the first element
  42  * of the queue.
  43  */
  44
  45 typedef struct circle_queue_head {
  46         queue_entry_t head;
  47 } circle_queue_head_t, *circle_queue_t;
  48
  49 static inline bool
  50 circle_queue_empty(circle_queue_t cq)
  51 {
  52         return cq->head == NULL;
  53 }
  54
  55 static inline queue_entry_t
  56 circle_queue_first(circle_queue_t cq)
  57 {
  58         return cq->head;
  59 }
  60
  61 static inline queue_entry_t
  62 circle_queue_last(circle_queue_t cq)
  63 {
  64         queue_entry_t elt = circle_queue_first(cq);
  65         if (elt) {
  66                 __builtin_assume(elt->prev != NULL);
  67                 return elt->prev;
  68         }
  69         return NULL;
  70 }
  71
  72 static inline queue_entry_t
  73 circle_queue_next(circle_queue_t cq, queue_entry_t elt)
  74 {
  75         return elt->next == cq->head ? NULL : elt->next;
  76 }
  77
  78 static inline size_t
  79 circle_queue_length(circle_queue_t cq)
  80 {
  81         queue_entry_t elt = circle_queue_first(cq);
  82         size_t n = 0;
  83
  84         for (; elt; elt = circle_queue_next(cq, elt)) {
  85                 n++;
  86         }
  87         return n;
  88 }
  89
  90 static inline void
  91 circle_enqueue_tail(circle_queue_t cq, queue_entry_t elt)
  92 {
  93         queue_entry_t head = circle_queue_first(cq);
  94         queue_entry_t tail = circle_queue_last(cq);
  95
  96         if (head == NULL) {
  97                 cq->head = elt->next = elt->prev = elt;
  98         } else {
  99                 elt->next = head;
 100                 elt->prev = tail;
 101                 tail->next = elt;
 102                 head->prev = elt;
 103         }
 104 }
 105
 106 static inline void
 107 circle_enqueue_head(circle_queue_t cq, queue_entry_t elt)
 108 {
 109         circle_enqueue_tail(cq, elt);
 110         cq->head = elt;
 111 }
 112
 113 static inline void
 114 circle_dequeue(circle_queue_t cq, queue_entry_t elt)
 115 {
 116         queue_entry_t elt_prev = elt->prev;
 117         queue_entry_t elt_next = elt->next;
 118
 119         if (elt == elt_next) {
 120                 assert(cq->head == elt);
 121                 cq->head = NULL;
 122         } else {
 123                 elt_prev->next = elt_next;
 124                 elt_next->prev = elt_prev;
 125                 if (cq->head == elt) {
 126                         cq->head = elt_next;
 127                 }
 128         }
 129         __DEQUEUE_ELT_CLEANUP(elt);
 130 }
 131
 132 static inline queue_entry_t
 133 circle_dequeue_head(circle_queue_t cq)
 134 {
 135         queue_entry_t elt = circle_queue_first(cq);
 136         if (elt) {
 137                 circle_dequeue(cq, elt);
 138         }
 139         return elt;
 140 }
 141
 142 static inline queue_entry_t
 143 circle_dequeue_tail(circle_queue_t cq)
 144 {
 145         queue_entry_t elt = circle_queue_last(cq);
 146         if (elt) {
 147                 circle_dequeue(cq, elt);
 148         }
 149         return elt;
 150 }
 151
 152 static inline void
 153 circle_queue_rotate_head_forward(circle_queue_t cq)
 154 {
 155         queue_entry_t first = circle_queue_first(cq);
 156         if (first != NULL) {
 157                 cq->head = first->next;
 158         }
 159 }
 160
 161 static inline void
 162 circle_queue_rotate_head_backward(circle_queue_t cq)
 163 {
 164         queue_entry_t last = circle_queue_last(cq);
 165         if (last != NULL) {
 166                 cq->head = last;
 167         }
 168 }
 169
 170 /*
 171  *      Macro:          cqe_element
 172  *      Function:
 173  *              Convert a cirle_queue_entry_t pointer to a queue element pointer.
 174  *              Get a pointer to the user-defined element containing
 175  *              a given cirle_queue_entry_t
 176  *      Header:
 177  *              <type> * cqe_element(cirle_queue_entry_t qe, <type>, field)
 178  *                      qe      - queue entry to convert
 179  *                      <type>  - what's in the queue (e.g., struct some_data)
 180  *                      <field> - is the chain field in <type>
 181  *      Note:
 182  *              Do not use pointer types for <type>
 183  */
 184 #define cqe_element(qe, type, field) __container_of(qe, type, field)
 185
 186 /*
 187  *      Macro:          cqe_foreach
 188  *      Function:
 189  *              Iterate over each queue_entry_t structure.
 190  *              Generates a 'for' loop, setting 'qe' to
 191  *              each queue_entry_t in the queue.
 192  *      Header:
 193  *              cqe_foreach(queue_entry_t qe, queue_t head)
 194  *                      qe   - iteration variable
 195  *                      head - pointer to queue_head_t (head of queue)
 196  *      Note:
 197  *              This should only be used with Method 1 queue iteration (linkage chains)
 198  */
 199 #define cqe_foreach(qe, head) \
 200         for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe))
 201
 202 /*
 203  *      Macro:          cqe_foreach_safe
 204  *      Function:
 205  *              Safely iterate over each queue_entry_t structure.
 206  *
 207  *              Use this iterator macro if you plan to remove the
 208  *              queue_entry_t, qe, from the queue during the
 209  *              iteration.
 210  *      Header:
 211  *              cqe_foreach_safe(queue_entry_t qe, queue_t head)
 212  *                      qe   - iteration variable
 213  *                      head - pointer to queue_head_t (head of queue)
 214  *      Note:
 215  *              This should only be used with Method 1 queue iteration (linkage chains)
 216  */
 217 #define cqe_foreach_safe(qe, head) \
 218         for (queue_entry_t _ne, _qe = circle_queue_first(head); \
 219              (qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \
 220              _qe = _ne)
 221
 222 /*
 223  *      Macro:          cqe_foreach_element
 224  *      Function:
 225  *              Iterate over each _element_ in a queue
 226  *              where each queue_entry_t points to another
 227  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 228  *              [de|en]queue_tail / remqueue / etc. function.
 229  *      Header:
 230  *              cqe_foreach_element(<type> *elt, queue_t head, <field>)
 231  *                      elt     - iteration variable
 232  *                      <type>  - what's in the queue (e.g., struct some_data)
 233  *                      <field> - is the chain field in <type>
 234  *      Note:
 235  *              This should only be used with Method 1 queue iteration (linkage chains)
 236  */
 237 #define cqe_foreach_element(elt, head, field) \
 238         for (queue_entry_t _qe = circle_queue_first(head); \
 239              _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \
 240              _qe = circle_queue_next(head, _qe))
 241
 242 /*
 243  *      Macro:          cqe_foreach_element_safe
 244  *      Function:
 245  *              Safely iterate over each _element_ in a queue
 246  *              where each queue_entry_t points to another
 247  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 248  *              [de|en]queue_tail / remqueue / etc. function.
 249  *
 250  *              Use this iterator macro if you plan to remove the
 251  *              element, elt, from the queue during the iteration.
 252  *      Header:
 253  *              cqe_foreach_element_safe(<type> *elt, queue_t head, <field>)
 254  *                      elt     - iteration variable
 255  *                      <type>  - what's in the queue (e.g., struct some_data)
 256  *                      <field> - is the chain field in <type>
 257  *      Note:
 258  *              This should only be used with Method 1 queue iteration (linkage chains)
 259  */
 260 #define cqe_foreach_element_safe(elt, head, field) \
 261         for (queue_entry_t _ne, _qe = circle_queue_first(head); \
 262              _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \
 263              _ne = circle_queue_next(head, _qe), 1); \
 264              _qe = _ne)
 265
 266 /* Dequeue an element from head, or return NULL if the queue is empty */
 267 #define cqe_dequeue_head(head, type, field) ({ \
 268         queue_entry_t _tmp_entry = circle_dequeue_head((head)); \
 269         type *_tmp_element = (type*) NULL; \
 270         if (_tmp_entry != (queue_entry_t) NULL) \
 271                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 272         _tmp_element; \
 273 })
 274
 275 /* Dequeue an element from tail, or return NULL if the queue is empty */
 276 #define cqe_dequeue_tail(head, type, field) ({ \
 277         queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \
 278         type *_tmp_element = (type*) NULL; \
 279         if (_tmp_entry != (queue_entry_t) NULL) \
 280                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 281         _tmp_element; \
 282 })
 283
 284 /* Peek at the first element, or return NULL if the queue is empty */
 285 #define cqe_queue_first(head, type, field) ({ \
 286         queue_entry_t _tmp_entry = circle_queue_first((head)); \
 287         type *_tmp_element = (type*) NULL; \
 288         if (_tmp_entry != (queue_entry_t) NULL) \
 289                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 290         _tmp_element; \
 291 })
 292
 293 /* Peek at the next element, or return NULL if it is last */
 294 #define cqe_queue_next(elt, head, type, field) ({ \
 295         queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \
 296         type *_tmp_element = (type*) NULL; \
 297         if (_tmp_entry != (queue_entry_t) NULL) \
 298                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 299         _tmp_element; \
 300 })
 301
 302 /* Peek at the tail element, or return NULL if the queue is empty */
 303 #define cqe_queue_last(head, type, field) ({ \
 304         queue_entry_t _tmp_entry = circle_queue_last((head)); \
 305         type *_tmp_element = (type*) NULL; \
 306         if (_tmp_entry != (queue_entry_t) NULL) \
 307                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 308         _tmp_element; \
 309 })
 310
 311 /*
 312  *      Macro:          circle_queue_init
 313  *      Function:
 314  *              Initialize the given circle queue.
 315  *      Header:
 316  *              void circle_queue_init(q)
 317  *                      circle_queue_t          q;      \* MODIFIED *\
 318  */
 319 #define circle_queue_init(q)   \
 320 MACRO_BEGIN             \
 321         (q)->head = NULL; \
 322 MACRO_END
 323
 324 __END_DECLS
 325
 326 #endif  /* _KERN_QUEUE_H_ */