1 /* 2 ** OSSP al -- Assembly Line 3 ** Copyright (c) 2002-2005 The OSSP Project <http://www.ossp.org/> 4 ** Copyright (c) 2002-2005 Cable & Wireless <http://www.cw.com/> 5 ** Copyright (c) 2002-2005 Ralf S. Engelschall <rse@engelschall.com> 6 ** Copyright (c) 2002-2005 Michael van Elst <mlelstv@serpens.de> 7 ** 8 ** This file is part of OSSP al, an abstract datatype of a data buffer 9 ** that can assemble, move and truncate data but avoids actual copying. 10 ** 11 ** Permission to use, copy, modify, and distribute this software for 12 ** any purpose with or without fee is hereby granted, provided that 13 ** the above copyright notice and this permission notice appear in all 14 ** copies. 15 ** 16 ** THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 17 ** WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 18 ** MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19 ** IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR 20 ** CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 ** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 ** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 23 ** USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 24 ** ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 25 ** OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 26 ** OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 ** SUCH DAMAGE. 28 ** 29 ** list.h: generic double-linked list macros 30 */ 31 32 #ifndef __LIST_H__ 33 #define __LIST_H__ 34 35 #define LIST(elem) \ 36 struct { elem *head, *tail; } 37 #define NODE(elem) \ 38 struct { elem *next, *prev; } 39 40 #define HEAD(q,l) ((q)->l.head) 41 #define TAIL(q,l) ((q)->l.tail) 42 #define NEXT(n,l) ((n)->l.next) 43 #define PREV(n,l) ((n)->l.prev) 44 45 #define ISEMPTY(q,l) (HEAD(q,l) == NULL) 46 47 #define LISTINIT(q,l) \ 48 do { \ 49 HEAD(q,l) = NULL; \ 50 TAIL(q,l) = NULL; \ 51 } while(0) 52 53 #define NODEINIT(n,l) \ 54 do { \ 55 NEXT(n,l) = NULL; \ 56 PREV(n,l) = NULL; \ 57 } while(0) 58 59 #define ADDTAIL2(q,l,n1,n2) \ 60 do { \ 61 if (TAIL(q,l)) { \ 62 NEXT(TAIL(q,l),l) = (n1); \ 63 PREV(n1,l) = TAIL(q,l); \ 64 } else { \ 65 HEAD(q,l) = (n1); \ 66 PREV(n1,l) = NULL; \ 67 } \ 68 TAIL(q,l) = (n2); \ 69 NEXT(n2,l) = NULL; \ 70 } while (0) 71 #define ADDTAIL(q,l,n) ADDTAIL2(q,l,n,n) 72 73 #define ADDHEAD2(q,l,n1,n2) \ 74 do { \ 75 if (HEAD(q,l)) { \ 76 PREV(HEAD(q,l),l) = (n2); \ 77 NEXT(n2,l) = HEAD(q,l); \ 78 } else { \ 79 TAIL(q,l) = (n2); \ 80 NEXT(n2,l) = NULL; \ 81 } \ 82 HEAD(q,l) = (n1); \ 83 PREV(n1,l) = NULL; \ 84 } while (0) 85 #define ADDHEAD(q,l,n) ADDHEAD2(q,l,n,n) 86 87 #define REMHEAD(q,l,n) \ 88 do { \ 89 (n) = HEAD(q,l); \ 90 if (n) { \ 91 HEAD(q,l) = NEXT(n,l); \ 92 if (HEAD(q,l)) \ 93 PREV(HEAD(q,l),l) = NULL; \ 94 else \ 95 TAIL(q,l) = NULL; \ 96 } \ 97 } while(0) 98 99 #define REMTAIL(q,l,n) \ 100 do { \ 101 (n) = TAIL(q,l); \ 102 if (n) { \ 103 TAIL(q,l) = PREV(n,l); \ 104 if (TAIL(q,l)) \ 105 NEXT(TAIL(q,l),l) = NULL; \ 106 else \ 107 HEAD(q,l) = NULL; \ 108 } \ 109 } while(0) 110 111 #define REMOVE2(q,l,n1,n2) \ 112 do { \ 113 if (PREV(n1,l)) \ 114 NEXT(PREV(n1,l),l) = NEXT(n2,l); \ 115 else \ 116 HEAD(q,l) = NEXT(n2,l); \ 117 if (NEXT(n2,l)) \ 118 PREV(NEXT(n2,l),l) = PREV(n1,l); \ 119 else \ 120 TAIL(q,l) = PREV(n1,l); \ 121 NEXT(n2,l) = NULL; \ 122 PREV(n1,l) = NULL; \ 123 } while (0) 124 #define REMOVE(q,l,n) REMOVE2(q,l,n,n) 125 126 #define INSERT2(q,l,i,n1,n2) \ 127 do { \ 128 if (PREV(i,l)) { \ 129 NEXT(PREV(i,l),l) = (n1); \ 130 } else { \ 131 HEAD(q,l) = (n1); \ 132 } \ 133 PREV(n1,l) = PREV(i,l); \ 134 PREV(i,l) = (n2); \ 135 NEXT(n2,l) = (i); \ 136 } while (0) 137 #define INSERT(q,l,i,n) INSERT2(q,l,i,n,n) 138 139 #define APPENDLIST(q1,l,q2) \ 140 do { \ 141 if (TAIL(q1,l)) { \ 142 NEXT(TAIL(q1,l),l) = HEAD(q2,l); \ 143 PREV(HEAD(q2,l),l) = TAIL(q1,l); \ 144 } else { \ 145 HEAD(q1,l) = HEAD(q2,l); \ 146 } \ 147 TAIL(q1,l) = TAIL(q2,l); \ 148 LISTINIT(q2,l); \ 149 } while(0) 150 151 #define INSERTLIST(q1,l,i,q2) \ 152 do { \ 153 if (PREV(i,l)) { \ 154 NEXT(PREV(i,l),l) = HEAD(q2,l); \ 155 } else { \ 156 HEAD(q1,l) = HEAD(q2,l); \ 157 } \ 158 PREV(HEAD(q2,l),l) = PREV(i,l); \ 159 NEXT(TAIL(q2,l),l) = (i); \ 160 PREV(i,l) = TAIL(q2,l); \ 161 LISTINIT(q2,l); \ 162 } while(0) 163 164 #define FOREACH(q,l,n) for (n = HEAD(q,l); n; n = NEXT(n,l)) 165 #define FOREACHR(q,l,n) for (n = TAIL(q,l); n; n = PREV(n,l)) 166 #define FOREACHD(q,l,n,r) for (n = TAIL(q,l); n && (r = PREV(n,l), 1); n = r) 167 168 #endif /* __LIST_H__ */ 169 170