1 /* 2 * Copyright (c) 2013-2014, 2017, 2019 The Linux Foundation. All rights reserved. 3 * 4 * Permission to use, copy, modify, and/or distribute this software for 5 * any purpose with or without fee is hereby granted, provided that the 6 * above copyright notice and this permission notice appear in all 7 * copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL 10 * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED 11 * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE 12 * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL 13 * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR 14 * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER 15 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 16 * PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 /*=========================================================================== */ 20 /* Double-link list definitions (adapted from Atheros SDIO stack) */ 21 /* */ 22 /* Author(s): ="Atheros" */ 23 /*=========================================================================== */ 24 25 #ifndef __DL_LIST_H___ 26 #define __DL_LIST_H___ 27 28 #define A_CONTAINING_STRUCT(address, struct_type, field_name) \ 29 ((struct_type *)((char *)(address) - \ 30 (char *)(&((struct_type *)0)->field_name))) 31 32 /* list functions */ 33 /* pointers for the list */ 34 typedef struct _DL_LIST { 35 struct _DL_LIST *pPrev; 36 struct _DL_LIST *pNext; 37 } DL_LIST, *PDL_LIST; 38 /* 39 * DL_LIST_INIT , initialize doubly linked list 40 */ 41 #define DL_LIST_INIT(pList) \ 42 {(pList)->pPrev = pList; (pList)->pNext = pList; } 43 44 /* faster macro to init list and add a single item */ 45 #define DL_LIST_INIT_AND_ADD(pList, pItem) \ 46 { (pList)->pPrev = (pItem); \ 47 (pList)->pNext = (pItem); \ 48 (pItem)->pNext = (pList); \ 49 (pItem)->pPrev = (pList); \ 50 } 51 52 #define DL_LIST_IS_EMPTY(pList) (((pList)->pPrev == (pList)) && \ 53 ((pList)->pNext == (pList))) 54 #define DL_LIST_GET_ITEM_AT_HEAD(pList) (pList)->pNext 55 #define DL_LIST_GET_ITEM_AT_TAIL(pList) (pList)->pPrev 56 /* 57 * ITERATE_OVER_LIST pStart is the list, pTemp is a temp list member 58 * NOT: do not use this function if the items in the list are deleted inside the 59 * iteration loop 60 */ 61 #define ITERATE_OVER_LIST(pStart, pTemp) \ 62 for ((pTemp) = (pStart)->pNext; pTemp != (pStart); \ 63 (pTemp) = (pTemp)->pNext) 64 65 static inline bool dl_list_is_entry_in_list(const DL_LIST *pList, 66 const DL_LIST *pEntry) 67 { 68 const DL_LIST *pTmp; 69 70 if (pList == pEntry) 71 return true; 72 73 ITERATE_OVER_LIST(pList, pTmp) { 74 if (pTmp == pEntry) 75 return true; 76 } 77 78 return false; 79 } 80 81 /* safe iterate macro that allows the item to be removed from the list 82 * the iteration continues to the next item in the list 83 */ 84 #define ITERATE_OVER_LIST_ALLOW_REMOVE(pStart, pItem, st, offset) \ 85 { \ 86 PDL_LIST pTemp; \ 87 { pTemp = (pStart)->pNext; } \ 88 while (pTemp != (pStart)) { \ 89 { (pItem) = A_CONTAINING_STRUCT(pTemp, st, offset); } \ 90 { pTemp = pTemp->pNext; } \ 91 92 #define ITERATE_IS_VALID(pStart) dl_list_is_entry_in_list(pStart, pTemp) 93 #define ITERATE_RESET(pStart) { pTemp = (pStart)->pNext; } 94 95 #define ITERATE_END }} 96 97 /* 98 * dl_list_insert_tail - insert pAdd to the end of the list 99 */ 100 static inline PDL_LIST dl_list_insert_tail(PDL_LIST pList, PDL_LIST pAdd) 101 { 102 /* insert at tail */ 103 pAdd->pPrev = pList->pPrev; 104 pAdd->pNext = pList; 105 if (pList->pPrev) 106 pList->pPrev->pNext = pAdd; 107 pList->pPrev = pAdd; 108 return pAdd; 109 } 110 111 /* 112 * dl_list_insert_head - insert pAdd into the head of the list 113 */ 114 static inline PDL_LIST dl_list_insert_head(PDL_LIST pList, PDL_LIST pAdd) 115 { 116 /* insert at head */ 117 pAdd->pPrev = pList; 118 pAdd->pNext = pList->pNext; 119 pList->pNext->pPrev = pAdd; 120 pList->pNext = pAdd; 121 return pAdd; 122 } 123 124 #define DL_ListAdd(pList, pItem) dl_list_insert_head((pList), (pItem)) 125 /* 126 * dl_list_remove - remove pDel from list 127 */ 128 static inline PDL_LIST dl_list_remove(PDL_LIST pDel) 129 { 130 if (pDel->pNext) 131 pDel->pNext->pPrev = pDel->pPrev; 132 if (pDel->pPrev) 133 pDel->pPrev->pNext = pDel->pNext; 134 /* point back to itself just to be safe, if remove is called again */ 135 pDel->pNext = pDel; 136 pDel->pPrev = pDel; 137 return pDel; 138 } 139 140 /* 141 * dl_list_remove_item_from_head - get a list item from the head 142 */ 143 static inline PDL_LIST dl_list_remove_item_from_head(PDL_LIST pList) 144 { 145 PDL_LIST pItem = NULL; 146 147 if (pList->pNext != pList) { 148 pItem = pList->pNext; 149 /* remove the first item from head */ 150 dl_list_remove(pItem); 151 } 152 return pItem; 153 } 154 155 static inline PDL_LIST dl_list_remove_item_from_tail(PDL_LIST pList) 156 { 157 PDL_LIST pItem = NULL; 158 159 if (pList->pPrev != pList) { 160 pItem = pList->pPrev; 161 /* remove the item from tail */ 162 dl_list_remove(pItem); 163 } 164 return pItem; 165 } 166 167 /* transfer src list items to the tail of the destination list */ 168 static inline void dl_list_transfer_items_to_tail(PDL_LIST pDest, PDL_LIST pSrc) 169 { 170 /* only concatenate if src is not empty */ 171 if (!DL_LIST_IS_EMPTY(pSrc)) { 172 /* cut out circular list in src and re-attach to end of dest */ 173 pSrc->pPrev->pNext = pDest; 174 pSrc->pNext->pPrev = pDest->pPrev; 175 pDest->pPrev->pNext = pSrc->pNext; 176 pDest->pPrev = pSrc->pPrev; 177 /* terminate src list, it is now empty */ 178 pSrc->pPrev = pSrc; 179 pSrc->pNext = pSrc; 180 } 181 } 182 183 /* transfer src list items to the head of the destination list */ 184 static inline void dl_list_transfer_items_to_head(PDL_LIST pDest, PDL_LIST pSrc) 185 { 186 /* only concatenate if src is not empty */ 187 if (!DL_LIST_IS_EMPTY(pSrc)) { 188 /* cut out circular list in src and reattach to start of dest */ 189 pSrc->pNext->pPrev = pDest; 190 pDest->pNext->pPrev = pSrc->pPrev; 191 pSrc->pPrev->pNext = pDest->pNext; 192 pDest->pNext = pSrc->pNext; 193 /* terminate src list, it is now empty */ 194 pSrc->pPrev = pSrc; 195 pSrc->pNext = pSrc; 196 } 197 } 198 199 #endif /* __DL_LIST_H___ */ 200