workbench/network/stacks/AROSTCP/bsdsocket/sys/queue2.h

   1 /*
   2  * Copyright (C) 1993 AmiTCP/IP Group, <amitcp-group@hut.fi>
   3  *                    Helsinki University of Technology, Finland.
   4  *                    All rights reserved.
   5  * Copyright (C) 2005 Neil Cafferkey
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License version 2 as
   9  * published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  19  * MA 02111-1307, USA.
  20  *
  21  */
  22
  23 /*
  24  * Mach Operating System
  25  * Copyright (c) 1992 Carnegie Mellon University
  26  * All Rights Reserved.
  27  *
  28  * Permission to use, copy, modify and distribute this software and its
  29  * documentation is hereby granted, provided that both the copyright
  30  * notice and this permission notice appear in all copies of the
  31  * software, derivative works or modified versions, and any portions
  32  * thereof, and that both notices appear in supporting documentation.
  33  *
  34  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  35  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  36  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  37  *
  38  * Carnegie Mellon requests users of this software to return to
  39  *
  40  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  41  *  School of Computer Science
  42  *  Carnegie Mellon University
  43  *  Pittsburgh PA 15213-3890
  44  *
  45  * any improvements or extensions that they make and grant Carnegie Mellon
  46  * the rights to redistribute these changes.
  47  */
  48
  49 #ifndef SYS_QUEUE_H
  50 #define SYS_QUEUE_H
  51
  52 /*
  53  *      Queue of abstract objects.  Queue is maintained
  54  *      within that object.
  55  *
  56  *      Supports fast removal from within the queue.
  57  *
  58  *      How to declare a queue of elements of type "foo_t":
  59  *              In the "*foo_t" type, you must have a field of
  60  *              type "queue_chain_t" to hold together this queue.
  61  *              There may be more than one chain through a
  62  *              "foo_t", for use by different queues.
  63  *
  64  *              Declare the queue as a "queue_t" type.
  65  *
  66  *              Elements of the queue (of type "foo_t", that is)
  67  *              are referred to by reference, and cast to type
  68  *              "queue_entry_t" within this module.
  69  */
  70
  71 /*
  72  *      A generic doubly-linked list (queue).
  73  */
  74
  75 struct queue_entry {
  76         struct queue_entry      *next;          /* next element */
  77         struct queue_entry      *prev;          /* previous element */
  78 };
  79
  80 typedef struct queue_entry      *queue_t;
  81 typedef struct queue_entry      queue_head_t;
  82 typedef struct queue_entry      queue_chain_t;
  83 typedef struct queue_entry      *queue_entry_t;
  84
  85 /*
  86  *      enqueue puts "elt" on the "queue".
  87  *      dequeue returns the first element in the "queue".
  88  *      remqueue removes the specified "elt" from the specified "queue".
  89  */
  90
  91 #define enqueue(queue,elt)      enqueue_tail(queue, elt)
  92 #define dequeue(queue)          dequeue_head(queue)
  93
  94 void            enqueue_head();
  95 void            enqueue_tail();
  96 queue_entry_t   dequeue_head();
  97 queue_entry_t   dequeue_tail();
  98 void            remqueue();
  99
 100 /*
 101  *      Macro:          queue_init
 102  *      Function:
 103  *              Initialize the given queue.
 104  *      Header:
 105  *              void queue_init(q)
 106  *                      queue_t         q;      \* MODIFIED *\
 107  */
 108 #define queue_init(q)   ((q)->next = (q)->prev = q)
 109
 110 /*
 111  *      Macro:          queue_first
 112  *      Function:
 113  *              Returns the first entry in the queue,
 114  *      Header:
 115  *              queue_entry_t queue_first(q)
 116  *                      queue_t q;              \* IN *\
 117  */
 118 #define queue_first(q)  ((q)->next)
 119
 120 /*
 121  *      Macro:          queue_next
 122  *      Header:
 123  *              queue_entry_t queue_next(qc)
 124  *                      queue_t qc;
 125  */
 126 #define queue_next(qc)  ((qc)->next)
 127
 128 /*
 129  *      Macro:          queue_end
 130  *      Header:
 131  *              boolean_t queue_end(q, qe)
 132  *                      queue_t q;
 133  *                      queue_entry_t qe;
 134  */
 135 #define queue_end(q, qe)        ((q) == (qe))
 136
 137 #define queue_empty(q)          queue_end((q), queue_first(q))
 138
 139 /*
 140  *      Macro:          queue_enter
 141  *      Header:
 142  *              void queue_enter(q, elt, type, field)
 143  *                      queue_t q;
 144  *                      <type> elt;
 145  *                      <type> is what's in our queue
 146  *                      <field> is the chain field in (*<type>)
 147  */
 148 #define queue_enter(head, elt, type, field)                     \
 149 {                                                               \
 150         if (queue_empty((head))) {                              \
 151                 (head)->next = (queue_entry_t) elt;             \
 152                 (head)->prev = (queue_entry_t) elt;             \
 153                 (elt)->field.next = head;                       \
 154                 (elt)->field.prev = head;                       \
 155         }                                                       \
 156         else {                                                  \
 157                 register queue_entry_t prev;                    \
 158                                                                 \
 159                 prev = (head)->prev;                            \
 160                 (elt)->field.prev = prev;                       \
 161                 (elt)->field.next = head;                       \
 162                 (head)->prev = (queue_entry_t)(elt);            \
 163                 ((type)prev)->field.next = (queue_entry_t)(elt);\
 164         }                                                       \
 165 }
 166
 167 /*
 168  *      Macro:          queue_field [internal use only]
 169  *      Function:
 170  *              Find the queue_chain_t (or queue_t) for the
 171  *              given element (thing) in the given queue (head)
 172  */
 173 #define queue_field(head, thing, type, field)                   \
 174                 (((head) == (thing)) ? (head) : &((type)(thing))->field)
 175
 176 /*
 177  *      Macro:          queue_remove
 178  *      Header:
 179  *              void queue_remove(q, qe, type, field)
 180  *                      arguments as in queue_enter
 181  */
 182 #define queue_remove(head, elt, type, field)                    \
 183 {                                                               \
 184         register queue_entry_t  next, prev;                     \
 185                                                                 \
 186         next = (elt)->field.next;                               \
 187         prev = (elt)->field.prev;                               \
 188                                                                 \
 189         queue_field((head), next, type, field)->prev = prev;    \
 190         queue_field((head), prev, type, field)->next = next;    \
 191 }
 192
 193 /*
 194  *      Macro:          queue_assign
 195  */
 196 #define queue_assign(to, from, type, field)                     \
 197 {                                                               \
 198         ((type)((from)->prev))->field.next = (to);              \
 199         ((type)((from)->next))->field.prev = (to);              \
 200         *to = *from;                                            \
 201 }
 202
 203 #define queue_remove_first(h, e, t, f)                          \
 204 {                                                               \
 205         e = (t) queue_first((h));                               \
 206         queue_remove((h), (e), t, f);                           \
 207 }
 208
 209 #define queue_remove_last(h, e, t, f)                           \
 210 {                                                               \
 211         e = (t) queue_last((h));                                \
 212         queue_remove((h), (e), t, f);                           \
 213 }
 214
 215 /*
 216  *      Macro:          queue_enter_first
 217  *      Header:
 218  *              void queue_enter_first(q, elt, type, field)
 219  *                      queue_t q;
 220  *                      <type> elt;
 221  *                      <type> is what's in our queue
 222  *                      <field> is the chain field in (*<type>)
 223  */
 224 #define queue_enter_first(head, elt, type, field)                       \
 225 {                                                               \
 226         if (queue_empty((head))) {                              \
 227                 (head)->next = (queue_entry_t) elt;             \
 228                 (head)->prev = (queue_entry_t) elt;             \
 229                 (elt)->field.next = head;                       \
 230                 (elt)->field.prev = head;                       \
 231         }                                                       \
 232         else {                                                  \
 233                 register queue_entry_t next;                    \
 234                                                                 \
 235                 next = (head)->next;                            \
 236                 (elt)->field.prev = head;                       \
 237                 (elt)->field.next = next;                       \
 238                 (head)->next = (queue_entry_t)(elt);            \
 239                 ((type)next)->field.prev = (queue_entry_t)(elt);\
 240         }                                                       \
 241 }
 242
 243 /*
 244  *      Macro:          queue_last
 245  *      Function:
 246  *              Returns the last entry in the queue,
 247  *      Header:
 248  *              queue_entry_t queue_last(q)
 249  *                      queue_t q;              \* IN *\
 250  */
 251 #define queue_last(q)   ((q)->prev)
 252
 253 /*
 254  *      Macro:          queue_prev
 255  *      Header:
 256  *              queue_entry_t queue_prev(qc)
 257  *                      queue_t qc;
 258  */
 259 #define queue_prev(qc)  ((qc)->prev)
 260
 261 #endif /* SYS_QUEUE_H */