home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.2 (Developer) / NS_dev_3.2.iso / NextDeveloper / Headers / kernserv / queue.h < prev    next >
Text File  |  1993-10-19  |  9KB  |  345 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 bug.
  55.  *
  56.  * 12-Jun-85  Avadis Tevanian (avie) at Carnegie-Mellon University
  57.  *    Created.
  58.  */
  59. /*
  60.  *    File:    queue.h
  61.  *
  62.  *    Type definitions for generic queues.
  63.  */
  64.  
  65. #ifndef    _KERN_INTERNAL_QUEUE_H_
  66. #define _KERN_INTERNAL_QUEUE_H_
  67.  
  68. #import <mach/machine/vm_types.h>
  69. #import <kernserv/lock.h>
  70. #import <kernserv/macro_help.h>
  71.  
  72. /*
  73.  *    Queue of abstract objects.  Queue is maintained
  74.  *    within that object.
  75.  *
  76.  *    Supports fast removal from within the queue.
  77.  *
  78.  *    How to declare a queue of elements of type "foo_t":
  79.  *        In the "*foo_t" type, you must have a field of
  80.  *        type "queue_chain_t" to hold together this queue.
  81.  *        There may be more than one chain through a
  82.  *        "foo_t", for use by different queues.
  83.  *
  84.  *        Declare the queue as a "queue_t" type.
  85.  *
  86.  *        Elements of the queue (of type "foo_t", that is)
  87.  *        are referred to by reference, and cast to type
  88.  *        "queue_entry_t" within this module.
  89.  */
  90.  
  91. /*
  92.  *    A generic doubly-linked list (queue).
  93.  */
  94.  
  95. struct queue_entry {
  96.     struct queue_entry    *next;        /* next element */
  97.     struct queue_entry    *prev;        /* previous element */
  98. };
  99.  
  100. typedef struct queue_entry    *queue_t;
  101. typedef    struct queue_entry    queue_head_t;
  102. typedef    struct queue_entry    queue_chain_t;
  103. typedef    struct queue_entry    *queue_entry_t;
  104.  
  105. /*
  106.  *    enqueue puts "elt" on the "queue".
  107.  *    dequeue returns the first element in the "queue".
  108.  *    remqueue removes the specified "elt" from the specified "queue".
  109.  */
  110.  
  111. #define enqueue(queue,elt)    enqueue_tail(queue, elt)
  112. #define    dequeue(queue)        dequeue_head(queue)
  113.  
  114. #if    defined(__GNU__) && defined(KERNEL_BUILD)
  115. #define    COMPILE_QUEUE        /* flag that queue.c should compile now */
  116. #import <kern/queue.c>
  117. #else    defined(__GNU__) && defined(KERNEL_BUILD)
  118. extern void        enqueue_head();
  119. extern void        enqueue_tail();
  120. extern queue_entry_t    dequeue_head();
  121. extern queue_entry_t    dequeue_tail();
  122. extern void        remqueue();
  123. #endif    defined(__GNU__) && defined(KERNEL_BUILD)
  124.  
  125.  
  126. /*
  127.  *    Macro:        queue_init
  128.  *    Function:
  129.  *        Initialize the given queue.
  130.  *    Header:
  131.  *        void queue_init(q)
  132.  *            queue_t        q;    \* MODIFIED *\
  133.  */
  134. #define    queue_init(q)    ((q)->next = (q)->prev = q)
  135.  
  136. /*
  137.  *    Macro:        queue_first
  138.  *    Function:
  139.  *        Returns the first entry in the queue,
  140.  *    Header:
  141.  *        queue_entry_t queue_first(q)
  142.  *            queue_t    q;        \* IN *\
  143.  */
  144. #define    queue_first(q)    ((q)->next)
  145.  
  146. /*
  147.  *    Macro:        queue_next
  148.  *    Header:
  149.  *        queue_entry_t queue_next(qc)
  150.  *            queue_t qc;
  151.  */
  152. #define    queue_next(qc)    ((qc)->next)
  153.  
  154. /*
  155.  *    Macro:        queue_end
  156.  *    Header:
  157.  *        boolean_t queue_end(q, qe)
  158.  *            queue_t q;
  159.  *            queue_entry_t qe;
  160.  */
  161. #define    queue_end(q, qe)    ((q) == (qe))
  162.  
  163. #define    queue_empty(q)        queue_end((q), queue_first(q))
  164.  
  165. /*
  166.  *    Macro:        queue_enter
  167.  *    Header:
  168.  *        void queue_enter(q, elt, type, field)
  169.  *            queue_t q;
  170.  *            <type> elt;
  171.  *            <type> is what's in our queue
  172.  *            <field> is the chain field in (*<type>)
  173.  */
  174. #define queue_enter(head, elt, type, field)            \
  175. MACRO_BEGIN                            \
  176.     if (queue_empty((head))) {                \
  177.         (head)->next = (queue_entry_t) elt;        \
  178.         (head)->prev = (queue_entry_t) elt;        \
  179.         (elt)->field.next = head;            \
  180.         (elt)->field.prev = head;            \
  181.     }                            \
  182.     else {                            \
  183.         register queue_entry_t prev;            \
  184.                                 \
  185.         prev = (head)->prev;                \
  186.         (elt)->field.prev = prev;            \
  187.         (elt)->field.next = head;            \
  188.         (head)->prev = (queue_entry_t)(elt);        \
  189.         ((type)prev)->field.next = (queue_entry_t)(elt);\
  190.     }                            \
  191. MACRO_END
  192.  
  193. /*
  194.  *    Macro:        queue_field [internal use only]
  195.  *    Function:
  196.  *        Find the queue_chain_t (or queue_t) for the
  197.  *        given element (thing) in the given queue (head)
  198.  */
  199. #define    queue_field(head, thing, type, field)            \
  200.         (((head) == (thing)) ? (head) : &((type)(thing))->field)
  201.  
  202. /*
  203.  *    Macro:        queue_remove
  204.  *    Header:
  205.  *        void queue_remove(q, qe, type, field)
  206.  *            arguments as in queue_enter
  207.  */
  208. #define    queue_remove(head, elt, type, field)            \
  209. MACRO_BEGIN                            \
  210.     register queue_entry_t    next, prev;            \
  211.                                 \
  212.     next = (elt)->field.next;                \
  213.     prev = (elt)->field.prev;                \
  214.                                 \
  215.     queue_field((head), next, type, field)->prev = prev;    \
  216.     queue_field((head), prev, type, field)->next = next;    \
  217. MACRO_END
  218.  
  219. /*
  220.  *    Macro:        queue_assign
  221.  */
  222. #define    queue_assign(to, from, type, field)            \
  223. MACRO_BEGIN                            \
  224.     ((type)((from)->prev))->field.next = (to);        \
  225.     ((type)((from)->next))->field.prev = (to);        \
  226.     *to = *from;                        \
  227. MACRO_END
  228.  
  229. #define    queue_remove_first(h, e, t, f)                \
  230. MACRO_BEGIN                            \
  231.     e = (t) queue_first((h));                \
  232.     queue_remove((h), (e), t, f);                \
  233. MACRO_END
  234.  
  235. #define queue_remove_last(h, e, t, f)                \
  236. MACRO_BEGIN                            \
  237.     e = (t) queue_last((h));                \
  238.     queue_remove((h), (e), t, f);                \
  239. MACRO_END
  240.  
  241. /*
  242.  *    Macro:        queue_enter_first
  243.  *    Header:
  244.  *        void queue_enter_first(q, elt, type, field)
  245.  *            queue_t q;
  246.  *            <type> elt;
  247.  *            <type> is what's in our queue
  248.  *            <field> is the chain field in (*<type>)
  249.  */
  250. #define queue_enter_first(head, elt, type, field)        \
  251. MACRO_BEGIN                            \
  252.     if (queue_empty((head))) {                \
  253.         (head)->next = (queue_entry_t) elt;        \
  254.         (head)->prev = (queue_entry_t) elt;        \
  255.         (elt)->field.next = head;            \
  256.         (elt)->field.prev = head;            \
  257.     }                            \
  258.     else {                            \
  259.         register queue_entry_t next;            \
  260.                                 \
  261.         next = (head)->next;                \
  262.         (elt)->field.prev = head;            \
  263.         (elt)->field.next = next;            \
  264.         (head)->next = (queue_entry_t)(elt);        \
  265.         ((type)next)->field.prev = (queue_entry_t)(elt);\
  266.     }                            \
  267. MACRO_END
  268.  
  269. /*
  270.  *    Macro:        queue_last
  271.  *    Function:
  272.  *        Returns the last entry in the queue,
  273.  *    Header:
  274.  *        queue_entry_t queue_last(q)
  275.  *            queue_t    q;        \* IN *\
  276.  */
  277. #define    queue_last(q)    ((q)->prev)
  278.  
  279. /*
  280.  *    Macro:        queue_prev
  281.  *    Header:
  282.  *        queue_entry_t queue_prev(qc)
  283.  *            queue_t qc;
  284.  */
  285. #define    queue_prev(qc)    ((qc)->prev)
  286.  
  287. /*
  288.  *    Macro:        queue_iterate
  289.  *    Function:
  290.  *        iterate over each item in the queue.
  291.  *        Generates a 'for' loop, setting elt to
  292.  *        each item in turn (by reference).
  293.  *    Header:
  294.  *        queue_iterate(q, elt, type, field)
  295.  *            queue_t q;
  296.  *            <type> elt;
  297.  *            <type> is what's in our queue
  298.  *            <field> is the chain field in (*<type>)
  299.  */
  300. #define queue_iterate(head, elt, type, field)            \
  301.     for ((elt) = (type) queue_first(head);            \
  302.          !queue_end((head), (queue_entry_t)(elt));        \
  303.          (elt) = (type) queue_next(&(elt)->field))
  304.  
  305. #ifdef    KERNEL
  306.  
  307. /*
  308.  *    Define macros for queues with locks.
  309.  */
  310. struct mpqueue_head {
  311.     struct queue_entry    head;        /* header for queue */
  312.     simple_lock_data_t    lock;        /* lock for queue */
  313. };
  314.  
  315. typedef struct mpqueue_head    mpqueue_head_t;
  316.  
  317. #define round_mpq(size)        (size)
  318.  
  319. #define mpqueue_init(q)                        \
  320. MACRO_BEGIN                            \
  321.     queue_init(&(q)->head);                    \
  322.     simple_lock_init(&(q)->lock);                \
  323. MACRO_END
  324.  
  325. #define mpenqueue_tail(q, elt)                    \
  326. MACRO_BEGIN                            \
  327.     simple_lock(&(q)->lock);                \
  328.     enqueue_tail(&(q)->head, elt);                \
  329.     simple_unlock(&(q)->lock);                \
  330. MACRO_END
  331.  
  332. #define mpdequeue_head(q, elt)                    \
  333. MACRO_BEGIN                            \
  334.     simple_lock(&(q)->lock);                \
  335.     if (queue_empty(&(q)->head))                \
  336.         *(elt) = 0;                    \
  337.     else                            \
  338.         *(elt) = dequeue_head(&(q)->head);        \
  339.     simple_unlock(&(q)->lock);                \
  340. MACRO_END
  341.  
  342. #endif    KERNEL
  343.  
  344. #endif    _KERN_INTERNAL_QUEUE_H_
  345.