home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / dev / gcc / ixemulsrc.lha / ixemul / include / sys / queue.h < prev    next >
C/C++ Source or Header  |  1996-12-11  |  11KB  |  314 lines
  1. /*    $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $    */
  2.  
  3. /*
  4.  * Copyright (c) 1991, 1993
  5.  *    The Regents of the University of California.  All rights reserved.
  6.  *
  7.  * Redistribution and use in source and binary forms, with or without
  8.  * modification, are permitted provided that the following conditions
  9.  * are met:
  10.  * 1. Redistributions of source code must retain the above copyright
  11.  *    notice, this list of conditions and the following disclaimer.
  12.  * 2. Redistributions in binary form must reproduce the above copyright
  13.  *    notice, this list of conditions and the following disclaimer in the
  14.  *    documentation and/or other materials provided with the distribution.
  15.  * 3. All advertising materials mentioning features or use of this software
  16.  *    must display the following acknowledgement:
  17.  *    This product includes software developed by the University of
  18.  *    California, Berkeley and its contributors.
  19.  * 4. Neither the name of the University nor the names of its contributors
  20.  *    may be used to endorse or promote products derived from this software
  21.  *    without specific prior written permission.
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  24.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  25.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  26.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  27.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  28.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  29.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  30.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  31.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  32.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33.  * SUCH DAMAGE.
  34.  *
  35.  *    @(#)queue.h    8.5 (Berkeley) 8/20/94
  36.  */
  37.  
  38. #ifndef    _SYS_QUEUE_H_
  39. #define    _SYS_QUEUE_H_
  40.  
  41. /*
  42.  * This file defines three types of data structures: lists, tail queues,
  43.  * and circular queues.
  44.  *
  45.  * A list is headed by a single forward pointer (or an array of forward
  46.  * pointers for a hash table header). The elements are doubly linked
  47.  * so that an arbitrary element can be removed without a need to
  48.  * traverse the list. New elements can be added to the list before
  49.  * or after an existing element or at the head of the list. A list
  50.  * may only be traversed in the forward direction.
  51.  *
  52.  * A simple queue is headed by a pair of pointers, one the head of the
  53.  * list and the other to the tail of the list. The elements are singly
  54.  * linked to save space, so only elements can only be removed from the
  55.  * head of the list. New elements can be added to the list before or after
  56.  * an existing element, at the head of the list, or at the end of the
  57.  * list. A simple queue may only be traversed in the forward direection.
  58.  *
  59.  * A tail queue is headed by a pair of pointers, one to the head of the
  60.  * list and the other to the tail of the list. The elements are doubly
  61.  * linked so that an arbitrary element can be removed without a need to
  62.  * traverse the list. New elements can be added to the list before or
  63.  * after an existing element, at the head of the list, or at the end of
  64.  * the list. A tail queue may only be traversed in the forward direction.
  65.  *
  66.  * A circle queue is headed by a pair of pointers, one to the head of the
  67.  * list and the other to the tail of the list. The elements are doubly
  68.  * linked so that an arbitrary element can be removed without a need to
  69.  * traverse the list. New elements can be added to the list before or after
  70.  * an existing element, at the head of the list, or at the end of the list.
  71.  * A circle queue may be traversed in either direction, but has a more
  72.  * complex end of list detection.
  73.  *
  74.  * For details on the use of these macros, see the queue(3) manual page.
  75.  */
  76.  
  77. /*
  78.  * List definitions.
  79.  */
  80. #define LIST_HEAD(name, type)                        \
  81. struct name {                                \
  82.     struct type *lh_first;    /* first element */            \
  83. }
  84.  
  85. #define LIST_ENTRY(type)                        \
  86. struct {                                \
  87.     struct type *le_next;    /* next element */            \
  88.     struct type **le_prev;    /* address of previous next element */    \
  89. }
  90.  
  91. /*
  92.  * List functions.
  93.  */
  94. #define    LIST_INIT(head) {                        \
  95.     (head)->lh_first = NULL;                    \
  96. }
  97.  
  98. #define LIST_INSERT_AFTER(listelm, elm, field) {            \
  99.     if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)    \
  100.         (listelm)->field.le_next->field.le_prev =        \
  101.             &(elm)->field.le_next;                \
  102.     (listelm)->field.le_next = (elm);                \
  103.     (elm)->field.le_prev = &(listelm)->field.le_next;        \
  104. }
  105.  
  106. #define    LIST_INSERT_BEFORE(listelm, elm, field) {            \
  107.     (elm)->field.le_prev = (listelm)->field.le_prev;        \
  108.     (elm)->field.le_next = (listelm);                \
  109.     *(listelm)->field.le_prev = (elm);                \
  110.     (listelm)->field.le_prev = &(elm)->field.le_next;        \
  111. }
  112.  
  113. #define LIST_INSERT_HEAD(head, elm, field) {                \
  114.     if (((elm)->field.le_next = (head)->lh_first) != NULL)        \
  115.         (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
  116.     (head)->lh_first = (elm);                    \
  117.     (elm)->field.le_prev = &(head)->lh_first;            \
  118. }
  119.  
  120. #define LIST_REMOVE(elm, field) {                    \
  121.     if ((elm)->field.le_next != NULL)                \
  122.         (elm)->field.le_next->field.le_prev =             \
  123.             (elm)->field.le_prev;                \
  124.     *(elm)->field.le_prev = (elm)->field.le_next;            \
  125. }
  126.  
  127. /*
  128.  * Simple queue definitions.
  129.  */
  130. #define SIMPLEQ_HEAD(name, type)                        \
  131. struct name {                                \
  132.     struct type *sqh_first;    /* first element */            \
  133.     struct type **sqh_last;    /* addr of last next element */        \
  134. }
  135.  
  136. #define SIMPLEQ_ENTRY(type)                        \
  137. struct {                                \
  138.     struct type *sqe_next;    /* next element */            \
  139. }
  140.  
  141. /*
  142.  * Simple queue functions.
  143.  */
  144. #define    SIMPLEQ_INIT(head) {                        \
  145.     (head)->sqh_first = NULL;                    \
  146.     (head)->sqh_last = &(head)->sqh_first;                \
  147. }
  148.  
  149. #define SIMPLEQ_INSERT_HEAD(head, elm, field) {                \
  150.     if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)    \
  151.         (head)->sqh_last = &(elm)->field.sqe_next;        \
  152.     (head)->sqh_first = (elm);                    \
  153. }
  154.  
  155. #define SIMPLEQ_INSERT_TAIL(head, elm, field) {                \
  156.     (elm)->field.sqe_next = NULL;                    \
  157.     *(head)->sqh_last = (elm);                    \
  158.     (head)->sqh_last = &(elm)->field.sqe_next;            \
  159. }
  160.  
  161. #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) {        \
  162.     if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
  163.         (head)->sqh_last = &(elm)->field.sqe_next;        \
  164.     (listelm)->field.sqe_next = (elm);                \
  165. }
  166.  
  167. #define SIMPLEQ_REMOVE_HEAD(head, elm, field) {                \
  168.     if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)    \
  169.         (head)->sqh_last = &(head)->sqh_first;            \
  170. }
  171.  
  172. /*
  173.  * Tail queue definitions.
  174.  */
  175. #define TAILQ_HEAD(name, type)                        \
  176. struct name {                                \
  177.     struct type *tqh_first;    /* first element */            \
  178.     struct type **tqh_last;    /* addr of last next element */        \
  179. }
  180.  
  181. #define TAILQ_ENTRY(type)                        \
  182. struct {                                \
  183.     struct type *tqe_next;    /* next element */            \
  184.     struct type **tqe_prev;    /* address of previous next element */    \
  185. }
  186.  
  187. /*
  188.  * Tail queue functions.
  189.  */
  190. #define    TAILQ_INIT(head) {                        \
  191.     (head)->tqh_first = NULL;                    \
  192.     (head)->tqh_last = &(head)->tqh_first;                \
  193. }
  194.  
  195. #define TAILQ_INSERT_HEAD(head, elm, field) {                \
  196.     if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)    \
  197.         (head)->tqh_first->field.tqe_prev =            \
  198.             &(elm)->field.tqe_next;                \
  199.     else                                \
  200.         (head)->tqh_last = &(elm)->field.tqe_next;        \
  201.     (head)->tqh_first = (elm);                    \
  202.     (elm)->field.tqe_prev = &(head)->tqh_first;            \
  203. }
  204.  
  205. #define TAILQ_INSERT_TAIL(head, elm, field) {                \
  206.     (elm)->field.tqe_next = NULL;                    \
  207.     (elm)->field.tqe_prev = (head)->tqh_last;            \
  208.     *(head)->tqh_last = (elm);                    \
  209.     (head)->tqh_last = &(elm)->field.tqe_next;            \
  210. }
  211.  
  212. #define TAILQ_INSERT_AFTER(head, listelm, elm, field) {            \
  213.     if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
  214.         (elm)->field.tqe_next->field.tqe_prev =         \
  215.             &(elm)->field.tqe_next;                \
  216.     else                                \
  217.         (head)->tqh_last = &(elm)->field.tqe_next;        \
  218.     (listelm)->field.tqe_next = (elm);                \
  219.     (elm)->field.tqe_prev = &(listelm)->field.tqe_next;        \
  220. }
  221.  
  222. #define    TAILQ_INSERT_BEFORE(listelm, elm, field) {            \
  223.     (elm)->field.tqe_prev = (listelm)->field.tqe_prev;        \
  224.     (elm)->field.tqe_next = (listelm);                \
  225.     *(listelm)->field.tqe_prev = (elm);                \
  226.     (listelm)->field.tqe_prev = &(elm)->field.tqe_next;        \
  227. }
  228.  
  229. #define TAILQ_REMOVE(head, elm, field) {                \
  230.     if (((elm)->field.tqe_next) != NULL)                \
  231.         (elm)->field.tqe_next->field.tqe_prev =         \
  232.             (elm)->field.tqe_prev;                \
  233.     else                                \
  234.         (head)->tqh_last = (elm)->field.tqe_prev;        \
  235.     *(elm)->field.tqe_prev = (elm)->field.tqe_next;            \
  236. }
  237.  
  238. /*
  239.  * Circular queue definitions.
  240.  */
  241. #define CIRCLEQ_HEAD(name, type)                    \
  242. struct name {                                \
  243.     struct type *cqh_first;        /* first element */        \
  244.     struct type *cqh_last;        /* last element */        \
  245. }
  246.  
  247. #define CIRCLEQ_ENTRY(type)                        \
  248. struct {                                \
  249.     struct type *cqe_next;        /* next element */        \
  250.     struct type *cqe_prev;        /* previous element */        \
  251. }
  252.  
  253. /*
  254.  * Circular queue functions.
  255.  */
  256. #define    CIRCLEQ_INIT(head) {                        \
  257.     (head)->cqh_first = (void *)(head);                \
  258.     (head)->cqh_last = (void *)(head);                \
  259. }
  260.  
  261. #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) {        \
  262.     (elm)->field.cqe_next = (listelm)->field.cqe_next;        \
  263.     (elm)->field.cqe_prev = (listelm);                \
  264.     if ((listelm)->field.cqe_next == (void *)(head))        \
  265.         (head)->cqh_last = (elm);                \
  266.     else                                \
  267.         (listelm)->field.cqe_next->field.cqe_prev = (elm);    \
  268.     (listelm)->field.cqe_next = (elm);                \
  269. }
  270.  
  271. #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) {        \
  272.     (elm)->field.cqe_next = (listelm);                \
  273.     (elm)->field.cqe_prev = (listelm)->field.cqe_prev;        \
  274.     if ((listelm)->field.cqe_prev == (void *)(head))        \
  275.         (head)->cqh_first = (elm);                \
  276.     else                                \
  277.         (listelm)->field.cqe_prev->field.cqe_next = (elm);    \
  278.     (listelm)->field.cqe_prev = (elm);                \
  279. }
  280.  
  281. #define CIRCLEQ_INSERT_HEAD(head, elm, field) {                \
  282.     (elm)->field.cqe_next = (head)->cqh_first;            \
  283.     (elm)->field.cqe_prev = (void *)(head);                \
  284.     if ((head)->cqh_last == (void *)(head))                \
  285.         (head)->cqh_last = (elm);                \
  286.     else                                \
  287.         (head)->cqh_first->field.cqe_prev = (elm);        \
  288.     (head)->cqh_first = (elm);                    \
  289. }
  290.  
  291. #define CIRCLEQ_INSERT_TAIL(head, elm, field) {                \
  292.     (elm)->field.cqe_next = (void *)(head);                \
  293.     (elm)->field.cqe_prev = (head)->cqh_last;            \
  294.     if ((head)->cqh_first == (void *)(head))            \
  295.         (head)->cqh_first = (elm);                \
  296.     else                                \
  297.         (head)->cqh_last->field.cqe_next = (elm);        \
  298.     (head)->cqh_last = (elm);                    \
  299. }
  300.  
  301. #define    CIRCLEQ_REMOVE(head, elm, field) {                \
  302.     if ((elm)->field.cqe_next == (void *)(head))            \
  303.         (head)->cqh_last = (elm)->field.cqe_prev;        \
  304.     else                                \
  305.         (elm)->field.cqe_next->field.cqe_prev =            \
  306.             (elm)->field.cqe_prev;                \
  307.     if ((elm)->field.cqe_prev == (void *)(head))            \
  308.         (head)->cqh_first = (elm)->field.cqe_next;        \
  309.     else                                \
  310.         (elm)->field.cqe_prev->field.cqe_next =            \
  311.             (elm)->field.cqe_next;                \
  312. }
  313. #endif    /* !_SYS_QUEUE_H_ */
  314.