home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.0 / NeXTSTEP3.0.iso / NextDeveloper / Headers / kernserv / queue.h < prev    next >
Text File  |  1992-07-29  |  9KB  |  339 lines
  1. /* 
  2.  * Mach Operating System
  3.  * Copyright (c) 1989 Carnegie-Mellon University
  4.  * Copyright (c) 1988 Carnegie-Mellon University
  5.  * Copyright (c) 1987 Carnegie-Mellon University
  6.  * All rights reserved.  The CMU software License Agreement specifies
  7.  * the terms and conditions for use and redistribution.
  8.  */
  9. /*
  10.  * HISTORY
  11.  * $Log:    queue.h,v $
  12.  * 21-May-89  Avadis Tevanian, Jr. (avie) at NeXT, Inc.
  13.  *    Use inline expansion if compiling with the GNU compiler.
  14.  *
  15.  * Revision 2.7  89/03/09  20:15:03  rpd
  16.  *     More cleanup.
  17.  * 
  18.  * Revision 2.6  89/02/25  18:07:48  gm0w
  19.  *     Kernel code cleanup.    
  20.  *     Put all the macros under #ifdef KERNEL
  21.  *     [89/02/15            mrt]
  22.  * 
  23.  * Revision 2.5  89/02/07  01:03:50  mwyoung
  24.  * Relocated from sys/queue.h
  25.  * 
  26.  * Revision 2.4  88/12/19  02:51:30  mwyoung
  27.  *     Eliminate round_queue.
  28.  *     [88/11/22  01:22:22  mwyoung]
  29.  *     
  30.  *     Add queue_remove_last.
  31.  *     [88/11/18            mwyoung]
  32.  * 
  33.  * Revision 2.3  88/08/24  02:40:43  mwyoung
  34.  *     Adjusted include file references.
  35.  *     [88/08/17  02:20:58  mwyoung]
  36.  * 
  37.  *
  38.  * 17-Jan-88  Daniel Julin (dpj) at Carnegie-Mellon University
  39.  *    Added queue_enter_first, queue_last and queue_prev for use by
  40.  *    the TCP netport code.
  41.  *
  42.  * 17-Mar-87  David Golub (dbg) at Carnegie-Mellon University
  43.  *    Made queue package return queue_entry_t instead of vm_offset_t.
  44.  *
  45.  * 27-Feb-87  David Golub (dbg) at Carnegie-Mellon University
  46.  *    Made remqueue a real routine on all machines.  Defined old
  47.  *    Queue routines as macros that invoke new queue routines.
  48.  *
  49.  * 25-Feb-87  Avadis Tevanian (avie) at Carnegie-Mellon University
  50.  *    Fixed non-KERNEL compilation.
  51.  *
  52.  * 24-Feb-87  David L. Black (dlb) at Carnegie-Mellon University
  53.  *    MULTIMAX: remqueue is now a real routine, removed define.
  54.  *    This is done to mask a compiler buT*
  55.  * 12-Jun-85  Avadis Tevanian (avie) at Carnegie-Mellon University
  56.  *    Created.
  57.  */
  58. /*
  59.  *    File:    queue.h
  60.  *
  61.  *    Type definitions for generic queues.
  62.  */
  63.  
  64. #ifndef    _KERN_INTERNAL_QUEUE_H_
  65. #define _KERN_INTERNAL_QUEUE_H_
  66.  
  67. #import <mach/machine/vm_types.h>
  68. #import <kernserv/lock.h>
  69. #import <kernserv/macro_help.h>
  70.  
  71. /*
  72.  *    Queue of abstract objects.  Queue is maintained
  73.  *    within that object.
  74.  *
  75.  *    Supports fast removal from within the queue.
  76.  *
  77.  *    How to declare a queue of elements of type "foo_t":
  78.  *        In the "*foo_t" type, you must have a field of
  79.  *        type "queue_chain_t" to hold together this queue.
  80.  *        There may be more than one chain through a
  81.  *        "foo_t", for use by different queues.
  82.  *
  83.  *        Declare the queue as a "queue_t" type.
  84.  *
  85.  *        Elements of the queue (of type "foo_t", that is)
  86.  *        are referred to by reference, and cast to type
  87.  *        "queue_entry_t" within this module.
  88.  */
  89.  
  90. /*
  91.  *    A generic doubly-linked list (queue).
  92.  */
  93.  
  94. struct queue_entry {
  95.     struct queue_entry    *next;        /* next element */
  96.     struct queue_entry    *prev;        /* previous element */
  97. };
  98.  
  99. typedef struct queue_entry    *queue_t;
  100. typedef    struct queue_entry    queue_head_t;
  101. typedef    struct queue_entry    queue_chain_t;
  102. typedef    struct queue_entry    *queue_entry_t;
  103.  
  104. /*
  105.  *    enqueue puts "elt" on the "queue".
  106.  *    dequeue returns the first element in the "queue".
  107.  *    remqueue removes the specified "elt" from the specified "queue".
  108.  */
  109.  
  110. #define enqueue(queue,elt)    enqueue_tail(queue, elt)
  111. #define    dequeue(queue)        dequeue_head(queue)
  112.  
  113. #if    defined(__GNU__) && defined(KERNEL_BUILD)
  114. #define    COMPILE_QUEUE        /* flag that queue.c should compile now */
  115. #import <kern/queue.c>
  116. #else    defined(__GNU__) && defined(KERNEL_BUILD)
  117. extern void        enqueue_head();
  118. extern void        enqueue_tail();
  119. extern queue_entry_t    dequeue_head();
  120. extern queue_entry_t    dequeue_tail();
  121. extern void        remqueue();
  122. #endif    defined(__GNU__) && defined(KERNEL_BUILD)
  123.  
  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.  *    Header:
  148.  *        queue_entry_t queue_next(qc)
  149.  *            queue_t qc;
  150. U#define    queue_next(qc)    ((qc)->next)
  151.  
  152. /*
  153.  *    Macro:        queue_end
  154.  *    Header:
  155.  *        boolean_t queue_end(q, qe)
  156.  *            queue_t q;
  157.  *            queue_entry_t qe;
  158.  */
  159. #define    queue_end(q, qe)    ((q) == (qe))
  160.  
  161. #define    queue_empty(q)        queue_end((q), queue_first(q))
  162.  
  163. /*
  164.  *    Macro:        queue_enter
  165.  *    Header:
  166.  *        void queue_enter(q, elt, type, field)
  167.  *            queue_t q;
  168.  *            <type> elt;
  169.  *            <type> is what's in our queue
  170.  *            <field> is the chain field in (*<type>)
  171.  */
  172. #define queue_enter(head, elt, type, field)            \
  173. MACRO_BEGIN                            \
  174.     if (queue_empty((head))) {                \
  175.         (head)->next = (queue_entry_t) elt;        \
  176.         (head)->prev = (queue_entry_t) elt;        \
  177.         (elt)->field.next = head;            \
  178.         (elt)->field.prev = head;            \
  179.     }                            \
  180.     else {                            \
  181.         register queue_entry_t prev;            \
  182.                                 \
  183.         prev = (head)->prev;                \
  184.         (elt)->field.prev = prev;            \
  185.         (elt)->field.next = head;            \
  186.         (head)->prev = (queue_entry_t)(elt);        \
  187.         ((type)prev)->field.next = (queue_entry_t)(elt);\
  188.     }                            \
  189. MACRO_END
  190.  
  191. /*
  192.  *    Macro:        queue_field [internal use only]
  193.  *    Function:
  194.  *        Find the queue_chain_t (or queue_t) for the
  195.  *        given element (thing) in the given queue (head)
  196.  */
  197. #define    queue_field(head, thing, type, field)            \
  198.         (((head) == (thing)) ? (head) : &((type)(thing))->field)
  199.  
  200. /*
  201.  *    Macro:        queue_remove
  202.  *    Header:
  203.  *        void queue_remove(q, qe, type, field)
  204.  *            arguments as in queue_enter
  205.  */
  206. #define    queue_remove(head, elt, type, field)            \
  207. MACRO_BEGIN                            \
  208.     register queue_entry_t    next, prev;            \
  209.                                 \
  210.     next = (elt)->field.next;                \
  211.     prev = (elt)->field.prev;                \
  212.                                 \
  213.     queue_field((head), next, type, field)->prev = prev;    \
  214.     queue_field((head), prev, type, field)->next = next;    \
  215. MACRO_END
  216.  
  217. /*
  218.  *    Macro:        queue_assign
  219.  */
  220. #define    queue_assign(to, from, type, field)            \
  221. MACRO_BEGIN                            \
  222.     ((type)((from)->prev))->field.next = (to);        \
  223.     ((type)((from)->next))->field.prev = (to);        \
  224.     *to = *from;                        \
  225. MACRO_END
  226.  
  227. #define    queue_remove_first(h, e, t, f)                \
  228. MACRO_BEGIN                            \
  229.     e = (t) queue_first((h));                \
  230.     queue_remove((h), (e), t, f);                \
  231. MACRO_END
  232.  
  233. #define queue_remove_last(h, e, t, f)                \
  234. MACRO_BEGIN                            \
  235.     e = (t) queue_last((h));                \
  236.     queue_remove((h), (e), t, f);                \
  237. MACRO_END
  238.  
  239. /*
  240.  *    Macro:        queue_enter_first
  241.  *    Header:
  242.  *        void queue_enter_first(q, elt, type, field)
  243.  *            queue_t q;
  244.  *            <type> elt;
  245.  *            <type> is what's in our queue
  246.  *            <fieVis the chain field in (*<type>)
  247.  */
  248. #define queue_enter_first(head, elt, type, field)        \
  249. MACRO_BEGIN                            \
  250.     if (queue_empty((head))) {                \
  251.         (head)->next = (queue_entry_t) elt;        \
  252.         (head)->prev = (queue_entry_t) elt;        \
  253.         (elt)->field.next = head;            \
  254.         (elt)->field.prev = head;            \
  255.     }                            \
  256.     else {                            \
  257.         register queue_entry_t next;            \
  258.                                 \
  259.         next = (head)->next;                \
  260.         (elt)->field.prev = head;            \
  261.         (elt)->field.next = next;            \
  262.         (head)->next = (queue_entry_t)(elt);        \
  263.         ((type)next)->field.prev = (queue_entry_t)(elt);\
  264.     }                            \
  265. MACRO_END
  266.  
  267. /*
  268.  *    Macro:        queue_last
  269.  *    Function:
  270.  *        Returns the last entry in the queue,
  271.  *    Header:
  272.  *        queue_entry_t queue_last(q)
  273.  *            queue_t    q;        \* IN *\
  274.  */
  275. #define    queue_last(q)    ((q)->prev)
  276.  
  277. /*
  278.  *    Macro:        queue_prev
  279.  *    Header:
  280.  *        queue_entry_t queue_prev(qc)
  281.  *            queue_t qc;
  282.  */
  283. #define    queue_prev(qc)    ((qc)->prev)
  284.  
  285. /*
  286.  *    Macro:        queue_iterate
  287.  *    Function:
  288.  *        iterate over each item in the queue.
  289.  *        Generates a 'for' loop, setting elt to
  290.  *        each item in turn (by reference).
  291.  *    Header:
  292.  *        queue_iterate(q, elt, type, field)
  293.  *            queue_t q;
  294.  *            <type> elt;
  295.  *            <type> is what's in our queue
  296.  *            <field> is the chain field in (*<type>)
  297.  */
  298. #define queue_iterate(head, elt, type, field)            \
  299.     for ((elt) = (type) queue_first(head);            \
  300.          !queue_end((head), (queue_entry_t)(elt));        \
  301.          (elt) = (type) queue_next(&(elt)->field))
  302.  
  303. /*
  304.  *    Define macros for queues with locks.
  305.  */
  306. struct mpqueue_head {
  307.     struct queue_entry    head;        /* header for queue */
  308.     simple_lock_data_t    lock;        /* lock for queue */
  309. };
  310.  
  311. typedef struct mpqueue_head    mpqueue_head_t;
  312.  
  313. #define round_mpq(size)        (size)
  314.  
  315. #define mpqueue_init(q)                        \
  316. MACRO_BEGIN                            \
  317.     queue_init(&(q)->head);                    \
  318.     simple_lock_init(&(q)->lock);                \
  319. MACRO_END
  320.  
  321. #define mpenqueue_tail(q, elt)                    \
  322. MACRO_BEGIN                            \
  323.     simple_lock(&(q)->lock);                \
  324.     enqueue_tail(&(q)->head, elt);                \
  325.     simple_unlock(&(q)->lock);                \
  326. MACRO_END
  327.  
  328. #define mpdIue_head(q, elt)                    \
  329. MACRO_BEGIN                            \
  330.     simple_lock(&(q)->lock);                \
  331.     if (queue_empty(&(q)->head))                \
  332.         *(elt) = 0;                    \
  333.     else                            \
  334.         *(elt) = dequeue_head(&(q)->head);        \
  335.     simple_unlock(&(q)->lock);                \
  336. MACRO_END
  337.  
  338. #endif    _KERN_INTERNAL_QUEUE_H_
  339.