/*
 * FreeRTOS Kernel V10.5.1
 * Copyright (C) 2021 Amazon.com, Inc. or its affiliates.  All Rights Reserved.
 *
 * SPDX-License-Identifier: MIT
 *
 * 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.
 *
 * https://www.FreeRTOS.org
 * https://github.com/FreeRTOS
 *
 */

/*
 * This is the list implementation used by the scheduler.  While it is tailored
 * heavily for the schedulers needs, it is also available for use by
 * application code.
 *
 * list_ts can only store pointers to list_item_ts.  Each ListItem_t contains a
 * numeric value (xItemValue).  Most of the time the lists are sorted in
 * ascending item value order.
 *
 * Lists are created already containing one list item.  The value of this
 * item is the maximum possible that can be stored, it is therefore always at
 * the end of the list and acts as a marker.  The list member pxHead always
 * points to this marker - even though it is at the tail of the list.  This
 * is because the tail contains a wrap back pointer to the true head of
 * the list.
 *
 * In addition to it's value, each list item contains a pointer to the next
 * item in the list (pxNext), a pointer to the list it is in (pxContainer)
 * and a pointer to back to the object that contains it.  These later two
 * pointers are included for efficiency of list manipulation.  There is
 * effectively a two way link between the object containing the list item and
 * the list item itself.
 *
 *
 * \page ListIntroduction List Implementation
 * \ingroup FreeRTOSIntro
 */


#ifndef LIST_H
#define LIST_H

#ifndef INC_FREERTOS_H
    #error "FreeRTOS.h must be included before list.h"
#endif

/*
 * The list structure members are modified from within interrupts, and therefore
 * by rights should be declared volatile.  However, they are only modified in a
 * functionally atomic way (within critical sections of with the scheduler
 * suspended) and are either passed by reference into a function or indexed via
 * a volatile variable.  Therefore, in all use cases tested so far, the volatile
 * qualifier can be omitted in order to provide a moderate performance
 * improvement without adversely affecting functional behaviour.  The assembly
 * instructions generated by the IAR, ARM and GCC compilers when the respective
 * compiler's options were set for maximum optimisation has been inspected and
 * deemed to be as intended.  That said, as compiler technology advances, and
 * especially if aggressive cross module optimisation is used (a use case that
 * has not been exercised to any great extend) then it is feasible that the
 * volatile qualifier will be needed for correct optimisation.  It is expected
 * that a compiler removing essential code because, without the volatile
 * qualifier on the list structure members and with aggressive cross module
 * optimisation, the compiler deemed the code unnecessary will result in
 * complete and obvious failure of the scheduler.  If this is ever experienced
 * then the volatile qualifier can be inserted in the relevant places within the
 * list structures by simply defining configLIST_VOLATILE to volatile in
 * FreeRTOSConfig.h (as per the example at the bottom of this comment block).
 * If configLIST_VOLATILE is not defined then the preprocessor directives below
 * will simply #define configLIST_VOLATILE away completely.
 *
 * To use volatile list structure members then add the following line to
 * FreeRTOSConfig.h (without the quotes):
 * "#define configLIST_VOLATILE volatile"
 */
#ifndef configLIST_VOLATILE
    #define configLIST_VOLATILE
#endif /* configSUPPORT_CROSS_MODULE_OPTIMISATION */

/* Macros that can be used to place known values within the list structures,
 * then check that the known values do not get corrupted during the execution of
 * the application.   These may catch the list data structures being overwritten in
 * memory.  They will not catch data errors caused by incorrect configuration or
 * use of FreeRTOS.*/
#if (configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0)
    /* Define the macros to do nothing. */
    #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
    #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
    #define listFIRST_LIST_INTEGRITY_CHECK_VALUE
    #define listSECOND_LIST_INTEGRITY_CHECK_VALUE
    #define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)
    #define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)
    #define listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList)
    #define listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList)
    #define listTEST_LIST_ITEM_INTEGRITY(pxItem)
    #define listTEST_LIST_INTEGRITY(pxList)
#else /* if ( configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES == 0 ) */
    /* Define macros that add new members into the list structures. */
    #define listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE     TickType_t xListItemIntegrityValue1;
    #define listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE    TickType_t xListItemIntegrityValue2;
    #define listFIRST_LIST_INTEGRITY_CHECK_VALUE          TickType_t xListIntegrityValue1;
    #define listSECOND_LIST_INTEGRITY_CHECK_VALUE         TickType_t xListIntegrityValue2;

/* Define macros that set the new structure members to known values. */
    #define listSET_FIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)     (pxItem)->xListItemIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
    #define listSET_SECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE(pxItem)    (pxItem)->xListItemIntegrityValue2 = pdINTEGRITY_CHECK_VALUE
    #define listSET_LIST_INTEGRITY_CHECK_1_VALUE(pxList)              (pxList)->xListIntegrityValue1 = pdINTEGRITY_CHECK_VALUE
    #define listSET_LIST_INTEGRITY_CHECK_2_VALUE(pxList)              (pxList)->xListIntegrityValue2 = pdINTEGRITY_CHECK_VALUE

/* Define macros that will assert if one of the structure members does not
 * contain its expected value. */
#define listTEST_LIST_ITEM_INTEGRITY(pxItem)    \
    configASSERT(((pxItem)->xListItemIntegrityValue1 == pdINTEGRITY_CHECK_VALUE) && ((pxItem)->xListItemIntegrityValue2 == pdINTEGRITY_CHECK_VALUE))
#define listTEST_LIST_INTEGRITY(pxList)          \
    configASSERT(((pxList)->xListIntegrityValue1 == pdINTEGRITY_CHECK_VALUE) && ((pxList)->xListIntegrityValue2 == pdINTEGRITY_CHECK_VALUE))
#endif /* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES */


/*
 * Definition of the only type of object that a list can contain.
 */
struct xLIST;

/* 双向链表节点管理结构 */
struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /* */
    configLIST_VOLATILE TickType_t xItemValue;          /* 有序链表的键值 */
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /* 后继节点 */
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 前驱节点 */
    void * pvOwner;                                     /* 保存私有数据 */
    struct xLIST * configLIST_VOLATILE pxContainer;     /* 节点所在的链表 */
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE          /* */
};
typedef struct xLIST_ITEM ListItem_t;

#if (configUSE_MINI_LIST_ITEM == 1)
/* 不带有私有数据的双向链表节点 */
struct xMINI_LIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE           /* */
    configLIST_VOLATILE TickType_t xItemValue;          /* 有序链表的键值 */
    struct xLIST_ITEM * configLIST_VOLATILE pxNext;     /* 后继节点 */
    struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /* 前驱节点 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
#else
    typedef struct xLIST_ITEM      MiniListItem_t;
#endif

/*
 * Definition of the type of queue used by the scheduler.
 */
typedef struct xLIST
{
    listFIRST_LIST_INTEGRITY_CHECK_VALUE        /**/
    volatile UBaseType_t uxNumberOfItems;       /* 链表中元素的个数 */
    ListItem_t * configLIST_VOLATILE pxIndex;
    MiniListItem_t xListEnd;                    /* 双向链表的尾节点(哨兵) */
    listSECOND_LIST_INTEGRITY_CHECK_VALUE       /**/
} List_t;

/*
 * pxListItem->pvOwner = pxOwner
 */
#define listSET_LIST_ITEM_OWNER(pxListItem, pxOwner)    ((pxListItem)->pvOwner = (void *)(pxOwner))

/*
 *  返回 pxListItem->pvOwner
 */
#define listGET_LIST_ITEM_OWNER(pxListItem)             ((pxListItem )->pvOwner)

/*
 * pxListItem->xItemValue = xValue
 */
#define listSET_LIST_ITEM_VALUE(pxListItem, xValue)     ((pxListItem)->xItemValue = (xValue))

/*
 * 返回 pxListItem->xItemValue
 */
#define listGET_LIST_ITEM_VALUE(pxListItem)             ((pxListItem)->xItemValue)

/*
 * 返回链表头节点的xItemValue
 */
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY(pxList)        (((pxList)->xListEnd).pxNext->xItemValue)

/*
 * 返回链表头结点
 */
#define listGET_HEAD_ENTRY(pxList)                      (((pxList)->xListEnd).pxNext)

/*
 * 返回pxListItem后继节点
 */
#define listGET_NEXT(pxListItem)                        ((pxListItem)->pxNext)

/*
 * 返回链表的尾部节点(哨兵节点)
 */
#define listGET_END_MARKER(pxList)                      ((ListItem_t const *) (&((pxList)->xListEnd)))

/*
 * 链表是否为空
 */
#define listLIST_IS_EMPTY(pxList)                       (((pxList)->uxNumberOfItems == (UBaseType_t)0) ? pdTRUE : pdFALSE)

/*
 * 返回链表中的元素个数
 */
#define listCURRENT_LIST_LENGTH(pxList)                 ((pxList)->uxNumberOfItems)

/*
 * Access function to obtain the owner of the next entry in a list.
 *
 * The list member pxIndex is used to walk through a list.  Calling
 * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list
 * and returns that entry's pxOwner parameter.  Using multiple calls to this
 * function it is therefore possible to move through every item contained in
 * a list.
 *
 * The pxOwner parameter of a list item is a pointer to the object that owns
 * the list item.  In the scheduler this is normally a task control block.
 * The pxOwner parameter effectively creates a two way link between the list
 * item and its owner.
 *
 * @param pxTCB pxTCB is set to the address of the owner of the next list item.
 * @param pxList The list from which the next item owner is to be returned.
 *
 * \page listGET_OWNER_OF_NEXT_ENTRY listGET_OWNER_OF_NEXT_ENTRY
 * \ingroup LinkedList
 */
#define listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList)                                         \
    {                                                                                      \
        List_t * const pxConstList = (pxList);                                             \
        /* Increment the index to the next item and return the item, ensuring */           \
        /* we don't return the marker used at the end of the list.  */                     \
        (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext;                           \
        if ((void *)(pxConstList)->pxIndex == (void *) &((pxConstList )->xListEnd))         \
        {                                                                                  \
            (pxConstList)->pxIndex = (pxConstList)->pxIndex->pxNext;                       \
        }                                                                                  \
        (pxTCB) = (pxConstList)->pxIndex->pvOwner;                                         \
    }

/*
 * 删除pxItemToRemove节点
 */
#define listREMOVE_ITEM(pxItemToRemove)                                             \
    {                                                                               \
        /* The list item knows which list it is in.  Obtain the list from the list  \
         * item. */                                                                 \
        List_t * const pxList = (pxItemToRemove)->pxContainer;                      \
                                                                                    \
        (pxItemToRemove)->pxNext->pxPrevious = (pxItemToRemove)->pxPrevious;        \
        (pxItemToRemove)->pxPrevious->pxNext = (pxItemToRemove)->pxNext;            \
        /* Make sure the index is left pointing to a valid item. */                 \
        if (pxList->pxIndex == (pxItemToRemove))                                     \
        {                                                                           \
            pxList->pxIndex = (pxItemToRemove)->pxPrevious;                         \
        }                                                                           \
                                                                                    \
        (pxItemToRemove)->pxContainer = NULL;                                       \
        (pxList->uxNumberOfItems)--;                                                \
    }

/*
 * pxNewListItem插入链表尾部
 */
#define listINSERT_END(pxList, pxNewListItem)                                         \
    {                                                                                 \
        ListItem_t * const pxIndex = (pxList)->pxIndex;                               \
                                                                                      \
        /* Only effective when configASSERT() is also defined, these tests may catch  \
         * the list data structures being overwritten in memory.  They will not catch \
         * data errors caused by incorrect configuration or use of FreeRTOS. */       \
        listTEST_LIST_INTEGRITY((pxList));                                            \
        listTEST_LIST_ITEM_INTEGRITY((pxNewListItem));                                \
                                                                                      \
        /* Insert a new list item into ( pxList ), but rather than sort the list,     \
         * makes the new list item the last item to be removed by a call to           \
         * listGET_OWNER_OF_NEXT_ENTRY(). */                                          \
        (pxNewListItem)->pxNext = pxIndex;                                            \
        (pxNewListItem)->pxPrevious = pxIndex->pxPrevious;                            \
                                                                                      \
        pxIndex->pxPrevious->pxNext = (pxNewListItem);                                \
        pxIndex->pxPrevious = (pxNewListItem);                                        \
                                                                                      \
        /* Remember which list the item is in. */                                     \
        (pxNewListItem)->pxContainer = (pxList);                                      \
                                                                                      \
        ((pxList)->uxNumberOfItems)++;                                                \
    }

/*
 * 返回头结点的pvOwner
 */
#define listGET_OWNER_OF_HEAD_ENTRY(pxList)            ((&((pxList)->xListEnd))->pxNext->pvOwner)

/*
 * pxListItem节点是否在pxList链表中
 */
#define listIS_CONTAINED_WITHIN(pxList, pxListItem)    (((pxListItem)->pxContainer == (pxList)) ? (pdTRUE) : (pdFALSE))

/*
 * 返回pxListItem节点所在的链表
 */
#define listLIST_ITEM_CONTAINER(pxListItem)            ((pxListItem)->pxContainer)

/*
 * pxList链表是否初始化
 */
#define listLIST_IS_INITIALISED(pxList)                ((pxList)->xListEnd.xItemValue == portMAX_DELAY)

/*
 * Must be called before a list is used!  This initialises all the members
 * of the list structure and inserts the xListEnd item into the list as a
 * marker to the back of the list.
 *
 * @param pxList Pointer to the list being initialised.
 *
 */
void vListInitialise(List_t * const pxList) PRIVILEGED_FUNCTION;

/*
 * Must be called before a list item is used.  This sets the list container to
 * null so the item does not think that it is already contained in a list.
 *
 * @param pxItem Pointer to the list item being initialised.
 *
 * \page vListInitialiseItem vListInitialiseItem
 * \ingroup LinkedList
 */
void vListInitialiseItem(ListItem_t * const pxItem) PRIVILEGED_FUNCTION;

/*
 * Insert a list item into a list.  The item will be inserted into the list in
 * a position determined by its item value (ascending item value order).
 *
 * @param pxList The list into which the item is to be inserted.
 *
 * @param pxNewListItem The item that is to be placed in the list.
 *
 * \page vListInsert vListInsert
 * \ingroup LinkedList
 */
void vListInsert(List_t * const pxList,
                  ListItem_t * const pxNewListItem) PRIVILEGED_FUNCTION;

/*
 * Insert a list item into a list.  The item will be inserted in a position
 * such that it will be the last item within the list returned by multiple
 * calls to listGET_OWNER_OF_NEXT_ENTRY.
 *
 * The list member pxIndex is used to walk through a list.  Calling
 * listGET_OWNER_OF_NEXT_ENTRY increments pxIndex to the next item in the list.
 * Placing an item in a list using vListInsertEnd effectively places the item
 * in the list position pointed to by pxIndex.  This means that every other
 * item within the list will be returned by listGET_OWNER_OF_NEXT_ENTRY before
 * the pxIndex parameter again points to the item being inserted.
 *
 * @param pxList The list into which the item is to be inserted.
 *
 * @param pxNewListItem The list item to be inserted into the list.
 *
 * \page vListInsertEnd vListInsertEnd
 * \ingroup LinkedList
 */
void vListInsertEnd(List_t * const pxList,
                     ListItem_t * const pxNewListItem) PRIVILEGED_FUNCTION;

/*
 * Remove an item from a list.  The list item has a pointer to the list that
 * it is in, so only the list item need be passed into the function.
 *
 * @param uxListRemove The item to be removed.  The item will remove itself from
 * the list pointed to by it's pxContainer parameter.
 *
 * @return The number of items that remain in the list after the list item has
 * been removed.
 *
 * \page uxListRemove uxListRemove
 * \ingroup LinkedList
 */
UBaseType_t uxListRemove(ListItem_t * const pxItemToRemove) PRIVILEGED_FUNCTION;

#endif /* ifndef LIST_H */