home *** CD-ROM | disk | FTP | other *** search
/ OpenStep 4.2J (Developer) / os42jdev.iso / NextDeveloper / Headers / kernserv / queue.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-27  |  8.3 KB  |  342 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.  
  66. #ifndef    _KERN_QUEUE_H_
  67. #define _KERN_QUEUE_H_
  68.  
  69. #import <mach/machine/vm_types.h>
  70. #import <kernserv/lock.h>
  71. #import <kernserv/macro_help.h>
  72.  
  73. /*
  74.  *    Queue of abstract objects.  Queue is maintained
  75.  *    within that object.
  76.  *
  77.  *    Supports fast removal from within the queue.
  78.  *
  79.  *    How to declare a queue of elements of type "foo_t":
  80.  *        In the "*foo_t" type, you must have a field of
  81.  *        type "queue_chain_t" to hold together this queue.
  82.  *        There may be more than one chain through a
  83.  *        "foo_t", for use by different queues.
  84.  *
  85.  *        Declare the queue as a "queue_t" type.
  86.  *
  87.  *        Elements of the queue (of type "foo_t", that is)
  88.  *        are referred to by reference, and cast to type
  89.  *        "queue_entry_t" within this module.
  90.  */
  91.  
  92. /*
  93.  *    A generic doubly-linked list (queue).
  94.  */
  95.  
  96. struct queue_entry {
  97.     struct queue_entry    *next;        /* next element */
  98.     struct queue_entry    *prev;        /* previous element */
  99. };
  100.  
  101. typedef struct queue_entry    *queue_t;
  102. typedef    struct queue_entry    queue_head_t;
  103. typedef    struct queue_entry    queue_chain_t;
  104. typedef    struct queue_entry    *queue_entry_t;
  105.  
  106. /*
  107.  *    enqueue puts "elt" on the "queue".
  108.  *    dequeue returns the first element in the "queue".
  109.  *    remqueue removes the specified "elt" from the specified "queue".
  110.  */
  111.  
  112. #define enqueue(queue,elt)    enqueue_tail(queue, elt)
  113. #define    dequeue(queue)        dequeue_head(queue)
  114.  
  115. extern void        enqueue_head();
  116. extern void        enqueue_tail();
  117. extern queue_entry_t    dequeue_head();
  118. extern queue_entry_t    dequeue_tail();
  119. extern void        remqueue();
  120.  
  121.  
  122. /*
  123.  *    Macro:        queue_init
  124.  *    Function:
  125.  *        Initialize the given queue.
  126.  *    Header:
  127.  *        void queue_init(q)
  128.  *            queue_t        q;    \* MODIFIED *\
  129.  */
  130. #define    queue_init(q)    ((q)->next = (q)->prev = q)
  131.  
  132. /*
  133.  *    Macro:        queue_first
  134.  *    Function:
  135.  *        Returns the first entry in the queue,
  136.  *    Header:
  137.  *        queue_entry_t queue_first(q)
  138.  *            queue_t    q;        \* IN *\
  139.  */
  140. #define    queue_first(q)    ((q)->next)
  141.  
  142. /*
  143.  *    Macro:        queue_next
  144.  *    Header:
  145.  *        queue_entry_t queue_next(qc)
  146.  *            queue_t qc;
  147.  */
  148. #define    queue_next(qc)    ((qc)->next)
  149.  
  150. /*
  151.  *    Macro:        queue_end
  152.  *    Header:
  153.  *        boolean_t queue_end(q, qe)
  154.  *            queue_t q;
  155.  *            queue_entry_t qe;
  156.  */
  157. #define    queue_end(q, qe)    ((q) == (qe))
  158.  
  159. #define    queue_empty(q)        queue_end((q), queue_first(q))
  160.  
  161. /*
  162.  *    Macro:        queue_enter
  163.  *    Header:
  164.  *        void queue_enter(q, elt, type, field)
  165.  *            queue_t q;
  166.  *            <type> elt;
  167.  *            <type> is what's in our queue
  168.  *            <field> is the chain field in (*<type>)
  169.  */
  170. #define queue_enter(head, elt, type, field)            \
  171. MACRO_BEGIN                            \
  172.     if (queue_empty((head))) {                \
  173.         (head)->next = (queue_entry_t) elt;        \
  174.         (head)->prev = (queue_entry_t) elt;        \
  175.         (elt)->field.next = head;            \
  176.         (elt)->field.prev = head;            \
  177.     }                            \
  178.     else {                            \
  179.         register queue_entry_t prev;            \
  180.                                 \
  181.         prev = (head)->prev;                \
  182.         (elt)->field.prev = prev;            \
  183.         (elt)->field.next = head;            \
  184.         (head)->prev = (queue_entry_t)(elt);        \
  185.         ((type)prev)->field.next = (queue_entry_t)(elt);\
  186.     }                            \
  187. MACRO_END
  188.  
  189. /*
  190.  *    Macro:        queue_field [internal use only]
  191.  *    Function:
  192.  *        Find the queue_chain_t (or queue_t) for the
  193.  *        given element (thing) in the given queue (head)
  194.  */
  195. #define    queue_field(head, thing, type, field)            \
  196.         (((head) == (thing)) ? (head) : &((type)(thing))->field)
  197.  
  198. /*
  199.  *    Macro:        queue_remove
  200.  *    Header:
  201.  *        void queue_remove(q, qe, type, field)
  202.  *            arguments as in queue_enter
  203.  */
  204. #define    queue_remove(head, elt, type, field)            \
  205. MACRO_BEGIN                            \
  206.     register queue_entry_t    next, prev;            \
  207.                                 \
  208.     next = (elt)->field.next;                \
  209.     prev = (elt)->field.prev;                \
  210.                                 \
  211.     queue_field((head), next, type, field)->prev = prev;    \
  212.     queue_field((head), prev, type, field)->next = next;    \
  213. MACRO_END
  214.  
  215. /*
  216.  *    Macro:        queue_assign
  217.  */
  218. #define    queue_assign(to, from, type, field)            \
  219. MACRO_BEGIN                            \
  220.     ((type)((from)->prev))->field.next = (to);        \
  221.     ((type)((from)->next))->field.prev = (to);        \
  222.     *to = *from;                        \
  223. MACRO_END
  224.  
  225. #define    queue_remove_first(h, e, t, f)                \
  226. MACRO_BEGIN                            \
  227.     e = (t) queue_first((h));                \
  228.     queue_remove((h), (e), t, f);                \
  229. MACRO_END
  230.  
  231. #define queue_remove_last(h, e, t, f)                \
  232. MACRO_BEGIN                            \
  233.     e = (t) queue_last((h));                \
  234.     queue_remove((h), (e), t, f);                \
  235. MACRO_END
  236.  
  237. /*
  238.  *    Macro:        queue_enter_first
  239.  *    Header:
  240.  *        void queue_enter_first(q, elt, type, field)
  241.  *            queue_t q;
  242.  *            <type> elt;
  243.  *            <type> is what's in our queue
  244.  *            <field> is the chain field in (*<type>)
  245.  */
  246. #define queue_enter_first(head, elt, type, field)        \
  247. MACRO_BEGIN                            \
  248.     if (queue_empty((head))) {                \
  249.         (head)->next = (queue_entry_t) elt;        \
  250.         (head)->prev = (queue_entry_t) elt;        \
  251.         (elt)->field.next = head;            \
  252.         (elt)->field.prev = head;            \
  253.     }                            \
  254.     else {                            \
  255.         register queue_entry_t next;            \
  256.                                 \
  257.         next = (head)->next;                \
  258.         (elt)->field.prev = head;            \
  259.         (elt)->field.next = next;            \
  260.         (head)->next = (queue_entry_t)(elt);        \
  261.         ((type)next)->field.prev = (queue_entry_t)(elt);\
  262.     }                            \
  263. MACRO_END
  264.  
  265. /*
  266.  *    Macro:        queue_last
  267.  *    Function:
  268.  *        Returns the last entry in the queue,
  269.  *    Header:
  270.  *        queue_entry_t queue_last(q)
  271.  *            queue_t    q;        \* IN *\
  272.  */
  273. #define    queue_last(q)    ((q)->prev)
  274.  
  275. /*
  276.  *    Macro:        queue_prev
  277.  *    Header:
  278.  *        queue_entry_t queue_prev(qc)
  279.  *            queue_t qc;
  280.  */
  281. #define    queue_prev(qc)    ((qc)->prev)
  282.  
  283. /*
  284.  *    Macro:        queue_iterate
  285.  *    Function:
  286.  *        iterate over each item in the queue.
  287.  *        Generates a 'for' loop, setting elt to
  288.  *        each item in turn (by reference).
  289.  *    Header:
  290.  *        queue_iterate(q, elt, type, field)
  291.  *            queue_t q;
  292.  *            <type> elt;
  293.  *            <type> is what's in our queue
  294.  *            <field> is the chain field in (*<type>)
  295.  */
  296. #define queue_iterate(head, elt, type, field)            \
  297.     for ((elt) = (type) queue_first(head);            \
  298.          !queue_end((head), (queue_entry_t)(elt));        \
  299.          (elt) = (type) queue_next(&(elt)->field))
  300.  
  301. #ifdef    KERNEL
  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 mpdequeue_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    KERNEL
  339.  
  340. #endif    _KERN_QUEUE_H_
  341.  
  342.