1 // Double linked list structure. Can be used as either a list head, or as link words.
2
3 // @struct USBH_DLIST |
4 // The USBH_DLIST structure is the link element of the double linked list. It is used as either a list head, or as link entry.
5 // @field struct tDLIST * | Flink |
6 // Pointer to the successor (forward link).
7 // @field struct tDLIST * | pPrev |
8 // Pointer to the predecessor (backward link).
9 // @comm By means of such elements any structures may be handled as a double linked list. The USBH_DLIST structure is to be inserted
10 // into the structure which is to be handled. A pointer to the original structure can be obtained by means of the macro <f STRUCT_BASE_POINTER>.
11 typedef struct USBH_DLIST USBH_DLIST;
12 struct USBH_DLIST {
13 USBH_DLIST * pNext;
14 USBH_DLIST * pPrev;
15 };
16
17 void USBH_DLIST_Append (USBH_DLIST * ListHead, USBH_DLIST * List);
18 void USBH_DLIST_InsertTail (USBH_DLIST * ListHead, USBH_DLIST * Entry);
19 void USBH_DLIST_InsertHead (USBH_DLIST * ListHead, USBH_DLIST * Entry);
20 void USBH_DLIST_InsertEntry(USBH_DLIST * Entry, USBH_DLIST * NewEntry);
21 void USBH_DLIST_RemoveTail (USBH_DLIST * ListHead, USBH_DLIST ** Entry);
22 void USBH_DLIST_RemoveHead (USBH_DLIST * ListHead, USBH_DLIST ** Entry);
23 void USBH_DLIST_RemoveEntry(USBH_DLIST * Entry);
24 USBH_DLIST * USBH_DLIST_GetPrev (USBH_DLIST * Entry);
25 USBH_DLIST * USBH_DLIST_GetNext (USBH_DLIST * Entry);
26 int USBH_DLIST_IsEmpty (USBH_DLIST * ListHead);
27 void USBH_DLIST_Init (USBH_DLIST * ListHead);
28
29
30 /*********************************************************************
31 *
32 * USBH_DLIST
33 */
34 typedef struct USBH_DLIST_ITEM {
35 struct USBH_DLIST_ITEM * pNext;
36 struct USBH_DLIST_ITEM * pPrev;
37 } USBH_DLIST_ITEM;
38
39 typedef struct {
40 struct USBH_DLIST_ITEM * pFirst;
41 int NumItems;
42 } USBH_DLIST_HEAD;
43
44 void USBH_DLIST_Remove(USBH_DLIST_HEAD * pHead, USBH_DLIST_ITEM * pItem);
45 void USBH_DLIST_Add (USBH_DLIST_HEAD * pHead, USBH_DLIST_ITEM * pNew);
1 typedef struct USBH_DLIST USBH_DLIST;
2 struct USBH_DLIST
3 {
4 USBH_DLIST * pNext;
5 USBH_DLIST * pPrev;
6 };
7
8 // USBH_DLIST_Init
9 // STR R0, [R0,#4]
10 // STR R0, [R0]
11 // BX LR
12 void USBH_DLIST_Init(USBH_DLIST * ListHead)
13 {
14 ListHead->pPrev = ListHead;
15 ListHead->pNext = ListHead;
16 }
17
18 // USBH_DLIST_Append
19 // LDR R2, [R0,#4]
20 // STR R1, [R2]
21 // LDR R3, [R1,#4]
22 // STR R0, [R3]
23 // LDR R3, [R1,#4]
24 // STR R3, [R0,#4]
25 // STR R2, [R1,#4]
26 // BX LR
27
28 // /---<<<<<<<<<<<<<<<<<<<<<<pNext---\ /---<<<<<<<<<<<<<<<<<<pNext---\
29 // ListHead <----> 0 <----> 1 <----> N List <----> 0 <----> 1 <----> N
30 // pPrev >>>>>>>>>>>>>>>>>>>>>>>>>---/ pPrev >>>>>>>>>>>>>>>>>>>>>---/
31 //
32 // /---<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<pNext---\
33 // ListHead <----> 0 <----> 1 <----> N <----> List <----> 0 <----> 1 <----> N
34 // pPrev >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>---/
35 void USBH_DLIST_Append(USBH_DLIST * ListHead, USBH_DLIST * List)
36 {
37 ListHead->pPrev->pNext = List;
38 List->pPrev->pNext = ListHead;
39 ListHead->pPrev = List->pPrev;
40 List->pPrev = ListHead->pPrev;
41 }
42
43 // USBH_DLIST_IsEmpty
44 // LDR R1, [R0]
45 // CMP R1, R0
46 // ITE EQ
47 // MOVEQ R0, #1
48 // MOVNE R0, #0
49 // BX LR
50 int USBH_DLIST_IsEmpty(USBH_DLIST * ListHead)
51 {
52 return ListHead == ListHead->pNext;
53 }
54
55 // USBH_DLIST_GetNext USBH_DLIST_GetPrev
56 // LDR R0, [R0] LDR R0, [R0,#4]
57 // BX LR BX LR
58 USBH_DLIST * USBH_DLIST_GetNext(USBH_DLIST * Entry)
59 {
60 return Entry->pNext;
61 }
62 USBH_DLIST * USBH_DLIST_GetPrev(USBH_DLIST * Entry)
63 {
64 return Entry->pPrev;
65 }
66
67 // USBH_DLIST_RemoveHead USBH_DLIST_RemoveTail
68 // LDR R0, [R0] LDR R0, [R0,#4]
69 // USBH_DLIST_RemoveEntry STR R0, [R1] STR R0, [R1]
70 //
71 // LDRD.W R1, R2, [R0] LDRD.W R1, R2, [R0] LDRD.W R1, R2, [R0]
72 // STR R1, [R2] STR R1, [R2] STR R1, [R2]
73 //
74 // LDRD.W R1, R2, [R0] LDRD.W R1, R2, [R0] LDRD.W R1, R2, [R0]
75 // STR R2, [R1,#4] STR R2, [R1,#4] STR R2, [R1,#4]
76 //
77 // STR R0, [R0,#4] STR R0, [R0,#4] STR R0, [R0,#4]
78 // STR R0, [R0] STR R0, [R0] STR R0, [R0]
79 // BX LR BX LR BX LR
80
81 // pPrev [ Entry ] pNext ---> pPrev pNext
82 void USBH_DLIST_RemoveEntry(USBH_DLIST * Entry)
83 {
84 Entry->pPrev->pNext = Entry->pNext;
85 Entry->pNext->pPrev = Entry->pPrev;
86 //USBH_DLIST_Init( Entry );
87 Entry->pPrev = Entry;
88 Entry->pNext = Entry;
89 }
90
91
92 void USBH_DLIST_RemoveHead(USBH_DLIST * ListHead, USBH_DLIST ** Entry)
93 {
94 (*Entry)->pNext = ListHead->pNext;
95 USBH_DLIST_RemoveEntry( ListHead->pNext );
96 }
97
98
99 void USBH_DLIST_RemoveTail(USBH_DLIST * ListHead, USBH_DLIST ** Entry)
100 {
101 (*Entry)->pNext = ListHead->pPrev;
102 USBH_DLIST_RemoveEntry( ListHead->pPrev );
103 }
104
105 // USBH_DLIST_InsertTail
106 // USBH_DLIST_InsertEntry USBH_DLIST_InsertHead LDR R0, [R0,#4]
107 // LDR R2, [R0] LDR R2, [R0] LDR R2, [R0]
108 // STRD.W R2, R0, [R1] STRD.W R2, R0, [R1] STRD.W R2, R0, [R1]
109 // LDR R2, [R0] LDR R2, [R0] LDR R2, [R0]
110 // STR R1, [R2,#4] STR R1, [R2,#4] STR R1, [R2,#4]
111 // STR R1, [R0] STR R1, [R0] STR R1, [R0]
112 // BX LR BX LR BX LR
113
114 void USBH_DLIST_InsertEntry(USBH_DLIST * Entry, USBH_DLIST * NewEntry)
115 {
116 NewEntry->pNext = Entry->pNext;
117 NewEntry->pPrev = Entry;
118
119 Entry->pNext->pPrev = NewEntry;
120 Entry->pNext = NewEntry;
121 }
122
123 void USBH_DLIST_InsertHead(USBH_DLIST * ListHead, USBH_DLIST * Entry)
124 {
125 USBH_DLIST_InsertEntry( ListHead, Entry );
126 }
127
128 void USBH_DLIST_InsertTail(USBH_DLIST * ListHead, USBH_DLIST * Entry)
129 {
130 USBH_DLIST_InsertEntry( ListHead->pPrev, Entry );
131 }
132
133 // -------------------------------------------------------------------------------
134 typedef struct USBH_DLIST_ITEM {
135 struct USBH_DLIST_ITEM * pNext;
136 struct USBH_DLIST_ITEM * pPrev;
137 } USBH_DLIST_ITEM;
138
139 typedef struct {
140 struct USBH_DLIST_ITEM * pFirst;
141 int NumItems;
142 } USBH_DLIST_HEAD;
143
144
145 void USBH_DLIST_InitHead(USBH_DLIST_HEAD * pHead)
146 {
147 pHead->pFirst = 0;
148 pHead->NumItems = 0;
149 }
150
151 // USBH_DLIST_Add
152 // MOVS R2, #0
153 // STR R2, [R1,#4] ; pNew->pPrev = 0;
154 //
155 // LDR R2, [R0]
156 // STR R2, [R1] ; pNew->pNext = pHead->pFirst;
157 //
158 // LDR R2, [R0]
159 // CMP R2, #0
160 // IT NE ; pHead->pFirst != 0
161 // STRNE R1, [R2,#4] ; pHead->pFirst->pPrev = pNew;
162 //
163 // STR R1, [R0] ; pHead->pFirst = pNew;
164 // BX LR
165 //
166 // pFirst --> pNew
167 // 0 <------- pNew ----> 0
168 //
169 // 0 <------- pNew ----> pOld
170 // pNew <---- pOld ----> 0
171 //
172 void USBH_DLIST_Add(USBH_DLIST_HEAD * pHead, USBH_DLIST_ITEM * pNew)
173 {
174 pNew->pPrev = 0;
175 pNew->pNext = 0;
176 if (pHead->pFirst != 0)
177 {
178 pNew->pNext = pHead->pFirst;
179 pHead->pFirst->pPrev = pNew;
180 }
181 pHead->pFirst = pNew;
182 //pHead->NumItems++;
183 }
184
185 // USBH_DLIST_Remove
186 // LDR R3, [R0]
187 // LDR R2, [R1]
188 //
189 // CMP R3, R1
190 // IT NE
191 // LDRNE R0, [R1,#4]
192 // STR R2, [R0]
193 //
194 // LDR R0, [R1]
195 // CMP R0, #0
196 // ITT NE
197 // LDRNE R1, [R1,#4]
198 // STRNE R1, [R0,#4]
199 //
200 // BX LR
201
202 //
203 void USBH_DLIST_Remove(USBH_DLIST_HEAD * pHead, USBH_DLIST_ITEM * pItem)
204 {
205 if (pHead->pFirst == pItem)
206 pHead->pFirst->pNext = pItem->pNext;
207 else
208 pItem->pPrev->pNext = pItem->pNext;
209
210 if (pItem->pNext != 0)
211 {
212 pHead->NumItems = (int)pItem->pPrev;
213 }
214 }
转载于:https://www.cnblogs.com/shangdawei/archive/2012/09/10/2678238.html
相关资源：数据结构—成绩单生成器
