/*
 * Amazon FreeRTOS Common V1.0.0
 * Copyright (C) 2018 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_doubly_linked_list.h
 * @brief Doubly Linked List implementation.
 *
 * A generic implementation of circular Doubly Linked List which consists of a
 * list head and some list entries (zero in case of an empty list).
 *
 * To start with, a structure of type Link_t should be embedded in the structure
 * which is to be organized as doubly linked list.
 * @code
 * typedef struct UserStruct
 * {
 *     uint32_t ulField1;
 *     uint32_t ulField2;
 *     Link_t xLink;
 * } UserStruct_t;
 * @endcode
 *
 * A List head should then be defined and initialized.
 * @code
 * Link_t xListHead;
 * listINIT_HEAD( &xListHead );
 * @endcode
 *
 * listADD can then be used to add nodes to the list.
 * @code
 * listADD( &( xListHead ), &( pxUserStruct->xLink ) );
 * @endcode
 *
 * listFOR_EACH can be used for traversing the list.
 * @code
 * Link_t *pxLink;
 * UserStruct_t *pxUserStruct;
 * listFOR_EACH( pxLink, &( xListHead ) )
 * {
 *      pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink );
 * }
 * @endcode
 *
 * listFOR_EACH_SAFE should be used if you want to perform destructive operations
 * (like free) on nodes while traversing the list.
 * @code
 * Link_t *pxLink, *pxTempLink;
 * UserStruct_t *pxUserStruct;
 * listFOR_EACH( pxLink, pxTempLink, &( xListHead ) )
 * {
 *      pxUserStruct = listCONTAINER( pxLink, UserStruct_t, xLink );
 *      free( pxUserStruct );
 * }
 * @endcode
 */

#ifndef _AWS_DOUBLY_LINKED_LIST_H_
#define _AWS_DOUBLY_LINKED_LIST_H_

#include <stddef.h>
#include <stdint.h>

/**
 * @brief Struct embedded in any struct to make it a doubly linked
 * list.
 *
 * pxNext in the head points to the first node in the list and pxPrev
 * in the head points to the last node in the list. In case of empty
 * list, both pxPrev and pxNext in the head point to the head node itself.
 */
typedef struct Link
{
    struct Link * pxPrev; /**< Pointer to the previous node. */
    struct Link * pxNext; /**< Pointer to the next node. */
} Link_t;

/**
 * @brief Initializes the given list head to an empty list.
 *
 * @param[in] pxHead The given list head to initialize.
 */
#define listINIT_HEAD( pxHead )          \
    {                                    \
        ( pxHead )->pxPrev = ( pxHead ); \
        ( pxHead )->pxNext = ( pxHead ); \
    }

/**
 * @brief Adds the given new node to the given list.
 *
 * @param[in] pxHead The head of the given list.
 * @param[in] pxLink The given new node to be added to the given
 * list.
 */
#define listADD( pxHead, pxLink )                     \
    {                                                 \
        Link_t * pxPrevLink = ( pxHead );             \
        Link_t * pxNextLink = ( ( pxHead )->pxNext ); \
                                                      \
        ( pxLink )->pxNext = pxNextLink;              \
        pxNextLink->pxPrev = ( pxLink );              \
        pxPrevLink->pxNext = ( pxLink );              \
        ( pxLink )->pxPrev = ( pxPrevLink );          \
    }

/**
 * @brief Removes the given node from the list it is part of.
 *
 * If the given node is not a part of any list (i.e. next and previous
 * nodes are NULL), nothing happens.
 *
 * @param[in] pxLink The given node to remove from the list.
 */
#define listREMOVE( pxLink )                                            \
    {                                                                   \
        /* If the link is part of a list, remove it from the list. */   \
        if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL )  \
        {                                                               \
            ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext;            \
            ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev;            \
        }                                                               \
                                                                        \
        /* Make sure that this link is not part of any list anymore. */ \
        ( pxLink )->pxPrev = NULL;                                      \
        ( pxLink )->pxNext = NULL;                                      \
    }

/**
 * @brief Given the head of a list, checks if the list is empty.
 *
 * @param[in] pxHead The head of the given list.
 */
#define listIS_EMPTY( pxHead )    ( ( ( pxHead ) == NULL ) || ( ( pxHead )->pxNext == ( pxHead ) ) )

/**
 * @brief Removes the first node from the given list and returns it.
 *
 * Removes the first node from the given list and assigns it to the
 * pxLink parameter. If the list is empty, it assigns NULL to the
 * pxLink.
 *
 * @param[in] pxHead The head of the list from which to remove the
 * first node.
 * @param[out] pxLink The output parameter to receive the removed
 * node.
 */
#define listPOP( pxHead, pxLink )                                           \
    {                                                                       \
        if( listIS_EMPTY( ( pxHead ) ) )                                    \
        {                                                                   \
            ( pxLink ) = NULL;                                              \
        }                                                                   \
        else                                                                \
        {                                                                   \
            ( pxLink ) = ( pxHead )->pxNext;                                \
            /* If the link is part of a list, remove it from the list. */   \
            if( ( pxLink )->pxNext != NULL && ( pxLink )->pxPrev != NULL )  \
            {                                                               \
                ( pxLink )->pxPrev->pxNext = ( pxLink )->pxNext;            \
                ( pxLink )->pxNext->pxPrev = ( pxLink )->pxPrev;            \
            }                                                               \
                                                                            \
            /* Make sure that this link is not part of any list anymore. */ \
            ( pxLink )->pxPrev = NULL;                                      \
            ( pxLink )->pxNext = NULL;                                      \
        }                                                                   \
    }

/**
 * @brief Merges a list into a given list.
 *
 * @param[in] pxHeadResultList The head of the given list into which the
 * other list should be merged.
 * @param[in] pxHeadListToMerge The head of the list to be merged into the
 * given list.
 */
#define listMERGE( pxHeadResultList, pxHeadListToMerge )                                     \
    {                                                                                        \
        if( !listIS_EMPTY( ( pxHeadListToMerge ) ) )                                         \
        {                                                                                    \
            /* Setup links between last node of listToMerge and first node of resultList. */ \
            ( pxHeadListToMerge )->pxPrev->pxNext = ( pxHeadResultList )->pxNext;            \
            ( pxHeadResultList )->pxNext->pxPrev = ( pxHeadListToMerge )->pxPrev;            \
                                                                                             \
            /* Setup links between first node of listToMerge and the head of resultList. */  \
            ( pxHeadListToMerge )->pxNext->pxPrev = ( pxHeadResultList );                    \
            ( pxHeadResultList )->pxNext = ( pxHeadListToMerge )->pxNext;                    \
            /* Empty the merged list. */                                                     \
            listINIT_HEAD( ( pxHeadListToMerge ) );                                          \
        }                                                                                    \
    }

/**
 * @brief Helper macro to iterate over a list. pxLink contains the link node
 * in each iteration.
 */
#define listFOR_EACH( pxLink, pxHead )    \
    for( ( pxLink ) = ( pxHead )->pxNext; \
         ( pxLink ) != ( pxHead );        \
         ( pxLink ) = ( pxLink )->pxNext )

/**
 * @brief Helper macro to iterate over a list. It is safe to destroy/free the
 * nodes while iterating. pxLink contains the link node in each iteration.
 */
#define listFOR_EACH_SAFE( pxLink, pxTempLink, pxHead )                        \
    for( ( pxLink ) = ( pxHead )->pxNext, ( pxTempLink ) = ( pxLink )->pxNext; \
         ( pxLink ) != ( pxHead );                                             \
         ( pxLink ) = ( pxTempLink ), ( pxTempLink ) = ( pxLink )->pxNext )

/**
 * @brief Given the pointer to the link member (of type Link_t) in a struct,
 * extracts the pointer to the containing struct.
 *
 * @param[in] pxLink The pointer to the link member.
 * @param[in] type The type of the containing struct.
 * @param[in] member Name of the link member in the containing struct.
 */
#define listCONTAINER( pxLink, type, member )    ( ( type * ) ( ( uint8_t * ) ( pxLink ) - ( uint8_t * ) ( &( ( type * ) 0 )->member ) ) )

#endif /* _AWS_DOUBLY_LINKED_LIST_H_ */