1 /* 2 3 Copyright (C) 2015-2018 Night Dive Studios, LLC. 4 5 This program is free software: you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation, either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 18 */ 19 // Llist.H Double-linked list header file 20 // Rex E. Bradford (REX) 21 /* 22 * $Header: n:/project/lib/src/dstruct/RCS/llist.h 1.5 1993/04/19 11:36:13 rex Exp $ 23 * $Log: llist.h $ 24 * Revision 1.5 1993/04/19 11:36:13 rex 25 * Arggh! More void* to make llist work! 26 * 27 * Revision 1.4 1993/04/19 09:35:40 rex 28 * Fixed llist macros again with void* so work with queues too (arrggh) 29 * 30 * Revision 1.3 1993/04/19 09:26:41 rex 31 * Fixed llist macros to do casting, so as to not get ptr warnings 32 * 33 * Revision 1.2 1993/04/16 12:02:57 rex 34 * Added llist_insert_before() and llist_insert_after(), dropped head arg 35 * from llist_remove() 36 * 37 * Revision 1.1 1993/04/16 11:04:26 rex 38 * Initial revision 39 * 40 * Revision 1.3 1993/04/15 16:25:40 rex 41 * Made basic llist, derived Llist from it. 42 * 43 * Revision 1.2 1993/01/12 17:54:37 rex 44 * Modified includes in preparation for turning into library 45 * 46 * Revision 1.1 1992/08/31 17:01:28 unknown 47 * Initial revision 48 * 49 */ 50 51 #ifndef LLIST_H 52 #define LLIST_H 53 54 #include "lg_types.h" 55 56 // -------------------------------------------------------------- 57 // LOW-LEVEL LINKED LIST 58 // -------------------------------------------------------------- 59 60 // List node (data must follow) 61 62 typedef struct _llist { 63 struct _llist *pnext; // ptr to next node or NULL if at tail 64 struct _llist *pprev; // ptr to prev node or NULL if at head 65 // real data follows, here 66 } llist; 67 68 // Queue node (sorted list, 1st item is short priority) 69 70 typedef struct _queue { 71 struct _queue *pnext; // ptr to next node or NULL if at tail 72 struct _queue *pprev; // ptr to prev node or NULL if at head 73 short priority; // higher numbers go to head of list 74 // real data follows, here 75 } queue; 76 77 // List header 78 79 typedef struct _llist_head { 80 llist head; // head list item (not really in list) 81 llist tail; // tail list item (not really in list) 82 } llist_head; 83 84 // Initialize a list header (must be done before use) 85 86 #define llist_init(plh) { \ 87 (plh)->head.pnext = llist_end(plh); \ 88 (plh)->tail.pprev = llist_beg(plh); \ 89 } 90 91 // Add a new list node to head of list 92 93 #define llist_add_head(plh,pll) { \ 94 (pll)->pnext = llist_head(plh); \ 95 (pll)->pprev = llist_beg(plh); \ 96 ((plh)->head.pnext)->pprev = (llist *) pll; \ 97 (plh)->head.pnext = (llist *) pll; \ 98 } 99 100 // Add a new list node to tail of list 101 102 #define llist_add_tail(plh,pll) { \ 103 (pll)->pnext = llist_end(plh); \ 104 (pll)->pprev = llist_tail(plh); \ 105 ((plh)->tail.pprev)->pnext = (llist *) pll; \ 106 (plh)->tail.pprev = (llist *) pll; \ 107 } 108 109 // Insert before specified node 110 111 #define llist_insert_before(pll,pnode) { \ 112 (pll)->pprev = (queue *) (pnode)->pprev; \ 113 (pll)->pnext = (queue *) pnode; \ 114 (pnode)->pprev->pnext = (queue *) pll; \ 115 (pnode)->pprev = (queue *) pll; \ 116 } 117 118 // Insert after specified node 119 120 #define llist_insert_after(pll,pnode) { \ 121 (pll)->pprev = (queue *) pnode; \ 122 (pll)->pnext = (queue *)(pnode)->pnext; \ 123 (pnode)->pnext->pprev = (queue *) pll; \ 124 (pnode)->pnext = (queue *) pll; \ 125 } 126 127 // Add in priority order 128 129 void llist_insert_queue(llist_head *plh, queue *plq); 130 131 // Move to new spot in queue (after inserting new priority) 132 133 uchar llist_move_queue(llist_head *plh, queue *plq); 134 135 // Remove node 136 137 #define llist_remove(pll) { \ 138 ((pll)->pprev)->pnext = (pll)->pnext; \ 139 ((pll)->pnext)->pprev = (pll)->pprev; \ 140 } 141 142 // Get ptr to head or tail list nodes 143 144 #define llist_head(plh) (llist*)((plh)->head.pnext) 145 #define llist_tail(plh) (llist*)((plh)->tail.pprev) 146 147 // Determine if list empty 148 149 #define llist_empty(plh) (llist_head(plh)==llist_end(plh)) 150 151 // Get # nodes in list 152 153 int llist_num_nodes(llist_head *plh); 154 155 // Get next & prev nodes from a node 156 157 #define llist_next(pll) (llist*)((pll)->pnext) // get ptr to next node 158 #define llist_prev(pll) (llist*)((pll)->pprev) // get ptr to prev node 159 160 // Get beginning and end items (used to check when traversing) 161 162 #define llist_beg(plh) (llist*)(&((plh)->head)) 163 #define llist_end(plh) (llist*)(&((plh)->tail)) 164 165 // Iterate across all items from head to tail 166 167 #define forallinlist(listtype,plh,pll) for (pll = \ 168 (listtype *) llist_head(plh); pll != llist_end(plh); pll = llist_next(pll)) 169 170 // Iterate across all items from tail to head 171 172 #define forallinlistrev(listtype,plh,pll) for (pll = \ 173 (listtype *) llist_tail(plh); pll != llist_beg(plh); pll = llist_prev(pll)) 174 175 // -------------------------------------------------------------- 176 // HIGH-LEVEL LINKED LIST OF FIXED SIZE ITEMS (MANAGES STORAGE) 177 // -------------------------------------------------------------- 178 179 // List header 180 181 typedef struct { 182 llist head; // head list item (not really in list) 183 llist tail; // tail list item (not really in list) 184 // struct _llist_head; // llist header (head, tail, numnodes) 185 llist *pfree; // ptr to next free element or NULL if no more 186 llist *pNodeStore; // ptr to first node store block, they're linked 187 // (node store is list ptrs followed by data block) 188 ushort nodeSize; // size of each node 189 short numNodesPerBlock; // # nodes in list storage (including free ones) 190 } LlistHead; 191 192 // Forgive the void pointers, C-- sucks 193 194 void LlistInit(LlistHead *plh, ushort nodeSize, short numNodesPerBlock); 195 void *LlistAddHead(LlistHead *plh); // add 1st free to head, return ptr 196 void *LlistAddTail(LlistHead *plh); // add 1st free to tail, return ptr 197 void *LlistAddQueue(LlistHead *plh, short prior); // add in priority order 198 uchar LlistMoveQueue(LlistHead *plh, void *pnode, short newprior); // move pri 199 void LlistFree(LlistHead *plh, void *pnode); // free node 200 void LlistFreeAll(LlistHead *plh); // free all nodes 201 void LlistDestroy(LlistHead *plh); // destroy list, reclaim storage 202 203 #define LlistHead(plh) (llist_head(plh)) // get ptr to head 204 #define LlistTail(plh) (llist_tail(plh)) // get ptr to tail 205 #define LlistFirstFree(plh) ((plh)->pfree) // get ptr to first free 206 207 #define LlistEmpty(plh) (llist_empty(plh)) // determine if list empty 208 #define LlistNumNodes(plh) (llist_num_nodes((llist_head *) plh)) // # active 209 210 #define LlistNext(pll) (llist_next(pll)) // get ptr to next node 211 #define LlistPrev(pll) (llist_prev(pll)) // get ptr to prev node 212 213 #define LlistBeg(plh) (llist_beg(plh)) // beginning of list 214 #define LlistEnd(plh) (llist_end(plh)) // end of list 215 216 #define FORALLINLIST(listtype,plh,pll) forallinlist(listtype,plh,pll) 217 #define FORALLINLISTREV(listtype,plh,pll) forallinlistrev(listtype,plh,pll) 218 219 #endif 220