1 | /** @file wlan_mac_dl_list.c |
---|
2 | * @brief Doubly-linked List Framework |
---|
3 | * |
---|
4 | * This contains the code for managing doubly-linked (DL) lists. |
---|
5 | * |
---|
6 | * @copyright Copyright 2014-2019, Mango Communications. All rights reserved. |
---|
7 | * Distributed under the Mango Communications Reference Design License |
---|
8 | * See LICENSE.txt included in the design archive or |
---|
9 | * at http://mangocomm.com/802.11/license |
---|
10 | * |
---|
11 | * This file is part of the Mango 802.11 Reference Design (https://mangocomm.com/802.11) |
---|
12 | */ |
---|
13 | |
---|
14 | |
---|
15 | /***************************** Include Files *********************************/ |
---|
16 | |
---|
17 | // Xilinx / Standard library includes |
---|
18 | #include "stdio.h" |
---|
19 | |
---|
20 | // WLAN includes |
---|
21 | #include "wlan_mac_common.h" |
---|
22 | #include "wlan_mac_dl_list.h" |
---|
23 | |
---|
24 | |
---|
25 | /******************************** Functions **********************************/ |
---|
26 | |
---|
27 | /*****************************************************************************/ |
---|
28 | /** |
---|
29 | * NOTE: Given that list operations can occur outside of an interrupt context, |
---|
30 | * specifically wlan_exp can add and remove entries from lists in code that is |
---|
31 | * interruptible, all list operations should be atomic (ie interrupts should be |
---|
32 | * disabled before manipulating the list and re-enabled after the list has been |
---|
33 | * modified. |
---|
34 | * |
---|
35 | *****************************************************************************/ |
---|
36 | |
---|
37 | |
---|
38 | /*****************************************************************************/ |
---|
39 | /** |
---|
40 | * @brief Initialize a dl_list |
---|
41 | * |
---|
42 | * @param dl_list * list - DL list to initialize |
---|
43 | * |
---|
44 | * @return None |
---|
45 | * |
---|
46 | *****************************************************************************/ |
---|
47 | void dl_list_init(dl_list* list) { |
---|
48 | if (list != NULL) { |
---|
49 | list->first = NULL; |
---|
50 | list->last = NULL; |
---|
51 | list->length = 0; |
---|
52 | } else { |
---|
53 | xil_printf("ERROR: Attempted to initialize a NULL list\n"); |
---|
54 | } |
---|
55 | return; |
---|
56 | } |
---|
57 | |
---|
58 | |
---|
59 | |
---|
60 | /*****************************************************************************/ |
---|
61 | /** |
---|
62 | * @brief Insert dl_entry after provided dl_entry in provided dl_list |
---|
63 | * |
---|
64 | * @param dl_list * list - DL list to insert new entry |
---|
65 | * @param dl_entry * entry - DL entry in DL list to insert entry after |
---|
66 | * @param dl_entry * new_entry - DL entry to insert into list |
---|
67 | * |
---|
68 | * @return None |
---|
69 | * |
---|
70 | *****************************************************************************/ |
---|
71 | void dl_entry_insertAfter(dl_list* list, dl_entry* entry, dl_entry* new_entry){ |
---|
72 | if (new_entry != NULL) { |
---|
73 | dl_entry_prev(new_entry) = entry; |
---|
74 | dl_entry_next(new_entry) = dl_entry_next(entry); |
---|
75 | |
---|
76 | if(dl_entry_next(entry) == NULL){ |
---|
77 | list->last = new_entry; |
---|
78 | } else { |
---|
79 | dl_entry_prev(dl_entry_next(entry)) = new_entry; |
---|
80 | } |
---|
81 | dl_entry_next(entry) = new_entry; |
---|
82 | |
---|
83 | (list->length)++; |
---|
84 | } else { |
---|
85 | xil_printf("ERROR: Attempted to insert a NULL dl_entry\n"); |
---|
86 | } |
---|
87 | } |
---|
88 | |
---|
89 | |
---|
90 | |
---|
91 | /*****************************************************************************/ |
---|
92 | /** |
---|
93 | * @brief Insert dl_entry before provided dl_entry in provided dl_list |
---|
94 | * |
---|
95 | * @param dl_list * list - DL list to insert new entry |
---|
96 | * @param dl_entry * entry - DL entry in DL list to insert entry before |
---|
97 | * @param dl_entry * new_entry - DL entry to insert into list |
---|
98 | * |
---|
99 | * @return None |
---|
100 | * |
---|
101 | *****************************************************************************/ |
---|
102 | void dl_entry_insertBefore(dl_list* list, dl_entry* entry, dl_entry* new_entry) { |
---|
103 | if (new_entry != NULL) { |
---|
104 | dl_entry_prev(new_entry) = dl_entry_prev(entry); |
---|
105 | dl_entry_next(new_entry) = entry; |
---|
106 | |
---|
107 | if(dl_entry_prev(entry) == NULL){ |
---|
108 | list->first = new_entry; |
---|
109 | } else { |
---|
110 | dl_entry_next(dl_entry_prev(entry)) = new_entry; |
---|
111 | } |
---|
112 | dl_entry_prev(entry) = new_entry; |
---|
113 | |
---|
114 | (list->length)++; |
---|
115 | } else { |
---|
116 | xil_printf("ERROR: Attempted to insert a NULL dl_entry\n"); |
---|
117 | } |
---|
118 | } |
---|
119 | |
---|
120 | |
---|
121 | |
---|
122 | /*****************************************************************************/ |
---|
123 | /** |
---|
124 | * @brief Insert dl_entry at the beginning of the provided dl_list |
---|
125 | * |
---|
126 | * @param dl_list * list - DL list to insert new entry |
---|
127 | * @param dl_entry * new_entry - DL entry to insert into list |
---|
128 | * |
---|
129 | * @return None |
---|
130 | * |
---|
131 | *****************************************************************************/ |
---|
132 | void dl_entry_insertBeginning(dl_list* list, dl_entry* new_entry) { |
---|
133 | if (new_entry != NULL) { |
---|
134 | if(list->first == NULL){ |
---|
135 | list->first = new_entry; |
---|
136 | list->last = new_entry; |
---|
137 | |
---|
138 | dl_entry_prev(new_entry) = NULL; |
---|
139 | dl_entry_next(new_entry) = NULL; |
---|
140 | |
---|
141 | (list->length)++; |
---|
142 | } else { |
---|
143 | dl_entry_insertBefore(list, list->first, new_entry); |
---|
144 | } |
---|
145 | } else { |
---|
146 | xil_printf("ERROR: Attempted to insert a NULL dl_entry\n"); |
---|
147 | } |
---|
148 | } |
---|
149 | |
---|
150 | |
---|
151 | |
---|
152 | /*****************************************************************************/ |
---|
153 | /** |
---|
154 | * @brief Insert dl_entry at the end of the provided dl_list |
---|
155 | * |
---|
156 | * @param dl_list * list - DL list to insert new entry |
---|
157 | * @param dl_entry * new_entry - DL entry to insert into list |
---|
158 | * |
---|
159 | * @return None |
---|
160 | * |
---|
161 | *****************************************************************************/ |
---|
162 | void dl_entry_insertEnd(dl_list* list, dl_entry* new_entry) { |
---|
163 | if (new_entry != NULL) { |
---|
164 | if (list->last == NULL) { |
---|
165 | dl_entry_insertBeginning(list, new_entry); |
---|
166 | } else { |
---|
167 | dl_entry_insertAfter(list, list->last, new_entry); |
---|
168 | } |
---|
169 | } else { |
---|
170 | xil_printf("ERROR: Attempted to insert a NULL dl_entry\n"); |
---|
171 | } |
---|
172 | } |
---|
173 | |
---|
174 | |
---|
175 | |
---|
176 | /*****************************************************************************/ |
---|
177 | /** |
---|
178 | * @brief Move multiple dl_entrys from the beginning of the src_list to the end |
---|
179 | * of the dest_list |
---|
180 | * |
---|
181 | * @param dl_list * src_list - DL list to remove entries (from beginning) |
---|
182 | * @param dl_list * dest_list - DL list to add entries (to end) |
---|
183 | * @param u16 num_entries - Number of entries to move |
---|
184 | * |
---|
185 | * @return int - Number of entries moved |
---|
186 | * |
---|
187 | *****************************************************************************/ |
---|
188 | int dl_entry_move(dl_list* src_list, dl_list* dest_list, u16 num_entries){ |
---|
189 | int num_moved; |
---|
190 | u32 idx; |
---|
191 | dl_entry* src_first; //Pointer to the first entry of the list that will be moved |
---|
192 | dl_entry* src_last; //Pointer to the last entry of the list that will be moved |
---|
193 | dl_entry* src_remaining; //Pointer to the first entry that remains in the src list after the move (can be NULL if none remain) |
---|
194 | |
---|
195 | |
---|
196 | // If the caller is not moving any entries or if there are no entries |
---|
197 | // in the source list, then just return |
---|
198 | if ((num_entries == 0) || (src_list->length == 0)) { return 0; } |
---|
199 | |
---|
200 | |
---|
201 | //1. Assign the dl_entry* endpoint markers |
---|
202 | src_first = src_list->first; |
---|
203 | |
---|
204 | if( num_entries >= src_list->length) { |
---|
205 | num_moved = src_list->length; |
---|
206 | src_last = src_list->last; |
---|
207 | src_remaining = NULL; |
---|
208 | } else { |
---|
209 | num_moved = num_entries; |
---|
210 | //Because we are moving a subset of the src_list, |
---|
211 | //we need to traverse it and find the last entry |
---|
212 | //we will move |
---|
213 | src_last = src_list->first; |
---|
214 | for(idx = 0; idx < (u16)(num_entries - 1); idx++){ |
---|
215 | src_last = dl_entry_next(src_last); |
---|
216 | } |
---|
217 | src_remaining = dl_entry_next(src_last); |
---|
218 | } |
---|
219 | |
---|
220 | //2. Stitch together the endpoints on the two lists |
---|
221 | if(dest_list->length > 0){ |
---|
222 | // There are currently entries in the destination list, so we will have to touch |
---|
223 | // the last entry to connect it to src_first |
---|
224 | dl_entry_next(dest_list->last) = src_first; |
---|
225 | dl_entry_prev(src_first) = dest_list->last; |
---|
226 | } else { |
---|
227 | dest_list->first = src_first; |
---|
228 | dl_entry_prev(src_first) = NULL; |
---|
229 | } |
---|
230 | |
---|
231 | dl_entry_next(src_last) = NULL; |
---|
232 | dest_list->last = src_last; |
---|
233 | dest_list->length += num_moved; |
---|
234 | |
---|
235 | //3. Clean up the source list |
---|
236 | if (src_remaining != NULL){ |
---|
237 | // There are remaining entries in the source list that we need to clean up |
---|
238 | src_list->first = src_remaining; |
---|
239 | dl_entry_prev(src_remaining) = NULL; |
---|
240 | } else { |
---|
241 | src_list->first = NULL; |
---|
242 | src_list->last = NULL; |
---|
243 | } |
---|
244 | src_list->length -= num_moved; |
---|
245 | |
---|
246 | |
---|
247 | return num_moved; |
---|
248 | } |
---|
249 | |
---|
250 | |
---|
251 | |
---|
252 | /*****************************************************************************/ |
---|
253 | /** |
---|
254 | * @brief Remove dl_entry from dl_list |
---|
255 | * |
---|
256 | * @param dl_list * list - DL list to remove entry |
---|
257 | * @param dl_entry * entry - DL entry to remove from list |
---|
258 | * |
---|
259 | * @return None |
---|
260 | * |
---|
261 | *****************************************************************************/ |
---|
262 | void dl_entry_remove(dl_list* list, dl_entry* entry) { |
---|
263 | if (list->length > 0) { |
---|
264 | if (entry != NULL) { |
---|
265 | if(dl_entry_prev(entry) == NULL){ |
---|
266 | list->first = dl_entry_next(entry); |
---|
267 | } else { |
---|
268 | dl_entry_next(dl_entry_prev(entry)) = dl_entry_next(entry); |
---|
269 | } |
---|
270 | |
---|
271 | if(dl_entry_next(entry) == NULL){ |
---|
272 | list->last = dl_entry_prev(entry); |
---|
273 | } else { |
---|
274 | dl_entry_prev(dl_entry_next(entry)) = dl_entry_prev(entry); |
---|
275 | } |
---|
276 | |
---|
277 | (list->length)--; |
---|
278 | |
---|
279 | // NULL fields in removed entry |
---|
280 | // NOTE: This will help in the case of pointers to "stale" entries. |
---|
281 | // |
---|
282 | // NOTE: There was discussion about whether to set the entry "data" pointer |
---|
283 | // to NULL. Currently, the code does not do this because the first |
---|
284 | // priority of the reference design is to not crash in hard to debug |
---|
285 | // ways. Trying to access or fill in a NULL data pointer would cause |
---|
286 | // the node to crash in non-obvious ways. This decision will be revisited |
---|
287 | // in future revisions of the reference design. |
---|
288 | // |
---|
289 | entry->next = NULL; |
---|
290 | entry->prev = NULL; |
---|
291 | } else { |
---|
292 | xil_printf("ERROR: Attempted to remove a NULL dl_entry\n"); |
---|
293 | } |
---|
294 | } else { |
---|
295 | xil_printf("ERROR: Attempted to remove dl_entry from dl_list that has nothing in it\n"); |
---|
296 | } |
---|
297 | } |
---|
298 | |
---|
299 | /*****************************************************************************/ |
---|
300 | /** |
---|
301 | * @brief Copy data from list |
---|
302 | * |
---|
303 | * This function is used to copy the data contents from a list into a contiguous |
---|
304 | * place in memory whose location is provided by an argument. |
---|
305 | * |
---|
306 | * @param u8* dest - destination address for copy |
---|
307 | * @param dl_entry* start_entry - First entry to copy (provided by caller) |
---|
308 | * @param dl_entry** end_entry - Last entry copied (provided to caller) |
---|
309 | * @param u32 num_entries - Number of entries to loop through |
---|
310 | * @param u32 offset_per_entry - Offset (in bytes) into entry's data where copying should start |
---|
311 | * @param u32 size_per_entry - Size (in bytes) of each entry's data that should be copied |
---|
312 | * |
---|
313 | * @return u32 - Number of bytes copied (0 if there was an error, less that num_entries*size_per_entry if list was smaller that provided argument) |
---|
314 | * |
---|
315 | *****************************************************************************/ |
---|
316 | u32 dl_list_copy_data(u8* dest, dl_entry* start_entry, dl_entry** end_entry, u32 num_entries, u32 offset_per_entry, u32 size_per_entry){ |
---|
317 | u32 num_copied; |
---|
318 | u32 i; |
---|
319 | dl_entry* curr_entry; |
---|
320 | u8* curr_dest_ptr; |
---|
321 | |
---|
322 | // Set default returns if we have to return before copying anything |
---|
323 | num_copied = 0; |
---|
324 | *end_entry = NULL; |
---|
325 | |
---|
326 | curr_entry = start_entry; |
---|
327 | curr_dest_ptr = dest; |
---|
328 | |
---|
329 | for(i=0; i<num_entries; i++){ |
---|
330 | if(curr_entry == NULL){ |
---|
331 | // The provided starting entry was not in a list of sufficient length |
---|
332 | // to handle copying num_entries number of entries. |
---|
333 | break; |
---|
334 | } |
---|
335 | |
---|
336 | // Copy data from current entry |
---|
337 | memcpy(curr_dest_ptr, ((u8*)curr_entry->data)+offset_per_entry, size_per_entry); |
---|
338 | num_copied++; |
---|
339 | *end_entry = curr_entry; |
---|
340 | |
---|
341 | |
---|
342 | curr_entry = dl_entry_next(curr_entry); |
---|
343 | curr_dest_ptr += size_per_entry; |
---|
344 | } |
---|
345 | |
---|
346 | return (num_copied*size_per_entry); |
---|
347 | } |
---|
348 | |
---|