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 /*
 153  *      Macro:          cqe_element
 154  *      Function:
 155  *              Convert a cirle_queue_entry_t pointer to a queue element pointer.
 156  *              Get a pointer to the user-defined element containing
 157  *              a given cirle_queue_entry_t
 158  *      Header:
 159  *              <type> * cqe_element(cirle_queue_entry_t qe, <type>, field)
 160  *                      qe      - queue entry to convert
 161  *                      <type>  - what's in the queue (e.g., struct some_data)
 162  *                      <field> - is the chain field in <type>
 163  *      Note:
 164  *              Do not use pointer types for <type>
 165  */
 166 #define cqe_element(qe, type, field) __container_of(qe, type, field)
 167
 168 /*
 169  *      Macro:          cqe_foreach
 170  *      Function:
 171  *              Iterate over each queue_entry_t structure.
 172  *              Generates a 'for' loop, setting 'qe' to
 173  *              each queue_entry_t in the queue.
 174  *      Header:
 175  *              cqe_foreach(queue_entry_t qe, queue_t head)
 176  *                      qe   - iteration variable
 177  *                      head - pointer to queue_head_t (head of queue)
 178  *      Note:
 179  *              This should only be used with Method 1 queue iteration (linkage chains)
 180  */
 181 #define cqe_foreach(qe, head) \
 182         for (qe = circle_queue_first(head); qe; qe = circle_queue_next(head, qe))
 183
 184 /*
 185  *      Macro:          cqe_foreach_safe
 186  *      Function:
 187  *              Safely iterate over each queue_entry_t structure.
 188  *
 189  *              Use this iterator macro if you plan to remove the
 190  *              queue_entry_t, qe, from the queue during the
 191  *              iteration.
 192  *      Header:
 193  *              cqe_foreach_safe(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_safe(qe, head) \
 200         for (queue_entry_t _ne, _qe = circle_queue_first(head); \
 201              (qe = _qe) && (_ne = circle_queue_next(head, _qe), 1); \
 202              _qe = _ne)
 203
 204 /*
 205  *      Macro:          cqe_foreach_element
 206  *      Function:
 207  *              Iterate over each _element_ in a queue
 208  *              where each queue_entry_t points to another
 209  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 210  *              [de|en]queue_tail / remqueue / etc. function.
 211  *      Header:
 212  *              cqe_foreach_element(<type> *elt, queue_t head, <field>)
 213  *                      elt     - iteration variable
 214  *                      <type>  - what's in the queue (e.g., struct some_data)
 215  *                      <field> - is the chain field in <type>
 216  *      Note:
 217  *              This should only be used with Method 1 queue iteration (linkage chains)
 218  */
 219 #define cqe_foreach_element(elt, head, field) \
 220         for (queue_entry_t _qe = circle_queue_first(head); \
 221              _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), 1); \
 222              _qe = circle_queue_next(head, _qe))
 223
 224 /*
 225  *      Macro:          cqe_foreach_element_safe
 226  *      Function:
 227  *              Safely iterate over each _element_ in a queue
 228  *              where each queue_entry_t points to another
 229  *              queue_entry_t, i.e., managed by the [de|en]queue_head/
 230  *              [de|en]queue_tail / remqueue / etc. function.
 231  *
 232  *              Use this iterator macro if you plan to remove the
 233  *              element, elt, from the queue during the iteration.
 234  *      Header:
 235  *              cqe_foreach_element_safe(<type> *elt, queue_t head, <field>)
 236  *                      elt     - iteration variable
 237  *                      <type>  - what's in the queue (e.g., struct some_data)
 238  *                      <field> - is the chain field in <type>
 239  *      Note:
 240  *              This should only be used with Method 1 queue iteration (linkage chains)
 241  */
 242 #define cqe_foreach_element_safe(elt, head, field) \
 243         for (queue_entry_t _ne, _qe = circle_queue_first(head); \
 244              _qe && (elt = cqe_element(_qe, typeof(*(elt)), field), \
 245              _ne = circle_queue_next(head, _qe), 1); \
 246              _qe = _ne)
 247
 248 /* Dequeue an element from head, or return NULL if the queue is empty */
 249 #define cqe_dequeue_head(head, type, field) ({ \
 250         queue_entry_t _tmp_entry = circle_dequeue_head((head)); \
 251         type *_tmp_element = (type*) NULL; \
 252         if (_tmp_entry != (queue_entry_t) NULL) \
 253                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 254         _tmp_element; \
 255 })
 256
 257 /* Dequeue an element from tail, or return NULL if the queue is empty */
 258 #define cqe_dequeue_tail(head, type, field) ({ \
 259         queue_entry_t _tmp_entry = circle_dequeue_tail((head)); \
 260         type *_tmp_element = (type*) NULL; \
 261         if (_tmp_entry != (queue_entry_t) NULL) \
 262                 _tmp_element = cqe_element(_tmp_entry, type, field); \
 263         _tmp_element; \
 264 })
 265
 266 /* Peek at the first element, or return NULL if the queue is empty */
 267 #define cqe_queue_first(head, type, field) ({ \
 268         queue_entry_t _tmp_entry = circle_queue_first((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 /* Peek at the next element, or return NULL if it is last */
 276 #define cqe_queue_next(elt, head, type, field) ({ \
 277         queue_entry_t _tmp_entry = circle_queue_next((head), (elt)); \
 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 tail element, or return NULL if the queue is empty */
 285 #define cqe_queue_last(head, type, field) ({ \
 286         queue_entry_t _tmp_entry = circle_queue_last((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 /*
 294  *      Macro:          circle_queue_init
 295  *      Function:
 296  *              Initialize the given circle queue.
 297  *      Header:
 298  *              void circle_queue_init(q)
 299  *                      circle_queue_t          q;      \* MODIFIED *\
 300  */
 301 #define circle_queue_init(q)   \
 302 MACRO_BEGIN             \
 303         (q)->head = NULL; \
 304 MACRO_END
 305
 306 __END_DECLS
 307
 308 #endif  /* _KERN_QUEUE_H_ */