sbDq.h (10084B)
1 #ifndef _SB__DQ_H_ 2 #define _SB__DQ_H_ 3 /* -------------------------------------------------------------------------- 4 ** 5 ** 6 ** 7 ** This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 8 ** 9 ** Copyright 2007-2019 Broadcom Inc. All rights reserved. 10 ** 11 ** sbDq.h: doubly linked lists 12 ** 13 ** --------------------------------------------------------------------------*/ 14 15 /* 16 * Singly linked list (stack) structure 17 */ 18 #define SL_INIT(l) do { (l) = NULL; } while (0) 19 #define SL_EMPTY(l) (!(l)) 20 21 #define SL_INSERT_HEAD(l, e) \ 22 do \ 23 { \ 24 *((void **) (e)) = (void *) (l); \ 25 ((void *) (l)) = (void *) (e); \ 26 } while (0) 27 28 #define SL_REMOVE_HEAD(l, e) \ 29 do \ 30 { \ 31 ((void *) e) = (void *) (l); \ 32 ((void *) (l)) = *((void **) (e)); \ 33 } while (0) 34 35 36 37 /* 38 * Doubly linked queue structure 39 */ 40 41 typedef struct dq_s *dq_p_t; 42 typedef struct dq_s 43 { 44 volatile dq_p_t flink; /* Forward link */ 45 volatile dq_p_t blink; /* Backward link */ 46 } 47 dq_t; 48 49 50 #define DQ_INIT(q) \ 51 do \ 52 { \ 53 (q)->flink = (q); \ 54 (q)->blink = (q); \ 55 } while (0) 56 57 /* true if element (e) is not in a list */ 58 #define DQ_NULL(e) (((e)->flink == (e)) && ((e)->blink == (e))) 59 60 /* true if queue (q) is empty */ 61 #define DQ_EMPTY(q) ((q)->flink == (q)) 62 63 #define DQ_HEAD(q, t) ((t) (q)->flink) 64 #define DQ_TAIL(q, t) ((t) (q)->blink) 65 #define DQ_NEXT(q, t) ((t) (q)->flink) 66 #define DQ_PREV(q, t) ((t) (q)->blink) 67 68 /* 69 * Arguments are: 70 * q: pointer to queue block 71 * e: pointer to element (DQ) to insert 72 */ 73 #define DQ_INSERT_HEAD(q, e) \ 74 do \ 75 { \ 76 dq_p_t pElement; \ 77 pElement = (dq_p_t) (e); \ 78 pElement->flink = (q)->flink; \ 79 pElement->blink = (q); \ 80 (q)->flink->blink = pElement; \ 81 (q)->flink = pElement; \ 82 } while (0) 83 84 85 /* 86 * Arguments are: 87 * q: pointer to queue block 88 * e: pointer to element (DQ) to insert 89 */ 90 #define DQ_INSERT_TAIL(q, e) \ 91 do \ 92 { \ 93 dq_p_t pElement; \ 94 pElement = (dq_p_t) (e); \ 95 pElement->flink = (q); \ 96 pElement->blink = (q)->blink; \ 97 (q)->blink->flink = pElement; \ 98 (q)->blink = pElement; \ 99 } while (0) 100 101 102 /* 103 * Arguments are: 104 * e: pointer to previous element 105 * n: pointer to new element to insert 106 * CHECK If pNew is head before using 107 */ 108 #define DQ_INSERT_PREV(e, n) \ 109 do \ 110 { \ 111 dq_p_t pElement; \ 112 dq_p_t _pNew; \ 113 dq_p_t pPrev; \ 114 pElement = (dq_p_t) (e); \ 115 _pNew = (dq_p_t) (n); \ 116 pPrev = pElement->blink; \ 117 pPrev->flink = _pNew; \ 118 _pNew->blink = pPrev; \ 119 _pNew->flink = pElement; \ 120 pElement->blink = _pNew; \ 121 } while (0) 122 123 /* 124 * Arguments are: 125 * e: pointer to next element 126 * n: pointer to new element to insert 127 * CHECK If pNew is tail before using 128 */ 129 #define DQ_INSERT_NEXT(e, n) \ 130 do \ 131 { \ 132 dq_p_t pElement; \ 133 dq_p_t _pNew; \ 134 dq_p_t pNext; \ 135 pElement = (dq_p_t) (e); \ 136 _pNew = (dq_p_t) (n); \ 137 pNext = pElement->flink; \ 138 pNext->blink = _pNew; \ 139 _pNew->flink = pNext; \ 140 pElement->flink = _pNew; \ 141 _pNew->blink = pElement; \ 142 } while (0) 143 144 /* 145 * Argument is: 146 * e: pointer to element (DQ) to remove 147 */ 148 #define DQ_REMOVE(e) \ 149 do \ 150 { \ 151 dq_p_t pElement; \ 152 pElement = (dq_p_t) (e); \ 153 pElement->blink->flink = pElement->flink; \ 154 pElement->flink->blink = pElement->blink; \ 155 } while (0) 156 157 158 /* 159 * Arguments are: 160 * q: pointer to queue block 161 * e: pointer to element (DQ) removed from the head of q 162 */ 163 #define DQ_REMOVE_HEAD(q, e) \ 164 do \ 165 { \ 166 dq_p_t pElement; \ 167 pElement = (dq_p_t) (e); \ 168 pElement = (q)->flink; \ 169 e = (void *)pElement; \ 170 pElement->blink->flink = pElement->flink; \ 171 pElement->flink->blink = pElement->blink; \ 172 } while (0) 173 174 /* 175 * Arguments are: 176 * q: pointer to queue block 177 * e: pointer to element (DQ) removed from the head of q 178 */ 179 #define DQ_REMOVE_TAIL(q, e) \ 180 do \ 181 { \ 182 dq_p_t pElement; \ 183 pElement = (dq_p_t) (e); \ 184 pElement = (q)->blink; \ 185 e = (void *)pElement; \ 186 pElement->blink->flink = pElement->flink; \ 187 pElement->flink->blink = pElement->blink; \ 188 } while (0) 189 190 /* 191 * Arguments new list head, old list head 192 * Used to copy list head from one memory area 193 * to a different memory area without affecting 194 * contents of list 195 */ 196 #define DQ_SWAP_HEAD(n, o) \ 197 do \ 198 { \ 199 (n)->flink = (o)->flink; \ 200 (n)->blink = (o)->blink; \ 201 (o)->flink->blink = (n); \ 202 (o)->blink->flink = (n); \ 203 } while (0) 204 205 /* 206 * This macro is a tidy way of performing subtraction to move from a 207 * pointer within an object to a pointer to the object. 208 * 209 * Arguments are: 210 * type of object to recover (e.g. dq_p_t) 211 * pointer to object from which to recover element pointer 212 * pointer to an object of type t 213 * name of the DQ field in t through which the queue is linked 214 * Returns: 215 * a pointer to the object, of type t 216 */ 217 #define DQ_ELEMENT(t, p, ep, f) \ 218 ((t) (((char *) (p)) - (((char *) &((ep)->f)) - ((char *) (ep))))) 219 220 /* 221 * DQ_ELEMENT_GET performs the same function as DQ_ELEMENT, but does not 222 * require a pointer of type (t). This form is preferred as DQ_ELEMENT 223 * typically generate Coverity errors, and the (ep) argument is unnecessary. 224 * 225 * Arguments are: 226 * type of object to recover (e.g. dq_p_t) 227 * pointer to object from which to recover element pointer 228 * name of the DQ field in t through which the queue is linked (t->dq_t) 229 * Returns: 230 * a pointer to the object, of type t 231 */ 232 #define DQ_ELEMENT_GET(t, p, f) \ 233 ((t) (((char *) (p)) - (((char *) &(((t)(0))->f))))) 234 235 /* 236 * Arguments: 237 * q: head of queue on which to map f 238 * f: function to apply to each element of q 239 */ 240 #define DQ_MAP(q, f, a) \ 241 do \ 242 { \ 243 dq_p_t e, e0, q0; \ 244 q0 = (q); \ 245 for (e=q0->flink; e != q0; e = e0) { \ 246 e0 = e->flink; \ 247 (void) (f)(e, a); \ 248 } \ 249 } while (0) 250 251 /* 252 * Arguments: 253 * q: head of queue on which to map f 254 * f: function to apply to each element of q; should return 1 when 255 * desired queue element has been found. 256 */ 257 #define DQ_FIND(q, f, a) \ 258 do \ 259 { \ 260 dq_p_t e, e0, q0; \ 261 q0 = (q); \ 262 for (e=q0->flink; e != q0; e = e0) { \ 263 e0 = e->flink; \ 264 if ((f)(e, a)) break; \ 265 } \ 266 } while (0) 267 268 /* 269 * Arguments: 270 * q: head of queue to determine length 271 */ 272 #define DQ_LENGTH(q, cnt) \ 273 do \ 274 { \ 275 dq_p_t e, q0; \ 276 (cnt) = 0; \ 277 q0 = (q); \ 278 for (e = q0->flink; e != q0; e = e->flink) { \ 279 (cnt)++; \ 280 } \ 281 } while (0) \ 282 283 /* 284 * Arguments: 285 * q: head of queue 286 * e: each elem during traverse 287 */ 288 #define DQ_TRAVERSE(q, e) \ 289 do \ 290 { \ 291 dq_p_t e0, q0; \ 292 q0 = (q); \ 293 for (e=q0->flink; e != q0; e = e0) { \ 294 e0 = e->flink; \ 295 296 /* 297 * Arguments: 298 * q: head of queue 299 * e: each elem during traverse 300 */ 301 #define DQ_BACK_TRAVERSE(q, e) \ 302 do \ 303 { \ 304 dq_p_t e0, q0; \ 305 q0 = (q); \ 306 for (e=q0->blink; e != q0; e = e0) { \ 307 e0 = e->blink; \ 308 309 #define DQ_TRAVERSE_END(q, e) \ 310 } \ 311 } while (0) 312 313 #endif /* _SB__DQ_H_ */