linklist.c

多叉树实现

/**************************************************************************
**  Copyright (c) 2008 OCC, Inc.
**
**  Project: Link List
**  File:    linklist.c
**  Author:  Michael
**  Date:    10/31/2008
**
**  Purpose:
**    Api for link list.
**************************************************************************/


/* Include files. */
#include "linklist.h"


/* Macro constant definitions. */


/* Type definitions. */


/* Local function declarations. */


/* Macro API definitions. */


/* Global variable declarations. */


/**************************************************************************
**  Function Name: LinkListAddNode
**  Purpose:
**    Add a node to link list.
**  Parameters:
**    tLinkListNode *linkListNodeP - point to the node.
**    eLinkListAddType addType - Add action type.
**    void *dataP - Data of node to add.
**    void *dataCreateFunP - Function for create the data of node.
**  Return:
**    None.
**  Notes:
**    We must have a parent node to record the header of link list.
**    So you must use LinkListInitOrDestroy() to get a link list header.
**************************************************************************/

tLinkListNode *
LinkListAddNode(tLinkListNode *linkListNodeP, eLinkListAddType addType,
  void *dataCreateFunP, void *dataP)
{

    tLinkListNode *newNodeP;
    tLinkListNode *tmpNodeP;


    /* We must have a parent node to record the header of link list. */
    if ((dataCreateFunP == NULL) ||
      ((linkListNodeP == NULL) && (addType != eLINK_LIST_ADD_TYPE_CREATE_HEARDER)))
    {
        return (NULL);
    }
    newNodeP = LinkListNodeCreate(dataCreateFunP, dataP);
    if (newNodeP == NULL)
    {
        return (NULL);
    }

    switch (addType)
    {
        /* add young brother(next) node. */
        case eLINK_LIST_ADD_TYPE_ADD_Y_BROTHER:
            newNodeP->parentP = linkListNodeP->parentP;
            newNodeP->oldBrotherP = linkListNodeP;
            newNodeP->youngBrotherP = linkListNodeP->youngBrotherP;
            /* current node has a young brother node. */
            if (linkListNodeP->youngBrotherP != NULL)
            {
                linkListNodeP->youngBrotherP->oldBrotherP = newNodeP;
            }
            break;

        /* add old brother(previous) node. */
        case eLINK_LIST_ADD_TYPE_ADD_O_BROTHER:
            newNodeP->parentP = linkListNodeP->parentP;
            newNodeP->oldBrotherP = linkListNodeP->oldBrotherP;
            newNodeP->youngBrotherP = linkListNodeP;
            linkListNodeP->oldBrotherP = newNodeP;
            /*
            **  if current node is the first node of his list.And now
            **  add a new node to be his old brother,modify his parent
            **  node's child node pointer.
            */
            if ((linkListNodeP->oldBrotherP == NULL) &&
              (linkListNodeP->parentP != NULL))
            {
                linkListNodeP->parentP->childP = newNodeP;
            }
            break;

        /* add child node. */
        case eLINK_LIST_ADD_TYPE_ADD_CHILD:
            newNodeP->parentP = linkListNodeP;
            tmpNodeP = linkListNodeP->childP;
            if (tmpNodeP != NULL)
            {
                /*
                **  current node have child node(s),add to
                **  the youngest one.
                */
                for (;;tmpNodeP = tmpNodeP->youngBrotherP)
                {
                    if (tmpNodeP->youngBrotherP == NULL)
                    {
                        break;
                    }
                }
                newNodeP->oldBrotherP = tmpNodeP;
                newNodeP->youngBrotherP = NULL;
                tmpNodeP->youngBrotherP = newNodeP;
            }
            else
            {
                /* current node have no child node. */
                newNodeP->oldBrotherP = NULL;
                newNodeP->youngBrotherP = NULL;
            }
            break;

        case eLINK_LIST_ADD_TYPE_CREATE_HEARDER:
            /* for init to creat a link list header node. */;
            break;

        default:
            return (NULL);
            break;
    }

    return (newNodeP);

} /* End of LinkListAddNode() */



/**************************************************************************
**  Function Name: LinkListNodeCreate
**  Purpose:
**    Create a link list node.
**  Parameters:
**    void *dataCreateFunP - Function for create the data of node.
**    void *dataP - the data of new node.
**  Return:
**    None.
**  Notes:
**    None.
**************************************************************************/

tLinkListNode *
LinkListNodeCreate(void *dataCreateFunP, void *dataP)
{

    eOsRet ret;
    tLinkListNode *newNodeP;


    if (!dataCreateFunP)
    {
        return (NULL);
    }

    newNodeP = MEMALLOC(sizeof(tLinkListNode));
    if (newNodeP == NULL)
    {
        PRINTF("Alloc memory for link list node failed.\n");
        return (NULL);
    }
    memset (newNodeP, MEM_SET_DEFAULT_VALUE, sizeof(tLinkListNode));

    (*(DataCreateFunP)dataCreateFunP)(newNodeP, dataP);
    if (newNodeP->dataP == NULL)
    {
        MEMFREE(newNodeP);
        return (NULL);
    }
    newNodeP->childP = NULL;

    return (newNodeP);

} /* End of LinkListNodeCreate() */


/**************************************************************************
**  Function Name: LiniListNodeDelete
**  Purpose:
**    Delete a link list node.
**  Parameters:
**    tLinkListNode *deleteNodeP - Pointe to the node that will be delete.
**    void *dataDeleteFunP - Function for delete the data of node.
**  Return:
**    None.
**  Notes:
**    None.
**************************************************************************/

eOsRet
LiniListNodeDelete(tLinkListNode *deleteNodeP, void *dataDeleteFunP)
{

    eOsRet ret;


    ASSERT_POINTER(deleteNodeP);
    ASSERT_POINTER(dataDeleteFunP);

    if (deleteNodeP->childP != NULL)
    {
        ret = LinkListDelete(deleteNodeP->childP, dataDeleteFunP);
        ASSERT_RETURN(ret);
    }
    /*
    **  if current node has a old brother.then his old brother's young 
    **  brother pointer point to his young brother.
    **  if current node has no old brother.point his parent's child pointer
    **  point to his young brother.and set his young brother's old brother
    **  pointer to NULL.
    */
    if (deleteNodeP->oldBrotherP != NULL)
    {
        deleteNodeP->oldBrotherP->youngBrotherP = deleteNodeP->youngBrotherP;
    }
    else if (deleteNodeP->parentP != NULL)
    {
        deleteNodeP->parentP = deleteNodeP->youngBrotherP;
        if (deleteNodeP->youngBrotherP != NULL)
        {
            deleteNodeP->youngBrotherP->oldBrotherP = NULL;
        }
    }
    /* delete data of current node. */
    ret = (*(DataDeleteFunP)dataDeleteFunP)(deleteNodeP);
    ASSERT_RETURN(ret);
    /* free current node. */
    MEMFREE(deleteNodeP);

    return (eOS_RET_SUCCESS);

} /* End of LiniListNodeDelete() */



/**************************************************************************
**  Function Name: LinkListDelete
**  Purpose:
**    Destroy a link list node.
**  Parameters:
**    tLinkListNode *linkListNodeP - Point to link list header.
**    void *dataDeleteFunP - Function for delete the data of node.
**  Return:
**    None.
**  Notes:
**    None.
**************************************************************************/

eOsRet
LinkListDelete(tLinkListNode *linkListNodeP, void *dataDeleteFunP)
{

    eOsRet ret;


    ASSERT_POINTER(linkListNodeP);

    /* Delete brother node. */
    if (linkListNodeP->youngBrotherP != NULL)
    {
        ret = LinkListDelete(linkListNodeP->youngBrotherP, dataDeleteFunP);
        ASSERT_RETURN(ret);
    }
    /* Delete child node. */
    if (linkListNodeP->childP != NULL)
    {
        LinkListDelete(linkListNodeP->childP, dataDeleteFunP);
        ASSERT_RETURN(ret);
    }
    /* Delete itself. */
    ret = LiniListNodeDelete(linkListNodeP, dataDeleteFunP);
    ASSERT_RETURN(ret);

    return (eOS_RET_SUCCESS);

} /* End of LinkListDelete() */


/**************************************************************************
**  Function Name: LinkListNodeDump
**  Purpose:
**    Dump link list node.
**  Parameters:
**    tLinkListNode *linkListNodeP - Pointer to the link list node to dump.
**    void *dataDumpFunP - Function for dump the data of node.
**  Return:
**    None.
**  Notes:
**    None.
**************************************************************************/

eOsRet
LinkListNodeDump(tLinkListNode *linkListNodeP, void *dataDumpFunP)
{

    ASSERT_POINTER(linkListNodeP);
    ASSERT_POINTER(dataDumpFunP);

    (*(DataDumpFunP)dataDumpFunP)(linkListNodeP->dataP);

    return (eOS_RET_SUCCESS);