/*
 * FreeRTOS Common V1.1.1
 * 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_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 <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/**
 * @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 <assert.h>
        #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 <b>not</b> 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_ */
