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