/*******************************************************************************
** 文件名称：GM_LinkedList.c
** 文件作用：链表通用操作源文件
** 编写作者：Tom Free 付瑞彪
** 编写时间：2018-08-25
** 文件备注：
**          1、通用链表操作，双向循环链表，头节点为管理节点，不存放用户数据，仅提供给链表
**             管理器使用
**          2、提供动态链表管理器创建，可以使用 GM_LinkedList_Create 函数进行创建，如
**             不需动态创建可直接采用静态或全局变量创建，也可用户自己采用动态内存进行创建
**          3、用户必需将 GM_LinkedListNode 型的一个变量放入结构体起始处来构建链表管理
**             数据，不可放置在结构体其它地方，本文件未提供相关函数或宏来进行索引
**
**          Note:若要查看相关帮助或例程请参考此文件夹下的ReadMe.md文件
**
** 更新记录：
**          2018-08-25 -> 创建文件                                   <Tom Free>
**          2018-08-30 -> 架构重新布局，采用更好的管理方式              <Tom Free>
**
**          1 Tab == 4 Spaces     UTF-8     ANSI C Language
*******************************************************************************/

/* 链表头文件 */
#include "gm_list.h"

/* 内存管理头文件 */
#include "./GM_Memory/gm_mem.h"

/* 链表节点数据结构类型定义 */
typedef struct _GM_LIST_NODE GM_LIST_NODE;

/* 链表节点数据结构定义 */
struct _GM_LIST_NODE
{
    GM_LIST_NODE *next;        /* 前向指针 */
    GM_LIST_NODE *prev;        /* 后向指针 */
};

/* 链表管理器数据结构和类型定义 */
typedef struct
{
    GM_LIST_NODE* xHeadNode;    /* 头节点  */
    GM_SIZE       NumOfNodes;   /* 总节点数 */
} GM_LIST_OBJ;

/*******************************************************************************
** 函数名称：GM_List_Create
** 函数作用：链表创建
** 输入参数：无
** 输出参数：创建的链表指针，GM_NULL - 创建失败
** 使用范例：GM_LIST pxNewLinkedList = GM_List_Create();
** 函数备注：创建成功后会进行初始化
*******************************************************************************/
GM_LIST GM_List_Create()
{
    GM_LIST_OBJ* pxListObj;

    pxListObj = (GM_LIST_OBJ*)GM_Mem_Alloc(sizeof(GM_LIST_OBJ));

    if (GM_NULL == pxListObj)
    {
        return GM_NULL;
    }

    pxListObj->xHeadNode->prev = pxListObj->xHeadNode;
    pxListObj->xHeadNode->next = pxListObj->xHeadNode;
    pxListObj->NumOfNodes = 0;

    return (GM_LIST)pxListObj;
}

/*******************************************************************************
** 函数名称：GM_List_AddToTail
** 函数作用：向链表尾部添加节点
** 输入参数：pxLinkedList - 链表
**          pxNode       - 待插入节点
** 输出参数：插入是否成功
** 使用范例：GM_BOOL emResult = GM_List_AddToTail(&xLinkedList, &xNode);
** 函数备注：此节点若是已在链表中，返回错误，否则进行添加
*******************************************************************************/
GM_BOOL GM_List_AddToTail(GM_LIST list, GM_SIZE size, void* pdata)
{
    GM_LIST_OBJ*  pxListObj = (GM_LIST_OBJ*)list;
    GM_LIST_NODE* pxListNode = GM_NULL;

    /* 如果链表或者节点为空，返回错误 */
    if ((GM_NULL == pxListObj) ||
        (GM_NULL == pdata))
    {
        return GM_FALSE;
    }

    /* 创建数据节点 */
    pxListNode = GM_Mem_Alloc(sizeof(GM_LIST_NODE) + size);

    /* 判断数据节点是否创建成功 */
    if (GM_NULL == pxListNode)
    {
        return GM_FALSE;
    }

    if (GM_NULL == pxListObj->xHeadNode)
    {
        /* 无头结点，即空链表 */
        pxListObj->xHeadNode = pxListNode;
        pxListObj->xHeadNode->prev = pxListObj->xHeadNode;
        pxListObj->xHeadNode->next = pxListObj->xHeadNode;
        pxListObj->NumOfNodes = 1;
    }
    else
    {
        /* 非空链表 */
        pxListNode->prev = pxListObj->xHeadNode->prev;
        pxListNode->next = pxListObj->xHeadNode;
        pxListObj->xHeadNode->prev->next = pxListNode;
        pxListObj->xHeadNode->prev = pxListNode;
        pxListObj->NumOfNodes++;
    }

    return GM_TRUE;
}

/*******************************************************************************
** 函数名称：GM_List_AddToHead
** 函数作用：向链表头部添加节点
** 输入参数：pxLinkedList - 链表
**          pxNode       - 待插入节点
** 输出参数：插入是否成功
** 使用范例：GM_BOOL emResult = GM_List_AddToHead(&xLinkedList, &xNode);
** 函数备注：此节点若是已在链表中，返回错误，否则进行添加
*******************************************************************************/
GM_BOOL GM_List_AddToHead(GM_LIST list, GM_SIZE size, void* pdata)
{
    GM_LIST_OBJ*  pxListObj = (GM_LIST_OBJ*)list;
    GM_LIST_NODE* pxListNode = GM_NULL;

    /* 如果链表或者节点为空，返回错误 */
    if ((GM_NULL == pxListObj) ||
        (GM_NULL == pdata))
    {
        return GM_FALSE;
    }

    /* 创建数据节点 */
    pxListNode = GM_Mem_Alloc(sizeof(GM_LIST_NODE) + size);

    /* 判断数据节点是否创建成功 */
    if (GM_NULL == pxListNode)
    {
        return GM_FALSE;
    }

    if (GM_NULL == pxListObj->xHeadNode)
    {
        /* 无头结点，即空链表 */
        pxListObj->xHeadNode = pxListNode;
        pxListObj->xHeadNode->prev = pxListObj->xHeadNode;
        pxListObj->xHeadNode->next = pxListObj->xHeadNode;
        pxListObj->NumOfNodes = 1;
    }
    else
    {
        /* 非空链表 */
        pxListNode->prev = pxListObj->xHeadNode;
        pxListNode->next = pxListObj->xHeadNode->next;
        pxListObj->xHeadNode->next->prev = pxListNode;
        pxListObj->xHeadNode->next = pxListNode;
        pxListObj->NumOfNodes++;
    }

    return GM_TRUE;
}

/*******************************************************************************
** 函数名称：GM_LinkedList_Delete
** 函数作用：从链表中删除节点
** 输入参数：pxLinkedList - 链表
**          pxNode       - 待删除节点
** 输出参数：删除是否成功
** 使用范例：GM_BOOL emResult = GM_LinkedList_Delete(&xLinkedList, &xNode);
** 函数备注：此节点如果是已在链表中的节点，会删除，如果不在链表中，不执行删除，并返回错误
*******************************************************************************/
GM_BOOL GM_List_Delete(GM_LIST list, GM_SIZE size, void* pdata)
{
    GM_LIST_OBJ*  pxListObj = (GM_LIST_OBJ*)list;
    GM_LIST_NODE* pxListNode = GM_NULL;

    /* 如果链表或者节点为空，返回错误 */
    if ((GM_NULL == pxListObj) ||
        (GM_NULL == pdata))
    {
        return GM_FALSE;
    }

    /* 如果链表或者节点为空，返回错误 */
    if ((GM_NULL == pxLinkedList) || (GM_NULL == pxNode))
    {
        return GM_ERR;
    }
    else
    {
        if (GM_FALSE == GM_LinkedList_NodeInList(pxLinkedList, pxNode))
        {
            /* 如果节点不在链表中，返回错误 */
            return GM_ERR;
        }
        else
        {
            /* 如果节点在链表中，删除节点 */
            pxNode->prev->next = pxNode->next;
            pxNode->next->prev = pxNode->prev;
            pxNode->next = GM_NULL;
            pxNode->prev = GM_NULL;

            /* 链表节点数据总数减1 */
            pxLinkedList->NumOfNodes--;

            return GM_OK;
        }
    }
}

/*******************************************************************************
** 函数名称：GM_LinkedList_NodeInList
** 函数作用：判断节点是否在链表中
** 输入参数：pxLinkedList - 链表
**          pxNode       - 节点
** 输出参数：GM_TRUE - 节点在链表中，GM_FALSE - 节点不在链表中
** 使用范例：GM_BOOL blResult = GM_LinkedList_NodeInList(&xLinkedList, &xNode);
** 函数备注：
*******************************************************************************/
GM_BOOL GM_LinkedList_NodeInList(GM_LIST* const pxLinkedList,
                                 GM_LIST_NODE* const pxNode)
{
    GM_LIST_NODE* pxTemp;

    /* 如果链表或者节点为空，返回否 */
    if ((GM_NULL == pxLinkedList) || (GM_NULL == pxNode))
    {
        return GM_FALSE;
    }
    else
    {
        pxTemp = pxLinkedList->xHeadNode.next;
        while (pxTemp != &(pxLinkedList->xHeadNode))
        {
            if (pxTemp == pxNode)
            {
                return GM_TRUE;
            }
            pxTemp = pxTemp->next;
        }
        return GM_FALSE;
    }
}

/*******************************************************************************
** 函数名称：GM_LinkedList_GetListLength
** 函数作用：获取链表长度
** 输入参数：pxLinkedList - 链表
** 输出参数：GM_TRUE - 节点在链表中，GM_FALSE - 节点不在链表中
** 使用范例：size_t num = GM_LinkedList_GetListLength(&xLinkedList);
** 函数备注：不包括头节点，头节点非用户使用，不算在链表长度之内
*******************************************************************************/
GM_SIZE GM_LinkedList_GetListLength(GM_LIST* const pxLinkedList)
{
    return pxLinkedList->NumOfNodes;
}