git.sur5r.net Git - freertos/blob - FreeRTOS-Labs/Demo/FreeRTOS_Plus_POSIX_with_actor_Windows_Simulator/lib/include/private/iot_doubly_linked_list.h

   1 /*\r
   2  * Amazon FreeRTOS Common V1.0.0\r
   3  * Copyright (C) 2018 Amazon.com, Inc. or its affiliates.  All Rights Reserved.\r
   4  *\r
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of\r
   6  * this software and associated documentation files (the "Software"), to deal in\r
   7  * the Software without restriction, including without limitation the rights to\r
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of\r
   9  * the Software, and to permit persons to whom the Software is furnished to do so,\r
  10  * subject to the following conditions:\r
  11  *\r
  12  * The above copyright notice and this permission notice shall be included in all\r
  13  * copies or substantial portions of the Software.\r
  14  *\r
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS\r
  17  * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR\r
  18  * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER\r
  19  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN\r
  20  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.\r
  21  *\r
  22  * http://aws.amazon.com/freertos\r
  23  * http://www.FreeRTOS.org\r
  24  */\r
  25 \r
  26 /**\r
  27  * @file iot_doubly_linked_list.h\r
  28  * @brief Doubly Linked List implementation.\r
  29  *\r
  30  * A generic implementation of circular Doubly Linked List which consists of a\r
  31  * list head and some list entries (zero in case of an empty list).\r
  32  *\r
  33  * To start with, a structure of type Link_t should be embedded in the structure\r
  34  * which is to be organized as doubly linked list.\r
  35  * @code\r
  36  * typedef struct UserStruct\r
  37  * {\r
  38  *     uint32_t ulField1;\r
  39  *     uint32_t ulField2;\r
  40  *     Link_t xLink;\r
  41  * } UserStruct_t;\r
  42  * @endcode\r
  43  *\r
  44  * A List head should then be defined and initialized.\r
  45  * @code\r
  46  * Link_t xListHead;\r
  47  * listINIT_HEAD( &xListHead );\r
  48  * @endcode\r
  49  *\r
  50  * listADD can then be used to add nodes to the list.\r
  51  * @code\r
  52  * listADD( &( xListHead ), &( pxUserStruct->xLink ) );\r
  53  * @endcode\r
  54  *\r
  55  * listFOR_EACH can be used for traversing the list.\r
  56  * @code\r
  57  * Link_t *pxLink;\r
  58  * UserStruct_t *pxUserStruct;\r
  59  * listFOR_EACH( pxLink, &( xListHead ) )\r
  60  * {\r
  61  *      pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink );\r
  62  * }\r
  63  * @endcode\r
  64  *\r
  65  * listFOR_EACH_SAFE should be used if you want to perform destructive operations\r
  66  * (like free) on nodes while traversing the list.\r
  67  * @code\r
  68  * Link_t *pxLink, *pxTempLink;\r
  69  * UserStruct_t *pxUserStruct;\r
  70  * listFOR_EACH( pxLink, pxTempLink, &( xListHead ) )\r
  71  * {\r
  72  *      pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink );\r
  73  *      free( pxUserStruct );\r
  74  * }\r
  75  * @endcode\r
  76  */\r
  77 \r
  78 #ifndef _AWS_DOUBLY_LINKED_LIST_H_\r
  79 #define _AWS_DOUBLY_LINKED_LIST_H_\r
  80 \r
  81 #include <stddef.h>\r
  82 #include <stdint.h>\r
  83 \r
  84 /**\r
  85  * @brief Struct embedded in any struct to make it a doubly linked\r
  86  * list.\r
  87  *\r
  88  * pxNext in the head points to the first node in the list and pxPrev\r
  89  * in the head points to the last node in the list. In case of empty\r
  90  * list, both pxPrev and pxNext in the head point to the head node itself.\r
  91  */\r
  92 typedef struct Link\r
  93 {\r
  94     struct Link * pxPrev; /**< Pointer to the previous node. */\r
  95     struct Link * pxNext; /**< Pointer to the next node. */\r
  96 } Link_t;\r
  97 \r
  98 /**\r
  99  * @brief Initializes the given list head to an empty list.\r
 100  *\r
 101  * @param[in] pxHead The given list head to initialize.\r
 102  */\r
 103 #define listINIT_HEAD( pxHead )          \\r
 104     {                                    \\r
 105         ( pxHead )->pxPrev = ( pxHead ); \\r
 106         ( pxHead )->pxNext = ( pxHead ); \\r
 107     }\r
 108 \r
 109 /**\r
 110  * @brief Adds the given new node to the given list.\r
 111  *\r
 112  * @param[in] pxHead The head of the given list.\r
 113  * @param[in] pxLink The given new node to be added to the given\r
 114  * list.\r
 115  */\r
 116 #define listADD( pxHead, pxLink )                     \\r
 117     {                                                 \\r
 118         Link_t * pxPrevLink = ( pxHead );             \\r
 119         Link_t * pxNextLink = ( ( pxHead )->pxNext ); \\r
 120                                                       \\r
 121         ( pxLink )->pxNext = pxNextLink;              \\r
 122         pxNextLink->pxPrev = ( pxLink );              \\r
 123         pxPrevLink->pxNext = ( pxLink );              \\r
 124         ( pxLink )->pxPrev = ( pxPrevLink );          \\r
 125     }\r
 126 \r
 127 /**\r
 128  * @brief Removes the given node from the list it is part of.\r
 129  *\r
 130  * If the given node is not a part of any list (i.e. next and previous\r
 131  * nodes are NULL), nothing happens.\r
 132  *\r
 133  * @param[in] pxLink The given node to remove from the list.\r
 134  */\r
 135 #define listREMOVE( pxLink )                                            \\r
 136     {                                                                   \\r
 137         /* If the link is part of a list, remove it from the list. */   \\r
 138         if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL )  \\r
 139         {                                                               \\r
 140             ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext;            \\r
 141             ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev;            \\r
 142         }                                                               \\r
 143                                                                         \\r
 144         /* Make sure that this link is not part of any list anymore. */ \\r
 145         ( pxLink )->pxPrev = NULL;                                      \\r
 146         ( pxLink )->pxNext = NULL;                                      \\r
 147     }\r
 148 \r
 149 /**\r
 150  * @brief Given the head of a list, checks if the list is empty.\r
 151  *\r
 152  * @param[in] pxHead The head of the given list.\r
 153  */\r
 154 #define listIS_EMPTY( pxHead )    ( ( ( pxHead ) == NULL ) || ( ( pxHead )->pxNext == ( pxHead ) ) )\r
 155 \r
 156 /**\r
 157  * @brief Removes the first node from the given list and returns it.\r
 158  *\r
 159  * Removes the first node from the given list and assigns it to the\r
 160  * pxLink parameter. If the list is empty, it assigns NULL to the\r
 161  * pxLink.\r
 162  *\r
 163  * @param[in] pxHead The head of the list from which to remove the\r
 164  * first node.\r
 165  * @param[out] pxLink The output parameter to receive the removed\r
 166  * node.\r
 167  */\r
 168 #define listPOP( pxHead, pxLink )                                           \\r
 169     {                                                                       \\r
 170         if( listIS_EMPTY( ( pxHead ) ) )                                    \\r
 171         {                                                                   \\r
 172             ( pxLink ) = NULL;                                              \\r
 173         }                                                                   \\r
 174         else                                                                \\r
 175         {                                                                   \\r
 176             ( pxLink ) = ( pxHead )->pxNext;                                \\r
 177             /* If the link is part of a list, remove it from the list. */   \\r
 178             if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL )  \\r
 179             {                                                               \\r
 180                 ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext;            \\r
 181                 ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev;            \\r
 182             }                                                               \\r
 183                                                                             \\r
 184             /* Make sure that this link is not part of any list anymore. */ \\r
 185             ( pxLink )->pxPrev = NULL;                                      \\r
 186             ( pxLink )->pxNext = NULL;                                      \\r
 187         }                                                                   \\r
 188     }\r
 189 \r
 190 /**\r
 191  * @brief Merges a list into a given list.\r
 192  *\r
 193  * @param[in] pxHeadResultList The head of the given list into which the\r
 194  * other list should be merged.\r
 195  * @param[in] pxHeadListToMerge The head of the list to be merged into the\r
 196  * given list.\r
 197  */\r
 198 #define listMERGE( pxHeadResultList, pxHeadListToMerge )                                     \\r
 199     {                                                                                        \\r
 200         if( !listIS_EMPTY( ( pxHeadListToMerge ) ) )                                         \\r
 201         {                                                                                    \\r
 202             /* Setup links between last node of listToMerge and first node of resultList. */ \\r
 203             ( pxHeadListToMerge )->pxPrev->pxNext = ( pxHeadResultList )->pxNext;            \\r
 204             ( pxHeadResultList )->pxNext->pxPrev = ( pxHeadListToMerge )->pxPrev;            \\r
 205                                                                                              \\r
 206             /* Setup links between first node of listToMerge and the head of resultList. */  \\r
 207             ( pxHeadListToMerge )->pxNext->pxPrev = ( pxHeadResultList );                    \\r
 208             ( pxHeadResultList )->pxNext = ( pxHeadListToMerge )->pxNext;                    \\r
 209             /* Empty the merged list. */                                                     \\r
 210             listINIT_HEAD( ( pxHeadListToMerge ) );                                          \\r
 211         }                                                                                    \\r
 212     }\r
 213 \r
 214 /**\r
 215  * @brief Helper macro to iterate over a list. pxLink contains the link node\r
 216  * in each iteration.\r
 217  */\r
 218 #define listFOR_EACH( pxLink, pxHead )    \\r
 219     for( ( pxLink ) = ( pxHead )->pxNext; \\r
 220          ( pxLink ) != ( pxHead );        \\r
 221          ( pxLink ) = ( pxLink )->pxNext )\r
 222 \r
 223 /**\r
 224  * @brief Helper macro to iterate over a list. It is safe to destroy/free the\r
 225  * nodes while iterating. pxLink contains the link node in each iteration.\r
 226  */\r
 227 #define listFOR_EACH_SAFE( pxLink, pxTempLink, pxHead )                        \\r
 228     for( ( pxLink ) = ( pxHead )->pxNext, ( pxTempLink ) = ( pxLink )->pxNext; \\r
 229          ( pxLink ) != ( pxHead );                                             \\r
 230          ( pxLink ) = ( pxTempLink ), ( pxTempLink ) = ( pxLink )->pxNext )\r
 231 \r
 232 /**\r
 233  * @brief Given the pointer to the link member (of type Link_t) in a struct,\r
 234  * extracts the pointer to the containing struct.\r
 235  *\r
 236  * @param[in] pxLink The pointer to the link member.\r
 237  * @param[in] type The type of the containing struct.\r
 238  * @param[in] member Name of the link member in the containing struct.\r
 239  */\r
 240 #define listCONTAINER( pxLink, type, member )    ( ( type * ) ( ( uint8_t * ) ( pxLink ) - ( uint8_t * ) ( &( ( type * ) 0 )->member ) ) )\r
 241 \r
 242 #endif /* _AWS_DOUBLY_LINKED_LIST_H_ */\r