1 /******************************************************************************* 2 *Copyright (c) 2014 PMC-Sierra, Inc. All rights reserved. 3 * 4 *Redistribution and use in source and binary forms, with or without modification, are permitted provided 5 *that the following conditions are met: 6 *1. Redistributions of source code must retain the above copyright notice, this list of conditions and the 7 *following disclaimer. 8 *2. Redistributions in binary form must reproduce the above copyright notice, 9 *this list of conditions and the following disclaimer in the documentation and/or other materials provided 10 *with the distribution. 11 * 12 *THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED 13 *WARRANTIES,INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 14 *FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 15 *FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 16 *NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 17 *BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 18 *LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 19 *SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE 20 * 21 * $FreeBSD$ 22 * 23 ********************************************************************************/ 24 /*******************************************************************************/ 25 /*! \file sallist.h 26 * \brief The file contains link list manipulation helper routines 27 * 28 */ 29 /*******************************************************************************/ 30 31 #ifndef __SALLIST_H__ 32 #define __SALLIST_H__ 33 34 35 /******************************************************************** 36 ********************************************************************* 37 ** DATA STRUCTURES 38 ********************************************************************/ 39 40 /** \brief Structure of Link Data 41 * 42 * link data, need to be included at the start (offset 0) 43 * of any structures that are to be stored in the link list 44 * 45 */ 46 typedef struct _SALINK 47 { 48 struct _SALINK *pNext; 49 struct _SALINK *pPrev; 50 51 /* 52 ** for assertion purpose only 53 */ 54 struct _SALINK * pHead; /* track the link list the link is a member of */ 55 56 } SALINK, * PSALINK; 57 58 /** \brief Structure of Link List 59 * 60 * link list basic pointers 61 * 62 */ 63 typedef struct _SALINK_LIST 64 { 65 PSALINK pHead; 66 bit32 Count; 67 68 SALINK Head; /* allways one link to speed up insert and delete */ 69 70 } SALINK_LIST, * PSALINK_LIST; 71 72 73 /******************************************************************** 74 ********************************************************************* 75 ** MACROS 76 ********************************************************************/ 77 78 /*! \def saLlistInitialize(pList) 79 * \brief saLlistInitialize macro 80 * 81 * use to initialize a Link List 82 */ 83 /******************************************************************************* 84 ******************************************************************************** 85 ** 86 ** MODULE NAME: saLlistInitialize 87 ** 88 ** PURPOSE: Initialize a link list. 89 ** 90 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 91 ** 92 ** SIDE EFFECTS & CAVEATS: 93 ** 94 ** ALGORITHM: 95 ** 96 ********************************************************************************/ 97 /*lint -emacro(613,saLlistInitialize) */ 98 99 #define saLlistInitialize(pList) {(pList)->pHead = &((pList)->Head); \ 100 (pList)->pHead->pNext = (pList)->pHead; \ 101 (pList)->pHead->pPrev = (pList)->pHead; \ 102 (pList)->Count = 0; \ 103 } 104 105 #define saLlistIOInitialize(pList){(pList)->pHead = &((pList)->Head); \ 106 (pList)->pHead->pNext = (pList)->pHead; \ 107 (pList)->pHead->pPrev = (pList)->pHead; \ 108 (pList)->Count = 0; \ 109 } 110 /*! \def saLlinkInitialize(pLink) 111 * \brief saLlinkInitialize macro 112 * 113 * use to initialize a Link 114 */ 115 /******************************************************************************** 116 ******************************************************************************** 117 ** 118 ** MODULE NAME: saLlinkInitialize 119 ** 120 ** PURPOSE: Initialize a link. 121 ** This function should be used to initialize a new link before it 122 ** is used in the linked list. This will initialize the link so 123 ** the assertion will work 124 ** 125 ** PARAMETERS: PSALINK IN - Link to be initialized. 126 ** 127 ** SIDE EFFECTS & CAVEATS: 128 ** 129 ** ALGORITHM: 130 ** 131 ******************************************************************************** 132 *******************************************************************************/ 133 134 /*lint -emacro(613,saLlinkInitialize) */ 135 136 #define saLlinkInitialize(pLink) { (pLink)->pHead = agNULL; \ 137 (pLink)->pNext = agNULL; \ 138 (pLink)->pPrev = agNULL; \ 139 } 140 141 #define saLlinkIOInitialize(pLink) { (pLink)->pHead = agNULL; \ 142 (pLink)->pNext = agNULL; \ 143 (pLink)->pPrev = agNULL; \ 144 } 145 /*! \def saLlistAdd(pList, pLink) 146 * \brief saLlistAdd macro 147 * 148 * use to add a link to the tail of list 149 */ 150 /******************************************************************************** 151 ******************************************************************************** 152 ** 153 ** MODULE NAME: saLlistAdd 154 ** 155 ** PURPOSE: add a link at the tail of the list 156 ** 157 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 158 ** PSALINK IN - Link to be inserted. 159 ** 160 ** SIDE EFFECTS & CAVEATS: 161 ** !!! assumes that fcllistInitialize has been called on the linklist 162 ** !!! if not, this function behavior is un-predictable 163 ** 164 ** The OS_ASSERT() is an assignment for debug code only 165 ** 166 ** ALGORITHM: 167 ** 168 ******************************************************************************** 169 *******************************************************************************/ 170 171 /*lint -emacro(506,saLlistAdd) */ 172 /*lint -emacro(613,saLlistAdd) */ 173 /*lint -emacro(666,saLlistAdd) */ 174 /*lint -emacro(720,saLlistAdd) */ 175 176 #define saLlistAdd(pList, pLink) { \ 177 (pLink)->pNext = (pList)->pHead; \ 178 (pLink)->pPrev = (pList)->pHead->pPrev; \ 179 (pLink)->pPrev->pNext = (pLink); \ 180 (pList)->pHead->pPrev = (pLink); \ 181 (pList)->Count ++; \ 182 (pLink)->pHead = (pList)->pHead; \ 183 } 184 185 #define saLlistIOAdd(pList, pLink) { \ 186 (pLink)->pNext = (pList)->pHead; \ 187 (pLink)->pPrev = (pList)->pHead->pPrev; \ 188 (pLink)->pPrev->pNext = (pLink); \ 189 (pList)->pHead->pPrev = (pLink); \ 190 (pList)->Count ++; \ 191 (pLink)->pHead = (pList)->pHead; \ 192 } 193 194 /*! \def saLlistInsert(pList, pLink, pNew) 195 * \brief saLlistInsert macro 196 * 197 * use to insert a link preceding the given one 198 */ 199 /******************************************************************************** 200 ******************************************************************************** 201 ** 202 ** MODULE NAME: saLlistInsert 203 ** 204 ** PURPOSE: insert a link preceding the given one 205 ** 206 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 207 ** PSALINK IN - Link to be inserted after. 208 ** PSALINK IN - Link to be inserted. 209 ** 210 ** SIDE EFFECTS & CAVEATS: 211 ** !!! assumes that fcllistInitialize has been called on the linklist 212 ** !!! if not, this function behavior is un-predictable 213 ** 214 ** The OS_ASSERT() is an assignment for debug code only 215 ** 216 ** ALGORITHM: 217 ** 218 ******************************************************************************** 219 *******************************************************************************/ 220 221 /*lint -emacro(506,saLlistInsert) */ 222 /*lint -emacro(613,saLlistInsert) */ 223 /*lint -emacro(666,saLlistInsert) */ 224 /*lint -emacro(720,saLlistInsert) */ 225 226 #define saLlistInsert(pList, pLink, pNew) { \ 227 (pNew)->pNext = (pLink); \ 228 (pNew)->pPrev = (pLink)->pPrev; \ 229 (pNew)->pPrev->pNext = (pNew); \ 230 (pLink)->pPrev = (pNew); \ 231 (pList)->Count ++; \ 232 (pNew)->pHead = (pList)->pHead; \ 233 } 234 235 /*! \def saLlistRemove(pList, pLink) 236 * \brief saLlistRemove macro 237 * 238 * use to remove the link from the list 239 */ 240 /******************************************************************************** 241 ******************************************************************************** 242 ** 243 ** MODULE NAME: saLlistRemove 244 ** 245 ** PURPOSE: remove the link from the list. 246 ** 247 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 248 ** PSALINK IN - Link to delet from list 249 ** 250 ** SIDE EFFECTS & CAVEATS: 251 ** !!! assumes that fcllistInitialize has been called on the linklist 252 ** !!! if not, this function behavior is un-predictable 253 ** 254 ** !!! No validation is made on the list or the validity of the link 255 ** !!! the caller must make sure that the link is in the list 256 ** 257 ** 258 ** ALGORITHM: 259 ** 260 ******************************************************************************** 261 *******************************************************************************/ 262 263 /*lint -emacro(506,saLlistRemove) */ 264 /*lint -emacro(613,saLlistRemove) */ 265 /*lint -emacro(666,saLlistRemove) */ 266 /*lint -emacro(720,saLlistRemove) */ 267 268 #define saLlistRemove(pList, pLink) { \ 269 (pLink)->pPrev->pNext = (pLink)->pNext; \ 270 (pLink)->pNext->pPrev = (pLink)->pPrev; \ 271 (pLink)->pHead = agNULL; \ 272 (pList)->Count --; \ 273 } 274 275 #define saLlistIORemove(pList, pLink) { \ 276 (pLink)->pPrev->pNext = (pLink)->pNext; \ 277 (pLink)->pNext->pPrev = (pLink)->pPrev; \ 278 (pLink)->pHead = agNULL; \ 279 (pList)->Count --; \ 280 } 281 /*! \def saLlistGetHead(pList) 282 * \brief saLlistGetHead macro 283 * 284 * use to get the link following the head link 285 */ 286 /******************************************************************************** 287 ******************************************************************************** 288 ** 289 ** MODULE NAME: saLlistGetHead 290 ** 291 ** PURPOSE: get the link following the head link. 292 ** 293 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 294 ** RETURNS - PSALINK the link following the head 295 ** agNULL if the following link is the head 296 ** 297 ** SIDE EFFECTS & CAVEATS: 298 ** !!! assumes that fcllistInitialize has been called on the linklist 299 ** !!! if not, this function behavior is un-predictable 300 ** 301 ** ALGORITHM: 302 ** 303 ******************************************************************************** 304 *******************************************************************************/ 305 #define saLlistGetHead(pList) saLlistGetNext(pList,(pList)->pHead) 306 307 #define saLlistIOGetHead(pList) saLlistGetNext(pList,(pList)->pHead) 308 309 /*! \def saLlistGetTail(pList) 310 * \brief saLlistGetTail macro 311 * 312 * use to get the link preceding the tail link 313 */ 314 /******************************************************************************** 315 ******************************************************************************** 316 ** 317 ** MODULE NAME: saLlistGetTail 318 ** 319 ** PURPOSE: get the link preceding the tail link. 320 ** 321 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 322 ** RETURNS - PSALINK the link preceding the head 323 ** agNULL if the preceding link is the head 324 ** 325 ** SIDE EFFECTS & CAVEATS: 326 ** 327 ** ALGORITHM: 328 ** 329 ******************************************************************************** 330 *******************************************************************************/ 331 #define saLlistGetTail(pList) saLlistGetPrev((pList), (pList)->pHead) 332 333 /*! \def saLlistGetCount(pList) 334 * \brief saLlistGetCount macro 335 * 336 * use to get the number of links in the list excluding head and tail 337 */ 338 /******************************************************************************** 339 ******************************************************************************** 340 ** 341 ** MODULE NAME: saLlistGetCount 342 ** 343 ** PURPOSE: get the number of links in the list excluding head and tail. 344 ** 345 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 346 ** 347 ** SIDE EFFECTS & CAVEATS: 348 ** !!! assumes that fcllistInitialize has been called on the linklist 349 ** !!! if not, this function behavior is un-predictable 350 ** 351 ** ALGORITHM: 352 ** 353 ******************************************************************************** 354 *******************************************************************************/ 355 356 /*lint -emacro(613,saLlistGetCount) */ 357 /*lint -emacro(666,saLlistGetCount) */ 358 359 #define saLlistGetCount(pList) ((pList)->Count) 360 361 #define saLlistIOGetCount(pList) ((pList)->Count) 362 363 /*! \def saLlistGetNext(pList, pLink) 364 * \brief saLlistGetNext macro 365 * 366 * use to get the next link in the list 367 */ 368 /******************************************************************************** 369 ******************************************************************************** 370 ** 371 ** MODULE NAME: saLlistGetNext 372 ** 373 ** PURPOSE: get the next link in the list. (one toward tail) 374 ** 375 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 376 ** PSALINK IN - Link to get next to 377 ** 378 ** return PLINK - points to next link 379 ** agNULL if next link is head 380 ** 381 ** SIDE EFFECTS & CAVEATS: 382 ** !!! assumes that fcllistInitialize has been called on the linklist 383 ** !!! if not, this function behavior is un-predictable 384 ** 385 ** !!! No validation is made on the list or the validity of the link 386 ** !!! the caller must make sure that the link is in the list 387 ** 388 ** ALGORITHM: 389 ** 390 ******************************************************************************** 391 *******************************************************************************/ 392 393 /*lint -emacro(613,saLlistGetNext) */ 394 395 #define saLlistGetNext(pList, pLink) (((pLink)->pNext == (pList)->pHead) ? \ 396 agNULL : (pLink)->pNext) 397 398 #define saLlistIOGetNext(pList, pLink) (((pLink)->pNext == (pList)->pHead) ? \ 399 agNULL : (pLink)->pNext) 400 401 /*! \def saLlistGetPrev(pList, pLink) 402 * \brief saLlistGetPrev macro 403 * 404 * use to get the previous link in the list 405 */ 406 /******************************************************************************** 407 ******************************************************************************** 408 ** 409 ** MODULE NAME: saLlistGetPrev 410 ** 411 ** PURPOSE: get the previous link in the list. (one toward head) 412 ** 413 ** PARAMETERS: PSALINK_LIST OUT - Link list definition. 414 ** PSALINK IN - Link to get prev to 415 ** 416 ** return PLINK - points to previous link 417 ** agNULL if previous link is head 418 ** 419 ** SIDE EFFECTS & CAVEATS: 420 ** !!! assumes that fcllistInitialize has been called on the linklist 421 ** !!! if not, this function behavior is un-predictable 422 ** 423 ** !!! No validation is made on the list or the validity of the link 424 ** !!! the caller must make sure that the link is in the list 425 ** 426 ** ALGORITHM: 427 ** 428 ******************************************************************************** 429 *******************************************************************************/ 430 431 /*lint -emacro(613,saLlistGetPrev) */ 432 433 #define saLlistGetPrev(pList, pLink) (((pLink)->pPrev == (pList)->pHead) ? \ 434 agNULL : (pLink)->pPrev) 435 436 437 438 #define agObjectBase(baseType,fieldName,fieldPtr) \ 439 (void * ) fieldPtr == (void *) 0 ? (baseType *) 0 : \ 440 ((baseType *)((bit8 *)(fieldPtr) - ((bitptr)(&(((baseType *)0)->fieldName))))) 441 442 443 #endif /* #ifndef __SALLIST_H__*/ 444