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