git.sur5r.net Git - freertos/blob - FreeRTOS-Plus/Source/FreeRTOS-IoT-Libraries/c_sdk/standard/common/include/iot_linear_containers.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_linear_containers.h\r
  28  * @brief Declares and implements doubly-linked lists and queues.\r
  29  */\r
  30 \r
  31 #ifndef IOT_LINEAR_CONTAINERS_H_\r
  32 #define IOT_LINEAR_CONTAINERS_H_\r
  33 \r
  34 /* The config header is always included first. */\r
  35 #include "iot_config.h"\r
  36 \r
  37 /* Standard includes. */\r
  38 #include <stdbool.h>\r
  39 #include <stddef.h>\r
  40 #include <stdint.h>\r
  41 \r
  42 /**\r
  43  * @defgroup linear_containers_datatypes_listqueue List and queue\r
  44  * @brief Structures that represent a list or queue.\r
  45  */\r
  46 \r
  47 /**\r
  48  * @ingroup linear_containers_datatypes_listqueue\r
  49  * @brief Link member placed in structs of a list or queue.\r
  50  *\r
  51  * All elements in a list or queue must contain one of these members. The macro\r
  52  * #IotLink_Container can be used to calculate the starting address of the\r
  53  * link's container.\r
  54  */\r
  55 typedef struct IotLink\r
  56 {\r
  57     struct IotLink * pPrevious; /**< @brief Pointer to the previous element. */\r
  58     struct IotLink * pNext;     /**< @brief Pointer to the next element. */\r
  59 } IotLink_t;\r
  60 \r
  61 /**\r
  62  * @ingroup linear_containers_datatypes_listqueue\r
  63  * @brief Represents a doubly-linked list.\r
  64  */\r
  65 typedef IotLink_t   IotListDouble_t;\r
  66 \r
  67 /**\r
  68  * @ingroup linear_containers_datatypes_listqueue\r
  69  * @brief Represents a queue.\r
  70  */\r
  71 typedef IotLink_t   IotDeQueue_t;\r
  72 \r
  73 /**\r
  74  * @constantspage{linear_containers,linear containers library}\r
  75  *\r
  76  * @section linear_containers_constants_initializers Linear Containers Initializers\r
  77  * @brief Provides default values for initializing the linear containers data types.\r
  78  *\r
  79  * @snippet this define_linear_containers_initializers\r
  80  *\r
  81  * All user-facing data types of the linear containers library should be initialized\r
  82  * using one of the following.\r
  83  *\r
  84  * @warning Failure to initialize a linear containers data type with the appropriate\r
  85  * initializer may result in a runtime error!\r
  86  * @note The initializers may change at any time in future versions, but their\r
  87  * names will remain the same.\r
  88  */\r
  89 /* @[define_linear_containers_initializers] */\r
  90 #define IOT_LINK_INITIALIZER           { 0 }                /**< @brief Initializer for an #IotLink_t. */\r
  91 #define IOT_LIST_DOUBLE_INITIALIZER    IOT_LINK_INITIALIZER /**< @brief Initializer for an #IotListDouble_t. */\r
  92 #define IOT_DEQUEUE_INITIALIZER        IOT_LINK_INITIALIZER /**< @brief Initializer for an #IotDeQueue_t. */\r
  93 /* @[define_linear_containers_initializers] */\r
  94 \r
  95 /**\r
  96  * @def IotContainers_Assert( expression )\r
  97  * @brief Assertion macro for the linear containers library.\r
  98  *\r
  99  * Set @ref IOT_CONTAINERS_ENABLE_ASSERTS to `1` to enable assertions in the linear\r
 100  * containers library.\r
 101  *\r
 102  * @param[in] expression Expression to be evaluated.\r
 103  */\r
 104 #if IOT_CONTAINERS_ENABLE_ASSERTS == 1\r
 105     #ifndef IotContainers_Assert\r
 106         #include <assert.h>\r
 107         #define IotContainers_Assert( expression )    assert( expression )\r
 108     #endif\r
 109 #else\r
 110     #define IotContainers_Assert( expression )\r
 111 #endif\r
 112 \r
 113 /**\r
 114  * @brief Calculates the starting address of a containing struct.\r
 115  *\r
 116  * @param[in] type Type of the containing struct.\r
 117  * @param[in] pLink Pointer to a link member.\r
 118  * @param[in] linkName Name of the #IotLink_t in the containing struct.\r
 119  */\r
 120 #define IotLink_Container( type, pLink, linkName ) \\r
 121     ( ( type * ) ( void * ) ( ( ( uint8_t * ) ( pLink ) ) - offsetof( type, linkName ) ) )\r
 122 \r
 123 /**\r
 124  * @brief Iterates through all elements of a linear container.\r
 125  *\r
 126  * Container elements must not be freed or removed while iterating.\r
 127  *\r
 128  * @param[in] pStart The first element to iterate from.\r
 129  * @param[out] pLink Pointer to a container element.\r
 130  */\r
 131 #define IotContainers_ForEach( pStart, pLink )  \\r
 132     for( ( pLink ) = ( pStart )->pNext;         \\r
 133          ( pLink ) != ( pStart );               \\r
 134          ( pLink ) = ( pLink )->pNext )\r
 135 \r
 136 /**\r
 137  * @functionspage{linear_containers,linear containers library}\r
 138  * - @functionname{linear_containers_function_link_islinked}\r
 139  * - @functionname{linear_containers_function_list_double_create}\r
 140  * - @functionname{linear_containers_function_list_double_count}\r
 141  * - @functionname{linear_containers_function_list_double_isempty}\r
 142  * - @functionname{linear_containers_function_list_double_peekhead}\r
 143  * - @functionname{linear_containers_function_list_double_peektail}\r
 144  * - @functionname{linear_containers_function_list_double_inserthead}\r
 145  * - @functionname{linear_containers_function_list_double_inserttail}\r
 146  * - @functionname{linear_containers_function_list_double_insertbefore}\r
 147  * - @functionname{linear_containers_function_list_double_insertafter}\r
 148  * - @functionname{linear_containers_function_list_double_insertsorted}\r
 149  * - @functionname{linear_containers_function_list_double_remove}\r
 150  * - @functionname{linear_containers_function_list_double_removehead}\r
 151  * - @functionname{linear_containers_function_list_double_removetail}\r
 152  * - @functionname{linear_containers_function_list_double_removeall}\r
 153  * - @functionname{linear_containers_function_list_double_findfirstmatch}\r
 154  * - @functionname{linear_containers_function_list_double_removefirstmatch}\r
 155  * - @functionname{linear_containers_function_list_double_removeallmatches}\r
 156  * - @functionname{linear_containers_function_queue_create}\r
 157  * - @functionname{linear_containers_function_queue_count}\r
 158  * - @functionname{linear_containers_function_queue_isempty}\r
 159  * - @functionname{linear_containers_function_queue_peekhead}\r
 160  * - @functionname{linear_containers_function_queue_peektail}\r
 161  * - @functionname{linear_containers_function_queue_enqueuehead}\r
 162  * - @functionname{linear_containers_function_queue_dequeuehead}\r
 163  * - @functionname{linear_containers_function_queue_enqueuetail}\r
 164  * - @functionname{linear_containers_function_queue_dequeuetail}\r
 165  * - @functionname{linear_containers_function_queue_remove}\r
 166  * - @functionname{linear_containers_function_queue_removeall}\r
 167  * - @functionname{linear_containers_function_queue_removeallmatches}\r
 168  */\r
 169 \r
 170 /**\r
 171  * @functionpage{IotLink_IsLinked,linear_containers,link_islinked}\r
 172  * @functionpage{IotListDouble_Create,linear_containers,list_double_create}\r
 173  * @functionpage{IotListDouble_Count,linear_containers,list_double_count}\r
 174  * @functionpage{IotListDouble_IsEmpty,linear_containers,list_double_isempty}\r
 175  * @functionpage{IotListDouble_PeekHead,linear_containers,list_double_peekhead}\r
 176  * @functionpage{IotListDouble_PeekTail,linear_containers,list_double_peektail}\r
 177  * @functionpage{IotListDouble_InsertHead,linear_containers,list_double_inserthead}\r
 178  * @functionpage{IotListDouble_InsertTail,linear_containers,list_double_inserttail}\r
 179  * @functionpage{IotListDouble_InsertBefore,linear_containers,list_double_insertbefore}\r
 180  * @functionpage{IotListDouble_InsertAfter,linear_containers,list_double_insertafter}\r
 181  * @functionpage{IotListDouble_InsertSorted,linear_containers,list_double_insertsorted}\r
 182  * @functionpage{IotListDouble_Remove,linear_containers,list_double_remove}\r
 183  * @functionpage{IotListDouble_RemoveHead,linear_containers,list_double_removehead}\r
 184  * @functionpage{IotListDouble_RemoveTail,linear_containers,list_double_removetail}\r
 185  * @functionpage{IotListDouble_RemoveAll,linear_containers,list_double_removeall}\r
 186  * @functionpage{IotListDouble_FindFirstMatch,linear_containers,list_double_findfirstmatch}\r
 187  * @functionpage{IotListDouble_RemoveFirstMatch,linear_containers,list_double_removefirstmatch}\r
 188  * @functionpage{IotListDouble_RemoveAllMatches,linear_containers,list_double_removeallmatches}\r
 189  * @functionpage{IotDeQueue_Create,linear_containers,queue_create}\r
 190  * @functionpage{IotDeQueue_Count,linear_containers,queue_count}\r
 191  * @functionpage{IotDeQueue_IsEmpty,linear_containers,queue_isempty}\r
 192  * @functionpage{IotDeQueue_PeekHead,linear_containers,queue_peekhead}\r
 193  * @functionpage{IotDeQueue_PeekTail,linear_containers,queue_peektail}\r
 194  * @functionpage{IotDeQueue_EnqueueHead,linear_containers,queue_enqueuehead}\r
 195  * @functionpage{IotDeQueue_DequeueHead,linear_containers,queue_dequeuehead}\r
 196  * @functionpage{IotDeQueue_EnqueueTail,linear_containers,queue_enqueuetail}\r
 197  * @functionpage{IotDeQueue_DequeueTail,linear_containers,queue_dequeuetail}\r
 198  * @functionpage{IotDeQueue_Remove,linear_containers,queue_remove}\r
 199  * @functionpage{IotDeQueue_RemoveAll,linear_containers,queue_removeall}\r
 200  * @functionpage{IotDeQueue_RemoveAllMatches,linear_containers,queue_removeallmatches}\r
 201  */\r
 202 \r
 203 /**\r
 204  * @brief Check if an #IotLink_t is linked in a list or queue.\r
 205  *\r
 206  * @param[in] pLink The link to check.\r
 207  *\r
 208  * @return `true` if `pCurrent` is linked in a list or queue; `false` otherwise.\r
 209  */\r
 210 /* @[declare_linear_containers_link_islinked] */\r
 211 static inline bool IotLink_IsLinked( const IotLink_t * const pLink )\r
 212 /* @[declare_linear_containers_link_islinked] */\r
 213 {\r
 214     bool isLinked = false;\r
 215 \r
 216     if( pLink != NULL )\r
 217     {\r
 218         isLinked = ( pLink->pNext != NULL ) && ( pLink->pPrevious != NULL );\r
 219     }\r
 220 \r
 221     return isLinked;\r
 222 }\r
 223 \r
 224 /**\r
 225  * @brief Create a new doubly-linked list.\r
 226  *\r
 227  * This function initializes a new doubly-linked list. It must be called on an\r
 228  * uninitialized #IotListDouble_t before calling any other doubly-linked list\r
 229  * function. This function must not be called on an already-initialized\r
 230  * #IotListDouble_t.\r
 231  *\r
 232  * This function will not fail. The function @ref linear_containers_function_list_double_removeall\r
 233  * may be called to destroy a list.\r
 234  *\r
 235  * @param[in] pList Pointer to the memory that will hold the new doubly-linked list.\r
 236  */\r
 237 /* @[declare_linear_containers_list_double_create] */\r
 238 static inline void IotListDouble_Create( IotListDouble_t * const pList )\r
 239 /* @[declare_linear_containers_list_double_create] */\r
 240 {\r
 241     /* This function must not be called with a NULL parameter. */\r
 242     IotContainers_Assert( pList != NULL );\r
 243 \r
 244     /* An empty list is a link pointing to itself. */\r
 245     pList->pPrevious = pList;\r
 246     pList->pNext = pList;\r
 247 }\r
 248 \r
 249 /**\r
 250  * @brief Return the number of elements contained in an #IotListDouble_t.\r
 251  *\r
 252  * @param[in] pList The doubly-linked list with the elements to count.\r
 253  *\r
 254  * @return The number of elements in the doubly-linked list.\r
 255  */\r
 256 /* @[declare_linear_containers_list_double_count] */\r
 257 static inline size_t IotListDouble_Count( const IotListDouble_t * const pList )\r
 258 /* @[declare_linear_containers_list_double_count] */\r
 259 {\r
 260     size_t count = 0;\r
 261 \r
 262     if( pList != NULL )\r
 263     {\r
 264         /* Get the list head. */\r
 265         const IotLink_t * pCurrent = pList->pNext;\r
 266 \r
 267         /* Iterate through the list to count the elements. */\r
 268         while( pCurrent != pList )\r
 269         {\r
 270             count++;\r
 271             pCurrent = pCurrent->pNext;\r
 272         }\r
 273     }\r
 274 \r
 275     return count;\r
 276 }\r
 277 \r
 278 /**\r
 279  * @brief Check if a doubly-linked list is empty.\r
 280  *\r
 281  * @param[in] pList The doubly-linked list to check.\r
 282  *\r
 283  * @return `true` if the list is empty; `false` otherwise.\r
 284  */\r
 285 /* @[declare_linear_containers_list_double_isempty] */\r
 286 static inline bool IotListDouble_IsEmpty( const IotListDouble_t * const pList )\r
 287 /* @[declare_linear_containers_list_double_isempty] */\r
 288 {\r
 289     /* An empty list is NULL link, or a link pointing to itself. */\r
 290     return( ( pList == NULL ) || ( pList->pNext == pList ) );\r
 291 }\r
 292 \r
 293 /**\r
 294  * @brief Return an #IotLink_t representing the first element in a doubly-linked list\r
 295  * without removing it.\r
 296  *\r
 297  * @param[in] pList The list to peek.\r
 298  *\r
 299  * @return Pointer to an #IotLink_t representing the element at the head of the\r
 300  * list; `NULL` if the list is empty. The macro #IotLink_Container may be used to\r
 301  * determine the address of the link's container.\r
 302  */\r
 303 /* @[declare_linear_containers_list_double_peekhead] */\r
 304 static inline IotLink_t * IotListDouble_PeekHead( const IotListDouble_t * const pList )\r
 305 /* @[declare_linear_containers_list_double_peekhead] */\r
 306 {\r
 307     IotLink_t * pHead = NULL;\r
 308 \r
 309     if( pList != NULL )\r
 310     {\r
 311         if( IotListDouble_IsEmpty( pList ) == false )\r
 312         {\r
 313             pHead = pList->pNext;\r
 314         }\r
 315     }\r
 316 \r
 317     return pHead;\r
 318 }\r
 319 \r
 320 /**\r
 321  * @brief Return an #IotLink_t representing the last element in a doubly-linked\r
 322  * list without removing it.\r
 323  *\r
 324  * @param[in] pList The list to peek.\r
 325  *\r
 326  * @return Pointer to an #IotLink_t representing the element at the tail of the\r
 327  * list; `NULL` if the list is empty. The macro #IotLink_Container may be used to\r
 328  * determine the address of the link's container.\r
 329  */\r
 330 /* @[declare_linear_containers_list_double_peektail] */\r
 331 static inline IotLink_t * IotListDouble_PeekTail( const IotListDouble_t * const pList )\r
 332 /* @[declare_linear_containers_list_double_peektail] */\r
 333 {\r
 334     IotLink_t * pTail = NULL;\r
 335 \r
 336     if( pList != NULL )\r
 337     {\r
 338         if( IotListDouble_IsEmpty( pList ) == false )\r
 339         {\r
 340             pTail = pList->pPrevious;\r
 341         }\r
 342     }\r
 343 \r
 344     return pTail;\r
 345 }\r
 346 \r
 347 /**\r
 348  * @brief Insert an element at the head of a doubly-linked list.\r
 349  *\r
 350  * @param[in] pList The doubly-linked list that will hold the new element.\r
 351  * @param[in] pLink Pointer to the new element's link member.\r
 352  */\r
 353 /* @[declare_linear_containers_list_double_inserthead] */\r
 354 static inline void IotListDouble_InsertHead( IotListDouble_t * const pList,\r
 355                                              IotLink_t * const pLink )\r
 356 /* @[declare_linear_containers_list_double_inserthead] */\r
 357 {\r
 358     /* This function must not be called with NULL parameters. */\r
 359     IotContainers_Assert( pList != NULL );\r
 360     IotContainers_Assert( pLink != NULL );\r
 361 \r
 362     /* Save current list head. */\r
 363     IotLink_t * pHead = pList->pNext;\r
 364 \r
 365     /* Place new element before list head. */\r
 366     pLink->pNext = pHead;\r
 367     pLink->pPrevious = pList;\r
 368 \r
 369     /* Assign new list head. */\r
 370     pHead->pPrevious = pLink;\r
 371     pList->pNext = pLink;\r
 372 }\r
 373 \r
 374 /**\r
 375  * @brief Insert an element at the tail of a doubly-linked list.\r
 376  *\r
 377  * @param[in] pList The double-linked list that will hold the new element.\r
 378  * @param[in] pLink Pointer to the new element's link member.\r
 379  */\r
 380 /* @[declare_linear_containers_list_double_inserttail] */\r
 381 static inline void IotListDouble_InsertTail( IotListDouble_t * const pList,\r
 382                                              IotLink_t * const pLink )\r
 383 /* @[declare_linear_containers_list_double_inserttail] */\r
 384 {\r
 385     /* This function must not be called with NULL parameters. */\r
 386     IotContainers_Assert( pList != NULL );\r
 387     IotContainers_Assert( pLink != NULL );\r
 388 \r
 389     /* Save current list tail. */\r
 390     IotLink_t * pTail = pList->pPrevious;\r
 391 \r
 392     pLink->pNext = pList;\r
 393     pLink->pPrevious = pTail;\r
 394 \r
 395     pList->pPrevious = pLink;\r
 396     pTail->pNext = pLink;\r
 397 }\r
 398 \r
 399 /**\r
 400  * @brief Insert an element before another element in a doubly-linked list.\r
 401  *\r
 402  * @param[in] pElement The new element will be placed before this element.\r
 403  * @param[in] pLink Pointer to the new element's link member.\r
 404  */\r
 405 /* @[declare_linear_containers_list_double_insertbefore] */\r
 406 static inline void IotListDouble_InsertBefore( IotLink_t * const pElement,\r
 407                                                IotLink_t * const pLink )\r
 408 /* @[declare_linear_containers_list_double_insertbefore] */\r
 409 {\r
 410     IotListDouble_InsertTail( pElement, pLink );\r
 411 }\r
 412 \r
 413 /**\r
 414  * @brief Insert an element after another element in a doubly-linked list.\r
 415  *\r
 416  * @param[in] pElement The new element will be placed after this element.\r
 417  * @param[in] pLink Pointer to the new element's link member.\r
 418  */\r
 419 /* @[declare_linear_containers_list_double_insertafter] */\r
 420 static inline void IotListDouble_InsertAfter( IotLink_t * const pElement,\r
 421                                               IotLink_t * const pLink )\r
 422 /* @[declare_linear_containers_list_double_insertafter] */\r
 423 {\r
 424     IotListDouble_InsertHead( pElement, pLink );\r
 425 }\r
 426 \r
 427 /**\r
 428  * @brief Insert an element in a sorted doubly-linked list.\r
 429  *\r
 430  * Places an element into a list by sorting it into order. The function\r
 431  * `compare` is used to determine where to place the new element.\r
 432  *\r
 433  * @param[in] pList The list that will hold the new element.\r
 434  * @param[in] pLink Pointer to the new element's link member.\r
 435  * @param[in] compare Determines the order of the list. Returns a negative\r
 436  * value if its first argument is less than its second argument; returns\r
 437  * zero if its first argument is equal to its second argument; returns a\r
 438  * positive value if its first argument is greater than its second argument.\r
 439  * The parameters to this function are #IotLink_t, so the macro #IotLink_Container\r
 440  * may be used to determine the address of the link's container.\r
 441  */\r
 442 /* @[declare_linear_containers_list_double_insertsorted] */\r
 443 static inline void IotListDouble_InsertSorted( IotListDouble_t * const pList,\r
 444                                                IotLink_t * const pLink,\r
 445                                                int32_t ( *compare )( const IotLink_t * const, const IotLink_t * const ) )\r
 446 /* @[declare_linear_containers_list_double_insertsorted] */\r
 447 {\r
 448     /* This function must not be called with NULL parameters. */\r
 449     IotContainers_Assert( pList != NULL );\r
 450     IotContainers_Assert( pLink != NULL );\r
 451     IotContainers_Assert( compare != NULL );\r
 452 \r
 453     /* Insert at head for empty list. */\r
 454     if( IotListDouble_IsEmpty( pList ) == true )\r
 455     {\r
 456         IotListDouble_InsertHead( pList, pLink );\r
 457     }\r
 458     else\r
 459     {\r
 460         bool inserted = false;\r
 461         IotLink_t * pCurrent = pList->pNext;\r
 462 \r
 463         /* Iterate through the list to find the correct position. */\r
 464         while( pCurrent != pList )\r
 465         {\r
 466             /* Comparing for '<' preserves the order of insertion. */\r
 467             if( compare( pLink, pCurrent ) < 0 )\r
 468             {\r
 469                 IotListDouble_InsertBefore( pCurrent, pLink );\r
 470                 inserted = true;\r
 471 \r
 472                 break;\r
 473             }\r
 474 \r
 475             pCurrent = pCurrent->pNext;\r
 476         }\r
 477 \r
 478         /* New element is greater than all elements in list. Insert at tail. */\r
 479         if( inserted == false )\r
 480         {\r
 481             IotListDouble_InsertTail( pList, pLink );\r
 482         }\r
 483     }\r
 484 }\r
 485 \r
 486 /**\r
 487  * @brief Remove a single element from a doubly-linked list.\r
 488  *\r
 489  * @param[in] pLink The element to remove.\r
 490  */\r
 491 /* @[declare_linear_containers_list_double_remove] */\r
 492 static inline void IotListDouble_Remove( IotLink_t * const pLink )\r
 493 /* @[declare_linear_containers_list_double_remove] */\r
 494 {\r
 495     /* This function must not be called with a NULL parameter. */\r
 496     IotContainers_Assert( pLink != NULL );\r
 497 \r
 498     /* This function must be called on a linked element. */\r
 499     IotContainers_Assert( IotLink_IsLinked( pLink ) == true );\r
 500 \r
 501     pLink->pPrevious->pNext = pLink->pNext;\r
 502     pLink->pNext->pPrevious = pLink->pPrevious;\r
 503     pLink->pPrevious = NULL;\r
 504     pLink->pNext = NULL;\r
 505 }\r
 506 \r
 507 /**\r
 508  * @brief Remove the element at the head of a doubly-linked list.\r
 509  *\r
 510  * @param[in] pList The doubly-linked list that holds the element to remove.\r
 511  *\r
 512  * @return Pointer to an #IotLink_t representing the removed list head; `NULL`\r
 513  * if the list is empty. The macro #IotLink_Container may be used to determine\r
 514  * the address of the link's container.\r
 515  */\r
 516 /* @[declare_linear_containers_list_double_removehead] */\r
 517 static inline IotLink_t * IotListDouble_RemoveHead( IotListDouble_t * const pList )\r
 518 /* @[declare_linear_containers_list_double_removehead] */\r
 519 {\r
 520     IotLink_t * pHead = NULL;\r
 521 \r
 522     if( IotListDouble_IsEmpty( pList ) == false )\r
 523     {\r
 524         pHead = pList->pNext;\r
 525         IotListDouble_Remove( pHead );\r
 526     }\r
 527 \r
 528     return pHead;\r
 529 }\r
 530 \r
 531 /**\r
 532  * @brief Remove the element at the tail of a doubly-linked list.\r
 533  *\r
 534  * @param[in] pList The doubly-linked list that holds the element to remove.\r
 535  *\r
 536  * @return Pointer to an #IotLink_t representing the removed list tail; `NULL`\r
 537  * if the list is empty. The macro #IotLink_Container may be used to determine\r
 538  * the address of the link's container.\r
 539  */\r
 540 /* @[declare_linear_containers_list_double_removetail] */\r
 541 static inline IotLink_t * IotListDouble_RemoveTail( IotListDouble_t * const pList )\r
 542 /* @[declare_linear_containers_list_double_removetail] */\r
 543 {\r
 544     IotLink_t * pTail = NULL;\r
 545 \r
 546     if( IotListDouble_IsEmpty( pList ) == false )\r
 547     {\r
 548         pTail = pList->pPrevious;\r
 549         IotListDouble_Remove( pTail );\r
 550     }\r
 551 \r
 552     return pTail;\r
 553 }\r
 554 \r
 555 /**\r
 556  * @brief Remove all elements in a doubly-linked list.\r
 557  *\r
 558  * @param[in] pList The list to empty.\r
 559  * @param[in] freeElement A function to free memory used by each removed list\r
 560  * element. Optional; pass `NULL` to ignore.\r
 561  * @param[in] linkOffset Offset in bytes of a link member in its container, used\r
 562  * to calculate the pointer to pass to `freeElement`. This value should be calculated\r
 563  * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL`\r
 564  * or its value is `0`.\r
 565  */\r
 566 /* @[declare_linear_containers_list_double_removeall] */\r
 567 static inline void IotListDouble_RemoveAll( IotListDouble_t * const pList,\r
 568                                             void ( *freeElement )( void * ),\r
 569                                             size_t linkOffset )\r
 570 /* @[declare_linear_containers_list_double_removeall] */\r
 571 {\r
 572     /* This function must not be called with a NULL pList parameter. */\r
 573     IotContainers_Assert( pList != NULL );\r
 574 \r
 575     /* Get the list head. */\r
 576     IotLink_t * pCurrent = pList->pNext;\r
 577 \r
 578     /* Iterate through the list and remove all elements. */\r
 579     while( pCurrent != pList )\r
 580     {\r
 581         /* Save a pointer to the next list element. */\r
 582         IotLink_t * pNext = pCurrent->pNext;\r
 583 \r
 584         /* Remove and free the current list element. */\r
 585         IotListDouble_Remove( pCurrent );\r
 586 \r
 587         if( freeElement != NULL )\r
 588         {\r
 589             freeElement( ( ( uint8_t * ) pCurrent ) - linkOffset );\r
 590         }\r
 591 \r
 592         /* Move the iterating pointer to the next list element. */\r
 593         pCurrent = pNext;\r
 594     }\r
 595 }\r
 596 \r
 597 /**\r
 598  * @brief Search a doubly-linked list for the first matching element.\r
 599  *\r
 600  * If a match is found, the matching element is <b>not</b> removed from the list.\r
 601  * See @ref linear_containers_function_list_double_removefirstmatch for the function\r
 602  * that searches and removes.\r
 603  *\r
 604  * @param[in] pList The doubly-linked list to search.\r
 605  * @param[in] pStartPoint An element in `pList`. Only elements between this one and\r
 606  * the list tail are checked. Pass `NULL` to search from the beginning of the list.\r
 607  * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to\r
 608  * search using the address `pMatch`, i.e. `element == pMatch`.\r
 609  * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared\r
 610  * to this address to find a match. Otherwise, it is passed as the second argument\r
 611  * to `isMatch`.\r
 612  *\r
 613  * @return Pointer to an #IotLink_t representing the first matched element; `NULL`\r
 614  * if no match is found. The macro #IotLink_Container may be used to determine the\r
 615  * address of the link's container.\r
 616  */\r
 617 /* @[declare_linear_containers_list_double_findfirstmatch] */\r
 618 static inline IotLink_t * IotListDouble_FindFirstMatch( const IotListDouble_t * const pList,\r
 619                                                         const IotLink_t * const pStartPoint,\r
 620                                                         bool ( *isMatch )( const IotLink_t * const, void * ),\r
 621                                                         void * pMatch )\r
 622 /* @[declare_linear_containers_list_double_findfirstmatch] */\r
 623 {\r
 624     /* The const must be cast away to match this function's return value. Nevertheless,\r
 625      * this function will respect the const-ness of pStartPoint. */\r
 626     IotLink_t * pCurrent = ( IotLink_t * ) pStartPoint;\r
 627 \r
 628     /* This function must not be called with a NULL pList parameter. */\r
 629     IotContainers_Assert( pList != NULL );\r
 630 \r
 631     /* Search starting from list head if no start point is given. */\r
 632     if( pStartPoint == NULL )\r
 633     {\r
 634         pCurrent = pList->pNext;\r
 635     }\r
 636 \r
 637     /* Iterate through the list to search for matches. */\r
 638     while( pCurrent != pList )\r
 639     {\r
 640         /* Call isMatch if provided. Otherwise, compare pointers. */\r
 641         if( isMatch != NULL )\r
 642         {\r
 643             if( isMatch( pCurrent, pMatch ) == true )\r
 644             {\r
 645                 return pCurrent;\r
 646             }\r
 647         }\r
 648         else\r
 649         {\r
 650             if( pCurrent == pMatch )\r
 651             {\r
 652                 return pCurrent;\r
 653             }\r
 654         }\r
 655 \r
 656         pCurrent = pCurrent->pNext;\r
 657     }\r
 658 \r
 659     /* No match found, return NULL. */\r
 660     return NULL;\r
 661 }\r
 662 \r
 663 /**\r
 664  * @brief Search a doubly-linked list for the first matching element and remove\r
 665  * it.\r
 666  *\r
 667  * An #IotLink_t may be passed as `pList` to start searching after the head of a\r
 668  * doubly-linked list.\r
 669  *\r
 670  * @param[in] pList The doubly-linked list to search.\r
 671  * @param[in] pStartPoint An element in `pList`. Only elements between this one and\r
 672  * the list tail are checked. Pass `NULL` to search from the beginning of the list.\r
 673  * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to\r
 674  * search using the address `pMatch`, i.e. `element == pMatch`.\r
 675  * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared\r
 676  * to this address to find a match. Otherwise, it is passed as the second argument\r
 677  * to `isMatch`.\r
 678  *\r
 679  * @return Pointer to an #IotLink_t representing the matched and removed element;\r
 680  * `NULL` if no match is found. The macro #IotLink_Container may be used to determine\r
 681  * the address of the link's container.\r
 682  */\r
 683 /* @[declare_linear_containers_list_double_removefirstmatch] */\r
 684 static inline IotLink_t * IotListDouble_RemoveFirstMatch( IotListDouble_t * const pList,\r
 685                                                           const IotLink_t * const pStartPoint,\r
 686                                                           bool ( *isMatch )( const IotLink_t *, void * ),\r
 687                                                           void * pMatch )\r
 688 /* @[declare_linear_containers_list_double_removefirstmatch] */\r
 689 {\r
 690     IotLink_t * pMatchedElement = IotListDouble_FindFirstMatch( pList,\r
 691                                                                 pStartPoint,\r
 692                                                                 isMatch,\r
 693                                                                 pMatch );\r
 694 \r
 695     if( pMatchedElement != NULL )\r
 696     {\r
 697         IotListDouble_Remove( pMatchedElement );\r
 698     }\r
 699 \r
 700     return pMatchedElement;\r
 701 }\r
 702 \r
 703 /**\r
 704  * @brief Remove all matching elements from a doubly-linked list.\r
 705  *\r
 706  * @param[in] pList The doubly-linked list to search.\r
 707  * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to\r
 708  * search using the address `pMatch`, i.e. `element == pMatch`.\r
 709  * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared\r
 710  * to this address to find a match. Otherwise, it is passed as the second argument\r
 711  * to `isMatch`.\r
 712  * @param[in] freeElement A function to free memory used by each removed list\r
 713  * element. Optional; pass `NULL` to ignore.\r
 714  * @param[in] linkOffset Offset in bytes of a link member in its container, used\r
 715  * to calculate the pointer to pass to `freeElement`. This value should be calculated\r
 716  * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL`\r
 717  * or its value is `0`.\r
 718  */\r
 719 /* @[declare_linear_containers_list_double_removeallmatches] */\r
 720 static inline void IotListDouble_RemoveAllMatches( IotListDouble_t * const pList,\r
 721                                                    bool ( *isMatch )( const IotLink_t *, void * ),\r
 722                                                    void * pMatch,\r
 723                                                    void ( *freeElement )( void * ),\r
 724                                                    size_t linkOffset )\r
 725 /* @[declare_linear_containers_list_double_removeallmatches] */\r
 726 {\r
 727     IotLink_t * pMatchedElement = NULL, * pNextElement = NULL;\r
 728 \r
 729     /* Search the list for all matching elements. */\r
 730     do\r
 731     {\r
 732         pMatchedElement = IotListDouble_FindFirstMatch( pList,\r
 733                                                         pMatchedElement,\r
 734                                                         isMatch,\r
 735                                                         pMatch );\r
 736 \r
 737         if( pMatchedElement != NULL )\r
 738         {\r
 739             /* Save pointer to next element. */\r
 740             pNextElement = pMatchedElement->pNext;\r
 741 \r
 742             /* Match found; remove and free. */\r
 743             IotListDouble_Remove( pMatchedElement );\r
 744 \r
 745             if( freeElement != NULL )\r
 746             {\r
 747                 freeElement( ( ( uint8_t * ) pMatchedElement ) - linkOffset );\r
 748             }\r
 749 \r
 750             /* Continue search from next element. */\r
 751             pMatchedElement = pNextElement;\r
 752         }\r
 753     } while( pMatchedElement != NULL );\r
 754 }\r
 755 \r
 756 /**\r
 757  * @brief Create a new queue.\r
 758  *\r
 759  * This function initializes a new double-ended queue. It must be called on an uninitialized\r
 760  * #IotDeQueue_t before calling any other queue function. This function must not be\r
 761  * called on an already-initialized #IotDeQueue_t.\r
 762  *\r
 763  * This function will not fail.\r
 764  *\r
 765  * @param[in] pQueue Pointer to the memory that will hold the new queue.\r
 766  */\r
 767 /* @[declare_linear_containers_queue_create] */\r
 768 static inline void IotDeQueue_Create( IotDeQueue_t * const pQueue )\r
 769 /* @[declare_linear_containers_queue_create] */\r
 770 {\r
 771     IotListDouble_Create( pQueue );\r
 772 }\r
 773 \r
 774 /**\r
 775  * @brief Return the number of elements contained in an #IotDeQueue_t.\r
 776  *\r
 777  * @param[in] pQueue The queue with the elements to count.\r
 778  *\r
 779  * @return The number of items elements in the queue.\r
 780  */\r
 781 /* @[declare_linear_containers_queue_count] */\r
 782 static inline size_t IotDeQueue_Count( const IotDeQueue_t * const pQueue )\r
 783 /* @[declare_linear_containers_queue_count] */\r
 784 {\r
 785     return IotListDouble_Count( pQueue );\r
 786 }\r
 787 \r
 788 /**\r
 789  * @brief Check if a queue is empty.\r
 790  *\r
 791  * @param[in] pQueue The queue to check.\r
 792  *\r
 793  * @return `true` if the queue is empty; `false` otherwise.\r
 794  *\r
 795  */\r
 796 /* @[declare_linear_containers_queue_isempty] */\r
 797 static inline bool IotDeQueue_IsEmpty( const IotDeQueue_t * const pQueue )\r
 798 /* @[declare_linear_containers_queue_isempty] */\r
 799 {\r
 800     return IotListDouble_IsEmpty( pQueue );\r
 801 }\r
 802 \r
 803 /**\r
 804  * @brief Return an #IotLink_t representing the element at the front of the queue\r
 805  * without removing it.\r
 806  *\r
 807  * @param[in] pQueue The queue to peek.\r
 808  *\r
 809  * @return Pointer to an #IotLink_t representing the element at the head of the\r
 810  * queue; `NULL` if the queue is empty. The macro #IotLink_Container may be used\r
 811  * to determine the address of the link's container.\r
 812  */\r
 813 /* @[declare_linear_containers_queue_peekhead] */\r
 814 static inline IotLink_t * IotDeQueue_PeekHead( const IotDeQueue_t * const pQueue )\r
 815 /* @[declare_linear_containers_queue_peekhead] */\r
 816 {\r
 817     return IotListDouble_PeekHead( pQueue );\r
 818 }\r
 819 \r
 820 /**\r
 821  * @brief Return an #IotLink_t representing the element at the back of the queue\r
 822  * without removing it.\r
 823  *\r
 824  * @param[in] pQueue The queue to peek.\r
 825  *\r
 826  * @return Pointer to an #IotLink_t representing the element at the head of the\r
 827  * queue; `NULL` if the queue is empty. The macro #IotLink_Container may be used\r
 828  * to determine the address of the link's container.\r
 829  */\r
 830 /* @[declare_linear_containers_queue_peektail] */\r
 831 static inline IotLink_t * IotDeQueue_PeekTail( const IotDeQueue_t * const pQueue )\r
 832 /* @[declare_linear_containers_queue_peektail] */\r
 833 {\r
 834     return IotListDouble_PeekTail( pQueue );\r
 835 }\r
 836 \r
 837 /**\r
 838  * @brief Add an element at the head of the queue.\r
 839  *\r
 840  * @param[in] pQueue The queue that will hold the new element.\r
 841  * @param[in] pLink Pointer to the new element's link member.\r
 842  */\r
 843 /* @[declare_linear_containers_queue_enqueuehead] */\r
 844 static inline void IotDeQueue_EnqueueHead( IotDeQueue_t * const pQueue,\r
 845                                      IotLink_t * const pLink )\r
 846 /* @[declare_linear_containers_queue_enqueuehead] */\r
 847 {\r
 848     IotListDouble_InsertHead( pQueue, pLink );\r
 849 }\r
 850 \r
 851 /**\r
 852  * @brief Remove an element at the head of the queue.\r
 853  *\r
 854  * @param[in] pQueue The queue that holds the element to remove.\r
 855  *\r
 856  * @return Pointer to an #IotLink_t representing the removed queue element; `NULL`\r
 857  * if the queue is empty. The macro #IotLink_Container may be used to determine\r
 858  * the address of the link's container.\r
 859  */\r
 860 /* @[declare_linear_containers_queue_dequeuehead] */\r
 861 static inline IotLink_t * IotDeQueue_DequeueHead( IotDeQueue_t * const pQueue )\r
 862 /* @[declare_linear_containers_queue_dequeuehead] */\r
 863 {\r
 864     return IotListDouble_RemoveHead( pQueue );\r
 865 }\r
 866 \r
 867 /**\r
 868  * @brief Add an element at the tail of the queue.\r
 869  *\r
 870  * @param[in] pQueue The queue that will hold the new element.\r
 871  * @param[in] pLink Pointer to the new element's link member.\r
 872  */\r
 873 /* @[declare_linear_containers_queue_enqueuetail] */\r
 874 static inline void IotDeQueue_EnqueueTail( IotDeQueue_t * const pQueue,\r
 875                                      IotLink_t * const pLink )\r
 876 /* @[declare_linear_containers_queue_enqueuetail] */\r
 877 {\r
 878     IotListDouble_InsertTail( pQueue, pLink );\r
 879 }\r
 880 \r
 881 /**\r
 882  * @brief Remove an element at the tail of the queue.\r
 883  *\r
 884  * @param[in] pQueue The queue that holds the element to remove.\r
 885  *\r
 886  * @return Pointer to an #IotLink_t representing the removed queue element; `NULL`\r
 887  * if the queue is empty. The macro #IotLink_Container may be used to determine\r
 888  * the address of the link's container.\r
 889  */\r
 890 /* @[declare_linear_containers_queue_dequeuetail] */\r
 891 static inline IotLink_t * IotDeQueue_DequeueTail( IotDeQueue_t * const pQueue )\r
 892 /* @[declare_linear_containers_queue_dequeuetail] */\r
 893 {\r
 894     return IotListDouble_RemoveTail( pQueue );\r
 895 }\r
 896 \r
 897 /**\r
 898  * @brief Remove a single element from a queue.\r
 899  *\r
 900  * @param[in] pLink The element to remove.\r
 901  */\r
 902 /* @[declare_linear_containers_queue_remove] */\r
 903 static inline void IotDeQueue_Remove( IotLink_t * const pLink )\r
 904 /* @[declare_linear_containers_queue_remove] */\r
 905 {\r
 906     IotListDouble_Remove( pLink );\r
 907 }\r
 908 \r
 909 /**\r
 910  * @brief Remove all elements in a queue.\r
 911  *\r
 912  * @param[in] pQueue The queue to empty.\r
 913  * @param[in] freeElement A function to free memory used by each removed queue\r
 914  * element. Optional; pass `NULL` to ignore.\r
 915  * @param[in] linkOffset Offset in bytes of a link member in its container, used\r
 916  * to calculate the pointer to pass to `freeElement`. This value should be calculated\r
 917  * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL`\r
 918  * or its value is `0`.\r
 919  */\r
 920 /* @[declare_linear_containers_queue_removeall] */\r
 921 static inline void IotDeQueue_RemoveAll( IotDeQueue_t * const pQueue,\r
 922                                        void ( * freeElement )( void * ),\r
 923                                        size_t linkOffset )\r
 924 /* @[declare_linear_containers_queue_removeall] */\r
 925 {\r
 926     IotListDouble_RemoveAll( pQueue, freeElement, linkOffset );\r
 927 }\r
 928 \r
 929 /**\r
 930  * @brief Remove all matching elements from a queue.\r
 931  *\r
 932  * @param[in] pQueue The queue to search.\r
 933  * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to\r
 934  * search using the address `pMatch`, i.e. `element == pMatch`.\r
 935  * @param[in] pMatch If `isMatch` is `NULL`, each element in the queue is compared\r
 936  * to this address to find a match. Otherwise, it is passed as the second argument\r
 937  * to `isMatch`.\r
 938  * @param[in] freeElement A function to free memory used by each removed queue\r
 939  * element. Optional; pass `NULL` to ignore.\r
 940  * @param[in] linkOffset Offset in bytes of a link member in its container, used\r
 941  * to calculate the pointer to pass to `freeElement`. This value should be calculated\r
 942  * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL`\r
 943  * or its value is `0`.\r
 944  */\r
 945 /* @[declare_linear_containers_queue_removeallmatches] */\r
 946 static inline void IotDeQueue_RemoveAllMatches( IotDeQueue_t * const pQueue,\r
 947                                               bool ( * isMatch )( const IotLink_t *, void * ),\r
 948                                               void * pMatch,\r
 949                                               void ( * freeElement )( void * ),\r
 950                                               size_t linkOffset )\r
 951 /* @[declare_linear_containers_queue_removeallmatches] */\r
 952 {\r
 953     IotListDouble_RemoveAllMatches( pQueue, isMatch, pMatch, freeElement, linkOffset );\r
 954 }\r
 955 \r
 956 #endif /* IOT_LINEAR_CONTAINERS_H_ */\r