The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/queue.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /* 
    2  * Mach Operating System
    3  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
    4  * All Rights Reserved.
    5  * 
    6  * Permission to use, copy, modify and distribute this software and its
    7  * documentation is hereby granted, provided that both the copyright
    8  * notice and this permission notice appear in all copies of the
    9  * software, derivative works or modified versions, and any portions
   10  * thereof, and that both notices appear in supporting documentation.
   11  * 
   12  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
   13  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
   14  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
   15  * 
   16  * Carnegie Mellon requests users of this software to return to
   17  *
   18  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
   19  *  School of Computer Science
   20  *  Carnegie Mellon University
   21  *  Pittsburgh PA 15213-3890
   22  *
   23  * any improvements or extensions that they make and grant Carnegie Mellon rights
   24  * to redistribute these changes.
   25  */
   26 /*
   27  * HISTORY
   28  * $Log:        queue.h,v $
   29  * Revision 2.5  92/05/21  17:15:24  jfriedl
   30  *           Removed coment starter from within comments to shut up gcc warnings.
   31  *      [92/05/16            jfriedl]
   32  * 
   33  * Revision 2.4  91/05/14  16:45:55  mrt
   34  *      Correcting copyright
   35  * 
   36  * Revision 2.3  91/02/05  17:28:43  mrt
   37  *      Changed to new Mach copyright
   38  *      [91/02/01  16:16:28  mrt]
   39  * 
   40  * Revision 2.2  89/09/08  11:26:11  dbg
   41  *      Streamlined generic queue macros.
   42  *      [89/08/17            dbg]
   43  * 
   44  * 19-Dec-88  David Golub (dbg) at Carnegie-Mellon University
   45  *      Added queue_remove_last; removed round_queue.  [Changes from
   46  *      mwyoung: 19 Dec 88.]
   47  *
   48  * 29-Nov-88  David Golub (dbg) at Carnegie-Mellon University
   49  *      Removed include of cputypes.h.  Added queue_iterate.
   50  *      Split into two groups the macros that operate directly on
   51  *      queues (or expect the queue chain to be first in a structure)
   52  *      and those that operate on generic structures (where the chain
   53  *      may be anywhere).
   54  *
   55  * 17-Jan-88  Daniel Julin (dpj) at Carnegie-Mellon University
   56  *      Added queue_enter_first, queue_last and queue_prev for use by
   57  *      the TCP netport code.
   58  *
   59  * 12-Jun-85  Avadis Tevanian (avie) at Carnegie-Mellon University
   60  *      Created.
   61  *
   62  */
   63 /*
   64  *      File:   queue.h
   65  *      Author: Avadis Tevanian, Jr.
   66  *      Date:   1985
   67  *
   68  *      Type definitions for generic queues.
   69  *
   70  */
   71 
   72 #ifndef _KERN_QUEUE_H_
   73 #define _KERN_QUEUE_H_
   74 
   75 #include <kern/lock.h>
   76 
   77 /*
   78  *      Queue of abstract objects.  Queue is maintained
   79  *      within that object.
   80  *
   81  *      Supports fast removal from within the queue.
   82  *
   83  *      How to declare a queue of elements of type "foo_t":
   84  *              In the "*foo_t" type, you must have a field of
   85  *              type "queue_chain_t" to hold together this queue.
   86  *              There may be more than one chain through a
   87  *              "foo_t", for use by different queues.
   88  *
   89  *              Declare the queue as a "queue_t" type.
   90  *
   91  *              Elements of the queue (of type "foo_t", that is)
   92  *              are referred to by reference, and cast to type
   93  *              "queue_entry_t" within this module.
   94  */
   95 
   96 /*
   97  *      A generic doubly-linked list (queue).
   98  */
   99 
  100 struct queue_entry {
  101         struct queue_entry      *next;          /* next element */
  102         struct queue_entry      *prev;          /* previous element */
  103 };
  104 
  105 typedef struct queue_entry      *queue_t;
  106 typedef struct queue_entry      queue_head_t;
  107 typedef struct queue_entry      queue_chain_t;
  108 typedef struct queue_entry      *queue_entry_t;
  109 
  110 /*
  111  *      enqueue puts "elt" on the "queue".
  112  *      dequeue returns the first element in the "queue".
  113  *      remqueue removes the specified "elt" from the specified "queue".
  114  */
  115 
  116 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
  117 #define dequeue(queue)          dequeue_head(queue)
  118 
  119 void            enqueue_head();
  120 void            enqueue_tail();
  121 queue_entry_t   dequeue_head();
  122 queue_entry_t   dequeue_tail();
  123 void            remqueue();
  124 
  125 /*
  126  *      Macro:          queue_init
  127  *      Function:
  128  *              Initialize the given queue.
  129  *      Header:
  130  *              void queue_init(q)
  131  *                      queue_t         q;      *MODIFIED*
  132  */
  133 #define queue_init(q)   ((q)->next = (q)->prev = q)
  134 
  135 /*
  136  *      Macro:          queue_first
  137  *      Function:
  138  *              Returns the first entry in the queue,
  139  *      Header:
  140  *              queue_entry_t queue_first(q)
  141  *                      queue_t q;              *IN*
  142  */
  143 #define queue_first(q)  ((q)->next)
  144 
  145 /*
  146  *      Macro:          queue_next
  147  *      Function:
  148  *              Returns the entry after an item in the queue.
  149  *      Header:
  150  *              queue_entry_t queue_next(qc)
  151  *                      queue_t qc;
  152  */
  153 #define queue_next(qc)  ((qc)->next)
  154 
  155 /*
  156  *      Macro:          queue_last
  157  *      Function:
  158  *              Returns the last entry in the queue.
  159  *      Header:
  160  *              queue_entry_t queue_last(q)
  161  *                      queue_t q;               *IN*
  162  */
  163 #define queue_last(q)   ((q)->prev)
  164 
  165 /*
  166  *      Macro:          queue_prev
  167  *      Function:
  168  *              Returns the entry before an item in the queue.
  169  *      Header:
  170  *              queue_entry_t queue_prev(qc)
  171  *                      queue_t qc;
  172  */
  173 #define queue_prev(qc)  ((qc)->prev)
  174 
  175 /*
  176  *      Macro:          queue_end
  177  *      Function:
  178  *              Tests whether a new entry is really the end of
  179  *              the queue.
  180  *      Header:
  181  *              boolean_t queue_end(q, qe)
  182  *                      queue_t q;
  183  *                      queue_entry_t qe;
  184  */
  185 #define queue_end(q, qe)        ((q) == (qe))
  186 
  187 /*
  188  *      Macro:          queue_empty
  189  *      Function:
  190  *              Tests whether a queue is empty.
  191  *      Header:
  192  *              boolean_t queue_empty(q)
  193  *                      queue_t q;
  194  */
  195 #define queue_empty(q)          queue_end((q), queue_first(q))
  196 
  197 
  198 /*----------------------------------------------------------------*/
  199 /*
  200  * Macros that operate on generic structures.  The queue
  201  * chain may be at any location within the structure, and there
  202  * may be more than one chain.
  203  */
  204 
  205 /*
  206  *      Macro:          queue_enter
  207  *      Function:
  208  *              Insert a new element at the tail of the queue.
  209  *      Header:
  210  *              void queue_enter(q, elt, type, field)
  211  *                      queue_t q;
  212  *                      <type> elt;
  213  *                      <type> is what's in our queue
  214  *                      <field> is the chain field in (*<type>)
  215  */
  216 #define queue_enter(head, elt, type, field)                     \
  217 {                                                               \
  218         register queue_entry_t prev;                            \
  219                                                                 \
  220         prev = (head)->prev;                                    \
  221         if ((head) == prev) {                                   \
  222                 (head)->next = (queue_entry_t) (elt);           \
  223         }                                                       \
  224         else {                                                  \
  225                 ((type)prev)->field.next = (queue_entry_t)(elt);\
  226         }                                                       \
  227         (elt)->field.prev = prev;                               \
  228         (elt)->field.next = head;                               \
  229         (head)->prev = (queue_entry_t) elt;                     \
  230 }
  231 
  232 /*
  233  *      Macro:          queue_enter_first
  234  *      Function:
  235  *              Insert a new element at the head of the queue.
  236  *      Header:
  237  *              void queue_enter_first(q, elt, type, field)
  238  *                      queue_t q;
  239  *                      <type> elt;
  240  *                      <type> is what's in our queue
  241  *                      <field> is the chain field in (*<type>)
  242  */
  243 #define queue_enter_first(head, elt, type, field)               \
  244 {                                                               \
  245         register queue_entry_t next;                            \
  246                                                                 \
  247         next = (head)->next;                                    \
  248         if ((head) == next) {                                   \
  249                 (head)->prev = (queue_entry_t) (elt);           \
  250         }                                                       \
  251         else {                                                  \
  252                 ((type)next)->field.prev = (queue_entry_t)(elt);\
  253         }                                                       \
  254         (elt)->field.next = next;                               \
  255         (elt)->field.prev = head;                               \
  256         (head)->next = (queue_entry_t) elt;                     \
  257 }
  258 
  259 /*
  260  *      Macro:          queue_field [internal use only]
  261  *      Function:
  262  *              Find the queue_chain_t (or queue_t) for the
  263  *              given element (thing) in the given queue (head)
  264  */
  265 #define queue_field(head, thing, type, field)                   \
  266                 (((head) == (thing)) ? (head) : &((type)(thing))->field)
  267 
  268 /*
  269  *      Macro:          queue_remove
  270  *      Function:
  271  *              Remove an arbitrary item from the queue.
  272  *      Header:
  273  *              void queue_remove(q, qe, type, field)
  274  *                      arguments as in queue_enter
  275  */
  276 #define queue_remove(head, elt, type, field)                    \
  277 {                                                               \
  278         register queue_entry_t  next, prev;                     \
  279                                                                 \
  280         next = (elt)->field.next;                               \
  281         prev = (elt)->field.prev;                               \
  282                                                                 \
  283         if ((head) == next)                                     \
  284                 (head)->prev = prev;                            \
  285         else                                                    \
  286                 ((type)next)->field.prev = prev;                \
  287                                                                 \
  288         if ((head) == prev)                                     \
  289                 (head)->next = next;                            \
  290         else                                                    \
  291                 ((type)prev)->field.next = next;                \
  292 }
  293 
  294 /*
  295  *      Macro:          queue_remove_first
  296  *      Function:
  297  *              Remove and return the entry at the head of
  298  *              the queue.
  299  *      Header:
  300  *              queue_remove_first(head, entry, type, field)
  301  *              entry is returned by reference
  302  */
  303 #define queue_remove_first(head, entry, type, field)            \
  304 {                                                               \
  305         register queue_entry_t  next;                           \
  306                                                                 \
  307         (entry) = (type) ((head)->next);                        \
  308         next = (entry)->field.next;                             \
  309                                                                 \
  310         if ((head) == next)                                     \
  311                 (head)->prev = (head);                          \
  312         else                                                    \
  313                 ((type)(next))->field.prev = (head);            \
  314         (head)->next = next;                                    \
  315 }
  316 
  317 /*
  318  *      Macro:          queue_remove_last
  319  *      Function:
  320  *              Remove and return the entry at the tail of
  321  *              the queue.
  322  *      Header:
  323  *              queue_remove_last(head, entry, type, field)
  324  *              entry is returned by reference
  325  */
  326 #define queue_remove_last(head, entry, type, field)             \
  327 {                                                               \
  328         register queue_entry_t  prev;                           \
  329                                                                 \
  330         (entry) = (type) ((head)->prev);                        \
  331         prev = (entry)->field.prev;                             \
  332                                                                 \
  333         if ((head) == prev)                                     \
  334                 (head)->next = (head);                          \
  335         else                                                    \
  336                 ((type)(prev))->field.next = (head);            \
  337         (head)->prev = prev;                                    \
  338 }
  339 
  340 /*
  341  *      Macro:          queue_assign
  342  */
  343 #define queue_assign(to, from, type, field)                     \
  344 {                                                               \
  345         ((type)((from)->prev))->field.next = (to);              \
  346         ((type)((from)->next))->field.prev = (to);              \
  347         *to = *from;                                            \
  348 }
  349 
  350 /*
  351  *      Macro:          queue_iterate
  352  *      Function:
  353  *              iterate over each item in the queue.
  354  *              Generates a 'for' loop, setting elt to
  355  *              each item in turn (by reference).
  356  *      Header:
  357  *              queue_iterate(q, elt, type, field)
  358  *                      queue_t q;
  359  *                      <type> elt;
  360  *                      <type> is what's in our queue
  361  *                      <field> is the chain field in (*<type>)
  362  */
  363 #define queue_iterate(head, elt, type, field)                   \
  364         for ((elt) = (type) queue_first(head);                  \
  365              !queue_end((head), (queue_entry_t)(elt));          \
  366              (elt) = (type) queue_next(&(elt)->field))
  367 
  368 
  369 
  370 /*----------------------------------------------------------------*/
  371 /*
  372  *      Define macros for queues with locks.
  373  */
  374 struct mpqueue_head {
  375         struct queue_entry      head;           /* header for queue */
  376         struct slock            lock;           /* lock for queue */
  377 };
  378 
  379 typedef struct mpqueue_head     mpqueue_head_t;
  380 
  381 #define round_mpq(size)         (size)
  382 
  383 #define mpqueue_init(q) \
  384         { \
  385                 queue_init(&(q)->head); \
  386                 simple_lock_init(&(q)->lock); \
  387         }
  388 
  389 #define mpenqueue_tail(q, elt) \
  390                 simple_lock(&(q)->lock); \
  391                 enqueue_tail(&(q)->head, elt); \
  392                 simple_unlock(&(q)->lock);
  393 
  394 #define mpdequeue_head(q, elt) \
  395                 simple_lock(&(q)->lock); \
  396                 if (queue_empty(&(q)->head)) \
  397                         *(elt) = 0; \
  398                 else \
  399                         *(elt) = dequeue_head(&(q)->head); \
  400                 simple_unlock(&(q)->lock);
  401 
  402 /*
  403  *      Old queue stuff, will go away soon.
  404  */
  405 
  406 #endif  _KERN_QUEUE_H_

Cache object: 15fb2caf0a5f1e776173973b27c6844e


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.