| /* | |
| * Amazon FreeRTOS Common V1.0.0 | |
| * Copyright (C) 2018 Amazon.com, Inc. or its affiliates. All Rights Reserved. | |
| * | |
| * Permission is hereby granted, free of charge, to any person obtaining a copy of | |
| * this software and associated documentation files (the "Software"), to deal in | |
| * the Software without restriction, including without limitation the rights to | |
| * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of | |
| * the Software, and to permit persons to whom the Software is furnished to do so, | |
| * subject to the following conditions: | |
| * | |
| * The above copyright notice and this permission notice shall be included in all | |
| * copies or substantial portions of the Software. | |
| * | |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS | |
| * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR | |
| * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER | |
| * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
| * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
| * | |
| * http://aws.amazon.com/freertos | |
| * http://www.FreeRTOS.org | |
| */ | |
| /** | |
| * @file iot_doubly_linked_list.h | |
| * @brief Doubly Linked List implementation. | |
| * | |
| * A generic implementation of circular Doubly Linked List which consists of a | |
| * list head and some list entries (zero in case of an empty list). | |
| * | |
| * To start with, a structure of type Link_t should be embedded in the structure | |
| * which is to be organized as doubly linked list. | |
| * @code | |
| * typedef struct UserStruct | |
| * { | |
| * uint32_t ulField1; | |
| * uint32_t ulField2; | |
| * Link_t xLink; | |
| * } UserStruct_t; | |
| * @endcode | |
| * | |
| * A List head should then be defined and initialized. | |
| * @code | |
| * Link_t xListHead; | |
| * listINIT_HEAD( &xListHead ); | |
| * @endcode | |
| * | |
| * listADD can then be used to add nodes to the list. | |
| * @code | |
| * listADD( &( xListHead ), &( pxUserStruct->xLink ) ); | |
| * @endcode | |
| * | |
| * listFOR_EACH can be used for traversing the list. | |
| * @code | |
| * Link_t *pxLink; | |
| * UserStruct_t *pxUserStruct; | |
| * listFOR_EACH( pxLink, &( xListHead ) ) | |
| * { | |
| * pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink ); | |
| * } | |
| * @endcode | |
| * | |
| * listFOR_EACH_SAFE should be used if you want to perform destructive operations | |
| * (like free) on nodes while traversing the list. | |
| * @code | |
| * Link_t *pxLink, *pxTempLink; | |
| * UserStruct_t *pxUserStruct; | |
| * listFOR_EACH( pxLink, pxTempLink, &( xListHead ) ) | |
| * { | |
| * pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink ); | |
| * free( pxUserStruct ); | |
| * } | |
| * @endcode | |
| */ | |
| #ifndef _AWS_DOUBLY_LINKED_LIST_H_ | |
| #define _AWS_DOUBLY_LINKED_LIST_H_ | |
| #include <stddef.h> | |
| #include <stdint.h> | |
| /** | |
| * @brief Struct embedded in any struct to make it a doubly linked | |
| * list. | |
| * | |
| * pxNext in the head points to the first node in the list and pxPrev | |
| * in the head points to the last node in the list. In case of empty | |
| * list, both pxPrev and pxNext in the head point to the head node itself. | |
| */ | |
| typedef struct Link | |
| { | |
| struct Link * pxPrev; /**< Pointer to the previous node. */ | |
| struct Link * pxNext; /**< Pointer to the next node. */ | |
| } Link_t; | |
| /** | |
| * @brief Initializes the given list head to an empty list. | |
| * | |
| * @param[in] pxHead The given list head to initialize. | |
| */ | |
| #define listINIT_HEAD( pxHead ) \ | |
| { \ | |
| ( pxHead )->pxPrev = ( pxHead ); \ | |
| ( pxHead )->pxNext = ( pxHead ); \ | |
| } | |
| /** | |
| * @brief Adds the given new node to the given list. | |
| * | |
| * @param[in] pxHead The head of the given list. | |
| * @param[in] pxLink The given new node to be added to the given | |
| * list. | |
| */ | |
| #define listADD( pxHead, pxLink ) \ | |
| { \ | |
| Link_t * pxPrevLink = ( pxHead ); \ | |
| Link_t * pxNextLink = ( ( pxHead )->pxNext ); \ | |
| \ | |
| ( pxLink )->pxNext = pxNextLink; \ | |
| pxNextLink->pxPrev = ( pxLink ); \ | |
| pxPrevLink->pxNext = ( pxLink ); \ | |
| ( pxLink )->pxPrev = ( pxPrevLink ); \ | |
| } | |
| /** | |
| * @brief Removes the given node from the list it is part of. | |
| * | |
| * If the given node is not a part of any list (i.e. next and previous | |
| * nodes are NULL), nothing happens. | |
| * | |
| * @param[in] pxLink The given node to remove from the list. | |
| */ | |
| #define listREMOVE( pxLink ) \ | |
| { \ | |
| /* If the link is part of a list, remove it from the list. */ \ | |
| if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL ) \ | |
| { \ | |
| ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext; \ | |
| ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev; \ | |
| } \ | |
| \ | |
| /* Make sure that this link is not part of any list anymore. */ \ | |
| ( pxLink )->pxPrev = NULL; \ | |
| ( pxLink )->pxNext = NULL; \ | |
| } | |
| /** | |
| * @brief Given the head of a list, checks if the list is empty. | |
| * | |
| * @param[in] pxHead The head of the given list. | |
| */ | |
| #define listIS_EMPTY( pxHead ) ( ( ( pxHead ) == NULL ) || ( ( pxHead )->pxNext == ( pxHead ) ) ) | |
| /** | |
| * @brief Removes the first node from the given list and returns it. | |
| * | |
| * Removes the first node from the given list and assigns it to the | |
| * pxLink parameter. If the list is empty, it assigns NULL to the | |
| * pxLink. | |
| * | |
| * @param[in] pxHead The head of the list from which to remove the | |
| * first node. | |
| * @param[out] pxLink The output parameter to receive the removed | |
| * node. | |
| */ | |
| #define listPOP( pxHead, pxLink ) \ | |
| { \ | |
| if( listIS_EMPTY( ( pxHead ) ) ) \ | |
| { \ | |
| ( pxLink ) = NULL; \ | |
| } \ | |
| else \ | |
| { \ | |
| ( pxLink ) = ( pxHead )->pxNext; \ | |
| /* If the link is part of a list, remove it from the list. */ \ | |
| if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL ) \ | |
| { \ | |
| ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext; \ | |
| ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev; \ | |
| } \ | |
| \ | |
| /* Make sure that this link is not part of any list anymore. */ \ | |
| ( pxLink )->pxPrev = NULL; \ | |
| ( pxLink )->pxNext = NULL; \ | |
| } \ | |
| } | |
| /** | |
| * @brief Merges a list into a given list. | |
| * | |
| * @param[in] pxHeadResultList The head of the given list into which the | |
| * other list should be merged. | |
| * @param[in] pxHeadListToMerge The head of the list to be merged into the | |
| * given list. | |
| */ | |
| #define listMERGE( pxHeadResultList, pxHeadListToMerge ) \ | |
| { \ | |
| if( !listIS_EMPTY( ( pxHeadListToMerge ) ) ) \ | |
| { \ | |
| /* Setup links between last node of listToMerge and first node of resultList. */ \ | |
| ( pxHeadListToMerge )->pxPrev->pxNext = ( pxHeadResultList )->pxNext; \ | |
| ( pxHeadResultList )->pxNext->pxPrev = ( pxHeadListToMerge )->pxPrev; \ | |
| \ | |
| /* Setup links between first node of listToMerge and the head of resultList. */ \ | |
| ( pxHeadListToMerge )->pxNext->pxPrev = ( pxHeadResultList ); \ | |
| ( pxHeadResultList )->pxNext = ( pxHeadListToMerge )->pxNext; \ | |
| /* Empty the merged list. */ \ | |
| listINIT_HEAD( ( pxHeadListToMerge ) ); \ | |
| } \ | |
| } | |
| /** | |
| * @brief Helper macro to iterate over a list. pxLink contains the link node | |
| * in each iteration. | |
| */ | |
| #define listFOR_EACH( pxLink, pxHead ) \ | |
| for( ( pxLink ) = ( pxHead )->pxNext; \ | |
| ( pxLink ) != ( pxHead ); \ | |
| ( pxLink ) = ( pxLink )->pxNext ) | |
| /** | |
| * @brief Helper macro to iterate over a list. It is safe to destroy/free the | |
| * nodes while iterating. pxLink contains the link node in each iteration. | |
| */ | |
| #define listFOR_EACH_SAFE( pxLink, pxTempLink, pxHead ) \ | |
| for( ( pxLink ) = ( pxHead )->pxNext, ( pxTempLink ) = ( pxLink )->pxNext; \ | |
| ( pxLink ) != ( pxHead ); \ | |
| ( pxLink ) = ( pxTempLink ), ( pxTempLink ) = ( pxLink )->pxNext ) | |
| /** | |
| * @brief Given the pointer to the link member (of type Link_t) in a struct, | |
| * extracts the pointer to the containing struct. | |
| * | |
| * @param[in] pxLink The pointer to the link member. | |
| * @param[in] type The type of the containing struct. | |
| * @param[in] member Name of the link member in the containing struct. | |
| */ | |
| #define listCONTAINER( pxLink, type, member ) ( ( type * ) ( ( uint8_t * ) ( pxLink ) - ( uint8_t * ) ( &( ( type * ) 0 )->member ) ) ) | |
| #endif /* _AWS_DOUBLY_LINKED_LIST_H_ */ |