/* * FreeRTOS Common V1.2.0 * Copyright (C) 2020 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_ble_linear_containers.h * @brief Declares and implements doubly-linked lists and queues. */ #ifndef IOT_LINEAR_CONTAINERS_H_ #define IOT_LINEAR_CONTAINERS_H_ /* The config header is always included first. */ #include "iot_config.h" /* Standard includes. */ #include #include #include /** * @defgroup linear_containers_datatypes_listqueue List and queue * @brief Structures that represent a list or queue. */ /** * @ingroup linear_containers_datatypes_listqueue * @brief Link member placed in structs of a list or queue. * * All elements in a list or queue must contain one of these members. The macro * #IotLink_Container can be used to calculate the starting address of the * link's container. */ typedef struct IotLink { struct IotLink * pPrevious; /**< @brief Pointer to the previous element. */ struct IotLink * pNext; /**< @brief Pointer to the next element. */ } IotLink_t; /** * @ingroup linear_containers_datatypes_listqueue * @brief Represents a doubly-linked list. */ typedef IotLink_t IotListDouble_t; /** * @ingroup linear_containers_datatypes_listqueue * @brief Represents a queue. */ typedef IotLink_t IotDeQueue_t; /** * @constants_page{linear_containers} * @constants_brief{linear containers library} * * @section linear_containers_constants_initializers Linear Containers Initializers * @brief Provides default values for initializing the linear containers data types. * * @snippet this define_linear_containers_initializers * * All user-facing data types of the linear containers library should be initialized * using one of the following. * * @warning Failure to initialize a linear containers data type with the appropriate * initializer may result in a runtime error! * @note The initializers may change at any time in future versions, but their * names will remain the same. */ /* @[define_linear_containers_initializers] */ #define IOT_LINK_INITIALIZER { 0 } /**< @brief Initializer for an #IotLink_t. */ #define IOT_LIST_DOUBLE_INITIALIZER IOT_LINK_INITIALIZER /**< @brief Initializer for an #IotListDouble_t. */ #define IOT_DEQUEUE_INITIALIZER IOT_LINK_INITIALIZER /**< @brief Initializer for an #IotDeQueue_t. */ /* @[define_linear_containers_initializers] */ /** * @def IotContainers_Assert( expression ) * @brief Assertion macro for the linear containers library. * * Set @ref IOT_CONTAINERS_ENABLE_ASSERTS to `1` to enable assertions in the linear * containers library. * * @param[in] expression Expression to be evaluated. */ #if IOT_CONTAINERS_ENABLE_ASSERTS == 1 #ifndef IotContainers_Assert #include #define IotContainers_Assert( expression ) assert( expression ) #endif #else #define IotContainers_Assert( expression ) #endif /** * @brief Calculates the starting address of a containing struct. * * @param[in] type Type of the containing struct. * @param[in] pLink Pointer to a link member. * @param[in] linkName Name of the #IotLink_t in the containing struct. */ #define IotLink_Container( type, pLink, linkName ) \ ( ( type * ) ( void * ) ( ( ( uint8_t * ) ( pLink ) ) - offsetof( type, linkName ) ) ) /** * @brief Iterates through all elements of a linear container. * * Container elements must not be freed or removed while iterating. * * @param[in] pStart The first element to iterate from. * @param[out] pLink Pointer to a container element. */ #define IotContainers_ForEach( pStart, pLink ) \ for( ( pLink ) = ( pStart )->pNext; \ ( pLink ) != ( pStart ); \ ( pLink ) = ( pLink )->pNext ) /** * @functions_page{linear_containers, Linear Containers} * @functions_brief{linear containers} * - @function_name{linear_containers_function_link_islinked} * @function_brief{linear_containers_function_link_islinked} * - @function_name{linear_containers_function_list_double_create} * @function_brief{linear_containers_function_list_double_create} * - @function_name{linear_containers_function_list_double_count} * @function_brief{linear_containers_function_list_double_count} * - @function_name{linear_containers_function_list_double_isempty} * @function_brief{linear_containers_function_list_double_isempty} * - @function_name{linear_containers_function_list_double_peekhead} * @function_brief{linear_containers_function_list_double_peekhead} * - @function_name{linear_containers_function_list_double_peektail} * @function_brief{linear_containers_function_list_double_peektail} * - @function_name{linear_containers_function_list_double_inserthead} * @function_brief{linear_containers_function_list_double_inserthead} * - @function_name{linear_containers_function_list_double_inserttail} * @function_brief{linear_containers_function_list_double_inserttail} * - @function_name{linear_containers_function_list_double_insertbefore} * @function_brief{linear_containers_function_list_double_insertbefore} * - @function_name{linear_containers_function_list_double_insertafter} * @function_brief{linear_containers_function_list_double_insertafter} * - @function_name{linear_containers_function_list_double_insertsorted} * @function_brief{linear_containers_function_list_double_insertsorted} * - @function_name{linear_containers_function_list_double_remove} * @function_brief{linear_containers_function_list_double_remove} * - @function_name{linear_containers_function_list_double_removehead} * @function_brief{linear_containers_function_list_double_removehead} * - @function_name{linear_containers_function_list_double_removetail} * @function_brief{linear_containers_function_list_double_removetail} * - @function_name{linear_containers_function_list_double_removeall} * @function_brief{linear_containers_function_list_double_removeall} * - @function_name{linear_containers_function_list_double_findfirstmatch} * @function_brief{linear_containers_function_list_double_findfirstmatch} * - @function_name{linear_containers_function_list_double_removefirstmatch} * @function_brief{linear_containers_function_list_double_removefirstmatch} * - @function_name{linear_containers_function_list_double_removeallmatches} * @function_brief{linear_containers_function_list_double_removeallmatches} * - @function_name{linear_containers_function_queue_create} * @function_brief{linear_containers_function_queue_create} * - @function_name{linear_containers_function_queue_count} * @function_brief{linear_containers_function_queue_count} * - @function_name{linear_containers_function_queue_isempty} * @function_brief{linear_containers_function_queue_isempty} * - @function_name{linear_containers_function_queue_peekhead} * @function_brief{linear_containers_function_queue_peekhead} * - @function_name{linear_containers_function_queue_peektail} * @function_brief{linear_containers_function_queue_peektail} * - @function_name{linear_containers_function_queue_enqueuehead} * @function_brief{linear_containers_function_queue_enqueuehead} * - @function_name{linear_containers_function_queue_dequeuehead} * @function_brief{linear_containers_function_queue_dequeuehead} * - @function_name{linear_containers_function_queue_enqueuetail} * @function_brief{linear_containers_function_queue_enqueuetail} * - @function_name{linear_containers_function_queue_dequeuetail} * @function_brief{linear_containers_function_queue_dequeuetail} * - @function_name{linear_containers_function_queue_remove} * @function_brief{linear_containers_function_queue_remove} * - @function_name{linear_containers_function_queue_removeall} * @function_brief{linear_containers_function_queue_removeall} * - @function_name{linear_containers_function_queue_removeallmatches} * @function_brief{linear_containers_function_queue_removeallmatches} */ /** * @function_page{IotLink_IsLinked,linear_containers,link_islinked} * @function_snippet{linear_containers,link_islinked,this} * @copydoc IotLink_IsLinked * @function_page{IotListDouble_Create,linear_containers,list_double_create} * @function_snippet{linear_containers,list_double_create,this} * @copydoc IotListDouble_Create * @function_page{IotListDouble_Count,linear_containers,list_double_count} * @function_snippet{linear_containers,list_double_count,this} * @copydoc IotListDouble_Count * @function_page{IotListDouble_IsEmpty,linear_containers,list_double_isempty} * @function_snippet{linear_containers,list_double_isempty,this} * @copydoc IotListDouble_IsEmpty * @function_page{IotListDouble_PeekHead,linear_containers,list_double_peekhead} * @function_snippet{linear_containers,list_double_peekhead,this} * @copydoc IotListDouble_PeekHead * @function_page{IotListDouble_PeekTail,linear_containers,list_double_peektail} * @function_snippet{linear_containers,list_double_peektail,this} * @copydoc IotListDouble_PeekTail * @function_page{IotListDouble_InsertHead,linear_containers,list_double_inserthead} * @function_snippet{linear_containers,list_double_inserthead,this} * @copydoc IotListDouble_InsertHead * @function_page{IotListDouble_InsertTail,linear_containers,list_double_inserttail} * @function_snippet{linear_containers,list_double_inserttail,this} * @copydoc IotListDouble_InsertTail * @function_page{IotListDouble_InsertBefore,linear_containers,list_double_insertbefore} * @function_snippet{linear_containers,list_double_insertbefore,this} * @copydoc IotListDouble_InsertBefore * @function_page{IotListDouble_InsertAfter,linear_containers,list_double_insertafter} * @function_snippet{linear_containers,list_double_insertafter,this} * @copydoc IotListDouble_InsertAfter * @function_page{IotListDouble_InsertSorted,linear_containers,list_double_insertsorted} * @function_snippet{linear_containers,list_double_insertsorted,this} * @copydoc IotListDouble_InsertSorted * @function_page{IotListDouble_Remove,linear_containers,list_double_remove} * @function_snippet{linear_containers,list_double_remove,this} * @copydoc IotListDouble_Remove * @function_page{IotListDouble_RemoveHead,linear_containers,list_double_removehead} * @function_snippet{linear_containers,list_double_removehead,this} * @copydoc IotListDouble_RemoveHead * @function_page{IotListDouble_RemoveTail,linear_containers,list_double_removetail} * @function_snippet{linear_containers,list_double_removetail,this} * @copydoc IotListDouble_RemoveTail * @function_page{IotListDouble_RemoveAll,linear_containers,list_double_removeall} * @function_snippet{linear_containers,list_double_removeall,this} * @copydoc IotListDouble_RemoveAll * @function_page{IotListDouble_FindFirstMatch,linear_containers,list_double_findfirstmatch} * @function_snippet{linear_containers,list_double_findfirstmatch,this} * @copydoc IotListDouble_FindFirstMatch * @function_page{IotListDouble_RemoveFirstMatch,linear_containers,list_double_removefirstmatch} * @function_snippet{linear_containers,list_double_removefirstmatch,this} * @copydoc IotListDouble_RemoveFirstMatch * @function_page{IotListDouble_RemoveAllMatches,linear_containers,list_double_removeallmatches} * @function_snippet{linear_containers,list_double_removeallmatches,this} * @copydoc IotListDouble_RemoveAllMatches * @function_page{IotDeQueue_Create,linear_containers,queue_create} * @function_snippet{linear_containers,queue_create,this} * @copydoc IotDeQueue_Create * @function_page{IotDeQueue_Count,linear_containers,queue_count} * @function_snippet{linear_containers,queue_count,this} * @copydoc IotDeQueue_Count * @function_page{IotDeQueue_IsEmpty,linear_containers,queue_isempty} * @function_snippet{linear_containers,queue_isempty,this} * @copydoc IotDeQueue_IsEmpty * @function_page{IotDeQueue_PeekHead,linear_containers,queue_peekhead} * @function_snippet{linear_containers,queue_peekhead,this} * @copydoc IotDeQueue_PeekHead * @function_page{IotDeQueue_PeekTail,linear_containers,queue_peektail} * @function_snippet{linear_containers,queue_peektail,this} * @copydoc IotDeQueue_PeekTail * @function_page{IotDeQueue_EnqueueHead,linear_containers,queue_enqueuehead} * @function_snippet{linear_containers,queue_enqueuehead,this} * @copydoc IotDeQueue_EnqueueHead * @function_page{IotDeQueue_DequeueHead,linear_containers,queue_dequeuehead} * @function_snippet{linear_containers,queue_dequeuehead,this} * @copydoc IotDeQueue_DequeueHead * @function_page{IotDeQueue_EnqueueTail,linear_containers,queue_enqueuetail} * @function_snippet{linear_containers,queue_enqueuetail,this} * @copydoc IotDeQueue_EnqueueTail * @function_page{IotDeQueue_DequeueTail,linear_containers,queue_dequeuetail} * @function_snippet{linear_containers,queue_dequeuetail,this} * @copydoc IotDeQueue_DequeueTail * @function_page{IotDeQueue_Remove,linear_containers,queue_remove} * @function_snippet{linear_containers,queue_remove,this} * @copydoc IotDeQueue_Remove * @function_page{IotDeQueue_RemoveAll,linear_containers,queue_removeall} * @function_snippet{linear_containers,queue_removeall,this} * @copydoc IotDeQueue_RemoveAll * @function_page{IotDeQueue_RemoveAllMatches,linear_containers,queue_removeallmatches} * @function_snippet{linear_containers,queue_removeallmatches,this} * @copydoc IotDeQueue_RemoveAllMatches */ /** * @brief Check if an #IotLink_t is linked in a list or queue. * * @param[in] pLink The link to check. * * @return `true` if `pCurrent` is linked in a list or queue; `false` otherwise. */ /* @[declare_linear_containers_link_islinked] */ static inline bool IotLink_IsLinked( const IotLink_t * const pLink ) /* @[declare_linear_containers_link_islinked] */ { bool isLinked = false; if( pLink != NULL ) { isLinked = ( pLink->pNext != NULL ) && ( pLink->pPrevious != NULL ); } return isLinked; } /** * @brief Create a new doubly-linked list. * * This function initializes a new doubly-linked list. It must be called on an * uninitialized #IotListDouble_t before calling any other doubly-linked list * function. This function must not be called on an already-initialized * #IotListDouble_t. * * This function will not fail. The function @ref linear_containers_function_list_double_removeall * may be called to destroy a list. * * @param[in] pList Pointer to the memory that will hold the new doubly-linked list. */ /* @[declare_linear_containers_list_double_create] */ static inline void IotListDouble_Create( IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_create] */ { /* This function must not be called with a NULL parameter. */ IotContainers_Assert( pList != NULL ); /* An empty list is a link pointing to itself. */ pList->pPrevious = pList; pList->pNext = pList; } /** * @brief Return the number of elements contained in an #IotListDouble_t. * * @param[in] pList The doubly-linked list with the elements to count. * * @return The number of elements in the doubly-linked list. */ /* @[declare_linear_containers_list_double_count] */ static inline size_t IotListDouble_Count( const IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_count] */ { size_t count = 0; if( pList != NULL ) { /* Get the list head. */ const IotLink_t * pCurrent = pList->pNext; /* Iterate through the list to count the elements. */ while( pCurrent != pList ) { count++; pCurrent = pCurrent->pNext; } } return count; } /** * @brief Check if a doubly-linked list is empty. * * @param[in] pList The doubly-linked list to check. * * @return `true` if the list is empty; `false` otherwise. */ /* @[declare_linear_containers_list_double_isempty] */ static inline bool IotListDouble_IsEmpty( const IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_isempty] */ { /* An empty list is NULL link, or a link pointing to itself. */ return( ( pList == NULL ) || ( pList->pNext == pList ) ); } /** * @brief Return an #IotLink_t representing the first element in a doubly-linked list * without removing it. * * @param[in] pList The list to peek. * * @return Pointer to an #IotLink_t representing the element at the head of the * list; `NULL` if the list is empty. The macro #IotLink_Container may be used to * determine the address of the link's container. */ /* @[declare_linear_containers_list_double_peekhead] */ static inline IotLink_t * IotListDouble_PeekHead( const IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_peekhead] */ { IotLink_t * pHead = NULL; if( pList != NULL ) { if( IotListDouble_IsEmpty( pList ) == false ) { pHead = pList->pNext; } } return pHead; } /** * @brief Return an #IotLink_t representing the last element in a doubly-linked * list without removing it. * * @param[in] pList The list to peek. * * @return Pointer to an #IotLink_t representing the element at the tail of the * list; `NULL` if the list is empty. The macro #IotLink_Container may be used to * determine the address of the link's container. */ /* @[declare_linear_containers_list_double_peektail] */ static inline IotLink_t * IotListDouble_PeekTail( const IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_peektail] */ { IotLink_t * pTail = NULL; if( pList != NULL ) { if( IotListDouble_IsEmpty( pList ) == false ) { pTail = pList->pPrevious; } } return pTail; } /** * @brief Insert an element at the head of a doubly-linked list. * * @param[in] pList The doubly-linked list that will hold the new element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_list_double_inserthead] */ static inline void IotListDouble_InsertHead( IotListDouble_t * const pList, IotLink_t * const pLink ) /* @[declare_linear_containers_list_double_inserthead] */ { /* This function must not be called with NULL parameters. */ IotContainers_Assert( pList != NULL ); IotContainers_Assert( pLink != NULL ); /* Save current list head. */ IotLink_t * pHead = pList->pNext; /* Place new element before list head. */ pLink->pNext = pHead; pLink->pPrevious = pList; /* Assign new list head. */ pHead->pPrevious = pLink; pList->pNext = pLink; } /** * @brief Insert an element at the tail of a doubly-linked list. * * @param[in] pList The double-linked list that will hold the new element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_list_double_inserttail] */ static inline void IotListDouble_InsertTail( IotListDouble_t * const pList, IotLink_t * const pLink ) /* @[declare_linear_containers_list_double_inserttail] */ { /* This function must not be called with NULL parameters. */ IotContainers_Assert( pList != NULL ); IotContainers_Assert( pLink != NULL ); /* Save current list tail. */ IotLink_t * pTail = pList->pPrevious; pLink->pNext = pList; pLink->pPrevious = pTail; pList->pPrevious = pLink; pTail->pNext = pLink; } /** * @brief Insert an element before another element in a doubly-linked list. * * @param[in] pElement The new element will be placed before this element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_list_double_insertbefore] */ static inline void IotListDouble_InsertBefore( IotLink_t * const pElement, IotLink_t * const pLink ) /* @[declare_linear_containers_list_double_insertbefore] */ { IotListDouble_InsertTail( pElement, pLink ); } /** * @brief Insert an element after another element in a doubly-linked list. * * @param[in] pElement The new element will be placed after this element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_list_double_insertafter] */ static inline void IotListDouble_InsertAfter( IotLink_t * const pElement, IotLink_t * const pLink ) /* @[declare_linear_containers_list_double_insertafter] */ { IotListDouble_InsertHead( pElement, pLink ); } /** * @brief Insert an element in a sorted doubly-linked list. * * Places an element into a list by sorting it into order. The function * `compare` is used to determine where to place the new element. * * @param[in] pList The list that will hold the new element. * @param[in] pLink Pointer to the new element's link member. * @param[in] compare Determines the order of the list. Returns a negative * value if its first argument is less than its second argument; returns * zero if its first argument is equal to its second argument; returns a * positive value if its first argument is greater than its second argument. * The parameters to this function are #IotLink_t, so the macro #IotLink_Container * may be used to determine the address of the link's container. */ /* @[declare_linear_containers_list_double_insertsorted] */ static inline void IotListDouble_InsertSorted( IotListDouble_t * const pList, IotLink_t * const pLink, int32_t ( * compare )( const IotLink_t * const, const IotLink_t * const ) ) /* @[declare_linear_containers_list_double_insertsorted] */ { /* This function must not be called with NULL parameters. */ IotContainers_Assert( pList != NULL ); IotContainers_Assert( pLink != NULL ); IotContainers_Assert( compare != NULL ); /* Insert at head for empty list. */ if( IotListDouble_IsEmpty( pList ) == true ) { IotListDouble_InsertHead( pList, pLink ); } else { bool inserted = false; IotLink_t * pCurrent = pList->pNext; /* Iterate through the list to find the correct position. */ while( pCurrent != pList ) { /* Comparing for '<' preserves the order of insertion. */ if( compare( pLink, pCurrent ) < 0 ) { IotListDouble_InsertBefore( pCurrent, pLink ); inserted = true; break; } pCurrent = pCurrent->pNext; } /* New element is greater than all elements in list. Insert at tail. */ if( inserted == false ) { IotListDouble_InsertTail( pList, pLink ); } } } /** * @brief Remove a single element from a doubly-linked list. * * @param[in] pLink The element to remove. */ /* @[declare_linear_containers_list_double_remove] */ static inline void IotListDouble_Remove( IotLink_t * const pLink ) /* @[declare_linear_containers_list_double_remove] */ { /* This function must not be called with a NULL parameter. */ IotContainers_Assert( pLink != NULL ); /* This function must be called on a linked element. */ IotContainers_Assert( IotLink_IsLinked( pLink ) == true ); pLink->pPrevious->pNext = pLink->pNext; pLink->pNext->pPrevious = pLink->pPrevious; pLink->pPrevious = NULL; pLink->pNext = NULL; } /** * @brief Remove the element at the head of a doubly-linked list. * * @param[in] pList The doubly-linked list that holds the element to remove. * * @return Pointer to an #IotLink_t representing the removed list head; `NULL` * if the list is empty. The macro #IotLink_Container may be used to determine * the address of the link's container. */ /* @[declare_linear_containers_list_double_removehead] */ static inline IotLink_t * IotListDouble_RemoveHead( IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_removehead] */ { IotLink_t * pHead = NULL; if( IotListDouble_IsEmpty( pList ) == false ) { pHead = pList->pNext; IotListDouble_Remove( pHead ); } return pHead; } /** * @brief Remove the element at the tail of a doubly-linked list. * * @param[in] pList The doubly-linked list that holds the element to remove. * * @return Pointer to an #IotLink_t representing the removed list tail; `NULL` * if the list is empty. The macro #IotLink_Container may be used to determine * the address of the link's container. */ /* @[declare_linear_containers_list_double_removetail] */ static inline IotLink_t * IotListDouble_RemoveTail( IotListDouble_t * const pList ) /* @[declare_linear_containers_list_double_removetail] */ { IotLink_t * pTail = NULL; if( IotListDouble_IsEmpty( pList ) == false ) { pTail = pList->pPrevious; IotListDouble_Remove( pTail ); } return pTail; } /** * @brief Remove all elements in a doubly-linked list. * * @param[in] pList The list to empty. * @param[in] freeElement A function to free memory used by each removed list * element. Optional; pass `NULL` to ignore. * @param[in] linkOffset Offset in bytes of a link member in its container, used * to calculate the pointer to pass to `freeElement`. This value should be calculated * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL` * or its value is `0`. */ /* @[declare_linear_containers_list_double_removeall] */ static inline void IotListDouble_RemoveAll( IotListDouble_t * const pList, void ( * freeElement )( void * ), size_t linkOffset ) /* @[declare_linear_containers_list_double_removeall] */ { /* This function must not be called with a NULL pList parameter. */ IotContainers_Assert( pList != NULL ); /* Get the list head. */ IotLink_t * pCurrent = pList->pNext; /* Iterate through the list and remove all elements. */ while( pCurrent != pList ) { /* Save a pointer to the next list element. */ IotLink_t * pNext = pCurrent->pNext; /* Remove and free the current list element. */ IotListDouble_Remove( pCurrent ); if( freeElement != NULL ) { freeElement( ( ( uint8_t * ) pCurrent ) - linkOffset ); } /* Move the iterating pointer to the next list element. */ pCurrent = pNext; } } /** * @brief Search a doubly-linked list for the first matching element. * * If a match is found, the matching element is not removed from the list. * See @ref linear_containers_function_list_double_removefirstmatch for the function * that searches and removes. * * @param[in] pList The doubly-linked list to search. * @param[in] pStartPoint An element in `pList`. Only elements between this one and * the list tail are checked. Pass `NULL` to search from the beginning of the list. * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to * search using the address `pMatch`, i.e. `element == pMatch`. * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared * to this address to find a match. Otherwise, it is passed as the second argument * to `isMatch`. * * @return Pointer to an #IotLink_t representing the first matched element; `NULL` * if no match is found. The macro #IotLink_Container may be used to determine the * address of the link's container. */ /* @[declare_linear_containers_list_double_findfirstmatch] */ static inline IotLink_t * IotListDouble_FindFirstMatch( const IotListDouble_t * const pList, const IotLink_t * const pStartPoint, bool ( * isMatch )( const IotLink_t * const, void * ), void * pMatch ) /* @[declare_linear_containers_list_double_findfirstmatch] */ { /* The const must be cast away to match this function's return value. Nevertheless, * this function will respect the const-ness of pStartPoint. */ IotLink_t * pCurrent = ( IotLink_t * ) pStartPoint; /* This function must not be called with a NULL pList parameter. */ IotContainers_Assert( pList != NULL ); /* Search starting from list head if no start point is given. */ if( pStartPoint == NULL ) { pCurrent = pList->pNext; } /* Iterate through the list to search for matches. */ while( pCurrent != pList ) { /* Call isMatch if provided. Otherwise, compare pointers. */ if( isMatch != NULL ) { if( isMatch( pCurrent, pMatch ) == true ) { return pCurrent; } } else { if( pCurrent == pMatch ) { return pCurrent; } } pCurrent = pCurrent->pNext; } /* No match found, return NULL. */ return NULL; } /** * @brief Search a doubly-linked list for the first matching element and remove * it. * * An #IotLink_t may be passed as `pList` to start searching after the head of a * doubly-linked list. * * @param[in] pList The doubly-linked list to search. * @param[in] pStartPoint An element in `pList`. Only elements between this one and * the list tail are checked. Pass `NULL` to search from the beginning of the list. * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to * search using the address `pMatch`, i.e. `element == pMatch`. * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared * to this address to find a match. Otherwise, it is passed as the second argument * to `isMatch`. * * @return Pointer to an #IotLink_t representing the matched and removed element; * `NULL` if no match is found. The macro #IotLink_Container may be used to determine * the address of the link's container. */ /* @[declare_linear_containers_list_double_removefirstmatch] */ static inline IotLink_t * IotListDouble_RemoveFirstMatch( IotListDouble_t * const pList, const IotLink_t * const pStartPoint, bool ( * isMatch )( const IotLink_t *, void * ), void * pMatch ) /* @[declare_linear_containers_list_double_removefirstmatch] */ { IotLink_t * pMatchedElement = IotListDouble_FindFirstMatch( pList, pStartPoint, isMatch, pMatch ); if( pMatchedElement != NULL ) { IotListDouble_Remove( pMatchedElement ); } return pMatchedElement; } /** * @brief Remove all matching elements from a doubly-linked list. * * @param[in] pList The doubly-linked list to search. * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to * search using the address `pMatch`, i.e. `element == pMatch`. * @param[in] pMatch If `isMatch` is `NULL`, each element in the list is compared * to this address to find a match. Otherwise, it is passed as the second argument * to `isMatch`. * @param[in] freeElement A function to free memory used by each removed list * element. Optional; pass `NULL` to ignore. * @param[in] linkOffset Offset in bytes of a link member in its container, used * to calculate the pointer to pass to `freeElement`. This value should be calculated * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL` * or its value is `0`. */ /* @[declare_linear_containers_list_double_removeallmatches] */ static inline void IotListDouble_RemoveAllMatches( IotListDouble_t * const pList, bool ( * isMatch )( const IotLink_t *, void * ), void * pMatch, void ( * freeElement )( void * ), size_t linkOffset ) /* @[declare_linear_containers_list_double_removeallmatches] */ { IotLink_t * pMatchedElement = NULL, * pNextElement = NULL; /* Search the list for all matching elements. */ do { pMatchedElement = IotListDouble_FindFirstMatch( pList, pMatchedElement, isMatch, pMatch ); if( pMatchedElement != NULL ) { /* Save pointer to next element. */ pNextElement = pMatchedElement->pNext; /* Match found; remove and free. */ IotListDouble_Remove( pMatchedElement ); if( freeElement != NULL ) { freeElement( ( ( uint8_t * ) pMatchedElement ) - linkOffset ); } /* Continue search from next element. */ pMatchedElement = pNextElement; } } while( pMatchedElement != NULL ); } /** * @brief Create a new queue. * * This function initializes a new double-ended queue. It must be called on an uninitialized * #IotDeQueue_t before calling any other queue function. This function must not be * called on an already-initialized #IotDeQueue_t. * * This function will not fail. * * @param[in] pQueue Pointer to the memory that will hold the new queue. */ /* @[declare_linear_containers_queue_create] */ static inline void IotDeQueue_Create( IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_create] */ { IotListDouble_Create( pQueue ); } /** * @brief Return the number of elements contained in an #IotDeQueue_t. * * @param[in] pQueue The queue with the elements to count. * * @return The number of items elements in the queue. */ /* @[declare_linear_containers_queue_count] */ static inline size_t IotDeQueue_Count( const IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_count] */ { return IotListDouble_Count( pQueue ); } /** * @brief Check if a queue is empty. * * @param[in] pQueue The queue to check. * * @return `true` if the queue is empty; `false` otherwise. * */ /* @[declare_linear_containers_queue_isempty] */ static inline bool IotDeQueue_IsEmpty( const IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_isempty] */ { return IotListDouble_IsEmpty( pQueue ); } /** * @brief Return an #IotLink_t representing the element at the front of the queue * without removing it. * * @param[in] pQueue The queue to peek. * * @return Pointer to an #IotLink_t representing the element at the head of the * queue; `NULL` if the queue is empty. The macro #IotLink_Container may be used * to determine the address of the link's container. */ /* @[declare_linear_containers_queue_peekhead] */ static inline IotLink_t * IotDeQueue_PeekHead( const IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_peekhead] */ { return IotListDouble_PeekHead( pQueue ); } /** * @brief Return an #IotLink_t representing the element at the back of the queue * without removing it. * * @param[in] pQueue The queue to peek. * * @return Pointer to an #IotLink_t representing the element at the head of the * queue; `NULL` if the queue is empty. The macro #IotLink_Container may be used * to determine the address of the link's container. */ /* @[declare_linear_containers_queue_peektail] */ static inline IotLink_t * IotDeQueue_PeekTail( const IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_peektail] */ { return IotListDouble_PeekTail( pQueue ); } /** * @brief Add an element at the head of the queue. * * @param[in] pQueue The queue that will hold the new element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_queue_enqueuehead] */ static inline void IotDeQueue_EnqueueHead( IotDeQueue_t * const pQueue, IotLink_t * const pLink ) /* @[declare_linear_containers_queue_enqueuehead] */ { IotListDouble_InsertHead( pQueue, pLink ); } /** * @brief Remove an element at the head of the queue. * * @param[in] pQueue The queue that holds the element to remove. * * @return Pointer to an #IotLink_t representing the removed queue element; `NULL` * if the queue is empty. The macro #IotLink_Container may be used to determine * the address of the link's container. */ /* @[declare_linear_containers_queue_dequeuehead] */ static inline IotLink_t * IotDeQueue_DequeueHead( IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_dequeuehead] */ { return IotListDouble_RemoveHead( pQueue ); } /** * @brief Add an element at the tail of the queue. * * @param[in] pQueue The queue that will hold the new element. * @param[in] pLink Pointer to the new element's link member. */ /* @[declare_linear_containers_queue_enqueuetail] */ static inline void IotDeQueue_EnqueueTail( IotDeQueue_t * const pQueue, IotLink_t * const pLink ) /* @[declare_linear_containers_queue_enqueuetail] */ { IotListDouble_InsertTail( pQueue, pLink ); } /** * @brief Remove an element at the tail of the queue. * * @param[in] pQueue The queue that holds the element to remove. * * @return Pointer to an #IotLink_t representing the removed queue element; `NULL` * if the queue is empty. The macro #IotLink_Container may be used to determine * the address of the link's container. */ /* @[declare_linear_containers_queue_dequeuetail] */ static inline IotLink_t * IotDeQueue_DequeueTail( IotDeQueue_t * const pQueue ) /* @[declare_linear_containers_queue_dequeuetail] */ { return IotListDouble_RemoveTail( pQueue ); } /** * @brief Remove a single element from a queue. * * @param[in] pLink The element to remove. */ /* @[declare_linear_containers_queue_remove] */ static inline void IotDeQueue_Remove( IotLink_t * const pLink ) /* @[declare_linear_containers_queue_remove] */ { IotListDouble_Remove( pLink ); } /** * @brief Remove all elements in a queue. * * @param[in] pQueue The queue to empty. * @param[in] freeElement A function to free memory used by each removed queue * element. Optional; pass `NULL` to ignore. * @param[in] linkOffset Offset in bytes of a link member in its container, used * to calculate the pointer to pass to `freeElement`. This value should be calculated * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL` * or its value is `0`. */ /* @[declare_linear_containers_queue_removeall] */ static inline void IotDeQueue_RemoveAll( IotDeQueue_t * const pQueue, void ( * freeElement )( void * ), size_t linkOffset ) /* @[declare_linear_containers_queue_removeall] */ { IotListDouble_RemoveAll( pQueue, freeElement, linkOffset ); } /** * @brief Remove all matching elements from a queue. * * @param[in] pQueue The queue to search. * @param[in] isMatch Function to determine if an element matches. Pass `NULL` to * search using the address `pMatch`, i.e. `element == pMatch`. * @param[in] pMatch If `isMatch` is `NULL`, each element in the queue is compared * to this address to find a match. Otherwise, it is passed as the second argument * to `isMatch`. * @param[in] freeElement A function to free memory used by each removed queue * element. Optional; pass `NULL` to ignore. * @param[in] linkOffset Offset in bytes of a link member in its container, used * to calculate the pointer to pass to `freeElement`. This value should be calculated * with the C `offsetof` macro. This parameter is ignored if `freeElement` is `NULL` * or its value is `0`. */ /* @[declare_linear_containers_queue_removeallmatches] */ static inline void IotDeQueue_RemoveAllMatches( IotDeQueue_t * const pQueue, bool ( * isMatch )( const IotLink_t *, void * ), void * pMatch, void ( * freeElement )( void * ), size_t linkOffset ) /* @[declare_linear_containers_queue_removeallmatches] */ { IotListDouble_RemoveAllMatches( pQueue, isMatch, pMatch, freeElement, linkOffset ); } #endif /* IOT_LINEAR_CONTAINERS_H_ */