home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / amiga / os / bsdss4.tz / bsdss4 / bsdss / server / sys / queue.h < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-22  |  6.9 KB  |  284 lines
  1. /* 
  2.  * Mach Operating System
  3.  * Copyright (c) 1992 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 
  24.  * the rights to redistribute these changes.
  25.  */
  26. /*
  27.  * HISTORY
  28.  * $Log:    queue.h,v $
  29.  * Revision 2.1  92/04/21  17:17:51  rwd
  30.  * BSDSS
  31.  * 
  32.  *
  33.  */
  34.  
  35. #ifndef    _QUEUE_
  36. #define    _QUEUE_
  37.  
  38. /*
  39.  *    Queue of abstract objects.  Queue is maintained
  40.  *    within that object.
  41.  *
  42.  *    Supports fast removal from within the queue.
  43.  *
  44.  *    How to declare a queue of elements of type "foo_t":
  45.  *        In the "*foo_t" type, you must have a field of
  46.  *        type "queue_chain_t" to hold together this queue.
  47.  *        There may be more than one chain through a
  48.  *        "foo_t", for use by different queues.
  49.  *
  50.  *        Declare the queue as a "queue_t" type.
  51.  *
  52.  *        Elements of the queue (of type "foo_t", that is)
  53.  *        are referred to by reference, and cast to type
  54.  *        "queue_entry_t" within this module.
  55.  */
  56.  
  57. /*
  58.  *    A generic doubly-linked list (queue).
  59.  */
  60.  
  61. struct queue_entry {
  62.     struct queue_entry    *next;        /* next element */
  63.     struct queue_entry    *prev;        /* previous element */
  64. };
  65.  
  66. typedef struct queue_entry    *queue_t;
  67. typedef    struct queue_entry    queue_head_t;
  68. typedef    struct queue_entry    queue_chain_t;
  69. typedef    struct queue_entry    *queue_entry_t;
  70.  
  71. /*
  72.  *    enqueue puts "elt" on the "queue".
  73.  *    dequeue returns the first element in the "queue".
  74.  *    remqueue removes the specified "elt" from the specified "queue".
  75.  */
  76.  
  77. #define enqueue(queue,elt)    enqueue_tail(queue, elt)
  78. #define    dequeue(queue)        dequeue_head(queue)
  79.  
  80. void        enqueue_head();
  81. void        enqueue_tail();
  82. queue_entry_t    dequeue_head();
  83. queue_entry_t    dequeue_tail();
  84. void        remqueue();
  85.  
  86. /*
  87.  *    Macro:        queue_init
  88.  *    Function:
  89.  *        Initialize the given queue.
  90.  *    Header:
  91.  *        void queue_init(q)
  92.  *            queue_t        q;    /* MODIFIED *\
  93.  */
  94. #define    queue_init(q)    ((q)->next = (q)->prev = q)
  95.  
  96. /*
  97.  *    Macro:        queue_first
  98.  *    Function:
  99.  *        Returns the first entry in the queue,
  100.  *    Header:
  101.  *        queue_entry_t queue_first(q)
  102.  *            queue_t    q;        /* IN *\
  103.  */
  104. #define    queue_first(q)    ((q)->next)
  105.  
  106. /*
  107.  *    Macro:        queue_next
  108.  *    Header:
  109.  *        queue_entry_t queue_next(qc)
  110.  *            queue_t qc;
  111.  */
  112. #define    queue_next(qc)    ((qc)->next)
  113.  
  114. /*
  115.  *    Macro:        queue_end
  116.  *    Header:
  117.  *        boolean_t queue_end(q, qe)
  118.  *            queue_t q;
  119.  *            queue_entry_t qe;
  120.  */
  121. #define    queue_end(q, qe)    ((q) == (qe))
  122.  
  123. #define    queue_empty(q)        queue_end((q), queue_first(q))
  124.  
  125. /*
  126.  *    Macro:        queue_enter
  127.  *    Header:
  128.  *        void queue_enter(q, elt, type, field)
  129.  *            queue_t q;
  130.  *            <type> elt;
  131.  *            <type> is what's in our queue
  132.  *            <field> is the chain field in (*<type>)
  133.  */
  134. #define queue_enter(head, elt, type, field)            \
  135. {                                 \
  136.     if (queue_empty((head))) {                \
  137.         (head)->next = (queue_entry_t) elt;        \
  138.         (head)->prev = (queue_entry_t) elt;        \
  139.         (elt)->field.next = head;            \
  140.         (elt)->field.prev = head;            \
  141.     }                            \
  142.     else {                            \
  143.         register queue_entry_t prev;            \
  144.                                 \
  145.         prev = (head)->prev;                \
  146.         (elt)->field.prev = prev;            \
  147.         (elt)->field.next = head;            \
  148.         (head)->prev = (queue_entry_t)(elt);        \
  149.         ((type)prev)->field.next = (queue_entry_t)(elt);\
  150.     }                            \
  151. }
  152.  
  153. /*
  154.  *    Macro:        queue_field [internal use only]
  155.  *    Function:
  156.  *        Find the queue_chain_t (or queue_t) for the
  157.  *        given element (thing) in the given queue (head)
  158.  */
  159. #define    queue_field(head, thing, type, field)            \
  160.         (((head) == (thing)) ? (head) : &((type)(thing))->field)
  161.  
  162. /*
  163.  *    Macro:        queue_remove
  164.  *    Header:
  165.  *        void queue_remove(q, qe, type, field)
  166.  *            arguments as in queue_enter
  167.  */
  168. #define    queue_remove(head, elt, type, field)            \
  169. {                                \
  170.     register queue_entry_t    next, prev;            \
  171.                                 \
  172.     next = (elt)->field.next;                \
  173.     prev = (elt)->field.prev;                \
  174.                                 \
  175.     queue_field((head), next, type, field)->prev = prev;    \
  176.     queue_field((head), prev, type, field)->next = next;    \
  177. }
  178.  
  179. /*
  180.  *    Macro:        queue_assign
  181.  */
  182. #define    queue_assign(to, from, type, field)            \
  183. {                                \
  184.     ((type)((from)->prev))->field.next = (to);        \
  185.     ((type)((from)->next))->field.prev = (to);        \
  186.     *to = *from;                        \
  187. }
  188.  
  189. #define    queue_remove_first(h, e, t, f)                \
  190. {                                \
  191.     e = (t) queue_first((h));                \
  192.     queue_remove((h), (e), t, f);                \
  193. }
  194.  
  195. #define    queue_remove_last(h, e, t, f)                \
  196. {                                \
  197.     e = (t) queue_last((h));                \
  198.     queue_remove((h), (e), t, f);                \
  199. }
  200.  
  201. /*
  202.  *    Macro:        queue_enter_first
  203.  *    Header:
  204.  *        void queue_enter_first(q, elt, type, field)
  205.  *            queue_t q;
  206.  *            <type> elt;
  207.  *            <type> is what's in our queue
  208.  *            <field> is the chain field in (*<type>)
  209.  */
  210. #define queue_enter_first(head, elt, type, field)            \
  211. {                                 \
  212.     if (queue_empty((head))) {                \
  213.         (head)->next = (queue_entry_t) elt;        \
  214.         (head)->prev = (queue_entry_t) elt;        \
  215.         (elt)->field.next = head;            \
  216.         (elt)->field.prev = head;            \
  217.     }                            \
  218.     else {                            \
  219.         register queue_entry_t next;            \
  220.                                 \
  221.         next = (head)->next;                \
  222.         (elt)->field.prev = head;            \
  223.         (elt)->field.next = next;            \
  224.         (head)->next = (queue_entry_t)(elt);        \
  225.         ((type)next)->field.prev = (queue_entry_t)(elt);\
  226.     }                            \
  227. }
  228.  
  229. /*
  230.  *    Macro:        queue_last
  231.  *    Function:
  232.  *        Returns the last entry in the queue,
  233.  *    Header:
  234.  *        queue_entry_t queue_last(q)
  235.  *            queue_t    q;        /* IN *\
  236.  */
  237. #define    queue_last(q)    ((q)->prev)
  238.  
  239. /*
  240.  *    Macro:        queue_prev
  241.  *    Header:
  242.  *        queue_entry_t queue_prev(qc)
  243.  *            queue_t qc;
  244.  */
  245. #define    queue_prev(qc)    ((qc)->prev)
  246.  
  247. /*
  248.  *    Old queue stuff, will go away soon.
  249.  */
  250.  
  251. /*
  252.  **********************************************************************
  253.  * HISTORY
  254.  * 21-May-85  Mike Accetta (mja) at Carnegie-Mellon University
  255.  *    Upgraded to 4.2BSD.  Changed to enQueue()/deQueue() names
  256.  *    to avoid conflicts with 4.2 dequeue().
  257.  *    [V1(1)]
  258.  *
  259.  * 06-Mar-80  Rick Rashid (rfr) at Carnegie-Mellon University
  260.  *    Created (V1.05).
  261.  *
  262.  **********************************************************************
  263.  */
  264.  
  265. /*
  266.  * General purpose structure to define circular queues.
  267.  *  Both the queue header and the queue elements have this
  268.  *  structure.
  269.  */
  270.  
  271. struct Queue
  272. {
  273.     struct Queue * F;
  274.     struct Queue * B;
  275. };
  276.  
  277. #define    initQueue(q)    (queue_init((queue_t)(q)))
  278. #define    enQueue(q,elt)    (enqueue_tail((queue_t)(q),(queue_entry_t)(elt)))
  279. #define    deQueue(q)    ((struct Queue *)dequeue_head((queue_t)(q)))
  280. #define    remQueue(q,elt)    (remqueue((queue_t)(q),(queue_entry_t)(elt)))
  281. #define    Queueempty(q)    (queue_empty((queue_t)(q)))
  282.  
  283. #endif    _QUEUE_
  284.