1 //------------------------------------------------------------------------------
2 // <copyright file="dl_list.h" company="Atheros">
3 // Copyright (c) 2004-2010 Atheros Corporation. All rights reserved.
4 //
5 //
6 // Permission to use, copy, modify, and/or distribute this software for any
7 // purpose with or without fee is hereby granted, provided that the above
8 // copyright notice and this permission notice appear in all copies.
9 //
10 // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 // ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 // ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 // OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 //
18 //
19 //------------------------------------------------------------------------------
20 //==============================================================================
21 // Double-link list definitions (adapted from Atheros SDIO stack)
22 //
23 // Author(s): ="Atheros"
24 //==============================================================================
25 #ifndef __DL_LIST_H___
26 #define __DL_LIST_H___
27
28 #include "a_osapi.h"
29
30 #define A_CONTAINING_STRUCT(address, struct_type, field_name)\
31 ((struct_type *)((unsigned long)(address) - (unsigned long)(&((struct_type *)0)->field_name)))
32
33 /* list functions */
34 /* pointers for the list */
35 struct dl_list {
36 struct dl_list *pPrev;
37 struct dl_list *pNext;
38 };
39 /*
40 * DL_LIST_INIT , initialize doubly linked list
41 */
42 #define DL_LIST_INIT(pList)\
43 {(pList)->pPrev = pList; (pList)->pNext = pList;}
44
45 /* faster macro to init list and add a single item */
46 #define DL_LIST_INIT_AND_ADD(pList,pItem) \
47 { (pList)->pPrev = (pItem); \
48 (pList)->pNext = (pItem); \
49 (pItem)->pNext = (pList); \
50 (pItem)->pPrev = (pList); \
51 }
52
53 #define DL_LIST_IS_EMPTY(pList) (((pList)->pPrev == (pList)) && ((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); (pTemp) = (pTemp)->pNext)
63
64
65 /* safe iterate macro that allows the item to be removed from the list
66 * the iteration continues to the next item in the list
67 */
68 #define ITERATE_OVER_LIST_ALLOW_REMOVE(pStart,pItem,st,offset) \
69 { \
70 struct dl_list * pTemp; \
71 pTemp = (pStart)->pNext; \
72 while (pTemp != (pStart)) { \
73 (pItem) = A_CONTAINING_STRUCT(pTemp,st,offset); \
74 pTemp = pTemp->pNext; \
75
76 #define ITERATE_END }}
77
78 /*
79 * DL_ListInsertTail - insert pAdd to the end of the list
80 */
DL_ListInsertTail(struct dl_list * pList,struct dl_list * pAdd)81 static INLINE struct dl_list *DL_ListInsertTail(struct dl_list *pList, struct dl_list *pAdd) {
82 /* insert at tail */
83 pAdd->pPrev = pList->pPrev;
84 pAdd->pNext = pList;
85 pList->pPrev->pNext = pAdd;
86 pList->pPrev = pAdd;
87 return pAdd;
88 }
89
90 /*
91 * DL_ListInsertHead - insert pAdd into the head of the list
92 */
DL_ListInsertHead(struct dl_list * pList,struct dl_list * pAdd)93 static INLINE struct dl_list * DL_ListInsertHead(struct dl_list * pList, struct dl_list * pAdd) {
94 /* insert at head */
95 pAdd->pPrev = pList;
96 pAdd->pNext = pList->pNext;
97 pList->pNext->pPrev = pAdd;
98 pList->pNext = pAdd;
99 return pAdd;
100 }
101
102 #define DL_ListAdd(pList,pItem) DL_ListInsertHead((pList),(pItem))
103 /*
104 * DL_ListRemove - remove pDel from list
105 */
DL_ListRemove(struct dl_list * pDel)106 static INLINE struct dl_list * DL_ListRemove(struct dl_list * pDel) {
107 pDel->pNext->pPrev = pDel->pPrev;
108 pDel->pPrev->pNext = pDel->pNext;
109 /* point back to itself just to be safe, incase remove is called again */
110 pDel->pNext = pDel;
111 pDel->pPrev = pDel;
112 return pDel;
113 }
114
115 /*
116 * DL_ListRemoveItemFromHead - get a list item from the head
117 */
DL_ListRemoveItemFromHead(struct dl_list * pList)118 static INLINE struct dl_list * DL_ListRemoveItemFromHead(struct dl_list * pList) {
119 struct dl_list * pItem = NULL;
120 if (pList->pNext != pList) {
121 pItem = pList->pNext;
122 /* remove the first item from head */
123 DL_ListRemove(pItem);
124 }
125 return pItem;
126 }
127
DL_ListRemoveItemFromTail(struct dl_list * pList)128 static INLINE struct dl_list * DL_ListRemoveItemFromTail(struct dl_list * pList) {
129 struct dl_list * pItem = NULL;
130 if (pList->pPrev != pList) {
131 pItem = pList->pPrev;
132 /* remove the item from tail */
133 DL_ListRemove(pItem);
134 }
135 return pItem;
136 }
137
138 /* transfer src list items to the tail of the destination list */
DL_ListTransferItemsToTail(struct dl_list * pDest,struct dl_list * pSrc)139 static INLINE void DL_ListTransferItemsToTail(struct dl_list * pDest, struct dl_list * pSrc) {
140 /* only concatenate if src is not empty */
141 if (!DL_LIST_IS_EMPTY(pSrc)) {
142 /* cut out circular list in src and re-attach to end of dest */
143 pSrc->pPrev->pNext = pDest;
144 pSrc->pNext->pPrev = pDest->pPrev;
145 pDest->pPrev->pNext = pSrc->pNext;
146 pDest->pPrev = pSrc->pPrev;
147 /* terminate src list, it is now empty */
148 pSrc->pPrev = pSrc;
149 pSrc->pNext = pSrc;
150 }
151 }
152
153 #endif /* __DL_LIST_H___ */
154