[6319] | 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 | |
---|